Blockchain consensus using a puzzle

In the previous article, we saw how we order transactions in a blockchain by hashing transactions. However, this alone doesn’t help achieve consensus as we haven’t found a way to solve the confusion we talked about in that article. In this article, we are going to see how we can solve this confusion and achieve consensus by introducing a puzzle.

In the last article, I mentioned that in practice, the restaurant will not accept my transaction immediately. This is because my transaction to the restaurant is in a branch. When a chain has branches, the transactions in the branches cannot be trusted because eventually only one branch will survive, and others will be disregarded.

But how do we decide which branch to keep and which branch to discard? We can simply select the longest of the branches and retain it while disregarding everything else. But this introduces a new issue.

In actuality, many thousands of transactions will take place each second, and our solution won’t scale well. As the participating nodes create more and more transactions, branches will keep branching exponentially. Soon, we will have too much confusion to resolve so much so that the blockchain will never be stable.

Resolving the confusion

How can we solve this? One way is to allow nodes to take turns performing their transaction. But without determining how many nodes are there, how do we decide the turn? In a blockchain network, any node can leave or enter at any time. So, this is impossible.

What if we can slow down the transactions? If we can make sure that we can only create one transaction per unit time, we can prevent exponential branching. But how do we slow down the transactions? It is by increasing the difficulty of creating a transaction.

So, how do we make creating transactions difficult? By introducing a puzzle! The first transaction to solve the puzzle gets approved and gets added to the ledger. But how long should it take?

How long should solving the puzzle take?

Let’s assume the time taken to crack a puzzle is t_create and it takes t_latency for all the nodes in the network to receive the transaction. If we consider a t_create value of 10s and a t_latency value of 60s, we will have 6 new transactions by the time all the nodes in the network receive the transaction that was created first. This means we may have up to 7 branches now. It’s not ideal but it’s not as bad as the situation before.

With fewer branches, there will be more stability. However, when we eventually choose one branch, the work that nodes put into the other branches is going to be wasted. Can we reduce this wastage? If so, how?

There are two parameters here—t_latency and t_create. You can see that the higher the t_latency value is, the higher the window for this wastage is. If the t_latency can be lowered, then we can reduce the number of transactions that end up getting discarded. But how do we lower t_latency? A paper written in 2013 claims that it takes 12.6 seconds to propagate to 95% of the network. In order to reduce this latency even further, we have to make structural and architectural changes to the network, which is impossible since you can’t have every node in the network make that change to their networks. In addition, there are technological limitations to increasing network speeds.

So, what can be done if we can’t reduce t_latency? If we can’t reduce t_latency, then the only option left to narrow down the window is to increase t_create, i.e., the time it takes to solve the puzzle.

Reducing wastage

Let’s look at the following table:

tcreate (s)	tlatency (s)	tlatency / tcreate * 100%
1	12.6	1260%
3	12.6	420%
5	12.6	252%
10	12.6	126%
15	12.6	84%
60	12.6	21%
300	12.6	4.2%
600	12.6	2.1%

The intuition here is that once we create a new transaction and broadcast it, the work nodes do to create new transactions before they receive the broadcast transaction is a waste of effort. We can express this wastage by dividing t_latency by t_create and expressing it as a percentage. As the table shows, we reduce the wastage by increasing t_create.

However, it may seem counterintuitive to increase the time it takes to create a transaction just so that we can reduce the ratio of the effort wasted in creating new transactions as nodes wait for the broadcast transaction. This is like a restaurant taking more time to prepare a dish so that the percentage of time spent during delivery to a customer is made to look small.

A time-consuming puzzle actually is good

But as you will see later, this longer time taken to create a transaction actually helps in increasing the robustness of our blockchain. To use the restaurant example once again, think of it as the restaurant using the longer time it takes to put more effort into the preparation of the dish, making it tastier.

Therefore, we cannot consider the effort nodes put into cracking the puzzle a waste. They invested their time and energy in a race to become the first to solve the puzzle. Running and losing a race is okay. But it will be foolish to run a race that is already over. Hence, a transaction trying to solve the puzzle after another transaction has already solved it is silly.

So, by increasing t_create, we make sure the effort that is wasted during the latency period is smaller in comparison to the effort put into solving the puzzle. Besides, when t_create is greater than t_latency, we make sure that nodes cannot create a new transaction during the latency period as the nodes will receive the broadcast transaction even before they can complete the puzzle.

Thus, we reduce wastage, increase stability and make the blockchain more robust by making it difficult to create new transactions. We make creating new transactions difficult using a puzzle. In the next article, we shall see how this puzzle works.