Tuesday, June 5, 2018

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*109 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 20th 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.
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.


David. said...

@mattblaze sums it up.

David. said...

See also Why a Blockchain-Powered World Is Still a Long Way Away: 11 Blockchain Experts on the Challenges Ahead by Saoirse Kerrigan.

David. said...

Some detailed decentralization numbers from Gencer et al:

"in Bitcoin, the weekly mining power of a single entity has never exceeded 21% of the overall power. In contrast, the top Ethereum miner has never had less than 21% of the mining power. Moreover, the top four Bitcoin miners have more than 53% of the average mining power. On average, 61% of the weekly power was shared by only three Ethereum miners. ... only two Bitcoin and three Ethereum miners ever held the top rank. The same mining pool has been at the top rank for 29% of the time in Bitcoin and 14% of the time in Ethereum. Over 50% of the mining power has exclusively been shared by eight miners in Bitcoin and five miners in Ethereum throughout the observed period. Even 90% of the mining power seems to be controlled by only 16 miners in Bitcoin and only 11 miners in Ethereum. Hence, both platforms rely heavily on very few distinct mining entities to maintain the blockchain."

The authors note that incentives for miners to obscure their activities mean that their measurements may well be under-estimates of centralization:

"For instance, two major mining pools, Ethpool and Ethermine, publicly reveal that they share the same admin [47]. Thus, any analysis based on the voluntary miner data skews toward a more decentralized network than the reality."

David. said...

As usual, Eric Hellman is right:

"It's not that blockchain for libraries couldn't work, it's that blockchain for libraries would be evil. Let me explain. ... I think library technology should not be enabling consensus on the basis of wealth or power rather than thought and discussion. That would be evil."

David. said...

"As I talk to the cryptoadvocates and read their work, I increasingly get the impression that they are not motivated by a rational analysis of the world but rather by an almost religious belief that cryptocurrencies will both change the world and make them really, really rich. Any counterargument threatens that worldview, to be dismissed like fake news. Discussing cryptocurrencies becomes akin to debating religion with the devout.

Cryptoadvocacy is just one form of prosperity gospel." writes John Danielsson (OK, an economist not a cryptographer) in Cryptocurrencies are lousy investments. His analysis of three possible futures for cryptocurrencies is worth reading.

David. said...

"People who purchase the CVL token, a form of cryptocurrency, will have a say concerning the projects hosted by Civil — meaning that they can vote on whether one of its websites violates the company’s journalism standards, which are outlined in the Civil Constitution.

Matthew Iles, the chief executive of Civil, said that by selling ownership stakes to the public, the company seeks to eliminate the possibility of one company or a small group of investors exerting power and influence over a journalistic organization and compromising its mission — exactly what many employees of the Denver Post accused Alden of doing." from Goodbye, Denver Post. Hello, Blockchain by Jaclyn Pelser at the New York Times.

Obviously, these people haven't looked at either the performance of cryptocurrencies since last December (number go up, not so much) or the Gini coefficient of cryptocurrency HODL-ing.

David. said...

"In a withering 24-page article released Sunday as part of its annual economic report, the BIS said Bitcoin and its ilk suffered from “a range of shortcomings” that would prevent cryptocurrencies from ever fulfilling the lofty expectations that prompted an explosion of interest -- and investment -- in the would-be asset class.

The BIS, an 88-year-old institution in Basel, Switzerland, that serves as a central bank for other central banks, said cryptocurrencies are too unstable, consume too much electricity, and are subject to too much manipulation and fraud to ever serve as bona fide mediums of exchange in the global economy. It cited the decentralized nature of cryptocurrencies -- Bitcoin and its imitators are created, transacted, and accounted for on a distributed network of computers -- as a fundamental flaw rather than a key strength." from Bitcoin Could Break the Internet, Central Bank Overseer Says by Edward Robinson at Bloomberg.

The BIS report is well worth reading.

David. said...

The Economic Limits Of Bitcoin And The Blockchain by Eric Budish is an important analysis of the economics of two kinds of attack on Bitcoin and other cryptocurrencies:

- A "51% attack", such as those on Bitcoin Gold and other alt-coins. Providing an economic disincentive requires limiting the rate at which value is transacted.

- A "sabotage" attack, in which short-sellers discredit the cryptocurrency. Preventing this requires conditions in the market for mining ASICs, and in the cryptocurrency market, which seem unlikely to persist.

I hope to review this paper in a full post shortly.

David. said...

"Security researchers have found, on average, five security flaws in each cryptocurrency ICO (Initial Coin Offering) held last year. Only one ICO held in 2017 did not contain any critical flaws.

According to Positive.com, a security firm specialized in ICO security audits, most of the vulnerabilities they found, they discovered in the smart contracts at the base of the ICO itself."


"Researchers also say that all the mobile apps ICO organizers have launched in 2017 contained security flaws. The good news is that not all ICO organizers have released mobile apps, but those who did, did not invest in securing it against attacks.

The Positive.com team says it identified more vulnerabilities in ICO mobile apps than in ICO official web applications.

Experts say the most common flaws in mobile apps are the use of insecure data transfer methods, storage of user data in phone backups, and disclosure of session IDs that an attacker could capture and use against the user."

From Catalin Cimpanu's Researchers: Last Year’s ICOs Had Five Security Vulnerabilities on Average. Note also:

"A previous study also found that 81% of recent ICOs were scams, which might explain why most ICO organizers didn't bother with security."

David. said...

'[Special Agent in Charge Angel] Melendez emphasized that the open nature of the blockchain made it difficult to hide drug money. “The biggest selling point for the blockchain is that it’s transparent. Everybody can see it. And we can see it, too.”' Melendez was announcing that:

"More than 40 alleged dark-web drug dealers have been arrested as part of a sweeping federal effort described by the Department of Justice as “the first nationwide undercover operation targeting dark net vendors.” The core of the operation was an online money-laundering business seized by agents from Homeland Security Investigations and operated as a sting for over a year. By offering cash for bitcoin, HSI agents were able to identify specific drug dealers, ultimately tracing more than $20 million in drug-linked cryptocurrency transactions."

The privacy of Bitcoin's blockchain isn't as good as dark web businesses would like to think, especially because you can't buy your Lamborghini or pretty much anything else with Bitcoin. You need "fiat currency" and the act of conversion is really had to anonymize.

David. said...

"Bancor, which lost $23.5 million in tokens on Monday — $12.5 million ETH, $1 million Pundi X (NPXS) and $10 million Bancor Network Tokens (BNT). They’d left administrative backdoors in the smart contract, and the thieves used those" reports David Gerard.

Udi Wertheimer wrote about the "administrative backdoors" a week after Bancor raised ~$150M:

"I took some time to read many of the materials published by Bancor, including its smart contract code. I was absolutely astonished by some of the things I found, including what I consider dangerous backdoors.

In this report, I will detail my findings, including the team’s ability to take anyone’s tokens arbitrarily."

Because Bancor inserted "adminstrative backdoors" that gave them complete control over the "smart contract", they have the following capabilities:

All transactions using the BNT token can be disabled by the team at any time for any reason

The team can issue new tokens at any time

the team can DESTROY any tokens FROM ANY ACCOUNT, at any time

And, it now turns out:

the ability to replace contract logic arbitrarily, and the ability to withdraw ETH from the contract.

That's some serious centralization.

David. said...

Not a cryptographer, but an (Nobel prize winning) economist. In Transaction Costs and Tethers: Why I’m a Crypto Skeptic Paul Krugman is as skeptical of cryptocurrencies as the cryptographers. His graph, showing that the stock of $20 and smaller bills has been a small but steadily falling fraction of US GDP, whereas the stock of $50s and $100s has been rapidly rising and is now much larger is fascinating. As he points out, these bills, like BTC, aren't really used for legal transactions, and are mainly a store of value in the underground economy. They're just much more stable and liquid than BTC.