[Solidity] Merkle Tree

Merkle Tree

url: https://solidity-by-example.org/app/merkle-tree/

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.17;

contract MerkleProof {
    function verify(
        bytes32[] memory proof,
        bytes32 root,
        bytes32 leaf,
        uint index
    ) public pure returns (bool) {
        bytes32 hash = leaf;

        for (uint i = 0; i < proof.length; i++) {
            bytes32 proofElement = proof[i];

            if (index % 2 == 0) {
                hash = keccak256(abi.encodePacked(hash, proofElement));
            } else {
                hash = keccak256(abi.encodePacked(proofElement, hash));
            }

            index = index / 2;
        }

        return hash == root;
    }
}

contract TestMerkleProof is MerkleProof {
    bytes32[] public hashes;

    constructor() {
        string[4] memory transactions = [
            "alice -> bob",
            "bob -> dave",
            "carol -> alice",
            "dave -> bob"
        ];

        for (uint i = 0; i < transactions.length; i++) {
            hashes.push(keccak256(abi.encodePacked(transactions[i])));
        }

        uint n = transactions.length;
        uint offset = 0;

        while (n > 0) {
            for (uint i = 0; i < n - 1; i += 2) {
                hashes.push(
                    keccak256(
                        abi.encodePacked(hashes[offset + i], hashes[offset + i + 1])
                    )
                );
            }
            offset += n;
            n = n / 2;
        }
    }

    function getRoot() public view returns (bytes32) {
        return hashes[hashes.length - 1];
    }

    /* verify
    3rd leaf
    0xdca3326ad7e8121bf9cf9c12333e6b2271abe823ec9edfe42f813b1e768fa57b

    root
    0xcc086fcc038189b4641db2cc4f1de3bb132aefbd65d510d817591550937818c7

    index
    2

    proof
    0x8da9e1c820f9dbd1589fd6585872bc1063588625729e7ab0797cfc63a00bd950
    0x995788ffc103b987ad50f5e5707fd094419eb12d9552cc423bd0cd86a3861433
    */
}

머클 트리는 암호화 연산을 통해 블록 트랜잭션 데이터들의 무결성을 검증하기 위해 사용된다.
머클 트리는 트리 구조로 되어있어 가장 최상위 루트 값만 저장한다. 최상위 값인 머클 루트는 하위 트랜잭션 해쉬 값들의 연산으로 이루어져, 이 중 하나의 값만 변경되더라도 머클 루트가 변경되게 된다. 따라서, 머클 트리는 머클 루트 값을 통해 하위의 트랜잭션들의 무결성을 검증하는데 사용된다.
머클 트리는 다음과 같은 과정으로 생성할 수 있다.

• 트랜잭션 값 해시화

for (uint i = 0; i < transactions.length; i++) {
	hashes.push(keccak256(abi.encodePacked(transactions[i])));
}

• 다음 트랜잭션 해시값과 연결하고 다시 해싱
  이 과정을 반복하여, 최종적으로 머클 루트를 계산할 수 있다.

uint n = transactions.length;
uint offset = 0;

while (n > 0) {
	for (uint i = 0; i < n - 1; i += 2) {
		hashes.push(
			keccak256(
				abi.encodePacked(hashes[offset + i], hashes[offset + i + 1])
			)
         );
    }
    offset += n;
    n = n / 2;
}

• 트랜잭션 인덱스로 구분한 머클 트리 구조

   6
 4   5
0 1 2 3

그리고, 특정 트랜잭션의 무결성을 검증하는 과정은 다음과 같다.

• 검증을 위한 bytes32[] proof, root (머클 루트 값), leaf (검증하려는 트랜잭션 해시 값), index (검증하려는 트랜잭션 index 값)을 입력한다.

/* verify
    proof
    0x8da9e1c820f9dbd1589fd6585872bc1063588625729e7ab0797cfc63a00bd950
    0x995788ffc103b987ad50f5e5707fd094419eb12d9552cc423bd0cd86a3861433
    
    root
    0xcc086fcc038189b4641db2cc4f1de3bb132aefbd65d510d817591550937818c7
    
    3rd leaf
    0xdca3326ad7e8121bf9cf9c12333e6b2271abe823ec9edfe42f813b1e768fa57b

    index
    2
*/

• leaf (트랜잭션 index에 해당하는 해시 값)부터 시작해서 머클 루트까지 계산한다.

bytes32 hash = leaf;

for (uint i = 0; i < proof.length; i++) {
	bytes32 proofElement = proof[i];

	if (index % 2 == 0) {
		hash = keccak256(abi.encodePacked(hash, proofElement));
    } else {
        hash = keccak256(abi.encodePacked(proofElement, hash));
    }
    index = index / 2;
}

• 최종적으로 계산한 머클 루트가 기존의 머클 루트와 동일한지 비교한다.

return hash == root;

해당 머클 트리 예제는 주어진 트랜잭션 샘플로 머클 트리를 구현하고, 구현된 머클 트리에서 트랜잭션에 대한 무결성을 검증할 수 있는 검증 로직까지 구현했다. 추가적으로, 동작 과정에서 단계별로 자세히 확인하기 위해 테스트 코드를 생성했다.

• 트랜잭션 해시 값 확인

/*
	"alice -> bob", hash => 0x78a93af7ef9f1380d64a61c552cbefc298da07acb65530265b8ade6ebe8218c4
	"bob -> dave", hash => 0x92ae03b807c62726370a4dcfecf582930f7fbb404217356b6160b587720d3ba7
	"carol -> alice", hash => 0xdca3326ad7e8121bf9cf9c12333e6b2271abe823ec9edfe42f813b1e768fa57b
	"dave -> bob" hash => 0x8da9e1c820f9dbd1589fd6585872bc1063588625729e7ab0797cfc63a00bd950
*/

function getHash(string calldata inputTx) public pure returns (bytes32){
        return keccak256(abi.encode(inputTx));
}

/*
	[0], [1] => [4]
	0x78a93af7ef9f1380d64a61c552cbefc298da07acb65530265b8ade6ebe8218c4
	0x92ae03b807c62726370a4dcfecf582930f7fbb404217356b6160b587720d3ba7
	=> 0x995788ffc103b987ad50f5e5707fd094419eb12d9552cc423bd0cd86a3861433

	[2], [3] => [5]
	0xdca3326ad7e8121bf9cf9c12333e6b2271abe823ec9edfe42f813b1e768fa57b
	0x8da9e1c820f9dbd1589fd6585872bc1063588625729e7ab0797cfc63a00bd950
	=> 0x2f71627ef88774789455f181c533a6f7a68fe16e76e7a50362af377269aabfee

	[4], [5] => [6] (merkle root)
	0x995788ffc103b987ad50f5e5707fd094419eb12d9552cc423bd0cd86a3861433
	0x2f71627ef88774789455f181c533a6f7a68fe16e76e7a50362af377269aabfee
	=> 0xcc086fcc038189b4641db2cc4f1de3bb132aefbd65d510d817591550937818c7
*/

function getMerkleHash(bytes32 _tx1, bytes32 _tx2) public pure returns (bytes32){
	return keccak256(abi.encodePacked(_tx1, _tx2));
}

동작을 확인하기 위한 테스트 코드 추가한 전체 소스 코드는 github에 업로드했다.
https://github.com/jh-cha/SolidityByExample/blob/main/src/merkleTree.sol