Data availability proof-friendly state tree transitions

data-structure

#21

Yeah, you can do it that way, nice. (y)


#22

Has anyone been able to make an implementation yet for the Sparse Merkle Tree?


#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")
    }
}

#24

I’m curious, what are the advantages/disadvantages of sparse Merkle Trees as compared to Merklix Trees (described here: https://www.deadalnix.me/2016/09/24/introducing-merklix-tree-as-an-unordered-merkle-tree-on-steroid and here: https://www.deadalnix.me/2016/09/29/using-merklix-tree-to-checkpoint-an-utxo-set ). It seems like at least in concept they try to accomplish the same thing.


#25

Sparse Merkle trees are incredibly simple.


#26

I am a bit confused, I thought when non-mining nodes receive a block from the miner they re-execute smart contracts and verify the new state tree root. If a miner creates a block with a fraudulent state root, wouldnt it be rejected by other nodes? How can an invalid state root end up at the light client unless the light client is connected to the mining node itself?


#27

The invalid state root can end up at the light client if any full node that it’s connected to feeds it the invalid block, because light clients just assume that the chain with the most work is valid. Under normal circumstances this should not happen, but in the rare case that the majority of the consensus is malicious then this can happen. Or even if people decided to fork the chain for sincere reasons e.g. due to disagreements, then light clients wouldn’t be able to distinguish between the forks if the consensus algorithms are the same.