1 package blockchain
2 3 import (
4 "fmt"
5 "github.com/p9c/p9/pkg/block"
6 7 "github.com/p9c/p9/pkg/chainhash"
8 "github.com/p9c/p9/pkg/database"
9 "github.com/p9c/p9/pkg/txscript"
10 "github.com/p9c/p9/pkg/util"
11 "github.com/p9c/p9/pkg/wire"
12 )
13 14 // txoFlags is a bitmask defining additional information and state for a transaction output in a utxo view.
15 type txoFlags uint8
16 17 const (
18 // tfCoinBase indicates that a txout was contained in a coinbase tx.
19 tfCoinBase txoFlags = 1 << iota
20 // tfSpent indicates that a txout is spent.
21 tfSpent
22 // tfModified indicates that a txout has been modified since it was loaded.
23 tfModified
24 )
25 26 // UtxoEntry houses details about an individual transaction output in a utxo view such as whether or not it was
27 // contained in a coinbase tx, the height of the block that contains the tx, whether or not it is spent, its public key
28 // script, and how much it pays.
29 type UtxoEntry struct {
30 // NOTE: Additions, deletions, or modifications to the order of the definitions in this struct should not be changed
31 // without considering how it affects alignment on 64-bit platforms. The current order is specifically crafted to
32 // result in minimal padding. There will be a lot of these in memory, so a few extra bytes of padding adds up.
33 amount int64
34 pkScript []byte // The public key script for the output.
35 blockHeight int32 // Height of block containing tx.
36 // packedFlags contains additional info about output such as whether it is a coinbase, whether it is spent, and
37 // whether it has been modified since it was loaded. This approach is used in order to reduce memory usage since
38 // there will be a lot of these in memory.
39 packedFlags txoFlags
40 }
41 42 // isModified returns whether or not the output has been modified since it was loaded.
43 func (entry *UtxoEntry) isModified() bool {
44 return entry.packedFlags&tfModified == tfModified
45 }
46 47 // IsCoinBase returns whether or not the output was contained in a coinbase transaction.
48 func (entry *UtxoEntry) IsCoinBase() bool {
49 return entry.packedFlags&tfCoinBase == tfCoinBase
50 }
51 52 // BlockHeight returns the height of the block containing the output.
53 func (entry *UtxoEntry) BlockHeight() int32 {
54 return entry.blockHeight
55 }
56 57 // IsSpent returns whether or not the output has been spent based upon the current state of the unspent transaction
58 // output view it was obtained from.
59 func (entry *UtxoEntry) IsSpent() bool {
60 return entry.packedFlags&tfSpent == tfSpent
61 }
62 63 // Spend marks the output as spent. Spending an output that is already spent has no effect.
64 func (entry *UtxoEntry) Spend() {
65 // Nothing to do if the output is already spent.
66 if entry.IsSpent() {
67 return
68 }
69 // Mark the output as spent and modified.
70 entry.packedFlags |= tfSpent | tfModified
71 }
72 73 // Amount returns the amount of the output.
74 func (entry *UtxoEntry) Amount() int64 {
75 return entry.amount
76 }
77 78 // PkScript returns the public key script for the output.
79 func (entry *UtxoEntry) PkScript() []byte {
80 return entry.pkScript
81 }
82 83 // Clone returns a shallow copy of the utxo entry.
84 func (entry *UtxoEntry) Clone() *UtxoEntry {
85 if entry == nil {
86 return nil
87 }
88 return &UtxoEntry{
89 amount: entry.amount,
90 pkScript: entry.pkScript,
91 blockHeight: entry.blockHeight,
92 packedFlags: entry.packedFlags,
93 }
94 }
95 96 // UtxoViewpoint represents a view into the set of unspent transaction outputs from a specific point of view in the
97 // chain. For example, it could be for the end of the main chain, some point in the history of the main chain, or down a
98 // side chain.
99 //
100 // The unspent outputs are needed by other transactions for things such as script validation and double spend
101 // prevention.
102 type UtxoViewpoint struct {
103 entries map[wire.OutPoint]*UtxoEntry
104 bestHash chainhash.Hash
105 }
106 107 // BestHash returns the hash of the best block in the chain the view currently represents.
108 func (view *UtxoViewpoint) BestHash() *chainhash.Hash {
109 return &view.bestHash
110 }
111 112 // SetBestHash sets the hash of the best block in the chain the view currently represents.
113 func (view *UtxoViewpoint) SetBestHash(hash *chainhash.Hash) {
114 view.bestHash = *hash
115 }
116 117 // LookupEntry returns information about a given transaction output according to the current state of the view. It will
118 // return nil if the passed output does not exist in the view or is otherwise not available such as when it has been
119 // disconnected during a reorg.
120 func (view *UtxoViewpoint) LookupEntry(outpoint wire.OutPoint) *UtxoEntry {
121 return view.entries[outpoint]
122 }
123 124 // addTxOut adds the specified output to the view if it is not provably unspendable. When the view already has an entry
125 // for the output, it will be marked unspent. All fields will be updated for existing entries since it's possible it has
126 // changed during a reorg.
127 func (view *UtxoViewpoint) addTxOut(outpoint wire.OutPoint, txOut *wire.TxOut, isCoinBase bool, blockHeight int32) {
128 // Don't add provably unspendable outputs.
129 if txscript.IsUnspendable(txOut.PkScript) {
130 return
131 }
132 // Update existing entries. All fields are updated because it's possible (although extremely unlikely) that the
133 // existing entry is being replaced by a different transaction with the same hash. This is allowed so long as the
134 // previous transaction is fully spent.
135 entry := view.LookupEntry(outpoint)
136 if entry == nil {
137 entry = new(UtxoEntry)
138 view.entries[outpoint] = entry
139 }
140 entry.amount = txOut.Value
141 entry.pkScript = txOut.PkScript
142 entry.blockHeight = blockHeight
143 entry.packedFlags = tfModified
144 if isCoinBase {
145 entry.packedFlags |= tfCoinBase
146 }
147 }
148 149 // AddTxOut adds the specified output of the passed transaction to the view if it exists and is not provably
150 // unspendable. When the view already has an entry for the output, it will be marked unspent. All fields will be updated
151 // for existing entries since it's possible it has changed during a reorg.
152 func (view *UtxoViewpoint) AddTxOut(tx *util.Tx, txOutIdx uint32, blockHeight int32) {
153 // Can't add an output for an out of bounds index.
154 if txOutIdx >= uint32(len(tx.MsgTx().TxOut)) {
155 return
156 }
157 // Update existing entries. All fields are updated because it's possible (although extremely unlikely) that the
158 // existing entry is being replaced by a different transaction with the same hash. This is allowed so long as the
159 // previous transaction is fully spent.
160 prevOut := wire.OutPoint{Hash: *tx.Hash(), Index: txOutIdx}
161 txOut := tx.MsgTx().TxOut[txOutIdx]
162 view.addTxOut(prevOut, txOut, IsCoinBase(tx), blockHeight)
163 }
164 165 // AddTxOuts adds all outputs in the passed transaction which are not provably unspendable to the view. When the view
166 // already has entries for any of the outputs, they are simply marked unspent. All fields will be updated for existing
167 // entries since it's possible it has changed during a reorg.
168 func (view *UtxoViewpoint) AddTxOuts(tx *util.Tx, blockHeight int32) {
169 // Loop all of the transaction outputs and add those which are not
170 // provably unspendable.
171 isCoinBase := IsCoinBase(tx)
172 prevOut := wire.OutPoint{Hash: *tx.Hash()}
173 for txOutIdx, txOut := range tx.MsgTx().TxOut {
174 // Update existing entries. All fields are updated because it's possible (although extremely unlikely) that the
175 // existing entry is being replaced by a different transaction with the same hash. This is allowed so long as
176 // the previous transaction is fully spent.
177 prevOut.Index = uint32(txOutIdx)
178 view.addTxOut(prevOut, txOut, isCoinBase, blockHeight)
179 }
180 }
181 182 // connectTransaction updates the view by adding all new utxos created by the passed transaction and marking all utxos
183 // that the transactions spend as spent.
184 //
185 // In addition, when the 'stxos' argument is not nil, it will be updated to append an entry for each spent txout. An
186 // error will be returned if the view does not contain the required utxos.
187 func (view *UtxoViewpoint) connectTransaction(tx *util.Tx, blockHeight int32, stxos *[]SpentTxOut) (e error) {
188 // Coinbase transactions don't have any inputs to spend.
189 if IsCoinBase(tx) {
190 // Add the transaction's outputs as available utxos.
191 view.AddTxOuts(tx, blockHeight)
192 return nil
193 }
194 // Spend the referenced utxos by marking them spent in the view and, if a slice was provided for the spent txout
195 // details, append an entry to it.
196 for _, txIn := range tx.MsgTx().TxIn {
197 // Ensure the referenced utxo exists in the view. This should never happen unless there is a bug is introduced
198 // in the code.
199 entry := view.entries[txIn.PreviousOutPoint]
200 if entry == nil {
201 return AssertError(
202 fmt.Sprintf(
203 "view missing input %v",
204 txIn.PreviousOutPoint,
205 ),
206 )
207 }
208 // Only create the stxo details if requested.
209 if stxos != nil {
210 // Populate the stxo details using the utxo entry.
211 var stxo = SpentTxOut{
212 Amount: entry.Amount(),
213 PkScript: entry.PkScript(),
214 Height: entry.BlockHeight(),
215 IsCoinBase: entry.IsCoinBase(),
216 }
217 *stxos = append(*stxos, stxo)
218 }
219 // Mark the entry as spent. This is not done until after the relevant details have been accessed since spending
220 // it might clear the fields from memory in the future.
221 entry.Spend()
222 }
223 // Add the transaction's outputs as available utxos.
224 view.AddTxOuts(tx, blockHeight)
225 return nil
226 }
227 228 // connectTransactions updates the view by adding all new utxos created by all of the transactions in the passed block,
229 // marking all utxos the transactions spend as spent, and setting the best hash for the view to the passed block. In
230 // addition, when the 'stxos' argument is not nil, it will be updated to append an entry for each spent txout.
231 func (view *UtxoViewpoint) connectTransactions(block *block.Block, stxos *[]SpentTxOut) (e error) {
232 for _, tx := range block.Transactions() {
233 e = view.connectTransaction(tx, block.Height(), stxos)
234 if e != nil {
235 return e
236 }
237 }
238 // Update the best hash for view to include this block since all of its transactions have been connected.
239 view.SetBestHash(block.Hash())
240 return nil
241 }
242 243 // fetchEntryByHash attempts to find any available utxo for the given hash by searching the entire set of possible
244 // outputs for the given hash. It checks the view first and then falls back to the database if needed.
245 func (view *UtxoViewpoint) fetchEntryByHash(db database.DB, hash *chainhash.Hash) (entry *UtxoEntry, e error) {
246 // First attempt to find a utxo with the provided hash in the view.
247 prevOut := wire.OutPoint{Hash: *hash}
248 for idx := uint32(0); idx < MaxOutputsPerBlock; idx++ {
249 prevOut.Index = idx
250 entry = view.LookupEntry(prevOut)
251 if entry != nil {
252 return entry, nil
253 }
254 }
255 // Chk the database since it doesn't exist in the view. This will often by the case since only specifically
256 // referenced utxos are loaded into the view.
257 e = db.View(
258 func(dbTx database.Tx) (e error) {
259 entry, e = dbFetchUtxoEntryByHash(dbTx, hash)
260 return e
261 },
262 )
263 return entry, e
264 }
265 266 // disconnectTransactions updates the view by removing all of the transactions created by the passed block, restoring
267 // all utxos the transactions spent by using the provided spent txo information, and setting the best hash for the view
268 // to the block before the passed block.
269 func (view *UtxoViewpoint) disconnectTransactions(db database.DB, block *block.Block, stxos []SpentTxOut) (e error) {
270 // Sanity check the correct number of stxos are provided.
271 if len(stxos) != countSpentOutputs(block) {
272 return AssertError(
273 "disconnectTransactions called with bad " +
274 "spent transaction out information",
275 )
276 }
277 // Loop backwards through all transactions so everything is unspent in reverse order. This is necessary since
278 // transactions later in a block can spend from previous ones.
279 stxoIdx := len(stxos) - 1
280 transactions := block.Transactions()
281 for txIdx := len(transactions) - 1; txIdx > -1; txIdx-- {
282 tx := transactions[txIdx]
283 // All entries will need to potentially be marked as a coinbase.
284 var packedFlags txoFlags
285 isCoinBase := txIdx == 0
286 if isCoinBase {
287 packedFlags |= tfCoinBase
288 }
289 // Mark all of the spendable outputs originally created by the transaction as spent. It is instructive to note
290 // that while the outputs aren't actually being spent here, rather they no longer exist, since a pruned utxo set
291 // is used, there is no practical difference between a utxo that does not exist and one that has been spent.
292 //
293 // When the utxo does not already exist in the view, add an entry for it and then mark it spent. This is done
294 // because the code relies on its existence in the view in order to signal modifications have happened.
295 txHash := tx.Hash()
296 prevOut := wire.OutPoint{Hash: *txHash}
297 for txOutIdx, txOut := range tx.MsgTx().TxOut {
298 if txscript.IsUnspendable(txOut.PkScript) {
299 continue
300 }
301 prevOut.Index = uint32(txOutIdx)
302 entry := view.entries[prevOut]
303 if entry == nil {
304 entry = &UtxoEntry{
305 amount: txOut.Value,
306 pkScript: txOut.PkScript,
307 blockHeight: block.Height(),
308 packedFlags: packedFlags,
309 }
310 view.entries[prevOut] = entry
311 }
312 entry.Spend()
313 }
314 // Loop backwards through all of the transaction inputs (except for the coinbase which has no inputs) and
315 // unspend the referenced txos. This is necessary to match the order of the spent txout entries.
316 if isCoinBase {
317 continue
318 }
319 for txInIdx := len(tx.MsgTx().TxIn) - 1; txInIdx > -1; txInIdx-- {
320 // Ensure the spent txout index is decremented to stay in sync with the transaction input.
321 stxo := &stxos[stxoIdx]
322 stxoIdx--
323 // When there is not already an entry for the referenced output in the view, it means it was previously
324 // spent, so create a new utxo entry in order to resurrect it.
325 originOut := &tx.MsgTx().TxIn[txInIdx].PreviousOutPoint
326 entry := view.entries[*originOut]
327 if entry == nil {
328 entry = new(UtxoEntry)
329 view.entries[*originOut] = entry
330 }
331 // The legacy v1 spend journal format only stored the coinbase flag and height when the output was the last
332 // unspent output of the transaction. As a result, when the information is missing, search for it by
333 // scanning all possible outputs of the transaction since it must be in one of them.
334 //
335 // It should be noted that this is quite inefficient, but it realistically will almost never run since all
336 // new entries include the information for all outputs and thus the only way this will be hit is if a long
337 // enough reorg happens such that a block with the old spend data is being disconnected. The probability of
338 // that in practice is extremely low to begin with and becomes vanishingly small the more new blocks are
339 // connected. In the case of a fresh database that has only ever run with the new v2 format, this code path
340 // will never run.
341 if stxo.Height == 0 {
342 utxo, e := view.fetchEntryByHash(db, txHash)
343 if e != nil {
344 return e
345 }
346 if utxo == nil {
347 return AssertError(
348 fmt.Sprintf(
349 "unable "+
350 "to resurrect legacy stxo %v",
351 *originOut,
352 ),
353 )
354 }
355 stxo.Height = utxo.BlockHeight()
356 stxo.IsCoinBase = utxo.IsCoinBase()
357 }
358 // Restore the utxo using the stxo data from the spend journal and mark it as modified.
359 entry.amount = stxo.Amount
360 entry.pkScript = stxo.PkScript
361 entry.blockHeight = stxo.Height
362 entry.packedFlags = tfModified
363 if stxo.IsCoinBase {
364 entry.packedFlags |= tfCoinBase
365 }
366 }
367 }
368 // Update the best hash for view to the previous block since all of the transactions for the current block have been
369 // disconnected.
370 view.SetBestHash(&block.WireBlock().Header.PrevBlock)
371 return nil
372 }
373 374 // RemoveEntry removes the given transaction output from the current state of the view. It will have no effect if the
375 // passed output does not exist in the view.
376 func (view *UtxoViewpoint) RemoveEntry(outpoint wire.OutPoint) {
377 delete(view.entries, outpoint)
378 }
379 380 // Entries returns the underlying map that stores of all the utxo entries.
381 func (view *UtxoViewpoint) Entries() map[wire.OutPoint]*UtxoEntry {
382 return view.entries
383 }
384 385 // commit prunes all entries marked modified that are now fully spent and marks all entries as unmodified.
386 func (view *UtxoViewpoint) commit() {
387 for outpoint, entry := range view.entries {
388 if entry == nil || (entry.isModified() && entry.IsSpent()) {
389 delete(view.entries, outpoint)
390 continue
391 }
392 entry.packedFlags ^= tfModified
393 }
394 }
395 396 // fetchUtxosMain fetches unspent transaction output data about the provided set of outpoints from the point of view of
397 // the end of the main chain at the time of the call.
398 //
399 // Upon completion of this function, the view will contain an entry for each requested outpoint. Spent outputs, or those
400 // which otherwise don't exist, will result in a nil entry in the view.
401 func (view *UtxoViewpoint) fetchUtxosMain(db database.DB, outpoints map[wire.OutPoint]struct{}) (e error) {
402 // Nothing to do if there are no requested outputs.
403 if len(outpoints) == 0 {
404 return nil
405 }
406 // Load the requested set of unspent transaction outputs from the point of view of the end of the main chain.
407 //
408 // NOTE: Missing entries are not considered an error here and instead will result in nil entries in the view. This
409 // is intentionally done so other code can use the presence of an entry in the store as a way to unnecessarily avoid
410 // attempting to reload it from the database.
411 return db.View(
412 func(dbTx database.Tx) (e error) {
413 for outpoint := range outpoints {
414 entry, e := dbFetchUtxoEntry(dbTx, outpoint)
415 if e != nil {
416 return e
417 }
418 view.entries[outpoint] = entry
419 }
420 return nil
421 },
422 )
423 }
424 425 // fetchUtxos loads the unspent transaction outputs for the provided set of outputs into the view from the database as
426 // needed unless they already exist in the view in which case they are ignored.
427 func (view *UtxoViewpoint) fetchUtxos(db database.DB, outpoints map[wire.OutPoint]struct{}) (e error) {
428 // Nothing to do if there are no requested outputs.
429 if len(outpoints) == 0 {
430 return nil
431 }
432 // Filter entries that are already in the view.
433 neededSet := make(map[wire.OutPoint]struct{})
434 for outpoint := range outpoints {
435 // Already loaded into the current view.
436 if _, ok := view.entries[outpoint]; ok {
437 continue
438 }
439 neededSet[outpoint] = struct{}{}
440 }
441 // Request the input utxos from the database.
442 return view.fetchUtxosMain(db, neededSet)
443 }
444 445 // fetchInputUtxos loads the unspent transaction outputs for the inputs referenced by the transactions in the given
446 // block into the view from the database as needed. In particular, referenced entries that are earlier in the block are
447 // added to the view and entries that are already in the view are not modified.
448 func (view *UtxoViewpoint) fetchInputUtxos(db database.DB, block *block.Block) (e error) {
449 // Build a map of in-flight transactions because some of the inputs in this block could be referencing other
450 // transactions earlier in this block which are not yet in the chain.
451 txInFlight := map[chainhash.Hash]int{}
452 transactions := block.Transactions()
453 for i, tx := range transactions {
454 txInFlight[*tx.Hash()] = i
455 }
456 // Loop through all of the transaction inputs (except for the coinbase which has no inputs) collecting them into
457 // sets of what is needed and what is already known (in-flight).
458 neededSet := make(map[wire.OutPoint]struct{})
459 for i, tx := range transactions[1:] {
460 for _, txIn := range tx.MsgTx().TxIn {
461 // It is acceptable for a transaction input to reference the output of another transaction in this block
462 // only if the referenced transaction comes before the current one in this block. Add the outputs of the
463 // referenced transaction as available utxos when this is the case. Otherwise, the utxo details are still
464 // needed.
465 //
466 // NOTE: The >= is correct here because i is one less than the actual position of the transaction within the
467 // block due to skipping the coinbase.
468 originHash := &txIn.PreviousOutPoint.Hash
469 if inFlightIndex, ok := txInFlight[*originHash]; ok &&
470 i >= inFlightIndex {
471 originTx := transactions[inFlightIndex]
472 view.AddTxOuts(originTx, block.Height())
473 continue
474 }
475 // Don't request entries that are already in the view from the database.
476 if _, ok := view.entries[txIn.PreviousOutPoint]; ok {
477 continue
478 }
479 neededSet[txIn.PreviousOutPoint] = struct{}{}
480 }
481 }
482 // Request the input utxos from the database.
483 return view.fetchUtxosMain(db, neededSet)
484 }
485 486 // NewUtxoViewpoint returns a new empty unspent transaction output view.
487 func NewUtxoViewpoint() *UtxoViewpoint {
488 return &UtxoViewpoint{
489 entries: make(map[wire.OutPoint]*UtxoEntry),
490 }
491 }
492 493 // FetchUtxoView loads unspent transaction outputs for the inputs referenced by the passed transaction from the point of
494 // view of the end of the main chain.
495 //
496 // It also attempts to fetch the utxos for the outputs of the transaction itself so the returned view can be examined
497 // for duplicate transactions.
498 //
499 // This function is safe for concurrent access however the returned view is NOT.
500 func (b *BlockChain) FetchUtxoView(tx *util.Tx) (view *UtxoViewpoint, e error) {
501 // Create a set of needed outputs based on those referenced by the inputs of the passed transaction and the outputs
502 // of the transaction itself.
503 neededSet := make(map[wire.OutPoint]struct{})
504 prevOut := wire.OutPoint{Hash: *tx.Hash()}
505 for txOutIdx := range tx.MsgTx().TxOut {
506 prevOut.Index = uint32(txOutIdx)
507 neededSet[prevOut] = struct{}{}
508 }
509 if !IsCoinBase(tx) {
510 for _, txIn := range tx.MsgTx().TxIn {
511 neededSet[txIn.PreviousOutPoint] = struct{}{}
512 }
513 }
514 // Request the utxos from the point of view of the end of the main
515 // chain.
516 view = NewUtxoViewpoint()
517 b.ChainLock.RLock()
518 e = view.fetchUtxosMain(b.db, neededSet)
519 b.ChainLock.RUnlock()
520 return view, e
521 }
522 523 // FetchUtxoEntry loads and returns the requested unspent transaction output from the point of view of the end of the
524 // main chain.
525 //
526 // NOTE: Requesting an output for which there is no data will NOT return an error. Instead both the entry and the error
527 // will be nil. This is done to allow pruning of spent transaction outputs. In practice this means the caller must check
528 // if the returned entry is nil before invoking methods on it.
529 //
530 // This function is safe for concurrent access however the returned entry (if any) is NOT.
531 // TODO: concurrent unsafe and copy creation should be universal and able to be expected
532 func (b *BlockChain) FetchUtxoEntry(outpoint wire.OutPoint) (*UtxoEntry, error) {
533 b.ChainLock.RLock()
534 defer b.ChainLock.RUnlock()
535 var entry *UtxoEntry
536 e := b.db.View(
537 func(dbTx database.Tx) (e error) {
538 entry, e = dbFetchUtxoEntry(dbTx, outpoint)
539 return e
540 },
541 )
542 if e != nil {
543 return nil, e
544 }
545 return entry, nil
546 }
547