Thursday, April 25, 2019

Short talk at Asilomar Microcomputer Workshop

I gave a revised version of Blockchain: What's Not To Like? in the 2019 Asilomar Microcomputer Workshop's Athematic session. Below the fold, the text of the talk with links to the sources. Readers should also consult the "Additional Material" in the original talk, the video of my original presentation, and the podcast interview.

It’s one of these things that if people say it often enough it starts to sound like something that could work,
Sadhbh McCarthy

I'm sure you've all read the supernova of hype surrounding cryptocurrencies and blockchain, the miracle new technology that is the Solution to Everything™. Almost everything positive you have read about it is paid advertising, and should be completely ignored. So why should you believe what I'm about to tell you? Two reasons. The first is that no-one is paying me and I have no investments in cryptocurrencies or blockchain companies.

This is not to diminish Nakamoto's achievement but to point out that he stood on the shoulders of giants. Indeed, by tracing the origins of the ideas in bitcoin, we can zero in on Nakamoto's true leap of insight—the specific, complex way in which the underlying components are put together.
Bitcoin's Academic Pedigree,
Arvind Narayanan and Jeremy Clark

The second is that more than fifteen years ago, nearly five years before Satoshi Nakamoto published the Bitcoin protocol, a cryptocurrency based on a decentralized consensus mechanism using proof-of-work, my co-authors and I won the "best paper" award at the prestigious SOSP workshop for a decentralized consensus mechanism using proof-of-work. It is the protocol underlying the LOCKSS system. The originality of our work didn't lie in decentralization, distributed consensus, or proof-of-work. All of these were part of the nearly three decades of research and implementation leading up to the Bitcoin protocol, as described by Arvind Narayanan and Jeremy Clark in Bitcoin's Academic Pedigree. Our work was original only in its application of these techniques to statistical fault tolerance; Nakamoto's only in its application of them to preventing double-spending in cryptocurrencies.

We're going to walk through the design of a system to perform some function, say monetary transactions, storing files, recording reviewers' contributions to academic communication, verifying archival content, whatever. Being of a naturally suspicious turn of mind, you don't want to trust any single central entity, but instead want a decentralized system. You place your trust in the consensus of a large number of entities, which will in effect vote on the state transitions of your system (the transactions, reviews, archival content, ...). You hope the good entities will out-vote the bad entities. In the jargon, the system is trustless (a misnomer).

Techniques using multiple voters to maintain the state of a system in the presence of unreliable and malign voters were first published in The Byzantine Generals Problem by Lamport et al in 1982. Alas, Byzantine Fault Tolerance (BFT) requires a central authority to authorize entities to take part. In the blockchain jargon, it is permissioned. You would rather let anyone interested take part, a permissionless system with no central control.

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.
The Meaning of Decentralization,
Vitalik Buterin, co-founder of Ethereum

The security of your permissionless system depends upon the assumption of uncoordinated choice, the idea that each voter acts independently upon its own view of the system's state.

If anyone can take part, your system is vulnerable to Sybil attacks, in which an attacker creates many apparently independent voters who are actually under his sole control. If creating and maintaining a voter is free, anyone can win any vote they choose simply by creating enough Sybil voters.

From a computer security perspective, the key thing to note ... is that the security of the blockchain is linear in the amount of expenditure on mining power, ... In contrast, in many other contexts investments in computer security yield convex returns (e.g., traditional uses of cryptography) ... analogously to how a lock on a door increases the security of a house by more than the cost of the lock.
The Economic Limits of Bitcoin and the Blockchain,
Eric Budish, Booth School, University of Chicago

So creating and maintaining a voter has to be expensive. Permissionless systems can defend against Sybil attacks by requiring a vote to be accompanied by a proof of the expenditure of some resource. This is where proof-of-work comes in; a concept originated by Cynthia Dwork and Moni Naor in 1992. To vote in a proof-of-work blockchain such as Bitcoin's or Ethereum's requires computing very many otherwise useless hashes. The idea is that the good voters will spend more, compute more useless hashes, than the bad voters.

The blockchain trilemma
much of the innovation in blockchain technology has been aimed at wresting power from centralised authorities or monopolies. Unfortunately, the blockchain community’s utopian vision of a decentralised world is not without substantial costs. In recent research, we point out a ‘blockchain trilemma’ – it is impossible for any ledger to fully satisfy the three properties shown in [the diagram] simultaneously ... In particular, decentralisation has three main costs: waste of resources, scalability problems, and network externality inefficiencies.
The economics of blockchains,
Markus K Brunnermeier & Joseph Abadi, Princeton

Brunnermeir and Abadi's Blockchain Trilemma shows that a blockchain has to choose at most two of the following three attributes:
  • correctness
  • decentralization
  • cost-efficiency
Obviously, your system needs the first two, so the third has to go. Running a voter (mining in the jargon) in your system has to be expensive if the system is to be secure. No-one will do it unless they are rewarded. They can't be rewarded in "fiat currency", because that would need some central mechanism for paying them. So the reward has to come in the form of coins generated by the system itself, a cryptocurrency. To scale, permissionless systems need to be based on a cryptocurrency; the system's state transitions will need to include cryptocurrency transactions in addition to records of files, reviews, archival content, whatever.

Your system needs names for the parties to these transactions. There is no central authority handing out names, so the parties need to name themselves. As proposed by David Chaum in 1981 they can do so by generating a public-private key pair, and using the public key as the name for the source or sink of each transaction.

we created a small Bitcoin wallet, placed it on images in our honeyfarm, and set up monitoring routines to check for theft. Two months later our monitor program triggered when someone stole our coins.

This was not because our Bitcoin was stolen from a honeypot, rather the graduate student who created the wallet maintained a copy and his account was compromised. 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?
Risks of Cryptocurrencies,
Nicholas Weaver, U.C. Berkeley

In practice this is implemented in wallet software, which stores one or more key pairs for use in transactions. The public half of the pair is a pseudonym. Unmasking the person behind the pseudonym turns out to be fairly easy in practice.

The security of the system depends upon the user and the software keeping the private key secret. This can be difficult, as Nicholas Weaver's computer security group at Berkeley discovered when their wallet was compromised and their Bitcoins were stolen.

Bitcoin "price" history
The capital and operational costs of running a miner include buying hardware, power, network bandwidth, staff time, etc. Bitcoin's volatile "price", variable transaction fees, low transaction throughput, and large proportion of failed transactions mean that almost no legal merchants accept payment in Bitcoin or other cryptocurrency. Thus one essential part of your system is one or more exchanges, at which the miners can sell their cryptocurrency rewards for the "fiat currency" they need to pay their bills.

Who is on the other side of those trades? The answer has to be speculators, betting that the "price" of the cryptocurrency will increase. Thus a second essential part of your system is a general belief in the inevitable rise in "price" of the coins by which the miners are rewarded. If miners believe that the "price" will go down, they will sell their rewards immediately, a self-fulfilling prophesy. Permissionless blockchains require an inflow of speculative funds at an average rate greater than the current rate of mining rewards if the "price" is not to collapse. To maintain Bitcoin's price at $4K requires an inflow of $300K/hour.

Ethereum pools 04/06/18
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 Meaning of Decentralization,
Vitalik Buterin

In order to spend enough to be secure, say $300K/hour, you need a lot of miners. It turns out that a third essential part of your system is a small number of “mining pools”. As of last August Bitcoin had the equivalent of around 3M Antminer S9s, and a block time of 10 minutes. Each S9, costing maybe $1K, could expect a reward about once every 60 years. It will be obsolete in about a year, so only 1 in 60 will ever earn anything.

To smooth out their income, miners join pools, contributing their mining power and receiving the corresponding fraction of the rewards earned by the pool. These pools have strong economies of scale, so successful cryptocurrencies end up with a majority of their mining power in 3-4 pools. Each of the big pools can expect a reward every hour or so. These blockchains aren’t decentralized, but centralized around a few large pools.

At multiple times in 2014 one mining pool controlled more than 51% of the Bitcoin mining power. At almost all times since 3-4 pools have controlled the majority of the Bitcoin mining power. Currently two of them are controlled by Bitmain, the dominant supplier of mining ASICs. With the advent of mining-as-a-service, 51% attacks have become endemic among the smaller alt-coins.

The security of a blockchain depends upon the assumption that these few pools are not conspiring together outside the blockchain; an assumption that is impossible to verify in the real world (and by Murphy's Law is therefore false). Similar off-chain collusion among cryptocurrency traders allows for extremely profitable pump-and-dump schemes.

Since then there have been other catastrophic bugs in these smart contracts, the biggest one in the Parity Ethereum wallet software ... The first bug enabled the mass theft from "multisignature" wallets, which supposedly required multiple independent cryptographic signatures on transfers as a way to prevent theft. Fortunately, that bug caused limited damage because a good thief stole most of the money and then returned it to the victims. Yet, the good news was limited as a subsequent bug rendered all of the new multisignature wallets permanently inaccessible, effectively destroying some $150M in notional value. This buggy code was largely written by Gavin Wood, the creator of the Solidity programming language and one of the founders of Ethereum. Again, we have a situation where even an expert's efforts fell short.
Risks of Cryptocurrencies,
Nicholas Weaver, U.C. Berkeley

In practice the security of a blockchain depends not merely on the security of the protocol itself, but on the security of the core software and the wallets and exchanges used to store and trade its cryptocurrency. This ancillary software has bugs, such as last September's major vulnerability in Bitcoin Core, the Parity Wallet fiasco, the routine heists using vulnerabilities in exchange software, and the wallet that was sending user's pass-phrases to the Google spell-checker over HTTP. Who doesn't need their pass-phrase spell-checked?

Recent game-theoretic analysis suggests that there are strong economic limits to the security of cryptocurrency-based blockchains. For safety, the total value of transactions in a block needs to be less than the value of the block reward.

Your system needs an append-only data structure to which records of the transactions, files, reviews, archival content, whatever are appended. It would be bad if the miners could vote to re-write history, undoing these records. In the jargon, the system needs to be immutable (another misnomer).

Merkle Tree (source)
The necessary data structure for this purpose was published by Stuart Haber and W. Scott Stornetta in 1991. A company using their technique has been providing a centralized service of securely time-stamping documents for nearly a quarter of a century. It is a form of Merkle or hash tree, published by Ralph Merkle in 1980. For blockchains it is a linear chain to which fixed-size blocks are added at regular intervals. Each block contains the hash of its predecessor; a chain of blocks.

The blockchain is mutable, it is just rather hard to mutate it without being detected, because of the Merkle tree’s hashes, and easy to recover, because there are Lots Of Copies Keeping Stuff Safe. But this is a double-edged sword. Immutability makes systems incompatible with the GDPR, and immutable systems to which anyone can post information will be suppressed by governments.

A user of your system wanting to perform a transaction, store a file, record a review, whatever, needs to persuade miners to include their transaction in a block. Miners are coin-operated; you need to pay them to do so. How much do you need to pay them? That question reveals another economic problem, fixed supply and variable demand, which equals variable "price". Each block is in effect a blind auction among the pending transactions.

BTC transaction fees
Cryptokitties’ popularity exploded in early December and had the Ethereum network gasping for air. ... Ethereum has historically made bold claims that it is able to handle unlimited decentralized applications  ... The Crypto-Kittie app has shown itself to have the power to place all network processing into congestion. ... at its peak [CryptoKitties] likely only had about 14,000 daily users. Neopets, a game to which CryptoKitties is often compared, once had as many as 35 million users.
How Crypto-Kitties Disrupted the Ethereum Network,
Open Trading Network

So lets talk about CryptoKitties, a game that bought the Ethereum blockchain to its knees despite the bold claims that it could handle unlimited decentralized applications. How many users did it take to cripple the network? It was far fewer than non-blockchain apps can handle with ease; CryptoKitties peaked at about 14K users. NeoPets, a similar centralized game, peaked at about 2,500 times as many.

CryptoKitties average "price" per transaction spiked 465% between November 28 and December 12 as the game got popular, a major reason why it stopped being popular. The same phenomenon happened during Bitcoin's price spike around the same time. Cryptocurrency transactions are affordable only if no-one wants to transact; when everyone does they immediately become un-affordable. If, over time, running a node continues to be expensive enough to preserve security, fees for inclusion in a block must increase because rewards for mining blocks are set to decrease.

Nakamoto's Bitcoin blockchain was designed only to support recording transactions. It can be abused for other purposes, such as storing illegal content. But it is likely that you need additional functionality, which is where Ethereum's "smart contracts" come in. These are fully functional programs, written in a JavaScript-like language, embedded in Ethereum's blockchain. They are mainly used to implement Ponzi schemes, but they can also be used to implement Initial Coin Offerings, games such as Cryptokitties, and gambling parlors. Further, in On-Chain Vote Buying and the Rise of Dark DAOs Philip Daian and co-authors show that "smart contracts" also provide for untraceable on-chain collusion in which the parties are mutually pseudonymous.

ICO Returns
The first big smart contract, the DAO or Decentralized Autonomous Organization, sought to create a democratic mutual fund where investors could invest their Ethereum and then vote on possible investments. Approximately 10% of all Ethereum ended up in the DAO before someone discovered a reentrancy bug that enabled the attacker to effectively steal all the Ethereum. The only reason this bug and theft did not result in global losses is that Ethereum developers released a new version of the system that effectively undid the theft by altering the supposedly immutable blockchain.
Risks of Cryptocurrencies,
Nicholas Weaver, U.C. Berkeley

"Smart contracts" are programs, and programs have bugs. Some of the bugs are exploitable vulnerabilities. Research has shown that the rate at which vulnerabilities in programs are discovered increases with the age of the program. The problems caused by making vulnerable software immutable were revealed by the first major "smart contract". The Decentralized Autonomous Organization (The DAO) was released on 30th April 2016, but on 27th May 2016 Dino Mark, Vlad Zamfir, and Emin Gün Sirer posted A Call for a Temporary Moratorium on The DAO, pointing out some of its vulnerabilities; it was ignored. Three weeks later, when The DAO contained about 10% of all the Ether in circulation, a combination of these vulnerabilities was used to steal its contents.

The loot was restored by a "hard fork", the blockchain's version of mutability. Since then it has become the norm for "smart contract" authors to make them "upgradeable", so that bugs can be fixed. "Upgradeable" is another way of saying "immutable in name only".

Permissionless systems trust:
  • The core developers of the blockchain software not to write bugs.
  • The developers of your wallet software not to write bugs.
  • The developers of the exchanges not to write bugs.
  • The operators of the exchanges not to manipulate the markets or to commit fraud.
  • The developers of your upgradeable "smart contracts" not to write bugs.
  • The owners of the smart contracts to keep their secret key secret.
  • The owners of the upgradeable smart contracts to avoid losing their secret key.
  • The owners and operators of the dominant mining pools not to collude.
  • The speculators to provide the funds needed to keep the “price” going up.
  • Users' ability to keep their secret key secret.
  • Users’ ability to avoid losing their secret key.
  • Other users not to transact when you want to.

So, this is the list of people your permissionless system has to trust if it is going to work as advertised over the long term.

You started out to build a trustless, decentralized system but you have ended up with:
  • A trustless system that trusts a lot of people you have every reason not to trust.
  • A decentralized system that is centralized around a few large mining pools that you have no way of knowing aren’t conspiring together.
  • An immutable system that either has bugs you cannot fix, or is not immutable
  • A system whose security depends on it being expensive to run, and which is thus dependent upon a continuing inflow of funds from speculators.
  • A system whose coins are convertible into large amounts of "fiat currency" via irreversible pseudonymous transactions, which is thus an irresistible target for crime.
If the “price” keeps going up, the temptation for your trust to be violated is considerable. If the "price" starts going down, the temptation to cheat to recover losses is even greater.

Maybe it is time for a re-think.

Suppose you give up on the idea that anyone can take part and accept that you have to trust a central authority to decide who can and who can’t vote. You will have a permissioned system.

The first thing that happens is that it is no longer possible to mount a Sybil attack, so there is no reason running a node need be expensive. You can use BFT to establish consensus, as IBM’s Hyperledger, the canonical permissioned blockchain system does. You need many fewer nodes in the network, and running a node just got way cheaper. Overall, the aggregated cost of the system got orders of magnitude cheaper.

Now there is a central authority it can collect “fiat currency” for network services and use it to pay the nodes. No need for cryptocurrency, exchanges, pools, speculators, or wallets, so much less temptation for bad behavior.

Permissioned systems trust:
  • The central authority.
  • The software developers.
  • The owners and operators of the nodes.
  • The secrecy of a few private keys.

This is now the list of entities you trust. Trusting a central authority to determine the voter roll has eliminated the need to trust a whole lot of other entities. The permissioned system is more trustless and, since there is no need for pools, the network is more decentralized despite having fewer nodes.

Faults Replicas
1 4
2 7
3 10
4 13
5 16
6 19
a Byzantine quorum system of size 20 could achieve better decentralization than proof-of-work mining at a much lower resource cost.
Decentralization in Bitcoin and Ethereum Networks,
Adem Efe Gencer Soumya Basu, Ittay Eyal, Robbert van Renesse and Emin Gün Sirer

How many nodes does your permissioned blockchain need? The rule for BFT is that 3f + 1 nodes can survive f simultaneous failures. That's an awful lot fewer than you need for a permissionless proof-of-work blockchain. What you get from BFT is a system that, unless it encounters more than f simultaneous failures, remains available and operating normally.

The problem with BFT is that if it encounters more than f simultaneous failures, the state of the system is irrecoverable. If you want a system that can be relied upon for the long term you need a way to recover from disaster. Successful permissionless blockchains have Lots Of Copies Keeping Stuff Safe, so recovering from a disaster that doesn't affect all of them is manageable.

So in addition to implementing BFT you need to back up the state of the system each block time, ideally to write-once media so that the attacker can't change it. But if you're going to have an immutable backup of the system's state, and you don't need continuous uptime, you can rely on the backup to recover from failures. In that case you can get away with, say, 2 replicas of the blockchain in conventional databases, saving even more money.

I've shown that, whatever consensus mechanism they use, permissionless blockchains are not sustainable for very fundamental economic reasons. These include the need for speculative inflows and mining pools, security linear in cost, economies of scale, and fixed supply vs. variable demand. Proof-of-work blockchains are also environmentally unsustainable. The top 5 cryptocurrencies are estimated to use as much energy as The Netherlands. This isn't to take away from Nakamoto's ingenuity; proof-of-work is the only consensus system shown to work well for permissionless blockchains. The consensus mechanism works, but energy consumption and emergent behaviors at higher levels of the system make it unsustainable.

Blockchain buzzwords in S&P500 presentations
S&P500 companies are slowly figuring out that there is no there there in blockchains and cryptocurrencies, and they're not the only ones.

Still new to NYC, but I met this really cool girl. Energy sector analyst or some such. Four dates in, she uncovers my love for BitCoin.

Completely ghosted.
Zack Voell


troymc said...

You wrote, "You can use BFT to establish consensus, as IBM’s Hyperledger, the canonical permissioned blockchain system does."

I assume you mean Hyperledger Fabric (HF), since that is the Hyperledger project most closely associated with IBM. (All Hyperledger projects are under the umbrella of the Linux Foundation, not IBM, but HF did begin its life inside IBM.)

In any case, HF is not yet BFT, although an option to support that is in the roadmap. HF supports a plugin "ordering service," but there is no working/maintained BFT ordering service for HF. If you want to follow the HF progress on a BFT ordering service, see issue FAB-33 in their JIRA:

Disclosure: I am, or was, associated with BigchainDB, which uses Tendermint, a third-party blockchain system that is BFT. Hyperledger Burrow also uses Tendermint.

David. said...

Thanks for the correction!

David. said...

The headline writers at Vulture Central were on form with John Oates' Blockchain is a lot like teen sex: Everybody talks about it, no one has a clue how to do it. Oates looked at the latest from the credulous "analysts" at Gartner, who found that:

"According to a survey of supply chain specialists carried out by Gartner, nine out of 10 blockchain-based projects will have come unstuck by 2023. Only 9 per cent of companies have actually spent money on blockchain projects and just 19 per cent said it was a very important technology for their business.

Alex Pradhan, senior principal research analyst at Gartner, said: "Supply chain blockchain projects have mostly focused on verifying authenticity, improving traceability and visibility, and improving transactional trust. However, most have remained pilot projects due to a combination of technology immaturity, lack of standards, overly ambitious scope and a misunderstanding of how blockchain could, or should, actually help the supply chain. Inevitably, this is causing the market to experience blockchain fatigue."

Despite this, they remained optimistic about blockchains:

"Gartner predicted that at least one cryptocurrency-funded, non-mainstream political party will win a national election by 2023 and that countries will begin to use cryptocurrencies over their own legal tender to counter hyperinflation. Mmkay.

It even forecast that: "By 2025, a public blockchain will provide a core interoperable foundation for global, decentralised identity management."


David. said...

Jeffrey Lee Funk's Big Tech leapt on the blockchain bandwagon but its applications are stuck in cryptocurrency is appropriately skeptical:

"Blockchain remains a far cry from the grandiose projections of Gartner and other consultants. The benefits will likely depend on the number of companies that participate in blockchain projects in, for example, finance or supply chain management, and it may take decades for many to become involved."

David. said...

The security of your blockchain depends not just on the security of the node you run, but on the security of all the other nodes in the network. One big problem for permissionless blockchains is that there is no mechanism for enforcing good behavior among the nodes. Catalin Cimpanu's A large chunk of Ethereum clients remain unpatched illustrates this problem:

"security researchers from SRLabs revealed that a large chunk of the Ethereum client software that runs on Ethereum nodes has not yet received a patch for a critical security flaw the company discovered earlier this year.

"According to our collected data, only two thirds of nodes have been patched so far," said Karsten Nohl, one of the researchers."

The reason is that:

""The Parity Ethereum has an automated update process - but it suffers from high complexity and some updates are left out," Nohl said.

Parity clients that have been configured incorrectly will not receive automatic updates, even if node maintainers believe they are. Any Parity client that doesn't synchronize with the main Ethereum blockchain, or is not available from all nodes, will not receive updates.

On the other hand, Geth lacks an automatic update system altogether, making node patching a manual process that requires the operator to keep an eye out for patches and apply them manually when they're available.

All of these issues put all Ethereum users at risk, and not just the nodes running unpatched versions. The number of unpatched notes may not be enough to carry out a direct 51% attack, but these vulnerable nodes can be crashed to reduce the cost of a 51% attack on Ethereum, currently estimated at around $120,000 per hour."

Why is there reluctance to update nodes?

"The bad news is that these problems are not unique to Ethereum and its node client software.

"Patch problems are widespread among blockchain clients," Nohl told ZDNet. "The patch gap signals a deep-rooted mistrust in central authority, including such any authority that can automatically update software on your computer."

"The blockchain patch gap is more critical for clients that process more complex protocols, in particular smart contacts, since these protocols typically create more surface for bugs that need to be patched."

If you trust a central authority to update your software, what is the point of a permissionless blockchain?