A dance with Merkle Trees

In my recent exploration into the web3 and blockchain world, I have frequently encountered the concept of Merkle trees, or hash trees. They provide a way to quickly and efficiently verify data since a hashed value remains constant. Additionally, Merkle trees offer a secure method for transferring large amounts of data between different nodes in a blockchain network.

What the Heck Are Merkle Trees?

At the base level, a Merkle tree is still a tree data structure, which is a hierarchical structure where each node has a left and right property that points to the next node in the tree structure. Each node also contains a value, which is a hash in this case.

The basic structure in Go is:

type MerkleTree struct {
    Root       *Node
    LeafHashes [][]byte
}

type Node struct {
    Left  *Node
    Right *Node
    Hash  []byte
}

A Simple Implementation of Merkle Trees in Golang

// merkle.go
package main

import (
    "crypto/sha256"
    "encoding/hex"
    "fmt"
)

type MerkleTree struct {
    Root       *Node
    LeafHashes [][]byte
}

type Node struct {
    Left  *Node
    Right *Node
    Hash  []byte
}

func hashData(data []byte) []byte {
    hash := sha256.Sum256(data)
    return hash[:]
}

func concatenateAndHash(left, right []byte) []byte {
    concatenated := append(left, right...)
    return hashData(concatenated)
}

func NewMerkleTree(data [][]byte) *MerkleTree {
    var nodes []Node

    // Create leaf nodes
    for _, datum := range data {
        hash := hashData(datum)
        nodes = append(nodes, Node{Hash: hash})
    }

    // Build the tree
    for len(nodes) > 1 {
        var newLevel []Node
        for i := 0; i < len(nodes); i += 2 {
            if i+1 == len(nodes) {
                // Odd number of nodes, duplicate the last node
                nodes = append(nodes, nodes[i])
            }
            left, right := nodes[i], nodes[i+1]
            newHash := concatenateAndHash(left.Hash, right.Hash)
            newLevel = append(newLevel, Node{Left: &left, Right: &right, Hash: newHash})
        }
        nodes = newLevel
    }

    tree := MerkleTree{Root: &nodes[0]}
    return &tree
}

Since a Merkle tree is a tree structure, we build the tree from the root node for each level. In a Merkle tree, each leaf node is a hash of a block of data, and each non-leaf node is a hash of its two child nodes.

We define the structures for the nodes and the Merkle tree. Each node has pointers to its left and right children and a hash value. The Merkle tree holds the root node and the leaf hashes.

type MerkleTree struct {
    Root       *Node
    LeafHashes [][]byte
}

type Node struct {
    Left  *Node
    Right *Node
    Hash  []byte
}

We also create the hash functions to hash the data to be embedded in the tree.

func hashData(data []byte) []byte {
    hash := sha256.Sum256(data)
    return hash[:]
}

func concatenateAndHash(left, right []byte) []byte {
    concatenated := append(left, right...)
    return hashData(concatenated)
}

To build a Merkle tree, we start by creating leaf nodes, each representing a hashed value of the input data. We then iteratively construct the tree by pairing up these nodes at each level, concatenating their hashes, and hashing the result to form the parent nodes. This process continues, forming new levels of parent nodes until only one node remains. If there is an odd number of nodes at any level, the last node is duplicated to ensure every node has a pair. The final remaining node becomes the root of the Merkle tree.

func NewMerkleTree(data [][]byte) *MerkleTree {
    var nodes []Node

    // Create leaf nodes
    for _, datum := range data {
        hash := hashData(datum)
        nodes = append(nodes, Node{Hash: hash})
    }

    // Build the tree
    for len(nodes) > 1 {
        var newLevel []Node
        for i := 0; i < len(nodes); i += 2 {
            if i+1 == len(nodes) {
                // Odd number of nodes, duplicate the last node
                nodes = append(nodes, nodes[i])
            }
            left, right := nodes[i], nodes[i+1]
            newHash := concatenateAndHash(left.Hash, right.Hash)
            newLevel = append(newLevel, Node{Left: &left, Right: &right, Hash: newHash})
        }
        nodes = newLevel
    }

    tree := MerkleTree{Root: &nodes[0]}
    return &tree
}

A Much Broader Use of Merkle Trees

I came across a post on how ApiToolKit by Anthony Alaribe uses Merkle Trees to detect API breaking changes, which majorly inspired this article. Thus, I wrote a simple simulator in Go on how that might have been implemented.

To simulate using Merkle trees to detect breaking changes in an API, we'll create a small Go program. This program will simulate the /get-coins and /buy-coins API requests, hash their responses, and store them in a Merkle tree. We'll then compare the hashes to detect changes.

// main.go
package main

import (
    "encoding/hex"
    "encoding/json"
    "fmt"
)

type ApiResponse struct {
    Endpoint string
    Data     []byte
}

func getCoins() ApiResponse {
    coins := []string{"BITCOIN", "SOLANA"}
    data, _ := json.Marshal(coins)
    return ApiResponse{Endpoint: "/get-coins", Data: data}
}

func buyCoins(successful bool) ApiResponse {
    if successful {
        status := map[string]int{"status": 100}
        data, _ := json.Marshal(status)
        return ApiResponse{Endpoint: "/buy-coins", Data: data}
    } else {
        status := map[string]int{"status": 101}
        data, _ := json.Marshal(status)
        return ApiResponse{Endpoint: "/buy-coins", Data: data}
    }
}

func detectBreakingChange(oldTree, newTree *MerkleTree) bool {
    return hex.EncodeToString(oldTree.Root.Hash) != hex.EncodeToString(newTree.Root.Hash)
}

func main() {
    // Simulate initial API calls
    initialGetCoinsResponse := getCoins()
    initialBuyCoinsResponse := buyCoins(true)

    // Hash initial responses and build Merkle tree
    initialData := [][]byte{initialGetCoinsResponse.Data, initialBuyCoinsResponse.Data}
    initialTree := NewMerkleTree(initialData)
    fmt.Println("Initial Merkle Tree:")
    printTree(initialTree.Root, 0)

    // Simulate subsequent API calls
    newGetCoinsResponse := getCoins()

    // Can switch to true to check if correct
    newBuyCoinsResponse := buyCoins(false)

    // Hash new responses and build new Merkle tree
    newData := [][]byte{newGetCoinsResponse.Data, newBuyCoinsResponse.Data}
    newTree := NewMerkleTree(newData)
    fmt.Println("\nNew Merkle Tree:")
    printTree(newTree.Root, 0)

    // Detect breaking changes
    if detectBreakingChange(initialTree, newTree) {
        fmt.Println("\nBreaking changes detected!")
    } else {
        fmt.Println("\nNo breaking changes detected.")
    }
}

The above implementation demonstrates how you can easily detect breaking changes in an API using Merkle trees. Merkle trees provide an efficient way to ensure data integrity because the hashed value of the same data remains unchanged. This approach is superior to comparing JSON objects directly, as it avoids the complexity of traversing each key and value to verify that the shape and structure are consistent. Instead, by simply comparing the root hashes of the Merkle trees, we can quickly detect any changes in the API responses, ensuring a reliable and secure method for monitoring API integrity. This implementation, inspired by the approach used by ApiToolKit by Anthony Alaribe, highlights the practical application of Merkle trees.

Blog

A dance with Merkle Trees

Abdulhafeez Abdulraheem

What the Heck Are Merkle Trees?

A Simple Implementation of Merkle Trees in Golang

A Much Broader Use of Merkle Trees

Join Our Newsletter. No Spam, Only the good stuff.

Related