The Paradox of Trust in Permissionless BlockChain

A few days ago, I posted on work by my colleagues (Eyal, Sirer, Van Renesse and Gencer), who showed that most BitCoin mining is occurring in a fairly small number of data centers, mostly operating in China.

Why is this even possible?  To appreciate the context, it helps to realize that any BlockChain system that operates anonymously needs a way to protect against DDoS attacks (BlockChain assumes that some percentage of the participating computers are unhelpful and perhaps even malicious in a Byzantine sense, and hence could try to flood the system with nonsense of various kinds).  To this end, they employ two mechanisms: (1) A proof-of-work requirement, so that it takes some heavy computing to generate new blocks; (2) A cryptocurrency reward for solving those puzzles and placing new blocks at the end of the chain.  Basically, even though you don't trust some of the computers, you block bad behavior and incent good behavior. 

This is how new cryptocoins arise.  Unlike fiat currency, which is simply printed by the United States Treasury, or the Chinese Treasury, or the Swiss one, you need to earn your BitCoins or Ether coins, by mining.  While you can also obtain coins in transactions with other participants, for example by selling them chewing gum or some other high-value commodity, those are previously minted ones.

As cryptocurrencies have soared in value, one after another, the potential to become rich by playing a big role in coin mining wasn't lost on the kind of companies in a position to invest in doing that.  In fact it makes sense to jump in early: you mine lots of coins back when the chain had no real value, and later it turns out that you possess a resource valuable beyond all comprehension.

So, if you are the kind of company that builds data centers, data centers specifically for mining cybercurrency makes sense.  It became very appealing to pursue this form of reward by five years ago, and massive data centers emerged.  Gradually, they upped their game, deploying cutting edge hardware to gain a performance edge.  This pushed less-well-equipped miners out: Anyone who knows how to mine faster and cheaper can earn more and more of those precious bits. 

But it turns out that this dynamic favors places like China, which have inexpensive electric power and labor, yet also have the needed high-tech skills to actually create and run such a mining operation.  So (1) the mining quickly concentrates in a few places, and (2) they tend to be in China.  But that one-two story creates a new and unexpected threat.

The risk is that once a majority of BitCoin mining becomes concentrated in the hands of any small number of players, they can use their power to control which transactions are logged and when, or can offer preferred performance to their friends and penalize their enemies, or even force a rollback to really harm someone they dislike.  A rollback is pretty drastic: since the coins actually originate in blocks within the chain, if the block that minted a coin rolls back, that coin evaporates.  Worse, transactions won't automatically be reissued and performed in the new chain: a transaction becomes invalid if it uses even a fractional version of a non-existent coin.  So potentially, some coins evaporate and some transactions evaporate too.  Yet the chewing gum already changed hands, and has been chewed.  Can't roll that back...

The risk is definitely real.  First, the mere possibility of behaving like a cartel in order to extract more profit from the BlockChain is a powerful force in favor of the first players to explore doing so.  Of course, any cartel will quickly turn into a kind of BitCoin mafia, but the members will get very rich in the process.  So it will happen sooner or later, purely due to market forces.

As for making deals to favor some transactions, or trying to extort money in exchange for fair treatment, we are definitely already hearing stories along those lines today.

But the really extreme case hasn't occurred -- yet.  The scenario here starts with a political event, such as a trade war or a confrontation over the ultimate status of some Asian island-state, or even a border dispute.  It causes great tension between China and some other country that uses BitCoin (or some other cybercoin where Chinese data farms are doing much of the heavy lifting).  Then you have to imagine that China is so angry that it steps in, demands national control over the data centers within its own borders, and then sets out to use this control as leverage in their global political ambitions.  This escalates until they just wipe out some huge portion of the chain by aggressively mining to create an even longer portion.  Everyone expects roll-back events with a block or two, but nobody is prepared for roll-backs that might span days, weeks, months... even years.  Could it happen?  Apparently.

So rather than wander into a gloom and doom story again (I did that on a prior posting), I wan to comment on "hoist on one's own petard" aspect of this.  Is BitCoin in fact doomed, in some way, by the very principle of democratization and global fairness that Satoshi set out to achieve?

How did I ever come up with that idea?  Well, you need to think about Satoshi Nakamoto's missive, the document that inspired the entire endeavor.  The story was basically one of eliminating the monopoly power that governments hold over fiat currency in favor of a global and decentralized model: everyone would mine coins, and everyone would share the benefit.

But with this flipped situation where the economic incentives favor centralization, we can now see something that wasn't evident back then: a paradoxical outcome in which it turns out that the seeds of monopoly were actually hidden in the original premise!  We need a game theoretic analysis!  But it seems to me that BitCoin is turning out to be a game with an unexpected Nash Equilibrium: a state in which there is a small monopoly in total control of the BlockChain.

It all centers on a mistaken notion of trust.  In Satoshi's writings, the concept of trust is central.  Satoshi does not trust centralized government, leading him to invent a new ecosystem in which nobody needs to trust any at all.  Everyone runs the BlockChain software, nobody cares where it runs, or trusts the participants, yet the chain grows, and everyone can use it to buy and sell the flavor of bubblegum that they prefer, in perfect anonymity.   In concept, at least, there is no advantage to be had by modifying the protocol or attacking the chain.

But we can see how this neglected one aspect of trust: trust that the BlockChain software is run by large numbers of autonomous players, and that mining doesn't become concentrated in any pool that gets even close to controlling one third or more of the mining power.  The point about one third, by the way, arises from a different way of manipulating the system: in a previous result, the same authors managed to show that a cartel with one-third of the mining power can earn all the income by sharing certain kinds of information only within cartel participants (this is a slight violation of the protocol, but one you could implement with just a few lines of changes to the BitCoin code base).

Nobody would know that the cartel had pulled the trick off.  It would just start to win every single competition to place the next block.  By shifting through lots of aliases, it would be quite hard to prove that they were up to this.

Conclusion: It appears that the economics of cybercoin mining creates an unexpected pressure to concentrate mining power in a small number of players.  This in turn gives those players an incentive to form a cartel, in which case they can earn all the money, decide which transactions to clear and which to ignore.  And if they get really, really angry, they can collapse the entire BlockChain.

Would I worry about this, if I was invested in BitCoin?  Actually, I think the risk seems real and worrying enough to genuinely think about.  It could happen.  And if the chain were to collapse, all of that wealth would evaporate like so much pixie dust.

So why aren't the big players in a panic?  My guess is that they have profited so greatly from playing in the current high-risk ecosystem that BitCoin represents that they became inured to risk along the way.  BitCoin sometimes doubles in price (or loses 80% of its value) in minutes.  Maybe this blog posting will send it on some new gyration.  And these investors have learned that like a really great roller coaster, each stomach-wrenching downslope is followed by a giddy climb to previously unimagined heights.  They get hooked on it... and are unable to appreciate that giving some cartel power to collapse the whole thing is perhaps unwise -- like simply assuming that the rollercoaster framework is sound, while entrusting it to an unknown construction crew from out of town.  Did they loosen the bolts last night,  secretly?  You might not find out until the thing literally collapses underneath you, and by then it would be far too late to reconsider your willingness to take another ride!

So here's a shout-out to my friends who work on game theory.  Are BlockChain systems doomed to form cartel structures?  Or could one imagine a version of BlockChain in which membership is anonymous (permissionless), and yet cartels cannot arise?

One last observation.  Right now, nobody thinks of systems like Microsoft/VMWare/Facebook's Corfu logs as the basis for a BlockChain, primarily because they don't use proof of work, because they don't operate in a permissionless model.  Same for Derecho, the system we've been working on at Cornell: Derecho is a fast version of Paxos, but you wouldn't normally store HyperLedger records into it.

But why not?  Why shouldn't we create permissioned ledgers this way?  We would eliminate that rate limitation, which drives everyone crazy right now, and in fact would gain other advantages too: auditability, elimination of proof-of-work computations.  This would be good, right?  Rather than mint coins in exchange for mining, we could just stick with traditional fiat currency, but allow these ledgered transactions to talk about it: "For the sum of $1, Ken agrees to sell five packs of BubbleYum Chewing Gum to Ittay."    Maybe later we find a follow-on transaction: "The third party escrow agent confirms delivery of the gum", and after that, confirmation that the $1 changed hands.

Then we could focus on ways to run transactions that span multiple BlockChains.  Maurice Herlihy just published a paper on a protocol for doing that sort of transaction.  Even more interesting than the solution is the specification: if I run a private chain at bank branch A, and it interacts with your branch B of some other bank, how do I know that the transaction was safe, and valid?  And can we avoid creating an audit dependency between A's private log, and B's private log?  Would there be a role for an organization like SWIFT, to assist in clearing at the end of the working day?

You can see where this all leads... my colleagues in game theory would oblige me by proving that permissionless BlockChain is doomed to create high-risk monopolies that concentrate all the control in the hands of a few small cartel-like groups.  Bad news.  To save themselves from a total coin-ocalypse, everyone switches to permissioned models, and we work out the details for using those to host cryptocurrency.  My research group and I enhance Derecho until it stands alone as the ultimate solution for solving that problem (perhaps you didn't know this, but Derecho is provably optimal for Paxos, and in fact is demonstrably way faster than any previous Paxos system, too).  My students then go out and commercialize this...   I like this story!

So what about it, game theory people?  Is this BitCoin vulnerability inevitable in permissionless BlockChains?

Blockchains immune to cartels.

In my last blog posting, I reported on work by my colleagues that showed how concentrated Blockchain mining has become, with twenty data centers (mostly in China) doing the majority of the mining.  We saw that this makes it easy for China to attack the Blockchain in various ways.

A natural question is to ask why exactly this issue arises, and what can be done about it.

For Bitcoin and other permissionless Blockchain Systems, the central issue is “proof of work,” and it arises because of two factors: the rewards for mining, and worries about a form of DDoS vulnerability.  In Bitcoin, the miner that creates a block of transactions and is able to place it in the Blockchain by computing a nonce value that will result in a SHA5 hash with the requisite number of zeros is paid for the effort: the block will “issue” a new coin to the miner, and the value of the coin combines a fee on the transactions it contains, plus a small additional reward for placing the block itself.  

Because the cryptographic system used is not known to offer any computational shortcuts, computing the nonce is a brute force task: a miner computes a next block and then tests various nonce values until it finds one that results in a hash with the desired characteristic.  There is no way to avoid the brute force task of sifting through nonce values, at present.  This Bitcoin rewards computational power.  The more powerful your mining center, in terms of hashes it can compute per second, the more money (coins) you earn.

Could we imagine a Bitcoin or Blockchain protocol wired to locality, so that the right to create blocks could be fairly shared between miners in the USA, Canada, France, Russia, China, India, Uzbekistan,  etc?  Not really.  Doing this would just incent global mining consortia that would run proxy computers in those countries, but would outsource the actual nonce computation back to the farms in China, allowing the existing mining cartel to preserve its monopoly on the income, and its power to attack the global Blockchain.

So why, exactly, did we need proof of work?  The DDoS worry stems directly from the anonymity of Bitcoin: any computer that wishes to join the Bitcoin pool can do so just by downloading the proper software and attaching itself to the network, using a virtual “name” that isn’t tied to any physical computer address in a direct way.  Thus one real computer could fork off hundreds of clones, and they could generate huge rates of transactions by just selling bubblegum to one-another at preposterously high rates.  Bitcoin is designed to discourage such behavior: first, the fees paid to log transactions make it expensive to generate huge numbers of them.  And second, the intent of the hashing thing is to spread the odds of creating the next block broadly, “fairly.”  Here we can see a flaw in the design: fairness breaks down, and once a cartel gains control of the show, most other properties of anonymity and non-fiat currency characteristics are out the window too.

Better, it seems to me, would be a permissioned model in which non-anonymized players (call them “banks”) maintain local ledgers.  We would have a local ledger of transactions at Bank of America, another local one at the Bank of Russia, etc.  Individual branches could have their own local sub-ledgers.  I’m not proposing that these logs replicate all the transactions in the world.  Just local logs,  using hyperledger or a similar technology to record banking and business contracts and e-coin transactions.

Such a local ledger won’t need to be permissionless because a branch of the Alternatives Federal Credit Union knows perfectly well which machines play server roles.  So we can use membership management protocols, and in fact are looking at a problem like the one solved by Corfu, or by Derecho in its persistent mode.  Perhaps it would be wise to harden the solution against Byzantine attacks, also a solvable, classic problem.   

Then we could create a protocol for banks to talk to one another, more or less SWIFT (the widely used standard interbank protocol) but enhanced to deal with inter-bank transfers.  Here, I think we see an interesting distributed transaction problem: how would one specify the required properties?  For example, if I ask Alternatives Federal Credit Union to purchase euros for me, then wire them to my sister-in-law in Belgium to pay my share of our house for the summer vacation rental, the money moves through a chain of perhaps six banks.  Each wants to know that after a clearing delay (as short as possible: zero would be best) its own local log is finalized.  We don’t want a lingering dependency period during which the ledger for the international branch of Chase Bank somehow can’t be audited for correctness without also auditing the one at Alternatives FCU in Ithaca.

But this seems solvable to me.  We could then eliminate proof of work (banks do charge fees for transactions, so those will avoid DDoS scenarios, and there is no anonymity, so the fairness aspect is moot).  We would simply have found a clean way to introduce Blockchain technology into standard banking, with or without cryptocurrency (honestly, I’m not s big believer in the stuff, but one can have Blockchain solutions for any kind of contract, and if you want to treat large numbers as commodities with value, who am I to stop you?  In fact the earliest banks operated precisely that way: “... just present this unforgeable document to my brother in Milan, and he will give you two gold florins”).  It would work just as well for crates of oranges, or contracts describing mortgage-backed securities.

Bottom line: my colleagues have shown that in effect, Bitcoin is currently a cartel, ultimately controlled by China. All that stuff about anonymity and fairness?  Basically, a hoax, except that the end users do seem to be anonymous, hence Bitcoin remains very helpful for drug transactions, prostitution, money laundering, international weapons sales.  Stuff like that, where real cash and credit is “awkward”.   Tax evasion.  Yet we can have Blockchain solutions without anonymity, and doing so allows high transaction rates, eliminates the monopoly data mining element, gets rid of the wasted power and cooling for all that SHA5 hashing, and if you want e-coins,  you can have them too.  

So it all comes down to the permissionless model, which in turn is ultimately a political statement by Satoshi Nakamoto, stemming from his distrust of fiat currencies and his views about global political structures.  He favors anonymity as a kind of enabler for anarchy, and envisioned a new global political system fueled by a fiat-free currency.  Yet his vision stumbles, we now see, on it’s substitution of computing power for political power, leaving China in control.  I myself would prefer to just have a system that really works (I pay my taxes, and don’t engage in money laundering or Bitcoin barter for illicit stuff).  If Bitcoin and anonymous Blockchain Systems are at risk of foreign domination and attack, I say: enough with this pretense of anonymity!  Let’s just go with Blockchains!

Attacking the blockchain

A recent paper by my colleagues showed that bitcoin mining’s dominated by about 20 computing farms, which apparently are located mostly in China.

This isn’t surprising: Blockchain mining centers on using special hardware (ASICs) designed to compute cryptographic hash values very rapidly, so a block chain mining cloud is just a massive array of these ASIC equipped computers.  These massive computing farms tend to be somewhat cheaper to build and operate in China, simply because the human costs of construction and management are low there.  It also helps to put them in places where electric power is cheap, and where cooling is easy to come by.  Turns out that China had all of these properties, and a big national semiconductor industry that designs and builds ASICS too.  (We aren’t talking about a sophisticated mathematical attack on the underlying cryptographic methods, just a brute force advantage that comes from owning more computers, and having more of these special hardware accelerators on them).

The question this raises is as follows:  what risks arise if some single country gains majority control over the Blockchain mining power for a particular currency?

Notice that we are talking here about a kind of brute-force control over the Blockchain.  Anyone could do it, by spending enough money on compute farms and specialized ASICs.  The key insight is that special hardware can be hundreds of thousands of times faster than desktop computing, for the kind of computation.  So you and your friends might run a Blockchain ledger on your home computers, and even configure them to crunch day and night trying to earn coins for you by extending the block chain, but because this involves solving cryptographic puzzles and the big farms collectively have millions of times more compute power, the probabilities favor those mining’s farms.  Most likely, those guys will win every single race to compute the next block, and pocket all the resulting coins.  So it isn’t a question of how many people are running the Blockchain software.  This is a story of how much compute power (and electric power, and money to build and operate the farm) you can dedicate.  The winner of that race will be the world leader in computing cryptographic hashes, and hence will dominate in extending the chain.  The issue arises for any Blockchain: Bitcoin, Ethereum, etc.

I talked this over with some friends who know their stuff, and thought I might share the list of weird attacks one can potentially launch once you have this sort of practical domination.

• Each new block is a set of transactions.  The dominating cartel could favor its own transactions, so that ones from less favored customers have very long clearing times, or perhaps never get logged at all.  They can effectively help friends and censor enemies: a big issue if the Blockchain is supposed to be fair.
• They could stop mining entirely.  This would cause chaos: new transactions would stop be logged, or be logged very, very slowly. The problem here is that the hardness of Blockchain schemes is a function of the mining power, so if the mining power suddenly drops drastically and the hardness remains the same, the rate of new blocks drops commensurately.
• As the main operators of the mining system, they would be in an unusual position to run compromised software, hence could collude among their farms, which is a way to further amplify the power of the cartel (there is a prior result by the Sirer and Eyal on this).
• They could  run two side-by-side Blockchains that start with the same prefix of blocks (by “forking” the original prefix), keeping one public and one secret.  Since they dominate the compute power by a large factor, they can run the public chain slowly, and the secret chain faster.  The secret chain will quickly become longer than the public one. Then one day they can suddenly release the secret chain.  This has the effect of rolling back every single block in the previously-public chain, because Blockchain software favors the longer chain.  So suddenly, every logged transaction in the public chain has been backed out!  This would allow double spending.  And such an attack could erase years of transactions.
• Same attack, but now suppose that the chain was also used to keep a ledger of contracts (for banking).  The rollback would effectively erase the tail of the ledger.  Those contracts might vanish entirely, or they could reappear at some other location or in some other order in the new chain (the previously secret one). Since some of the contract languages are state or order-sensitive, like hyperledger, this can change the meaning of the contracts. This risk arises because with hyperledger, one record can refer to a value defined in another record. 
• With knowledge of the secret chain, they could arbitrage.  For example, suppose that in the public chain, a million shares of Apple are sold at some price.  This might impact the actual share price of Apple.  But if the sale was erased in the secret chain, not only would we have chaos concerning ownership of the shares, we would also have impacted the price, and the attackers could exploit this knowledge to anticipate the impact and profit from it by placing bets in public exchanges, via futures contracts.

I bet this list isn’t exclusive.  Jump in with your own ideas!  But you can already see that basically, if you use Blockchain, you had better trust the operators of the majority of the mining power in the mining pool.  If you don’t, or if they turn on you, you could be seriously harmed down the road.

The bad news, obviously, is that apparently, today’s Blockchain systems are seriously at risk in this sense!