머클경로 편집하기

'''머클경로'''<!--머클 경로, 머클패스, 머클 패스-->(Merkle path)는 어떤 거래의 진위를 따질 때 이를 검증하는 과정을 말한다. [[머클루트]]가 주어진다면, 더 쉽게 검증할 수 있다.

==개요==
머클경로는 [[풀노드]]로부터 정보를 받아 [[해시함수]]에 대입시켜 사용자가 해시 값의 상대값을 알아가면서 계속 해시를 진행해 나갈 수 있게 하는 것이다.

==머클트리==
[[파일:머클트리.png|썸네일|400픽셀|머클트리]]
머클트리는 ‘트리구조’를 형성하고 있는 [[암호화]] 과정이라고 할 수 있다. 꼭대기에 위치한 최종 값을 '루트', 하부의 값들을 '리프'라고 칭한다. 8개 거래에 대한 머클트리를 예시로 들자. 위 그림과 같이 거래에 대한 해시값이 Hash1부터 Hash8과 같이 '리프'가 이어져 있고, 이를 두 개씩 묶어 더한 후 같은 방식으로 진행하여 최종 값인 머클루트를 얻는다. (Hash9 값은 (Hash1 + Hash2)의 sha256 해시를 2번 취한 값 ) 

[[머클루트]](Merkle Root)란, 단어 속 ‘[[루트]](root)’에서 알 수 있듯이 뿌리와 같은 결과로써 하나의 최종 값을 의미하며, 그림상으로는 맨 위에 해당하는 값이 된다.

이 트리를 보면서 ‘거래가 홀수일 경우는 어떻게 되지?’라는 의문이 생길 수 있다. 이러한 경우 맨 마지막 거래를 복사하여 거래를 짝수개로 만들어 사용하는 원칙으로 이용되고 있다. (이러한 경우를 균형트리(balanced tree))

머클트리를 보면서 ‘거래의 원본이 그대로 저장이 안 되고 해시값을 이용하는 것이 왜 필요한가?’에 대한 의문이 들 수 있지만, 해시의 쓰임새를 다시 한번 생각해 봤을 때, 위변조를 한 번에 알 수 있다는 장점이 있기에 머클루트는 매우 중요하다. 즉, 블록 안의 300개의 데이터 중 1개의 데이터, 혹은 그 1개의 데이터 중 글자 하나만 바뀌어도 해시값인 머클루트는 완전히 다른 값이 나온다는 것을 인지한다면 머클루트의 효과를 확실히 알 수 있을 것이다. (참고로 이더리움의 경우, [[머클패트리샤 트리]](Merkle-Patricia tree(trie))를 이용하여 '상태(state)'의 정보를 저장한다)

머클트리의 장점은 위변조 가능성을 넘어서, 빠른 탐색을 용이하게 만들어준다. 머클경로를 이용한다면, 머클루트를 알고 있을 때, ‘어떠한 거래가 들어있다는 확인’을 하는 절차는 매우 용이하다.<ref name="브런치">Skkrypto, 〈[https://brunch.co.kr/@skkrypto/1 Bitcoin#5: 풀(Pool)과 머클 루트]〉, 《브런치》, 2018-11-01</ref>{{자세히|머클트리}}

==예제==
[[파일:머클트리 예시.png|썸네일|400픽셀|머클트리 예시]]
A는 본인의 거래 Tx1이 [[블록]]에 담겨있는지 확인하고자 한다면, 풀노드(full-node)로부터 블록헤더와, 머클경로를 전달받는다. 이때, 블록헤더 중 머클루트와 머클경로를 통해 Tx1의 포함 여부를 확인한다. 이어서 Tx1이 들어있다는 것을 확인해야 한다.

Hash2, Hash10, Hash14 만 있으면 머클루트를 직접 계산하여 도출할 수 있다. 즉, A는 Tx1을 이용하여 Hash1을 만들면, 머클경로에 포함된 Hash2를 더하며 Hash9를 얻을 수 있다. 이후 Hash9과 머클경로에 포함되어 있던 Hash10을 통해 Hash13을 얻을 수 있고 같은 방식으로 Hash14를 통해 머클루트를 직접 구할 수 있다. 이 결괏값을 '전달받은 머클루트'와 비교하여 일치한다면 본인 거래 Tx1이 블록에 담겨있다는 것을 확인할 수 있을 것이다. 이는 log2(8)=3개의 머클경로가 포함되어있음을 확인할 수 있다. 

이는 [[SPV]](Simplified Payment Verification) [[노드]]가 쉽고 빠르게 특정 거래를 찾을 수 있게 도와준다.<ref name="브런치"></ref>

===C===
;머클트리 생성
 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는 각 트리레벨에 맞춰 삽입해야할 첫번째 위치를 가리킨다.
             j += nSize;
         }
         return (vMerkleTree.empty() ? 0 : vMerkleTree.back());
     }
 }

위에서 설명한 소스코드를 활용하여 7개의 [[트랜잭션]]으로 1차원 [[벡터]](vector)를 구현한다면 아래와 같은 그림이 된다.
* H(tx[0]): 0번 트랜잭션(1번째 트랜잭션)에 대한 해시값
* H(66): 6번 트랜잭션(7번째 트랜잭션)에 대한 해시와 6번 트랜잭션에 대한 해시를 이어붙인 값을 다시 해시한 값
2개씩 묶어서 새로운 해시를 생성해야 하는데 7개의 트랜잭션이므로 홀수개다. 따라서 6번 트랜잭션(7번째 트랜잭션)은 자기 자신과 해시하는 방식으로 구현한다. 2개씩 해시하고 벡터에 삽입하는 과정을 반복하면 벡터의 마지막에는 머클 루트가 자리잡게 된다.

[[파일:머클트리 1차원 벡터.png|800픽셀|가운데|]]

;머클트리의 증명
위변조 검사를 할 때 필요한 노드를 추출하는 코드이다. 모든 트랜잭션들을 검증할 필요는 없으며, 필요한 트랜잭션 해시들만 선별한다.

 // 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;
 }

아래는 위변조를 검사하는 코드이다. 해시할 때의 규칙은 짝수에 해당하는 인덱스를 가진 해시는 다음에 해시될 때 좌측에 위치해야 한다는 것이고 홀수에 해당하는 인덱스를 가진 해시는 우측에 위치해야 한다는 것이다. 즉, [[SHA256]](짝수인덱스를 가진 트랜잭션 해시, 홀수인덱스를 가진 트랜잭션 해시) 이렇게 구성된다는 뜻이다. 해시될 때의 순서에 따라 결과값은 완전 달라지기 때문에 순서 규칙을 지켜주는 것은 중요하다.

 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
 }
<ref>aeharvlee, 〈[https://medium.com/pocs/bitcoin01-01-%EB%B9%84%ED%8A%B8%EC%BD%94%EC%9D%B8-%EC%BD%94%EC%96%B4-%EC%86%8C%EC%8A%A4%EC%BD%94%EB%93%9C%EB%A1%9C-%EC%82%B4%ED%8E%B4%EB%B3%B4%EB%8A%94-%EB%A8%B8%ED%81%B4-%ED%8A%B8%EB%A6%AC-3b93d59c989b 비트코인 코어 소스코드로 살펴보는 머클 트리]〉, 《미디움》, 2018-06-07</ref><ref>세진쨩, 〈[https://sejinik.tistory.com/120 머클트리(Merkle tree)에 대해 알아보자]〉, 《티스토리》, 2018-10-04</ref>

{{각주}}

==참고자료==
* 에코버스, 〈[https://blog.naver.com/ecoverse/221426267794 블록체인상식(17) “머클 트리(Merkle Tree)” - 진위(眞僞)를 판단하는, 작지만 알찬 나무]〉, 《네이버 블로그》, 2018-12-24
* Skkrypto, 〈[https://brunch.co.kr/@skkrypto/1 Bitcoin#5: 풀(Pool)과 머클 루트]〉, 《브런치》, 2018-11-01
* aeharvlee, 〈[https://medium.com/pocs/bitcoin01-01-%EB%B9%84%ED%8A%B8%EC%BD%94%EC%9D%B8-%EC%BD%94%EC%96%B4-%EC%86%8C%EC%8A%A4%EC%BD%94%EB%93%9C%EB%A1%9C-%EC%82%B4%ED%8E%B4%EB%B3%B4%EB%8A%94-%EB%A8%B8%ED%81%B4-%ED%8A%B8%EB%A6%AC-3b93d59c989b 비트코인 코어 소스코드로 살펴보는 머클 트리]〉, 《미디움》, 2018-06-07
* 세진쨩, 〈[https://sejinik.tistory.com/120 머클트리(Merkle tree)에 대해 알아보자]〉, 《티스토리》, 2018-10-04

==같이 보기==
* [[머클루트]]
* [[머클트리]]

{{블록체인 기술|토막글}}