SPV 노드의 거래를 검증하기 위한 머클트리

머클트리는 다음그림과 같은 구조를 가지고 있습니다.

하기 그림에서 거래 A와 거래 B는 각각 고유의 해쉬값을 가지고 있고, 거래 A와B를 더하여 A+B의 해쉬값을 다시 계산하여 상위해쉬로 계산합니다. 이과정을 더이상 리프노드가 없을때까지 반복하게 되면 최종적으로 하나의 머클루트가 남게 됩니다. 이 머클루트가 블록의 헤더에 포함이 되어 SPV 노드에서 특정거래가 블록에 포함되어 있는지 검증하는데 사용됩니다.

[참조 : Mastering Bitcoin]

머클루트를 이용하여 특정거래가 해당블록에 포함되어 있는지 검증하기 위해서 머클패스가 사용됩니다.

예를 들어 하기 예에서 거래 K가 블록에 포함되어있는지 검증하기 위해 제공되는 머클패스는 H(L), H(IJ), H(MNOP), H(ABCDEFGH) 가 됩니다.

거래 K와 위의 머클패스를 제공받게 되면 어떤 노드라도 해쉬계산을 통해 머클루트를 계산해낼수 있고, 그값을 블록헤더에 포함된 머클루트와 비교하여 해당거래가 블록에 포함되어 있는지 검증할수 있습니다.

다음 그림에서 거래 K가 블록에 포함되어 있는지 검증하는 과정은 다음과 같습니다.

1. 거래 K와 머클패스로 제공된 Hash(L)을 사용하여 Hash(KL)을 계산

2. 머클패스로 제공된 Hash(IJ)와 계산된 Hash(KL)을 사용하여 Hash(IJHL) 계산

3. 계산된 Hash(IJKL)과 머클패스로 제공된 Hash(MNOP)를 사용하여 Hash(IJKLMNOP) 계산

4. 머클패스로 제공된 Hash(ABCDEFGH)와 계산된 Hash(IJKLMNOP)를 사용하여 Hash(ABCDEFGHIJKLMNOP)를 계산

5. 계산된 Hash(ABCDEFGHIJKLMNOP)와 헤더에 포함된 머클루트를 비교하여 동일한 값이면 거래 K가 블록에 포함되어있음이 증명됨

[참조 : Mastering Bitcoin]