Documentation ¶
Overview ¶
Package merkletree is an implementation of a Merkle tree (https://en.wikipedia.org/wiki/Merkle_tree). It provides methods to create a tree and generate and verify proofs. The hashing algorithm for the tree is selectable between BLAKE2b and Keccak256, or you can supply your own.
This implementation includes advanced features salting and pollarding. Salting is the act of adding a piece of data to each value in the Merkle tree as it is initially hashed to form the leaves, which helps avoid rainbow table attacks on leaf hashes presented as part of proofs. Pollarding is the act of providing the root plus all branches to a certain height which can be used to reduce the size of proofs. This is useful when multiple proofs are presented against the same tree as it can reduce the overall size.
Creating a Merkle tree requires a list of values that are each byte arrays. Once a tree has been created proofs can be generated using the tree's GenerateProof() function.
The package includes a function VerifyProof() to verify a generated proof given only the data to prove, proof and the pollard of the relevant Merkle tree. This allows for efficient verification of proofs without requiring the entire Merkle tree to be stored or recreated.
Implementation notes ¶
The tree pads its values to the next highest power of 2; values not supplied are treated as null with a value hash of 0. This can be seen graphically by generating a DOT representation of the graph with DOT().
If salting is enabled it appends an 4-byte value to each piece of data. The value is the binary representation of the index in big-endian form. Note that if there are more than 2^32 values in the tree the salt will wrap, being modulo 2^32
Package merkletree is an implementation of a Merkle tree (https://en.wikipedia.org/wiki/Merkle_tree). It provides methods to create a tree and generate and verify proofs. The hashing algorithm for the tree is selectable between BLAKE2b and Keccak256, or you can supply your own.
This implementation includes advanced features salting and pollarding. Salting is the act of adding a piece of data to each value in the Merkle tree as it is initially hashed to form the leaves, which helps avoid rainbow table attacks on leaf hashes presented as part of proofs. Pollarding is the act of providing the root plus all branches to a certain height which can be used to reduce the size of proofs. This is useful when multiple proofs are presented against the same tree as it can reduce the overall size.
Creating a Merkle tree requires a list of values that are each byte arrays. Once a tree has been created proofs can be generated using the tree's GenerateProof() function.
The package includes a function VerifyProof() to verify a generated proof given only the data to prove, proof and the pollard of the relevant Merkle tree. This allows for efficient verification of proofs without requiring the entire Merkle tree to be stored or recreated.
Implementation notes ¶
The tree pads its values to the next highest power of 2; values not supplied are treated as null with a value hash of 0. This can be seen graphically by generating a DOT representation of the graph with DOT().
If salting is enabled it appends an 4-byte value to each piece of data. The value is the binary representation of the index in big-endian form. Note that if there are more than 2^32 values in the tree the salt will wrap, being modulo 2^32
Index ¶
- func VerifyMultiProof(data [][]byte, salt bool, proof *MultiProof, root []byte) (bool, error)deprecated
- func VerifyMultiProofUsing(data [][]byte, salt bool, proof *MultiProof, root []byte, hashType HashType) (bool, error)deprecated
- func VerifyPollard(pollard [][]byte) bool
- func VerifyPollardUsing(pollard [][]byte, hashType HashType) bool
- func VerifyProof(data []byte, salt bool, proof *Proof, pollard [][]byte) (bool, error)
- func VerifyProofUsing(data []byte, salt bool, proof *Proof, pollard [][]byte, hashType HashType) (bool, error)
- type Formatter
- type HashFunc
- type HashType
- type HexFormatter
- type MerkleTree
- func (t *MerkleTree) DOT(lf Formatter, bf Formatter) string
- func (t *MerkleTree) DOTMultiProof(multiProof *MultiProof, lf Formatter, bf Formatter) string
- func (t *MerkleTree) DOTProof(proof *Proof, lf Formatter, bf Formatter) string
- func (t *MerkleTree) GenerateMultiProof(data [][]byte) (*MultiProof, error)
- func (t *MerkleTree) GenerateMultiProofWithIndices(indices []uint64) (*MultiProof, error)
- func (t *MerkleTree) GenerateProof(data []byte, height int) (*Proof, error)
- func (t *MerkleTree) GenerateProofWithIndex(index uint64, height int) (*Proof, error)
- func (t *MerkleTree) GetSalt() bool
- func (t *MerkleTree) MarshalJSON() ([]byte, error)
- func (t *MerkleTree) Pollard(height int) [][]byte
- func (t *MerkleTree) Root() []byte
- func (t *MerkleTree) String() string
- func (t *MerkleTree) UnmarshalJSON(data []byte) error
- type MultiProof
- type Parameter
- type Proof
- type StringFormatter
- type TruncatedHexFormatter
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func VerifyMultiProof
deprecated
VerifyMultiProof verifies multiple Merkle tree proofs for pieces of data using the default hash type. The proof and path are as per Merkle tree's GenerateProof(), and root is the root hash of the tree against which the proof is to be verified. Note that this does not require the Merkle tree to verify the proof, only its root; this allows for checking against historical trees without having to instantiate them.
This returns true if the proof is verified, otherwise false.
Deprecated: please use MultiProof.Verify(...)
func VerifyMultiProofUsing
deprecated
func VerifyMultiProofUsing(data [][]byte, salt bool, proof *MultiProof, root []byte, hashType HashType) (bool, error)
VerifyMultiProofUsing verifies multiple Merkle tree proofs for pieces of data using the provided hash type. The proof and is as per Merkle tree's GenerateProof(), and root is the root hash of the tree against which the proof is to be verified. Note that this does not require the Merkle tree to verify the proof, only its root; this allows for checking against historical trees without having to instantiate them.
This returns true if the proof is verified, otherwise false.
Deprecated: please use MultiProof.Verify(...)
func VerifyPollard ¶
VerifyPollard ensures that the branches in the pollard match up with the root using the default hash type.
func VerifyPollardUsing ¶
VerifyPollardUsing ensures that the branches in the pollard match up with the root using the supplied hash type.
func VerifyProof ¶
VerifyProof verifies a Merkle tree proof for a piece of data using the default hash type. The proof and path are as per Merkle tree's GenerateProof(), and root is the root hash of the tree against which the proof is to be verified. Note that this does not require the Merkle tree to verify the proof, only its root; this allows for checking against historical trees without having to instantiate them.
This returns true if the proof is verified, otherwise false.
func VerifyProofUsing ¶
func VerifyProofUsing(data []byte, salt bool, proof *Proof, pollard [][]byte, hashType HashType) (bool, error)
VerifyProofUsing verifies a Merkle tree proof for a piece of data using the provided hash type. The proof and is as per Merkle tree's GenerateProof(), and root is the root hash of the tree against which the proof is to be verified. Note that this does not require the Merkle tree to verify the proof, only its root; this allows for checking against historical trees without having to instantiate them.
This returns true if the proof is verified, otherwise false.
Types ¶
type Formatter ¶
Formatter formats a []byte in to a string. It is used by DOT() to provide users with the required format for the graphical display of their Merkle trees.
type HashType ¶
type HashType interface { // Hash calculates the hash of a given input. Hash(data ...[]byte) []byte // HashName returns the name of the hashing algorithm to be used in encoding HashName() string // HashLength provides the length of the hash. HashLength() int }
HashType defines the interface that must be supplied by hash functions.
type HexFormatter ¶
type HexFormatter struct{}
HexFormatter shows the entire value.
func (*HexFormatter) Format ¶
func (*HexFormatter) Format(data []byte) string
Format formats a value as a full hex string.
type MerkleTree ¶
type MerkleTree struct { // if Salt is true the Data values are salted with their index Salt bool `json:"salt"` // if Sorted is true, the Hash values are Sorted before hashing branch Nodes Sorted bool `json:"sorted"` // Hash is a pointer to the hashing struct Hash HashType `json:"hash_type"` // Data is the Data from which the Merkle tree is created Data [][]byte `json:"data"` // Nodes are the leaf and branch Nodes of the Merkle tree Nodes [][]byte `json:"nodes"` }
MerkleTree is the structure for the Merkle tree.
Example ¶
Example using the Merkle tree to generate and verify proofs.
package main import ( "fmt" merkletree "github.com/wealdtech/go-merkletree/v2" ) func main() { // Data for the tree data := [][]byte{ []byte("Foo"), []byte("Bar"), []byte("Baz"), } // Create the tree tree, err := merkletree.New(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") } fmt.Printf("%x\n", root) }
Output: 2c95331b1a38dba3600391a3e864f9418a271388936e54edecd916824bb54203
func New ¶
func New(data [][]byte) (*MerkleTree, error)
New creates a new Merkle tree using the provided raw data and default hash type. Salting is not used. data must contain at least one element for it to be valid. Deprecated: plase use NewTree().
func NewTree ¶
func NewTree(params ...Parameter) (*MerkleTree, error)
NewTree creates a new merkle tree using the provided information.
func NewUsing ¶
func NewUsing(data [][]byte, hash HashType, salt bool) (*MerkleTree, error)
NewUsing creates a new Merkle tree using the provided raw data and supplied hash type. Salting is used, and hashes are sorted if requested. data must contain at least one element for it to be valid. Deprecated: plase use NewTree().
func (*MerkleTree) DOT ¶
func (t *MerkleTree) DOT(lf Formatter, bf Formatter) string
DOT creates a DOT representation of the tree. It is generally used for external presentation. This takes two optional formatters for []byte data: the first for leaf data and the second for branches.
func (*MerkleTree) DOTMultiProof ¶
func (t *MerkleTree) DOTMultiProof(multiProof *MultiProof, lf Formatter, bf Formatter) string
DOTMultiProof creates a DOT representation of the tree with highlights for a multiproof. It is generally used for external presentation. This takes two optional formatters for []byte data: the first for leaf data and the second for branches.
func (*MerkleTree) DOTProof ¶
func (t *MerkleTree) DOTProof(proof *Proof, lf Formatter, bf Formatter) string
DOTProof creates a DOT representation of the tree with highlights for a proof. It is generally used for external presentation. This takes two optional formatters for []byte data: the first for leaf data and the second for branches.
func (*MerkleTree) GenerateMultiProof ¶
func (t *MerkleTree) GenerateMultiProof(data [][]byte) (*MultiProof, error)
GenerateMultiProof generates the proof for multiple pieces of data.
func (*MerkleTree) GenerateMultiProofWithIndices ¶ added in v2.6.0
func (t *MerkleTree) GenerateMultiProofWithIndices(indices []uint64) (*MultiProof, error)
GenerateMultiProofWithIndices generates the proof for multiple pieces of data.
func (*MerkleTree) GenerateProof ¶
func (t *MerkleTree) GenerateProof(data []byte, height int) (*Proof, error)
GenerateProof generates the proof for a piece of data. Height is the height of the pollard to verify the proof. If using the Merkle root to verify this should be 0. If the data is not present in the tree this will return an error. If the data is present in the tree this will return the hashes for each level in the tree and the index of the value in the tree.
func (*MerkleTree) GenerateProofWithIndex ¶ added in v2.6.0
func (t *MerkleTree) GenerateProofWithIndex(index uint64, height int) (*Proof, error)
GenerateProofWithIndex generates the proof for the data at the given index. It is faster than GenerateProof() if the index is already known. Height is the height of the pollard to verify the proof. If using the Merkle root to verify this should be 0. If the index is out of range this will return an error. If the data is present in the tree this will return the hashes for each level in the tree and the index of the value in the tree.
func (*MerkleTree) GetSalt ¶
func (t *MerkleTree) GetSalt() bool
GetSalt returns the true if the values in this Merkle tree are salted.
func (*MerkleTree) MarshalJSON ¶
func (t *MerkleTree) MarshalJSON() ([]byte, error)
MarshalJSON implements json.Marshaler.
func (*MerkleTree) Pollard ¶
func (t *MerkleTree) Pollard(height int) [][]byte
Pollard returns the Merkle root plus branches to a certain height. Height 0 will return just the root, height 1 the root plus the two branches directly above it, height 2 the root, two branches directly above it and four branches directly above them, etc.
func (*MerkleTree) Root ¶
func (t *MerkleTree) Root() []byte
Root returns the Merkle root (hash of the root node) of the tree.
func (*MerkleTree) String ¶
func (t *MerkleTree) String() string
String implements the stringer interface.
func (*MerkleTree) UnmarshalJSON ¶
func (t *MerkleTree) UnmarshalJSON(data []byte) error
UnmarshalJSON implements json.Unmarshaler.
type MultiProof ¶
type MultiProof struct { // Values is the number of values in the Merkle tree. Values uint64 // Hashes are indexed hashes of values that cannot be calculated from the index data Hashes map[uint64][]byte // Indices are the indices of the data that can be proved with the hashes Indices []uint64 // contains filtered or unexported fields }
MultiProof is a single structure containing multiple proofs of a Merkle tree.
func NewMultiProof ¶
func NewMultiProof(params ...Parameter) (*MultiProof, error)
NewMultiProof creates a new multiproof using the provided information.
type Parameter ¶
type Parameter interface {
// contains filtered or unexported methods
}
Parameter is the interface for service parameters.
func WithHashType ¶
WithHashType sets the hash type for the merkle tree or proof.
func WithHashes ¶
WithHashes sets the indexed hashes of values that cannot be calculated from the proof.
func WithIndices ¶
WithIndices sets the indices that can be calculated from the proof.
func WithSorted ¶
WithSorted sets the sorted for the merkle tree.
func WithValues ¶
WithValues sets the values for the merkle proof.
type StringFormatter ¶
type StringFormatter struct{}
StringFormatter shows the entire value as a string.
func (*StringFormatter) Format ¶
func (*StringFormatter) Format(data []byte) string
Format formats a value as a UTF-8 string.
type TruncatedHexFormatter ¶
type TruncatedHexFormatter struct{}
TruncatedHexFormatter shows only the first and last two bytes of the value.
func (*TruncatedHexFormatter) Format ¶
func (*TruncatedHexFormatter) Format(data []byte) string
Format formats a value as truncated hex, showing the first and last four characers of the hex string.
Source Files ¶
Directories ¶
Path | Synopsis |
---|---|
Package blake2b provides hashing using the BLAKE 2b system.
|
Package blake2b provides hashing using the BLAKE 2b system. |
Package keccak256 provides hashing using the Keccak256 system.
|
Package keccak256 provides hashing using the Keccak256 system. |
Package poseidon provides hashing using the Poseidon system.
|
Package poseidon provides hashing using the Poseidon system. |
Package sha3 provides hashing using the SHA3 system.
|
Package sha3 provides hashing using the SHA3 system. |