cșerb

cserb.net — blockchain, crystal-lang, startups

Build your first blockchain from scratch (#1 Probabilistic Finality)

Posted at — Oct 31, 2019

Introduction

I won’t be able to cover all aspects in detail, neither is it intended. You should rather make yourself familiar with the high level concept of how a blockchain works. As kind of a reference point you should be familiar with Andreas Antonopoulos’ book Mastering Bitcoin, which if needed covers quite some detail.

Understanding how e.g. Bitcoin works doesn’t necessarily give you the insight on how to actually build your own blockchain. So I will try to focus during the series solely on the aspects of engineering and will reference to videos, blog articles or to Mastering Bitcoin when it might be of help.

Think of the series as a walkthrough. You can follow along and end up with your own blockchain, but you need to do your homework to fully grasp the non-technical side of blockchain.

Let’s start with one of the hardest parts of blockchain: Probabilistic Finality. It’s at the core of the consensus mechanism and depends on multiple concepts that come together to achieve probabilistic finality.

1. Probabilistic Finality

Finality is the agreement that a valid transaction between A and B has been executed and can’t be reverted. If A uses a Visa card to buy coffee from B, B trusts its bank that the agreement the bank made with Visa will ensure a finalized transaction.

In a decentralized network the trust is given to the majority of the participants (nodes in our case) and we find out what is considered finalized by looking at how the majority sees the state of the transaction.

Learn more about it here: On Settlement Finality, Finality in Blockchain Consensus [video]

So how do we “implement finality” in our blockchain?

Imagine you are a node within our blockchain network. Your node is maintaining a copy of the blockchain data and at the moment it’s waiting for the next block to be propagated. Current block is #3000 and #3001 should arrive soon. But because there are multiple miners there is a chance you will receive 2 versions of #3001. Which one to choose?

Alt Text

The example above shows how the current tip of the blockchain could look like after we received 2 versions of block #3001. In the end we don’t choose any of the propagated #3001 blocks, but wait for several more consecutive blocks to make a decision.

To understand why waiting makes sense we also need to understand Proof of Work (PoW).

2. Proof of Work (PoW)

PoW is the algorithm that makes mining possible. It is usually explained by what it does:

In the simplest terms, mining is the process of hashing the block header repeatedly, changing one parameter, until the resulting hash matches a specific target. The hash function’s result cannot be determined in advance, nor can a pattern be created that will produce a specific hash value. (from Mastering Bitcoin)

But more than by what it does, we need to understand what it’s used for. The game theoretic aspect is one of its use cases, that we will cover later. It is important for finality, but not so much for the engineering part.

PoW is also used for randomness and we are very much interested in that part, so that we can implement finality.

Imagine 3 miners embark on the mission to mine the next block. All 3 look for a different solution, since the block header they constructed is unique and because of that the time it takes to mine is more or less random.

Another way to think about mining is by imagining a race, where each participant has a different predetermined, but unknown, finish line. Thus the time it takes to reach the finish line is unpredictable and random.

2.1 Randomness

Let’s find out what would happen if we build a blockchain without PoW. If every node in the network would have the ability to create a block instantly, it would look like in the example below

Alt Text

Multiple miners will create a block at the same time and broadcast it to the network. It would be impossible to reach consensus, if for each round T all blocks of Tn would be propagated at the same time.

It can still happen that different miners find the next block at the same time (see example below), but at some point the chances that only one miner will find the next block are very high (because of the randomness in PoW) and as a consequence we can consider the chain of B1.1-> B2.1->B3.1->B4.1->B5.1 as the longest one. Also we can decide to finalize block B2.1 if we want.

Alt Text

Note: Block 4.2 has been abandoned mid-mining because it just wasn’t fast enough. So there is no reason to waste more energy on it.

3. Conclusion

In order to reach probabilistic finality we need to make our nodes agree on the longest chain and the mechanism that enables this is PoW. There is much more to PoW, but for now we don’t need to cover that.

4. Next Up

In the next article will find out how a Directed Acyclic Graph works and why we need it to find the longest chain.

Part #2: DAGs