Sunday, September 18, 2016

Bitcoin: A Sequence of Proofs

Imagine a lawless land where only other lands' money was trusted. Doing business with them was slow, often hazardous. Theft was possible, because you paid people by giving them a copy of the key (credit card information) to your personal gold vault. This was unsafe, but you didn't know how to do commerce any other way. The point of sale needed to be instant, and the sale was often so far from home.
Now imagine, a new casino appeared which was larger than most amusement parks and wanted a stable internal currency for the significant transactions. In this lawless land, they didn't want to have people walking around with currency that could be stolen. They wanted something like gold, but they didn't want gold. They gave people checkbooks and promised them there was gold somewhere behind the money. As long as people believed in the added value, it existed. The economy grew and it became more valued for it's use as a currency.
Eventually, the casino was made non-profit. It had a controlled rate of releasing this new currency and started letting anybody work for it at any time of the day, paying them this currency.
The bank worked in an odd way. The volunteers watched customers' messages come up and ask for transactions to be made. They'd collect a certain quantity of them and go to check that they all followed the rules. They follow a specific policy for how to throw out transactions that can't happen at the same time. These transactions are signed with the customer's secrets, so they are definitely from the listed customers. After they check it, they store the correct transactions in-order in a signed envelope (Merkle tree) . They pay themselves a little bit at the start of each envelope, but customers also pay a little extra in the transaction for the worker. The worker must now go to the strangest machine in the land. 
The bank distributed a machine which examines the signed envelope and spits out a custom lottery game. This game was very slow, and the poor volunteer has to go through the process of playing the lottery until he wins. 
But it gets worse.
If another lottery player collected a copy of that same quantity of messages, they could also start playing the lottery. And they're almost certainly going to be. They might start before or after, but it doesn't really matter. A million losses doesn't make the next lottery ticket any more likely to be a winner. Each event is independent.
If they win first, then their envelope goes into the casino's history ledger and they get the reward they paid themselves. All of your lottery playing is for nothing.
We should clarify that lottery playing doesn't make anybody money when a loss occurs. This lottery is entirely done for the people and by the people. 
Eventually, people decided to team up and share the rewards. Big clubs of lottery players formed which promised a pay out equivalent to the work done. People were happy, and they played on. After a day's pay, they took their coin home and spread it far throughout the economy. 
Ordering of events in a distributed system is a hard problem. It's one of the hard problems in Computer Science. Even if all of the packets are sent in the same order to all peers, having multiple sources of events means that events are doomed to be reordered. Some of the time, this doesn't matter. Most of the internet is optimized around the idea of allowing unrelated transactions to be reordered and buffered. Unfortunately, sometimes it is necessary to have the entire network agree on a linear history.

This is the case in systems where exposed actions can make resources inaccessible. An example is currency; a person is only able to spend funds for the small window in time that they own them. Blockchain technologies form an explicit linear ordering of synchronized operations enforced in a distributed manner.

The name comes from the fact that the envelopes from the story above are called "blocks" in Bitcoin. Transactions fill blocks, which have lotteries played over them through proof-of-work. This process is called "mining". The democratic mob votes on a history of transactions to accept by gambling at hash values.

While the first lottery writer might have won a reward from the casino in our parable, the reward only holds if it holds in the longest chain of history. Good nodes will reject the invalid transaction history in the mined transaction chunk (block), and will collectively play the odds better than the bad actor. They will eventually catch up. The good history will grow larger, and the bad actor will lose it all.


The value of bitcoin is set by supply and demand, like everything else in economics. Relative prices for goods between currencies should be stable, else people label it arbitrage and abuse it until it is fixed. This means that the value of bitcoin is a consensus had by people on how much utility there is in being able to spend bitcoins. 

If people are willing to exchange 50 chickens for a bitcoin, then a bitcoin is worth your currency's equivalent of 50 chickens. If bitcoins are difficult to find in your corner of the world, then they might be worth more. 

Threat Model

Bitcoin's only tractable attack is an attack on the integrity of the blockchain's linear history. Bitcoin is a set of rules for creating a data structure, the blockchain. The rules assume that whomever owns the private key associated with bitcoins is the owner of the bitcoins. When the customer wants to place a transaction, they need to sign the transaction. The ability to sign a transaction is a proof that one has the private key associated with the public key that the bitcoin was last sent to. The "last sent to" part is the reason that a linear history is necessary.

If you try to spend bitcoin that has already been spent, the mining nodes will reject your message. The only real practical attack on the blockchain is to spend bitcoins at a vendor, get the service after the transaction is in the blockchain, and then mine a block that has you sending the bitcoin elsewhere. This "history rewriting" requires the attacker to do the proof-of-work for all blocks after the rewritten one. Bitcoin specifies that the longest chain is the one that is correct. This means that the attacker needs to outrace the rest of the network in order to convince them to accept the evil fork.

The farther back in history, the more work that an attacker must do to catch up with the rest of the network and overcome them. This means that after a number of blocks have been mined, transactions are more or less unable to be altered. This gives the system a consensus on the linear ordering of transactions. Note though that integrity depends on the majority of the network choosing a chain that can be verified.

Cryptography Used

Bitcoin uses HashCash for proof of work. HashCash works much like the lottery metraphor above. One has a block of information to hash, including a nonce that is the miner's current lottery guess. The work difficulty is set by requiring the worker's nonce make the SHA256 hash lower than a given value. The output hash will vary in an unpredictable way as the nonce is incremented, making this search a pseudorandom Poisson process. Bitcoin has a rather difficult proof of work. Every two weeks, the Bitcoin network calibrates the current proof-of-work difficulty to reflect capacities. 

The other major use of cryptography in Bitcoin is the use of public key cryptography to handle a person's account balance. The transaction sends the currency to a person's public key. The private key associated with this public key then gains the power of that currency. The funds holder can sign transactions and smart contracts with this key to express consent. 

Sequence of Proofs

That brings us to a powerful alternate view of the blockchain that is the reason why it generalizes. It's not a key-value store of bank balances. It's a sequence of proofs. The existence of the completed proof-of-work is proof of the existence of the payout coins. Every future transaction with the coins refers to the transaction which created the coins being spent. It is the burden of the network to assert that you are referring to the latest state of that resource.

Consider instead a system of games of chess with betting. Each transaction "pays" the turn to the next payer, with alteration. Checking board rules would fall to the miners. You can prevent turn alteration this way.

Consider instead a blockchain that began with a number of facts and implications, along with implications such as Modus Ponens. From these, you could make each transaction identify itself as a usage of a reasoning rule, and it could refer back to the pieces of data which inhabit it. The proof checking would only have to check the latest transaction, as the assumptions of the proof being fulfilled are asserted to be true because they are older than it in the blockchain. Reasoned, accountable arguments could be carried out this way.

Scalability Problems

The previous chess network would be miserable to use in all likelihood. If the proof-of-work is sufficiently hard, then it should take minutes to get a move accepted by the blockchain. Interactive applications seeking to use the blockchain run up against many issues. Current bitcoin mining even runs up against this problem. Long transaction times result from the throughput limitations built into the bitcoin network by setting the difficulty.

This difficulty pushes miners to turn toward pools. As mining pools control a larger and larger fraction of the world's mining power, the bitcoin network suddenly becomes dependent on these mining pools being good actors. The distributed system of bitcoin becomes a decentralized system, compromising many of the initial promises.

This stems from the fact that proof-of-work is inherently costly. There are other ways to address the problems of double spending, which we will cover. Most of the problems related to bitcoin is due to incorrect usage of bitcoin. Bitcoin is designed to be a ledger which has the last word. It promises linear, strong consistency between transactions on the blockchain. Many applications are alright with eventual consistency. We will see that it is possible to conduct business off of the blockchain which can then have the state at the end of the session persist. 


Proof of Stake And Tattling

A potential solution to the growing pains of Bitcoin is the use of proof-of-stake rather than proof-of-work. An attacker which has a stake in the history already on the blockchain is unlikely to jeopardize it. In proof-of-stake, the cryptocurrency is paid by the miners into the bets of the next block to win. If an attacker bets on multiple chains, then they're guaranteed to lose money. This, combined with the fact that buying a lot of currency is more expensive than a lot of computer power, makes proof-of-stake practical. We will cover Peercoin later, which does proof of stake and has other mitigations for certain attacks. 

An interesting idea is vote tattling. When an attacker votes on one block with a predecessor, and then votes on another with the same predecessor, peers can observe this. They can report double voting by using the votes as cryptographically-verified evidence, and taking the attacker's vote-money. 


Many times, entities want low-latency transactions over a short duration of time. Betting, bars, and moonlighting with frequent and small rewards are all examples. In order to achieve that, micropayment channels can be used. 

Bitcoin has the ability to represent fairly complex transactions, much more complex than simple money exchange. The transactions are written around a number of simple opcodes. One such opcode gives ability to hold locked funds until a certain timeframe has elapsed.  

Note also, that bitcoin transactions have their own meanings even before being entered in the blockcahin. These two facts allow people to set up a channel of payments. In a payment channel, the sender places a certain amount of money under time-lock. Until the time specified in the bitcoin transaction, the sender can't access their funds unless the receiver allows them to. Now the receiver can have the sender sign bitcoin transactions of increasingly larger value as the payments accumulate down the channel. 

None of these signed transactions are published until the channel is closed. When closed, the receiver publishes the latest signed transaction. It ends the time-lock and sends the confirmed funds to the receiver and refunds the remaining funds to the sender. If the receiver doesn't finish this handshake, and sacrifices their payments, then the transaction times out and the sender can do whatever they like with the locked funds. 


One issue that should be jumping out to the attentive reader is that bitcoin itself offers no anonymity. The public ledger has a timeline of all funds moved. People trying to replace other transaction mechanisms with bitcoin have to worry if the timing, quantities, frequency, and partners of bitcoin trades could give the world enough information to target them for abuse or persecution. This isn't the only problem; law enforcement might be able to convince miners to refuse to do business with your bitcoins. The Bitcoin system is not resilient to all kinds of attacks. 

Monero is to Bitcoin as Tor is to the public internet. It uses a ring signature to allow people trying to transact to use each other's input transactions instead. The interaction between people is randomized and mostly one-way, decreasing the possible attack surface. 

Monero fights the scalability effects on trust centralization due to mining pools in two ways. Monero doesn't allow for transaction fees to be set, instead making all blocks equally attractive to mine. This defeats a scaling issue which bitcoin will face when the reward for mining will come entirely from transaction fees. Secondly they obfuscate transactions to protect miners from effective legal demands. 

Related Resources


  1. This comment has been removed by the author.

  2. The difficulty with proof-of-stake is that it's not clear that it's possible to achieve, even if the "nothing at stake" problem is addressed. The fundamental challenge is to ensure that a staker can't increase profits by spending energy. If the staker can do so, then it's not PoS, but a highly complex PoW algorithm that superficially resembles PoS. To the best of my knowledge, no PoS algorithm has been proven to have this property (but would love to learn otherwise!).

    EDIT: missing a word