standalone

package module
v1.1.1 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jun 10, 2023 License: ISC Imports: 7 Imported by: 14

README

standalone

Build Status ISC License GoDoc

Package standalone provides standalone functions useful for working with the Decred blockchain consensus rules.

The primary goal of offering these functions via a separate module is to reduce the required dependencies to a minimum as compared to the blockchain module.

It is ideal for applications such as lightweight clients that need to ensure basic security properties hold and calculate appropriate vote subsidies and block explorers.

For example, some things an SPV wallet needs to prove are that the block headers all connect together, that they satisfy the proof of work requirements, and that a given transaction tree is valid for a given header.

The provided functions fall into the following categories:

  • Proof-of-work
    • Converting to and from the compact target difficulty representation
    • Calculating work values based on the compact target difficulty
    • Checking a block hash satisfies a target difficulty and that target difficulty is within a valid range
  • Merkle root calculation
    • Calculation from individual leaf hashes
    • Calculation from a slice of transactions
  • Subsidy calculation
    • Proof-of-work subsidy for a given height and number of votes
    • Stake vote subsidy for a given height
    • Treasury subsidy for a given height and number of votes
  • Coinbase transaction identification

Installation and Updating

$ go get -u github.com/decred/dcrd/blockchain/standalone

Examples

  • CompactToBig Example
    Demonstrates how to convert the compact "bits" in a block header which represent the target difficulty to a big integer and display it using the typical hex notation.

  • BigToCompact Example
    Demonstrates how to convert a target difficulty into the compact "bits" in a block header which represent that target difficulty.

  • CheckProofOfWork Example
    Demonstrates checking the proof of work of a block hash against a target difficulty.

  • CalcMerkleRoot Example
    Demonstrates calculating a merkle root from a slice of leaf hashes.

License

Package standalone is licensed under the copyfree ISC License.

Documentation

Overview

Package standalone provides standalone functions useful for working with the Decred blockchain consensus rules.

The primary goal of offering these functions via a separate module is to reduce the required dependencies to a minimum as compared to the blockchain module.

It is ideal for applications such as lightweight clients that need to ensure basic security properties hold and calculate appropriate vote subsidies and block explorers.

For example, some things an SPV wallet needs to prove are that the block headers all connect together, that they satisfy the proof of work requirements, and that a given transaction tree is valid for a given header.

The provided functions fall into the following categories:

  • Proof-of-work
  • Converting to and from the compact target difficulty representation
  • Calculating work values based on the compact target difficulty
  • Checking a block hash satisfies a target difficulty and that target difficulty is within a valid range
  • Merkle root calculation
  • Calculation from individual leaf hashes
  • Calculation from a slice of transactions
  • Subsidy calculation
  • Proof-of-work subsidy for a given height and number of votes
  • Stake vote subsidy for a given height
  • Treasury subsidy for a given height and number of votes
  • Coinbase transaction identification
  • Merkle tree inclusion proofs
  • Generate an inclusion proof for a given tree and leaf index
  • Verify a leaf is a member of the tree at a given index via the proof

Errors

Errors returned by this package are of type standalone.RuleError. This allows the caller to differentiate between errors further up the call stack through type assertions. In addition, callers can programmatically determine the specific rule violation by examining the ErrorCode field of the type asserted standalone.RuleError.

Index

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func BigToCompact 

func BigToCompact(n *big.Int) uint32

BigToCompact converts a whole number N to a compact representation using an unsigned 32-bit number. The compact representation only provides 23 bits of precision, so values larger than (2^23 - 1) only encode the most significant digits of the number. See CompactToBig for details.

Example

This example demonstrates how to convert a target difficulty into the compact "bits" in a block header which represent that target difficulty. 

package main

import (
	"fmt"
	"math/big"

	"github.com/decred/dcrd/blockchain/standalone"
)

func main() {
	// Convert the target difficulty from block 1 in the main chain to compact
	// form.
	t := "000000000001ffff000000000000000000000000000000000000000000000000"
	targetDifficulty, success := new(big.Int).SetString(t, 16)
	if !success {
		fmt.Println("invalid target difficulty")
		return
	}
	bits := standalone.BigToCompact(targetDifficulty)

	fmt.Println(bits)

}

Output:

453115903

func CalcCombinedTxTreeMerkleRoot added in v1.1.0 

func CalcCombinedTxTreeMerkleRoot(regularTxns, stakeTxns []*wire.MsgTx) chainhash.Hash

CalcCombinedTxTreeMerkleRoot calculates and returns the combined merkle root for the provided regular and stake transaction trees in accordance with DCP0005.

In particular, the final merkle root is the result of a merkle tree that itself has the individual merkle roots of the two transaction trees as leaves. The full (including witness data) hashes for the transactions are used as required for merkle roots.

A diagram depicting this follows: 

root = blake256(regularTreeRoot || stakeTreeRoot)
          /                           \
   regularTreeRoot               stakeTreeRoot

It is also worth noting that it also happens to be exactly equivalent to the blake256 hash of the concatenation of the two individual merkle roots due to the way two leaf merkle trees are calculated: 

blake256(regularTreeRoot || stakeTreeRoot)

func CalcMerkleRoot 

func CalcMerkleRoot(leaves []chainhash.Hash) chainhash.Hash

CalcMerkleRoot treats the provided slice of hashes as leaves of a merkle tree and returns the resulting merkle root.

A merkle tree is a tree in which every non-leaf node is the hash of its children nodes. A diagram depicting how this works for Decred transactions where h(x) is a blake256 hash follows: 

         root = h1234 = h(h12 + h34)
        /                           \
  h12 = h(h1 + h2)            h34 = h(h3 + h4)
   /            \              /            \
h1 = h(tx1)  h2 = h(tx2)    h3 = h(tx3)  h4 = h(tx4)

The number of inputs is not always a power of two which results in a balanced tree structure as above. In that case, parent nodes with no children are also zero and parent nodes with only a single left node are calculated by concatenating the left node with itself before hashing.

Example

This example demonstrates calculating a merkle root from a slice of leaf hashes. 

package main

import (
	"fmt"

	"github.com/decred/dcrd/blockchain/standalone"
	"github.com/decred/dcrd/chaincfg/chainhash"
)

func main() {
	// Create a slice of the leaf hashes.
	leaves := make([]chainhash.Hash, 3)
	for i := range leaves {
		// The hash would ordinarily be calculated from the TxHashFull function
		// on a transaction, however, it's left as a zero hash for the purposes
		// of this example.
		leaves[i] = chainhash.Hash{}
	}

	merkleRoot := standalone.CalcMerkleRoot(leaves)
	fmt.Printf("Result: %s", merkleRoot)

}

Output:

Result: 5fdfcaba377aefc1bfc4af5ef8e0c2a61656e10e8105c4db7656ae5d58f8b77f

func CalcMerkleRootInPlace 

func CalcMerkleRootInPlace(leaves []chainhash.Hash) chainhash.Hash

CalcMerkleRootInPlace is an in-place version of CalcMerkleRoot that reuses the backing array of the provided slice to perform the calculation thereby preventing extra allocations. It is the caller's responsibility to ensure it is safe to mutate the entries in the provided slice.

The function internally appends an additional entry in the case the number of provided leaves is odd, so the caller may wish to pre-allocate space for one additional element in the backing array in that case to ensure it doesn't need to be reallocated to expand it.

For example: 

allocLen := len(leaves) + len(leaves)&1
leaves := make([]chainhash.Hash, len(leaves), allocLen)
// populate the leaves

See CalcMerkleRoot for more details on how the merkle root is calculated.

func CalcTxTreeMerkleRoot 

func CalcTxTreeMerkleRoot(transactions []*wire.MsgTx) chainhash.Hash

CalcTxTreeMerkleRoot calculates and returns the merkle root for the provided transactions. The full (including witness data) hashes for the transactions are used as required for merkle roots.

See CalcMerkleRoot for more details on how the merkle root is calculated.

func CalcWork 

func CalcWork(bits uint32) *big.Int

CalcWork calculates a work value from difficulty bits. Decred increases the difficulty for generating a block by decreasing the value which the generated hash must be less than. This difficulty target is stored in each block header using a compact representation as described in the documentation for CompactToBig. The main chain is selected by choosing the chain that has the most proof of work (highest difficulty). Since a lower target difficulty value equates to higher actual difficulty, the work value which will be accumulated must be the inverse of the difficulty. Also, in order to avoid potential division by zero and really small floating point numbers, the result adds 1 to the denominator and multiplies the numerator by 2^256.

func CheckProofOfWork 

func CheckProofOfWork(blockHash *chainhash.Hash, difficultyBits uint32, powLimit *big.Int) error

CheckProofOfWork ensures the provided block hash is less than the provided compact target difficulty and that the target difficulty is in min/max range per the provided proof-of-work limit.

Example

This example demonstrates checking the proof of work of a block hash against a target difficulty. 

package main

import (
	"fmt"
	"math/big"

	"github.com/decred/dcrd/blockchain/standalone"
	"github.com/decred/dcrd/chaincfg/chainhash"
)

func main() {
	// This is the pow limit for mainnet and would ordinarily come from chaincfg
	// params, however, it is hard coded here for the purposes of the example.
	l := "00000000ffffffffffffffffffffffffffffffffffffffffffffffffffffffff"
	powLimit, success := new(big.Int).SetString(l, 16)
	if !success {
		fmt.Println("invalid pow limit")
		return
	}

	// Check the proof of work for block 1 in the main chain.
	h := "000000000000437482b6d47f82f374cde539440ddb108b0a76886f0d87d126b9"
	hash, err := chainhash.NewHashFromStr(h)
	if err != nil {
		fmt.Printf("failed to parse hash: %v\n", err)
		return
	}
	bits := uint32(453115903)

	if err := standalone.CheckProofOfWork(hash, bits, powLimit); err != nil {
		fmt.Printf("proof of work check failed: %v\n", err)
		return
	}

}

Output:

func CheckProofOfWorkRange 

func CheckProofOfWorkRange(difficultyBits uint32, powLimit *big.Int) error

CheckProofOfWorkRange ensures the provided compact target difficulty is in min/max range per the provided proof-of-work limit.

func CompactToBig 

func CompactToBig(compact uint32) *big.Int

CompactToBig converts a compact representation of a whole number N to an unsigned 32-bit number. The representation is similar to IEEE754 floating point numbers.

Like IEEE754 floating point, there are three basic components: the sign, the exponent, and the mantissa. They are broken out as follows:

  • the most significant 8 bits represent the unsigned base 256 exponent

  • bit 23 (the 24th bit) represents the sign bit

  • the least significant 23 bits represent the mantissa

    ------------------------------------------------- | Exponent | Sign | Mantissa | ------------------------------------------------- | 8 bits [31-24] | 1 bit [23] | 23 bits [22-00] | -------------------------------------------------

The formula to calculate N is: 

N = (-1^sign) * mantissa * 256^(exponent-3)

This compact form is only used in Decred to encode unsigned 256-bit numbers which represent difficulty targets, thus there really is not a need for a sign bit, but it is implemented here to stay consistent with legacy code.

Example

This example demonstrates how to convert the compact "bits" in a block header which represent the target difficulty to a big integer and display it using the typical hex notation. 

package main

import (
	"fmt"

	"github.com/decred/dcrd/blockchain/standalone"
)

func main() {
	// Convert the bits from block 1 in the main chain.
	bits := uint32(453115903)
	targetDifficulty := standalone.CompactToBig(bits)

	// Display it in hex.
	fmt.Printf("%064x\n", targetDifficulty.Bytes())

}

Output:

000000000001ffff000000000000000000000000000000000000000000000000

func GenerateInclusionProof added in v1.1.0 

func GenerateInclusionProof(leaves []chainhash.Hash, leafIndex uint32) []chainhash.Hash

GenerateInclusionProof treats the provided slice of hashes as leaves of a merkle tree and generates and returns a merkle tree inclusion proof for the given leaf index. The proof can be used to efficiently prove the leaf associated with given leaf index is a member of the tree.

A merkle tree inclusion proof consists of the ceil(log2(x)) intermediate sibling hashes along the path from the target leaf to prove through the root node. The sibling hashes, along with the original leaf hash (and its original leaf index), can be used to recalculate the merkle root which, in turn, can be verified against a known good merkle root in order to prove the leaf is actually a member of the tree at that position.

For example, consider the following merkle tree: 

       root = h1234 = h(h12 + h34)
      /                           \
h12 = h(h1 + h2)            h34 = h(h3 + h4)
 /            \              /            \
h1            h2            h3            h4

Further, consider the goal is to prove inclusion of h3 at the 0-based leaf index of 2. The proof will consist of the sibling hashes h4 and h12. On the other hand, if the goal were to prove inclusion of h2 at the 0-based leaf index of 1, the proof would consist of the sibling hashes h1 and h34.

Specifying a leaf index that is out of range will return nil.

func HashToBig 

func HashToBig(hash *chainhash.Hash) *big.Int

HashToBig converts a chainhash.Hash into a big.Int that can be used to perform math comparisons.

func IsCoinBaseTx 

func IsCoinBaseTx(tx *wire.MsgTx) bool

IsCoinBaseTx determines whether or not a transaction is a coinbase. A coinbase is a special transaction created by miners that has no inputs. This is represented in the block chain by a transaction with a single input that has a previous output transaction index set to the maximum value along with a zero hash.

func IsErrorCode 

func IsErrorCode(err error, c ErrorCode) bool

IsErrorCode returns whether or not the provided error is a rule error with the provided error code.

func VerifyInclusionProof added in v1.1.0 

func VerifyInclusionProof(root, leaf *chainhash.Hash, leafIndex uint32, proof []chainhash.Hash) bool

VerifyInclusionProof returns whether or not the given leaf hash, original leaf index, and inclusion proof result in recalculating a merkle root that matches the provided merkle root. See GenerateInclusionProof for details about the proof.

For example, consider a provided root hash denoted by "h1234o", a leaf hash to verify inclusion for denoted by "h2" with a leaf index of 2, and an inclusion proof consisting of hashes denoted by "h1o", and "h34o". The "o" here stands for original, as in the original hashes calculated while generating the proof.

These values would form the following merkle tree: 

       root = h1234 = h(h12 + h34o)
      /                           \
h12 = h(h1o + h2)                h34o
 /            \
h1o           h2

The verification will succeed if the root of the new partial merkle tree, "h1234", matches the provided root hash "h1234o".

Types

type ErrorCode 

type ErrorCode int

ErrorCode identifies a kind of error. 

const (
	// ErrUnexpectedDifficulty indicates specified bits do not align with
	// the expected value either because it doesn't match the calculated
	// value based on difficulty rules or it is out of the valid range.
	ErrUnexpectedDifficulty ErrorCode = iota

	// ErrHighHash indicates the block does not hash to a value which is
	// lower than the required target difficultly.
	ErrHighHash
)

These constants are used to identify a specific RuleError.

func (ErrorCode) String 

func (e ErrorCode) String() string

String returns the ErrorCode as a human-readable name.

type RuleError 

type RuleError struct {
	ErrorCode   ErrorCode // Describes the kind of error
	Description string    // Human readable description of the issue
}

RuleError identifies a rule violation. The caller can use type assertions to determine if a failure was specifically due to a rule violation and access the ErrorCode field to ascertain the specific reason for the rule violation.

func (RuleError) Error 

func (e RuleError) Error() string

Error satisfies the error interface and prints human-readable errors.

type SubsidyCache 

type SubsidyCache struct {
	// contains filtered or unexported fields
}

SubsidyCache provides efficient access to consensus-critical subsidy calculations for blocks and votes, including the max potential subsidy for given block heights, the proportional proof-of-work subsidy, the proportional proof of stake per-vote subsidy, and the proportional treasury subsidy.

It makes using of caching to avoid repeated calculations.

func NewSubsidyCache 

func NewSubsidyCache(params SubsidyParams) *SubsidyCache

NewSubsidyCache creates and initializes a new subsidy cache instance. See the SubsidyCache documentation for more details.

func (*SubsidyCache) CalcBlockSubsidy 

func (c *SubsidyCache) CalcBlockSubsidy(height int64) int64

CalcBlockSubsidy returns the max potential subsidy for a block at the provided height. This value is reduced over time based on the height and then split proportionally between PoW, PoS, and the Treasury.

Subsidy calculation for exponential reductions: 

subsidy := BaseSubsidyValue()
for i := 0; i < (height / SubsidyReductionIntervalBlocks()); i++ {
  subsidy *= SubsidyReductionMultiplier()
  subsidy /= SubsidyReductionDivisor()
}

This function is safe for concurrent access.

func (*SubsidyCache) CalcStakeVoteSubsidy 

func (c *SubsidyCache) CalcStakeVoteSubsidy(height int64) int64

CalcStakeVoteSubsidy returns the subsidy for a single stake vote for a block. It is calculated as a proportion of the total subsidy and max potential number of votes per block.

Unlike the Proof-of-Work and Treasury subsidies, the subsidy that votes receive is not reduced when a block contains less than the maximum number of votes. Consequently, this does not accept the number of votes. However, it is important to note that blocks that do not receive the minimum required number of votes for a block to be valid by consensus won't actually produce any vote subsidy either since they are invalid.

This function is safe for concurrent access.

func (*SubsidyCache) CalcTreasurySubsidy 

func (c *SubsidyCache) CalcTreasurySubsidy(height int64, voters uint16) int64

CalcTreasurySubsidy returns the subsidy required to go to the treasury for a block. It is calculated as a proportion of the total subsidy and further reduced proportionally depending on the number of votes once the height at which voting begins has been reached.

Note that passing a number of voters fewer than the minimum required for a block to be valid by consensus along with a height greater than or equal to the height at which voting begins will return zero.

This function is safe for concurrent access.

func (*SubsidyCache) CalcWorkSubsidy 

func (c *SubsidyCache) CalcWorkSubsidy(height int64, voters uint16) int64

CalcWorkSubsidy returns the proof of work subsidy for a block for a given number of votes. It is calculated as a proportion of the total subsidy and further reduced proportionally depending on the number of votes once the height at which voting begins has been reached.

Note that passing a number of voters fewer than the minimum required for a block to be valid by consensus along with a height greater than or equal to the height at which voting begins will return zero.

This function is safe for concurrent access.

type SubsidyParams 

type SubsidyParams interface {
	// BlockOneSubsidy returns the total subsidy of block height 1 for the
	// network.  This is separate since it encompasses the initial coin
	// distribution.
	BlockOneSubsidy() int64

	// BaseSubsidyValue returns the starting base max potential subsidy amount
	// for mined blocks.  This value is reduced over time and then split
	// proportionally between PoW, PoS, and the Treasury.  The reduction is
	// controlled by the SubsidyReductionInterval, SubsidyReductionMultiplier,
	// and SubsidyReductionDivisor parameters.
	//
	// NOTE: BaseSubsidy must be a max of 140,739,635,871,744 atoms or incorrect
	// results will occur due to int64 overflow.  This value comes from
	// MaxInt64/MaxUint16 = (2^63 - 1)/(2^16 - 1) = 2^47 + 2^31 + 2^15.
	BaseSubsidyValue() int64

	// SubsidyReductionMultiplier returns the multiplier to use when performing
	// the exponential subsidy reduction described by the CalcBlockSubsidy
	// documentation.
	SubsidyReductionMultiplier() int64

	// SubsidyReductionDivisor returns the divisor to use when performing the
	// exponential subsidy reduction described by the CalcBlockSubsidy
	// documentation.
	SubsidyReductionDivisor() int64

	// SubsidyReductionIntervalBlocks returns the reduction interval in number
	// of blocks.
	SubsidyReductionIntervalBlocks() int64

	// WorkSubsidyProportion returns the comparative proportion of the subsidy
	// generated for creating a block (PoW).
	//
	// The proportional split between PoW, PoS, and the Treasury is calculated
	// by treating each of the proportional parameters as a ratio to the sum of
	// the three proportional parameters: WorkSubsidyProportion,
	// StakeSubsidyProportion, and TreasurySubsidyProportion.
	//
	// For example:
	// WorkSubsidyProportion:     6 => 6 / (6+3+1) => 6/10 => 60%
	// StakeSubsidyProportion:    3 => 3 / (6+3+1) => 3/10 => 30%
	// TreasurySubsidyProportion: 1 => 1 / (6+3+1) => 1/10 => 10%
	WorkSubsidyProportion() uint16

	// StakeSubsidyProportion returns the comparative proportion of the subsidy
	// generated for casting stake votes (collectively, per block).  See the
	// documentation for WorkSubsidyProportion for more details on how the
	// parameter is used.
	StakeSubsidyProportion() uint16

	// TreasurySubsidyProportion returns the comparative proportion of the
	// subsidy allocated to the project treasury.  See the documentation for
	// WorkSubsidyProportion for more details on how the parameter is used.
	TreasurySubsidyProportion() uint16

	// StakeValidationBeginHeight returns the height at which votes become
	// required to extend a block.  This height is the first that will be voted
	// on, but will not include any votes itself.
	StakeValidationBeginHeight() int64

	// VotesPerBlock returns the maximum number of votes a block must contain to
	// receive full subsidy once voting begins at StakeValidationBeginHeight.
	VotesPerBlock() uint16
}

SubsidyParams defines an interface that is used to provide the parameters required when calculating block and vote subsidies. These values are typically well-defined and unique per network.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.