merkle

Documentation

Overview

merkle handles creating Merkle trees. The method of creation is modeled after Certificate Transparency.

https://datatracker.ietf.org/doc/html/rfc9162#section-2.1

Index

• Constants
• func CalcInclusionProof(proof *InclusionProof, reader io.Reader) ([]byte, error)
• func HashLeaf(r io.Reader, nonce Nonce) ([]byte, error)
• type InclusionProof
  • func GetInclusionProof(root *Node, n, m uint64) (*InclusionProof, error)
• type Node
  • func CreateLeaf(name string, r io.Reader, nonce Nonce) (*Node, error)
  • func CreateTree(leaves []*Node) *Node
  • func GetLeaf(root *Node, n, m uint64) (*Node, error)
  • func (n *Node) DotGraph(w io.Writer) error
  • func (n *Node) String() string
• type Nonce

Constants

const (
	NonceSize  = 16 // 128 bits
	Blake3Size = 32 // 256 bits, like SHA2
)

Functions

func CalcInclusionProof

func CalcInclusionProof(proof *InclusionProof, reader io.Reader) ([]byte, error)

CalcInclusion proof gets the root hash for the given inclusion proof.

The proof argument is the result of GetInclusionProof.

An error is not returned if the inclusion proof was not verified.

Note the inclusion proof may or may not be valid, it depends on what root hash you are expecting. The root hash must be verified outside of this function.

func HashLeaf

func HashLeaf(r io.Reader, nonce Nonce) ([]byte, error)

Types

type InclusionProof

type InclusionProof struct {
	LeafIndex uint64   // zero-indexed leaf number, from left to right
	TreeSize  uint64   // number of leaves
	Nonce     []byte   // Nonce for proven leaf
	Proof     [][]byte // Node hashes, in bottom-to-top order
}

func GetInclusionProof

func GetInclusionProof(root *Node, n, m uint64) (*InclusionProof, error)

GetInclusionProof returns a Merkle inclusion proof for the given tree and leaf.

The leaf is indicated by an index argument, m. The first leaf in the tree is m=0, and so on. If the given leaf index doesn't exist, the function returns an error.

The argument n is the total number of leaves in the tree. If that ends being incorrect, the function returns an error.

type Node

type Node struct {
	Hash  []byte
	Name  string `cbor:",omitempty"` // Filepath, used for leaf nodes
	Left  *Node  `cbor:",omitempty"` // Nil for leaves
	Right *Node  `cbor:",omitempty"` // Nil for leaves
	// Random nonce that was prepended to data before calculating hash
	// Only used for leaf nodes to anonymize actual file hash
	Nonce Nonce `cbor:",omitempty"`
}

func CreateLeaf

func CreateLeaf(name string, r io.Reader, nonce Nonce) (*Node, error)

CreateLeaf creates a leaf node. A random nonce is generated and used if the provided one is nil. The only possible errors are ones returned from the io.Reader, or those raised during random number generation.

func CreateTree

func CreateTree(leaves []*Node) *Node

CreateTree create a Merkle tree from the given leaves. Leaves are used in the provided order. The root node of the newly-formed tree is returned.

func GetLeaf

func GetLeaf(root *Node, n, m uint64) (*Node, error)

GetLeaf walks the given tree and returns the requested leaf. It works similarly to GetInclusionProof, and returns errors in the same way.

func (*Node) DotGraph

func (n *Node) DotGraph(w io.Writer) error

DotGraph writes a complete directed graph for the tree that this node is the root of. It uses the DOT language. If an error is returned, the written bytes are likely not a valid DOT file.

func (*Node) String

func (n *Node) String() string

type Nonce

type Nonce []byte