mirror of
https://github.com/kaspanet/kaspad.git
synced 2025-03-30 15:08:33 +00:00
684cf4b5fa
* [NOD-406] Don't do ECMH operations on mempool * [NOD-406] Change NewUTXODiff(false) to NewUTXODiffWithoutMultiset * [NOD-406] Rename dClone -> clone * [NOD-406] Remove redudnant assignment * [NOD-406] Remove dag.UTXOToECMHCacheLock and make NewBlockTemplate use dag's write lock * [NOD-406] Add tests to UTXO diffs without multiset
907 lines
30 KiB
Go
907 lines
30 KiB
Go
package blockdag
|
|
|
|
import (
|
|
"fmt"
|
|
"github.com/pkg/errors"
|
|
"math"
|
|
"sort"
|
|
"strings"
|
|
|
|
"github.com/daglabs/btcd/btcec"
|
|
"github.com/daglabs/btcd/wire"
|
|
)
|
|
|
|
const (
|
|
// UnacceptedBlueScore is the blue score used for the "block" blueScore
|
|
// field of the contextual transaction information provided in a
|
|
// transaction store when it has not yet been accepted by a block.
|
|
UnacceptedBlueScore uint64 = math.MaxUint64
|
|
)
|
|
|
|
// UTXOEntry houses details about an individual transaction output in a utxo
|
|
// set such as whether or not it was contained in a coinbase tx, the blue
|
|
// score of the block that accepts the tx, its public key script, and how
|
|
// much it pays.
|
|
type UTXOEntry struct {
|
|
// NOTE: Additions, deletions, or modifications to the order of the
|
|
// definitions in this struct should not be changed without considering
|
|
// how it affects alignment on 64-bit platforms. The current order is
|
|
// specifically crafted to result in minimal padding. There will be a
|
|
// lot of these in memory, so a few extra bytes of padding adds up.
|
|
|
|
amount uint64
|
|
scriptPubKey []byte // The public key script for the output.
|
|
blockBlueScore uint64 // Blue score of the block accepting the tx.
|
|
|
|
// packedFlags contains additional info about output such as whether it
|
|
// is a coinbase, and whether it has been modified
|
|
// since it was loaded. This approach is used in order to reduce memory
|
|
// usage since there will be a lot of these in memory.
|
|
packedFlags txoFlags
|
|
}
|
|
|
|
// IsCoinbase returns whether or not the output was contained in a block
|
|
// reward transaction.
|
|
func (entry *UTXOEntry) IsCoinbase() bool {
|
|
return entry.packedFlags&tfCoinbase == tfCoinbase
|
|
}
|
|
|
|
// BlockBlueScore returns the blue score of the block accepting the output.
|
|
func (entry *UTXOEntry) BlockBlueScore() uint64 {
|
|
return entry.blockBlueScore
|
|
}
|
|
|
|
// Amount returns the amount of the output.
|
|
func (entry *UTXOEntry) Amount() uint64 {
|
|
return entry.amount
|
|
}
|
|
|
|
// ScriptPubKey returns the public key script for the output.
|
|
func (entry *UTXOEntry) ScriptPubKey() []byte {
|
|
return entry.scriptPubKey
|
|
}
|
|
|
|
// IsUnaccepted returns true iff this UTXOEntry has been included in a block
|
|
// but has not yet been accepted by any block.
|
|
func (entry *UTXOEntry) IsUnaccepted() bool {
|
|
return entry.blockBlueScore == UnacceptedBlueScore
|
|
}
|
|
|
|
// txoFlags is a bitmask defining additional information and state for a
|
|
// transaction output in a UTXO set.
|
|
type txoFlags uint8
|
|
|
|
const (
|
|
// tfCoinbase indicates that a txout was contained in a coinbase tx.
|
|
tfCoinbase txoFlags = 1 << iota
|
|
)
|
|
|
|
// NewUTXOEntry creates a new utxoEntry representing the given txOut
|
|
func NewUTXOEntry(txOut *wire.TxOut, isCoinbase bool, blockBlueScore uint64) *UTXOEntry {
|
|
entry := &UTXOEntry{
|
|
amount: txOut.Value,
|
|
scriptPubKey: txOut.ScriptPubKey,
|
|
blockBlueScore: blockBlueScore,
|
|
}
|
|
|
|
if isCoinbase {
|
|
entry.packedFlags |= tfCoinbase
|
|
}
|
|
|
|
return entry
|
|
}
|
|
|
|
// utxoCollection represents a set of UTXOs indexed by their outpoints
|
|
type utxoCollection map[wire.Outpoint]*UTXOEntry
|
|
|
|
func (uc utxoCollection) String() string {
|
|
utxoStrings := make([]string, len(uc))
|
|
|
|
i := 0
|
|
for outpoint, utxoEntry := range uc {
|
|
utxoStrings[i] = fmt.Sprintf("(%s, %d) => %d, blueScore: %d",
|
|
outpoint.TxID, outpoint.Index, utxoEntry.amount, utxoEntry.blockBlueScore)
|
|
i++
|
|
}
|
|
|
|
// Sort strings for determinism.
|
|
sort.Strings(utxoStrings)
|
|
|
|
return fmt.Sprintf("[ %s ]", strings.Join(utxoStrings, ", "))
|
|
}
|
|
|
|
// add adds a new UTXO entry to this collection
|
|
func (uc utxoCollection) add(outpoint wire.Outpoint, entry *UTXOEntry) {
|
|
uc[outpoint] = entry
|
|
}
|
|
|
|
// remove removes a UTXO entry from this collection if it exists
|
|
func (uc utxoCollection) remove(outpoint wire.Outpoint) {
|
|
delete(uc, outpoint)
|
|
}
|
|
|
|
// get returns the UTXOEntry represented by provided outpoint,
|
|
// and a boolean value indicating if said UTXOEntry is in the set or not
|
|
func (uc utxoCollection) get(outpoint wire.Outpoint) (*UTXOEntry, bool) {
|
|
entry, ok := uc[outpoint]
|
|
return entry, ok
|
|
}
|
|
|
|
// contains returns a boolean value indicating whether a UTXO entry is in the set
|
|
func (uc utxoCollection) contains(outpoint wire.Outpoint) bool {
|
|
_, ok := uc[outpoint]
|
|
return ok
|
|
}
|
|
|
|
// containsWithBlueScore returns a boolean value indicating whether a UTXOEntry
|
|
// is in the set and its blue score is equal to the given blue score.
|
|
func (uc utxoCollection) containsWithBlueScore(outpoint wire.Outpoint, blueScore uint64) bool {
|
|
entry, ok := uc.get(outpoint)
|
|
return ok && entry.blockBlueScore == blueScore
|
|
}
|
|
|
|
// clone returns a clone of this collection
|
|
func (uc utxoCollection) clone() utxoCollection {
|
|
clone := utxoCollection{}
|
|
for outpoint, entry := range uc {
|
|
clone.add(outpoint, entry)
|
|
}
|
|
|
|
return clone
|
|
}
|
|
|
|
// UTXODiff represents a diff between two UTXO Sets.
|
|
type UTXODiff struct {
|
|
toAdd utxoCollection
|
|
toRemove utxoCollection
|
|
diffMultiset *btcec.Multiset
|
|
useMultiset bool
|
|
}
|
|
|
|
// NewUTXODiffWithoutMultiset creates a new, empty utxoDiff
|
|
// without a multiset.
|
|
func NewUTXODiffWithoutMultiset() *UTXODiff {
|
|
return &UTXODiff{
|
|
toAdd: utxoCollection{},
|
|
toRemove: utxoCollection{},
|
|
useMultiset: false,
|
|
}
|
|
}
|
|
|
|
// NewUTXODiff creates a new, empty utxoDiff.
|
|
func NewUTXODiff() *UTXODiff {
|
|
return &UTXODiff{
|
|
toAdd: utxoCollection{},
|
|
toRemove: utxoCollection{},
|
|
useMultiset: true,
|
|
diffMultiset: btcec.NewMultiset(btcec.S256()),
|
|
}
|
|
}
|
|
|
|
// diffFrom returns a new utxoDiff with the difference between this utxoDiff and another
|
|
// Assumes that:
|
|
// Both utxoDiffs are from the same base
|
|
// If a txOut exists in both utxoDiffs, its underlying values would be the same
|
|
//
|
|
// diffFrom follows a set of rules represented by the following 3 by 3 table:
|
|
//
|
|
// | | this | |
|
|
// ---------+-----------+-----------+-----------+-----------
|
|
// | | toAdd | toRemove | None
|
|
// ---------+-----------+-----------+-----------+-----------
|
|
// other | toAdd | - | X | toAdd
|
|
// ---------+-----------+-----------+-----------+-----------
|
|
// | toRemove | X | - | toRemove
|
|
// ---------+-----------+-----------+-----------+-----------
|
|
// | None | toRemove | toAdd | -
|
|
//
|
|
// Key:
|
|
// - Don't add anything to the result
|
|
// X Return an error
|
|
// toAdd Add the UTXO into the toAdd collection of the result
|
|
// toRemove Add the UTXO into the toRemove collection of the result
|
|
//
|
|
// Examples:
|
|
// 1. This diff contains a UTXO in toAdd, and the other diff contains it in toRemove
|
|
// diffFrom results in an error
|
|
// 2. This diff contains a UTXO in toRemove, and the other diff does not contain it
|
|
// diffFrom results in the UTXO being added to toAdd
|
|
func (d *UTXODiff) diffFrom(other *UTXODiff) (*UTXODiff, error) {
|
|
result := UTXODiff{
|
|
toAdd: make(utxoCollection, len(d.toRemove)+len(other.toAdd)),
|
|
toRemove: make(utxoCollection, len(d.toAdd)+len(other.toRemove)),
|
|
useMultiset: d.useMultiset,
|
|
}
|
|
|
|
// Note that the following cases are not accounted for, as they are impossible
|
|
// as long as the base utxoSet is the same:
|
|
// - if utxoEntry is in d.toAdd and other.toRemove
|
|
// - if utxoEntry is in d.toRemove and other.toAdd
|
|
|
|
// All transactions in d.toAdd:
|
|
// If they are not in other.toAdd - should be added in result.toRemove
|
|
// If they are in other.toRemove - base utxoSet is not the same
|
|
for outpoint, utxoEntry := range d.toAdd {
|
|
if !other.toAdd.containsWithBlueScore(outpoint, utxoEntry.blockBlueScore) {
|
|
result.toRemove.add(outpoint, utxoEntry)
|
|
}
|
|
if diffEntry, ok := other.toRemove.get(outpoint); ok {
|
|
// An exception is made for entries with unequal blue scores
|
|
// as long as the appropriate entry exists in either d.toRemove
|
|
// or other.toAdd.
|
|
// These are just "updates" to accepted blue score
|
|
if diffEntry.blockBlueScore != utxoEntry.blockBlueScore &&
|
|
(d.toRemove.containsWithBlueScore(outpoint, diffEntry.blockBlueScore) ||
|
|
other.toAdd.containsWithBlueScore(outpoint, utxoEntry.blockBlueScore)) {
|
|
continue
|
|
}
|
|
return nil, errors.Errorf("diffFrom: outpoint %s both in d.toAdd and in other.toRemove", outpoint)
|
|
}
|
|
}
|
|
|
|
// All transactions in d.toRemove:
|
|
// If they are not in other.toRemove - should be added in result.toAdd
|
|
// If they are in other.toAdd - base utxoSet is not the same
|
|
for outpoint, utxoEntry := range d.toRemove {
|
|
if !other.toRemove.containsWithBlueScore(outpoint, utxoEntry.blockBlueScore) {
|
|
result.toAdd.add(outpoint, utxoEntry)
|
|
}
|
|
if diffEntry, ok := other.toAdd.get(outpoint); ok {
|
|
// An exception is made for entries with unequal blue scores
|
|
// as long as the appropriate entry exists in either d.toAdd
|
|
// or other.toRemove.
|
|
// These are just "updates" to accepted blue score
|
|
if diffEntry.blockBlueScore != utxoEntry.blockBlueScore &&
|
|
(d.toAdd.containsWithBlueScore(outpoint, diffEntry.blockBlueScore) ||
|
|
other.toRemove.containsWithBlueScore(outpoint, utxoEntry.blockBlueScore)) {
|
|
continue
|
|
}
|
|
return nil, errors.New("diffFrom: transaction both in d.toRemove and in other.toAdd")
|
|
}
|
|
}
|
|
|
|
// All transactions in other.toAdd:
|
|
// If they are not in d.toAdd - should be added in result.toAdd
|
|
for outpoint, utxoEntry := range other.toAdd {
|
|
if !d.toAdd.containsWithBlueScore(outpoint, utxoEntry.blockBlueScore) {
|
|
result.toAdd.add(outpoint, utxoEntry)
|
|
}
|
|
}
|
|
|
|
// All transactions in other.toRemove:
|
|
// If they are not in d.toRemove - should be added in result.toRemove
|
|
for outpoint, utxoEntry := range other.toRemove {
|
|
if !d.toRemove.containsWithBlueScore(outpoint, utxoEntry.blockBlueScore) {
|
|
result.toRemove.add(outpoint, utxoEntry)
|
|
}
|
|
}
|
|
|
|
if d.useMultiset {
|
|
// Create a new diffMultiset as the subtraction of the two diffs.
|
|
result.diffMultiset = other.diffMultiset.Subtract(d.diffMultiset)
|
|
}
|
|
|
|
return &result, nil
|
|
}
|
|
|
|
// WithDiff applies provided diff to this diff, creating a new utxoDiff, that would be the result if
|
|
// first d, and than diff were applied to the same base
|
|
//
|
|
// WithDiff follows a set of rules represented by the following 3 by 3 table:
|
|
//
|
|
// | | this | |
|
|
// ---------+-----------+-----------+-----------+-----------
|
|
// | | toAdd | toRemove | None
|
|
// ---------+-----------+-----------+-----------+-----------
|
|
// other | toAdd | X | - | toAdd
|
|
// ---------+-----------+-----------+-----------+-----------
|
|
// | toRemove | - | X | toRemove
|
|
// ---------+-----------+-----------+-----------+-----------
|
|
// | None | toAdd | toRemove | -
|
|
//
|
|
// Key:
|
|
// - Don't add anything to the result
|
|
// X Return an error
|
|
// toAdd Add the UTXO into the toAdd collection of the result
|
|
// toRemove Add the UTXO into the toRemove collection of the result
|
|
//
|
|
// Examples:
|
|
// 1. This diff contains a UTXO in toAdd, and the other diff contains it in toRemove
|
|
// WithDiff results in nothing being added
|
|
// 2. This diff contains a UTXO in toRemove, and the other diff does not contain it
|
|
// WithDiff results in the UTXO being added to toRemove
|
|
func (d *UTXODiff) WithDiff(diff *UTXODiff) (*UTXODiff, error) {
|
|
result := UTXODiff{
|
|
toAdd: make(utxoCollection, len(d.toAdd)+len(diff.toAdd)),
|
|
toRemove: make(utxoCollection, len(d.toRemove)+len(diff.toRemove)),
|
|
useMultiset: d.useMultiset,
|
|
}
|
|
|
|
// All transactions in d.toAdd:
|
|
// If they are not in diff.toRemove - should be added in result.toAdd
|
|
// If they are in diff.toAdd - should throw an error
|
|
// Otherwise - should be ignored
|
|
for outpoint, utxoEntry := range d.toAdd {
|
|
if !diff.toRemove.containsWithBlueScore(outpoint, utxoEntry.blockBlueScore) {
|
|
result.toAdd.add(outpoint, utxoEntry)
|
|
}
|
|
if diffEntry, ok := diff.toAdd.get(outpoint); ok {
|
|
// An exception is made for entries with unequal blue scores
|
|
// as long as the appropriate entry exists in either d.toRemove
|
|
// or diff.toRemove.
|
|
// These are just "updates" to accepted blue score
|
|
if diffEntry.blockBlueScore != utxoEntry.blockBlueScore &&
|
|
(d.toRemove.containsWithBlueScore(outpoint, diffEntry.blockBlueScore) ||
|
|
diff.toRemove.containsWithBlueScore(outpoint, utxoEntry.blockBlueScore)) {
|
|
continue
|
|
}
|
|
return nil, ruleError(ErrWithDiff, fmt.Sprintf("WithDiff: outpoint %s both in d.toAdd and in other.toAdd", outpoint))
|
|
}
|
|
}
|
|
|
|
// All transactions in d.toRemove:
|
|
// If they are not in diff.toAdd - should be added in result.toRemove
|
|
// If they are in diff.toRemove - should throw an error
|
|
// Otherwise - should be ignored
|
|
for outpoint, utxoEntry := range d.toRemove {
|
|
if !diff.toAdd.containsWithBlueScore(outpoint, utxoEntry.blockBlueScore) {
|
|
result.toRemove.add(outpoint, utxoEntry)
|
|
}
|
|
if diffEntry, ok := diff.toRemove.get(outpoint); ok {
|
|
// An exception is made for entries with unequal blue scores
|
|
// as long as the appropriate entry exists in either d.toAdd
|
|
// or diff.toAdd.
|
|
// These are just "updates" to accepted blue score
|
|
if diffEntry.blockBlueScore != utxoEntry.blockBlueScore &&
|
|
(d.toAdd.containsWithBlueScore(outpoint, diffEntry.blockBlueScore) ||
|
|
diff.toAdd.containsWithBlueScore(outpoint, utxoEntry.blockBlueScore)) {
|
|
continue
|
|
}
|
|
return nil, ruleError(ErrWithDiff, "WithDiff: transaction both in d.toRemove and in other.toRemove")
|
|
}
|
|
}
|
|
|
|
// All transactions in diff.toAdd:
|
|
// If they are not in d.toRemove - should be added in result.toAdd
|
|
for outpoint, utxoEntry := range diff.toAdd {
|
|
if !d.toRemove.containsWithBlueScore(outpoint, utxoEntry.blockBlueScore) {
|
|
result.toAdd.add(outpoint, utxoEntry)
|
|
}
|
|
}
|
|
|
|
// All transactions in diff.toRemove:
|
|
// If they are not in d.toAdd - should be added in result.toRemove
|
|
for outpoint, utxoEntry := range diff.toRemove {
|
|
if !d.toAdd.containsWithBlueScore(outpoint, utxoEntry.blockBlueScore) {
|
|
result.toRemove.add(outpoint, utxoEntry)
|
|
}
|
|
}
|
|
|
|
// Apply diff.diffMultiset to d.diffMultiset
|
|
if d.useMultiset {
|
|
result.diffMultiset = d.diffMultiset.Union(diff.diffMultiset)
|
|
}
|
|
|
|
return &result, nil
|
|
}
|
|
|
|
// clone returns a clone of this utxoDiff
|
|
func (d *UTXODiff) clone() *UTXODiff {
|
|
clone := &UTXODiff{
|
|
toAdd: d.toAdd.clone(),
|
|
toRemove: d.toRemove.clone(),
|
|
useMultiset: d.useMultiset,
|
|
}
|
|
if d.useMultiset {
|
|
clone.diffMultiset = d.diffMultiset.Clone()
|
|
}
|
|
return clone
|
|
}
|
|
|
|
// AddEntry adds a UTXOEntry to the diff
|
|
//
|
|
// If d.useMultiset is true, this function MUST be
|
|
// called with the DAG lock held.
|
|
func (d *UTXODiff) AddEntry(outpoint wire.Outpoint, entry *UTXOEntry) error {
|
|
if d.toRemove.containsWithBlueScore(outpoint, entry.blockBlueScore) {
|
|
d.toRemove.remove(outpoint)
|
|
} else if _, exists := d.toAdd[outpoint]; exists {
|
|
return errors.Errorf("AddEntry: Cannot add outpoint %s twice", outpoint)
|
|
} else {
|
|
d.toAdd.add(outpoint, entry)
|
|
}
|
|
|
|
if d.useMultiset {
|
|
newMs, err := addUTXOToMultiset(d.diffMultiset, entry, &outpoint)
|
|
if err != nil {
|
|
return err
|
|
}
|
|
d.diffMultiset = newMs
|
|
}
|
|
return nil
|
|
}
|
|
|
|
// RemoveEntry removes a UTXOEntry from the diff.
|
|
//
|
|
// If d.useMultiset is true, this function MUST be
|
|
// called with the DAG lock held.
|
|
func (d *UTXODiff) RemoveEntry(outpoint wire.Outpoint, entry *UTXOEntry) error {
|
|
if d.toAdd.containsWithBlueScore(outpoint, entry.blockBlueScore) {
|
|
d.toAdd.remove(outpoint)
|
|
} else if _, exists := d.toRemove[outpoint]; exists {
|
|
return errors.Errorf("removeEntry: Cannot remove outpoint %s twice", outpoint)
|
|
} else {
|
|
d.toRemove.add(outpoint, entry)
|
|
}
|
|
|
|
if d.useMultiset {
|
|
newMs, err := removeUTXOFromMultiset(d.diffMultiset, entry, &outpoint)
|
|
if err != nil {
|
|
return err
|
|
}
|
|
d.diffMultiset = newMs
|
|
}
|
|
return nil
|
|
}
|
|
|
|
func (d UTXODiff) String() string {
|
|
if d.useMultiset {
|
|
return fmt.Sprintf("toAdd: %s; toRemove: %s, Multiset-Hash: %s", d.toAdd, d.toRemove, d.diffMultiset.Hash())
|
|
}
|
|
return fmt.Sprintf("toAdd: %s; toRemove: %s", d.toAdd, d.toRemove)
|
|
}
|
|
|
|
// UTXOSet represents a set of unspent transaction outputs
|
|
// Every DAG has exactly one fullUTXOSet.
|
|
// When a new block arrives, it is validated and applied to the fullUTXOSet in the following manner:
|
|
// 1. Get the block's PastUTXO:
|
|
// 2. Add all the block's transactions to the block's PastUTXO
|
|
// 3. For each of the block's parents,
|
|
// 3.1. Rebuild their utxoDiff
|
|
// 3.2. Set the block as their diffChild
|
|
// 4. Create and initialize a new virtual block
|
|
// 5. Get the new virtual's PastUTXO
|
|
// 6. Rebuild the utxoDiff for all the tips
|
|
// 7. Convert (meld) the new virtual's diffUTXOSet into a fullUTXOSet. This updates the DAG's fullUTXOSet
|
|
type UTXOSet interface {
|
|
fmt.Stringer
|
|
diffFrom(other UTXOSet) (*UTXODiff, error)
|
|
WithDiff(utxoDiff *UTXODiff) (UTXOSet, error)
|
|
diffFromTx(tx *wire.MsgTx, acceptingBlueScore uint64) (*UTXODiff, error)
|
|
diffFromAcceptedTx(tx *wire.MsgTx, acceptingBlueScore uint64) (*UTXODiff, error)
|
|
AddTx(tx *wire.MsgTx, blockBlueScore uint64) (ok bool, err error)
|
|
clone() UTXOSet
|
|
Get(outpoint wire.Outpoint) (*UTXOEntry, bool)
|
|
Multiset() *btcec.Multiset
|
|
WithTransactions(transactions []*wire.MsgTx, blockBlueScore uint64, ignoreDoubleSpends bool) (UTXOSet, error)
|
|
}
|
|
|
|
// diffFromTx is a common implementation for diffFromTx, that works
|
|
// for both diff-based and full UTXO sets
|
|
// Returns a diff that is equivalent to provided transaction,
|
|
// or an error if provided transaction is not valid in the context of this UTXOSet
|
|
func diffFromTx(u UTXOSet, tx *wire.MsgTx, acceptingBlueScore uint64) (*UTXODiff, error) {
|
|
diff := NewUTXODiff()
|
|
isCoinbase := tx.IsCoinBase()
|
|
if !isCoinbase {
|
|
for _, txIn := range tx.TxIn {
|
|
if entry, ok := u.Get(txIn.PreviousOutpoint); ok {
|
|
err := diff.RemoveEntry(txIn.PreviousOutpoint, entry)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
} else {
|
|
return nil, ruleError(ErrMissingTxOut, fmt.Sprintf(
|
|
"Transaction %s is invalid because spends outpoint %s that is not in utxo set",
|
|
tx.TxID(), txIn.PreviousOutpoint))
|
|
}
|
|
}
|
|
}
|
|
for i, txOut := range tx.TxOut {
|
|
entry := NewUTXOEntry(txOut, isCoinbase, acceptingBlueScore)
|
|
outpoint := *wire.NewOutpoint(tx.TxID(), uint32(i))
|
|
err := diff.AddEntry(outpoint, entry)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
}
|
|
return diff, nil
|
|
}
|
|
|
|
// diffFromAcceptedTx is a common implementation for diffFromAcceptedTx, that works
|
|
// for both diff-based and full UTXO sets.
|
|
// Returns a diff that replaces an entry's blockBlueScore with the given acceptingBlueScore.
|
|
// Returns an error if the provided transaction's entry is not valid in the context
|
|
// of this UTXOSet.
|
|
func diffFromAcceptedTx(u UTXOSet, tx *wire.MsgTx, acceptingBlueScore uint64) (*UTXODiff, error) {
|
|
diff := NewUTXODiff()
|
|
isCoinbase := tx.IsCoinBase()
|
|
for i, txOut := range tx.TxOut {
|
|
// Fetch any unaccepted transaction
|
|
existingOutpoint := *wire.NewOutpoint(tx.TxID(), uint32(i))
|
|
existingEntry, ok := u.Get(existingOutpoint)
|
|
if !ok {
|
|
return nil, errors.Errorf("cannot accept outpoint %s because it doesn't exist in the given UTXO", existingOutpoint)
|
|
}
|
|
|
|
// Remove unaccepted entries
|
|
err := diff.RemoveEntry(existingOutpoint, existingEntry)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
|
|
// Add new entries with their accepting blue score
|
|
newEntry := NewUTXOEntry(txOut, isCoinbase, acceptingBlueScore)
|
|
err = diff.AddEntry(existingOutpoint, newEntry)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
}
|
|
return diff, nil
|
|
}
|
|
|
|
// FullUTXOSet represents a full list of transaction outputs and their values
|
|
type FullUTXOSet struct {
|
|
utxoCollection
|
|
UTXOMultiset *btcec.Multiset
|
|
}
|
|
|
|
// NewFullUTXOSet creates a new utxoSet with full list of transaction outputs and their values
|
|
func NewFullUTXOSet() *FullUTXOSet {
|
|
return &FullUTXOSet{
|
|
utxoCollection: utxoCollection{},
|
|
UTXOMultiset: btcec.NewMultiset(btcec.S256()),
|
|
}
|
|
}
|
|
|
|
// newFullUTXOSetFromUTXOCollection converts a utxoCollection to a FullUTXOSet
|
|
func newFullUTXOSetFromUTXOCollection(collection utxoCollection) (*FullUTXOSet, error) {
|
|
var err error
|
|
multiset := btcec.NewMultiset(btcec.S256())
|
|
for outpoint, utxoEntry := range collection {
|
|
multiset, err = addUTXOToMultiset(multiset, utxoEntry, &outpoint)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
}
|
|
return &FullUTXOSet{
|
|
utxoCollection: collection,
|
|
UTXOMultiset: multiset,
|
|
}, nil
|
|
}
|
|
|
|
// diffFrom returns the difference between this utxoSet and another
|
|
// diffFrom can only work when other is a diffUTXOSet, and its base utxoSet is this.
|
|
func (fus *FullUTXOSet) diffFrom(other UTXOSet) (*UTXODiff, error) {
|
|
otherDiffSet, ok := other.(*DiffUTXOSet)
|
|
if !ok {
|
|
return nil, errors.New("can't diffFrom two fullUTXOSets")
|
|
}
|
|
|
|
if otherDiffSet.base != fus {
|
|
return nil, errors.New("can diffFrom only with diffUTXOSet where this fullUTXOSet is the base")
|
|
}
|
|
|
|
return otherDiffSet.UTXODiff, nil
|
|
}
|
|
|
|
// WithDiff returns a utxoSet which is a diff between this and another utxoSet
|
|
func (fus *FullUTXOSet) WithDiff(other *UTXODiff) (UTXOSet, error) {
|
|
return NewDiffUTXOSet(fus, other.clone()), nil
|
|
}
|
|
|
|
// AddTx adds a transaction to this utxoSet and returns isAccepted=true iff it's valid in this UTXO's context.
|
|
// It returns error if something unexpected happens, such as serialization error (isAccepted=false doesn't
|
|
// necessarily means there's an error).
|
|
//
|
|
// This function MUST be called with the DAG lock held.
|
|
func (fus *FullUTXOSet) AddTx(tx *wire.MsgTx, blueScore uint64) (isAccepted bool, err error) {
|
|
isCoinbase := tx.IsCoinBase()
|
|
if !isCoinbase {
|
|
if !fus.containsInputs(tx) {
|
|
return false, nil
|
|
}
|
|
|
|
for _, txIn := range tx.TxIn {
|
|
outpoint := *wire.NewOutpoint(&txIn.PreviousOutpoint.TxID, txIn.PreviousOutpoint.Index)
|
|
err := fus.removeAndUpdateMultiset(outpoint)
|
|
if err != nil {
|
|
return false, err
|
|
}
|
|
}
|
|
}
|
|
|
|
for i, txOut := range tx.TxOut {
|
|
outpoint := *wire.NewOutpoint(tx.TxID(), uint32(i))
|
|
entry := NewUTXOEntry(txOut, isCoinbase, blueScore)
|
|
|
|
err := fus.addAndUpdateMultiset(outpoint, entry)
|
|
if err != nil {
|
|
return false, err
|
|
}
|
|
}
|
|
|
|
return true, nil
|
|
}
|
|
|
|
// diffFromTx returns a diff that is equivalent to provided transaction,
|
|
// or an error if provided transaction is not valid in the context of this UTXOSet
|
|
func (fus *FullUTXOSet) diffFromTx(tx *wire.MsgTx, acceptingBlueScore uint64) (*UTXODiff, error) {
|
|
return diffFromTx(fus, tx, acceptingBlueScore)
|
|
}
|
|
|
|
func (fus *FullUTXOSet) containsInputs(tx *wire.MsgTx) bool {
|
|
for _, txIn := range tx.TxIn {
|
|
outpoint := *wire.NewOutpoint(&txIn.PreviousOutpoint.TxID, txIn.PreviousOutpoint.Index)
|
|
if !fus.contains(outpoint) {
|
|
return false
|
|
}
|
|
}
|
|
|
|
return true
|
|
}
|
|
|
|
func (fus *FullUTXOSet) diffFromAcceptedTx(tx *wire.MsgTx, acceptingBlueScore uint64) (*UTXODiff, error) {
|
|
return diffFromAcceptedTx(fus, tx, acceptingBlueScore)
|
|
}
|
|
|
|
// clone returns a clone of this utxoSet
|
|
func (fus *FullUTXOSet) clone() UTXOSet {
|
|
return &FullUTXOSet{utxoCollection: fus.utxoCollection.clone(), UTXOMultiset: fus.UTXOMultiset.Clone()}
|
|
}
|
|
|
|
// Get returns the UTXOEntry associated with the given Outpoint, and a boolean indicating if such entry was found
|
|
func (fus *FullUTXOSet) Get(outpoint wire.Outpoint) (*UTXOEntry, bool) {
|
|
utxoEntry, ok := fus.utxoCollection[outpoint]
|
|
return utxoEntry, ok
|
|
}
|
|
|
|
// Multiset returns the ecmh-Multiset of this utxoSet
|
|
func (fus *FullUTXOSet) Multiset() *btcec.Multiset {
|
|
return fus.UTXOMultiset
|
|
}
|
|
|
|
// addAndUpdateMultiset adds a UTXOEntry to this utxoSet and updates its multiset accordingly
|
|
func (fus *FullUTXOSet) addAndUpdateMultiset(outpoint wire.Outpoint, entry *UTXOEntry) error {
|
|
fus.add(outpoint, entry)
|
|
newMs, err := addUTXOToMultiset(fus.UTXOMultiset, entry, &outpoint)
|
|
if err != nil {
|
|
return err
|
|
}
|
|
fus.UTXOMultiset = newMs
|
|
return nil
|
|
}
|
|
|
|
// removeAndUpdateMultiset removes a UTXOEntry from this utxoSet and updates its multiset accordingly
|
|
func (fus *FullUTXOSet) removeAndUpdateMultiset(outpoint wire.Outpoint) error {
|
|
entry, ok := fus.Get(outpoint)
|
|
if !ok {
|
|
return errors.Errorf("Couldn't find outpoint %s", outpoint)
|
|
}
|
|
fus.remove(outpoint)
|
|
var err error
|
|
newMs, err := removeUTXOFromMultiset(fus.UTXOMultiset, entry, &outpoint)
|
|
if err != nil {
|
|
return err
|
|
}
|
|
fus.UTXOMultiset = newMs
|
|
return nil
|
|
}
|
|
|
|
// WithTransactions returns a new UTXO Set with the added transactions.
|
|
//
|
|
// This function MUST be called with the DAG lock held.
|
|
func (fus *FullUTXOSet) WithTransactions(transactions []*wire.MsgTx, blockBlueScore uint64, ignoreDoubleSpends bool) (UTXOSet, error) {
|
|
diffSet := NewDiffUTXOSet(fus, NewUTXODiff())
|
|
for _, tx := range transactions {
|
|
isAccepted, err := diffSet.AddTx(tx, blockBlueScore)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
if !ignoreDoubleSpends && !isAccepted {
|
|
return nil, errors.Errorf("Transaction %s is not valid with the current UTXO set", tx.TxID())
|
|
}
|
|
}
|
|
return UTXOSet(diffSet), nil
|
|
}
|
|
|
|
// DiffUTXOSet represents a utxoSet with a base fullUTXOSet and a UTXODiff
|
|
type DiffUTXOSet struct {
|
|
base *FullUTXOSet
|
|
UTXODiff *UTXODiff
|
|
}
|
|
|
|
// NewDiffUTXOSet Creates a new utxoSet based on a base fullUTXOSet and a UTXODiff
|
|
func NewDiffUTXOSet(base *FullUTXOSet, diff *UTXODiff) *DiffUTXOSet {
|
|
return &DiffUTXOSet{
|
|
base: base,
|
|
UTXODiff: diff,
|
|
}
|
|
}
|
|
|
|
// diffFrom returns the difference between this utxoSet and another.
|
|
// diffFrom can work if other is this's base fullUTXOSet, or a diffUTXOSet with the same base as this
|
|
func (dus *DiffUTXOSet) diffFrom(other UTXOSet) (*UTXODiff, error) {
|
|
otherDiffSet, ok := other.(*DiffUTXOSet)
|
|
if !ok {
|
|
return nil, errors.New("can't diffFrom diffUTXOSet with fullUTXOSet")
|
|
}
|
|
|
|
if otherDiffSet.base != dus.base {
|
|
return nil, errors.New("can't diffFrom with another diffUTXOSet with a different base")
|
|
}
|
|
|
|
return dus.UTXODiff.diffFrom(otherDiffSet.UTXODiff)
|
|
}
|
|
|
|
// WithDiff return a new utxoSet which is a diffFrom between this and another utxoSet
|
|
func (dus *DiffUTXOSet) WithDiff(other *UTXODiff) (UTXOSet, error) {
|
|
diff, err := dus.UTXODiff.WithDiff(other)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
|
|
return NewDiffUTXOSet(dus.base, diff), nil
|
|
}
|
|
|
|
// AddTx adds a transaction to this utxoSet and returns true iff it's valid in this UTXO's context.
|
|
//
|
|
// If dus.UTXODiff.useMultiset is true, this function MUST be
|
|
// called with the DAG lock held.
|
|
func (dus *DiffUTXOSet) AddTx(tx *wire.MsgTx, blockBlueScore uint64) (bool, error) {
|
|
isCoinbase := tx.IsCoinBase()
|
|
if !isCoinbase && !dus.containsInputs(tx) {
|
|
return false, nil
|
|
}
|
|
|
|
err := dus.appendTx(tx, blockBlueScore, isCoinbase)
|
|
if err != nil {
|
|
return false, err
|
|
}
|
|
|
|
return true, nil
|
|
}
|
|
|
|
func (dus *DiffUTXOSet) appendTx(tx *wire.MsgTx, blockBlueScore uint64, isCoinbase bool) error {
|
|
if !isCoinbase {
|
|
for _, txIn := range tx.TxIn {
|
|
outpoint := *wire.NewOutpoint(&txIn.PreviousOutpoint.TxID, txIn.PreviousOutpoint.Index)
|
|
entry, ok := dus.Get(outpoint)
|
|
if !ok {
|
|
return errors.Errorf("Couldn't find entry for outpoint %s", outpoint)
|
|
}
|
|
err := dus.UTXODiff.RemoveEntry(outpoint, entry)
|
|
if err != nil {
|
|
return err
|
|
}
|
|
}
|
|
}
|
|
|
|
for i, txOut := range tx.TxOut {
|
|
outpoint := *wire.NewOutpoint(tx.TxID(), uint32(i))
|
|
entry := NewUTXOEntry(txOut, isCoinbase, blockBlueScore)
|
|
|
|
err := dus.UTXODiff.AddEntry(outpoint, entry)
|
|
if err != nil {
|
|
return err
|
|
}
|
|
}
|
|
return nil
|
|
}
|
|
|
|
func (dus *DiffUTXOSet) containsInputs(tx *wire.MsgTx) bool {
|
|
for _, txIn := range tx.TxIn {
|
|
outpoint := *wire.NewOutpoint(&txIn.PreviousOutpoint.TxID, txIn.PreviousOutpoint.Index)
|
|
isInBase := dus.base.contains(outpoint)
|
|
isInDiffToAdd := dus.UTXODiff.toAdd.contains(outpoint)
|
|
isInDiffToRemove := dus.UTXODiff.toRemove.contains(outpoint)
|
|
if (!isInBase && !isInDiffToAdd) || (isInDiffToRemove && !(isInBase && isInDiffToAdd)) {
|
|
return false
|
|
}
|
|
}
|
|
|
|
return true
|
|
}
|
|
|
|
// meldToBase updates the base fullUTXOSet with all changes in diff
|
|
func (dus *DiffUTXOSet) meldToBase() error {
|
|
for outpoint := range dus.UTXODiff.toRemove {
|
|
if _, ok := dus.base.Get(outpoint); ok {
|
|
dus.base.remove(outpoint)
|
|
} else {
|
|
return errors.Errorf("Couldn't remove outpoint %s because it doesn't exist in the DiffUTXOSet base", outpoint)
|
|
}
|
|
}
|
|
|
|
for outpoint, utxoEntry := range dus.UTXODiff.toAdd {
|
|
dus.base.add(outpoint, utxoEntry)
|
|
}
|
|
|
|
if dus.UTXODiff.useMultiset {
|
|
dus.base.UTXOMultiset = dus.base.UTXOMultiset.Union(dus.UTXODiff.diffMultiset)
|
|
}
|
|
|
|
if dus.UTXODiff.useMultiset {
|
|
dus.UTXODiff = NewUTXODiff()
|
|
} else {
|
|
dus.UTXODiff = NewUTXODiffWithoutMultiset()
|
|
}
|
|
return nil
|
|
}
|
|
|
|
// diffFromTx returns a diff that is equivalent to provided transaction,
|
|
// or an error if provided transaction is not valid in the context of this UTXOSet
|
|
func (dus *DiffUTXOSet) diffFromTx(tx *wire.MsgTx, acceptingBlueScore uint64) (*UTXODiff, error) {
|
|
return diffFromTx(dus, tx, acceptingBlueScore)
|
|
}
|
|
|
|
func (dus *DiffUTXOSet) diffFromAcceptedTx(tx *wire.MsgTx, acceptingBlueScore uint64) (*UTXODiff, error) {
|
|
return diffFromAcceptedTx(dus, tx, acceptingBlueScore)
|
|
}
|
|
|
|
func (dus *DiffUTXOSet) String() string {
|
|
return fmt.Sprintf("{Base: %s, To Add: %s, To Remove: %s, Multiset-Hash:%s}", dus.base, dus.UTXODiff.toAdd, dus.UTXODiff.toRemove, dus.Multiset().Hash())
|
|
}
|
|
|
|
// clone returns a clone of this UTXO Set
|
|
func (dus *DiffUTXOSet) clone() UTXOSet {
|
|
return NewDiffUTXOSet(dus.base.clone().(*FullUTXOSet), dus.UTXODiff.clone())
|
|
}
|
|
|
|
// Get returns the UTXOEntry associated with provided outpoint in this UTXOSet.
|
|
// Returns false in second output if this UTXOEntry was not found
|
|
func (dus *DiffUTXOSet) Get(outpoint wire.Outpoint) (*UTXOEntry, bool) {
|
|
if toRemoveEntry, ok := dus.UTXODiff.toRemove.get(outpoint); ok {
|
|
// An exception is made for entries with unequal blue scores
|
|
// These are just "updates" to accepted blue score
|
|
if toAddEntry, ok := dus.UTXODiff.toAdd.get(outpoint); ok && toAddEntry.blockBlueScore != toRemoveEntry.blockBlueScore {
|
|
return toAddEntry, true
|
|
}
|
|
return nil, false
|
|
}
|
|
if txOut, ok := dus.base.get(outpoint); ok {
|
|
return txOut, true
|
|
}
|
|
txOut, ok := dus.UTXODiff.toAdd.get(outpoint)
|
|
return txOut, ok
|
|
}
|
|
|
|
// Multiset returns the ecmh-Multiset of this utxoSet
|
|
func (dus *DiffUTXOSet) Multiset() *btcec.Multiset {
|
|
return dus.base.UTXOMultiset.Union(dus.UTXODiff.diffMultiset)
|
|
}
|
|
|
|
// WithTransactions returns a new UTXO Set with the added transactions.
|
|
//
|
|
// If dus.UTXODiff.useMultiset is true, this function MUST be
|
|
// called with the DAG lock held.
|
|
func (dus *DiffUTXOSet) WithTransactions(transactions []*wire.MsgTx, blockBlueScore uint64, ignoreDoubleSpends bool) (UTXOSet, error) {
|
|
diffSet := NewDiffUTXOSet(dus.base, dus.UTXODiff.clone())
|
|
for _, tx := range transactions {
|
|
isAccepted, err := diffSet.AddTx(tx, blockBlueScore)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
if !ignoreDoubleSpends && !isAccepted {
|
|
return nil, errors.Errorf("Transaction %s is not valid with the current UTXO set", tx.TxID())
|
|
}
|
|
}
|
|
return UTXOSet(diffSet), nil
|
|
}
|
|
|
|
func addUTXOToMultiset(ms *btcec.Multiset, entry *UTXOEntry, outpoint *wire.Outpoint) (*btcec.Multiset, error) {
|
|
utxoMS, err := utxoMultiset(entry, outpoint)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
return ms.Union(utxoMS), nil
|
|
}
|
|
|
|
func removeUTXOFromMultiset(ms *btcec.Multiset, entry *UTXOEntry, outpoint *wire.Outpoint) (*btcec.Multiset, error) {
|
|
utxoMS, err := utxoMultiset(entry, outpoint)
|
|
if err != nil {
|
|
return nil, err
|
|
}
|
|
return ms.Subtract(utxoMS), nil
|
|
}
|