Cryptographers on Blockchains: Part 2 (updated)

Back in April I wrote Cryptographers on Blockchains; they weren't enthusiastic. It is time for some more of the same, so follow me below the fold.

Radia Perlman

Besides being a fellow Distinguished Engineer at Sun Microsystems, Radia Perlman is an ACM Fellow, a member of the Internet Hall of Fame, and a recipient of the USENIX Lifetime Achievement Award. A year ago I commented briefly on her Blockchain: Hype or Hope? when it first appeared in the print edition of Usenix ;login:. Now it is freely available online a more detailed look is timely.

After a detailed but clear description of how the Bitcoin blockchain works she poses four questions asking what is innovative about it:

• Is It Having a “Ledger”? Perlman writes:
  

  Blockchain’s “ledger” is an append-only log that needs to be kept in its entirety, and needs to be world-readable and world-writable. Very few applications really want these properties. Much more flexible databases have of course existed for a long time

• 

  Bitcoin Blockchain Size

  Is It Replicating the Data? Each miner in a blockchain needs access to the entire chain; successful blockchain applications like Bitcoin observe the Lots Of Copies Keep Stuff Safe principle. But they go way beyond the point of diminishing returns, and each copy is quite big (currently over 150GB and growing rapidly), so the current Bitcoin implementation is both unsustainable and incapable of scaling to compete with Visa and Mastercard (see If we lived in a Bitcoin future, how big would the blockchain have to be? by Subhan Nadeem).
  
  There are estimated to be 577*10⁹ non-cash transactions in 2018. At 250 bytes per basic transaction, 2018 would add around 144TB to the blockchain size. There are currently about 10K reachable Bitcoin nodes (I'll ignore the perhaps fifteen times as many unreachable nodes). Assuming each reachable node has a copy, 2018 would consume about 1500 EB of new storage. Unfortunately, in 2017 the world only built about half that amount of disk. Replication isn't innovative, and the blockchain's way of doing it isn't scalable.
  
  
• Is It Being “Immutable”? Perlman writes:
  

  The term immutable means the data cannot be modified. The term “immutable ledger” isn’t quite true. The data can certainly be modified, but the assumption is that there is an integrity check that can be used to detect whether the data has been modified. Blockchain did not invent the concept of an integrity check, just the concept of a horrendously expensive-to-compute integrity check. Traditional cryptography has long known about easy-to-compute integrity checks that are computationally infeasible to forge.

  In any case, immutability renders the technology unsuited to most real-life applications, for example anything storing personally identifiable information under GDPR, anything to which unauthenticated users can upload illegal content such as child porn, or indeed routine financial transactions. Fortunately, as Perlman points out, in practice blockchains are not immutable:
  

  Forks can occur, starting from, say, block N, where multiple different subsequent blocks N+1 and further might be found. The hope is that this situation would be resolved quickly, because a miner seeing two different valid chains will only accept the longer one. However, a fork can persist for a long time if there were an Internet partition, or if the gossip network connecting the miners got partitioned, due to some highly connected node going down, perhaps. Also, if there were any incompatibility in code, such that a transaction looked valid in one version of the code and invalid in a different version, then the miners running different versions will ignore each other’s chains. This situation actually occurred in 2013. If blockchain were truly decentralized, then this situation would be permanent. However, there are a few people who really are paying attention and in charge, and after the fork in 2013, they decided which version of the blockchain should live.

  
  
• Is It Being Decentralized? The example above, and the graphs of mining pool power, show that Bitcoin hasn't actually been decentralized since at least 2013. There are two fundamental problems with decentralized systems. Firstly, as I've been pointing out for nearly four years, Economies of Scale in Peer-to-Peer Systems mean that they can be decentralized or successful, but not both. Secondly, as Vitalik Buterin (a co-founder of Ethereum), writes in The Meaning of Decentralization:
  

  In the case of blockchain protocols, the mathematical and economic reasoning behind the safety of the consensus often relies crucially on the uncoordinated choice model, or the assumption that the game consists of many small actors that make decisions independently. If any one actor gets more than 1/3 of the mining power in a proof of work system, they can gain outsized profits by selfish-mining. However, can we really say that the uncoordinated choice model is realistic when 90% of the Bitcoin network’s mining power is well-coordinated enough to show up together at the same conference?

  The security of a blockchain depends upon an assumption that is impossible to verify in the real world (and by Murphy's Law is therefore false). Fortunately, in the real world there is a much simpler solution. Perlman writes:
  

  Blockchain is an append-only log. If all that were needed was an append-only log, and an application (e.g., a consortium of banks) wished to collaborate on maintaining the log, a very simple solution would be to have an entry signed by any of the trusted parties in the consortium appended to the log. To handle Byzantine failures (where a minority of the entities in the consortium might become untrustworthy), the simple solution would be to require an entry to be signed by a majority of the consortium before it is appended to the log. So the novel part of Blockchain is having a consortium of unknown entities maintain the ledger.

  Trusting that the majority of a set of unknown entities are not colluding is a pretty shaky basis for any system.

Nicholas Weaver

On April 20^th Nicholas Weaver of ICSI and UC Berkeley gave a talk in the I-school entitled Blockchains and Cryptocurrencies: Burn It With Fire (start at 3:00). It is well worth watching. One comment I particularly liked was:

The interesting problem with Ponzi schemes and with bubbles is the first winners become cheerleaders and they kind of propel the bubble.

Weaver contributed Risks of Cryptocurrencies to Peter Neumann's Risks column in this month's Communications of the ACM. It covers much of the same ground in a more formal way. After explaining the fundamental problems involved in using an irreversible, highly volatile, and fundamentally deflationary "currency" for payments, he identifies four classes of risk posed by cryptocurrencies:

• Individual Technical Risks: Weaver identifies two of them, malware and bugs. For malware, he uses the theft of their honeypot's Bitcoin:
  

  If security experts can’t safely keep cryptocurrencies on an Internet-connected computer, nobody can. If Bitcoin is the “Internet of money,” what does it say that it cannot be safely stored on an Internet connected computer?

  For bugs, his examples are the DAO heist, and the Parity Wallet fiasco, both resulting from code written by experts in the field.
  
  
• Individual Economic Risks: Weaver discusses a range of fraudulent activity, such as ICOs and Ponzi schemes, trading on the gullibility of cryptocurrency enthusiasts:
  

  Even explicitly advertised Ponzi schemes see significant activity, such as the “Proof of Weak Hands’, a Ponzi scheme implemented as an Ethereum smart contract. More than $1 million in notional value flowed into the scheme in the space of a few hours before the flow stabilized. Two days later, one bug froze the scheme (making withdraws impossible) before a second bug enabled a thief to take all the value.

• Systemic Risks: Weaver's list of risks posed to the whole cryptocurrency systems is:
  

  The entire cryptocurrency environment also faces systemic risks including worms, exchanges, central authorities, and government intervention.

  Worms can propagate through vulnerabilities in P2P systems very rapidly, exchanges routinely lose customer's funds and manipulate the market, central authorities such as the core developers routinely fork their chains to "fix bugs", and governments don't appear yet to have effectively used their regulatory or technical capabilities such as:
  

  The limited transaction capability can be exploited by a government purchasing a quantity of Bitcoin, and then creating useless transactions. The goal of such a spam campaign would not be simply to clog the network, but also to generate responding spam filters. As the spam campaign continues, the goal becomes to tune the spam so that the filters cause false positives. How can a cryptocurrency work if a non-trivial fraction of legitimate transactions are blocked by spam filters?

  That's an interesting question but it is important to observe that competition for the limited number of transactions per block means that, even without false positives in transaction spam filters, transactions can be delayed for long periods or even fail to be confirmed.
  
  
• Risks to Society: Weaver focuses on the risk that an anonymous cryptocurrency that was an effective means of exchange would greatly increase the bandwidth of crime:
  

  The only reason why the online drug markets remained small (approximately $1M a day in sales despite existing for half a decade) is that Bitcoin and the other cryptocurrencies are like the classic corrupt poker game; yes, it’s rigged, but it’s the only game in town. A cryptocurrency that actually offered both real anonymity and acted as a store of value (eliminating the need to constantly shift between dollars) would see an explosion in this market.
  
  But such uses would not be limited to criminal-to-criminal transactions but would also act as a vehicle for extortion. The first ransomware epidemic a few years ago offered a choice to victims, either Green Dot or Bitcoin, with almost every victim using the much easier Green Dot, ... How much greater would the current ransomware epidemic be if it was easy for victims to pay? How much other criminal extortion would target ordinary citizens?

Daniel Genkin et al

The same issue of CACM carries Privacy in Decentralized Cryptocurrencies by Daniel Genkin, Dimitrios Papadopoulos and Charalampos Papamanthou. They have definitely drunk the blockchain KoolAid, because they start by making two (parenthesized) claims that are false:

Apart from its other benefits (decentralized architecture, small transaction fees, among others), Bitcoin's design attempts to provide some level of "pseudonymity" by not directly publishing the identities of the participating parities.

BTC "market cap"

When people see graphs showing a "market cap" of $323B it is natural to assume that the underlying technology is a "success" and that it got to be a "success" by delivering on its promised "benefits". But Bitcoin has delivered on precisely none of the goals that Nakamoto set for it. In practice, it isn't trustless, it isn't a medium of exchange, it isn't secure, it isn't anonymous, it isn't decentralized and the transaction fees make micropayments impossible. Lets look at Genkin et al's "other benefits".

First, "decentralized architecture" would only be a benefit if the implementation of the architecture was actually decentralized. None of the actual major cryptocurrencies can claim to be decentralized; Bitcoin hasn't been in the past 5 years. As David Vorick wrote a year ago in Choosing ASICs for Sia:

Ultimately you only need about 5 mining pools to get 51% of the hashrate in Bitcoin, and 10 to hit 75%. ... The story is actually a bit worse in Ethereum — 3 pools control more than 60% of the hashrate, and 6 pools will get you over 85%.

Note that the security of these blockchains rests on the unverifiable assumption that these pools are not secretly collaborating. David Gerard points to this table of the cost of a 1-hour 51% attack on a range of cryptocurrencies. Note that only Bitcoin and Ethereum among cryptocurrencies with "market cap" over $100M would cost more than $100K to attack. The total "market cap" of these 8 currencies is $271.71B and the total cost to 51% attack them all is $1.277M or 0.000047% of their market cap.

Median transaction fee

Second, "small transaction fees" are only small at times when few people want to transact. From August 2017 through February 2018 the median fee was never less than $0.70. From mid-December through mid-February, when many people wanted to transact, the median fee was never less than $10 and peaked over $30.

Average cost per Transaction

But even that isn't the real cost to transact. Miners are rewarded for mining a block of transactions with newly minted Bitcoin. These newly minted coins dilute the value of the existing coins, and this dilution must be amortized over the transactions in the block. Thus the average real cost of a transaction is the miner's revenue (reward plus fees) divided by the number of transactions. This graph shows that this hasn't been less than $50 since mid-November, and it peaked at $162. These are not "small transaction fees".

Despite the KoolAid, Genkin et al provide a clear description of the privacy problems of the Bitcoin protocol, including the ability to analyze the transaction graph to link payment addresses, the connection between payment addresses and IP addresses:

most Bitcoin client implementations can be configured to run over an anonymous Tor proxy, hiding the participants' [IP] addresses. Unlike what one might expect, this approach does not solve the problem. Subsequent work has demonstrated how the interaction between Bitcoin and Tor can be exploited by an adversary who not only compromises user privacy (negating the anonymizing effect of the latter) but can also launch a stealthy man-in-the-middle attack, targeting the security of the Bitcoin protocol itself.

and:

We stress the gap between anonymity as a property of the cryptocurrency protocol execution and "real-world anonymity." For example, when one uses a cryptocurrency to purchase goods or services from a vendor they must provide the latter with certain personal information (identity for registration, physical address for delivery, email for purchase confirmation, and so on). Thus, the vendor can trivially link the public key with its owner, in a strong sense. Moreover, this information may be extracted by others (for example, in case the vendor is hacked or a government agency issues a subpoena). Combined with "Know-your-Customer" anti-money laundering policies that enforce the collection of such data (like the one included in the USA Patriot Act of 2001) this can seriously compromise the privacy of cryptocurrency users.

They go on to describe the two approaches to improving privacy, mixing and alternative crytocurrencies. The descriptions are useful but in both cases effective privacy involves one or both of assumptions that are impossible to verify in the real world, and/or cryptographic protocols so complex as to be unlikely to be implemented or executed perfectly. They conclude:

We believe our exposition so far indicates there is no general consensus regarding a technique for anonymous cryptocurrencies.

and identify four open problems:

• "there is no de facto unified privacy definition that would allow a fair comparison of different proposals"
• "cryptocurrencies that achieve the strong anonymity levels of Zerocash but without the need for a sensitive trusted setup phase and without relying on the non- falsifiable cryptographic assumptions inherent to zk-SNARKs"
• "scalability; for any privacy solution to be widely used in practice, it must not only protect the users' anonymity but also be able to scale to realistic numbers of users and transactions."
• "increased user privacy may raise concerns, such as users participating in illegal activities or facilitating various cryptographic ransomware."

So even those cryptocurrency enthusiasts who understand the details can only work up much enthusiasm for cryptocurrency privacy if it is treated as an unsolved research problem.

Update: Adem Efe Gencer et al

In Decentralization in Bitcoin and Ethereum Adem Efe Gencer, Soumya Basu, Ittay Eyal, Robbert van Renesse, and Emin Gün Sirer actually measure decentralization:

Blockchain-based cryptocurrencies have demonstrated how to securely implement traditionally centralized systems, such as currencies, in a decentralized fashion. However, there have been few measurement studies on the level of decentralization they achieve in practice. We present a measurement study on various decentralization metrics of two of the leading cryptocurrencies with the largest market capitalization and user base, Bitcoin and Ethereum.

They summarize the paper on the Hacking, Distributed blog. A key point is:

Both Bitcoin and Ethereum mining are very centralized, with the top four miners in Bitcoin and the top three miners in Ethereum controlling more than 50% of the hash rate.

The entire blockchain for both systems is determined by fewer than 20 mining entities [4]. While traditional Byzantine quorum systems operate in a different model than Bitcoin and Ethereum, a Byzantine quorum system with 20 nodes would be more decentralized than Bitcoin or Ethereum with significantly fewer resource costs. Of course, the design of a quorum protocol that provides open participation, while fairly selecting 20 nodes to sequence transactions, is non-trivial.

The last comment relates to work we published nearly 15 years ago. Note [4] makes an important point:

Of course, some of these entities are pools. And some people will claim that pools provide decentralization, because they are composed of multiple independent actors. This argument is incorrect for a few reasons: (1) we retrospectively examine the historical record, and at the time of that particular block's commitment to the blockchain, there was a de facto, undeniable agreement among the pool members to act in unison, now recorded on the blockchain, (2) perhaps the pool members would leave if the pool engaged in activities that damage the currency, but this has historically not happened, to the point where a pool exceeded 51% of the hash power, (3) even if pool members were motivated to leave their pool in the presence of unwanted behaviors (e.g. selective transaction censorship by the pool), their ability to do so depends on their ability to detect these behaviors, and most participants are not geared to detect them in the first place. In short, pools providing any level of decentralized decision making is more aspirational talk than a proven reality.

They don't point out that it is impossible to know whether the top four Bitcoin pools or the top three Ethereum pools are covertly colluding.