Mining on Top of Unknown Block: A new protocol weakness

[King Lear]

I have recently discovered a weakness of the way Proof of Work is currently implemented in Bitcoin. In this post I show how a miner can mine a valid block without knowing on top of which previous block he/she mines, and without even knowing the hash of the previous block. Then I explain the consequence of this weakness on the real world possibility of  51% attack and selfish mining / block discarding attacks. Simple protocol modifications are proposed and discussed at the end of the post.

Mining without knowing the hash of the previous block
We are all familiar with the proof of work (PoW) concept, and we all know that a certain hash of the block-header of any valid Bitcoin block must be lower than the corresponding target, yet the specific technical implementation of PoW is less discussed. All details can be found in the wiki or in this recent interesting paper.

For simplicity let's say that the block-header is the concatenation of the previous block's hash, root of the current block's merkle tree, and a 32bit short nonce, in this order. Note that the first two fields are of 256 bits each. In reality the block header contains also a timestamp and other data we shall ignore in order to make the weakness clearer. The SHA-256 hash function is applied twice over the block header (meaning, first SHA-256 is calculated over the header and then SHA-256 is calculated over the outcome of the previous calculation), and the result should be lower than the target.

Since the current difficulty is higher than 60 bits and the short nonce contains only 32 bits, once every 2^32 double-SHA-256 calculations the Merkle-tree must be changed in order to refresh the block-header (in fact, the coin-base transaction of the tree contains some extra-nonce as a special field). Moreover, pool miners are used to modify the coin-base transaction of the Merkle-tree not only for block-header refreshing, but also in order to mark the block so that the pool owner can reward them for their shares.

Let's say that the pool organizer sends all pool members (different) lists of merkle-tree roots. Each pool miner then try all 2^32 possible combinations for the short nonce, before taking another root and start all over again. The miner doesn’t need to know the actual merkel-tree, because the pool organizer has already marked it for him/her. Now here is the key point: SHA-256 is a Merkle-Damgard hash function that iteratively compresses 512 bits blocks of the input data. So the first step of calculating SHA-256 over the block-header is compressing the first 512 bits, which are the concatenation of the previous block's hash with the Merkle tree root. After this step those 512 bits are unneeded, hence the pool organizer may just send the pool miners a list of compressed concatenations of the previous block's hash with some Merkle tree root.

Since the compression function of SHA-256 is one-way and the Merkle-tree roots are effectively random numbers, the pool miners cannot discover the hash of the previous block. In other words, they are mining valid blocks without knowing on top of which previous blocks they mine.

Implications
Recently Eyal and Sirer published a paper describing the "selfish mining" attack. Unfortunately I was independently working on the same attack, but they have published their results first (and refused to share the credit with me…). Anyway, I have published my results too and since the Block Discarding Attack is more general and comprehensive I advise you to read my paper too.

I have claimed that the Block Discarding Attack / Selfish Mining is not applicable to pools, and have just changed my mind about that due to the possibility of mining without knowing the previous block's hash. Assuming pool miners must know the previous block's hash, it can be shown that in practice the selfish mining attack cannot work properly if the attacker is a pool:  the attack is based on two contradicting requirements. The first is the ability of pool miners to keep in secret blocks they have found but have not released yet (the pool miners will mine on top of this secret blocks while the honest network mines on older blocks). The second is the acceptance of new miners to the pool (who want to join the pool so they will not suffer from reduced profits due to the attack).

Because anyone can join the pool, including other pools organizers or sites like blockchain.info (note that miners are anonymous), and because pool miners are expected to mine on top of the secret block (whenever there is such a block), assuming that mining can only be done when the previous block hash is known, the hash of any withholded block is expected to be published by some of the pool unfaithful miners. When this hash is published, non-pool miners can also mine on top of it, making the attack impossible (Asaf Ziv, a friend of mine, have noted that in such a situation the pool organizer can choose not to reveal the full block whose hash have been published. However by doing so the pool loses a single block and the honest network loses only a single block too, so this is unprofitable unless the pool has more than half of the total computational power).

Anyway, a pool can use the technique presented here so that unfaithful pool miners will not be able to publish the secret block (or its hash). The only thing they can do is to publish the compressed concatenations of the secret block's hash with a Merkle tree root whose coin-base transaction rewards the pool organizer 25 Bitcoins. Obviously, this cannot harm the pool.

As for the 51% attack, a group of pool organizers whose total hash-power exceeds the hash-power of the rest of the network can use the describe technique to anonymously perform 51% attack, without being affiliated with the attack not even by pool miners! The pool organizer can use new address in the (initially secret) coin-base transactions, so that whenever a valid block is mined by one of the pool miners, only this miner is expected to know that the pool participates in the attack. Because I don’t know of any honest advantage of this technique, my observation about the 51% attack is probably insignificant: honest pools, or pools that pretend to be honest, will simply not use this technique, and thus no honest pool miner will be tricked to participate in any attack.

Protocol modification
The Bitcoin protocol can be slightly modify so that mining without knowing the previous block's hash (and may be the Merkle tree root too) will not be enabled. There are many possibly ways to do so, of which the most simple is probably reversing the order of the block-header's fields so that the nonce becomes first. Other possibilities include: concatenating the block-header to itself and computing a single SHA-256 over the doubled block-header; Xoring the previous block's hash to the outcome of the first SHA-256 iteration before doing the second SHA-256 iteration; requiring that the outcome of the second SHA-256 iteration will be a number bigger than 2^-128 times the previous block's hash and smaller than 2^-128 times the previous block's hash plus the current target; etc.

Along with the weakness of mining without knowing the previous block's hash, there is another weakness, which is the possibility of non-trivial mining optimizations, i.e. the existence of better mining algorithms than simply calculating the regular SHA-256 function. One such optimization is described here. When I have the time, I intend to look for optimization of mining multiple blocks on top of the same block, for example mining two blocks on top of the same block so that it will only take 1.5 times more calculations than mining a single block (this might have bad implications over the GHOST proposal).

I think the current protocol should be changed in the near future, so that it will have no weakness due to the specific use of SHA-256.


Lear.
 

[gmaxwell]

I think the current protocol should be changed in the near future, so that it will have no weakness due to the specific use of SHA-256.

You'd propose a risky change that moots millions of dollars of deployed hardware to address a theoretical implementation of a theoretical weakness?

...A implementation which requires hashers to voluntarily sign up for using services which hide extra data from them? That that an attacker wants to hide because it doesn't want hashers to know that they're beginning to perform the aforementioned theoretical attack (which can't really be hidden once its actually happening actively, as miners will see their solutions being delayed and the network will see orphans). ... and yet hashers are somehow not going to be smart enough to realize that anyone asking them to switch software/firmware is doing so because they want to perform that attack?

Existing mining software (BFGMiner) already validates the sanity of prevblocks in requested work, e.g. validates that a pool isn't asking the miner to fork its own past work. I don't think there is any risk of anyone sneaking this in on anyone.

[King Lear]

Hi gmaxwell,

I agree with you that the threat of the 51% attack is not much increased by this weakness, yet the vulnerability to selfish mining is: say there are bad miners whose total hash-power is only 30% of the total network's hash-power. Despite the selfish mining attack being profitable to an attacker having 30% of the total network's hash-power, it is not trivial to actually perform this attack. If one of the bad miners is a traitor (i.e. a good miner), this miner can discretely publish all the blocks that the pool wants to keep secret, and thus preventing the attack – unless the pool miners just don’t know the previous (secret) block. The bad miners will have no problem mining on top of unknown blocks, as long as they receive their (increased…) rewards. So this is not a pure theoretic attack. Yet I agree with you that this is not an immediate threat.

As for the ASICs:  the Bitcoin dedicated hardware can compute SHA-256 really fast. As long as we continue to use the SHA-256 compression function, there is no need to switch to a new hardware – just to modify the program of the ASIC machines. Consider for example my proposal of requiring that the outcome will be close to the (upper 128 bits of the) previous block's hash rather than being close to zero.  

Lear.

[timewave0]

As for the ASICs:  the Bitcoin dedicated hardware can compute SHA-256 really fast. As long as we continue to use the SHA-256 compression function, there is no need to switch to a new hardware – just to modify the program of the ASIC machines. Consider for example my proposal of requiring that the outcome will be close to the (upper 128 bits of the) previous block's hash rather than being close to zero.  

Not necessarily. There are certain optimizations made possible by the current structure of the block header.

[TierNolan]

Not necessarily. There are certain optimizations made possible by the current structure of the block header.

ASICs don't compute SHA256 anyway.  They compute a vast number is parallel without any flexibility at all.

If the header was changed (say to move the nonce), then ASICs would be useless.  They might be able to handle a change in the size of the header (up to around 120-127 bytes), but the nonce must be in the correct position.  Otherwise, the ASIC wouldn't be set up to increment it properly.

[coinrevo]

I think the current protocol should be changed in the near future

Ahem. Sure. There are so many flaws in all of these "papers" its not even funny. Just two examples:

The integral diverges to infinity, so if the attacker continues with the strategy long enough, eventually she will win and be able to double spend

The point is: attacking costs money, as electricity spend is not rewarded by mining. That is the major reason an attack is so extremely unlikely. The reward is connected to establishing the hashing power. After that investment, compared to that reward of a double spend is extremely small.

"Although not very likely, it is absolutely p ossible that some government oended by the dark market uses of Bitcoins decides to launch a DoS attack against the system"

You obviously don't know what a DoS attack is, and how this relates to P2P. Hint: there is no DoS in P2P.

[acoindr]

There is a problem with Selfish Mining I haven't seen addressed: incentive.

It's strange to me Cornell University researchers would publish a paper proposing profitable incentive to act "selfishly" and immediately predict the demise of Bitcoin. Why would a selfish miner execute a profit seeking attack knowing a successful attack could decrease the value of all held coins?

Recently Ghash.io went from near 51% of network hashing to under 30% in less than 48 hours as community reaction set in.

The design of Bitcoin and its future success was never guaranteed. The reason for optimism is it solves an important enough problem that whatever challenges arise resourceful people will put in the effort necessary to find a solution. As Bitcoin approaches global saturation 51% attacks or even 30% ones become exceedingly unlikely.

[coinrevo]

yeah, it takes a kind of audacity or stupidity to make such claims. basically academics don't learn to validate their ideas, especially mathematicians, have a strong tendency to invent their own problems which don't exist. if you like at the authors work - they do interesting stuff, but for them it was probably a few months work. with that kind of background you will likely miss a many subtle points. And they say they want to change protocol, but not have written a single line of code. If they would be so sure about themselves, they would want implement to it. there is a reason cryptocurrencies were completely non-existent as an academic field.

http://www.cs.cornell.edu/people/egs/

[King Lear]

I believe a system should by secure by-design and not by anything else. It is true that a system may have some weaknesses and yet practically be quite safe, but this is not preferable. Fortunately for most of the problems we do have simple solutions, and as long as a solution causes no further problem I think it should be implemented.
 
If it was the case that there is not possible secure modification of the PoW structure which is suitable to current ASICs, then maybe we better put with the weakness (there are other ways to counter block discarding attacks, such as my "fork punishment" proposal). As far as I'm concerned, Bitcoin ASICs' designs are not open source so neither me and you can know for sure whether a concrete modification is applicable or not. Yet I think that ASIC machine has a unique set of op-codes (such as SHA-256 compression function) and can be programed to run different codes. Do you know that Sony Playstation machines have been used to run cryptanalysis programs? Dedicated hardware can be very flexible!
 
I have no intention to argue about off-topic issues that have been thoroughly discussed in other threads, yet I will just note that there is an incentive for selfish mining: increased mining profits. Such an attack will most probably not cause the total destruction of the system (it will just cause some honest miners to earn less, and the dev team to implement proposals like mine's). Moreover, I don’t think we should make any assumptions about the attacker intentions and incentives: the attacker may theoretically want to harm the system (say if it is a terror organization, the Chinese government, or more likely the NSA).

I will say it again: a system should be secure by design and not by anything else!

One last thing: it is OK to criticize academy, just please remember that Bitcoin is built upon cryptographic elements that were all invented by the academy. We don’t know who Nakamoto is, but I am quite sure he is an academician. Nevertheless I absolutely agree with you that academicians should not say "Bitcoin is broken" whenever a new weakness have been found.

Lear
 

[gmaxwell]

Secure by design is great and necessary.

But I don't believe what you've suggested actually advances that.  You're trying to close off an avenue for hiding data which only exists if an unjustified and obtrusive form of conspicuous data hiding is already used.  I think this is pointless and does not contribute to security in any meaningful way.

Moreover, Bitcoin mining asics are not some hypothetical. They exist and we know how flexible they are and are not. What you suggested is not compatible.

[acoindr]

I believe a system should by secure by-design and not by anything else.

If that's possible I completely agree.

If it was the case that there is not possible secure modification of the PoW structure which is suitable to current ASICs, then maybe we better put with the weakness ...

Unfortunately suitable course of action isn't necessarily a black and white call. If we were in a lab under controlled conditions then of course we could use pure logic for system optimization. This is not the case. Bitcoin is made up of independent actors all of which to some degree influence the whole. It's similar to how economics as a science is the one field where experts can agree upon a set of data yet come up with opposing views.

With Bitcoin protocol changes therefore can't ever be taken lightly. The larger the system grows the more difficult it is to come to consensus on any change. At some point I imagine it becomes impossible (one reason I believe alt-coins have a role). So I'm very glad people like you are raising these ideas sooner than later.

Bitcoin as money relies on shared confidence in its value. Confidence in Bitcoin's value naturally rests upon many things including the viability of the system, which includes withstanding attacks. It's unclear what would be the result of a pushed for yet unsuccessful protocol change. That's why we need to be careful about what things are viewed as critical.

(there are other ways to counter block discarding attacks, such as my "fork punishment" proposal).

While I agree with many of your conclusions I'm not yet sold on the fork punishment countermeasure.

I have no intention to argue about off-topic issues that have been thoroughly discussed in other threads, yet I will just note that there is an incentive for selfish mining: increased mining profits. Such an attack will most probably not cause the total destruction of the system ...

Even you yourself say "probably" not cause the total destruction of the system. Nobody can say what the effect would be. Something less than completely healthy seems assured, and that in all likelihood means lower value for coins.
 

Moreover, I don’t think we should make any assumptions about the attacker intentions and incentives: the attacker may theoretically want to harm the system (say if it is a terror organization, the Chinese government, or more likely the NSA).

But that matters in practice. The security of the system relies on the assumption an attacker's resources will be low compared to the honest network. There are real costs (including other than financial) to prepare and execute the attack. If an attacker can't use pooled resources from the network their challenge is great. Governments might be the only viable candidate but governments are subject to political repercussion. Any attacker building out the server farms, power centers, etc. would probably not go undetected.

[coinrevo]

I'm really trying to understand at least some of the logic of this, but it might as well be written in Chinese.

Because anyone can join the pool, including other pools organizers

you're saying pools don't know each other??

in the other thread

2.   The attack is based on secretly holding new mined blocks while trying to mine the next block on top of a secret one.

the problem is that the attacker is running the risk of falling behind. you can't outpace the network. this is again a problem of coordination and about the fundamental algorithm. otherwise you would always have competing nodes going many blocks back. if this was even a possibility then the network would not function. because every pool would have figured this out long ago, because it seems trivial. don't you think people making millions of dollars and working on it full time would have thought of same basic techniques to make even more money? we are talking about people running the worlds largest super computer, who now build hardware surpassing Intel. not exactly stupid people. the basic argument against all attacks (although not 100% assuring): if there would be any such possibility it would have happened a long time ago. most well known cryptographers must have looked in this early on and when it took off in 2010/2011. also its probably too late for NSA to destroy the network. that is really the only entity I can think off who has the resources and possible intent.

[Altoidnerd]

There is a problem with Selfish Mining I haven't seen addressed: incentive.

It's strange to me Cornell University researchers would publish a paper proposing profitable incentive to act "selfishly" and immediately predict the demise of Bitcoin. Why would a selfish miner execute a profit seeking attack knowing a successful attack could decrease the value of all held coins?

I've considered the same problem.  Their selfish mining concept is correct; the unfortunately took the argument in the wrong direction by insisting this means all miners join the selfish pool bringing about the demise of bitcoin.

They failed to examine the consequences of competing selfish pools.  This was the first thing I thought of when I read the paper, but the authors didn't examine that case, which I find more likely - multiple disjoint pools delaying transmissions (to be selfish).

[acoindr]

They failed to examine the consequences of competing selfish pools.

Well selfish mining only starts to make much sense at around 1/3 of the network's hashing power. That means you could only have 3 competing pools behave that way where it might make sense for them. The assumption is miners would gravitate to whatever pool amassed an advantage in order to make the most profit on the winning most team, with the process leading to one pool having a large majority.

This idea is okay on paper but not I feel in practice. It's for the same reason pools have, in reality, made decisions not for their immediate bottom line, but for the longer term implications for the network. We see this with pools who have somehow fallen shy of 51% hashing; we see it with pools on the wrong side of the version 8 fork ditching their blocks.

Bitcoin is strongest and more importantly most valuable when all its participants act in a manner which supports a viable healthy system. That's at direct odds with the reasoning given for expecting selfish mining.