Go implementation of a Merkle tree.
go-merkletree is a standard Go module which can be installed with:
go get github.com/wealdtech/go-merkletree/v2go-merkletree generates Merkle trees from an array of []byte values and uses them to generate proofs. Proofs can be verified, and graphs generated
This package uses pollards and sparese multiproofs for efficient generation of multiple proofs against the same tree; see the articles Understanding Merkle pollards and Understanding sparse Merkle multiproofs for details.
This package can generate visualisations (in DOT format) for trees and proofs. Below is a tree visualisation:
and below is a proof visualisation with the value being proved in red, the intermediate branches in green and the root in blue:
package main
import (
merkletree "github.com/wealdtech/go-merkletree/v2"
)
// Example using the Merkle tree to generate and verify proofs.
func main() {
// Data for the tree
data := [][]byte{
[]byte("Foo"),
[]byte("Bar"),
[]byte("Baz"),
}
// Create the tree
tree, err := merkletree.NewTree(merkletree.WithData(data))
if err != nil {
panic(err)
}
// Fetch the root hash of the tree
root := tree.Root()
baz := data[2]
// Generate a proof for 'Baz'
proof, err := tree.GenerateProof(baz, 0)
if err != nil {
panic(err)
}
// Verify the proof for 'Baz'
verified, err := merkletree.VerifyProof(baz, false, proof, [][]byte{root})
if err != nil {
panic(err)
}
if !verified {
panic("failed to verify proof for Baz")
}
}Jim McDonald: @mcdee.
Contributions welcome. Please check out the issues.
Apache-2.0 © 2019 Weald Technology Trading Ltd