Data availability proof-friendly state tree transitions

[MaxC]

@musalbas

Oh actually, it’s quite simple. If an entire row is missing, the fraud proof consists of M merkle proofs of the missing chunks of the rows recomputed from the columns, from the column merkle roots. The light client then computes the whole row from these column merkle proofs, and checks to see if it matches the given merkle root of the row. There’s quite an overhead for having to provide a merkle proof for every chunk, though.

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

[tim]

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

[musalbas]

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

[irakliy81]

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.

[vbuterin]

Sparse Merkle trees are incredibly simple.

[kladkogex]

@musalbas

However, a malicious miner could create a blockchain with a fraudulent state tree root, that does not match the state transitions made by the transactions in the block, and so no one would be able to find prove the inclusion of any state in the tree and find proofs of fraudulent state, because they don’t have the data for it.

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?

[musalbas]

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.