block.go raw
1 // Package block parses a raw block far enough to check it.
2 //
3 // A compact filter can say a block mentions one of the wallet's scripts, but not what the block
4 // contains. Fetching the block only helps if the wallet can prove it is the block a header
5 // committed to: the header's merkle root is that commitment, and everything here exists to
6 // rebuild the root from the transactions the block actually carries.
7 package block
8
9 import (
10 "crypto/sha256"
11 "encoding/binary"
12 "errors"
13 "fmt"
14 )
15
16 // Errors the parser refuses.
17 var (
18 // ErrShort is a block that ends before its structure does.
19 ErrShort = errors.New("block: truncated")
20 // ErrNoTransactions is a block with no coinbase.
21 ErrNoTransactions = errors.New("block: no transactions")
22 // ErrMerkleMismatch is a block whose transactions do not hash to its header's root.
23 ErrMerkleMismatch = errors.New("block: the transactions do not match the header's merkle root")
24 )
25
26 // HeaderLen is the fixed header size.
27 const HeaderLen = 80
28
29 // Block is a parsed block.
30 type Block struct {
31 // Hash is the double SHA-256 of the header, in wire order.
32 Hash [32]byte
33 // MerkleRoot is the root the header commits to, in wire order.
34 MerkleRoot [32]byte
35 // TxIDs are the transaction ids, in the order the block lists them.
36 TxIDs [][32]byte
37 // Outputs are each transaction's outputs, in the same order as TxIDs.
38 Outputs [][]Output
39 }
40
41 // Output is one transaction output.
42 type Output struct {
43 // Value is the amount in satoshis.
44 Value uint64
45 // Script is the scriptPubKey.
46 Script []byte
47 }
48
49 // Match is one output that pays a script the caller asked about.
50 type Match struct {
51 // TxID is the transaction that created it, in wire order.
52 TxID [32]byte
53 // Vout is its position in that transaction.
54 Vout uint32
55 // Value is the amount in satoshis.
56 Value uint64
57 // Script is the scriptPubKey that matched.
58 Script []byte
59 }
60
61 // Match returns the outputs of this block that pay any of the scripts.
62 //
63 // This is what turns a filter hit into a coin: the filter said the block mentions a script, and
64 // this says which output, in which transaction, for how much.
65 func (b *Block) Match(scripts [][]byte) []Match {
66 wanted := make(map[string]bool, len(scripts))
67
68 for _, script := range scripts {
69 wanted[string(script)] = true
70 }
71
72 var matches []Match
73
74 for index, outputs := range b.Outputs {
75 for vout, output := range outputs {
76 if !wanted[string(output.Script)] {
77 continue
78 }
79
80 matches = append(matches, Match{
81 TxID: b.TxIDs[index],
82 Vout: uint32(vout),
83 Value: output.Value,
84 Script: output.Script,
85 })
86 }
87 }
88
89 return matches
90 }
91
92 // Parse reads a block's header and transactions.
93 func Parse(raw []byte) (*Block, error) {
94 if len(raw) < HeaderLen+1 {
95 return nil, fmt.Errorf("%w: %d bytes", ErrShort, len(raw))
96 }
97
98 block := &Block{
99 Hash: doubleSHA256(raw[:HeaderLen]),
100 MerkleRoot: toArray(raw[36:68]),
101 }
102
103 at := HeaderLen
104 count, next, err := compactSize(raw, at)
105
106 if err != nil {
107 return nil, err
108 }
109
110 at = next
111
112 if count == 0 {
113 return nil, ErrNoTransactions
114 }
115
116 for index := 0; index < count; index++ {
117 id, outputs, next, err := scanTx(raw, at)
118
119 if err != nil {
120 return nil, fmt.Errorf("block: transaction %d: %w", index, err)
121 }
122
123 block.TxIDs = append(block.TxIDs, id)
124 block.Outputs = append(block.Outputs, outputs)
125 at = next
126 }
127
128 return block, nil
129 }
130
131 // VerifyMerkle rebuilds the root and compares it with the header's.
132 func (b *Block) VerifyMerkle() error {
133 root, err := merkleRoot(b.TxIDs)
134
135 if err != nil {
136 return err
137 }
138
139 if root != b.MerkleRoot {
140 return fmt.Errorf("%w: the header says %x, the transactions hash to %x",
141 ErrMerkleMismatch, b.MerkleRoot, root)
142 }
143
144 return nil
145 }
146
147 // scanTx walks one transaction and returns its id and the offset after it.
148 //
149 // The id is the hash of the transaction without its witness: the marker, flag and witness
150 // stacks are not part of what identifies it, so they are skipped while the rest is hashed.
151 func scanTx(raw []byte, at int) ([32]byte, []Output, int, error) {
152 var zero [32]byte
153
154 if at+4 > len(raw) {
155 return zero, nil, 0, ErrShort
156 }
157
158 version := raw[at : at+4]
159 body := at + 4
160 witness := false
161
162 if body >= len(raw) {
163 return zero, nil, 0, ErrShort
164 }
165
166 // A zero input count is the segwit marker; the flag follows, then the real input count.
167 if raw[body] == 0x00 && body+1 < len(raw) && raw[body+1] == 0x01 {
168 witness = true
169 body += 2
170 }
171
172 inputs, next, err := compactSize(raw, body)
173
174 if err != nil {
175 return zero, nil, 0, err
176 }
177
178 at = next
179
180 for index := 0; index < inputs; index++ {
181 if at+36 > len(raw) {
182 return zero, nil, 0, ErrShort
183 }
184
185 at += 36
186
187 length, next, err := compactSize(raw, at)
188
189 if err != nil {
190 return zero, nil, 0, err
191 }
192
193 at = next + length
194
195 if at+4 > len(raw) {
196 return zero, nil, 0, ErrShort
197 }
198
199 at += 4
200 }
201
202 outputCount, next, err := compactSize(raw, at)
203
204 if err != nil {
205 return zero, nil, 0, err
206 }
207
208 at = next
209
210 outputs := make([]Output, 0, outputCount)
211
212 for index := 0; index < outputCount; index++ {
213 if at+8 > len(raw) {
214 return zero, nil, 0, ErrShort
215 }
216
217 value := binary.LittleEndian.Uint64(raw[at:])
218 at += 8
219
220 length, next, err := compactSize(raw, at)
221
222 if err != nil {
223 return zero, nil, 0, err
224 }
225
226 at = next
227
228 if at+length > len(raw) {
229 return zero, nil, 0, ErrShort
230 }
231
232 outputs = append(outputs, Output{Value: value, Script: raw[at : at+length]})
233 at += length
234 }
235
236 end := at
237
238 if witness {
239 for index := 0; index < inputs; index++ {
240 if at >= len(raw) {
241 return zero, nil, 0, ErrShort
242 }
243
244 items, next, err := compactSize(raw, at)
245
246 if err != nil {
247 return zero, nil, 0, err
248 }
249
250 at = next
251
252 for item := 0; item < items; item++ {
253 length, next, err := compactSize(raw, at)
254
255 if err != nil {
256 return zero, nil, 0, err
257 }
258
259 at = next + length
260
261 if at > len(raw) {
262 return zero, nil, 0, ErrShort
263 }
264 }
265 }
266 }
267
268 if at+4 > len(raw) {
269 return zero, nil, 0, ErrShort
270 }
271
272 locktime := raw[at : at+4]
273 at += 4
274
275 // The id commits to version, inputs, outputs and locktime, in that order, with no witness.
276 plain := make([]byte, 0, len(version)+(end-body)+4)
277 plain = append(plain, version...)
278 plain = append(plain, raw[body:end]...)
279 plain = append(plain, locktime...)
280
281 return doubleSHA256(plain), outputs, at, nil
282 }
283
284 // merkleRoot rebuilds the root, pairing an odd last hash with itself.
285 func merkleRoot(txids [][32]byte) ([32]byte, error) {
286 if len(txids) == 0 {
287 return [32]byte{}, ErrNoTransactions
288 }
289
290 level := make([][32]byte, len(txids))
291 copy(level, txids)
292
293 for len(level) > 1 {
294 if len(level)%2 == 1 {
295 level = append(level, level[len(level)-1])
296 }
297
298 next := make([][32]byte, 0, len(level)/2)
299
300 for index := 0; index < len(level); index += 2 {
301 pair := make([]byte, 0, 64)
302 pair = append(pair, level[index][:]...)
303 pair = append(pair, level[index+1][:]...)
304 next = append(next, doubleSHA256(pair))
305 }
306
307 level = next
308 }
309
310 return level[0], nil
311 }
312
313 // compactSize reads Bitcoin's length prefix.
314 func compactSize(raw []byte, at int) (int, int, error) {
315 if at >= len(raw) {
316 return 0, 0, ErrShort
317 }
318
319 first := raw[at]
320 at++
321
322 switch first {
323 case 0xfd:
324 if at+2 > len(raw) {
325 return 0, 0, ErrShort
326 }
327
328 return int(binary.LittleEndian.Uint16(raw[at:])), at + 2, nil
329 case 0xfe:
330 if at+4 > len(raw) {
331 return 0, 0, ErrShort
332 }
333
334 return int(binary.LittleEndian.Uint32(raw[at:])), at + 4, nil
335 case 0xff:
336 if at+8 > len(raw) {
337 return 0, 0, ErrShort
338 }
339
340 return int(binary.LittleEndian.Uint64(raw[at:])), at + 8, nil
341 }
342
343 return int(first), at, nil
344 }
345
346 // doubleSHA256 is Bitcoin's hash.
347 func doubleSHA256(raw []byte) [32]byte {
348 first := sha256.Sum256(raw)
349
350 return sha256.Sum256(first[:])
351 }
352
353 // toArray copies a slice into a fixed-size hash.
354 func toArray(raw []byte) [32]byte {
355 var out [32]byte
356
357 copy(out[:], raw)
358
359 return out
360 }
361