DEV Community: Dmytro Svynarenko

Designing Blockchain #4: Merkle Trees and State Verification

Dmytro Svynarenko — Thu, 15 Jan 2026 18:16:10 +0000

Intro

In the previous article, we secured our Fleming blockchain by implementing cryptographic signatures and wallets, ensuring that only legitimate account owners can authorise transactions. However, if you remember from the second article, we left a critical architectural problem unresolved: storing the full state in every block is extremely wasteful and doesn't scale well.

Let's understand the magnitude of this problem. In our current implementation, each block contains a complete copy of the entire blockchain state — a HashMap<Address, u64> where Address is a String ("0x" prefix + 40 hex characters = 42 bytes) and balance is a u64 (8 bytes). That's 50 bytes per account just for the data itself, not counting HashMap's internal overhead. If our blockchain has 1,000,000 accounts, each block stores at least 50 MB of state data. Now imagine we have 10,000 blocks in our chain. That's 500 GB just for storing redundant state copies! And the problem compounds exponentially as both the number of accounts and blocks grow.

This memory inefficiency makes our blockchain impractical for any real-world application. We need a way to represent the entire state compactly while still being able to verify individual account balances. The solution comes from cryptographic data structures called Merkle Trees.

In this article, we'll explore how Merkle Trees work, discover why a simple binary tree isn't enough for our needs, and implement a data structure that allows us to represent millions of accounts with just a single 32-byte hash. We'll also see how to cryptographically prove that a specific account exists in the state without revealing the entire state data. By the end, instead of storing megabytes of redundant state in each block, we'll store just 32 bytes.

Tree Data Structures

Before diving into Merkle Trees, let's establish what tree data structures are and why they're useful for blockchain.

A tree is a hierarchical data structure consisting of nodes connected by edges. Each tree has a root node at the top, and every node can have zero or more child nodes. Nodes without children are called leaf nodes. Trees enable efficient O(log N) operations — with 1,000,000 elements, you might only need to traverse 20 levels instead of checking all million elements linearly.

A trie (pronounced "try", from retrieval) is a specialized type of tree where the path from root to a node represents a key. The key difference from regular trees: in a trie, keys are broken down into individual components (characters, nibbles, or bits), and nodes share common prefixes.

Here's a simple example storing words "cat", "car", and "dog":

    root
   /    \
  c      d
  |      |
  a      o
 / \     |
t   r    g

Notice how "cat" and "car" share the path root→c→a, saving space. This prefix-sharing property makes tries perfect for blockchain addresses.

For blockchain, we use hexadecimal tries where each level of the tree represents one hex character (0-9, a-f). Since our addresses are hex strings like "0x3a7f...", we can naturally traverse the trie by following the hex characters:

Address: 0x3a7f...

     root
    / | \
   3  a  f  ...
   |
   a
   |
   7
   |
   f

Each node can have up to 16 children (one for each hex digit). This structure is perfect for organizing blockchain addresses efficiently.

Merkle Trees

A Merkle Tree (also known as a hash tree) is a tree data structure where every leaf node contains a hash of some data, and every non-leaf node contains a hash of its child nodes. This structure was invented by Ralph Merkle in 1979 and has become fundamental to blockchain technology.

Let's build up the concept step by step. Imagine we have four accounts in our blockchain state:

Account A: balance = 100
Account B: balance = 50
Account C: balance = 75
Account D: balance = 200

Instead of storing this data directly, we create a binary tree of hashes:

             ROOT HASH
            /          \
           /            \
       H(AB)            H(CD)
      /    \           /    \
     /      \         /      \
  H(A)    H(B)     H(C)    H(D)
   |       |        |        |
A:100    B:50     C:75    D:200

At the bottom level (leaf nodes), we hash each account's data. For example, H(A) = SHA256("A" + "100"). Then we move up the tree, combining pairs of hashes: H(AB) = SHA256(H(A) + H(B)). We continue this process until we reach a single hash at the top — the Merkle Root.

The Merkle Root is a single 32-byte hash that uniquely represents all the data in the tree. If any account balance changes — even by a single coin — the root hash changes completely. This is the cryptographic property we need: a compact fingerprint of the entire state.

Now here's the powerful part: we can prove that a specific account exists in the state without revealing all the other accounts. This is called a Merkle Proof.

Merkle Proof

Let's say someone asks: "Does account B with balance 50 exist in this state?" Instead of showing them all four accounts, we provide a Merkle Proof — just the minimum set of hashes needed to verify the data.

For account B, the proof would be:

Proof = {
  leaf_hash: H(B),
  siblings: [H(A), H(CD)]
}

The verifier can then:

Start with H(B) — the hash of account B's data
Combine with H(A) to get H(AB)
Combine H(AB) with H(CD) to get the ROOT HASH
Compare this computed root with the root stored in the block header

If they match, the proof is valid — account B definitely exists in this state. If the account data was tampered with, or if it doesn't exist in the state, the computed root wouldn't match.

The beauty is that the proof size grows logarithmically with the number of accounts. For 1,000,000 accounts in a binary tree, you only need about 20 hashes (log₂ 1,000,000 ≈ 20) to prove any single account — that's just 640 bytes instead of 50 MB!

Merkle Tree vs Merkle Trie

Before we continue, it's important to clarify the terminology, as these terms are often used interchangeably but refer to different structures:

A Merkle Tree is a general hash tree where the structure can be arbitrary. The classic example is Bitcoin's binary Merkle Tree — transactions are grouped pairwise, hashed together, and combined bottom-up until reaching a single root. The tree structure doesn't encode any information about the data itself; it's just an efficient way to hash a list of items.

A Merkle Trie (or Merkle Patricia Trie) is a specific type of Merkle Tree where the path from root to leaf encodes the key. In a trie, you traverse the tree by following the components of the key (bits, hex characters, etc.) to find the value. This makes it perfect for key-value storage like account balances, where the address itself determines the path through the tree.

The key difference: in a Merkle Tree, the structure is determined by how you group the data. In a Merkle Trie, the structure is determined by the keys themselves.

Why Merkle Trees for Blockchain

Merkle Trees (and Merkle Tries) solve several critical problems for blockchain:

Compact state representation — Instead of storing the full state (50+ MB) in each block, we store just the Merkle Root (32 bytes). This makes blocks dramatically smaller and the blockchain more scalable.

Efficient verification — Anyone can verify that a specific account exists in the state with a small proof, without needing to download and validate the entire state. This enables light clients — nodes that don't store the full blockchain but can still verify data.

Tamper detection — Any change to any account instantly changes the root hash. This makes it cryptographically impossible to modify historical state without detection, as the root hash is included in the block hash.

Deterministic — For the same set of accounts and balances, the Merkle Root is always the same. Different nodes can independently compute the state and verify they're in sync by comparing just 32 bytes.

Merkle Trees in Production Blockchains

Different blockchains use Merkle Trees in different ways, depending on their architecture and requirements:

Bitcoin uses a simple binary Merkle Tree to organize transactions within each block. All transactions in a block are hashed pairwise and combined bottom-up until reaching a single Merkle Root, which is included in the block header. This enables Simplified Payment Verification (SPV) — light clients can verify that a transaction exists in a block by downloading just the block headers and a Merkle Proof, without downloading all transactions. Bitcoin doesn't use Merkle Trees for state because it follows the UTXO model, where state is simply the set of unspent outputs.

Ethereum takes a more sophisticated approach with three separate Patricia Merkle Tries for each block: a State Trie (account balances and contract storage), a Transaction Trie (transactions in the block), and a Receipt Trie (transaction execution results). The Patricia Trie is a modified hexadecimal trie with several optimizations — it uses extension nodes to compress long paths without branching, and branch nodes that can have up to 16 children (one for each hex digit 0-f). These optimizations dramatically reduce tree depth compared to a naive implementation. The structure allows efficient incremental updates: when an account balance changes, only the path from that leaf to the root needs to be recalculated, not the entire tree. The State Trie enables light clients to verify account balances without storing Ethereum's entire state (over 200 million accounts).

Solana uses Merkle Trees for its accounts database. The blockchain maintains a Merkle Tree of all account states, and the root is included in each block. Solana's high-performance architecture processes thousands of transactions per second, and Merkle Trees enable efficient state verification without sacrificing speed. Light clients can query account data and verify it against the Merkle Root without trusting full nodes.

Cardano also employs Merkle Trees for transaction verification within blocks, similar to Bitcoin. This allows light wallets to verify transactions efficiently without downloading the entire blockchain.

For our Fleming blockchain, we'll implement a hexadecimal Merkle Trie similar to Ethereum's approach — using hex characters from our addresses to traverse the trie. Since the path through the tree is determined by the address itself (each hex character decides which of the 16 children to follow), this is a trie structure, not a simple tree. This gives us a good balance between implementation simplicity and real-world applicability.

Sparse Merkle Trie

Now that we understand Merkle Trees and Merkle Tries, let's address a critical challenge: how do we handle dynamic state updates efficiently?

Imagine we implement a naive hexadecimal Merkle Trie for our blockchain state. Our addresses are 40 hex characters long, which means a full trie would have a depth of 40 levels. Here's the problem: if we only have 3 accounts in our blockchain, we'd still need to maintain the entire tree structure with potentially millions of empty branches. Even worse, every time we add a new account, we'd need to traverse up to 40 levels to insert it and recalculate hashes along the path.

This is where the Sparse Merkle Trie comes in. The key insight is that most of the trie is empty — with millions of possible addresses but only thousands or millions actually in use, the vast majority of the tree nodes don't exist. A Sparse Merkle Trie takes advantage of this sparseness.

How Sparse Merkle Tries Work

A Sparse Merkle Trie has a fixed depth determined by the key length. For our 40-character hex addresses, the tree has exactly 40 levels. However, instead of actually creating all possible nodes, we only store the nodes that exist along paths to actual data.

Here's the clever part: we use a default hash for empty branches. If a subtree contains no data, we don't store it at all — we just use a pre-computed empty hash. When we need to compute a node's hash and one or more of its children are empty, we use the default hash for those children.

Let's visualize this with a simple example. Suppose we have only two accounts with addresses starting with "0x3..." and "0xf...":

           root
          /    \
         /      \
      [3]       [f]
       |         |
     actual    actual
      data      data

All other children (0,1,2,4,5,6,7,8,9,a,b,c,d,e) use default empty hash

Why Sparse Merkle Tries Solve Our Problem

Efficient storage — We only store nodes that lead to actual accounts. If we have 1,000 accounts in a tree with 40 levels, we store roughly 1,000 × 40 = 40,000 nodes maximum, not the theoretical 16^40 nodes of a full trie.

Incremental updates — When we add a new account or update a balance, we only need to update the nodes along one path from the leaf to the root (40 nodes). We don't need to rebuild the entire tree. This is O(depth) = O(40) for our addresses — a constant-time operation regardless of how many accounts exist.

Deterministic root — For any given set of accounts and balances, the root hash is always the same. Empty parts of the tree always hash to the default value, so two nodes with identical state will compute identical roots.

Efficient proofs — To prove an account exists, we provide the hashes along the path from leaf to root (40 hashes). To prove an account doesn't exist, we can show that a path leads to an empty node (default hash).

Our Implementation Approach

For our Fleming blockchain, we'll implement a hexadecimal Sparse Merkle Trie with these characteristics:

Fixed depth of 40 levels (one per hex character in our addresses)
16 children per node (one for each hex digit 0-f)
Default hash for empty nodes (pre-computed to avoid redundant calculations)
HashMap-based storage (only storing non-empty nodes)

This approach gives us a good balance: simple enough to understand and implement, but efficient enough to handle millions of accounts with incremental updates.

Let's implement it.

Implementation

Before implementing the Sparse Merkle Trie, we need to refactor our hash types. Currently, we have BlockHash as a wrapper, but we'll be using 32-byte hashes in multiple places: blocks, Merkle Tree nodes, and state roots. Instead of having different hash types for different purposes, let's introduce a single consistent hash type.

Since we're using SHA-256 everywhere (which produces 256-bit = 32-byte hashes), let's rename BlockHash to Hash256:

// core/hash256.rs
use std::fmt::{Debug, Formatter};

#[derive(Clone, Copy, PartialEq, Eq, Hash)]
pub struct Hash256(pub [u8; 32]);

impl Debug for Hash256 {
    fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
        write!(f, "\"0x{}\"", hex::encode(self.0))
    }
}

Now we can update our Block structure to use Hash256 instead of BlockHash:

// core/block.rs
use crate::core::Hash256;

#[derive(Debug, Clone)]
pub struct Block {
    number: u64,
    transactions: Vec<Transaction>,
    state: State,
    previous_hash: Hash256,  // was BlockHash
    hash: Hash256,           // was BlockHash
    timestamp: u64,
}

This refactoring gives us:

Consistency — all 32-byte hashes use the same type across the codebase
Type safety — Hash256 is a distinct type, not just an alias
Reusability — we can now use Hash256 for Merkle Trie hashes without creating yet another hash type

With this foundation in place, we're ready to implement the Sparse Merkle Trie.

Let's extend our existing core/state.rs module with the Sparse Merkle Trie implementation. First, add the new data structures:

use crate::core::Hash256;
use crate::core::address::Address;
use std::collections::HashMap;

const TREE_DEPTH: usize = 40;
const HEX_RADIX: usize = 16;

pub type State = HashMap<Address, u64>;

struct TrieNode {
    hash: Hash256,
    value: Option<u64>, // just for leafs
}

pub struct SparseMerkleTrie {
    nodes: HashMap<String, TrieNode>, // path -> node
}

The TrieNode stores the hash of a node and optionally a balance value (only for leaf nodes). The SparseMerkleTrie uses a HashMap to store nodes indexed by their path — for example, "3a7f" represents the node at depth 4 reached by following hex characters 3, a, 7, and f from the root. We use a HashMap-based approach rather than recursive node structures to avoid Rust's ownership complexities with Box<T> and self-referential types.

Now let's implement the helper functions for hashing:

impl SparseMerkleTrie {
    fn hash_leaf(balance: Option<u64>) -> Hash256 {
        let mut hasher = Sha256::new();
        if let Some(balance) = balance {
            hasher.update(balance.to_le_bytes());
        }
        Hash256(hasher.finalize().into())
    }

    fn hash_internal_node(children: &[Hash256; HEX_RADIX]) -> Hash256 {
        let mut hasher = Sha256::new();
        for child_hash in children {
            hasher.update(child_hash.0);
        }
        Hash256(hasher.finalize().into())
    }

    fn address_to_path(address: &Address) -> &str {
        address
            .as_str()
            .strip_prefix("0x")
            .unwrap_or(address.as_str())
    }
}

The hash_leaf function hashes a balance value (or an empty value for non-existent accounts). The hash_internal_node concatenates the hashes of all 16 children and hashes the result. The address_to_path function strips the "0x" prefix from addresses to get the path through the trie.

Next, implement the constructor and basic operations:

pub fn new() -> Self {
    SparseMerkleTrie {
        nodes: HashMap::new(),
    }
}

pub fn get(&self, address: &Address) -> Option<u64> {
    let path = Self::address_to_path(address);
    self.nodes.get(path).and_then(|node| node.value)
}

pub fn insert(&mut self, address: &Address, balance: u64) {
    let path = Self::address_to_path(address);

    // Create leaf node with balance
    let leaf_hash = Self::hash_leaf(Some(balance));
    self.nodes.insert(
        path.to_string(),
        TrieNode {
            hash: leaf_hash,
            value: Some(balance),
        },
    );

    // Update hashes of all parent nodes up to root
    self.update_path(path);
}

The get method simply looks up the node in the HashMap and returns its balance. The insert method creates or updates a leaf node with the account balance, then updates all ancestor hashes up to the root.

Now implement the core logic for updating hashes along a path:

fn update_path(&mut self, path: &str) {
    // Update hashes from leaf to root
    // Walk backwards: parent_of_leaf -> parent_of_parent -> ... -> root
    for i in (0..path.len()).rev() {
        let parent_path = &path[..i]; // trim last character
        let parent_hash = self.compute_node_hash(parent_path);

        // Create/update parent node
        self.nodes.insert(
            parent_path.to_string(),
            TrieNode {
                hash: parent_hash,
                value: None, // only leaves have values
            },
        );
    }
}

fn compute_node_hash(&self, path: &str) -> Hash256 {
    let mut children_hashes = [Hash256([0u8; 32]); HEX_RADIX];

    // Check all 16 possible children (0-f)
    for (i, hex_char) in "0123456789abcdef".chars().enumerate() {
        let child_path = format!("{}{}", path, hex_char);

        // If a child exists, use its hash; otherwise use zero hash
        children_hashes[i] = if let Some(child_node) = self.nodes.get(&child_path) {
            child_node.hash
        } else {
            Hash256([0u8; 32]) // empty branch
        };
    }

    // Hash all 16 children hashes together
    Self::hash_internal_node(&children_hashes)
}

pub fn get_root_hash(&self) -> Hash256 {
    // Root has empty path
    self.compute_node_hash("")
}

The update_path method walks from the leaf up to the root, recalculating hashes for each ancestor node. The compute_node_hash method computes a node's hash by gathering the hashes of all 16 possible children — using the stored hash if the child exists, or a zero hash if it doesn't. The get_root_hash method returns the Merkle Root by computing the hash of the root node (empty path).

Finally, let's update the Block structure to use the Merkle Root instead of storing the full state:

// core/block.rs

#[derive(Debug, Clone)]
pub struct Block {
    number: u64,                    // just a serial number of block
    transactions: Vec<Transaction>, // array of transactions
    state_root: Hash256,            // Merkle root of the state trie (32 bytes)
    previous_hash: Hash256,         // SHA-256 of previous block
    hash: Hash256,                  // SHA-256 of current block
    timestamp: u64,                 // block creation timestamp
}

Now update the block hash calculation to include the state root:

fn calculate_hash(&self) -> Hash256 {
    let mut hasher = Sha256::new();
    hasher.update(self.number.to_le_bytes());
    hasher.update(&self.previous_hash.0);
    hasher.update(self.timestamp.to_le_bytes());

    for tx in &self.transactions {
        hasher.update(tx.as_bytes());
    }

    hasher.update(&self.state_root.0);

    Hash256(hasher.finalize().into())
}

And update the blockchain to maintain the trie and compute state roots:

// core/blockchain.rs

pub struct Blockchain {
    chain: Vec<Block>, // chain of blocks
    state: SparseMerkleTrie, // global state trie
}

pub fn append_block(&mut self, transactions: Vec<Transaction>) {
    let previous_block = self.chain.last().unwrap();
    let previous_hash = previous_block.hash().clone();
    let block_number = previous_block.number() + 1;

    // apply all transactions to the state
    for tx in &transactions {
        // check transaction
        if !tx.is_valid() {
            panic!("Invalid transaction");
        }

        // check balances
        let from_balance = self.state.get(&tx.from).unwrap_or(0);
        if from_balance < tx.amount {
            // will handle correctly later
            panic!("Insufficient balance!");
        }

        let to_balance = self.state.get(&tx.to).unwrap_or(0);

        self.state.insert(&tx.from, from_balance - tx.amount);
        self.state.insert(&tx.to, to_balance + tx.amount);
    }

    let state_root = self.state.get_root_hash();
    let new_block = Block::new(block_number, transactions, state_root, previous_hash);
    println!("Appending block: {:#?}", new_block);
    self.chain.push(new_block);
}

Instead of storing the full state in each block (which was 50+ MB for 1,000,000 accounts), we now store only the 32-byte Merkle Root. The blockchain maintains a single SparseMerkleTrie that gets updated with each block, and only the root hash is included in the block. This dramatically reduces storage requirements while maintaining cryptographic verifiability of the entire state.

Now let's implement Merkle Proofs to verify account balances without storing the full state. We'll need this later when we add peer-to-peer connections — a light client can request a proof from a full node and verify it against the state root in the block header.

First, define the proof structure:

// core/state.rs

#[derive(Clone, Debug, Eq, PartialEq)]
pub struct MerkleProof {
    pub siblings: Vec<Hash256>,
}

impl SparseMerkleTrie {
    pub fn get_proof(&self, address: &Address) -> Option<MerkleProof> {
        let path = Self::address_to_path(address);

        // Check if account exists
        if !self.nodes.contains_key(path) {
            return None;
        }

        let mut siblings = Vec::new();

        // Collect sibling hashes along the path
        for i in (0..path.len()).rev() {
            let parent_path = &path[..i];
            let current_char = path.chars().nth(i).unwrap();

            // For each level, we need the hashes of all 15 siblings
            // (all children except the one we're traversing)
            for (j, hex_char) in "0123456789abcdef".chars().enumerate() {
                if hex_char != current_char {
                    let sibling_path = format!("{}{}", parent_path, hex_char);
                    let sibling_hash = if let Some(node) = self.nodes.get(&sibling_path) {
                        node.hash
                    } else {
                        Hash256([0u8; 32])
                    };
                    siblings.push(sibling_hash);
                }
            }
        }

        Some(MerkleProof { siblings })
    }

    pub fn verify_proof(
        address: &Address,
        balance: u64,
        proof: &MerkleProof,
        expected_root: &Hash256,
    ) -> bool {
        let path = Self::address_to_path(address);
        let mut current_hash = Self::hash_leaf(Some(balance));
        let mut sibling_idx = 0;

        // Rebuild the path from leaf to root using the proof
        for i in (0..path.len()).rev() {
            let current_char = path.chars().nth(i).unwrap();
            let char_idx = "0123456789abcdef".find(current_char).unwrap();

            let mut children_hashes = [Hash256([0u8; 32]); HEX_RADIX];

            // Place current hash at correct position
            children_hashes[char_idx] = current_hash;

            // Fill in siblings from proof
            for (j, _) in "0123456789abcdef".chars().enumerate() {
                if j != char_idx {
                    children_hashes[j] = proof.siblings[sibling_idx];
                    sibling_idx += 1;
                }
            }

            current_hash = Self::hash_internal_node(&children_hashes);
        }

        // Compare computed root with expected root
        current_hash.0 == expected_root.0
    }
}

The get_proof method collects all sibling hashes along the path from the leaf to the root. For our hexadecimal trie, each level contributes 15 sibling hashes (all 16 children except the one we traverse). The verify_proof method reconstructs the root hash using only the address, balance, and proof — if the computed root matches the expected root, the proof is valid. This allows light clients to verify account balances with just ~19 KB of data instead of downloading the entire state.

We've now transformed our blockchain to use Merkle Trie for state management. However, this refactoring requires updating all existing tests — changing assertions from checking HashMap state to using the get() method, updating genesis block initialization, and adjusting validation logic. Rather than showing dozens of test updates in this article, you can find the complete test suite in the GitHub. The tests verify trie operations, proof generation and verification, and ensure backward compatibility with previous functionality.

Conclusion

In this article, we've solved the memory inefficiency problem by implementing a Sparse Merkle Trie for state management in our Fleming blockchain. We explored how Merkle Trees work, understood the difference between Merkle Trees and Merkle Tries, and implemented a hexadecimal Sparse Merkle Trie that efficiently handles millions of accounts.

We successfully implemented:

Hash type refactoring with Hash256 for consistency across the codebase
Sparse Merkle Trie with HashMap-based storage for efficient sparse data handling
Hashing functions for leaf nodes and internal nodes
Incremental hash updates from leaf to root
Merkle Proof generation and verification for light client support
Block structure update to store only the 32-byte Merkle Root instead of the full state

The impact is dramatic: instead of storing 50+ MB of state data in each block for 1,000,000 accounts, we now store just 32 bytes. The Merkle Root provides cryptographic verification of the entire state — any change to any account balance instantly changes the root hash, making tampering detectable. With Merkle Proofs, light clients can verify account balances using only ~19 KB of data instead of downloading the entire blockchain state, enabling efficient verification without trusting full nodes.

However, our blockchain still stores everything in memory, which means we lose all data when the program stops. For a real-world blockchain, we need persistent storage that survives restarts and can handle massive amounts of data efficiently.

In the next article, we'll tackle persistent storage by integrating Rocks DB — a high-performance embedded database used by production blockchains. We'll explore how to store blocks and state on disk, implement efficient queries, and ensure data integrity across restarts. This will transform our blockchain from a learning prototype into something that could actually handle real-world workloads.

As usual, all the source code from the article can be found here.

Stay tuned!

Designing Blockchain #3: Cryptography and Wallets

Dmytro Svynarenko — Tue, 11 Nov 2025 14:12:28 +0000

Intro

In the previous article, we explored how blockchain manages accounts and state transitions through transactions. However, we left a critical security gap: anyone could create a transaction claiming to be from any account. This article addresses that fundamental problem by introducing cryptographic signatures and wallets, the mechanisms that prove ownership and secure transactions on the blockchain.

Cryptographic Primitives

Let's dive into the cryptographic foundations. From the first article, we learned about hash functions. To recap: a hash function is a cryptographic algorithm that transforms any input into a fixed-size output (digest). Any change to the input produces a completely different output. But hashing is a one-way process — we need something we can encrypt and decrypt, or sign and verify. This is where asymmetric cryptography comes in. Unlike symmetric encryption, where the same key encrypts and decrypts data, asymmetric cryptography uses two mathematically related keys: a private key (kept secret) and a public key (shared openly).

Here's how asymmetric cryptography solves our account ownership problem: when you create an account, you generate two linked keys — a private key (like a secret password only you know) and a public key (like your account number that everyone can see). To prove you own an account, you sign a transaction with your private key. This creates a unique signature that anyone can verify using your public key. If the signature checks out, it proves only the private key holder could have created it. Think of it like signing a check: anyone can see your signature and verify it's yours, but only you can actually create it.

We have a public key, but blockchains need addresses. The transformation involves several steps. First, we hash the public key to create a shorter identifier. This hashing serves multiple purposes: it makes addresses easier to work with, adds security (even if quantum computers break the key derivation, they'd still need to reverse the hash), and creates a uniform address format regardless of the cryptographic algorithm used.

Traditional algorithms like RSA produce very large keys — often 2048 or 4096 bits. This creates problems for blockchain: larger keys mean larger transactions, which means more data to store and transmit. Remember, every node stores a complete copy of the blockchain, so size matters enormously.

Elliptic Curve Cryptography (ECC) provides the same security as RSA but with much smaller keys. A 256-bit ECC key offers equivalent security to a 3072-bit RSA key — more than 10 times smaller! This efficiency is crucial for blockchain, where we process thousands of transactions, each containing signatures. Smaller keys mean faster verification, less storage, and lower network bandwidth. ECC achieves this through the mathematical properties of elliptic curves, which make certain computational problems extremely hard to solve even with smaller key sizes.

The most widely used elliptic curves in blockchain are:

secp256k1 — standardized by the Standards for Efficient Cryptography Group. Bitcoin chose it for its efficiency and security, and Ethereum followed.
Curve25519 — designed by Daniel J. Bernstein with a focus on security and performance. It's used in modern protocols and newer blockchains.

Elliptic curves support different signature schemes, each with distinct trade-offs:

ECDSA (Elliptic Curve Digital Signature Algorithm) is the most common scheme, used in Bitcoin and Ethereum. It produces variable-length signatures and requires careful implementation to avoid vulnerabilities.
Schnorr signatures, introduced in Bitcoin's Taproot upgrade, offer key advantages: they're more efficient, support signature aggregation (combining multiple signatures into one), and have simpler security proofs.
EdDSA (Edwards-curve Digital Signature Algorithm) uses twisted Edwards curves like Ed25519. It provides deterministic signatures — no random number generation needed — making it less prone to implementation errors. EdDSA is faster and simpler than ECDSA.

Blockchain implementations:

Bitcoin: Uses secp256k1 curve with ECDSA signatures. Taproot upgrade (2021) added Schnorr signature support for improved privacy and efficiency.
Ethereum: Uses secp256k1 curve with ECDSA signatures. Addresses are derived by taking the Keccak-256 hash of the public key and using the last 20 bytes.
Solana: Uses Ed25519 (EdDSA) with Curve25519. This choice prioritizes performance — signature verification is significantly faster than ECDSA.
Cardano: Uses Ed25519 for transaction signatures, emphasizing security through formal verification and deterministic signatures.
Polkadot: Uses Schnorrkel/Ristretto, a variant of Schnorr signatures built on Curve25519, enabling efficient multi-signature schemes for its nominated proof-of-stake consensus.

For our learning purposes, we'll use the more efficient and modern Ed25519 with Curve25519 for the Fleming blockchain.

Wallet

A wallet in blockchain is software that manages your cryptographic keys — it doesn't actually store cryptocurrency. The coins exist on the blockchain; the wallet stores the private keys that prove you own them. Think of it like a keychain: your house (the account) exists independently, but you need the key (private key) to access it.

Modern wallets use Hierarchical Deterministic (HD) wallets, which generate unlimited key pairs from a single seed. This seed is typically represented as a mnemonic phrase — a sequence of 12 or 24 human-readable words (like "army van defense carry jealous true garbage claim echo media make crunch"). This phrase, following the BIP-39 standard, can regenerate all your private keys, making backup and recovery much simpler than managing individual keys.

The beauty of this system: you only need to safely store those 12–24 words to recover access to all your accounts, even if you lose your device.

There's much more to say about wallets, but that's not the focus of this article. For the Fleming blockchain, I'll use BIP39 to generate key pairs from a seed phrase — it's simpler than managing raw private keys. I'll skip implementing full HD wallets for the same reason.

Implementation

Let's start with the Wallet implementation. First, we need to install new dependencies (ed25519-dalek, bip39 and rand):

[dependencies]
sha2 = "0.10.9"
hex = "0.4.3"
ed25519-dalek = "2.2.0"
bip39 = "2.2.0"
rand = "0.9.2"

Then, add a couple of type aliases for simplicity:

use ed25519_dalek::{SigningKey as Ed25519SigningKey, VerifyingKey as Ed25519VerifyingKey};

pub type PrivateKey = Ed25519SigningKey;
pub type PublicKey = Ed25519VerifyingKey;

Finally, out Wallet definition:

use crate::core::address::Address;
use crate::core::crypto::{PrivateKey, PublicKey};

pub struct Wallet {
    private_key: PrivateKey,   // private key
    pub public_key: PublicKey, // public key
    pub address: Address,      // address (hash of public key)
}

Now we'll create a wallet from a mnemonic phrase using BIP-39:

impl Wallet {
    pub fn from_mnemonic(mnemonic_phrase: &str) -> Self {
        let mnemonic = Mnemonic::parse(mnemonic_phrase).expect("Invalid mnemonic phrase");
        let seed = mnemonic.to_seed(""); // don't use passphrase for our simple wallet

        // private key should be 256 bits (32 bytes) so slicing seed
        let private_key = PrivateKey::from_bytes(&seed[..32].try_into().expect("Invalid seed"));
        let public_key = private_key.verifying_key();
        let address = Address::from_public_key(public_key);

        Wallet {
            private_key,
            public_key,
            address,
        }
    }
}

In the Fleming blockchain, we derive the address by taking the SHA-256 hash of the public key and using the first 20 bytes (ADDRESS_LENGTH), whereas Ethereum uses Keccak-256 and takes the last 20 bytes, Bitcoin uses a more complex process with RIPEMD-160 after SHA-256 and adds checksums for error detection, and Solana simply uses the raw 32-byte Ed25519 public key as the address without hashing:

pub const ADDRESS_LENGTH: usize = 20;

#[derive(Hash, Clone, PartialEq, Eq)]
pub struct Address(String);

impl Address {
    pub fn from_public_key(public_key: &PublicKey) -> Self {
        let mut hasher = Sha256::new();
        hasher.update(public_key.as_bytes());
        let hash = hasher.finalize();

        // Like Ethereum but just first 20 bytes, not last
        Address(format!("0x{}", hex::encode(&hash[..ADDRESS_LENGTH])))
    }
}

Next, let's add the signer's public key and signature fields to the transaction:

#[derive(Debug, Clone)]
pub struct Transaction {
    pub from: Address,
    pub to: Address,
    pub amount: u64,
    pub signer: Option<PublicKey>,
    pub signature: Option<Signature>,
}

In Ed25519, the public key cannot be recovered from the signature alone, unlike ECDSA where public key recovery is possible through additional parameters. Therefore, we must explicitly include the signer's public key in the transaction so verifiers can validate the signature against it.

Now, add a sign method to the Wallet:

pub fn sign(&self, transaction: &mut Transaction) {
    let message = transaction.as_bytes();

    // add signer's public key and signature
    transaction.signer = Some(self.public_key);
    transaction.signature = Some(self.private_key.sign(message.as_slice()));
}

The Wallet's sign method serialises the transaction data, attaches the signer's public key to the transaction, and creates a cryptographic signature using the private key.

Now, let's implement signature verification. We'll add a verify method to check if a transaction was actually signed by the owner of the from address:

pub fn verify_signature(&self) -> bool {
    if let (Some(public_key), Some(signature)) = (&self.signer, &self.signature) {
        let message = self.as_bytes();
        public_key.verify(&message.as_slice(), signature).is_ok()
    } else {
        false
    }
}

The verification process reconstructs the original message from the transaction data and uses the public key to verify the signature matches. If verification succeeds, we know the transaction was signed by someone with the corresponding private key.

Now add all checks to the is_valid method:

pub fn is_valid(&self) -> bool {
    if self.signer.is_none() || self.signature.is_none() {
        return false;
    }

    if !self.verify_signature() {
        return false;
    }

    if let Some(signer) = &self.signer {
        if self.from != Address::from_public_key(signer) {
            return false;
        }
    }

    true
}

Finally, we need to update our blockchain validation to verify transaction signatures before accepting them into blocks:

pub fn append_block(&mut self, transactions: Vec<Transaction>) {

    ...

    // apply all transactions to the state
    for tx in &transactions {
        // check transaction
        if !tx.is_valid() {
            panic!("Invalid transaction");
        }

        ...
    }

    ...
}

The last step is updating the tests, but that's routine work. You can find the complete implementation on GitHub.

Conclusion

In this article, we've secured our Fleming blockchain by implementing cryptographic signatures and wallets using Ed25519 with Curve25519. We explored how public-key cryptography works, implemented wallet generation from mnemonic phrases using BIP-39, and added signature verification to ensure only the legitimate owner of an account can authorise transactions. With cryptographic security in place, our blockchain now prevents unauthorised transactions, but we still need to address the memory inefficiency problem of storing full state in every block — a challenge we'll tackle in the next article.

As usual all the source code from the article can be found here.

Stay tuned!

Designing Blockchain #2: Accounts and State

Dmytro Svynarenko — Tue, 11 Nov 2025 13:56:11 +0000

Intro

In the previous article, we created a simple blockchain from scratch, covering the fundamentals of blocks, hashing, and chain validation, but we left our transactions in a very primitive way. So, today we'll fix them, but before we do, we need to dive deeper into one of the most critical components of any blockchain system: accounts and state management.

Accounting models

There are two most popular accounting models for blockchains: UTXO and account-based.

It's worth mentioning that Sui blockchain implements a different approach — an object-centric data model, where everything is an object, but to my taste it's more like a customised UTXO model than truly something new.

UTXO

UTXO (UTxO, Unspent Transaction Output) is an accounting model where transactions consume previous outputs as inputs and create new outputs, with no concept of account balances — only unspent outputs that can be used in future transactions. I know it sounds difficult to understand, but I'll show an example and it'll make things clear.

Imagine you have a wallet with paper money and coins. These are your UTXOs — you can't divide them (just like in real life, you can't cut a $5 bill and claim it's now $4.85). You can only use them whole for transactions. How do you know your balance? Simply sum up all your paper money and coins — or in blockchain terms, your UTXOs. Now, you want to buy a newspaper (create a transaction) that costs $2, but you only have a $5 bill, so you'll receive change — for example, three $1 bills.

Congratulations — now you understand how Bitcoin works! In the UTXO model, there are no accounts with balances. Instead, each transaction consumes previous outputs and creates new ones. Here are some blockchains that use this model:

Bitcoin and similar blockchains like Litecoin (forked from Bitcoin's source code), Bitcoin Cash (a hard fork), Dogecoin (based on Litecoin), ZCash (forked from Bitcoin's source code) and others.
Cardano (extended UTXO model with smart contract support)
Monero

Now let's explore the pros and cons of the UTXO model.

Pros:

High privacy — each transaction generates a new address, making it harder to trace wallet activity
High scalability — parallel transaction processing significantly increases efficiency and throughput
Easy validation — simply check whether a UTXO exists in the unspent set

Cons:

Smart contracts — difficult to implement, though Cardano's extended UTXO model (eUTXO) provides smart contract support
Balance fragmentation — wallets with many small UTXOs can struggle to transfer certain amounts in a single transaction due to input limits or this transaction will . For example, if I have 1000 UTXOs worth 0.001 COIN each and want to send 1 COIN, but can only include 900 UTXOs in a transaction.
Hard to maintain wallet state — requires storing and indexing all unspent UTXOs to manage the wallet's balance.

Account-Based

Account-based is an accounting model where transactions directly modify account balances, maintaining a global state of all accounts with their current balances — similar to traditional banking systems.

Think of it like your bank account. When you receive your salary, the bank simply adds that amount to your account balance. When you buy something, they subtract the cost. Your balance is always stored and updated directly — there's no need to track individual bills or coins.

Here is our example with a newspaper:

In the account-based model, each account has a persistent balance that's updated with every transaction. Here are some blockchains that use this model:

Ethereum and EVM-compatible chains like Polygon, Binance Smart Chain, Avalanche C-Chain, and many others
Solana
Tezos

Now let's explore the pros and cons of the account-based model.

Pros:

Simplicity — easy to understand and implement, similar to traditional banking
Smart contracts — naturally supports complex smart contract logic and state management
Efficient for frequent transactions — no need to track multiple outputs, just update the balance

Cons:

Lower privacy — all transactions are directly linked to account addresses, making activity easier to trace
Replay attack vulnerability — requires nonces or sequence numbers to prevent transaction replay
Sequential processing — transactions from the same account must be processed in order, limiting parallelisation

State

Now that we understand the two main accounting models, let's talk about state — one of the most fundamental concepts in blockchain architecture.

State represents the current snapshot of all data in the blockchain at a given moment. Think of it as a photograph of the entire system — all account balances, smart contract storage, and any other data that exists at a specific block height.

The way state is managed differs significantly between UTXO and account-based models.

UTXO

In UTXO-based blockchains, the state is the set of all unspent transaction outputs (the UTXO set). Each block modifies this set by:

Consuming (removing) UTXOs used as transaction inputs
Creating (adding) new UTXOs as transaction outputs

The current state can be calculated by starting from the genesis block and applying all transactions in sequence. However, most implementations maintain the UTXO set in memory or a database for quick access.

Account-Based

In account-based blockchains, the state is a mapping of account addresses to their current data, which typically includes:

Balance — the amount of cryptocurrency the account holds
Code — smart contract bytecode (if the account is a contract)
Storage — persistent data used by smart contracts

Each transaction modifies the state by updating account balances or changing smart contract storage. The state is somehow stored in the block.

Implementation

For our Fleming blockchain, we'll use the account-based model because it's easier to understand and offers more interesting concepts to explore.

I'm continuing to update the codebase from the previous article, which you can find here.

First, define a type alias for the Address type:

pub type Address = String;

Now let's update our Transaction type:

#[derive(Debug, Clone)]
pub struct Transaction {
    pub from: Address,
    pub to: Address,
    pub amount: u64,
}

Done! Now we're ready to create state for our blockchain. To keep things simple, let's define our state as a hashmap where the key is an address and the value is the balance of that address:

pub type State = HashMap<Address, u64>;

Then let’s add state to a block. For now, let’s store a full state in each block:

#[derive(Debug, Clone)]
pub struct Block {
    number: u64,                    // just a serial number of block
    transactions: Vec<Transaction>, // array of transactions
    state: State,                   // FULL state of blockchain
    previous_hash: BlockHash,       // SHA-256 of previous block
    hash: BlockHash,                // SHA-256 of current block
    timestamp: u64,                 // block creation timestamp
}

Update the calculate_hash method to include state in block hash calculations (this prevents compromising the blockchain by tampering with state):

fn calculate_hash(&self) -> BlockHash {
    let mut hasher = Sha256::new();
    hasher.update(self.number.to_le_bytes());
    hasher.update(&self.previous_hash.0);
    hasher.update(self.timestamp.to_le_bytes());

    for tx in &self.transactions {
        hasher.update(tx.as_bytes());
    }

    // Since HashMap has indeterministic order, lets convert it to an array and sort by keys
    let mut state_entries: Vec<_> = self.state.iter().collect();
    state_entries.sort_by(|a, b| a.0.cmp(b.0));

    for (address, balance) in state_entries {
        hasher.update(address.as_bytes());
        hasher.update(balance.to_le_bytes());
    }

    BlockHash(hasher.finalize().into())
}

Now we need to process transactions by checking the blockchain's state:

pub fn append_block(&mut self, transactions: Vec<Transaction>) {
    let previous_block = self.chain.last().unwrap();
    let previous_hash = previous_block.hash().clone();
    let block_number = previous_block.number() + 1;

    // clone full state
    let mut new_state = previous_block.state().clone();

    // apply all transactions to the state
    for tx in &transactions {
        let from_balance = new_state.get(&tx.from).unwrap_or(&0);
        if *from_balance < tx.amount {
            // will handle correctly later
            panic!("Insufficient balance!");
        }

        *new_state.get_mut(&tx.from).unwrap() -= tx.amount;
        *new_state.entry(tx.to.clone()).or_insert(0) += tx.amount;
    }

    let new_block = Block::new(block_number, transactions, new_state, previous_hash);
    println!("Appending block: {:#?}", new_block);
    self.chain.push(new_block);
}

The transaction processing logic iterates through each transaction and updates the state. First, it verifies that the sender has sufficient balance to cover the transaction amount and panicking if they don't. I know this isn't a good way to handle such cases, and we'll fix it later, but for now it's fine. Then it deducts the amount from the sender's balance and adds it to the recipient's balance, creating a new entry if the recipient doesn't exist in the state yet. To validate that our new logic works correctly, let's update our unit tests and add a couple more:

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_blockchain_creation_with_state() {
        let blockchain = Blockchain::new(vec![(String::from("A"), 10), (String::from("B"), 5)]);
        assert_eq!(blockchain.chain.len(), 1);
        assert!(blockchain.is_valid());

        let genesis_block = &blockchain.chain.last().unwrap();
        assert_eq!(genesis_block.number(), 0);
        assert_eq!(*genesis_block.state().get("A").unwrap(), 10);
        assert_eq!(*genesis_block.state().get("B").unwrap(), 5);
    }

    #[test]
    fn test_valid_blockchain_and_state_after_transactions() {
        let mut blockchain = Blockchain::new(vec![(String::from("A"), 10), (String::from("C"), 5)]);
        blockchain.append_block(vec![Transaction::new(
            String::from("A"),
            String::from("B"),
            10,
        )]);
        blockchain.append_block(vec![Transaction::new(
            String::from("C"),
            String::from("D"),
            5,
        )]);

        assert_eq!(blockchain.chain.len(), 3);
        assert!(blockchain.is_valid());

        // initial: A=10, C=5
        // A -(10)-> B: A=0, B=10
        // C -(5)-> D: C=0, D=5
        let last_block = &blockchain.chain.last().unwrap();
        assert_eq!(last_block.number(), 2);
        assert_eq!(*last_block.state().get("A").unwrap(), 0);
        assert_eq!(*last_block.state().get("B").unwrap(), 10);
        assert_eq!(*last_block.state().get("C").unwrap(), 0);
        assert_eq!(*last_block.state().get("D").unwrap(), 5);
    }

    #[test]
    #[should_panic(expected = "Insufficient balance")]
    fn test_insufficient_balance_panics() {
        let mut blockchain = Blockchain::new(vec![(String::from("A"), 10)]);

        blockchain.append_block(vec![Transaction::new(
            String::from("A"),
            String::from("B"),
            15,
        )]);
    }

    #[test]
    fn test_tampered_transaction_blockchain_invalid() {
        let mut blockchain = Blockchain::new(vec![(String::from("A"), 10), (String::from("C"), 5)]);
        blockchain.append_block(vec![Transaction::new(
            String::from("A"),
            String::from("B"),
            10,
        )]);
        blockchain.append_block(vec![Transaction::new(
            String::from("C"),
            String::from("D"),
            5,
        )]);

        blockchain.chain[1]
            .tamper_transaction(0, Transaction::new(String::from("A"), String::from("B"), 2));

        assert!(!blockchain.is_valid());
    }

    #[test]
    fn test_tampered_state_blockchain_invalid() {
        let mut blockchain = Blockchain::new(vec![(String::from("A"), 10), (String::from("C"), 5)]);
        blockchain.append_block(vec![Transaction::new(
            String::from("A"),
            String::from("B"),
            10,
        )]);
        blockchain.append_block(vec![Transaction::new(
            String::from("C"),
            String::from("D"),
            5,
        )]);

        blockchain.chain[1].tamper_state(String::from("F"), 15);

        assert!(!blockchain.is_valid());
    }
}

The test suite validates the blockchain's state management and transaction processing capabilities. Tests verify that the genesis block initialises with the correct state, transactions properly update account balances, and the blockchain maintains validity after multiple transactions. The suite also ensures that insufficient balance scenarios are caught and that any tampering with either transactions or state makes the blockchain invalid. Finally, tests confirm that the cryptographic hashing properly detects modifications to both transaction data and state data.

Conclusion

In this article, we've taken a significant step forward by implementing accounts and state management in our Fleming blockchain. We explored the two main accounting models used in blockchain systems — UTXO and account-based — and chose the account-based model for its simplicity and flexibility with smart contracts.

We successfully implemented:

Account addresses and transaction structure with sender, recipient, and amount
State management as a hashmap of account balances
Transaction processing logic that validates balances and updates state
Comprehensive tests to ensure our blockchain maintains validity

However, our current implementation has two critical problems that we need to address:

Memory inefficiency: Storing the full state in every block is extremely wasteful and doesn't scale well. As the blockchain grows and the number of accounts increases, each block becomes larger and larger, consuming excessive memory and making the blockchain impractical for real-world use.
Security vulnerability: Currently, anyone can create transactions from any account without proving ownership. There's no authentication mechanism to verify that the person sending a transaction actually owns the account they're sending from. This is a massive security flaw that would allow anyone to steal funds from any account.

In the next article, we'll tackle the second problem by implementing wallets and cryptographic signatures. We'll explore how public-key cryptography works, how to generate wallet addresses, and most importantly, how to ensure that only the legitimate owner of an account can authorise transactions from that account. This will make our blockchain secure and ready for more advanced features.

As usual all the source code from the article can be found here.

Stay tuned!

Designing Blockchain #1: Introduction

Dmytro Svynarenko — Tue, 11 Nov 2025 13:32:26 +0000

Intro

In today's rapidly growing Web3 world of blockchains, understanding the fundamental technology behind cryptocurrencies, smart contracts, and decentralized applications has become increasingly important. To build a strong general knowledge of how blockchain works, I've decided to create a cycle of articles about creating a blockchain from scratch in Rust. This hands-on approach will provide deeper insights into the inner workings of blockchain technology while also offering practical programming experience with a powerful systems language.

What is Blockchain?

From Wikipedia:

The blockchain is a distributed ledger with growing lists of records (blocks) that are securely linked together via cryptographic hashes.

From ChatGPT:

Blockchain is essentially a digital, decentralised ledger that records transactions in a way that is secure, transparent, and tamper-resistant. Think of it as a chain of “blocks,” where each block contains a list of transactions. Once a block is added, it’s linked to the previous one, forming a chain—hence the name blockchain.

So, from both definitions we have the common keywords:

Distributed
Ledger
Records/Block
Security

Distributed – the blockchain's data isn't stored in just one central location or controlled by a single entity. Instead, it's copied and spread across many computers (called nodes) in different locations. This distribution makes the blockchain more resilient because if one node fails or is compromised, the data still exists on many others. This is a bit complicated thing to implement, so we’ll talk about it in later articles.

Ledger – a digital record-keeping system that tracks all transactions that have occurred on the blockchain. Unlike traditional ledgers that might be controlled by a single entity (like a bank), blockchain ledgers are distributed (our previous word) across the network, with each node having their own copy. This ensures transparency and makes it extremely difficult to alter past records, as any change would need to be approved by the majority of the network.

Block – a fundamental unit of a blockchain that contains a collection of transactions and metadata. When transactions occur on the blockchain, they are verified and grouped together into blocks. Each block contains:

Block Number
List of validated transactions
Timestamp showing when the block was created
Link to the previous block

The first block in the blockchain called master-block. So, now we have a ledger in a form of a chain of blocks, let’s move to the final keyword.

Security – comes from using cryptographic methods (mainly hash and asymmetric crypto functions). Each block has its own hash (like a digital fingerprint) created from what's inside the block. If someone changes anything in the block, the hash completely changes too. Because each block contains the previous block's hash, any changes are easy to spot, making the chain secure and hard to tamper with.

Okay, for now we have the fundamental definition of the blockchain, and to start our Rust simple implementation we just need to find out what a hash function is (we'll talk about asymmetric crypto functions later).

Hash function

Hash function – is like a digital fingerprint machine for data. It takes any information (like a transaction or block details) and converts it into a fixed-size string of characters that looks random. The main crucial properties of hash functions are:

Any tiny change to the data completely changes the hash output
You can't recreate the original data from just the hash

It's not a trivial task to create a secure and efficient hash function by yourself, and you need at least a PhD in cryptography, so we'll use existing ones.

For example, usage of hash functions by popular blockchains:

Bitcoin – SHA-256
Ethereum – Keccak-256
Solana – SHA-256 / BLAKE3
Litecoin – Scrypt
Cardano – Blake2b-256

SHA-256 (256 means that the hash length is 256 bits) – is very popular and time-tested algorithm in cryptography that provides strong security guarantees.

SHA-3 (Keccak) – a newer member of the SHA family, standardized in 2015. Unlike SHA-256, it uses a different internal structure (sponge construction) making it resistant to attacks that might eventually threaten SHA-256. Ethereum chose Keccak-256 (a variant of SHA-3) for its blockchain to differentiate from Bitcoin and provide additional security margins.

Also, it's important to use a verified or even audited version of the crypto library, so for our case I'll choose the sha2 crate (since it's battle-proven with the Solana blockchain).

Initial implementation

Our blockchain project is named Fleming, after Ian Fleming, the creator of James Bond. The word "Bond" is similar-sounding to the financial instrument "bond" — a wordplay I find particularly interesting in the context of blockchain technology.

Since we decided to use sha2 as the library for hashing, let's install it as well (hex is used for encoding byte arrays to more human-readable strings):

[package]
name = "fleming"
version = "0.1.0"
edition = "2021"

[dependencies]
sha2 = "0.10.9"
hex = "0.4.3"

First of all, let's define the Transaction type (in this article it'll be just a string alias, we'll come back to it in the next articles):

pub type Transaction = String;

Now, let's add a more user-friendly type alias for hashes and use the hex crate to encode it to a string for debug purposes:

#[derive(Clone)]
pub struct BlockHash(pub [u8; 32]); //  SHA-256 -> 32 bytes = 256 bits

impl Debug for BlockHash {
    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
        write!(f, "\\"0х{}\\"", hex::encode(self.0))
    }
}

Then the Block:

#[derive(Debug, Clone)]
pub struct Block {
    number: u64,                    // just a serial number of block
    transactions: Vec<Transaction>, // array of transactions
    previous_hash: BlockHash,       // SHA-256 of previous block
    hash: BlockHash,                // SHA-256 of current block
    timestamp: u64,                 // block creation timestamp
}

And, finally, the Blockchain:

pub struct Blockchain {
    chain: Vec<Block>, // chain of blocks
}

Now that we've defined our data structures, let's implement them. We'll start with the Block:

pub fn new(
    block_number: u64,
    transactions: Vec<Transaction>,
    previous_hash: BlockHash,
) -> Self {
    let mut block = Block {
        number: block_number,
        transactions,
        timestamp: get_timestamp(),
        previous_hash,
        hash: BlockHash([0; 32]),
    };

    block.hash = block.calculate_hash();
    block
}

To create a new block, we need three things: a block number, an array of transactions, and the previous block's hash. Once we have these, we calculate the block's hash:

fn calculate_hash(&self) -> BlockHash {
    let mut hasher = Sha256::new();
    hasher.update(self.number.to_le_bytes());
    hasher.update(&self.previous_hash.0);
    hasher.update(self.timestamp.to_le_bytes());

    for tx in &self.transactions {
        hasher.update(tx.as_bytes());
    }

    BlockHash(hasher.finalize().into())
}

All components must be included in the hash. To verify the block, we can recalculate its hash and compare it to the stored one:

pub fn is_valid(&self) -> bool {
    let current_hash = self.calculate_hash();
    self.hash.0 == current_hash.0
}

We're done with the Block. Let's move on to the Blockchain:

pub fn new() -> Self {
    let master_block = Block::new(0, vec![], BlockHash([0; 32]));
    println!("Master block: {:#?}", master_block);

    Blockchain {
        chain: vec![master_block],
    }
}

To create a new blockchain, we initialize it with a master-block (block number 0) that has an empty transaction list and a zero hash as its previous hash, since there's no block before it.

pub fn append_block(&mut self, transactions: Vec<Transaction>) {
    let previous_block = self.chain.last().unwrap();
    let previous_hash = previous_block.hash().clone();
    let block_number = previous_block.number() + 1;

    let new_block = Block::new(block_number, transactions, previous_hash);
    println!("Appending block: {:#?}", new_block);
    self.chain.push(new_block);
}

To append a new block to the blockchain, we retrieve the last block from the chain, get its hash and block number, then create a new block with an incremented number and the previous block's hash. And, finally, to validate the whole blockchain:

pub fn is_valid(&self) -> bool {
    for block_index in 1..self.chain.len() {
        let current_block = &self.chain[block_index];
        let previous_block = &self.chain[block_index - 1];

        if !current_block.is_valid() {
            println!("Block {} has invalid hash", current_block.number());
            return false;
        }

        if current_block.previous_hash().0 != previous_block.hash().0 {
            println!("Block {} has invalid previous_hash", current_block.number());
            return false;
        }
    }
    true
}

To validate the entire blockchain, we iterate through each block (starting from block 1, since the master block has no previous block to verify against), check if each block's hash is valid, and verify that each block's previous_hash matches the actual hash of the preceding block. And that's it. We've got a basic blockchain implementation in a couple of hundred lines of code. Don’t forget to write a couple unit tests to make sure our logic is fine:

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_blockchain_creation() {
        let blockchain = Blockchain::new();
        assert_eq!(blockchain.chain.len(), 1);
        assert!(blockchain.is_valid());
    }

    #[test]
    fn test_valid_blockchain() {
        let mut blockchain = Blockchain::new();
        blockchain.append_block(vec![String::from("A -> B: 10 FLMG")]);
        blockchain.append_block(vec![String::from("C -> D: 5 FLMG")]);

        assert_eq!(blockchain.chain.len(), 3);
        assert!(blockchain.is_valid());
    }

    #[test]
    fn test_tampered_blockchain_invalid() {
        let mut blockchain = Blockchain::new();
        blockchain.append_block(vec![String::from("A -> B: 10 FLMG")]);
        blockchain.append_block(vec![String::from("C -> D: 5 FLMG")]);

        blockchain.chain[1].tamper_transaction(0, String::from("A -> B: 1000 FLMG"));

        assert!(!blockchain.is_valid());
    }
}

Conclusion

In this article, we've built a foundational blockchain implementation in Rust from scratch. We explored the core concepts of blockchain technology — distributed ledgers, blocks, and cryptographic security — and implemented basic data structures for transactions, blocks, and the blockchain itself. Using the SHA-256 hash function via the sha2 crate, we created a system where each block contains transactions, a timestamp, and a cryptographic link to the previous block. We also implemented validation mechanisms to ensure the integrity of individual blocks and the entire chain, demonstrating how blockchain's immutability works in practice.

In the next article, we'll talk about accounting models, states, and make our transactions more functional, so stay tuned!

All code from this article can be found here or in the release here.