티스토리 뷰
본 게시글에서는 저서 '밑바닥부터 시작하는 비트코인'의 Python으로 작성된 예제 코드를 Go로 컨버팅 하여 작성하였습니다.
📺시리즈
2023.08.25 - [블록체인/Bitcoin] - 밑바닥부터 시작하는 비트코인 - 1장 유한체
2023.08.27 - [블록체인/Bitcoin] - 밑바닥부터 시작하는 비트코인 - 2장 타원곡선
2023.08.30 - [블록체인/Bitcoin] - 밑바닥부터 시작하는 비트코인 - 3장 타원곡선 암호
2023.09.02 - [블록체인/Bitcoin] - 밑바닥부터 시작하는 비트코인 - 4장 직렬화
2023.09.05 - [블록체인/Bitcoin] - 밑바닥부터 시작하는 비트코인 - 5장 트랜잭션
2023.09.11 - [블록체인/Bitcoin] - 밑바닥부터 시작하는 비트코인 - 6장 스크립트
2023.09.16 - [블록체인/Bitcoin] - 밑바닥부터 시작하는 비트코인 - 7장 트랜잭션 검증과 생성
2023.09.20 - [블록체인/Bitcoin] - 밑바닥부터 시작하는 비트코인 - 8장 p2sh 스크립트
2023.09.21 - [블록체인/Bitcoin] - 밑바닥부터 시작하는 비트코인 - 9장 블록
2024.01.08 - [블록체인/Bitcoin] - 밑바닥부터 시작하는 비트코인 - 10장 네트워킹
🐲 전체 코드
GitHub - piatoss3612/bitcoin-from-scratch: 밑바닥부터 시작하는 비트코인을 읽고 Go로 구현해보는 프로젝
밑바닥부터 시작하는 비트코인을 읽고 Go로 구현해보는 프로젝트. Contribute to piatoss3612/bitcoin-from-scratch development by creating an account on GitHub.
github.com
🥅 학습 목표
1. 머클트리와 머클트리의 성질에 대해 알아봅니다.
2. 머클블록과 단순 지급 검증에 대해 알아봅니다.
🌲1. 머클트리
머클트리는 포함증명을 효율적으로 탐색할 수 있도록 고안된 자료구조입니다. 포함증명이란, 특정 트랜잭션이 블록에 포함되었는지 여부를 확인하기 위해 필요한 일련의 데이터를 의미합니다.
머클트리를 구성하기 위해 순서 리스트와 해시함수가 필요합니다. 비트코인에서 순서 리스트는 트랜잭션 해시 목록을 가리키며 해시 함수는 sha256 함수를 의미합니다.
트리에서 맨 아래의 노드를 단말 노드(terminal node) 또는 잎사귀 노드(leaf node)라고 하며 단말 노드 외에는 내부 노드(internal node)라고 합니다. 단말 노드는 부모 레벨을 형성하기 위해 결합되며, 부모 레벨을 결합하여 머클루트를 구할 수 있습니다.
1.1 머클부모
두 개의 해시값이 주어지면 이를 이어 붙여 또 다른 해시값을 구한 것을 머클 부모라고 합니다.
H = 해시함수
P = 부모 해시값
L = 왼쪽 해시값
R = 오른쪽 해시값
P = H(L||R)
* ||은 L과 R을 이어 붙임(concat)을 의미
1.2 머클부모 레벨
리스트에 있는 모든 해시값에 대해 부모 해시값을 구한 것을 머클부모 레벨이라고 합니다.
짝수 개의 해시값이 있는 경우
짝수 개의 해시값이 있는 경우는 순서대로 두 개씩 짝지어 머클부모를 만들어주면 머클부모 레벨을 손쉽게 구할 수 있습니다.
홀수 개의 해시값이 있는 경우
위와 같이 홀수 개의 해시값으로 머클부모 레벨을 만드는 경우에는 마지막 해시값을 복사 붙여 넣기 하여 리스트의 항목을 짝수 개로 만들어 줍니다. 머클부모 레벨의 항목 수는 항상 해시값의 수를 절반으로 나눈 값을 반올림한 수가 됩니다.
1.3 머클루트
머클부모 레벨을 반복해서 계산하다 보면 하나의 부모 해시값만 남게 되는데, 이렇게 최종으로 남게 되는 해시값을 머클루트라고 합니다.
블록에서 머클루트를 검증하는 메서드를 다음과 같이 작성했습니다. 머클루트를 계산하고 검증하는 과정에서 엔디언 문제에 주의해야 합니다.
type Block struct {
Version int
PrevBlock string
MerkleRoot string
Timestamp int
Bits int
Nonce int
TxHashes [][]byte // 새로 추가된 필드: 트랜잭션 해시 목록
}
func (b Block) ValidateMerkleRoot() (bool, error) {
if len(b.TxHashes) == 0 {
return false, errors.New("tx hashes is empty")
}
hashes := make([][]byte, len(b.TxHashes))
for i, txHash := range b.TxHashes {
hashes[i] = utils.ReverseBytes(txHash) // 1. 머클루트를 계산하기 위해 트랜잭션 해시를 리버스
}
root := utils.MerkleRoot(hashes)
revRoot := utils.ReverseBytes(root) // 2. 계산된 머클루트를 리버스
return strings.Compare(hex.EncodeToString(revRoot), b.MerkleRoot) == 0, nil
}1.4 머클트리 활용하기
앞서 말씀드렸다시피 머클트리는 포함증명을 만들거나 확인할 때 사용됩니다. 특정 트랜잭션이 블록에 포함되어 있는지 확인하기 위해서 모든 트랜잭션을 알 필요가 없습니다. 이는 특히 블록체인의 모든 데이터를 가지고 있지 않은 라이트 노드에서 유용합니다.
어떤 블록에 두 개의 트랜잭션 해시값 HK와 HN이 들어있는지 궁금하고 머클트리의 구조가 다음과 같은 경우, 머클루트를 구하여 검증하기 위해 필요한 값은 다음과 같습니다.
HL, HM, HIJ, HOP, HABCDEFGH
1. HK와 HL을 알면 HKL을 구할 수 있습니다.
2. HM과 HN을 알면 HMN을 구할 수 있습니다.
3. HIJ와 1에서 구한 HKL을 알면 HIJKL을 구할 수 있습니다.
4. 2에서 구한 HMN과 HOP를 알면 HMNOP를 구할 수 있습니다.
5. 3과 4에서 구한 HIJKL과 HMNOP를 알면 HIJKLMNOP를 구할 수 있습니다.
6. HABCDEFGH와 5에서 구한 HIJKLMNOP를 알면 HABCDEFGHIJKLMNOP를 구할 수 있습니다.
7. 6에서 구한 머클루트를 블록의 머클루트와 비교하여 HK와 HN이 블록에 포함되어 있는지 검증합니다.
1.5 머클트리 구현
머클트리를 표현하기 위한 MerkleTree 구조체를 다음과 같이 정의했습니다. 머클트리의 최대 깊이를 계산하여 머클부모 레벨과 각 레벨에 필요한 원소의 수만큼의 크기로 초기화된 슬라이스를 생성한 뒤, MerkleTree 인스턴스를 생성하여 반환합니다.
type MerkleTree struct {
Total int // 리프 노드 수
MaxDepth int // 최대 깊이
Nodes [][][]byte // 트리 노드 배열
CurrentDepth int // 현재 깊이
CurrentIndex int // 현재 인덱스
}
func NewMerkleTree(total int) *MerkleTree {
maxDepth := int(math.Ceil(math.Log2(float64(total)))) // 최대 깊이 계산 = 부모 레벨 수 계산 (log2(total) 올림)
nodes := make([][][]byte, maxDepth+1) // 트리 노드 배열 생성
for i := 0; i <= maxDepth; i++ {
numItems := int(math.Ceil(float64(total) / math.Pow(2, float64(maxDepth-i)))) // 각 레벨의 노드 수 계산 (total / 2^(maxDepth-i) 올림)
levelHahes := make([][]byte, numItems) // 각 레벨의 노드 배열 생성
nodes[i] = levelHahes // 레벨 배열을 트리 노드 배열에 추가
}
return &MerkleTree{
Total: total,
MaxDepth: maxDepth,
Nodes: nodes,
CurrentDepth: 0,
CurrentIndex: 0,
}
}MerkleTree 구조체를 초기화하고 해시값을 채워 넣어 머클루트를 계산하는 방법은 다음과 같습니다.
func practice6() {
hexHashes := []string{
"9745f7173ef14ee4155722d1cbf13304339fd00d900b759c6f9d58579b5765fb",
"5573c8ede34936c29cdfdfe743f7f5fdfbd4f54ba0705259e62f39917065cb9b",
"82a02ecbb6623b4274dfcab82b336dc017a27136e08521091e443e62582e8f05",
"507ccae5ed9b340363a0e6d765af148be9cb1c8766ccc922f83e4ae681658308",
"a7a4aec28e7162e1e9ef33dfa30f0bc0526e6cf4b11a576f6c5de58593898330",
"bb6267664bd833fd9fc82582853ab144fece26b7a8a5bf328f8a059445b59add",
"ea6d7ac1ee77fbacee58fc717b990c4fcccf1b19af43103c090f601677fd8836",
"457743861de496c429912558a106b810b0507975a49773228aa788df40730d41",
"7688029288efc9e9a0011c960a6ed9e5466581abf3e3a6c26ee317461add619a",
"b1ae7f15836cb2286cdd4e2c37bf9bb7da0a2846d06867a429f654b2e7f383c9",
"9b74f89fa3f93e71ff2c241f32945d877281a6a50a6bf94adac002980aafe5ab",
"b3a92b5b255019bdaf754875633c2de9fec2ab03e6b8ce669d07cb5b18804638",
"b5c0b915312b9bdaedd2b86aa2d0f8feffc73a2d37668fd9010179261e25e263",
"c9d52c5cb1e557b92c84c52e7c4bfbce859408bedffc8a5560fd6e35e10b8800",
"c555bc5fc3bc096df0a0c9532f07640bfb76bfe4fc1ace214b8b228a1297a4c2",
"f9dbfafc3af3400954975da24eb325e326960a25b87fffe23eef3e7ed2fb610e",
}
tree := merkleblock.NewMerkleTree(len(hexHashes))
tree.Nodes[4] = func() [][]byte {
hashes := make([][]byte, len(tree.Nodes[4]))
for i, hexHash := range hexHashes {
hashes[i], _ = hex.DecodeString(hexHash)
}
return hashes
}()
tree.Nodes[3] = utils.MerkleParentLevel(tree.Nodes[4])
tree.Nodes[2] = utils.MerkleParentLevel(tree.Nodes[3])
tree.Nodes[1] = utils.MerkleParentLevel(tree.Nodes[2])
tree.Nodes[0] = utils.MerkleParentLevel(tree.Nodes[1])
fmt.Println(tree)
}$ go run .
*597c4baf...*
6382df3f...,87cf8fa3...
3ba6c080...,8e894862...,7ab01bb6...,3df760ac...
272945ec...,9a38d037...,4a64abd9...,ec7c95e1...,3b67006c...,850683df...,d40d268b...,8636b7a3...
9745f717...,5573c8ed...,82a02ecb...,507ccae5...,a7a4aec2...,bb626766...,ea6d7ac1...,45774386...,76880292...,b1ae7f15...,9b74f89f...,b3a92b5b...,b5c0b915...,c9d52c5c...,c555bc5f...,f9dbfafc...
그런데 일반적으로 네트워크를 통해 전달받는 포함증명에서 위의 예시처럼 모든 리프 노드의 해시값이 들어있는 것은 아닙니다. 포함증명은 리프 노드가 아닌 내부 노드의 해시값도 가지고 있을 수 있습니다. 그래야 머클루트를 구하기 위해 필요한 해시값의 수를 최소화할 수 있습니다.
그렇다면 모든 리프 노드를 사용하지 않고도 머클트리의 노드를 채우는 방법은 무엇일까요? 트리를 순회하는 순서로 노드를 채우는 것입니다. 이를 위해서는 트리에서 현재 깊이와 위치가 어딘지 추적할 수 있어야 하는데, 이를 가능하게 하는 값들이 바로 MerkleTree 구조체의 CurrentDepth와 CurrentIndex 필드입니다.
머클트리를 순회하고 값을 채워넣는 메서드들을 다음과 같이 정의하였습니다.
// 부모 노드로 이동
func (m *MerkleTree) Up() *MerkleTree {
m.CurrentDepth--
m.CurrentIndex /= 2
return m
}
// 왼쪽 자식 노드로 이동
func (m *MerkleTree) Left() *MerkleTree {
m.CurrentDepth++
m.CurrentIndex *= 2
return m
}
// 오른쪽 자식 노드로 이동
func (m *MerkleTree) Right() *MerkleTree {
m.CurrentDepth++
m.CurrentIndex = m.CurrentIndex*2 + 1
return m
}
// 루트 노드 반환
func (m *MerkleTree) Root() []byte {
return m.Nodes[0][0]
}
// 현재 노드에 해시 설정
func (m *MerkleTree) SetCurrentNode(hash []byte) *MerkleTree {
m.Nodes[m.CurrentDepth][m.CurrentIndex] = hash
return m
}
// 현재 노드 반환
func (m *MerkleTree) GetCurrentNode() []byte {
return m.Nodes[m.CurrentDepth][m.CurrentIndex]
}
// 왼쪽 자식 노드 반환
func (m *MerkleTree) GetLeftNode() []byte {
return m.Nodes[m.CurrentDepth+1][m.CurrentIndex*2]
}
// 오른쪽 자식 노드 반환
func (m *MerkleTree) GetRightNode() []byte {
return m.Nodes[m.CurrentDepth+1][m.CurrentIndex*2+1]
}
// 현재 노드가 리프 노드인지 확인
func (m *MerkleTree) IsLeaf() bool {
return m.CurrentDepth == m.MaxDepth
}
// 오른쪽 자식 노드가 존재하는지 확인
func (m *MerkleTree) RightExists() bool {
return len(m.Nodes[m.CurrentDepth+1]) > m.CurrentIndex*2+1
}이제 깊이 우선 탐색 방식으로 트리를 순회하면서 노드를 채워 넣을 수 있습니다.
func practice8() {
hexHashes := []string{
"9745f7173ef14ee4155722d1cbf13304339fd00d900b759c6f9d58579b5765fb",
"5573c8ede34936c29cdfdfe743f7f5fdfbd4f54ba0705259e62f39917065cb9b",
"82a02ecbb6623b4274dfcab82b336dc017a27136e08521091e443e62582e8f05",
"507ccae5ed9b340363a0e6d765af148be9cb1c8766ccc922f83e4ae681658308",
"a7a4aec28e7162e1e9ef33dfa30f0bc0526e6cf4b11a576f6c5de58593898330",
"bb6267664bd833fd9fc82582853ab144fece26b7a8a5bf328f8a059445b59add",
"ea6d7ac1ee77fbacee58fc717b990c4fcccf1b19af43103c090f601677fd8836",
"457743861de496c429912558a106b810b0507975a49773228aa788df40730d41",
"7688029288efc9e9a0011c960a6ed9e5466581abf3e3a6c26ee317461add619a",
"b1ae7f15836cb2286cdd4e2c37bf9bb7da0a2846d06867a429f654b2e7f383c9",
"9b74f89fa3f93e71ff2c241f32945d877281a6a50a6bf94adac002980aafe5ab",
"b3a92b5b255019bdaf754875633c2de9fec2ab03e6b8ce669d07cb5b18804638",
"b5c0b915312b9bdaedd2b86aa2d0f8feffc73a2d37668fd9010179261e25e263",
"c9d52c5cb1e557b92c84c52e7c4bfbce859408bedffc8a5560fd6e35e10b8800",
"c555bc5fc3bc096df0a0c9532f07640bfb76bfe4fc1ace214b8b228a1297a4c2",
"f9dbfafc3af3400954975da24eb325e326960a25b87fffe23eef3e7ed2fb610e",
"38faf8c811988dff0a7e6080b1771c97bcc0801c64d9068cffb85e6e7aacaf51",
}
tree := merkleblock.NewMerkleTree(len(hexHashes))
tree.Nodes[5] = func() [][]byte {
hashes := make([][]byte, len(tree.Nodes[5]))
for i, hexHash := range hexHashes {
hashes[i], _ = hex.DecodeString(hexHash)
}
return hashes
}()
// 루트 노드에서 깊이 우선 탐색 시작
for tree.Root() == nil {
// 현재 노드가 리프 노드이면 부모 노드로 이동
if tree.IsLeaf() {
tree.Up()
continue
}
left := tree.GetLeftNode() // 왼쪽 자식 노드 반환
// 왼쪽 자식 노드가 존재하지 않으면 왼쪽 자식 노드로 이동
if left == nil {
tree.Left()
} else if tree.RightExists() { // 오른쪽 자식 노드가 존재하는지 확인
right := tree.GetRightNode() // 오른쪽 자식 노드 반환
// 오른쪽 자식 노드가 존재하지 않으면 오른쪽 자식 노드로 이동
if right == nil {
tree.Right()
} else {
// 왼쪽, 오른쪽 자식 노드가 모두 존재하면 h256(L + R) 값을 현재 노드로 설정하고 부모 노드로 이동
tree.SetCurrentNode(utils.MerkleParent(left, right))
tree.Up()
}
} else { // 왼쪽 자식 노드만 존재하면 h256(L + L) 값을 현재 노드로 설정하고 부모 노드로 이동
tree.SetCurrentNode(utils.MerkleParent(left, left))
tree.Up()
}
}
fmt.Println(tree)
}$ go run .
0a313864...
597c4baf...,6f8a8190...
6382df3f...,87cf8fa3...,5647f416...
3ba6c080...,8e894862...,7ab01bb6...,3df760ac...,28e93b98...
272945ec...,9a38d037...,4a64abd9...,ec7c95e1...,3b67006c...,850683df...,d40d268b...,8636b7a3...,ce26d40b...
9745f717...,5573c8ed...,82a02ecb...,507ccae5...,a7a4aec2...,bb626766...,ea6d7ac1...,45774386...,76880292...,b1ae7f15...,9b74f89f...,b3a92b5b...,b5c0b915...,c9d52c5c...,c555bc5f...,f9dbfafc...,38faf8c8...📦2. 머클블록
풀노드가 포함증명과 함께 두 가지 정보를 라이트 노드에 전달할 때 구성하는 블록을 머클블록이라고 합니다. 두 가지 정보는 각각 머클트리의 구조에 대한 정보와 머클트리에서 어떤 해시값이 어느 위치에 있는지에 대한 정보입니다. 라이트 노드는 이 정보를 활용해 머클트리를 부분적으로 재구성하여 포함증명을 검증할 수 있습니다.
2.1 머클블록 커맨드
머클블록을 보내는 네트워크 커맨드는 'merkleblock'이며, 다음과 같은 형식입니다.
| 버전 | 4 bytes, little-endian |
| 이전 블록 해시 | 32 bytes, little-endian |
| 머클 루트 | 32 bytes, little-endian |
| 타임스탬프 | 4 bytes, little-endian |
| 난이도 | 4 bytes |
| 논스 | 4 bytes |
| 트랜잭션의 수 | 4 bytes, little-endian |
| 해시값의 수 | varint |
| 해시값 | 32 bytes * 해시값의 수, little-endian |
| 플래그 비트의 개수 | varint |
| 플래그 비트 | 플래그 비트의 개수만 |
처음 여섯 개의 필드는 블록의 헤더 정보를 나타내며, 마지막 다섯 개의 필드가 포함증명입니다. 트랜잭션의 수는 머클트리의 리프 노드의 개수를 의미하며, 해시값의 수와 해시값은 머클루트를 구하기 위해 필요한 해시값입니다. 마지막으로 플래그 비트는 각 해시값이 머클트리의 순회 순서에서 어느 위치에 있는가를 나타내는 위치 정보를 나타내고 있습니다.
플래그는 아래의 함수로 비트(1 또는 0) 리스트로 변환하여 사용합니다.
func BytesToBitField(bytes []byte) []byte {
var result []byte
for _, b := range bytes {
for i := 0; i < 8; i++ {
result = append(result, (b>>uint(i))&1)
}
}
return result
}머클블록을 나타내는 MerkleBlock 구조체와 머클블록을 파싱 하는 메서드는 다음과 같습니다.
type MerkleBlock struct {
Version int
PrevBlockHash []byte
MerkleRoot []byte
Timestamp int
Bits int
Nonce int
TotalTx int
Hashes [][]byte
Flags []byte
}
func (m *MerkleBlock) Parse(b []byte) error {
buf := bytes.NewBuffer(b)
m.Version = utils.LittleEndianToInt(buf.Next(4))
m.PrevBlockHash = utils.ReverseBytes(buf.Next(32))
m.MerkleRoot = utils.ReverseBytes(buf.Next(32))
m.Timestamp = utils.LittleEndianToInt(buf.Next(4))
m.Bits = utils.BytesToInt(buf.Next(4))
m.Nonce = utils.BytesToInt(buf.Next(4))
m.TotalTx = utils.LittleEndianToInt(buf.Next(4))
hashCount, read := utils.ReadVarint(buf.Bytes())
buf.Next(read)
m.Hashes = make([][]byte, hashCount)
for i := 0; i < int(hashCount); i++ {
m.Hashes[i] = utils.ReverseBytes(buf.Next(32))
}
flagCount, read := utils.ReadVarint(buf.Bytes())
buf.Next(read)
m.Flags = buf.Next(int(flagCount))
return nil
}2.2 단순 지급 검증
플래그 비트 작성 규칙은 다음과 같습니다.
- 노드의 해시값이 머클블록의 포함증명 해시값에 들어 있으면 플래그 비트는 0.
- 라이트 노드가 계산해야 하는 내부 노드인 경우 플래그 비트는 1.
- 라이트 노드에서 블록 포함 여부를 확인하고자하는 리프 노드인 경우 플래그 비트는 1. 이 값들도 머클블록의 포함증명 해시값에 포함되어 있습니다.
플래그 비트 규칙을 적용하여 머클트리를 검증하는 과정은 다음과 같습니다.
- 루트 노드1의 해시값은 라이트 노드에서 계산이 필요하므로 플래그 비트가 1입니다. 왼쪽 자식 노드를 확인합니다.
- 왼쪽 자식 노드2의 해시값은 포함증명 해시값에 들어있으므로 플래그 비트가 0입니다.
- 2의 해시값을 알고 있으니 그 자식 노드들은 더 이상 탐색할 필요가 없습니다. 따라서 1로 되돌아가 3으로 이동합니다.
- 오른쪽 자식 노드3은 계산이 필요하므로 플래그 비트가 1입니다. 계산을 위해서는 자식 노드의 해시값이 필요하므로 4로 이동합니다.
- 4는 계산이 필요하므로 플래그 비트가 1입니다. 5로 이동합니다.
- 5는 포함증명 해시값에 들어있으므로 플래그 비트가 0입니다. 4로 되돌아간 뒤, 6으로 이동합니다.
- 6은 계산이 필요하므로 플래그 비트가 1입니다. 7로 이동합니다.
- 7은 포함증명 해시값에 들어있지만, 블록에 포함 여부를 확인하고자 하는 단말 노드이므로 플래그 비트는 1입니다. 6으로 되돌아간 뒤, 8로 이동합니다.
- 8은 포함증명 해시값에 들어있으므로 플래그 비트가 0입니다. 6으로 되돌아갑니다.
- 7과 8을 사용해 6을 계산합니다. 4로 되돌아갑니다.
- 5과 6을 사용해 4를 계산합니다. 3으로 되돌아간 뒤, 9로 이동합니다.
- 9는 계산이 필요하므로 플래그 비트가 1입니다. 10으로 이동합니다.
- 10은 계산이 필요하므로 플래그 비트가 1입니다. 11로 이동합니다.
- 11은 포함증명 해시값에 들어있으므로 플래그 비트가 0입니다. 10으로 되돌아간 뒤, 12로 이동합니다.
- 12는 포함증명 해시값에 들어있지만, 블록에 포함 여부를 확인하고자 하는 단말 노드이므로 플래그 비트는 1입니다. 10으로 되돌아갑니다.
- 11과 12를 사용해 10을 계산합니다. 9로 되돌아간 뒤, 13으로 이동합니다.
- 13은 포함증명 해시값에 들어있으므로 플래그 비트가 0입니다. 9로 되돌아갑니다.
- 10과 13을 사용해 9를 계산합니다. 3으로 되돌아갑니다.
- 4와 9를 사용해 3을 계산합니다. 1로 되돌아갑니다.
- 2와 3을 사용해 1을 계산합니다.
- 마침내 구한 머클루트를 블록 헤더의 머클루트와 비교하여 검증합니다.
깊이 우선 탐색 방식으로 순회 순서에 따라 도출되는 플래그 비트는 다음과 같습니다.
[1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 0]
플래그 비트와 포함증명 해시값을 사용해 머클루트를 구하는 메서드는 다음과 같습니다.
func (m *MerkleTree) PopulateTree(flagBits []byte, hashes [][]byte) error {
// 루트 노드에서 깊이 우선 탐색 시작
for m.Root() == nil {
// 현재 노드가 리프 노드인 경우
if m.IsLeaf() {
m.SetCurrentNode(hashes[0]) // 현재 노드에 해시 설정
hashes = hashes[1:] // 사용된 해시 제거
flagBits = flagBits[1:] // 사용된 플래그 제거
m.Up() // 부모 노드로 이동
} else {
// 현재 노드가 리프 노드가 아닌 경우
leftHash := m.GetLeftNode() // 왼쪽 자식 노드 해시 가져오기
// 왼쪽 자식 노드의 해시값이 설정되지 않은 경우
if leftHash == nil {
bit := flagBits[0] // 플래그 비트 가져오기
flagBits = flagBits[1:] // 사용된 플래그 제거
// 플래그 비트가 0인 경우
if bit == 0 {
m.SetCurrentNode(hashes[0]) // 현재 노드에 해시 설정
hashes = hashes[1:] // 사용된 해시 제거
m.Up() // 부모 노드로 이동
} else {
// 플래그 비트가 1인 경우 (계산이 필요한 경우)
m.Left() // 왼쪽 자식 노드로 이동
}
} else if m.RightExists() {
// 왼쪽 자식 노드가 존재하고 오른쪽 자식 노드가 존재하는 경우
rightHash := m.GetRightNode() // 오른쪽 자식 노드 해시 가져오기
// 오른쪽 자식 노드의 해시값이 설정되지 않은 경우
if rightHash == nil {
m.Right() // 오른쪽 자식 노드로 이동
} else {
// 오른쪽 자식 노드의 해시값이 설정된 경우
m.SetCurrentNode(utils.MerkleParent(leftHash, rightHash)) // 현재 노드에 hash256(L+R) 설정
m.Up() // 부모 노드로 이동
}
} else {
// 왼쪽 자식 노드가 존재하고 오른쪽 자식 노드가 존재하지 않는 경우
m.SetCurrentNode(utils.MerkleParent(leftHash, leftHash)) // 현재 노드에 hash256(L+L) 설정
m.Up() // 부모 노드로 이동
}
}
}
// 모든 해시와 플래그가 소비되었는지 확인
if len(hashes) != 0 {
return fmt.Errorf("hashes not all consumed %d", len(hashes))
}
for _, bit := range flagBits {
if bit != 0 {
return fmt.Errorf("flagBits not all consumed")
}
}
return nil
}머클루트를 구한 뒤에 블록 헤더의 머클루트와 비교하여 검증하는 메서드는 다음과 같습니다.
func (m *MerkleBlock) IsValid() (bool, error) {
flagBits := utils.BytesToBitField(m.Flags) // 비트 필드 생성
hashes := m.Hashes // 해시 목록 복사 및 리틀 엔디언으로 읽기
for i, hash := range hashes {
hashes[i] = utils.ReverseBytes(hash)
}
mt := NewMerkleTree(m.TotalTx) // 머클 트리 생성
err := mt.PopulateTree(flagBits, hashes) // 머클 트리 채우기
if err != nil {
return false, err
}
return bytes.Equal(utils.ReverseBytes(mt.Root()), m.MerkleRoot), nil // 머클 루트 비교
}머클블록을 파싱하고 머클루트를 검증하는 예제는 다음과 같습니다.
func practice12() {
rawMerkleBlock, _ := hex.DecodeString("00000020df3b053dc46f162a9b00c7f0d5124e2676d47bbe7c5d0793a500000000000000ef445fef2ed495c275892206ca533e7411907971013ab83e3b47bd0d692d14d4dc7c835b67d8001ac157e670bf0d00000aba412a0d1480e370173072c9562becffe87aa661c1e4a6dbc305d38ec5dc088a7cf92e6458aca7b32edae818f9c2c98c37e06bf72ae0ce80649a38655ee1e27d34d9421d940b16732f24b94023e9d572a7f9ab8023434a4feb532d2adfc8c2c2158785d1bd04eb99df2e86c54bc13e139862897217400def5d72c280222c4cbaee7261831e1550dbb8fa82853e9fe506fc5fda3f7b919d8fe74b6282f92763cef8e625f977af7c8619c32a369b832bc2d051ecd9c73c51e76370ceabd4f25097c256597fa898d404ed53425de608ac6bfe426f6e2bb457f1c554866eb69dcb8d6bf6f880e9a59b3cd053e6c7060eeacaacf4dac6697dac20e4bd3f38a2ea2543d1ab7953e3430790a9f81e1c67f5b58c825acf46bd02848384eebe9af917274cdfbb1a28a5d58a23a17977def0de10d644258d9c54f886d47d293a411cb6226103b55635")
merkleBlock := merkleblock.MerkleBlock{}
merkleBlock.Parse(rawMerkleBlock)
valid, err := merkleBlock.IsValid()
if err != nil {
panic(err)
}
if !valid {
panic("invalid merkle block")
}
fmt.Println("valid merkle block")
}$ go run .
valid merkle block📖 참고자료
밑바닥부터 시작하는 비트코인
비트코인은 블록체인 기술의 집약체입니다. 이더리움, 이오스 같은 2, 3세대 블록체인은 비트코인을 바탕으로 확장, 발전한 개념입니다. 디앱 개발에서 머무르지 않고 블록체인 개발자로 성장하
www.hanbit.co.kr
GitHub - jimmysong/programmingbitcoin: Repository for the book
Repository for the book. Contribute to jimmysong/programmingbitcoin development by creating an account on GitHub.
github.com
'블록체인 > Bitcoin' 카테고리의 다른 글
| 밑바닥부터 시작하는 비트코인 - 13장 세그윗 1 (0) | 2024.01.13 |
|---|---|
| 밑바닥부터 시작하는 비트코인 - 12장 블룸 필터 (1) | 2024.01.10 |
| 밑바닥부터 시작하는 비트코인 - 10장 네트워킹 (1) | 2024.01.08 |
| 밑바닥부터 시작하는 비트코인 - 9장 블록 (0) | 2023.09.21 |
| 밑바닥부터 시작하는 비트코인 - 8장 p2sh 스크립트 (0) | 2023.09.20 |