RECENT CHANGES:
- (2015-02-06) Change incentive structure to a temporary chain work penalty.
Title: Double-Spend Deprecation Window Author: Tom Harding Published: 2014-10-27
Any needed rules and incentives can be enforced with this consensus mechanism.[0]
--Satoshi Nakamoto, bitcoin.pdf, final sentence
... the block chain with this block would have lower cumulative difficulty than without it[1]
--Hal Finney, regarding a consensus rule to shorten unconfirmed double-spend risk
Abstract
This proposal aims to bring meaningful and quantifiable, though incremental, reliability to unconfirmed transactions. The method proposed is to identify double-spend transactions with a predictably small margin of error, and to prefer blockchain branches that do not contain them.
No permanent soft or hard blockchain fork is required to adopt this proposal. Once adopted by a certain minority of hash power, a meaningful economic incentive develops for remaining miners to adopt it as well. This incentive increases with increasing adoption.
Node deprecates a transaction tx2 that double-spends a coin already spent in another unconfirmed transaction tx1, when node received tx1 recently, but not too recently: the time gap between tx1 and tx2, as witnessed locally by node, falls into a specified deprecation window.
Node expresses its deprecation as it searches for the best chain by assigning, for a specified time, no more than zero work to a block containing a deprecated double-spend. By so doing, nodes collectively create a disincentive for miners to include these double-spends. Since they do not consider the block invalid, this action does not create a permanent fork risk. Just as important, this action does not tamper with the proof of work required for validity.
A specific rule is considered that defines the double-spend deprecation window to be (T = 30 seconds, Tmax = 2 hours). Once adopted, this rule is predicted to change transaction inclusion patterns such that, if transmitted more than 30 seconds after tx1, tx2 will not be confirmed before 2 hours after tx1 was transmitted, thereby giving tx1 that amount of time to be confirmed first.
Motivation
Address a major usability weakness: the long (10-minute) and highly variable time before a transaction gains any reliability by being included in a block.
Establish a strong economic incentive for miners not to include deprecated respend transactions, which could be attempts to defraud intended recipients of payment, especially those who deliver value within seconds, and have little recourse if those payments fail.
The specific rule considered, if fully adopted, would generally eradicate successful double-spends aged between 30 seconds and 2 hours, as well as successful Finney attacks where the block is mined more than 30 seconds and less than 2 hours after the appearance of tx1.
Specification
Node tracks receipt time of double-spend transactions not accepted, and relays those transactions. Suitable anti-DoS provisions have been developed to enable this (primarily, by only tracking the first respend event for a coin)[3].
Node inspects each valid block B for respend transactions tx2, where it knows of a transaction tx1 that is valid, unconfirmed, seen earlier than tx2, and spends a tx2 input coin.
Definitions
Four policy parameters characterize this specification:
Table 1, Parameters
| Parameter | Inter-Parameter Relationship |
Name | Specific Policy Considered |
|---|---|---|---|
| T | deprecated respend gap | 30 seconds | |
| Tfull | T <= Tfull | full-penalty respend gap | 40 seconds |
| Tmax | Tfull < Tmax | block penalty duration | 2 hours |
| M | transaction maturation duration | 30 seconds |
Define a function node_time_received(tx):
Node's local clock time when data matching the tx hash is first received. This may be as part of a block. An orphan transaction is treated as having been received when accepted. If not otherwise defined, +infinity.
For the found pairs (tx1 tx2), node defines the following calculated quantities, using its own clock:
Table 2, Calculated quantities
| Calculated quantity | Name | Formula |
|---|---|---|
| t | transaction respend gap | node_time_received(tx2) - node_time_received(tx1) |
| tB | block respend gap | max(t) |
| penalty_expirationB | block penalty expiration time | max(node_time_received(tx1)) + Tmax |
Double-Spend Deprecation Rule
Followed by: Full nodes, including miners
if (T < tB < Tfull) //lesser penalty
ChainWorkB = 0;
else
if(Tfull <= tB < Tmax) //full penalty
ChainWorkB = -1;
if(defined(ChainWorkB) && TargetB+1 > TargetB) //upward retarget coming, neutralize
ChainWorkB += TargetB - TargetB+1;
A value assigned to ChainWorkB under this rule replaces the usual nChainWork value assigned to B, and is used to find the "most-work" chain. The usual value is the difficulty Target, which itself is always unchanged by this proposal.
A value assigned to ChainWorkB under this rule expires at penalty_expirationB. The active chain is re-evaluated when this occurs.
Transaction Maturation Rule
Followed by: Miners
if (min(node_time_received(tx2), now) - node_time_received(tx1) < M)
do not include tx1 in block;
Startup
Unless node pre-loads its transaction memory pool from a live trusted source, it will not be able to immediately apply the above rules on startup. It first needs to witness new transactions for an interval equal to Tmax (2 hours, in the specfic rule considered).
Node should not relay or mine blocks until it has a mempool that is complete over time Tmax, because it may not have received transactions that would have caused it to assign zero incremental work to, or not produce, those blocks.
Clean-up processes
Node must periodically clean up cached double-spends older than Tmax.
Illustration
By assigning zero incremental work to a block B, node evaluates the chain of which it is the tip as less attractive than that of its parent, which arrived earlier. It does not activate B. In particular, if node is mining, it does not build on B. Node will accept either a sibling or a child of B that is received from the network.
Figure 1, Block Deprecated with Lesser Penalty
In the case of a fully penalized block, assigning negative incremental work causes node to evaluate a child of B as less attractive than an unpenalized sibling of B. Therefore, miners conclude that producing a block B containing a fully penalized double-spend will cause nodes that adopt this proposal not to build on their work.
Figure 2, Block Deprecated with Full Penalty
When T < tB < Tfull, the lesser penalty minimizes the effect of an attack by hash power seeking to maximize disagreement on whether B is penalized, by targeting tB = T. Setting incremental work no lower than zero in this case renders this attack no more effective than a long-existing and easier to implement future-timestamp attack (see Fragmentation attack by hash power, below).
Compatibility
This proposal does not change block validity criteria. Specifically, it does not change required proof of work, nor the retargeting process, which references the proof-of-work target and not accumulated chain work. Node continues to require every block to have valid proof of work but, for blocks containing deprecated respends, this work is not immediately considered when searching for the best chain.
If this proposal is implemented and adopted by a significant minority of hash power, a fork-off risk will develop to blocks that contain deprecated double-spends, produced by miners who have not adopted. These dynamics would need to be antipated and planned for through broad communications channels. It is in the interest of adopting miners to do so.
Example
Consider that the concrete double-spend deprecation rule defined in the last column of Table 1 has been fully adopted by the network.
Assume further that
Transaction propagation to nodes is lognormally distributed with the recent empirical median of 1 second[2] and fitted sigma
Figure 3, Transaction Propagation Time Density
Transaction tx1 and double-spend tx2 originate at the same node
- tx2 is the only double-spend available for inclusion
- tx2 offers .03 BTC additional fee over tx1
- Block subsidy = 25 BTC
Three scenarios are considered. The originating node transmits tx1, waits for a transmission gap G, depending on scenario, then transmits the double-spend tx2. Consider the cost and benefit of a miner decision to include tx2 in his block. Summarizing the results:
Table 3, Cost vs. Benefit of Including tx2
| Scenario | Transmission Gap G |
% Receiving tx1 First |
% Respend Gap t > 30s |
Cost BTC | Benefit BTC | Miner Decision |
|---|---|---|---|---|---|---|
| 1 | 0s | 50% | 0% | 0.0000 | .03 | |
| 2 | 30s | 100% | 50% | >6.2500 | .03 | exclude tx2 |
| 3 | 60s | 100% | 100% | >25.0000 | .03 | exclude tx2 |
Scenario 1
tx2 is transmitted immediately after tx1.
Results:
- 50% of nodes receive tx2 after tx1.
- 0% of nodes receive tx2 more than 30 seconds after tx1.
The measured respend gap t is a random variable which has the distribution of the difference of two identically-distributed lognormal propagation times. In this scenario, the difference is virtually certain never to exceed 30 seconds.
Miner might include either transaction, and 100% of the network will accept it. The benefit of including tx2 is .03.
Any nodes that somehow see a respend gap of > 30 seconds, despite the transactions having been transmitted simultaneously, penalize the block. When the first child block arrives, they change their mind, and both blocks are connected (unless these few nodes have already produced a longer chain, which is fine, but exceedingly unlikely). This is << 1% of nodes. An even smaller theoretical subset might have measured a respend gap > 40s. Any such nodes would need to see 2 subsequent blocks to overcome negative chain work and connect the sequence.
0% and 100% figures in the example section are accurate to within 0.1%.
Scenario 2
tx2 is transmitted 30 seconds after tx1.
This scenario is of interest because it maximizes disagreement among nodes on whether t < T. Nevertheless, we see that miner's decision to exclude tx2 is straightforward on economic grounds.
Results:
- 100% of nodes receive tx2 after tx1.
- 50% of nodes receive tx2 more than 30 seconds after tx1.
Miner makes an economic decision whether to include tx2. Consider a miner who sees tx1 and tx2 exactly 30 seconds apart. He infers that if he includes tx2 in his block, 50% of hash power will not build on it. That cohort must mine 2 blocks to overcome it. Expected cost (over a 2-block horizon) of including tx2: (50%)2 * (25 BTC + fees) > 6.25 BTC. Benefit: (tx2 fees - tx1 fees) = .03 BTC. The economic decision is to exclude tx2.
Miner can reduce his risk by setting a threshold lower than 30 seconds for exclusion (NOT for evaluating others' blocks), or by simply excluding any transaction that locally evaluates to being a double-spend, no matter how small the respend gap. Bitcoin core does the latter.
Figure 4 illustrates the likelihood of node measuring a particular respend gap t in this scenario. Focusing on the range less than T=G=30s; we see the effect of the distance from G, and the median transaction propagation time, on the probabilty of measuring t to be at or below a particular value.
Figure 4, Scenario 2 Cumulative Distribution of Measured Respend Gap by Median Propagation Time
Scenario 3
tx2 is transmitted 60 seconds after tx1.
Results:
- 100% of nodes receive tx2 after tx1.
- 100% of nodes receive tx2 more than 30 seconds after tx1
Consider a miner who sees tx1 and tx2 exactly 60 seconds apart. He infers that if he includes tx2 in his block, 100% of hash power will not build on it. Expected cost of including tx2: 25 BTC + fees, Benefit: (tx2 fees - tx1 fees) = .03 BTC. The economic decision is to exclude tx2.
Incomplete adoption
Examine the effect of incomplete network adoption of the double-spend deprecation rule.
The effect of incomplete adoption is to reduce, by a factor of the adoption rate, the deprecating cohort's proportion of the network. To see how the economic incentive reacts to incomplete adoption, define a break-even adoption rate such that:
Expected Cost(BreakEvenAdoptionRate) = Benefit
(BreakEvenAdoptionRate * DiffCDF(...,T=30))^2 * 25 = .03
BreakEvenAdoptionRate = sqrt(.03/25) / .5 = 6.9%
Under our assumptions, it is economically advantageous for miner to exclude double-spend tx2 as long as he believes that as little as 6.9% of the network has adopted the double-spend deprecation rule. Our 100% adoption assumption turns out to be far from critical.
Now keep other parameters constant and consider the effect of a more aggressive rule, one with a smaller value for T. The break-even adoption rate increases as the rule becomes more aggressive:
Table 4, Break-Even Adoption Rate vs. T
| T | DiffCDF(...,T) | Break-Even Adoption Rate |
|---|---|---|
| 30.0s | .5 | 6.9% |
| 29.5s | .346 | 10 % |
| 23.8s | .0346 | 100 % |
If 100% of the network adopts a double-spend deprecation rule with T = 23.8s, it is marginally economically advantageous for miner to observe that rule by deprecating double-spends with an observed respend gap of as little as 23.8 seconds.
This result is sensitive to the other assumptions in our example. In particular, T can be safely lowered further as transaction propagation mean and/or variance decrease.
Confidence to include tx1
A double-spend attacker succeeds when he receives value in exchange for tx1, but prevents tx1 from being confirmed. So, not only is miner incentivized by this proposal to exclude deprecated respends, but also he must be confident that he can include tx1 without causing the network to deprecate his block. Excluding tx1 would hand victory to the attacker.
When tx1 is received, simply because it is a first-seen spend, miner can expect that no more than 0.094% of the network believes it is a respend of some unseen-by-miner transaction sent 30 seconds earlier.
If miner waits another M = 30 seconds without seeing a double-spend of tx1, the portion of the network expected to believe that tx1 itself is a 30-second respend in the other direction is a tiny 0.010%, or 1 node out of 10000. As a point of comparison, this rises to 0.58% or 58/10000 nodes, if median propagation time is 4 seconds rather than 1 second.
The transaction maturation rule therefore suffices to protect miners from risk of deprecation due to random propagation effects.
Deliberate deprecation attack
Consider a concerted attack aimed at convincing many nodes to deprecate blocks. If executed in collusion with hash power, such an attack would give a mining advantage to the extent it caused others' blocks to be deprecated.
Honest miner relays tx1 as soon as he accepts it. But the threat of DoS attack requires that remote nodes only track and relay one conflicting transaction per coin. With this restriction, a remote node with a transaction tx1r, which conflicts with tx1, may be unaware of tx1 until it receives miner's block. If this happens, remote node may deprecate the block. Miner is interested in capping the likelihood of such a deprecation below an arbitrary level through his choice of M.
For remote node to ignore tx1, it must have already received two tx1 conflicts. Consider the worst-case sequence of events at a remote node:
- Remote node receives tx1r
- Next, remote node receives a conflict tx2r which, as first conflict for the coin, is relayed
- Next, remote node receives miner's tx1, which it ignores
The worst case is that all three transactions are received as close to simultaneously as possible, while maintaining this ordering. Any reordering would cause miner and remote node to agree on the existence of tx1. Any gaps would make it more likely for miner to have received tx1r from remote node, before having received tx1. So, in the worst case, at the moment it receives tx1, remote node has just transmitted tx1r.
Figure 5, Worst-Case Sequence of Events
At miner node, define a worst-case conflict gap w as:
w = node_time_received(tx1r) - node_time_received(tx1)
w is a random variable which has the distribution of the sum two lognormal propagation times (outbound tx1 plus inbound tx1r). Miner cannot identify tx1r as such, and cannot measure w. But he measures the respend gap t between tx1 and the first double-spend tx2. If tx1r is not itself the first respend tx2, then it arrives later than tx2, so the respend gap t is a conservative estimate of w. Figure 6 illustrates the likelihood of the worst-case conflict gap w being at or below a particular value M.
Figure 6, Cumulative Distribution of Worst-Case Conflict Gap
From this plot miner knows that, if he sees no double-spend of tx1 within a transaction maturation time M = 15 seconds, then less than 2.1% of the network will deprecate his block for including tx1. If he sees no double-spend within M = 30 seconds, then less than 0.27% will deprecate it.
These are grossly conservative estimates. In addition to the under-estimation of w, they assume the block took more than 30 seconds to be found, and 100% adoption of the double-spend deprecation rule. And unrealistically, these estimates assume that 100% of the network experiences the worst-case event sequence and timing.
Seeking to cause 100% of the network, except for miner, to receive a conflict pair like (tx1r, tx2r) immediately before tx1, attacker's success will be moderated by 2 factors:
- His ability to transmit messages timed to an accuracy << 1 second to a large portion of the network simultaneously, otherwise random delays disturb the order of events
- His ability to identify miners and transmit unique isolated tx1's to each
As educated guesses, assume 33% for the first factor (3 transactions being shuffled) and 50% for the second. Now miner estimates that 0.046%, of the network, 5/10000 nodes, will deperecate his block for each transaction that has seen exactly 30 seconds with no double-spend. This is during a concerted attack.
In practice, a suitable value for M would be determined empirically and by starting with a conservative value. M = T = 30 seconds would be a simple choice, but it would mean that within about 30 seconds, spender could effectively issue a "stop payment" on tx1 by double-spending it. Ideally, M and T would be set independently, each as small as possible.
Fragmentation attack by hash power
Suppose that miners decide to attack the network by deliberately including in B a tx2 with respend gap tB exactly equal to T (30s in example), with the goal of generating disagreement on whether their block should be deprecated. Presumably they would do this repeatedly in an attempt to splinter the network.
Miner already has an even easier vector for such an attack. He can simply assign to his block X a blocktime of exactly (now + 2 hours + avg-block-propagation-time). Due to propagation and node clock differences, X is rejected by 50% of the network. The half that accepts X will switch if a competing chain reaches length 2. The half that rejects X is highly likely to switch after it is confirmed by just one more block - the reason is that after a few seconds (avg-block-propagation-time), X will have become valid.
The network reaction to B is virtually identical to the reaction to X. Half of the network deprecates B, but switches to B when one block confirms it; the half that accepts B will switch away from it if a competing chain reaches length 2.
Targeting tB = Tfull can produce 50/50 disagreement on the strength of the penalty, but disagreement on its existence is limited in this case by the likelihood of a propagation time difference > Tfull - T. This likelihood can be made arbitrarily small by the choice of Tfull. With the numeric values considered, it is less than 1.5% of nodes. Disagreement on penalty strength alone does not amplify the attack beyond the attacker cohort, unless some other part of the network is running custom rules that match neither current behavior nor this proposal.
References
[0] S. Nakamoto, Bitcoin: A peer-to-peer electronic cash system, 2009, https://www.bitcoin.org/bitcoin.pdf
[1] H. Finney presents idea, 2011, https://bitcointalk.org/index.php?topic=3441.msg48789#msg48789
[2] C. Decker, Data Propagation Daily Snapshot, http://bitcoinstats.com/network/propagation/
[3] G. Andresen, T. Harding, Bitcoin core pull request, Relay first double-spend as alert, notify wallet, 2014, https://github.com/bitcoin/bitcoin/pull/4570
[4] Real-time observed double-spends, http://respends.thinlink.com
Thanks to Andrew Poelstra, Christian Decker, and Matt Corallo for very thoughtful contributions.