Blockchain & Cryptocurrency #8: Consensus without Identity: the Blockchain

In this post we will discuss in more details the Bitcoin's consensus algorithm. We will see how it is possible to reach consensus without identity through the blockchain.

Nodes and identities

Nodes without persistent identity

We will have to keep in mind that Bitcoin nodes don't have any persistent long term identities. This is another difference from how traditional distributive consensus algorithms operate. If nodes had identities, it would make things a lot easier:

• it would be possible to include in the protocol specific references to nodes IDs.
• the system would be more secure. If nodes were identified and weren't able to create new identities, we could make assumption on malicious nodes and try to eliminate them from the network, to be sure that at least 50% of them are not malicious.

Why Bitcoin nodes don't have identities?

There are a couple of reasons why Bitcoin nodes don't have identities:

• Bitcoin protocol is a peer-to-peer decentralized system. So there is no central authority that assignes identities to nodes and verify that they're not creating new nodes. This could take to a Sybils attack: malicious nodes could create a lot of copies of nodes all controlled by them to look like there are a lot of different participants. When in fact, all those pseudo participants are really controlled by the same adversary.
• Pseudo-anonimity is a goal of Bitcoin, so it doesn't assign an immutable identity even if it could be possible also in a decentralized system. Bitcoin doesn't provide a strong anonymity, since different transactions of the same subject can probably be linked together. But, at the same time, it is not necessary to use a real identity to take part to the network. So an adversary could trace the transactions and connect them to an "address", but it would be harder to understand who is really making that transactions.

Ability to check a random node

Even if the Bitcoin nodes don't have an immutable identity we can make one assumption. We can suppose to have the ability to pick a random node and check it. It is similar to systems such as lotteries where people are tracked and verified not through their real identity, but through a ticket or a token assigned to them to take part in the game.

For the moment we will assume that there's a similar token generation and distribution also in Bitcoin protocol. This protocol will assure that if an adversary tries to create a lot of civil nodes, all of them will just get one token. So the adversary is not able to multiply his power that way.

We will see later that it is legitimate to make this assumption.

Implicit consensus

Under the assumption of random node selection, it is possible to reach implicit consensus. Let's identify a round as the insertion of a new block in the blockchain. In each round a random node is somehow selected, and this node will be able to propose the next block in to be inserted in the blockchain.

There is no consensus algorithm and no voting. This node simply unilaterally proposes what the next block in the block chain is going to be. If the node is a malicious one, other nodes will implicitly accept its block or reject it. The acceptance is implicit because:

• if other nodes consider the new block valid, they will extend the blockchain starting from this block
• while if other nodes want to reject the new block, they will continue the blockchain starting from the previous one

It's easy to manage this choice, since every new block in the blockchain has a hash pointer to the previous one. Except for the simplification regarding node selection, this is close to how Bitcoin actually works.

Consensus algorithm

So, here's a semplified version of consensus algorithm for Bitcoin:

1. When Alice wants to pay Bob, she creates a transaction and broadcasts it to all of the nodes.
2. Each node is constantly listening to the network and collecting a list of transactions not yet inserted into the blockchain.
3. at some point, one of these nodes is chosen randomly to propose the next block. It will put in the new block a bunch of transaction and add it to the blockchain. This node can be honest, or malicious and try to insert some invalid transactions. For example it could insert transaction with non-valid signature or with coins already spent.
4. the other nodes will accept this block or reject it, by either including the hash of this latest block in their next block or ignoring it. The block is accepted only if all the transaction in it are valid.

Why the consensus algorithm works?

Let's see how can a malicious adversary try to subvert this process. If Alice is a malicious attacker, she could try to:

• steal Bitcoins belonging to another user. She is not able to do this, because she cannot forge someone else's signature.
• act against another user Bob. For example Alice could try not to insert any Bob's transactions into new blocks. But there will be other honest nodes that will gather Bob's transaction into a new block.
• try to spend some coins twice (double-spending attack).

Double-spending attack

Suppose that Alice creates a Bitcoin transaction to pay some online service offered by Bob. Some honest node will verify and insert it into the blockchain. This transaction will contain Alice signature, the reference to the coins for Bob, and a hash. This hash is a reference to a previous transaction CA where Alice received the coin from someone else. So Bob sees that the transaction is validated and provides the service to Alice. Suppose that the node that has to insert the next block is controlled by Alice. She could propose another block containing a transaction to send the same coins used to pay Bob to address A', also controlled by Alice. This is a new transaction referring to the same previous transaction CA.

Can double-spending attack succeed?

Which of the two blocks is valid? The valid one is the one followed by next blocks inserted by other nodes. Honest nodes always extend the longest valid branch. But, which of these is the longest valid branch?

From a moral point of view the green and red transactions might look very different. The first one is an attempt by Alice to pay Bob. Whereas the second is an attempt by Alice to defraud Bob and pay coins back to herself. But, from a technical point of view, these two transactions are identical. The nodes looking at them have no way to tell which one is the "legitimate" transaction.

Nodes often follow the heuristic rule of extending the block that they first heard about. But we have seen that there's no global time in Bitcoin network due to latency. So, suppose that the next node extends the block with the red transaction instead of the green one. The following blocks will be very likely attached to this last one, and the block with the green transaction gets ignored by the network and become an orphan block. So, at this point, it seems that the double-spending attack succeded.

How can Bob protect himself from double-spending attack?

Bob can consider Alice transaction valid at different times:

• 0-confirmation transaction: Bob is listening the Bitcoin network and can accept Alice payment as soon as he hears about the transaction. This leads to an even more basic double spending attack than the one described before. If Bob allows Alice to access the service before the transaction receives even a single confirmation on the blockchain, then Alice can immediately make a double-spend transaction. And an honest node may include it in the next block instead of the transaction that pays Bob.
• 1-confirmation transaction: Bob accepts Alice transaction after the block is inserted into the blockchain as described in previous paragraph.
• 3-confirmation transaction: Bob waits to see if the following blocks in the blockchain are attached to the block containing its transaction, before allowing Alice to access the service.

6-confirmation transaction

The more confirmations his transaction gets, the higher is the probability that it is going to end up on the long term consensus chain. In fact, honest nodes will always follow the longest chain. So the only chance that the transaction will be invalidated is that k malicious nodes are chosen to insert the following k blocks and continue the shorter chain. The probability that this happens decreases esponentially with the length k of the longest chain.

In the Bitcoin ecosystem, the rule is to wait for six confirmations. There is nothing really special about the number six. It's just a good trade-off between the amount of time you have to wait and your guarantee that the transaction you're interested in ends up on the consensus block chain.