-
Notifications
You must be signed in to change notification settings - Fork 26
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Timestamp Attacks #30
Comments
This was referenced Aug 7, 2018
This was referenced Aug 11, 2018
This was referenced Dec 7, 2018
aviator-app bot
pushed a commit
to tari-project/tari
that referenced
this issue
Sep 16, 2021
Description --- This changes the timestamp of a new block template to be always greater than the median time past (MTP) of the past blocks as per consensus. Motivation and Context --- It is possible for an attack to forward the median time to be greater than now, but less than the future time limit(FTL). This means that all valid blocks with the current timestamp will be rejected. This will ensure that ll newly created blocks always have a timestamp greater than the MTP. Due to consensus we also know that MTP will always be less than FTL. This ensures that all new block timestamps are `MTP < Timestamp < FTL` For a description see: [Graft network](graft-project/GraftNetwork#118 (comment)) and [MTP Attack (Jagernan)](zawy12/difficulty-algorithms#30) How Has This Been Tested? --- All current unit tests pass.
Open
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
"A Compleat Collectioin of Englifh Proverbs" - Rev. John Ray, 1668, page 33
Overview
The following are clock and timestamp requirements for distributed consensus. Following these rules prevent all known attacks on Nakamoto consensus except a basic >50% hashrate attack. It prevents timewarp, selfish mining, and peer time attacks as well as a slew of other attacks seen in alt coins. The rules are usually broken by good intentions that add code.
Timestamp attacks result from "good intentions" or other mistakes that modify the local clock or timestamp constraints required by Nakamoto consensus security proofs. All distributed consensus mechanisms require the clock (local time) to be more secure than the consensus mechanism [1][3] and messages (blocks) must have sequential (monotonic) timestamps.[2] Allowing non-sequential timestamps in bitcoin has caused many problems. The block height is not sufficient (or necessary) because timestamps estimate hashrate to set difficulty which determines which tip has consensus, overriding block height. Timestamps estimate total hashes which are the events for Lamport ordering. A 3rd fundamental requirement of all distributed consensus mechanisms ("all" includes Nakamoto consensus because the 1978 derivation by Lamport didn't depend on the algorithm) is there must be a limit on how far in the future (ahead of local time) timestamps can be. In practical terms, to prevent all the attacks and problems described on this page, Nakamoto consensus must:
If any of the above requirements are not in place, there's an exploit.
The following are examples of bad ideas that harm the consensus mechanism. Patches on top of patches are often applied. The problems are not solved unless the patches are algorithmically at least as restrictive as the above requirements.
Most coins have # 2 which allows an attacker to get > 5000 blocks in a few hours with my timespan limit attack (if they also do not force sequential timestamps).
The following repeats the requirements above differently. The theoretical reasons are explained in the introduction further below and in the footnotes.
Contents
Short Summaries of Attacks covered:
51% attack on symmetrical limits that allows unlimited blocks in a few times the difficulty averaging window. Not imposing the limits could enable a a malicious attack forcing a negative difficulty. Solution is to require sequential timestamps. Non-symmetrical limits in Digishield allow 50% extra profit in selfish mining even with sequential timestamps. ETH has similar problem that allows 75% more profit (see ETH attack)
A 6-block attack MTP causes miners to have blocks with honest timestamps that are before the MTP blocking them, allowing attacker to get 100% of the blocks with small hashrate.
FTL too large, allowing difficulty in all algos to be briefly lowered, periodically. Allows 10% more blocks in a 10-block attack on BCH's 10-block rule with any difficulty algorithm.
A Sybil attack on peer time (which is an unnecessary non-POW consensus rule) which can block honest miners in a way like "jagerman's" MTP attack, or isolate a merchant to accept only your blocks while doing a double spend on the public chain.
Sybil attack on peer time combined with a future timestamp on a block may freeze a node by making a previously-valid block have a time in the future. An extension of Culubas timejacking.
Algo allows a negative in the extremes, requiring a protective limit that enables a >51% attack to get 175% of the blocks instead of 100%. Similar idea to timespan limit attack.
Aka out-of-sequence timestamp problem # 1. If a difficulty algo that uses individual solvetimes does not modify the way it uses the most recent timestamps, this attack uses the non-symmetrical timestamp limits (FTL & MTP) to lower difficulty to zero. It can be done with <49% hashrate, depending on how asymmetrical the limits are.
Caused by a hole in BTC's difficulty code.
Attacks Without a Specific Section below.
Chain work is not the perfectly correct way to choose the tip with the highest average hashrate. If a difficulty algorithm changes significantly while hashrate is constant, an attack can exploit this to win a tip race with < 50% hashrate. A bigger error is caused by not using an N/(N-1) adjustment to increase chain work as the number of blocks in the tip increases. Another error is that there is no reduction in a chain work calculation if the tip was solved a longer time in the past than a competing tip. An example attack I thought of for a 6/29/2020 comment for an extremely fast-changing DA with FTL = 7200 allows getting 133% of blocks with only 8% HR attack. An RTT might allow for a 100x change in difficulty in each block which enables a selfish mining attack where a 2.6% HR will be calculated as 51% HR. hashrate. The fix is to correctly calculate chain work (which is very difficult for non-TSA type of RTTs)
Out-of-sequence problem # 2. Some algos that allow out-of-sequence timestamps can allow a >50% private mine to hold up the MTP far enough that it can submit a highest work chain to the public, knowing that all the nodes will get a negative or divide by zero difficulty on the next block, potentially halting the chain until a fork. I do not cover this below.
Out-of-sequence problem # 3. If the chain allows out of sequence timestamps, a big on-off miner will find it beneficial to make his last timestamp as in the past as possible, back to the MTP. This will make difficulty higher for everyone else on the next block which will encourage an oscillation so that it is lower when he returns. I do not cover this below.
ZEC's February 2020 security patch made a more strict FTL based on MTP instead of local time. This allows a miner to forward the MTP to the 90 minute limit, forcing other miners with honest timestamps to help him exploit the asymmetrical 16% and 32% limits without needing the very precise private mine as detailed in the timestamp attack section. It increases coin emission rate by at least 25%. See this..
A >50% (of total hashrate) block-withholding attack on ASERT / EMA that results in 38% more blocks than than the public chain and 50% more on SMA coins. I have not tested the size of the vulnerability in Digishield. I can't find a vulnerability in LWMA but it opens an interesting but difficult-to-solve question: what is the optimum timestamp sequence to use in LWMA (or any DA)? When I say "50% block-withholding mine" I mean a miner on another coin with 100% of the current hashrate decides to attack a coin, thereby becoming 50% of the total. Example attack on ASERT N=288. 1st timestamp set equal to 2*N*T - 1.38*2*N seconds after previous one. Next 1.38*2*N timestamps set 1 second apart. The average D of the blocks is 0.729 of the public chain. It takes 2*N*T to get them and the total chain work is 2*N blocks at the avg public difficulty so it wins chain work. Attack on SMA coins with window of N: 1st timestamp is 0.66*N*T into the future. Block-withholding for N block and quits. It takes only 0.66*N*T time to get the N blocks. ETH has an "inverted EMA" algo that required a patch that increases the 38% to I believe well over 74% (the 74% is described in its own section below). All these attacks can be prevented if honest miners do a sanity check on timestamps and agree to ignore the cheater's chain, but this assumes they know the cheater will quite and not let the chain get further ahead. The effect appears to be much worse in RTTs unless my TSA type of RTT is used (the RTT "rides on top" of a regular DA, not directly affecting the subsequent difficulty calculation) or unless the RTT math is made ugly (made incorrect for getting the correct avg solvetime, so after modifying the DA you have to test to determine a fake target time in the equation that will result in the correct avg solvetime) to give a greater penalty to fast solvetimes than it is supposed to and limiting the adjust to say 6xT (which greatly harms the ability of the RTT to recover in a stuck chain situation). I mentioned this is for a "100%" attack. It is more difficult and harder to predict the consequences if a miner with 50% of the current hashrate switches to a private mine. Theoretically he gets the same benefit, but by switching, the public difficulty will start to go lower which will attract more public hashrate that can beat his hashrate. This attack causes large changes in difficulty which means the attacker will be credited with more hashrate than he actually has and therefore this attack can be significantly worse than I've indicated because (as discussed above and in another issue) the actual chain work (if hashrate is constant) is the number of blocks times the harmonic mean of the difficulties, not the sum of difficulties, and the harmonic mean is always lower. This last effect can be corrected by correctly calculating chain work. This attack could be stopped by penalizing a chain who's solvetimes are obviously not following a legitimate exponential (P of solvetimes), Poisson (P of k blocks per time), and Erlang (P of time per k blocks) distributions that apply to hashing, but I do not know how to do the corrections. They have to assume constant hashrate which means a legitimate variation in public hashrate or just random variation could end up giving an advantage to an attack who exploits the correction.
Introduction
All timestamp attacks result from violating the Byzantine fault tolerance foundations, undermining the Nakamoto consensus security.
If every node points to a certain BTC chain as the correct chain and it has a massive amount of chain work, your node can unilaterally reject it if a single block is beyond your local time plus the FTL. Nakamoto consensus requires node operators to have an independent ("maximally decentralized") opinion of current time. Median of peer time in Nakamoto consensus is subject to a Sybil attack.
If we do not want a "somewhat arbitrary" but agreed-upon ordering[2], there is no consensus mechanism that does not require a "prior" consensus on time[1][3] (or a time oracle) within clock error and network delays (FLP impossibility). In Nakamoto consensus, time does not merely dictate the start and end of voting rounds (to measure votes cast or allow lottery tickets to be redeemed) as in other consensus mechanisms, it measures the number of lottery tickets purchased (hashes) in order to find the least-partitioned chain (highest number of tickets purchased aka most-work) by increasing difficulty by seeing too-fast solvetimes. We can't use any consensus mechanism to determine time without weakening the decentralization of Nakamoto consensus. So how do we get get time? Ideally, nodes determine it without reference to an authority other than their operator. The node must be its own oracle. NTP and GPS are feasible, but they are central sources that may be attacked. Even the U.S. government does not trust that GPS can't be brought down. The deepest consensus principles require nodes to unilaterally and incontrovertibly decide the time. Do not change or limit what it says beyond what the consensus security dictates (see next paragraph). Ultimately the node's oracle should be the stars, subject to any changes the UN's UTI agency makes in defining UTC. But even that's centralization. Ideally, all the nodes should operate a telescope and calibrate sufficiently frequently based on the position of the stars and the node's geographical location so that the UTI can't change the definition of UTC. BTW, other astronomical observations may enable a permissionless (maximally decentralized) source of randomness to replace the permissioned aspect of "decentralized" random beacons.
Anything that changes or restricts the oracle's (the node's) opinion of time (including the allowable timestamps range or how they are used) affects the correct estimation of hashrate aka our consensus votes (lottery ticket purchases). Any incorrect estimation of current hashrate causes harm to Nakamoto consensus. FTL, MTP, and median of peer time are all "well-intentioned" patches to our lack of a common time oracle (excepting the stars) but they all cause problems in proportion to how far they are from true time. There's a long history of reducing their values to stop future attacks. FTL is the only one that arguably should not be zero due to honest clock error. It is not unreasonable to have FTL=10 seconds. If the mining network has nodes with clock error > FTL, it can block valid winners for a time, increasing the orphan rate. The fraction of FTL to the difficulty averaging window is the fraction that manipulation can decrease difficulty in one or more subsequent blocks.
Sequential logical stamps are a requirement of distributed ordering.[2] To prevent "somewhat arbitrary" ordering, physical clocks must be used and they allow or assign any timestamp before any prior timestamp that the node approved) It appears using MTP=1 instead of MTP=11 (which means the 6th block in the past will be the "MTP block" if the 11 timestamps are in order) will force the next timestamp to be greater than previous timestamp. If all the code elsewhere is written correctly, nothing will be broken by this change and the remaining exploits in bitcoin will be impossible. Digishield and other difficulty algorithms prevent an attack from non-sequential timestamps by using the MTP block as the most recent block and this causes persistent but small oscillations. If monotonic timestamps are not used, the next best solution is to use code in the difficulty algorithm to create a "fake" sequence of monotonic timestamps when they get out of order, but not "if solvetime < 0 then solvetime = 0".
Giving miners more room to set timestamps (within the 2-hour FTL and MTP=11) appears to be from a mistaken belief that the average honest miner is setting the time. But nodes individually and unilaterally set the limit on how much time can be forwarded and miner greed of wanting blocks as minimal difficulty prevents them from holding time back.
I want reiterate that [1] shows ordering is possible without a clock. This is potentially very useful in new coin ideas. In another scheme, the time oracle can be reduced to assuming a maximum drift rate in the nodes' clocks.[4] This provides every node with the ability to survive any attack on network time, like a node looking at the stars to unilaterally determine time. In either method, they can know they have the correct system-wide consensus even if every other node in the system disagrees with them.
Definitions:
Note on the Verge Attack
The Verge attack seemed to have been a combination of a too-long FTL value (forward timestamps), a 1/3 and 3x timespanLimit attack, making the longest chain the one with the most blocks instead of chain work, and the attacker having a lot of hashrate in one of the algos.
TimespanLimit attack (aka timewarp) #
I originally mistakenly called this the powLimit attack.
I discovered this while writing this article to explain the Zeitgeist attack. My own LWMA difficulty algorithm was the first to be attacked using it (that I am aware of) about 40 days after I wrote this article. I mistakenly thought mine was immune. In April 2018 LWMA coins attacked were Niobio, Intense, Karbo, Sumo, and a couple of others. I don't know if the Verge attack that occurred then used this. Typically in an hour or two attacker could lower difficulty to 1/100,000th the original value and get 5,000 blocks.
This uses the "timespanLimits" against themselves using a specific sequence of timestamps. Most coins have inherited some form of the timespanLimits from BTC. It almost always requires 51% hashrate block-withholding mining attack to have complete control of the timestamps. The result is that an attacker can get unlimited blocks in less than 3x the difficulty averaging window. The attack is stopped if monotonic timestamps are enforced, or the MTP is used as the input to the difficulty algorithm (another type of monotonicity).
In places I may say or imply both limits are required to perform the attack. The only necessary condition to increase emission rate is a limit on how high the difficulty can rise in a block such as a limit on how short the timespan is. The converse limit may cause a decrease in the avg block emission rate.
Update: In places I mention the MTP-forced sequential timestamps in Digishield (like Zcash) prevent this attack. In fact, the asymmetrical 16% and 32% limits on timestamps in Digishield allow a 51% attack to get about 50% more blocks than the normal 100%. The process is: alternate stamps between the MTP and the value that maximizes the drop without exceeding the 32% limit. That value is the median of the last 3 in the window plus 5814 seconds which comes from (1.32-0.75)*150*17/0.25 = 5814. Alternate for 10 blocks. Then make each stamp 150 plus previous stamp for 11 blocks. Repeat the cycle however many times. The difficulty will lower but your clock will be ahead of time. End attack by setting every stamp equal to the allowed MTP. Your clock stops while difficulty rises until your clock time is equal to current time and you can end the attack.
Conceptual Overview
The timestamps in simple moving average (SMA) and BTC-type algos are selected to alternate between forward stamps that reach the upper timespan limit and delayed stamps that EXCEED the lower limit. This makes difficulty go up and down by the same amount, but by exceeding the lower limit, we can delay time which allow us to use more forward stamps to repeatedly lower difficulty, without without costing all the time we gained, eventually getting many block in little time. Direct limits on difficulty changes per block or limits on individual solvetimes per block can be similarly attacked.
Attack Specifics for SMA-type algorithms
N = blocks in difficulty averaging window
T = target block solve time
L = timespan limit which is 4x in BTC, 3x in Dash, and 2x in BCH.
Here's a quick review of a SMA difficulty algorithm:
next_target = sum_targets * T / ( timestamp[N] - timestamp[0])
The denominator
timestamp[N] - timestamp[0]
is limited to L*N*T and N*T/L.A block-withholding mine that has complete control of timestamps keeps the MTP delayed by making 6 of every 11 blocks' timestamps set back to the MTP limit. This does not require the 2015/2016 "hole" that exists in bitcoin. The first timestamp ( I call it "Q") is set forward in time to drop the difficulty the most it can by setting the timestamp so that the timespan limit reached. This is M = N*T*L seconds after the timestamp of the block that is at the beginning of the averaging window, N blocks in the past. Unlimited blocks can always be obtained in less than 3*N*T (3 averaging windows). In the simple attack (that may take 2x longer) the first N=2016 blocks are just set to Q plus 1 second for each block after the block with the initial Q timestamp. The plus 1 second is because Q will soon become the MTP and the MTP rules normally require timestamps to be at least 1 second after the MTP. After the first N blocks, we start alternating timestamps between Q+i and Q+M+i where i is the number of blocks into the attack. We do not have to advance 1 second on the Q+M blocks, but it makes coding simpler at a slight cost in time. We alternate according to a specific rule: if a Q+M+i timestamp is not going to cause the MTP to increase in the next block, and if the block at the back of the averaging window N is a Q+i block, we assign a Q+M+i timestamp. Otherwise, we assign a Q+i timestamp. The chain is submitted to the public when current time equals Q+M+i. In code this simple attack is the following.
Code to demonstrate this attack in SMAs and others (in future)
Which coins are vulnerable? Half? Most coins have inherited a timespanLimit idea from Bitcoin which uses 1/4 and 4x. Coins that use the MTP as the most recent timestamp in their difficulty calculation are not vulnerable, but there are better options for small coins than using the MTP delay in responding to hashrate changes (MTP delay causes oscillations). Digishield coins appear to use MTP as most recent timestamp, so they are not vulnerable. [edit: Digishield coins are vulnerable if they are not using the MTP as the most recent block...I know of a big coin that has been attacked with it.] DGW coins do not, and therefore appear vulnerable. Coins that do not place limits on timespans are not vulnerable to it. Coins like LWMA that look at individual solvetimes are vulnerable if they have limits on the solvetimes.
The following type of limiting is subject to the same attack:
next_target = max(0.5*prev_target, min(next_target, 2*prev_target));
KGW (Kimoto Gravity Wave) may be even more vulnerable because it has a timespan limit here
if (PastRateActualSeconds < 0) { PastRateActualSeconds = 0; }
that prevents difficulty from rising but not a symmetrical limit to prevent it from falling.
Solutions:
timespan = median(TS[i]...TS[i-11]) - median(TS[i-N]...TS[i-11-N]) ;
targetSum = sum(target[i] to target[i-N+1])
I'll describe 4 versions of this attack that use the same general idea. Only the last can be done with < 50% and requires the difficulty algorithm to have MTP/N > timespanLimit (in SMA terms).
Other problems timespanLimit causes: It causes Digishield coins to surprisingly take 500 blocks instead of 80 to reach the correct difficulty at startup, which I covered here.
Here's an old method I had of doing this attack that's not as good as the new one.
https://user-images.githubusercontent.com/18004719/43910698-898e682e-9bcb-11e8-8720-caf74d5fc495.png
timespanLimit # 2 (public method)
In public non-block-withholding mining) version, the attack first makes the MTP get way behind with a lot of MTP timestamps, raising the difficulty. He then proceeds like the block-withholding mining version of this attack, letting other miners assign the honest timestamps which are acting as "forwarded" timestamps, while he focuses on trying to maintain the MTP as old as possible, but coinciding with every honest timestamp possible as they pass out the back of the averaging window, and sometimes letting it coincide with other delayed timestamps, to make sure he maintains the delayed MTP.
Hashrate required: It requires > 90% hashrate if a coin uses the common MTP=11 and the FTL is not too large, so often it's not practical. Cryptonote coin default has MTP=60 which makes it easy, but they do not usually have a timespanLimit. It is also easier to a much smaller extent if the algorithm has short a averaging window, largish FTL/(T*N) ratio, small timespanLimits, or asymmetrical timespanLimits. It requires extremely high hashrate for smallish MTP=11 because the attacker has to get 6 of out every 11 blocks, without fail, or the attack ends and he has to start over. The following is my first pass estimate of the hashrate needed. The attack has to last at least 1.5*timespanLimit*(blocks in averaging window) to be profitable because these are the delays that result from making the MTP behind real time by the initial and necessary 2*timespanLimit*(window timespan) seconds. The smallest N for averaging windows are about 15. Some timespanLimits are 2x instead of 4x. 1.5*2*15 / 11 = 8 sequences of blocks of 11 that the attack must get at least 6 of them. 6/11 = 55%. 0.55^(1/8) = 93% in a good case scenario, not counting an advantage an attacker can gain from a large FTL/(TxN) which lowers this.
timespanLimit # 3 ( block-withholding mining on BTC-type algos)
These are the timestamps a 51% block-withholding miner can use to get infinite BTC blocks in 16 weeks.
timespanLimit # 4
The attack is easy and possible by < 50% if the % a single reverse timestamp can raise the difficulty is more than the timespanLimit. As those timestamps pass out the back of the window, the difficulty will drop more than it was allowed to raise. This is provided the limits are symmetrical or the drop limit is more than the rise limit. In SMAs, an attacker would look for MTP/N > timespanLimit. In Digishield 4x dampening: MTP/(4*N) > timespanLimit. In EMA, LWMA, and DGW types that give more weight to recent blocks, it's about 2*MTP/N > timespanLimit. Technically it's 1/timespanLimitsince it's in target.
MTP Attack (Jagernan)
An attacker with 25% hashrate can get lucky and find more 6 or more of the past 11 blocks, allowing him to "own" the MTP (if it's set to BTC's 11). He could forward those timestamps to the FTL limit (2 hrs in BTC). If there is an error in the template code which does not automatically give the miners timestamps similarly into the future (MTP+1), nodes will reject blocks (those with honest timestamps). Attacker could get 100% of all future blocks until other miners give their nodes a future time or fix the template-creation software. This was accounted for in BTC, but it was lost in cryptonote coins. Jagerman found the issue while tracking down Graft attacks and released a patch.
Zcash's 2/6/2020 security update could have allowed this same attack in the opposite direction by basing a new FTL limit off of the MTP but the devs knew to prevent it by having the template code use false timestamps. (https://github.com/zcash/zcash/blob/ba20384845c04fe7f3c7a585fc99d57bfccdb54b/src/main.cpp#L3829-L3840). If they had not not to enforce a dishonest stamp, attacker would have just needed to send 6 timestamps 120 minutes into the future, blocking all other miners who attempt to use honest timestamps in their templates. He can get all the blocks at low hashrate until other miners learn to give their node a fake time into the future.
Node Peer Time attack on FTL ("Culubas Timejacking")
In many coins like BTC, ZEC, and BCH, nodes use the median of their peers as the current time to enforce the FTL above. Coins should not use peer time because a median from peers is a consensus mechanism that does not have POW security. This allows a Sybil attack to slow a victim's network time up to the point that blocks with honest timestamps will be more than the FTL past the victim's network time, causing him to reject the blocks, at least until the block's time is in the victim's past. This allows the attacker to use bad timestamps to get accepted by the victim, enabling a double spend on the victim. If he can do the attack on a < 51% pool, he only needs half of the remaining hashrate to do a block-withholding attack to keep the blocks, and possibly do double spends on an exchange using the victim pool.
These attacks are hard to do on BTC, ZEC, BCH, etc because they revert to a node's clock time and throw a warning if median of peer time is > 70 minutes off from the node's clock. This is about 1/2 of the FTL on purpose. So the attacker can advance the victim's clock by 70 minutes before it will attempt to use its own clock, but because the FTL is a lot longer, the victim will not reject blocks with honest timestamp. So the cure is to make the revert to node time rule about < 1/2 FTL.
But it needs to be less than 1/2 FTL as Culubas's long 2011 article says. This is because the attacker might be able to do a Sybil attack on the miners' network and send the majority hashrate's time in the opposite direction regaining the ability to force the victim's node to reject the main-chain's timestamps. Attacker still needs substantial hashrate because after a while, the public chain 's older stamps will start being valid to the victim. Culubas considered the options and decided simply making the revert rule 1/4 of FTL seems to be the best.
My preference is to remove median time all together. Cryptonote who uses only the node's clock time without any problem. There was an discussion on this between kjj, kheymos, and Mike Hearn. (I agree with kjj)
Removing peer time in the above and near-perfect (+/- 1 second) local time does not eliminate the problem. An attacker with 25% hashrate could send a timestamp equal to the FTL to split the network in half and work on that tip while 1/2 the honest miners work on the older tip. His tip has 25% + 75%/2 = 62.5% hashrate the other tip has 37.5%.
Peer time / timestamp attack on database (Michael Davidson disclosed to Zcash Dec 2019)
After some sleuthing (with help from @h4x3rotab ), this is what I think motivated Zcash to do a security update.
The database code gets the node stuck (during reboot) by the attacker making previously-approved blocks invalid due to being in the future. A Sybil attack makes the victim nodes time go into future up to the peer offset limit (70 minutes in BTC etc). He then finds a block with a timestamp up to the normal future time limit (120 in BTC et al) plus the 70 minutes. If the node reboots in 70 minutes (can the attacker motivate a reboot?) the node can't reboot because it is not connected to the problem peer time and sees a block with a timestamp in the future.
Another attack could be to send miner nodes peer time 70 minutes into past and then find blocks with timestamps at 120 future time limit. Non-attacked nodes will approve it, but the attacked nodes will cause their miners to reject those blocks and work on a chain that will get orphaned.
Zcash's fix was to by default not allow peer time. That fixes it. But users can still select to use it. So they added a 90 minute FTL limit relative to the MTP timestamp in addition to the normal FTL=120 and limited the amount peer time can adjust time to +/-25 minutes. Or rather they make sure the constants obey 25 + 90 < 120 in case they are changed them in the future.
Forwarded Timestamp Attack (FTL attack)
A typical timestamp attack is to set the timestamp of a solved block to the max future time limit (FTL) that nodes will allow. Most coins just accepted BTC's 2 hour FTL like Cryptonote, Zcash, and all the clones that came after. This was a problem because N*T in clones is a LOT lower in clones than BTC, and the amount a forwarded timestamp can lower difficulty in a single bock is
next_difficulty = average_difficulty * 1/(1+FTL/(T*N))
next_target = average_target * ( 1+FTT/(T*N) )
This attack does not cause much of a problem even with a 30% potential drop in 1 block (according to the above equation) if the attacker has < 50% of the network hashrate and the algorithm is allowing out-of-sequence timestamps and not monkeying with the math so that it the next honest timestamp is block from correcting it. If the attacker has 51% hashrate, he can start getting ahead of the honest timestamps until it has reached that amount of drop. He then starts "bumping into the FTL" and is forced to quit and let the difficulty rise back up to the correct value in N blocks, so a 51% miner on a "30% potential drop" coin (based on FTL, N, and T) gets N blocks at an average difficulty that is 15% too low from beginning to end of attack which is about N blocks. He then needs to stop manipulation for N blocks to let D rise back to normal to repeat with equal success. More likely, he will be a >3x miner who can get N/4 blocks at about 25% lower difficulty with a brief attack before moving to another coin for > N blocks.
Solution: Use FTL < N*T/10 for < 10% manipulation (lowering) of the difficulty with a single block.
Ethereum Timestamp Attack
This allows a >50% block-withholding miner or a 66% attack on the public chain to release more blocks than scheduled in the Homestead algo. It could be prevented with using a slightly different form for the math. See the bottom of my ETH difficulty article.
Reverse Timestamp Attack
If a coin is using an algorithm that sums solvetimes instead of subtracting first and last timestamp in the window, and if it is allowing or incorrectly adjusting for out-of-sequence timestamps by using
if solvetime < 1 then solvetime = 1
(or in some cases simply sorting timestamps), its difficulty will drop to zero when a miner starts sending reverse timestamps. The negative solvetime is being ignored and the subsequent honest timestamp is being viewed by the algo as a really long solvetime because it subtracts current timestamp from that fake old one. The attacker can have significantly less than 50%. For MTP = 11 (a median at 6 blocks in past limit), it only requires > 1/6 of the network hashrate to start lowering difficulty.
Solutions:
timespan = median(TS[i]...TS[i-11]) - median(TS[i-N]...TS[i-11-N]) ;
Zeitgeist Attack
This appears to be named after a 2011 GeistGeld attack described by Artforz. The only place I could find it called this is Litecoin's wiki and they have a "2" appended to the end, which I've dropped. I historically called this "the" timewarp attack and got people to say "timestamp manipulation" for other things.
The attack is not possible in any typical rolling average method. This is because it depends on a gap in the way BTC is calculating the next target. The attack is still possible on BTC, but it requires a > 50% miner.
UPDATE:
This is an executive summary for those already a little familiar with the attack. Further below has the gory details.
He needs >50% to perform a block-withholding mine so that he has control of the timestamps. He has to get at least 6 out of every 11 blocks for at least 2016 blocks to perform the attack, which requires a LOT more than 50% if it's not a block-withholding mine.
A block-withholding mine attack with only 51% hashrate would go like this:
Start block-withholding mine at end of a 2016 block cycle.
Set 2016th timestamp to 2 weeks ahead. He can do this because he has set his node to not reject the future time. Difficulty will drop to 1/3 previous value because of this.
Set at least 6 out of every 11 blocks to 1 second after the MTP for next 2015 blocks.
Since attacker has 50% network hashrate, it takes 2/3 of a week to get them.
Set next "2016th" block to same timestamp as the 1st one, 1 week into future.
Since the MTP is still delayed to only 2015 seconds after the beginning of the attack, the calculation lowers difficulty to 1/3 again, 1/9 of the initial difficulty.
He gets next 2015 blocks in 2/9 of a week.
So he's 7*(2/3+2/9) =6.2 days into the attack with 4032 blocks.
He can repeat the process to lower difficulty as much as he wants, and get as many blocks as he wants in 2 weeks.
He can't submit the chain to other nodes until real time catches up with his forwarded time (2 weeks). He must block-withholding mine the entire 2 weeks to make sure he has the most chain work.
END UPDATE
A review
I've read there's an off-by-one error which may mean the timestamp[2016] is actually 2015, so the numerator may be 2015 solvetimes from the subtraction of 2016 timestamps instead of 2016 like I have it, so the result of the error would be that next_target is 1/2016 too low.
Here is a restatement of the equation to show by intuition that it should work. if avg solvetime was 50% too high, it raises target 50%, making it 50% easier (2x higher difficulty)
next_target = previous_target * average(solvetime) / target_solvetime
For reference, a simple rolling average difficulty algorithm is basically the same thing, except that it can change every block.
The Problem
I'll more fully explain ArtForz's description of the GeistGeld attack and shamelessly steal his example.
Let's say we have a chain with 3-block difficulty window instead of 2016, and target solvetime is 10 sec/block, and miners just happen to get all the blocks in exactly the target solvetime. So blocks would come in like this:
The old BTC algorithm with a 3-block window is: (ignoring integer math round off error)
next_target = prev_target * (timestamp[4] - timestamp[1]) / 3 / 10
I've called this a 3-block window but Artforz incorrectly called it 4-block. The (timestamp[4] - timestamp[1]) is only 3 solvetimes. For the above 10-sec solvetimes, next_target will be the same as previous target because all the solvetimes were the target solvetime (it does not need an adjustment).
The problem results from how one calculation of it does not begin exactly at the end of the previous calculation. It uses (timestamp[9] - timestamp[5]) instead of (timestamp[8] - timestamp[4]). The problem is that there's a solvetime not being accounted for. The solvetime (timestamp[5]-timestamp[4]) is missing. Someone figured out how to exploit this.
The Attack
I'm going to describe this as a block-withholding attack with a >50% miner, but enough hash power and lucky enough to always get at least 6 out of every 11 blocks for the entire 2016 blocks he can do this so that the difficulty is lowered for everyone. He could hold the median of the timestamps to increase only the minimum of 1 second per block, and then avoid setting the 2016th block to that delayed time (otherwise difficulty would jump (target would fall) to the max of 4x (1/4 previous target)), and be sure to get the 2017th block and set it to that delayed time which is only 2017 seconds after the previous week's final block instead of the real time which would be about 2016*600 seconds afterwards. Then he just needs to sit back for a week for the next adjustment which will drop to 1/4 of the previous difficulty (4x higher target).
Imagine a big miner with > 50% network hashrate starts block-withholding. He could assign timestamps like this
Note that most of his timestamps are assigned into the past. 30, 70, and 110 are the only correct timestamps. The MTP limit on past times will not stop this because the correct time coming once every 4 blocks will never be the median of the past 11. The FTL limit will not stop it because the miner doesn't need a node to approve it, and if he's using a node to send the block template, then he's changing the time on it to generate the above times, so of course the node will agree with itself.
The attacker's "sum of solvetimes" for the next_target numerators are:
first period (#4 - #1) is 30s as before => next_target = prev_target
2nd period is (#8 - #5) ... 66s => next_target = prev_target * 66/30
3rd period is (#12 - #9) ... 104s => next_target = prev_target * 104/30
So by the 3rd calculation, the target has risen 66/30*104/30 = 7.6x higher (easier) when it was supposed to be the same (for this example). In reality, if he had 51%, the first solvetimes would have been 2x too long, so target would have risen 2*7.6 by the 3rd calculation.
So the >50% miner can have all the blocks he wants in less time than the network has had to go through about 6 target changes.
When he decides to submit the chain to the network, he will make his final timestamp correct so nodes checking it against current time (within FTL limit) will not see a problem and approve it. They can't check prior blocks against current time.
If he has more than 50%, and his final blocks get back to current time, he will have more chain work by whatever proportion he was over 50% of the network hashrate, which is not related to how many blocks he gets or what the difficulties were. His advantage is that there will be many more blocks he's solved. Artforz indicates he needs to assign 1 second solves to make difficulty rise high at the end in order to win chain work, but that's not correct. It can't help him to get the highest chain work if he has < 50%.
Example: 51% Miner on BTC getting 100% of blocks
Let's say a 51% miner who's been mining BTC starts block-withholding right before a difficulty change, below the underline shown below. As he starts to block-withholding, the rest of the network is going to take 2x longer to find blocks because he has left.
![image](https://user-images.githubusercontent.com/18004719/43745088-08c3efce-99ab-11e8-819b-e75a26bfd7e2.png)
T = target solvetime = 600.
But because of the timestamp he's assigning, he's not going to have delays. Notice that his final timestamp matches real time so that he can then submit the chain to the network. Notice that he got all 2*2016 blocks in the two weeks he was block-withholding, while the network only got 2016, which they now have to discard. Despite having 2x more blocks, his total work is only 1% more than the public chain, which is the only reason he needs to have > 51%.
![image](https://user-images.githubusercontent.com/18004719/43746211-dc3e6564-99b0-11e8-8090-041246fa209f.png)
Red is the last block of a window, and blue is the 1st block. So the solvetime in the equation is red minus blue timestamps.
References
[1] 1993 "The Consensus Problem in Fault-Tolerant Computing" Barborak, Malek
[2] 1978 "Time, Clocks, and the Ordering of Events in a Distributed System" Lamport
Conditions IR2 and IR2' require sequential stamps on messages. This paper requires all events (change of state) to increase (no reset of a clock to be before a previously-ordered event). In the case of Nakamoto consensus, this means new timestamps on blocks can't be set to before validated timestamps on prior blocks. Block height is not relevant because a faster sequence of timestamps can override previous height ordering because it indicates a higher hashrate ("participation rate of voters"). "Timestamps used to count participation" was the key discovery of Nakamoto consensus that seemed to do the impossible. Timestamps count hashes via the difficulty setting and hashes are the sum of all events in all mining nodes for Lamport ordering that all nodes can estimate from how fast blocks are and the difficulty setting. A negative solvetime (non-sequential timestamps) has been used many times in different ways to attack the consensus on coins because it exaggerates the estimate of hashrate. Prior proofs assumed nodes would use agreed-upon start and stop times to measure participation, but Nakamoto consensus does it sort of backwards, using time itself to count participation.
[3] 1982 "The Byzantine Generals Problem", Lamport, Shostak, Pease. p398-399
[4] 1988 "Fault-Tolerant Clock Synchronization" Halpern, Simons, Strong, IBM Research
The text was updated successfully, but these errors were encountered: