Decred’s Proof-of-Stake (PoS) system makes use of a pseudorandom lottery to select five tickets from the live ticket pool to vote on the validity of each mined block. This page describes the algorithm used to select tickets.
The Proof-of-Stake Overview page provides a higher level overview of the ticket voting process.
Pseudorandom Number Generation
In order to calculate which tickets are eligible to vote on a given block, full nodes utilize a deterministic Pseudorandom Number Generator (PRNG).
Values generated by PRNGs are not truly random because they are completely determined by an intial seed value. This is a desirable property in the context of blockchains because it allows for the randomness to be reproduced and verified by multiple parties without them having to trust one another.
The PRNG used by dcrd to select tickets is named
Hash256PRNG. It utilizes
BLAKE-256 (a 256-bit
secure hashing function) to generate unsigned 32 bit integers between zero and a
specified upper limit, avoiding modulo bias in order to yield a normal
distribution within the specified range.
When a Decred full node is validating a mined block (height N), it will calculate the set of tickets which are eligible to vote on the validity of that block. When the next block is mined (height N+1), it will use that pre-calculated list to ensure that the votes included in block N+1 are from the correct tickets.
Below are the steps taken by a full node to determine the set of tickets eligible to vote on the validity of block N. Before these steps take place, the live ticket pool is stored in an ordered data structure. Each live ticket is hashed using BLAKE-256, and sorted lexicographically by their hash to generate a total order.
Concatenate the hash of the header of block N with a constant value which is known to all full nodes. This constant is derived from the hex representation of the mathematical constant Pi (𝜋), and acts as a publicly verifiable Nothing-Up-My-Sleeve number.
Hash the result from step 1 with BLAKE-256, and use this hash as the seed value to initialize an instance of
Hash256PRNGinstance to generate five random integers, using the size of the live ticket pool as an upper bound.
Use the five integers as indices to select tickets from the ordered list. These are the five tickets eligible to vote in the next block.
Due to the fact that this entire process is deterministic, each full node in the network is able to independently calculate the same set of five tickets, giving nodes a trustless method of validating that miners are including the correct votes on their mined blocks.