How to Write Your Own Blockchain

The surest way to truly understand a technology like blockchain is still to code your own implementation. This is a journey I undertook last spring, and now I am writing up what I learned. While reading this guide will never give you the same insight and understanding gained by the blood, sweat, and tears of implementing it yourself—I do hope that it can help you on that journey.

The results of my labours is my blockchain for research named Dunsinane.¹ You can check it out on GitHub.

The Blockchain as P2P Network ​

In essence, a blockchain is a distributed datastructure shared by a network of peers (nodes), also refered to as a ledger. The ledger is a chain of blocks each containing a number of grouped transactions. Different nodes can append transactions to this shared ledger in such a way that it is always consistently replicated, has no central coordination, and is append-only. As we implement our blockchain we will follow the transactions through the entire "append" process.

Nodes in the blockchain network can perform various classes. Typically nodes are differentiated into three classes; full nodes, light nodes, and miner nodes. Depending on the implementation nodes can be divided into even more variations, such as archival nodes, validator nodes, master nodes, etc.

Full nodes are critical to the blockchain algorithm. These nodes usually store the entire history of the ledger from the genesis block to the latest block. Full nodes may also construct and propose new blocks, however, not all full nodes are block proposers. Maintaining a copy of the entire ledger allows full nodes to trust no external sources, and validate everything themselves. This trustless constraint is essential to the idea of the blockchain.

As the name suggests, light nodes are more lightweight versions of full nodes designed for speed and efficiency. They only keep a limited piece of the ledger, usually only the block headers. Block headers record the validity of a block but not the actual data, this must be provided by the full nodes. This means that light nodes are not fully trustless, they are forced to trust full nodes for the transaction data.

Finally, the miner nodes are responsible for validating transactions and generating new blocks for the ledger. These nodes perform the work in the proof of work consensus algorithm. In order to validate and mine these nodes also need to keep a full copy of the ledger, so they are full nodes with additional capabilities.

Implementation: nodes ​

In our Rust implementation we only have two types of nodes, full and light.

pub enum NodeMode { Full, Light, }

Miner nodes are full nodes that also implement the Miner trait. The miner receives a candidate block whose transactions have already been selected and validated. Blocks with invalid transactions are rejected outright.

pub trait Miner: Send + Sync {
    fn mine(&self,
        candidate: Block,
        context: &MiningContext,
    ) -> Result<Block>;
}

The mine functions is a general abstraction for producing validated blocks. It's implementation depends on the consensus algorithm used. Later in this post I will show how to implement both proof of work and proof of authority.

Similar to the Miner trait, full nodes that function as block proposers implement the BlockProposer trait.

pub trait BlockProposer { /* More on this later. */ }

Coordination between Peers ​

To understand how the nodes and the miners work, we need to look at how transactions are generated and grouped into blocks. In practices, transactions are often generated and signed by user applications (clients), before being sent to a single node. For simplicities sake, we leave out the clients in this story and assume all full nodes (including miners) can generate and sign new transactions. Transactions are cryptographically signed so they cannot be altered after creation.

Unconfirmed transactions are kept in a local cache on the node called the mempool.² In blockchain literature the mempool is often used to denote all currently pending transactions in the network. To avoid confusion, we will refer to this as the global mempool.

Remember we are working with an asynchronous network, and nodes need to broadcast new transactions through this network. Since a blockchain has no central coordination mechanism, this presents a serious coordination challenge. Specifically there are many local mempools that can each have a different view of the global mempool.

Blockchains permits these inconsistent views among nodes, only the ledger has to be consistent. This allows mempools to continuously accumulate pending transactions worrying about coordination. This in turn provides block proposers a steady stream of pending transactions from which to choose when creating a new block.

Implementation: Mempools ​

While the idea of a local transaction cache is a simple one, there is a lot of machinery connected to mempools. Firstly, they need to broadcast records to peers. Secondly, mempools cannot hold infinite records, therefore nodes need to have an admission policy and lifecycle rules. Many of the details here are very nitty gritty, but they can have an impact on the selected transactions and their ordering in mined blocks.

For Dunsinane we keep things simple. Each full node maintains a mempool, which all have the same basic operations. A mempool only contains a vector of mempool entries.

pub struct Mempool {
    transactions: Vec<MempoolEntry>,
}

pub struct MempoolEntry {
    pub transaction: TransactionKind,
    pub inserted_at: u64,
}

The basic operations of a mempool are: insert, replace, and is_full.

impl Mempool {
    fn is_full(&self) { ... }

    fn len(&self) -> usize { ... }

    fn insert(
        &mut self,
        index: usize,
        transaction: TransactionKind) { ... }
    
    fn replace(
        &mut self,
        Vec<MempoolEntry>) { ... }
}

Each node manages their mempool directly. How they do this is abstract into a MempoolPolicy. This allows dunsinane to easily add more complex policies, and benchmarking and comparing different policies. Any policy is responsible for defining how to handle three different aspects of the transaction's lifecycle in the mempool as shown below in Figure 1.

In Rust we codefy these responsibilities as three methods in the MempoolPolicy trait: admit, select, and maintain. Each method receives the mempool and any additionally needed arguments.

pub trait MempoolPolicy {
    fn admit(
        &self,
        mempool: &Mempool,
        transaction: &TransactionKind,
    ) -> bool;
    
    fn maintain(
        &mut self,
        mempool: &mut Mempool,
        contex: &NodeContext,
    ) -> Vec<MempoolEntry>;
    
    fn order(
        &self,
        mempool: &Mempool,
        transaction: &TransactionKind,
        context: &NodeContext,
    ) -> usize;
}

The admit method receives a transaction and returns a boolean with it's decision whether to admit it to the mempool. Transactions are of the TransactionKind type since we will have multiple types of transactions, more on that later.

The maintain method receives a NodeContext object that contains context information relevant to the maintainance operation. It returns the new cleaned up transaction list as a vector.

The order method receives the new transaction to add, together with the NodeContext. It returns the index at which the transaction should be inserted into the mempool. This allows the node to preserve the ordering defined by the policy without rebuilding the entire transaction vector.

self.mempool.insert(
    self.mempool_policy.order(
        &self.mempool, 
        transaction, 
        &self.context,
    ),
    transaction
);

As you can see, the managing of the mempool in a node is decoupled from the policy. This allows us to easily change or extend the policy without needing to touch the node's internal code.

Implementation: Remove Stale Policy ​

Now as an example, the simplest mempool policy is to simply accept all incoming transactions, keep transactions in the order they arrive, and remove stale transactions. In Dunsinane this looks as follows.

We first define the policy struct with its possible configuration parameters. In this example we can only configure the age at which a transaction becomes stale.

pub struct RemoveStale {
    pub max_age: u64,
}

The admit method is trivial since it always returns true unless the mempool is full. It simply returns !mempool.is_full().

Similarly the select function is straightforward, it simply returns the length of the current mempool: mempool.len().

The maintain function simply calculates a cutoff timestamp based on the max_age, and filters out transactions beyond this cutoff.

impl MempoolPolicy for RemoveStale {
    /* ... */

    fn maintain(
        &mut self,
        mempool: &mut Mempool,
        current_time: u64,
    ) -> Vec<MempoolEntry> {
        let cutoff = current_time.saturating_sub(self.max_age);  

        std::mem::take(&mut mempool.transactions)                
            .into_iter()                                         
            .filter(|entry| entry.inserted_at >= cutoff)         
            .collect()                                           
    }

    /* ... */
}

As you can imagine, the mempool policy can greatly impact the performance of a blockchain. More on this at the end of this article.

Implementation: Transactions ​

Now in all of this we have left out the details for transactions. Classically, transactions in blockchains are transfers of value between accounts. However, today smartcontracts represent an important part of blockchain technology. Interactions with these smart contracts present a new type of transactions.

In Dunsinane, we have three kinds of transactions on the chain: a transfer, contract creation, and method call on a contract. We group all these kinds of transactions under a single sum type³: TransactionKind.

pub enum TransactionKind {
    Transfer(Transfer),
    Contract(Contract),
    ContractCall(ContractCall),
}

General methods for transactions are defined under the Transaction trait. For each kind needs to implement this trait as well as the the From<T> trait for the TransactionKind. For simplicity we will focus on transfers for now.

Remember blockchain is in essence a replicated ledger that records transactions between different accounts. Accounts are typically called wallets in the blockchain ecosystem and each have a unique address. So a transfer moves a certain amount of a currency from the owners address to the recipients.

As we mentioned before, when creating a transaction the owner also signs it using their own private key. At it's core signing works as follows. The owner creates a cryptographic hash of the transaction's content and signs that hash using their private key. The resulting signature is included in the transaction so anyone can recompute the cryptographic hash and verify the signature using the owner's public key. This simple setup gives transactions three very important cryptographic properties.

In the implementation, the Transfer struct is pretty straightforward.⁴

pub struct Transfer {
    owner: Address,
    recipient: Address,
    amount: u64,
    signature: Signature,
    public_key: PublicKey,
}

The three typical operations on any transaction are (1) computing its hash, (2) retrieving the owner's address, and (3) validating its fields and signature. These operations are not specific to transfers. In other words our generic Transaction trait has to support the following methods.

pub trait Transaction {
    fn owner(&self) -> &Address;

    fn validate(&self) -> Result<()>;

    fn hash(&self) -> Hash;
}

The owner and hash functions are self-explanatory. The validate function returns a std::result rather than a boolean value since the validation can fail for different reasons, and this type allows us to return different kinds of errors.

Now that we have a good understanding of transactions and mempools, we can finally have a peak at the engine behind every blockchain: the consensus algorithm. We will start with the construction of blocks.

The Blocks in Blockchain ​

Let us quickly reiterate what a consensus algorithm is for exactly. In our distributed trustless blockchain network, there are many nodes with each their own mempool. While there are many mempools, there is only one valid version of the replicated ledger. New transactions that want to be appended to this ledger are broadcast through the network. Every mempool can have a slightly different view of all currently pending transactions. This inconsistency forms a huge problem when the ledger clearly has to remain consistent—we have a classic coordination problem.

The Block Proposer Election Problem ​

In essence a blockchain resolves the coordination problem by having certain peers, called block proposers, create candidate blocks. Candidate blocks are broadcasts into the network. However, only one of these blocks can be the next in the chain. Or in other words, only one block proposer can be elected to append their candidate block to the chain. In literature this is often refered to as the leader election problem.

A blockchain network reaches a consensus in the leader election in a trustless way without direct coordination. There are many different consensus algorithm to solve the leader election problem. For instance, in the classic proof of work the leader is elected based on compute power.

Regardless of the consensus algorithm deployed, the leader election starts with the construction of new candidate blocks.

Block Construction ​

At a steady pace⁵, block proposer nodes select a number of transactions from the mempool based on certain selection criteria and bundle them into a new candidate block.

Just like transactions, blocks need to be cryptographically hashed. Not just for signing, but many consensus algorithms require this too. Additionally, we often want to check whether a transaction is part of a block. For large collections, straight hashing makes this far too inefficient since it demands recomputing the entire hash from all transactions. To solve this problem blocks use a tailored datastructure called a Merkle tree.

A Merkle tree organises the transactions into the leaves of a tree. Every other node in the tree is the hash of its children, all the way to the root. The top hash in the root is then a unique hash that can be used to verify all the data in the leaf nodes of the tree in one go.

A block then contains a header with its merkle root, the proposer's public key, and the signature of the block. This is nearly all the information light nodes need to validate blocks. Blocks are chained on the ledger so we also need to know what the previous block is, even for candidates. The header therefore also includes the hash of the previous block.

The header includes a final nonce value (number used once), this is a unique value that is crucial to some consensus algorithms. A nonce is a standard cryptographical device. It is a random or pseudo-random number that can only be used once.

In some consensus algorithms such as proof of work, the nonce value is repeatedly altered. This means we cannot sign the header until a block is validated and selected to be appended to the blockchain.

The full block additionally contains the list of transactions alongside the header.

After reaching consensus on the next block, the proposer node signs the block's header in the same way transactions are signed by their owner. Not all blockchains require this step, but Dunsinane does perform it every time regardless of the deployed algorithm.

The proposer's signature authenticates the signed block header. By recomputing the Merkle root, a full node can verify that the block's transaction list matches the root, while light nodes can use Merkle proofs to verify the inclusion of individual transactions. Transaction and block validity must still be checked separately.

Implementation: Blocks ​

The implementation of blocks in Dunsinane is straightforward. The struct implements exactly the structure shown in Figure 3.

pub struct BlockHeader {
    pub merkle_root: Hash,
    pub signature: Signature,
    pub proposer: PublicKey,
    pub nonce: u64,
    pub previous: Hash,
}

pub struct Block {
    pub header: BlockHeader,
    pub transactions: Vec<TransactionKind>,
}

We further implement a few utility functions that help when implementing the consensus algorithms. These includes hashing the block header, or validating the correct structure of the block.

impl Block {
    pub fn validate(&self) -> Result<()> { ... }

    pub fn compute_header_hash(&self) -> &Hash { ... }
}

The Engine: the Consensus Algorithm ​

So far in the lifecycle of our transaction, they have been broadcast through a P2P network where they waited in mempools to be selected by block proposer nodes. At this point the transaction has been grouped into a candidate block with a load of other transactions. Next, the network uses it's specific consensus algorithm to choose which candidate block is appended to the chain.

The Goal: Validation ​

No matter the specifics of a blockchain's consensus algorithm, it is in essence a race between peers to validate the next block. Many candidate blocks can compete in this race, and many nodes in the network can attempt to validate a block. In the end only one peer can win, this is the elected leader. Their winning block, now validated, will be appended to the ledger.

There are many different consensus algorithms, you have probably heard of many of these; proof of work, proof of authority, proof of stake, proof of history, and so on. Let's look at the original to understand how they work.

Proof of Work ​

The classical consensus algorithm is called Proof of Work (PoW). Proof of work was proposed as a basis for consensus in the infamous Bitcoin white paper by Satoshi Nakamoto.⁶ It remains the consensus algorithm used by bitcoin today.

In PoW leaders are elected based on computational power. This is where miner nodes come in. Miner nodes attempt to validate the next block before anyone else in return for a monetary reward (in bitcoin or another cryptocurrency). In order to validate a candidate block a miner needs to solve a complex cryptographic puzzle, and thereby prove to other verifiers that a certain amount of computation was performed.

The cryptographic puzzle is where the nonce value in the block header comes in. In order to win the leader election, a miner must provide a block with a hash that starts with a specific number of leading zeros. This number is the network's difficulty target. Miners try to find such a hash by tweaking the nonce value in the block header. In other words, mining is a race between peers to find a nonce value that meets the network's difficulty.

Why is this proof of work? The proof relies on the strength of the cryptographic hash function. The output of such a hash function is impossible to predict, hence miners must find the satisfactory nonce value by trial and error. For an appriopriate difficulty, miners must guess and test billions of nonce values until one hits the winning combination. Providing a solution therefore presents a proof that a miner did in fact runs such vast amounts of tests.

This is a simplified version. In Bitcoin for instance the difficulty setting works slightly differently and is automatically raised or lowered every two weeks. The simple version works well enough for our purposes however. Ignoring a few details, this is in fact precisely how PoW is implemented in Dunsinane.

Implementation: Proof of Work ​

Consensus in Dunsinane is modeled as a simple trait with only two functions: validate_block to verify the validity of a block, and mine to find a valid nonce.

pub trait Consensus: Send + Sync + ConsensusRules {
    fn mine(&self, block: &mut Block) -> Result<()>;

    fn validate_block(&self, block: &Block) -> Result<()> {
        block.validate()?;
        self.validate_consensus_rules(block)
    }
}

pub trait ConsensusRules {
    fn validate_consensus_rules(&self, block: &Block) -> Result<()>;
}

The block validation is the same for all consensus implementations, since each can implement their specific rules using the ConsensusRules trait. Validation is then merely the checking of those rules against a structurally valid block.

The mining strategy of Dunsinane nodes is very simple. A node simply starts from 0 and increments the nonce by one until the hash matches the set difficulty.

impl Consensus for ProofOfWork {
    fn mine(&self, block: &mut Block) -> Result<()> {
        let mut nonce = 0u64;
        loop {
            block.header.nonce = nonce;
            let hash = block.compute_header_hash();
            if self.meets_difficulty(&hash) {
                return Ok(());
            }
            nonce += 1;
        }
    }
}

In the PoW implementation, Dunsinane uses single SHA-256 hashing, and the default difficulty is set very low at 16. Checking whether the hash meets the difficulty is very simple. The SHA-256 hash is an array of 32 bytes. Using some Rust twiddling we can easily count the leading zeros and compare it to the difficulty treshold.

impl ProofOfWork {
    fn meets_difficulty(&self, block: &Block) -> bool {
        hash.iter()
            .position(|&byte| byte != 0)
            .map_or(256, |i| i as u32 * 8 + hash[i].leading_zeros())
            >= self.difficulty
    }
}

Proof of Authority ​

Proof of Authority (PoA) breaks with many of the assumptions of blockchains. In PoA leader election is based on the reputation and authority of block proposers. The network is no longer purely trustless peer-to-peer. In fact the validators authorised to built and validate blocks are often appointed by a centralised authority. This breaks the entirely decentralised constraint at the core of many blockchains.

By breaking with these assumptions PoA is freed from many constraints and can achieve comparatively fast block time. Block time measures the average time of a network to validate the next block in the chain. It is a standard way to measure blockchain efficiency. Therefore, PoA can present a good trade-off between centralisation and efficiency. In fact it is actively used by quite a number of blockchains.

In Dunsinane, the PoA algorithm is used as a simple placeholder algorithm. Validation relies purely on authority, so there is no leader election. The nonce value in every header is kept at zero, and the first candidate block is automatically selected.

Implementation: Proof of Authority ​

This means that for our Rust implementation the mining functions always succeeds. The entire implementation of PoA is the following simple function.

impl Consensus for ProofOfAuthority {
    fn mine(&self, block: &mut Block) -> Result<()> {
        // PoA doesn't require mining; just set a deterministic nonce
        block.set_nonce(0);
        Ok(())
    }
}

What's Next? ​

This post took a lot longer to write then I imagined. It became a lot longer as well. If you made it this far, thank you. I would like to have included a section on smartcontracts, but that will now get it's own post.