October 25, 2016

Untangling Mining Incentives in Bitcoin and ByzCoin

As the first widely-deployed cryptocurrency, Bitcoin has proven hugely successful and inspired a blockchain fever (or is it a bubble?). Bitcoin's security and economic assumptions are showing significant fractures, however. Following previously-identified selfish mining and stubborn mining attacks, new research from Princeton being presented at CCS identifies further incentive weaknesses that appear as transaction fees supplant block rewards as the primary incentive for mining.

In short, miners motivated by transaction fees have even greater incentive to deviate strategically from the standard Bitcoin protocol in selfish and potentially destructive ways. In his summary, Arvind Narayanan notes:

At a deeper level, our results suggest a fundamental rethinking of the role of block rewards in cryptocurrency design.

At least one such “rethinking of the role of block rewards” already exists, however. You may judge for yourself how “fundamental” this rethinking is.

ByzCoin is an experimental protocol created by the Decentralized and Distributed Systems (DEDIS) lab at EPFL and presented at the USENIX Security conference this past summer. While a rigorous incentive analysis has not yet been done on ByzCoin, informal analysis suggests that ByzCoin's architecture may be far more resilient to these known incentive-compatibility weaknesses. In essence, both the new attacks — and the earlier selfish or stubborn mining attacks — appear to be ineffective against ByzCoin. This blog post informally compares the way Bitcoin and ByzCoin handle transaction fee incentives, deferring the topic of selfish mining to a followup post.

Instant Gratification in Bitcoin

In Bitcoin, miners earn immediate rewards for successfully solving the cryptographic puzzles that allow them to extend the blockchain. These rewards are divided into block rewards, in which the miner may create a fixed amount of “new money” according to a hard-coded schedule, and transaction fees, which the miner receives from Bitcoin users as an incentive to include their transactions in the blockchain. As block rewards regularly decrease by half — eventually dropping to zero in the year 2140 — miners' incentives shift from block rewards to transaction fees. For the moment, however, the important point is that Bitcoin confers both block rewards and transaction fees to miners immediately upon the successful mining of a new block. We might describe Bitcoin as an “instant gratification cryptocurrency.”

Note that Bitcoin does impose a 100-block delay before newly-mined block rewards can actually be spent. But this rule does not apply to transaction fees — and even if it did, that would be irrelevant for mining incentive purposes. The critical fact is that the miner immediately knows what his payoff will be for successfully mining a particular block at a particular time, and can use that information to mine strategically, e.g., by selfishly withholding blocks or deliberately forking the blockchain.

Delayed Gratification in ByzCoin

Mining in ByzCoin, in contrast, does not immediately confer any reward on the successful miner, but instead represents an investment whose rewards accrue gradually over a fixed time period, such as the following day or week. In particular, solving a cryptographic puzzle and mining a keyblock in ByzCoin rewards the miner with a temporary share in a consensus group. This consensus group is defined by a sliding window of recently-mined blocks: e.g., the last 1008 blocks, representing one share per keyblock mined within approximately the past week, at Bitcoin's self-adjusting mining rate of 10 minutes per block. Adopting a refinement recently suggested by Pass and Shi, ByzCoin also adds a short delay, e.g., six blocks (about one hour), before a newly-mined keyblock enters the consensus group, ensuring that miners agree on all rather than just “almost all” consensus group members in the presence of temporary keyblock forks.

The consensus group formed this way then uses a scalable Byzantine consensus protocol based on collective signing to agree on and commit to microblocks containing actual transactions. Building on ideas in Eyal and Sirer's Bitcoin-NG, this decoupling enables ByzCoin to commit transaction microblocks much more frequently than keyblocks are mined (e.g., in seconds rather than minutes). Due to its Byzantine consensus, however, ByzCoin subsequently ensures that microblocks are immediately committed permanently and cannot subsequently be reverted or double-spent even in the near future, as is possible in Bitcoin or Bitcoin-NG.

Independent of its Byzantine consensus process, ByzCoin also makes an important change to the way miners earn rewards. Instead of conferring block rewards and transaction fees immediately on the miner of each new block, ByzCoin divides all block rewards and transaction fees evenly among the shareholders comprising the current consensus group. If the consensus group consists of the last 1008 successful keyblock miners, for example, then the transaction fees derived from all transactions committed while this consensus group is in charge — together with the block reward associated with the mining of the next keyblock — are split evenly among the 1008 shareholders comprising the current consensus group.

Thus, while ByzCoin miners earn no rewards immediately upon mining a new keyblock, that keyblock confers on them a 1/1008 share of all the block rewards and transaction fees earned by anyone during the 1008 sliding-window positions during which this share is within the consensus group. In short, ByzCoin gives miners delayed rather than instant gratification. And this characteristic could have important benefits in the stability and security of its mining incentives, as we discuss next.

The Goose Egg Problem

The creator of any Bitcoin transaction defines a transaction fee, which goes to the miner as an incentive to include the transaction in the blockchain. Occasionally — most likely in error — users have proven spectacularly generous with their transaction fees. Transactions with inordinately huge fees are sometimes called goose eggs.

For example, in 2015 a user accidentally donated 111 BTC to a miner, which in this case the lucky miner graciously refunded. This past April a transaction with a 291 BTC fee (worth $139,000 at the time) appeared. But these are only the most spectacular goose eggs: as Arvind Narayanan observed in May, “there have been ~150 transactions with a fee over $1,000.”

For several years, Emin Gün Sirer and others have warned that goose eggs pose an incentive problem to Bitcoin security, in strategic miners may be inclined to “fight over” the goose egg. Suppose for example that a goose egg appears in the transaction pool, and Innocent Ivan is the first miner lucky enough to create a valid Bitcoin block including this transaction. But suppose another miner, Greedy Griffith, is paying attention and controls significant mining power (but still under 1/3 of the total).

Even if Greedy Griffith is well aware of Innocent Ivan's new block, Griffith may be strongly inclined to ignore it and instead try to mine a competing block in hopes of “stealing” the goose egg from Ivan. To pull off this heist, Griffith may have to “get lucky” twice in a row and produce two new blocks before another miner extends Ivan's chain: one block to compete with Ivan's, and a second block to convince other miners to ditch Ivan's chain for Griffith's. Even if this gamble presents fairly long odds for Griffith, the spectacular payoff presented by the goose egg makes it worth the risk.

If multiple miners independently emulate Greedy Griffith, this could lead to chaos and large amounts of wasted hash power as miners clamor over the goose egg. In the worst case, if multiple large mining pools behaved this way, the blockchain could even deadlock or permanently hard-fork as different entrenched pools stubbornly refuse to honor any blockchain other than the one in which they captured the egg.

Consider ByzCoin, in contrast, where mining a keyblock confers no immediate reward, but merely a share in rewards that arrive later while the mined keyblock is part of a consensus group. If a transaction containing a goose egg appears, the one and only way for any miner to profit from it is to divide it equally across the entire consensus group, like dividends paid to shareholders. At this point, it is too late for any greedy keyblock mining strategy to affect this distribution of profits significantly.

To start with, since ByzCoin irreversibly commits transactions every few seconds as part of microblocks, a greedy miner has only seconds, not minutes, to carry out any potential mining strategy — whereas the expected time to mine a new keyblock is still long (e.g., 10 minutes). Second, any profit advantage of such a strategy will be counted only in shares of a goose egg; no single miner ever gets the whole egg. For example, suppose a goose egg appears at about the time Innocent Ivan mines a new keyblock. Greedy Griffith can try to mine against Ivan's keyblock, but this will not change the consensus group that distributes the goose egg, since new keyblocks must “mature” for a time (e.g., six blocks) before they become active shares in any consensus group. Griffith would have to displace not only Ivan's keyblock but several blocks before it to affect the profit distribution at all. Even if he succeeded, Griffith would get only an additional 1/1008th of the goose egg for each additional share acquired strategically.

Transaction Fee Market Incentives

The new incentive analysis by Narayanan's group in essence observes that, as block rewards decrease and transaction fees gradually supplant them as the primary motivation for miners to mine, Bitcoin encounters a miniature goose egg problem at every single block. The problem is that just after any block has been successfully mined, there are few uncommitted transactions available — and hence minimal fees to be collected — for mining a subsequent block. Thus, at least until this pool of uncommitted transactions builds up again, it is more profitable for miners to treat the bundle of ordinary transaction fees in the previous block as a small goose egg and try to capture it by mining against it rather than on top of it.

Further, Narayanan's group identifies “second-order” greedy deviations that work even better when other miners are greedy. For example, if Innocent Ivan has just mined a block that commits transactions worth 10 BTC in fees, Greedy Griffith no longer necessarily needs to mine two blocks in order to steal Ivan's fees; instead Griffith might just mine one block that deliberately “consumes” only a subset of transactions worth 5 BTC of fees, deliberately leaving the other 5 BTC worth of fees as an incentive for other greedy miners to prefer Griffith's chain over Ivan's.

Now consider again how ByzCoin affects this situation. Since transaction fees are divided equally among the current consensus group, whose membership is determined not by the latest keyblock miner but by all the successful miners between an hour and a week ago, any keyblock mining strategy has a minuscule chance of affecting profit distribution significantly. Since ByzCoin commits many transaction microblocks for each mined keyblock, and rewards from all microblocks committed by the consensus group are distributed to the same miners in the same proportion, the precise time a transaction appears has almost no bearing on reward distribution. Strategic keyblock mining might, at best, affect transactions committed close to another keyblock mining event causing a consensus group shift — but any such effect can at most amount to changing the distribution of one share (e.g., 1/1008) worth of transaction fee profits from that microblock.

Conclusion

This post of course represents only an informal and certainly incomplete analysis of differences in incentives between Bitcoin and ByzCoin, focusing specifically on transaction fees. It is quite possible that a full, rigorous analysis of ByzCoin may reveal new incentive-compatibility issues that its architecture introduces. Further, ByzCoin is still an experimental protocol under rapid development and evolution.

Given these caveats, however, ByzCoin's architecture at least appears to be much more resilient to several known strategic mining attacks against Bitcoin, including the new attacks identified by Narayanan's group. By replacing Bitcoin's instant-gratification, winner-take-all reward model with a delayed-gratification, investment-dividend model, ByzCoin ensures that the distribution of mining profits are fixed long before any strategic miner might know about or be able to respond to the appearance of a goose egg or other transaction fee variance.

In short, it does not appear necessary for new cryptocurrencies to “make the block reward permanent and accept monetary inflation as inevitable” as Narayanan suggests. Whether inflationary or deflationary monetary policies are preferable is an important and highly debatable question, but its answer need not be constrained by Bitcoin's technical weaknesses. With more sophisticated blockchain architectures such as ByzCoin, there is plenty of hope that mining incentives can work independent of monetary policy.

---

The author wishes to thank Philipp Jovanovic, Ismail Khoffi, Lefteris Kokoris-Kogias, Arvind Narayanan, and Emin Gün Sirer, for helpful feedback on early drafts of this post.