New Stake Difficulty Algorithm

This specifies a proposed replacement algorithm for determining the stake difficulty (commonly called the ticket price).

Motivation

The current stake difficulty algorithm satisfies the dead minimum requirement of maintaining a relatively stable ticket pool size which is important since the ticket pool size growing too large or too small can substantially alter the social contract between stakeholders and the network, disrupting the predictable nature of average time to vote a ticket, percentage of tickets that expire, and, consequently, the expected rate of return.

However, the current algorithm also exhibits several shortcomings. Most notably, it allows the prices to swing too wildly which encourages all tickets to be purchased during a single interval when the price is artificially low, followed by discouraging any purchases at all for several intervals due to the price becoming artificially high. In short, very limited price exploration occurs which leads to several undesirable outcomes and behaviors such as a poor user experience due to intense fee competition during the single interval where tickets can reasonably be purchased and huge swings in mining hash power since miners direct large amounts of hash power at the network during the high fee interval and remove it after the interval is over.

This proposal resolves all of these issues by replacing the stake difficulty algorithm completely with a new algorithm that adheres to the following requirements and goals of an ideal stake difficulty algorithm:

• The pool size must remain fairly stable around the target pool size since sizes that are too large or too small would substantially alter the social contract between stakeholders and the network, disrupting the predictable nature of average time to vote a ticket, percentage of tickets that expire, and the rate of return. This is by far the most important requirement.
• The stake difficulty must not fall into a resonant pattern that only encourages ticket purchases during a single interval.
• The stake difficulty must adjust quickly enough to encourage or discourage the desired purchasing behavior necessary to maintain pool size stability and should ideally adjust smoothly when the system is running at or near equilibrium to encourage good price exploration and discourage fee wars.
• The algorithm must be able to absorb sudden surges and ebbs in demand and staking proportions and recover back to expected steady state behavior.
• The algorithm must not be overfitted to a specific demand distribution function (DDF) or the specific mainnet parameters since it will be used on the testnet and simnet networks and the parameters of mainnet could change in a future hard fork vote.
• The algorithm must be reasonably efficient to compute.
• The algorithm should ideally be simple to understand and implement.

Specification

Integer Math

In order to facilitate better compatibility across implementations and languages, the formulas defined by the specification make use of integer math instead of floating point math as denoted by use of the floor function. This is highly desirable for consensus code since floating point math can be problematic across languages due to issues such as rounding errors and uncertainty in their respective libraries.

Supply Estimation Formulas

The actual total coin supply as of a given block height depends on many factors such as the number of votes included in every prior block and whether or not any of the prior blocks have been invalidated by stakeholders.

In order to avoid this complexity, the proposed algorithm instead makes use of an estimate of the total coin supply as a function of a given block height as follows:

Explanation of terms:

C_{est} = Estimated total coin supply for a given height
h = The height for which the coin supply is to be estimated
P = The coins generated by the first block (1,680,000 X 10⁸ on mainnet)
I = The number of blocks in the subsidy reduction interval (6144 on mainnet)
c_{0} = The base coin subsidy before any reductions (3,119,582,664 on mainnet)
R_{m} = The coin subsidy reduction multiplier (100 on mainnet)
R_{d} = The coin subsidy reduction divisor (101 on mainnet)

Stake Difficulty Formulas

The stake difficulty is calculated at each stake difficulty retarget interval and remains the same throughout the entire interval.

S_{N} = Stake difficulty of the current interval
S_{N-1} = Stake difficulty of the previous interval
P_{N} = Current pool size including immature tickets
P_{N-1} = Previous interval’s pool size including immature tickets
T = Target pool size to maintain including ticket maturity period (42,240 on mainnet)
C_{est} = Estimated total current coin supply
B = Number of blocks with max votes needed to exhaust target pool size (8,192 on mainnet)

Rationale

Theory of Operation

The general idea of the proposed algorithm is rooted in the concept of forces that react to and drive changes to the pool size. The first force acts to counteract the relative change in the pool size, while the second force acts as a restorative force to push the pool size towards the target value. There are minimum and maximum bounds imposed to prevent runaway behavior.

Generalized Algorithm Formula

The following is the general form of the proposed stake difficulty algorithm:

Explanation of terms:

S_{N} = Stake difficulty of the current interval
S_{N-1} = Stake difficulty of the previous interval
F_{c} = Force to counteract relative change in pool size
F_{r} = Restorative force to push the pool size towards target
S_{lb} = Lower bound of final computed stake difficulty
S_{ub} = Upper bound of final computed stake difficulty

Specialized Algorithm Formulas

The following specializes the general form of the algorithm by defining the forces and bounds:

Explanation of terms:

P_{N} = Current pool size including immature tickets
P_{N-1} = Previous interval’s pool size including immature tickets
T = Target pool size to maintain including ticket maturity period (42,240 on mainnet)
S_{lb} = Lower bound of final computed stake difficulty
S_{ub} = Upper bound of final computed stake difficulty
C_{est} = Estimated total current coin supply
B = Number of blocks with max votes needed to exhaust target pool size (8,192 on mainnet)

Simplified Integer Formula

Finally, the following rearranges and simplifies the formula to use integer math which, as mentioned in the specification, is highly desirable for consensus code since floating point math can be problematic across languages due to issues such as rounding errors and uncertainty in their respective libraries. The is the final form used in the specification:

Explanation of terms:

S_{N} = Stake difficulty of the current interval
S_{N-1} = Stake difficulty of the previous interval
P_{N} = Current pool size including immature tickets
P_{N-1} = Previous interval’s pool size including immature tickets
T = Target pool size to maintain including ticket maturity period (42,240 on mainnet)
C_{est} = Estimated total current coin supply
B = Number of blocks with max votes needed to exhaust target pool size (8,192 on mainnet)

Simulation Results

Simulator Notes

Before showing the results, it is worth noting that dcrstakesim, the software used to perform these simulations, intentionally aims for several worst case scenarios in order to help ensure the algorithm behaves well under extreme conditions and attack scenarios:

• All coins are managed as a single entity to simulate multiple stakeholders conspiring to manipulate the price. In real world usage scenarios, the coins are distributed among different parties who act in their own best interest which is more stable than the simulated behavior.
• The simulator provides much larger surges and ebbs in demand and staking proportions as compared with likely real world staking. More concretely, it instantly surges the amount of staked coins by a full 20% of the entire supply while simultaneously doubling the demand and then drops them by the same. This surge and ebb is signified by the section highlited in yellow.
• One of the demand distribution functions (DDF B) solely chases nominal estimated yield which is quite irrational in that it completely ignores things like opportunity cost, the volume-weighted average price, and the fact that the actual expected yield is lower when the pool size is larger. The vast majority of real-world stakers generally make much more rational decisions.

Graphs

The simulator was used to test 7 different public proposals and several more private ones. This github issue contains the detailed results of simulations run on all public proposals. For brevity, only the results for two of the demand distribution functions against the current algorithm and the proposed algorithm are provided here.

Current Algorithm
As a point of comparison, the following graphs show the simulation run using two different demand distribution functions with the current algorithm this proposal replaces. It can be seen how the simulation closely mirrors the actual behavior on mainnet with DDF A:

Proposed Algorithm
The following graphs show the simulations run using two different demand distribution functions with the proposed algorithm out through block 500,000:

Analysis

Strengths and Weaknesses
Strengths:

• Both the pool size and ticket price are quite stable
• The algorithm itself is easy to understand and can be efficiently computed
• The algorithm handles the initial bringup period well with realistic and rational staking behavior
• The algorithm behaves nicely under extreme surge conditions
• The algorithm handles steady state properly
• The algorithm recovers well from sudden shocks to the system

Weaknesses:

• The initial bringup period with the more irrational staking behavior (DDF B) allows the pool size to surge to roughly 70k

Summary
This proposal satisfies all of the hard requirements for a stake difficulty algorithm and manages to achieve the ideal goals as well. For example, the mathematical form of the algorithm is simple and its theory of operation is easy to understand. The algorithm also lends itself well to implementation in multiple programming languages.

After running over 300 different simulations with this algorithm and manually tweaking the DDFs to intentionally throw various forms of irrational and attack-like behavior at it, the only notable weakness found is that under unrealistically extreme conditions the pool size can spike up higher than would be ideal, however, that is mitigated by the fact it fairly quickly self corrects and returns to the desired target pool size versus experiencing the runaway behavior of nearly all other algorithms tested, including the existing algorithm on mainnet, under those same circumstances.

Deployment

This agenda will be deployed using the standard Decred on-chain voting infrastructure as follows:

Compatibility

This is a hard-forking change to the Decred consensus. This means that once the agenda is voted in and becomes locked in, anybody running code that fully validates blocks must upgrade before the activation time or they will risk rejecting a chain containing a stake difficulty that does not match the value calculated by the new algorithm.

Other software, such as statistics dashboards, will need to either make use of the estimatestakediff RPC or update their estimation code according to the specification herein.

Reference Implementation

Supply Estimation

// estimateSupply returns an estimate of the coin supply for the provided block
// height.  This is primarily used in the stake difficulty algorithm and relies
// on an estimate to simplify the necessary calculations.  The actual total
// coin supply as of a given block height depends on many factors such as the
// number of votes included in every prior block (not including all votes
// reduces the subsidy) and whether or not any of the prior blocks have been
// invalidated by stakeholders thereby removing the PoW subsidy for them.
func estimateSupply(height int64) int64 {
	// These parameters are ordinarily unique per chain and thus should be
	// passed into the function via a chain parameters structure, however,
	// they are defined as constants with the mainnet parameters here for the
	// purposes of providing a self-contained function for the DCP.
	const (
		mainnetBlockOneSubsidy = 1680000 * 100000000
		mainnetSubsidyReductionInterval = 6144
		mainnetBaseSubsidy = 3119582664
		mainnetSubsidyReductionMultiplier = 100
		mainnetSubsidyReductionDivisor = 101
	)

	// No subsidy for genesis block or prior.
	if height <= 0 {
		return 0
	}

	// Estimate the supply by calculating the full block subsidy for each
	// reduction interval and multiplying it the number of blocks in the
	// interval then adding the subsidy produced by number of blocks in the
	// current interval.
	supply := int64(mainnetBlockOneSubsidy)
	reductions := int64(height) / mainnetSubsidyReductionInterval
	subsidy := int64(mainnetBaseSubsidy)
	for i := int64(0); i < reductions; i++ {
		supply += mainnetSubsidyReductionInterval * subsidy

		subsidy *= mainnetSubsidyReductionMultiplier
		subsidy /= mainnetSubsidyReductionDivisor
	}
	supply += (1 + int64(height)%mainnetSubsidyReductionInterval) * subsidy

	// Blocks 0 and 1 have special subsidy amounts that have already been
	// added above, so remove what their subsidies would have normally been
	// which were also added above.
	supply -= mainnetBaseSubsidy * 2
	return supply
}

Stake Diffulculty Calculation

// calcNextStakeDiff calculates the next stake difficulty for the given set
// of parameters using the algorithm defined in this document.
//
// This function contains the heart of the algorithm and thus is separated for
// use in both the actual stake difficulty calculation as well as estimation.
//
// The caller must perform all of the necessary chain traversal in order to
// get the current difficulty, previous retarget interval's pool size plus
// its immature tickets, as well as the current pool size plus immature tickets.
func calcNextStakeDiff(nextHeight, curDiff, prevPoolSizeAll, curPoolSizeAll int64) int64 {
	// These parameters are ordinarily unique per chain and thus should be
	// passed into the function via a chain parameters structure, however,
	// they are defined as constants with the mainnet parameters here for the
	// purposes of providing a self-contained function for the DCP.
	const (
		votesPerBlock          = 5
		ticketPoolSize         = 8192
		ticketMaturity         = 256
		targetPoolSizeAll      = votesPerBlock * (ticketPoolSize + ticketMaturity)
		minimumStakeDifficulty = 200000000
	)

	// Calculate the difficulty according to the formula defined in this
	// document.
	curPoolSizeAllBig := big.NewInt(curPoolSizeAll)
	nextDiffBig := big.NewInt(curDiff)
	nextDiffBig.Mul(nextDiffBig, curPoolSizeAllBig)
	nextDiffBig.Mul(nextDiffBig, curPoolSizeAllBig)
	nextDiffBig.Div(nextDiffBig, big.NewInt(prevPoolSizeAll))
	nextDiffBig.Div(nextDiffBig, big.NewInt(targetPoolSizeAll))

	// Limit the new stake difficulty between the minimum allowed stake
	// difficulty and a maximum value that is relative to the total supply.
	nextDiff := nextDiffBig.Int64()
	estimatedSupply := estimateSupply(nextHeight)
	maximumStakeDiff := estimatedSupply / ticketPoolSize
	if nextDiff > maximumStakeDiff {
		nextDiff = maximumStakeDiff
	}
	if nextDiff < minimumStakeDifficulty {
		nextDiff = minimumStakeDifficulty
	}
	return nextDiff
}

Pull Request

A reference implementation is provided by this pull request:

Test Vectors

The following test vectors are provided in order to facilitate testing across implementations. These are the expected values for mainnet.

Supply Estimation

Stake Difficulty

Acknowledgements

The algorithm in this proposal is based upon the collaborative work of many individuals all of whom either proposed potential new algorithms or otherwise provided feedback (alphabetical order):

• @animedow
• Edson Brusque (@edsonbrusque)
• Jonathan Chappelow (@chappjc)
• Dave Collins (@davecgh)
• Charlie Lee (@coblee)
• @raedah
• Julian Y (@jyap808)
• Jake Yocom-Piatt (@behindtext)

A special thanks to @raedah, @behindtext, and @davecgh for submitting the proposal that was ultimately selected, however, as mentioned above, the final algorithm would not have been possible without the collaborative effort of everyone involved.

Thanks to the following individuals who provided valuable feedback during the review process of this proposal:

• Jonathan Zeppettini
• @kandiru
• John C. Vernaleo (@jcvernaleo)

See the github issue for detailed results of simulations run on all public proposals.

Copyright

This document is licensed under the CC0–1.0: Creative Commons CC0 1.0 Universal license.

The code is licensed under the ISC License.

Originally published at github.com/decred/dcps on May 4, 2017.