1 package blockchain
2 3 import (
4 "bytes"
5 "container/list"
6 "errors"
7 "fmt"
8 "time"
9 10 "github.com/p9c/p9/pkg/chainhash"
11 "github.com/p9c/p9/pkg/database"
12 "github.com/p9c/p9/pkg/wire"
13 )
14 15 // blockHdrOffset defines the offsets into a v1 block index row for the block header.
16 //
17 // The serialized block index row format is:
18 //
19 // <blocklocation><blockheader>
20 const blockHdrOffset = 12
21 22 // errInterruptRequested indicates that an operation was cancelled due to a user-requested interrupt.
23 var errInterruptRequested = errors.New("interrupt requested")
24 25 // interruptRequested returns true when the provided channel has been closed.
26 //
27 // This simplifies early shutdown slightly since the caller can just use an if statement instead of a select.
28 func interruptRequested(interrupted <-chan struct{}) bool {
29 select {
30 case <-interrupted:
31 return true
32 default:
33 }
34 return false
35 }
36 37 // blockChainContext represents a particular block's placement in the block chain. This is used by the block index
38 // migration to track block metadata that will be written to disk.
39 type blockChainContext struct {
40 parent *chainhash.Hash
41 children []*chainhash.Hash
42 height int32
43 mainChain bool
44 }
45 46 // migrateBlockIndex migrates all block entries from the v1 block index bucket to the v2 bucket. The v1 bucket stores
47 // all block entries keyed by block hash, whereas the v2 bucket stores the exact same values, but keyed instead by block
48 // height + hash.
49 func migrateBlockIndex(db database.DB) (e error) {
50 // Hardcoded bucket names so updates to the global values do not affect old upgrades.
51 v1BucketName := []byte("ffldb-blockidx")
52 v2BucketName := []byte("blockheaderidx")
53 e = db.Update(
54 func(dbTx database.Tx) (e error) {
55 v1BlockIdxBucket := dbTx.Metadata().Bucket(v1BucketName)
56 if v1BlockIdxBucket == nil {
57 return fmt.Errorf("bucket %s does not exist", v1BucketName)
58 }
59 I.Ln(
60 "Re-indexing block information in the database. " +
61 "This might take a while",
62 )
63 var v2BlockIdxBucket database.Bucket
64 v2BlockIdxBucket, e = dbTx.Metadata().CreateBucketIfNotExists(v2BucketName)
65 if e != nil {
66 return e
67 }
68 // Get tip of the main chain.
69 serializedData := dbTx.Metadata().Get(chainStateKeyName)
70 state, e := deserializeBestChainState(serializedData)
71 if e != nil {
72 return e
73 }
74 tip := &state.hash
75 // Scan the old block index bucket and construct a mapping of each block to parent block and all child blocks.
76 blocksMap, e := readBlockTree(v1BlockIdxBucket)
77 if e != nil {
78 return e
79 }
80 // Use the block graph to calculate the height of each block.
81 e = determineBlockHeights(blocksMap)
82 if e != nil {
83 return e
84 }
85 // Find blocks on the main chain with the block graph and current tip.
86 determineMainChainBlocks(blocksMap, tip)
87 // Now that we have heights for all blocks, scan the old block index
88 // bucket and insert all rows into the new one.
89 return v1BlockIdxBucket.ForEach(
90 func(hashBytes, blockRow []byte) (e error) {
91 endOffset := blockHdrOffset + blockHdrSize
92 headerBytes := blockRow[blockHdrOffset:endOffset:endOffset]
93 var hash chainhash.Hash
94 copy(hash[:], hashBytes[0:chainhash.HashSize])
95 chainContext := blocksMap[hash]
96 if chainContext.height == -1 {
97 return fmt.Errorf(
98 "unable to calculate chain height for "+
99 "stored block %s", hash,
100 )
101 }
102 // Mark blocks as valid if they are part of the main chain.
103 status := statusDataStored
104 if chainContext.mainChain {
105 status |= statusValid
106 }
107 // Write header to v2 bucket
108 value := make([]byte, blockHdrSize+1)
109 copy(value[0:blockHdrSize], headerBytes)
110 value[blockHdrSize] = byte(status)
111 key := blockIndexKey(&hash, uint32(chainContext.height))
112 e = v2BlockIdxBucket.Put(key, value)
113 if e != nil {
114 return e
115 }
116 // Delete header from v1 bucket
117 truncatedRow := blockRow[0:blockHdrOffset:blockHdrOffset]
118 return v1BlockIdxBucket.Put(hashBytes, truncatedRow)
119 },
120 )
121 },
122 )
123 if e != nil {
124 return e
125 }
126 I.Ln("Block database migration complete")
127 return nil
128 }
129 130 // readBlockTree reads the old block index bucket and constructs a mapping of each block to its parent block and all
131 // child blocks. This mapping represents the full tree of blocks. This function does not populate the height or
132 // mainChain fields of the returned blockChainContext values.
133 func readBlockTree(v1BlockIdxBucket database.Bucket) (blocksMap map[chainhash.Hash]*blockChainContext, e error) {
134 blocksMap = make(map[chainhash.Hash]*blockChainContext)
135 e = v1BlockIdxBucket.ForEach(
136 func(_, blockRow []byte) (e error) {
137 var header wire.BlockHeader
138 endOffset := blockHdrOffset + blockHdrSize
139 headerBytes := blockRow[blockHdrOffset:endOffset:endOffset]
140 e = header.Deserialize(bytes.NewReader(headerBytes))
141 if e != nil {
142 return e
143 }
144 blockHash := header.BlockHash()
145 prevHash := header.PrevBlock
146 if blocksMap[blockHash] == nil {
147 blocksMap[blockHash] = &blockChainContext{height: -1}
148 }
149 if blocksMap[prevHash] == nil {
150 blocksMap[prevHash] = &blockChainContext{height: -1}
151 }
152 blocksMap[blockHash].parent = &prevHash
153 blocksMap[prevHash].children =
154 append(blocksMap[prevHash].children, &blockHash)
155 return nil
156 },
157 )
158 return blocksMap, e
159 }
160 161 // determineBlockHeights takes a map of block hashes to a slice of child hashes and uses it to compute the height for
162 // each block.
163 //
164 // The function assigns a height of 0 to the genesis hash and explores the tree of blocks breadth-first, assigning a
165 // height to every block with a path back to the genesis block.
166 //
167 // This function modifies the height field on the blocksMap entries.
168 func determineBlockHeights(blocksMap map[chainhash.Hash]*blockChainContext) (e error) {
169 queue := list.New()
170 // The genesis block is included in blocksMap as a child of the zero hash because that is the value of the PrevBlock
171 // field in the genesis header.
172 preGenesisContext, exists := blocksMap[zeroHash]
173 if !exists || len(preGenesisContext.children) == 0 {
174 return fmt.Errorf("unable to find genesis block")
175 }
176 for _, genesisHash := range preGenesisContext.children {
177 blocksMap[*genesisHash].height = 0
178 queue.PushBack(genesisHash)
179 }
180 for e := queue.Front(); e != nil; e = queue.Front() {
181 queue.Remove(e)
182 hash := e.Value.(*chainhash.Hash)
183 height := blocksMap[*hash].height
184 // For each block with this one as a parent, assign it a height and
185 // push to queue for future processing.
186 for _, childHash := range blocksMap[*hash].children {
187 blocksMap[*childHash].height = height + 1
188 queue.PushBack(childHash)
189 }
190 }
191 return nil
192 }
193 194 // determineMainChainBlocks traverses the block graph down from the tip to determine which block hashes that are part of
195 // the main chain. This function modifies the mainChain field on the blocksMap entries.
196 func determineMainChainBlocks(blocksMap map[chainhash.Hash]*blockChainContext, tip *chainhash.Hash) {
197 for nextHash := tip; *nextHash != zeroHash; nextHash = blocksMap[*nextHash].parent {
198 blocksMap[*nextHash].mainChain = true
199 }
200 }
201 202 // deserializeUtxoEntryV0 decodes a utxo entry from the passed
203 // serialized byte slice according to the legacy version 0 format into a map
204 // of utxos keyed by the output index within the transaction.
205 // The map is necessary because the previous format encoded all unspent
206 // outputs for a transaction using a single entry,
207 // whereas the new format encodes each unspent output individually.
208 //
209 // The legacy format is as follows:
210 //
211 // <version><height><header code><unspentness bitmap>[<compressed txouts>,...]
212 //
213 // Field Type Size
214 //
215 // version VLQ variable
216 //
217 // block height VLQ variable
218 //
219 // header code VLQ variable
220 //
221 // unspentness bitmap []byte variable
222 //
223 // compressed txouts
224 //
225 // compressed amount VLQ variable
226 // compressed script []byte variable
227 //
228 // The serialized header code format is:
229 //
230 // bit 0 - containing transaction is a coinbase
231 //
232 // bit 1 - output zero is unspent
233 //
234 // bit 2 - output one is unspent
235 //
236 // bits 3-x - number of bytes in unspentness bitmap. When both bits 1 and 2
237 // are unset, it encodes N-1 since there must be at least one unspent
238 // output.
239 //
240 // The rationale for the header code scheme is as follows:
241 //
242 // - Transactions which only pay to a single output and a change output are
243 // extremely common, thus an extra byte for the unspentness bitmap can be
244 // avoided for them by encoding those two outputs in the low order bits.
245 //
246 // - Given it is encoded as a VLQ which can encode values up to 127 with a
247 // single byte, that leaves 4 bits to represent the number of bytes in the
248 // unspentness bitmap while still only consuming a single byte for the
249 // header code. In other words, an unspentness bitmap with up to 120
250 // transaction outputs can be encoded with a single-byte header code.
251 // This covers the vast majority of transactions.
252 //
253 // - Encoding N-1 bytes when both bits 1 and 2 are unset allows an additional
254 // 8 outpoints to be encoded before causing the header code to require an
255 // additional byte.
256 //
257 // Example 1:
258 //
259 // From tx in main blockchain:
260 //
261 // Blk 1, 0e3e2357e806b6cdb1f70b54c3a3a17b6714ee1f0e68bebb44a74b1efd512098
262 // 010103320496b538e853519c726a2c91e61ec11600ae1390813a627c66fb8be7947be63c52
263 // <><><><------------------------------------------------------------------>
264 // | | \--------\ |
265 // | height | compressed txout 0
266 // version header code
267 //
268 // - version: 1
269 //
270 // - height: 1
271 //
272 // - header code: 0x03 (coinbase, output zero unspent, 0 bytes of unspentness)
273 //
274 // - unspentness: Nothing since it is zero bytes
275 //
276 // - compressed txout 0:
277 //
278 // - 0x32: VLQ-encoded compressed amount for 5000000000 (50 DUO)
279 //
280 // - 0x04: special script type pay-to-pubkey
281 //
282 // - 0x96...52: x-coordinate of the pubkey
283 //
284 // Example 2:
285 //
286 // From tx in main blockchain:
287 //
288 // Blk 113931, 4a16969aa4764dd7507fc1de7f0baa4850a246de90c45e59a3207f9a26b5036f
289 // 0185f90b0a011200e2ccd6ec7c6e2e581349c77e067385fa8236bf8a800900b8025be1b3efc63b0ad48e7f9f10e87544528d58
290 // <><----><><><------------------------------------------><-------------------------------------------->
291 // | | | \-------------------\ | |
292 // version | \--------\ unspentness
293 // | compressed txout 2
294 // height header code compressed txout 0
295 //
296 // - version: 1
297 //
298 // - height: 113931
299 //
300 // - header code: 0x0a (output zero unspent, 1 byte in unspentness bitmap)
301 //
302 // - unspentness: [0x01] (bit 0 is set, so output 0+2 = 2 is unspent)
303 // NOTE: It's +2 since the first two outputs are encoded in the header code
304 //
305 // - compressed txout 0:
306 //
307 // - 0x12: VLQ-encoded compressed amount for 20000000 (0.2 DUO)
308 //
309 // - 0x00: special script type pay-to-pubkey-hash
310 //
311 // - 0xe2...8a: pubkey hash
312 //
313 // - compressed txout 2:
314 //
315 // - 0x8009: VLQ-encoded compressed amount for 15000000 (0.15 DUO)
316 //
317 // - 0x00: special script type pay-to-pubkey-hash
318 //
319 // - 0xb8...58: pubkey hash
320 //
321 // Example 3:
322 //
323 // From tx in main blockchain:
324 //
325 // Blk 338156, 1b02d1c8cfef60a189017b9a420c682cf4a0028175f2f563209e4ff61c8c3620
326 // 0193d06c100000108ba5b9e763011dd46a006572d820e448e12d2bbb38640bc718e6
327 // <><----><><----><-------------------------------------------------->
328 // | | | \-----------------\ |
329 // version | \--------\ unspentness |
330 // height header code compressed txout 22
331 //
332 // - version: 1
333 //
334 // - height: 338156
335 //
336 // - header code: 0x10 (2+1 = 3 bytes in unspentness bitmap) NOTE: It's +1 since neither bit 1 nor 2 are set, so N-1 is
337 // encoded.
338 //
339 // - unspentness: [0x00 0x00 0x10] (bit 20 is set, so output 20+2 = 22 is unspent)
340 // NOTE: It's +2 since the first two outputs are encoded in the header code
341 //
342 // - compressed txout 22:
343 //
344 // - 0x8ba5b9e763: VLQ-encoded compressed amount for 366875659 (3.66875659 DUO)
345 //
346 // - 0x01: special script type pay-to-script-hash
347 //
348 // - 0x1d...e6: script hash
349 func deserializeUtxoEntryV0(serialized []byte) (map[uint32]*UtxoEntry, error) {
350 // Deserialize the version.
351 // NOTE: Ignore version since it is no longer used in the new format.
352 _, bytesRead := deserializeVLQ(serialized)
353 offset := bytesRead
354 if offset >= len(serialized) {
355 return nil, errDeserialize("unexpected end of data after version")
356 }
357 // Deserialize the block height.
358 blockHeight, bytesRead := deserializeVLQ(serialized[offset:])
359 offset += bytesRead
360 if offset >= len(serialized) {
361 return nil, errDeserialize("unexpected end of data after height")
362 }
363 // Deserialize the header code.
364 code, bytesRead := deserializeVLQ(serialized[offset:])
365 offset += bytesRead
366 if offset >= len(serialized) {
367 return nil, errDeserialize("unexpected end of data after header")
368 }
369 // Decode the header code.
370 //
371 // Bit 0 indicates whether the containing transaction is a coinbase.
372 //
373 // Bit 1 indicates output 0 is unspent.
374 //
375 // Bit 2 indicates output 1 is unspent.
376 //
377 // Bits 3-x encodes the number of non-zero unspentness bitmap bytes that follow. When both output 0 and 1 are spent,
378 // it encodes N-1.
379 isCoinBase := code&0x01 != 0
380 output0Unspent := code&0x02 != 0
381 output1Unspent := code&0x04 != 0
382 numBitmapBytes := code >> 3
383 if !output0Unspent && !output1Unspent {
384 numBitmapBytes++
385 }
386 // Ensure there are enough bytes left to deserialize the unspentness bitmap.
387 if uint64(len(serialized[offset:])) < numBitmapBytes {
388 return nil, errDeserialize(
389 "unexpected end of data for " +
390 "unspentness bitmap",
391 )
392 }
393 // Add sparse output for unspent outputs 0 and 1 as needed based on the details provided by the header code.
394 var outputIndexes []uint32
395 if output0Unspent {
396 outputIndexes = append(outputIndexes, 0)
397 }
398 if output1Unspent {
399 outputIndexes = append(outputIndexes, 1)
400 }
401 // Decode the unspentness bitmap adding a sparse output for each unspent output.
402 for i := uint32(0); i < uint32(numBitmapBytes); i++ {
403 unspentBits := serialized[offset]
404 for j := uint32(0); j < 8; j++ {
405 if unspentBits&0x01 != 0 {
406 // The first 2 outputs are encoded via the header code, so adjust the output number accordingly.
407 outputNum := 2 + i*8 + j
408 outputIndexes = append(outputIndexes, outputNum)
409 }
410 unspentBits >>= 1
411 }
412 offset++
413 }
414 // Map to hold all of the converted outputs.
415 entries := make(map[uint32]*UtxoEntry)
416 // All entries will need to potentially be marked as a coinbase.
417 var packedFlags txoFlags
418 if isCoinBase {
419 packedFlags |= tfCoinBase
420 }
421 // Decode and add all of the utxos.
422 for i, outputIndex := range outputIndexes {
423 // Decode the next utxo.
424 amount, pkScript, bytesRead, e := decodeCompressedTxOut(
425 serialized[offset:],
426 )
427 if e != nil {
428 return nil, errDeserialize(
429 fmt.Sprintf(
430 "unable to "+
431 "decode utxo at index %d: %v", i, e,
432 ),
433 )
434 }
435 offset += bytesRead
436 // Create a new utxo entry with the details deserialized above.
437 entries[outputIndex] = &UtxoEntry{
438 amount: int64(amount),
439 pkScript: pkScript,
440 blockHeight: int32(blockHeight),
441 packedFlags: packedFlags,
442 }
443 }
444 return entries, nil
445 }
446 447 // upgradeUtxoSetToV2 migrates the utxo set entries from version 1 to 2 in batches. It is guaranteed to updated if this
448 // returns without failure.
449 func upgradeUtxoSetToV2(db database.DB, interrupt <-chan struct{}) (e error) {
450 // Hardcoded bucket names so updates to the global values do not affect old upgrades.
451 var (
452 v1BucketName = []byte("utxoset")
453 v2BucketName = []byte("utxosetv2")
454 )
455 I.Ln("Upgrading utxo set to v2. This will take a while")
456 start := time.Now()
457 // Create the new utxo set bucket as needed.
458 e = db.Update(
459 func(dbTx database.Tx) (e error) {
460 _, e = dbTx.Metadata().CreateBucketIfNotExists(v2BucketName)
461 return e
462 },
463 )
464 if e != nil {
465 return e
466 }
467 // doBatch contains the primary logic for upgrading the utxo set from version 1 to 2 in batches. This is done
468 // because the utxo set can be huge and thus attempting to migrate in a single database transaction would result in
469 // massive memory usage and could potentially crash on many systems due to ulimits. It returns the number of utxos
470 // processed.
471 const maxUtxos = 200000
472 doBatch := func(dbTx database.Tx) (uint32, error) {
473 v1Bucket := dbTx.Metadata().Bucket(v1BucketName)
474 v2Bucket := dbTx.Metadata().Bucket(v2BucketName)
475 v1Cursor := v1Bucket.Cursor()
476 // Migrate utxos so long as the max number of utxos for this batch has not been exceeded.
477 var numUtxos uint32
478 for ok := v1Cursor.First(); ok && numUtxos < maxUtxos; ok =
479 v1Cursor.Next() {
480 // Old key was the transaction hash.
481 oldKey := v1Cursor.Key()
482 var txHash chainhash.Hash
483 copy(txHash[:], oldKey)
484 // Deserialize the old entry which included all utxos for the given transaction.
485 var utxos map[uint32]*UtxoEntry
486 utxos, e = deserializeUtxoEntryV0(v1Cursor.Value())
487 if e != nil {
488 return 0, e
489 }
490 // Add an entry for each utxo into the new bucket using the new format.
491 for txOutIdx, utxo := range utxos {
492 var reserialized []byte
493 reserialized, e = serializeUtxoEntry(utxo)
494 if e != nil {
495 return 0, e
496 }
497 key := outpointKey(
498 wire.OutPoint{
499 Hash: txHash,
500 Index: txOutIdx,
501 },
502 )
503 e = v2Bucket.Put(*key, reserialized)
504 // NOTE: The key is intentionally not recycled here since the database interface contract prohibits
505 // modifications. It will be garbage collected normally when the database is done with it.
506 if e != nil {
507 return 0, e
508 }
509 }
510 // Remove old entry.
511 e = v1Bucket.Delete(oldKey)
512 if e != nil {
513 return 0, e
514 }
515 numUtxos += uint32(len(utxos))
516 if interruptRequested(interrupt) {
517 // No error here so the database transaction is not cancelled and therefore outstanding work is written
518 // to disk.
519 break
520 }
521 }
522 return numUtxos, nil
523 }
524 // Migrate all entries in batches for the reasons mentioned above.
525 var totalUtxos uint64
526 for {
527 var numUtxos uint32
528 e = db.Update(
529 func(dbTx database.Tx) (e error) {
530 numUtxos, e = doBatch(dbTx)
531 return e
532 },
533 )
534 if e != nil {
535 return e
536 }
537 if interruptRequested(interrupt) {
538 return errInterruptRequested
539 }
540 if numUtxos == 0 {
541 break
542 }
543 totalUtxos += uint64(numUtxos)
544 I.F("migrated %d utxos (%d total)", numUtxos, totalUtxos)
545 }
546 // Remove the old bucket and update the utxo set version once it has been fully migrated.
547 e = db.Update(
548 func(dbTx database.Tx) (e error) {
549 e = dbTx.Metadata().DeleteBucket(v1BucketName)
550 if e != nil {
551 return e
552 }
553 return dbPutVersion(dbTx, utxoSetVersionKeyName, 2)
554 },
555 )
556 if e != nil {
557 return e
558 }
559 seconds := int64(time.Since(start) / time.Second)
560 I.F(
561 "Done upgrading utxo set. Total utxos: %d in %d seconds",
562 totalUtxos, seconds,
563 )
564 return nil
565 }
566 567 // maybeUpgradeDbBuckets checks the database version of the buckets used by this package and performs any needed
568 // upgrades to bring them to the latest version. All buckets used by this package are guaranteed to be the latest
569 // version if this function returns without error.
570 func (b *BlockChain) maybeUpgradeDbBuckets(interrupt <-chan struct{}) (e error) {
571 // Load or create bucket versions as needed.
572 var utxoSetVersion uint32
573 e = b.db.Update(
574 func(dbTx database.Tx) (e error) {
575 // Load the utxo set version from the database or create it and initialize it to version 1 if it doesn't exist.
576 utxoSetVersion, e = dbFetchOrCreateVersion(
577 dbTx,
578 utxoSetVersionKeyName, 1,
579 )
580 return e
581 },
582 )
583 if e != nil {
584 return e
585 }
586 // Update the utxo set to v2 if needed.
587 if utxoSetVersion < 2 {
588 if e := upgradeUtxoSetToV2(b.db, interrupt); E.Chk(e) {
589 return e
590 }
591 }
592 return nil
593 }
594