primitives

package
v1.9.3 Latest Latest
Warning

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

 Go to latest Published: Jun 19, 2024 License: ISC Imports: 5 Imported by: 0

README

primitives

Build Status ISC License Doc

Package and Module Status

This package is currently a work in progress in the context of a larger refactor and thus does not yet provide most of the things that are ultimately planned. See https://github.com/decred/dcrd/issues/2786 for further details.

The intention is to create a containing primitives module that will be kept at an experimental module version ("v0") until everything is stabilized to avoid major module version churn in the mean time.

Overview

This package ultimately aims to provide core data structures and functions for working with several aspects of Decred consensus.

The provided functions fall into the following categories:

  • Proof-of-work
    • Converting to and from the target difficulty bits representation
    • Calculating work values based on the target difficulty bits
    • Checking that a block hash satisfies a target difficulty and that the target difficulty is within a valid range
  • Merkle root calculation
    • Calculation from individual leaf hashes
  • Inclusion proofs
    • Generating Merkle tree inclusion proofs
    • Verifying Merkle tree inclusion proofs
  • 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

Maintainer Note

Since the primitives module is heavily relied upon by consensus code, there are some important aspects that must be kept in mind when working on this code:

  • It must provide correctness guarantees and full test coverage
  • Be extremely careful when making any changes to avoid breaking consensus
    • This often means existing code can't be changed without adding an internal flag to control behavior and introducing a new method with the new behavior
  • Minimize the number of allocations as much as possible
  • Opt for data structures that improve cache locality
  • Keep a strong focus on providing efficient code
  • Avoid external dependencies
    • Consensus code requires much stronger guarantees than typical code and consequently code that is not specifically designed with such rigid constraints will almost always eventually break things in subtle ways over time
  • Do not change the API in a way that requires a new major semantic version
    • This is not entirely prohibited, but major module version bumps have severe ramifications on every consumer, and thus they should be an absolute last resort
  • Take care when adding new methods to avoid method signatures that would require a major version bump due to a new major dependency version

Installation and Updating

This package is internal and therefore is neither directly installed nor needs to be manually updated.

License

Package primitives is licensed under the copyfree ISC License.

Documentation

Index

Constants

View Source 
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 = ErrorKind("ErrUnexpectedDifficulty")

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

These constants are used to identify a specific RuleError.

Variables

This section is empty.

Functions

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.

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 CalcWork 

func CalcWork(diffBits uint32) uint256.Uint256

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 DiffBitsToUint256. 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. For legacy reasons, the result is zero when the difficulty is zero. Finally, to avoid really small floating point numbers, the result multiplies the numerator by 2^256 and adds 1 to the denominator.

func CheckProofOfWork 

func CheckProofOfWork(powHash *chainhash.Hash, diffBits uint32, powLimit *uint256.Uint256) error

CheckProofOfWork ensures the provided hash is less than the target difficulty represented by given header bits and that said difficulty is in min/max range per the provided proof-of-work limit.

func CheckProofOfWorkRange 

func CheckProofOfWorkRange(diffBits uint32, powLimit *uint256.Uint256) error

CheckProofOfWorkRange ensures the provided target difficulty represented by the given header bits is in min/max range per the provided proof-of-work limit.

func DiffBitsToUint256 

func DiffBitsToUint256(bits uint32) (n uint256.Uint256, isNegative bool, overflows bool)

DiffBitsToUint256 converts the compact representation used to encode difficulty targets to an unsigned 256-bit integer. 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:

  1. the most significant 8 bits represent the unsigned base 256 exponent
  2. zero-based bit 23 (the 24th bit) represents the sign bit
  3. the least significant 23 bits represent the mantissa

Diagram: 

-------------------------------------------------
|   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)

Note that this encoding is capable of representing negative numbers as well as numbers much larger than the maximum value of an unsigned 256-bit integer. However, it is only used in Decred to encode unsigned 256-bit integers which represent difficulty targets, so rather than using a much less efficient arbitrary precision big integer, this implementation uses an unsigned 256-bit integer and returns flags to indicate whether or not the encoding was for a negative value and/or overflows a uint256 to enable proper error detection and stay consistent with legacy code.

func GenerateInclusionProof 

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 a 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 HashToUint256 

func HashToUint256(hash *chainhash.Hash) uint256.Uint256

HashToUint256 converts the provided hash to an unsigned 256-bit integer that can be used to perform math comparisons.

func Uint256ToDiffBits 

func Uint256ToDiffBits(n *uint256.Uint256) uint32

Uint256ToDiffBits converts a uint256 to a compact representation using an unsigned 32-bit integer. 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 DiffBitsToUint256 for details.

func VerifyInclusionProof 

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 ErrorKind 

type ErrorKind string

ErrorKind identifies a kind of error. It has full support for errors.Is and errors.As, so the caller can directly check against an error kind when determining the reason for an error.

func (ErrorKind) Error 

func (e ErrorKind) Error() string

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

type RuleError 

type RuleError struct {
	Description string
	Err         error
}

RuleError identifies a rule violation. It has full support for errors.Is and errors.As, so the caller can ascertain the specific reason for the error by checking the underlying error.

func (RuleError) Error 

func (e RuleError) Error() string

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

func (RuleError) Unwrap 

func (e RuleError) Unwrap() error

Unwrap returns the underlying wrapped error.

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 use 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, useDCP0010 bool) int64

CalcStakeVoteSubsidy returns the subsidy for a single stake vote for a block using either the original subsidy split that was in effect at Decred launch or the modified subsidy split defined in DCP0010 according to the provided flag.

It is calculated as a proportion of the total subsidy and max potential number of votes per block.

Unlike the Proof-of-Work subsidy, 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, useDCP0006 bool) 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.

When the treasury agenda is active the subsidy rule changes from paying out a proportion based on the number of votes to always pay the full subsidy.

This function is safe for concurrent access.

func (*SubsidyCache) CalcWorkSubsidy 

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

CalcWorkSubsidy returns the proof of work subsidy for a block for a given number of votes using either the original subsidy split that was in effect at Decred launch or the modified subsidy split defined in DCP0010 according to the provided flag.

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: This 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

	// 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.