smtproofs

README

Proofs SMT

This project demonstrates the generation and validation of ICS-23 proofs for a sparse Merkle tree (SMT) as implemented by Celestia.

Library usage

It exposes a two main functions :

func CreateMembershipProof(tree *smt.SparseMerkleTree, key []byte) (*ics23.CommitmentProof, error) produces a CommitmentProof that the given key exists in the SMT (and contains the current value). This returns an error if the key does not exist in the tree.

func CreateNonMembershipProof(tree *smt.SparseMerkleTree, key []byte, preimages PreimageMap) (*ics23.CommitmentProof, error) produces a CommitmentProof that the given key doesn't exist in the SMT. This returns an error if the key does not exist in the tree. This relies on an auxiliary PreimageMap object which provides access to the preimages of all keys in the tree based on their (hashed) path ordering.

CLI usage

We also expose a simple script to generate test data for the confio proofs package.

go install ./cmd/testgen-smt
testgen-smt exist left 10

Will output some json data, from a randomly generated Merkle tree each time.

{
  "key": "574f516c4364415274743845444d397347484937",
  "proof": "0a9d010a2024910c64b5b74b6b72e6b9d3310a1d0bd599032e05e8abc43112d194e1a78f30121e76616c75655f666f725f574f516c4364415274743845444d3973474849371a07080118012a0100222708011201011a20b51557119b6985d54a48a4510e528d5f929f0b1c8b57914bb6cd8f9eab035d75222708011201011a20fff8248ca9e98cbb05c81612d38e74780b2c02d9c88ee628cfbdb8ca44769a63",
  "root": "f69ef3599b7f0471b61735490636608a8ff43a327b2b5a3a5528ca7f7059ffa5",
  "value": "76616c75655f666f725f574f516c4364415274743845444d397347484937"
}

"root" is the hex-encoded root hash of the Merkle tree.

"proof" is the hex-encoding of the protobuf binary encoding of a proofs.ExistenceProof object. This contains a (key, value) pair, along with all steps to reach the root hash. This provides a non-trivial test case, to ensure clients in multiple languages can verify the protobuf proofs we generate from the SMT.

Documentation

Index

• func CreateMembershipProof(tree *smt.SparseMerkleTree, key []byte) (*ics23.CommitmentProof, error)
• func CreateNonMembershipProof(tree *smt.SparseMerkleTree, key []byte, preimages PreimageMap) (*ics23.CommitmentProof, error)
• type PreimageMap

Functions

func CreateMembershipProof

func CreateMembershipProof(tree *smt.SparseMerkleTree, key []byte) (*ics23.CommitmentProof, error)

CreateMembershipProof will produce a CommitmentProof that the given key (and queries value) exists in the SMT. If the key doesn't exist in the tree, this will return an error.

func CreateNonMembershipProof

func CreateNonMembershipProof(tree *smt.SparseMerkleTree, key []byte, preimages PreimageMap) (*ics23.CommitmentProof, error)

CreateNonMembershipProof will produce a CommitmentProof that the given key doesn't exist in the SMT. If the key exists in the tree, this will return an error.

Types

type PreimageMap

type PreimageMap interface {
	// KeyFor returns the preimage (key) for given path index.
	KeyFor(int) []byte
	// FindPath returns the ordered index of a given path, and whether it's contained in the tree.
	// If not found, the returned index is where the path would be inserted.
	FindPath([32]byte) (int, bool)
	// Len returns the number of mapped paths.
	Len() int
}

PreimageMap represents an interface for accessing hashed tree paths and retrieving their corresponding preimages.