Data availability proof-friendly state tree transitions

Sharding
23

I’ve implemented a Sparse Merkle tree library in Go. It also allows for verifying the “Merkle change proofs” I discussed in the post, which are in fact just standard Merkle proofs (i.e. stateless client witnesses). It allows a light client to verify, using the sub-tree of the state, the new root of the tree.

The API works by first creating a new empty subtree, adding proofs to it, updating leafs, and calculating the new root. Example usage:

package main

import(
    "bytes"
    "fmt"
    "crypto/sha256"
    "github.com/musalbas/smt"
)

func main() {
    // Initialise the tree
    tree := smt.NewSparseMerkleTree(smt.NewSimpleMap(), sha256.New())

    // Set some keys
    tree.Update([]byte("key1"), []byte("value1"))
    tree.Update([]byte("key2"), []byte("value2"))
    tree.Update([]byte("key3"), []byte("value3"))
    tree.Update([]byte("key4"), []byte("value4"))

    // Generate a Merkle proof for key1=value1 and key2=value2
    proof1, _ := tree.Prove([]byte("key1"))
    proof2, _ := tree.Prove([]byte("key2"))

    // Initialise the deep subtree
    subtree := smt.NewDeepSparseMerkleSubTree(smt.NewSimpleMap(), sha256.New())

    // Add the branches to the subtree
    subtree.AddBranches(proof1, []byte("key1"), []byte("value1"), true)
    subtree.AddBranches(proof2, []byte("key2"), []byte("value2"), true)

    // Update key1 and key2 in both trees
    subtree.Update([]byte("key1"), []byte("value5"))
    tree.Update([]byte("key1"), []byte("value5"))
    subtree.Update([]byte("key2"), []byte("value6"))
    tree.Update([]byte("key2"), []byte("value6"))

    // Verify that both roots are equal
    if bytes.Compare(tree.Root(), subtree.Root()) == 0 {
        fmt.Println("Success")
    } else {
        fmt.Println("Failure")
    }
}
1 Like