Go로 만드는 블록체인 part 7 - Merkle Tree

이전 포스트와 비슷한 맥락에서,

이번엔 다른 개념을 사용하여 조금 더 최적화해보도록 하겠다.

 

Block Structure

우선 Bitcoin의 블록 구조를 살펴보도록 하겠다.

 

block structure

블록은 크게 Header와 Body로 나누어 살펴볼 수 있다.

이 둘은 서로 정보를 비교하며 무결성을 높이게 된다.

 

Bitcoin의 block body에는 Transaction이 담겨있다.

아래의 표는 Bitcoin의 block header 구조이다.

Version	버전
Target Bits	작업 증명 난이도
Previous Block Hash	이전 블록의 해시
Time Stamp	블록 생성 시간
Merkle Root	트랜잭션 해시 값
Nonce	작업 증명을 위한 임의의 값

type Block struct {
	TimeStamp	int32 `validate:"required"`
	Hash		[]byte `validate:"required"`
	PrevHash	[]byte `validate:"required"`
	Transactions	[]*Transaction `validate:"required"`
	Nonce		int `validate:"min=0"`
}

현재 Block 구조체의 모습이다.

타겟 Bits의 값은 나중에 넣어줄 예정이다.

Transactions	[]*Transaction

위 표에서의 Merkle Root를 Transactions 필드가 담당하고 있다.

그렇다면 Merkle Root란 무엇일까?

Merkle Tree란?

merkle root를 알기 위해선 우선 merkle tree가 무엇인지 알아야 한다.

Merkle Tree는 Block에 포함된 Transaction들을 나무 형태로 요약한 것이다.

 

수많은 거래들을 짝지어 해싱하고 합쳐나가며 최종적으로 하나의 Merkle Root를 구하게 된다.

이렇게 다수의 거래내역들을 하나로 합친 Merkle Root를 Block의 Header에 담아 용량을 절약할 수 있게 된다.

Merkle Tree

Merkle Tree는 Root를 구하기 전까지 위 이미지처럼 토너먼트 모양으로 과정이 반복된다.

가장 먼저 Tx들을 SHA-256 암호화 기술을 사용하여 해싱하고, 그 값들을 2개씩 짝지어 다시 해싱하여 하나의 노드로 만든다. 그다음 계속해서 2개씩 짝지어 모든 노드들이 하나로 합쳐질 때까지 반복하여 Merkle Root를 구해낸다.

 

그렇기 때문에 머클 루트만 있다면 해당 블록에 포함된 거래들의 진위여부를 알 수 있다.

특정 거래내역의 증명을 위해 모든 거래내역을 탐색할 필요가 없이 Merkle Root만 있으면 되기 때문에

블록체인 자체의 효율이 상당히 높아진다.

 

이제 코드를 작성해보도록 하겠다.

Merkle Tree의 구현은 

https://github.com/cbergoon/merkletree

GitHub - cbergoon/merkletree: A Merkle Tree implementation written in Go.

위 레포를 참고하였다.

 

Type MerkleTree

// MerkleTree is the container for the tree. It holds a pointer to the root of the tree,
// a list of pointers to the leaf nodes, and the merkle root.
type MerkleTree struct {
	Root         *Node
	merkleRoot   []byte
	Leafs        []*Node
}

Type Node

// Node represents a node, root, or leaf in the tree. It stores pointers to its immediate
// relationships, a hash, the content stored if it is a leaf, and other metadata.
type Node struct {
	Tree		*MerkleTree
	Parent		*Node
	Left		*Node
	Right		*Node
	Hash		[]byte
}

각각의 Node들이 잎을 구성하며, 그 잎들이 모여 Merkle Tree를 구성하게 된다.

Root 값은 Merkle Tree 구조체 내에 저장한다.

Function NewMerkleNode

// Creates a new Merkle tree node
func NewMerkleNode(left, right *Node, data []byte) *Node {
	mNode := Node{}

	if left == nil && right == nil {
		hash := sha256.Sum256(data)
		mNode.Hash = hash[:]
	} else {
		hashes := append(left.Hash, right.Hash...)
		hash := sha256.Sum256(hashes)
		mNode.Hash = hash[:]
		left.Parent = &mNode
		right.Parent = &mNode
	}

	mNode.Left = left
	mNode.Right = right

	return &mNode
}

Node를 반환해주는 함수이다.

if left == nil && right == nil {
    hash := sha256.Sum256(data)
    mNode.Hash = hash[:]
}

연결된 잎이 없다면 해싱하여 반환하고,

else {
    hashes := append(left.Hash, right.Hash...)
    hash := sha256.Sum256(hashes)
    mNode.Hash = hash[:]
    left.Parent = &mNode
    right.Parent = &mNode
}

연결된 잎이 있다면 해당 잎들을 합쳐서 해싱해준다.

Function NewMerkleTree

// Creates a new Merkle tree
func NewMerkleTree(data [][]byte) *MerkleTree {
	var nodes []*Node

	// Make it even
	if len(data)%2 != 0 {
		data = append(data, data[len(data)-1])
	}

	// Hash transactions
	for _, tx := range data {
		node := NewMerkleNode(nil, nil, tx)
		nodes = append(nodes, node)
	}

	for i := 0; i < len(data)/2; i++ {
		var newLevel []*Node

		for j := 0; j < len(nodes); j += 2 {
			node := NewMerkleNode(nodes[j], nodes[j+1], nil)
			newLevel = append(newLevel, node)
		}

		nodes = newLevel
	}

	mTree := MerkleTree{nodes[0], nodes[0].Hash, nodes}
	return &mTree
}

그렇게 만든 Node들을 기반으로 Tree를 반환하는 친구이다.

// Make it even
if len(data)%2 != 0 {
    data = append(data, data[len(data)-1])
}

쌍을 지어야하기 때문에 거래내역의 개수는 짝수여야만 한다.

그래서 만약 짝수가 아니라면 가장 마지막 거래내역을 복제하여 추가한다.

// Hash transactions
for _, tx := range data {
    node := NewMerkleNode(nil, nil, tx)
    nodes = append(nodes, node)
}

그 다음 모든 Transaction을 해싱해둔다.

for i := 0; i < len(data)/2; i++ {
    var newLevel []*Node

    for j := 0; j < len(nodes); j += 2 {
        node := NewMerkleNode(nodes[j], nodes[j+1], nil)
        newLevel = append(newLevel, node)
    }

    nodes = newLevel
}

그 후 토너먼트 방식으로 반복하며 Root를 구해낸다.

func (pow *ProofOfWork) prepareData(nonce int) []byte {
	data := bytes.Join(
		[][]byte{
			[]byte(pow.block.PrevHash),
			pow.block.HashTransactions(),
			IntToHex(int64(pow.block.TimeStamp)),
			IntToHex(int64(targetBits)),
			IntToHex(int64(nonce)),
		},
		[]byte{},
	)
	return data
}

이제 머클트리는 작업 증명 과정에서 사용된다.

// Hash transactions
func (b *Block) HashTransactions() []byte {
	var transactions [][]byte

	for _, tx := range b.Transactions {
			transactions = append(transactions, tx.Serialize())
	}
	mTree := NewMerkleTree(transactions)
	
	return mTree.merkleRoot
}

먼저 인코딩해준 후, Merkle Tree를 반환받아 Root를 리턴해준다.

 

 

 

자세한 코드는 아래에서 확인할 수 있다.

 

https://github.com/hou27/blockchain_go/tree/part7

GitHub - hou27/blockchain_go: Making a Cryptocurrency with GO.

---

참고자료

 

blockchain block structure

쉽게 설명하는 블록체인

Bitcoin thesis

investopedia - Merkle Tree

BRILLIANT - Merkle Tree

cbergoon - merkle tree