/
tx.go
168 lines (149 loc) · 4.45 KB
/
tx.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
package proof
import (
"errors"
"io"
"github.com/btcsuite/btcd/blockchain"
"github.com/btcsuite/btcd/btcutil"
"github.com/btcsuite/btcd/chaincfg/chainhash"
"github.com/btcsuite/btcd/wire"
"github.com/lightningnetwork/lnd/tlv"
)
// TxMerkleProof represents a simplified version of BIP-0037 transaction merkle
// proofs for a single transaction.
type TxMerkleProof struct {
// Nodes is the list of nodes to hash along with the transaction being
// proved to arrive at the block's merkle root.
Nodes []chainhash.Hash
// Bits indicates the direction for each node found in Nodes above. A
// 0 bit indicates a left direction or a right direction otherwise.
Bits []bool
}
// NewTxMerkleProof computes the merkle proof for a specific transaction found
// within a block's set of transactions.
func NewTxMerkleProof(txs []*wire.MsgTx, txIdx int) (*TxMerkleProof, error) {
if len(txs) <= txIdx {
return nil, errors.New("invalid transaction index for block")
}
blockTxs := make([]*btcutil.Tx, 0, len(txs))
for _, tx := range txs {
blockTxs = append(blockTxs, btcutil.NewTx(tx))
}
// Compute the full merkle tree for the set of transactions.
hashes := blockchain.BuildMerkleTreeStore(blockTxs, false)
// Only one transaction found within the block, return immediately.
if len(hashes) == 1 {
return &TxMerkleProof{
Nodes: []chainhash.Hash{},
Bits: []bool{},
}, nil
}
// With the full merkle tree computed above, we'll iterate through it
// level by level, starting from the transaction leaf, up to the root.
var (
nextPoT = nextPowerOfTwo(len(txs))
currentIdx = txIdx
nodes []chainhash.Hash
bits []bool
)
for level := 0; ; level++ {
// We determine the direction of our sibling based on our
// current index within the tree level.
var sibling chainhash.Hash
isRightSibling := currentIdx%2 == 0
if isRightSibling {
// If we are the left child, a right sibling may not
// exist.
hash := hashes[currentIdx+1]
if hash != nil {
sibling = *hash
} else if hashes[currentIdx] == nil {
return nil, errors.New("invalid merkle tree")
} else {
sibling = *hashes[currentIdx]
}
} else {
// If we are the right child, there'll always be a left
// sibling.
sibling = *hashes[currentIdx-1]
}
nodes = append(nodes, sibling)
bits = append(bits, isRightSibling)
// Obtain the next set of hashes for the next level in the tree.
var nextLevelOffset int
if level == 0 {
nextLevelOffset = nextPoT // Avoids division by 0.
} else {
nextLevelOffset = (nextPoT >> level)
}
hashes = hashes[nextLevelOffset:]
// Update the currentIdx to reflect the next level in the tree.
// We divide by 2 since we always hash in pairs.
currentIdx = currentIdx / 2
// We've arrived at the root so our proof is complete.
if len(hashes) == 1 {
return &TxMerkleProof{
Nodes: nodes,
Bits: bits,
}, nil
}
}
}
// Verify verifies a merkle proof for `tx` by ensuring the end result matches
// the expected `merkleRoot`.
func (p TxMerkleProof) Verify(tx *wire.MsgTx, merkleRoot chainhash.Hash) bool {
current := tx.TxHash()
for i := range p.Nodes {
var left, right *chainhash.Hash
if p.Bits[i] {
left, right = ¤t, &p.Nodes[i]
} else {
right, left = ¤t, &p.Nodes[i]
}
current = blockchain.HashMerkleBranches(left, right)
}
return current == merkleRoot
}
// Encode encodes a TxMerkleProof into `w`.
func (p TxMerkleProof) Encode(w io.Writer) error {
numNodes := uint64(len(p.Nodes))
var buf [8]byte
if err := tlv.WriteVarInt(w, numNodes, &buf); err != nil {
return err
}
for _, node := range p.Nodes {
hash := [32]byte(node)
if err := tlv.EBytes32(w, &hash, &buf); err != nil {
return err
}
}
bits := packBits(p.Bits)
return tlv.EVarBytes(w, &bits, &buf)
}
// Decode decodes a TxMerkleProof from `r`.
func (p *TxMerkleProof) Decode(r io.Reader) error {
var buf [8]byte
numNodes, err := tlv.ReadVarInt(r, &buf)
if err != nil {
return err
}
if numNodes > MerkleProofMaxNodes {
return tlv.ErrRecordTooLarge
}
p.Nodes = make([]chainhash.Hash, 0, numNodes)
for i := uint64(0); i < numNodes; i++ {
var hash [chainhash.HashSize]byte
err = tlv.DBytes32(r, &hash, &buf, chainhash.HashSize)
if err != nil {
return err
}
p.Nodes = append(p.Nodes, chainhash.Hash(hash))
}
var packedBits []byte
err = tlv.DVarBytes(r, &packedBits, &buf, packedBitsLen(numNodes))
if err != nil {
return err
}
bits := unpackBits(packedBits)
p.Bits = bits[:len(p.Nodes)]
return nil
}