| 최신판 |
당신의 편집 |
| 2번째 줄: |
2번째 줄: |
| | | | |
| | ==개요== | | ==개요== |
| − | 머클경로는 [[풀노드]]로부터 정보를 받아 [[해시함수]]에 대입 시켜 사용자가 해시 값의 상대값을 알아가면서 계속 해시를 진행해 나갈 수 있게 하는 것이다. | + | 머클경로는 [[풀노드]]로부터 정보를 받아 [[해시함수]]에 대입시켜 사용자가 해시 값의 상대값을 알아가면서 계속 해시를 진행해 나갈 수 있게 하는 것이다. |
| | | | |
| | ==머클트리== | | ==머클트리== |
| | [[파일:머클트리.png|썸네일|400픽셀|머클트리]] | | [[파일:머클트리.png|썸네일|400픽셀|머클트리]] |
| − | 머클트리는 ‘트리구조’를 형성하고 있는 [[암호화]] 과정이라고 할 수 있다. 꼭대기에 위치한 최종 값을 '루트', 하부의 값들을 '리프'라고 칭한다. 8개 거래에 대한 머클트리를 예로, 위 그림과 같이 거래에 대한 해시값이 Hash1부터 Hash8과 같이 '리프'가 이어져 있고, 이를 두 개씩 묶어 더한 후 같은 방식으로 진행하여 최종 값인 머클루트를 얻는다. (Hash9 값은 (Hash1 + Hash2)의 sha256 해시를 2번 취한 값 )
| + | 머클 트리는 ‘트리구조’를 형성하고 있는 암호화 과정이라고 할 수 있다. 꼭대기에 위치한 최종 값을 '루트', 하부의 값들을 '리프'라고 칭한다. 8개 거래에 대한 머클 트리를 예시로 들자. 위 그림과 같이 거래에 대한 해시값이 Hash1부터 Hash8과 같이 '리프'가 이어져 있고, 이를 두 개씩 묶어 더한 후 같은 방식으로 진행하여 최종 값인 머클 루트를 얻는다. (Hash9 값은 (Hash1 + Hash2)의 sha256 해시를 2번 취한 값 ) |
| | | | |
| − | [[머클루트]](Merkle Root)란, 단어 속 ‘[[루트]](root)’에서 알 수 있듯이 뿌리와 같은 결과로써 하나의 최종 값을 의미하며, 그림상으로는 맨 위에 해당하는 값이 된다.
| + | 머클루트(Merkle Root)란, 단어 속 ‘root’에서 알 수 있듯이 뿌리와 같은 결과로써 하나의 최종 값을 의미하며, 그림상으로는 맨 위에 해당하는 값이 된다. |
| | | | |
| − | 이 트리를 보면서 거래가 홀수일 경우에 대하여 의문이 생길 수 있다. 이러한 경우 맨 마지막 거래를 복사하여 거래를 짝수개로 만들어 사용하는 원칙으로 이용되고 있다. (이러한 경우를 균형트리(balanced tree)) | + | 이 트리를 보면서 ‘거래가 홀수일 경우는 어떻게 되지?’라는 의문이 생길 수 있다. 이러한 경우 맨 마지막 거래를 복사하여 거래를 짝수개로 만들어 사용하는 원칙으로 이용되고 있다. (이러한 경우를 균형 트리(balanced tree)) |
| | | | |
| − | 머클트리를 보면서 거래의 원본이 그대로 저장이 안 되고 해시값을 이용하는 것에 필요성을 느끼지 못할 수 있지만, 해시의 쓰임새를 다시 한번 생각해 봤을 때, 위변조를 한 번에 알 수 있다는 장점이 있기에 머클루트는 매우 중요하다. 즉, 블록 안의 300개의 데이터 중 1개의 데이터, 혹은 그 1개의 데이터 중 글자 하나만 바뀌어도 해시값인 머클루트는 완전히 다른 값이 나온다는 것을 인지한다면 머클루트의 효과를 확실히 알 수 있을 것이다. (참고로 이더리움의 경우, [[머클패트리샤 트리]](Merkle-Patricia tree(trie))를 이용하여 '상태(state)'의 정보를 저장한다)
| + | 머클 트리를 보면서 ‘거래의 원본이 그대로 저장이 안 되고 해시값을 이용하는 것이 왜 필요한가?’에 대한 의문이 들 수 있지만, 해시의 쓰임새를 다시 한번 생각해 봤을 때, 위변조를 한 번에 알 수 있다는 장점이 있기에 머클 루트는 매우 중요하다. 즉, 블록 안의 300개의 데이터 중 1개의 데이터, 혹은 그 1개의 데이터 중 글자 하나만 바뀌어도 해시값인 머클 루트는 완전히 다른 값이 나온다는 것을 인지한다면 머클 루트의 효과를 확실히 알 수 있을 것이다. (참고로 이더리움의 경우, 머클 패트리샤 트리(Merkle-Patricia tree(trie))를 이용하여 '상태(state)'의 정보를 저장한다) |
| | | | |
| − | 머클트리의 장점은 위변조 가능성을 넘어서, 빠른 탐색을 용이하게 만들어준다. 머클경로를 이용한다면, 머클루트를 알고 있을 때, ‘어떠한 거래가 들어있다는 확인’을 하는 절차는 매우 용이하다.<ref name="브런치">Skkrypto, 〈[https://brunch.co.kr/@skkrypto/1 Bitcoin#5: 풀(Pool)과 머클 루트]〉, 《브런치》, 2018-11-01</ref>{{자세히|머클트리}}
| + | 머클 트리의 장점은 위변조 가능성을 넘어서, 빠른 탐색을 용이하게 만들어준다. 머클 패스(Merkle Path)를 이용한다면, 머클 루트를 알고 있을 때, ‘어떠한 거래가 들어있다는 확인’을 하는 절차는 매우 용이하다.<ref name="브런치">Skkrypto, 〈[https://brunch.co.kr/@skkrypto/1 Bitcoin#5: 풀(Pool)과 머클 루트]〉, 《브런치》, 2018-11-01</ref> |
| | | | |
| | ==예제== | | ==예제== |
| 22번째 줄: |
22번째 줄: |
| | Hash2, Hash10, Hash14 만 있으면 머클루트를 직접 계산하여 도출할 수 있다. 즉, A는 Tx1을 이용하여 Hash1을 만들면, 머클경로에 포함된 Hash2를 더하며 Hash9를 얻을 수 있다. 이후 Hash9과 머클경로에 포함되어 있던 Hash10을 통해 Hash13을 얻을 수 있고 같은 방식으로 Hash14를 통해 머클루트를 직접 구할 수 있다. 이 결괏값을 '전달받은 머클루트'와 비교하여 일치한다면 본인 거래 Tx1이 블록에 담겨있다는 것을 확인할 수 있을 것이다. 이는 log2(8)=3개의 머클경로가 포함되어있음을 확인할 수 있다. | | Hash2, Hash10, Hash14 만 있으면 머클루트를 직접 계산하여 도출할 수 있다. 즉, A는 Tx1을 이용하여 Hash1을 만들면, 머클경로에 포함된 Hash2를 더하며 Hash9를 얻을 수 있다. 이후 Hash9과 머클경로에 포함되어 있던 Hash10을 통해 Hash13을 얻을 수 있고 같은 방식으로 Hash14를 통해 머클루트를 직접 구할 수 있다. 이 결괏값을 '전달받은 머클루트'와 비교하여 일치한다면 본인 거래 Tx1이 블록에 담겨있다는 것을 확인할 수 있을 것이다. 이는 log2(8)=3개의 머클경로가 포함되어있음을 확인할 수 있다. |
| | | | |
| − | 이는 [[SPV]](Simplified Payment Verification) [[노드]]가 쉽고 빠르게 특정 거래를 찾을 수 있게 도와준다.<ref name="브런치"></ref> | + | 이는 [[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>
| |
| | | | |
| | {{각주}} | | {{각주}} |
| 103번째 줄: |
29번째 줄: |
| | * 에코버스, 〈[https://blog.naver.com/ecoverse/221426267794 블록체인상식(17) “머클 트리(Merkle Tree)” - 진위(眞僞)를 판단하는, 작지만 알찬 나무]〉, 《네이버 블로그》, 2018-12-24 | | * 에코버스, 〈[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 | | * 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
| |
| | | | |
| | ==같이 보기== | | ==같이 보기== |
| | * [[머클루트]] | | * [[머클루트]] |
| | * [[머클트리]] | | * [[머클트리]] |
| − | * [[트랜잭션]]
| |
| − | * [[노드]]
| |
| − | * [[SHA-256]]
| |
| | | | |
| − | {{블록체인 기술|검토 필요}} | + | {{블록체인 기술|토막글}} |
해시넷
