Friday, June 29, 2018

Cryptocurrencies Have Limits

The Economic Limits Of Bitcoin And The Blockchain by Eric Budish is an important analysis of the economics of two kinds of "51% attack" on Bitcoin and other cryptocurrencies, such as those becoming endemic on Bitcoin Gold and other alt-coins:
  • A "double spend" attack, in which an attacker spends cryptocurrency to obtain goods, then makes the spend disappear in order to spend the cryptocurrency again.
  • A "sabotage" attack, in which short-sellers discredit the cryptocurrency to reduce its value.
Below the fold, some commentary on Budish's paper.

Cost-Benefit Analysis Of 51% Attack

Budish starts by over-simplifying, showing that if all things were equal competition among miners would erode the returns from mining to zero:
assume that it takes one chip and one unit of electricity to produce one unit of computational power, a chip costs C, the per-block cost of capital (including depreciation) is r, and the per-block cost of one unit of electricity is e; then we have:
c = rC + e
Assume for now that this cost is symmetric across all participants and that the chips are easily repurposable, so we do not have to worry about sunk costs, adjustment costs, etc. ... If there are N units of computational power in the network, then each unit has a 1/N probability of winning the prize Pblock. Under standard free entry logic — any entity that likes can add computational power to the network — the equilibrium amount of computational power devoted to blockchain mining, N*, is thus characterized by:
N*c = Pblock
This is Equation 1. A "51% attack" on this simplified network from an outsider who controls none of the "honest" mining power would cost at least:
N*c + ε
An attacker who already controlled half the mining power could pay as little as:
(N*c)/2 + ε
An outside attacker could pay A>1 times as much and gain a super-majority of A/(A+1). To ensure that there is no incentive for outsiders to attack the network, the cost of the attack has to be greater than the potential gain from the attack, Vattack, which leads to Budish's Equation 2:
α⋅N*c > Vattack
Where, if t is the duration of the attack in block times:
α = (A-1)t
Like Radia Perlman, Budish notes that:
From a computer security perspective, the key thing to note about (2) is that the security of the blockchain is linear in the amount of expenditure on mining power, i.e., linear in N*c ... 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.
One problem with this over-simplified model is that it applies to outsiders. For insiders, an attack is much cheaper, so Equation 2 should be:
α⋅N*c > 2⋅Vattack
Mining power 25 June 2018
As I started to write, two pools apparently owned and operated by Bitmain controlled 41.2% of the Bitcoin hash rate (BTC.com 24.8%, AntPool 16.4%). Add in SlushPool's 10.6% and you have 51.8%. As the dominant supplier of mining chips, Bitmain has a great deal of influence over other major mining pools. So Bitcoin is already somewhat vulnerable to a 51% attack by Bitmain, albeit their Vattack would be outweighed by the damage to their business. 51% attacks on cryptocurrencies with less mining power are becoming routine, thanks to the availability of "mining as a service".

Budish combines Equations 1 & 2 to get Equation 3:
Pblock > Vattack⁄α
This inequality expresses the honest equilibrium condition for deterring an outsider's 51% attack (to deter insiders, Pblock has to be twice as big):
the equilibrium per-block payment to miners for running the blockchain must be large relative to the one-off benefits of attacking it. Equation (3) places potentially serious economic constraints on the applicability of the Nakamoto (2008) blockchain innovation. By analogy, imagine if users of the Visa network had to pay fees to Visa, every ten minutes, that were large relative to the value of a successful one-off attack on the Visa network.
What is Vattack, the potential gain from an attack? That depends on the kind of attack.

Double Spending

A 51% attacker can add blocks to the chain, and prevent others doing so, enabling "double spending":
The most widely discussed manipulation a majority attacker can engage in is known in the literature as “double spending”. An attacker could (i) spend Bitcoins, i.e., engage in a transaction in which he sends his Bitcoins to some merchant in exchange for goods or assets; then (ii) allow that transaction to be added to the public blockchain (i.e., the longest chain); and then subsequently (iii) remove that transaction from the public blockchain, by building an alternative longest chain, which he can do with certainty given his majority of computing power. The merchant, upon seeing the transaction added to the public blockchain in (ii), gives the attacker goods or assets in exchange for the Bitcoins, perhaps after an escrow period. But, when the attacker removes the transaction from the public blockchain in (iii), the merchant effectively loses his Bitcoins, allowing the attacker to “double spend” the coins elsewhere.

As should be clear, while this problem is called the “double spending” problem, the “double” part is a misnomer — the attacker can re-spend his Bitcoins arbitrarily many times.
As a worst case, the attacker can fill the blocks he adds to the chain with large transactions, so if there are k transactions per block and the maximum permitted value is Vmax:
Vattack ≤ k⋅Vmax
Thus, from Equation 3, in the worst case the block reward per transaction must exceed Vmax divided by α, which is my re-statement of Budish's Equation 4. The limited block size causes high and volatile transaction fees, and uncertain delay in transaction confirmation, making Bitcoin useless for small transactions. This is the problem the Lightning network is attempting (unsuccessfully) to solve. Equation 4 means it is unsafe for the Bitcoin blockchain to allow large transactions. But the problem for Bitcoin is worse. The major attraction of Bitcoin for devotees of Austrian economics is that there will never be more than 21M Bitcoins. To ensure this, Pblock decreases with time, eventually becoming zero. And so does the largest transaction it is safe to allow.

Budish ran simulations exploring "double spend" attacks against the current Bitcoin blockchain, and shows the results in Table 1. For the canonical case of waiting six blocks for confirmation (t = 6) and assuming A = 1.25, the attack lasts less than 14 block times and has an expected cost net of block rewards of 3.35 times Pblock, or under 42BTC ($248K, if you believe "market prices").

David Gerard points to this table of the cost of a 1-hour 51% attack on a range of cryptocurrencies, using prices from NiceHash (of course, NiceHash would not actually be able to sell you this much mining power). Attacking Bitcoin would cost $424,469, less than a factor of two away from an estimate from Budish's work. 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 is $1.277M or 4.7E-6 of their market cap.

Sabotage Attack

[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 had been arrested. (Source)
The downside for an insider 51% attacker is that, after the fact, the attack would likely be detected, discrediting the cryptocurrency and thus reducing its value, and the insider's investment.

Budish analyzes this case (I have changed the symbols slightly for ease of understanding):
Formally, let us assume that the double-spending attack analyzed in Section 2.1 causes a proportional decline in the value of Bitcoin of attack, and that the attacker holds the minimum amount of Bitcoin necessary to conduct the attack, namely k⋅Vmax worth. ... The attack decline in the value of Bitcoin modifies equation (4) to be Equation 4′:
Pblock > k⋅Vmax⋅(1 - ∆attack)/(A -1 + ∆attack)
The larger is attack, the smaller is the implicit tax on the system necessary to deter the majority attack, i.e., the level of [block reward per transaction] necessary to support a given [Vmax]. For example, if attack = 1, i.e., if the attack causes a total collapse of the value of Bitcoin, the attacker loses exactly as much in Bitcoin value as he gains from double spending; in effect, there is no chance to “double” spend after all. ... However, attack is something of a “pick your poison” parameter. If attack is small, then the system is vulnerable to the double-spending attack ... and the implicit transactions tax on economic activity using the blockchain has to be high. If attack is large, then a short time period of access to a large amount of computing power can sabotage the blockchain.
Experience tends to show that the Bitcoin market is sufficiently manipulated that attack would be small. But this may no longer be the case. Olga Kharif's Crypto Collapse Spreads With Hundreds of Coins Plunging in Value reports that:
Over 80 percent of 1,586 digital coins Finder.com tracks in a weekly survey decreased in price in the past seven days. The tokens fell 19 percent on average, Finder.com found in the week ended June 25.

Trading volume dropped as well, declining by 6 percent from the previous week, Finder.com said. Bitcoin, Tether, Ether, EOS and Bitcoin Cash were the top five traded cryptocurrencies. Volume was half of what it was at the end of April, when Finder.com first started releasing its Weekly Coin Analysis.
1-yr BTC-USD "Price"
However, there are two cases in which the goal is for attack to be large, and powerful adversaries would likely have the PR resources to achieve this goal:
  • Recently, the financial wizards who brought us the 2008 global financial crisis have started Bitcoin Futures markets, which enable shorting of BTC. Shorting BTC has been a very profitable trade this year, as BTC's "market price" has declined from $19,499 on 15th December 2017 to, as I write this, $5,890. Further sharp declines would be in the short-sellers' interest.
  • Governments dislike the major uses for cryptocurrencies, unregulated speculation, money laundering, ransomware, and trade in illicit goods. They would be happy to see cryptocurrency values crash.

More Realistic Models

To this point, Budish's analysis has made a set of assumptions that don't hold in the real Bitcoin mining market:
Assume for now that [mining] cost is symmetric across all participants and that the chips are easily repurposable, so we do not have to worry about sunk costs, adjustment costs, etc.
In Section 3 Budish examines lifting these assumptions:
The analysis in Sections 1-2 assumed that the attacker’s cost of waging the majority attack was proportional to the per-block “flow” cost of mining the block chain. ... However, if both (i) the technology necessary for mining the blockchain is specific (i.e., non-repurposable), and (ii) the attack harms the subsequent value of that technology, then it may be appropriate to charge the attacker a stock cost rather than a flow cost. Importantly, (i) and (ii) seem likely to hold for the Bitcoin blockchain at present.
For the details, you need to read the paper, but the TL;DR is in Section 3.3, Collapse Scenarios. There are three:
  1. Ultra-cheap specialized ASICs. Given the huge advantages enjoyed by mining chip manufacturers, outlined by David Vorick in The State Of Cryptocurrency Mining, even large manufacturers' "slow AIs" would find it hard to give up the margins they can extract from miners. So I don't see this case as realistic.
  2. Efficient-enough repurposable chips. David Vorick argues, and I agree, that custom ASICs will always greatly out-perform general-purpose ones. The risk is that BTC gets cheap enough that the mining market can no longer support the development of new generations of custom ASICs. A decline like the one so far this year would do the trick.
  3. Economic sabotage becomes sufficiently tempting. These are the two cases I outlined above, and both are realistic.
There are further refinements of the analysis that Budish does not pursue, for example the radically non-uniform costs among miners, and the very rapid depreciation of mining hardware. But my guess is that these will not change to overall picture greatly.

Postscript

I can't resist noting that the double spend attack is related to an attack on an early version of Andries Brouwer's Hack game. The first thing Andries added to the Lincoln-Sudbury Regional High School original was a little dog that accompanied the player; I never saw Andries without his dog.

The Dutch have a long history of commerce, so as I recall the next thing Andries added was a shop, well-stocked with valuable items, and a shop-keeper. A player could enter the shop via the door, and exchange gold for items and vice versa. The shop-keeper was friendly unless attacked, or the player exited the door without settling up, when he became extremely violent.

One night in the fall of 1982 my second-year CS students at the Universiteit van Amsterdam  discovered that it was possible to use a Wand of Digging to open a passage into the back of the shop. The player could enter the shop this way, grab as many items as he could carry, and exit the shop via the newly created passage. Since they had not exited via the door, there was no need to pay for the items. Next, the player could enter the shop via the door and sell the loot to the shop-keeper. After exiting the shop empty-handed via the door, the player could repeat the process. And, because Andries had omitted to provide the shop-keeper with a budget, the process could be repeated ad infinitum. My students had discovered an unlimited supply of gold!

Don't try this at home, kids! Andries quickly made entering the shop other than via the door a careerlife-limiting move.

15 comments:

David. said...

More on manipulation in cryptocurrency markets from a Bloomberg investigation of Tether trading on Kraken:

"Because many venues are unable to secure bank accounts to give their customers access to dollars or other traditional currencies, investors are often paid with Tether when they cash out.

Kraken is among very few markets worldwide that let investors trade U.S. dollars for Tether and vice versa. So Kraken should play a large role in establishing Tether’s price.

But the normal economics of supply and demand don’t always appear to apply."

David. said...

"Ripple, ... has quietly become one of the most valuable start-ups of the last decade thanks to the value of XRP, the digital token its founders created six years ago.

Now comes the hard part: persuading people to use XRP for something other than speculative trading. It is an issue facing most of the still-young cryptocurrency industry. Digital tokens like Bitcoin and its many imitators (like XRP) were designed to make electronic transactions of all sorts easier. But today almost no transactions are happening, other than on virtual currency exchanges where people bet on their price.

Despite a dramatic drop in the value of cryptocurrencies this year, Ripple still owns $30 billion worth of XRP, and the company wants to get some of those digital tokens into the hands of potential users." reports Nathaniel Popper in Here’s Some Cryptocurrency. Now Please Use It.

You have to read this article to get an idea of how insane this bubble is:

"Many people who bought the digital tokens created by these projects did so in the belief they will one day be useful for real transactions of some sort. If the projects want to keep those investors from selling, the projects have to convince them the tokens will have some long-term value.

A company known as Block.One, for example, raised $4 billion from investors before it even had functioning software. Now it is using some of the billions it has raised to create investment funds that will encourage developers to work on making its cryptocurrency, EOS, useful."

David. said...

Believers in "smart contracts" should check out this github repository of buggy ERC20 tokens. Immutability and programs don't mix.

David. said...

"It all felt a bit PR-y and lacking the kind of critical approach we would expect from a serious university like LSE, so we called up Dr Carsten Sørensen, the course convenor and a reader in digital innovation in the university's management department. When we questioned him about some of the promises and statements in the prospectus, he said:

Stop being a journalist and just think. You’re citing marketing material as if that were the ultimate truth."

From The London School of Cryptonomics, Jemima Kelly's laugh-out-loud takedown of the PR for the London School of Economics' new cryptocurrency course.

David. said...

"About 56 percent of crypto startups that raise money through token sales die within four months of their initial coin offerings.

That’s the finding of a Boston College study that analyzed the intensity of tweets from the startups’ Twitter accounts to infer signs of life. The researchers determined that only 44.2 percent of startups survive after 120 days from the end of their ICOs. The researchers, Hugo Benedetti and Leonard Kostovetsky, examined 2,390 ICOs that were completed before May."

From Olga Kharif's Half of ICOs Die Within Four Months After Token Sales Finalized. So you don't need 51% to attack a token, you just need a few months and it'll discredit itself.

Actually, 44.2% survival is pretty good in the light of 81% of Recent ICOs Were Scams, Research Finds:

"Four out of five initial coin offerings (ICOs) that have taken place in the last year have been classified as scams, according to a recent study by Satis Group, an ICO advisory firm."

So about one in three ICOs are still stringing the chumps along after 4 months.

David. said...

BTC has been below $8K for two months, and it is starting to hurt miners. /. reports that cloud mining company Hashflare has announced:

"For over a month our users encountered a situation when the payouts were lower than the maintenance fees, resulting in zero accruals to the balance. As of 18.07.2018, the payouts were lower than maintenance for 28 consecutive days. BTC mining continues being unprofitable, in light of which we would like to inform you that on 18.07.2018 we were forced to start disabling SHA hardware and today, on 20.07.2018, stop the mining service of active SHA-256 contracts in accordance with clause 5.5 of our Terms of Service, which are required to be accepted when creating a purchase and are the basis of concluding the contract."

As I predicted, over time economies of scale will force centralization around the miners with the lowest cost base.

David. said...

In Declining cryptocurrency prices are making graphics cards affordable again Timothy B. Lee reports:

"About a year ago, graphics card prices started to go crazy. Then in early 2018, things got even crazier. The price of a Radeon RX 570—a mid-range graphics card popular for cryptocurrency mining—soared from under $200 in April 2017 to over $450 in February 2018. Over the same period, a high-end RX 580 soared from around $230 in April 2017 to as much as $540 in February 2018.

But since then, graphics-card prices have been falling steadily, according to data collected by PC Part Picker. An RX 570 fell to around $350 by the end of April. And you can now get one for a bit more than $300. An RX 580 now goes for around $330."

David. said...

Jemima Kelly's Crypto & government: from anarchy to amity in the USA is laugh-out-loud funny. I won't spoil it, except for this partial quote from Tim Swanson:

"The irony of setting up a PAC, or lobbying organisation, or even donating directly to specific candidates, is that the underlying architectural assumption with cryptocurrencies - such as bitcoin - is that they are anarchic by design. That is to say, these networks were originally architected to bypass intermediaries and traditional gatekeepers.
...
To use an analogy, an anarchist PAC is like a libertarian police department: it's a contradiction in terms."

Go read the whole thing.

David. said...

Cryptocurrency "price" manipulation is alive and well!

"On Wednesday, the Tether treasury wallet sent two transactions, of 50 and 30 million USDT. The funds were moved directly into one of the Bitfinex hot wallets.

For a few hours on Wednesday, both BTC and altcoins recovered sharply. BTC returned above $6,500, and some altcoins grew by 20%, and as much as 90% for smaller assets.

The coincidence of USDT tranches and a quick recovery of BTC prices by a few hundred dollars confirmed some of the suspicions of market manipulation."

From Tether (USDT) Keeps Pumping Liquidity on Bitfinex, Props Up Bitcoin (BTC) Price by Christine Masters.

David. said...

Bittrex has delisted Bitcoin Gold:

"after BTG maintainers declined to pay half of the damages Bittrex suffered during a complex multi-stage cyber-attack earlier this year.

According to a statement from the BTG team, Bittrex asked the BTG team to pay 12,372 BTG (~$256,000) as reparations for the attacks.
...
The BTG team says the hack was a combination between a 51% attack and a double-spend attack.

BTG experts said hackers rented servers through the NiceHash cryptocurrency mining market to overwhelm the Bitcoin Gold network and take control of more than half the BTG network computational hashrate."

David. said...

In A glimpse into the dark underbelly of cryptocurrency markets Nic Carter investigates:

"the key drivers of the unrelenting cryptocurrency/cryptoasset markets, and explain why they aren’t likely to go away soon. In particular, I will focus on the incentives which cause rankings sites to uncritically include junk exchange volume in their data.

The major stakeholders in this market are exchanges (naturally), altcoin/cryptocurrency/fork issuers, and coin ranking sites, who mutualistically work together to extract value from one group: retail investors. Unwitting investors juice the whole operation with infusions of capital."

David. said...

Brian Harvey's A Case Study: The Lincoln-Sudbury Regional High School provides the fascinating back-story of the environment that spawned Hack.

David. said...

I was reminded by a room filled with rupees in Legend of Zelda: Link's Awakening of another early addition to Hack that, IIRC, was my idea. The cave acquired a Treasure Zoo, a room entirely filled with a random assortment of monsters, each sitting on a random treasure. Entering the room was certain death. But if you stood in the door only one monster at a time could attack you. Death before the room ran out of monsters was still likely, but not inevitable. The reward for survival was probably a cornucopia of riches.

David. said...

Hack evolved into NetHack. In A Gaming Night at the Museum, Jean-Christophe Collet writes:

"This is how, as we were closing on the 35th anniversary of the project, I learned that NetHack was being added to the collection of the Museum of Modern Art of New York. It had been selected by the Architecture and Design department for its small collection of video games, and was going to be displayed as part of the Never Alone exhibition this fall."

David. said...

IIRC Jonathan Payne's README on the Usenix tape from which Andries got Hack included a phone number and the note "if you have problems you can call me, but I have a teenage sister and a modem, so good luck!"