Permalink
Find file Copy path
1fbf5bc Jul 11, 2017
1 contributor

Users who have contributed to this file

589 lines (494 sloc) 22.6 KB

DCP: 0001
Title: New Stake Difficulty Algorithm
Author: Dave Collins <davec@decred.org>
Status: Active
Created: 2017-05-04
License: CC0-1.0
License-Code: ISC

Table of Contents

Abstract

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:

Cest = 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 108 on mainnet)
I = The number of blocks in the subsidy reduction interval (6144 on mainnet)
c0 = The base coin subsidy before any reductions (3,119,582,664 on mainnet)
Rm = The coin subsidy reduction multiplier (100 on mainnet)
Rd = 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.

Explanation of terms:

SN = Stake difficulty of the current interval
SN-1 = Stake difficulty of the previous interval
PN = Current pool size including immature tickets
PN-1 = Previous interval's pool size including immature tickets
T = Target pool size to maintain including ticket maturity period (42,240 on mainnet)
Cest = 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:

SN = Stake difficulty of the current interval
SN-1 = Stake difficulty of the previous interval
Fc = Force to counteract relative change in pool size
Fr = Restorative force to push the pool size towards target
Slb = Lower bound of final computed stake difficulty
Sub = 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:

PN = Current pool size including immature tickets
PN-1 = Previous interval's pool size including immature tickets
T = Target pool size to maintain including ticket maturity period (42,240 on mainnet)
Slb = Lower bound of final computed stake difficulty
Sub = Upper bound of final computed stake difficulty
Cest = 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:

SN = Stake difficulty of the current interval
SN-1 = Stake difficulty of the previous interval
PN = Current pool size including immature tickets
PN-1 = Previous interval's pool size including immature tickets
T = Target pool size to maintain including ticket maturity period (42,240 on mainnet)
Cest = 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:

Name Setting
Deployment Version 4
Agenda ID sdiffalgorithm
Agenda Description Change stake difficulty algorithm as defined in DCP0001
Start Time 1493164800 (Apr 26th, 2017 00:00:00 +0000 UTC)
Expire Time 1524700800 (Apr 26th, 2018 00:00:00 +0000 UTC)
Mask 0x06 (Bits 1 and 2)
Choices
Choice English Description Bits
abstain abstain voting for change 0x00
no keep the existing algorithm 0x02 (Bit 1)
yes change to the new algorithm 0x04 (Bit 2)

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

Height Estimated Supply (in atoms)
-1 0
0 0
1 168000000000000
2 168003119582664
3 168006239165328
6143 187160476722288
6144 187163565417994
6145 187166654113700
12287 206137423139952
12288 206140481254512
12289 206143539369072
116735 501461431196784
116736 501464013399865
116737 501466595602946
442367 1158182625545328
442368 1158184149449220
442369 1158185673353112
2457599 2067664381463664
2457600 2067664439747298
2457601 2067664498030932
11010045 2103831507356782
11010046 2103831507356783
11010047 2103831507356784
11010048 2103831507356784
11010049 2103831507356784

Stake Difficulty

Next Height Current (in atoms) Previous Pool Size Current Pool Size Expected (in atoms)
0 200000000 0 0 200000000
144 200000000 0 0 200000000
288 200000000 0 620 200000000
432 200000000 620 2060 200000000
432 200000000 620 3500 200000000
576 200000000 2060 4930 200000000
720 200000000 4930 6360 200000000
864 200000000 6360 9250 200000000
1008 200000000 9250 10680 200000000
1152 200000000 10680 13570 200000000
1296 200000000 13570 15000 200000000
1440 200000000 15000 17890 200000000
1584 200000000 17890 19320 200000000
1728 200000000 19320 22210 200000000
1872 200000000 22210 23640 200000000
2016 200000000 23640 26530 200000000
2160 200000000 26530 27960 200000000
2304 200000000 27960 30850 200000000
2304 200000000 38040 40920 208418769
2448 200000000 30850 32280 200000000
2448 208418769 40920 43800 231326567
2592 200000000 32280 35170 200000000
2592 231326567 43800 46680 272451490
2736 200000000 35170 36600 200000000
2736 272451490 46680 49560 339388424
2880 200000000 36600 39490 201743368
2880 339388424 49560 52440 445827839
3024 201743368 39490 40776 201093236
3024 445827839 52440 55320 615949254
3168 201093236 40776 43667 222625877
3168 615949254 55320 58200 892862990
3312 222625877 43667 44808 242331291
3312 892862990 58200 61080 1354989669
3456 242331291 44808 47700 291317641
3456 1354989669 61080 63960 2148473276
3600 2148473276 63960 66840 3552797658
3744 3552797658 66840 69720 6116808441
3888 6116808441 69720 71592 10645659768
3888 6116808441 69720 72600 10947547379
4032 10645659768 71592 71599 18046712136
4032 10947547379 72600 75480 20338554623
4176 200000000 37740 38785 200000000
4176 18046712136 71599 71217 22097687698
4176 20338554623 75480 77965 22097687698
4320 22097687698 71217 70497 22152524112
4464 22152524112 70497 69777 22207360526

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

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:

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.