가지고 있는 트랜잭션 중 트랜잭션 K(위 그림에서 녹색으로 표시)의 위변조가 의심되어 위변조 여부를 조사하려 한다. 이때 필요한 정보는 파란색으로 칠해진 4개의 해시값(H_L, H_IJ, H_ABCDEFGH), 그리고 머클 루트다.
실제 구현: 각 트랜잭션들의 해시(uint 256: SHA256의 결과값은 unsigned 256bit)를 저장하기 위해 vector<uint256> vMerkleTree가 존재한다.
트랜잭션 K의 위변조 여부를 조사하기 위해, K에 대한 해시값(녹색으로 표시)과 파란색으로 칠해진 4개의 해시값을 이용하면 머클 루트값(전체 거래내역 A~P에 대한 고유한 해시값)을 재구성할 수 있다. 두 개씩 차례로 이어붙인 후 그 값을 다시 해시하는 방식으로 루트값이 나올 때까지 반복한다. 전체 거래내역을 조회하는 것이 아닌, 단지 4개의 해시값만을 이용하여 위변조 여부를 검증할 수 있다는 건 매우 효율적이다.
실제 구현: 먼저 BuildMerkleTree( )메서드로 머클트리를 먼저 구성하고, 그 후 BuildMerkleBranch(매개변수: 위변조 검증을 원하는 트랜잭션의 해시) 메서드로 검증에 필요한 해시값들(위 그림 상에서 파란색으로 칠해진 값들)로 구성된 1차원 vector를 따로 제작한다. 이 vector를 머클 브랜치라 칭한다. 그 후 CheckMerkleBranch( ) 메서드로 머클 브랜치에 있는 해시값들, 그리고 위변조 검증을 원하는 트랜잭션을 가지고 검사를 진행한다.
class CBlock in main.h
// header: 흔히 말하는 블록 헤더의 정체다. 풀노드가 아닌 경량 클라이언트(light client)들은 블록 헤더만 저장하게 된다.
int nVersion;
uint256 hashPrevBlock;
uint256 hashMerkleRoot; // BuildMerkleTree()로 생성되는 머클루트
unsigned int nTime;
unsigned int nBits;
unsigned int nNonce;
// network and disk
vector<CTransaction> vtx; // 트랜잭션들을 저장할 때는 CTransaction 클래스의 벡터로 저장
// A block contains multiple transactions, held in vector vtx.
// memory only
mutable vector\<uint256> vMerkleTree;
CBlock::BuildMerkleTree( )
uint256 BuildMerkleTree() const
{
vMerkleTree.clear();
// 각 트랜잭션들의 해시값을 따로 저장하여 vMerkleTree 생성
foreach(const CTransaction& tx, vtx)
vMerkleTree.push_back(tx.GetHash());
int j = 0;
for (int nSize = vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
{
for (int i = 0; i < nSize; i += 2)
{
// 만약 트랜잭션이 짝수개가 아니라면, 마지막 트랜잭션의 해시는 자기 자신과 해시하게 된다.
int i2 = min(i+1, nSize-1);
// 트랜잭션의 해시를 2개씩 묶어서 다시 머클트리에 삽입한다.
vMerkleTree.push_back(Hash(BEGIN(vMerkleTree[j+i]), END(vMerkleTree[j+i]),
BEGIN(vMerkleTree[j+i2]), END(vMerkleTree[j+i2])));
}
j += nSize; // j는 각 트리레벨에 맞춰 삽입해야할 첫번째 위치를 가리킨다.
}
return (vMerkleTree.empty() ? 0 : vMerkleTree.back());
}
// nIndex로 위변조 여부를 검사할 특정 트랜잭션을 선택하고 머클 트리내의 트랜잭션 해시값과 연관된
// 트랜잭션의 해시들만 따로 추출하여 MerkleBranch를 생성한다.
vector\<uint256> GetMerkleBranch(int nIndex) const
{ // nIndex에 해당하는 트랜잭션 증명에 사용되는 노드들을 vMerkleBranch에 담는 작업을 진행
if (vMerkleTree.empty())
BuildMerkleTree();
vector\<uint256> vMerkleBranch;
int j = 0;
for (int nSize = vtx.size(); nSize > 1; nSize = (nSize + 1) / 2)
{
int i = min(nIndex^1, nSize-1); // nIndex^1의 값은 0 또는 1(반복)
vMerkleBranch.push_back(vMerkleTree[j+i]);
nIndex >>= 1;
j += nSize;
}
return vMerkleBranch;
}
static uint256 CheckMerkleBranch(uint256 hash, const vector\<uint256>& vMerkleBranch, int nIndex)
{
if (nIndex == -1)
return 0;
foreach(const uint256& otherside, vMerkleBranch)
{ // 해시되는 순서를 지켜주기 위해 아래의 두 경우를 구분하여 처리
if (nIndex & 1) // 트랜잭션의 인덱스가 홀수일 경우
hash = Hash(BEGIN(otherside), END(otherside), BEGIN(hash), END(hash));
else // 트랜잭션의 인덱스가 짝수일 경우
hash = Hash(BEGIN(hash), END(hash), BEGIN(otherside), END(otherside));
nIndex >>= 1; // 해시되는 순서를 맞춰준다.
}
return hash; // it should be merkleRoot
}