merkle

Documentation

Overview

Package merkle provides functions and types to deal with the creation and storage of Merkle trees, using the secure SHAKE256 KDF implemented in the signing/key package: thus not being affected by the the infamous M-Bug.

Index

• Variables
• func MerkleRoot(leafHash trinary.Hash, leafIndex uint32, auditPath []trinary.Hash, ...) (trinary.Hash, error)
• func SignatureFragments(seed Hash, leafIndex uint32, securityLvl SecurityLevel, hashToSign Hash, ...) ([]Trytes, error)
• func StoreMerkleTreeFile(filePath string, merkleTree *MerkleTree) error
• func ValidateSignatureFragments(expectedRoot Hash, leafIndex uint32, auditPath []Hash, fragments []Trytes, ...) (bool, error)
• type MerkleCreateOptions
• type MerkleTree
  • func CreateMerkleTree(seed trinary.Hash, securityLvl consts.SecurityLevel, depth int, ...) (*MerkleTree, error)
  • func LoadMerkleTreeFile(filePath string) (*MerkleTree, error)
  • func (mt *MerkleTree) AuditPath(leafIndex uint32) ([]trinary.Hash, error)
  • func (mt *MerkleTree) ReadFrom(reader io.Reader) (n int64, err error)
  • func (mt *MerkleTree) WriteTo(writer io.Writer) (n int64, err error)
• type MerkleTreeLayer
  • func (mtl *MerkleTreeLayer) ReadFrom(reader io.Reader) (n int64, err error)
  • func (mtl *MerkleTreeLayer) WriteTo(writer io.Writer) (int64, error)

Variables

var (
	// ErrDepthTooSmall is returned when the depth for creating the Merkle tree is too low.
	ErrDepthTooSmall = errors.New("depth must be positive")
	// ErrDepthTooLarge is returned when the depth for creating the Merkle tree is too high.
	ErrDepthTooLarge = errors.New("largest depth is 32")
	// ErrInvalidAuditPathLength is returned when the length of the Merkle audit path does not match the leaf index.
	ErrInvalidAuditPathLength = errors.New("invalid length of the audit path")
	// ErrInvalidLeafIndex is returned for invalid leaf indices.
	ErrInvalidLeafIndex = errors.New("invalid leaf index")
)

Functions

func MerkleRoot

func MerkleRoot(leafHash trinary.Hash, leafIndex uint32, auditPath []trinary.Hash, spongeFunc ...sponge.SpongeFunction) (trinary.Hash, error)

MerkleRoot computes the Merkle tree root from a leaf hash and the given audit path. Optionally takes the SpongeFunction to use. Default is Kerl.

func SignatureFragments

func SignatureFragments(seed Hash, leafIndex uint32, securityLvl SecurityLevel, hashToSign Hash, spongeFunc ...sponge.SpongeFunction) ([]Trytes, error)

SignatureFragments returns the signed fragments of hashToSign for the given seed and leafIndex. Optionally takes the SpongeFunction to use. Default is Kerl.

func StoreMerkleTreeFile

func StoreMerkleTreeFile(filePath string, merkleTree *MerkleTree) error

StoreMerkleTreeFile stores the MerkleTree structure in a binary output file.

func ValidateSignatureFragments

func ValidateSignatureFragments(expectedRoot Hash, leafIndex uint32, auditPath []Hash, fragments []Trytes, hashToSign Hash, spongeFunc ...sponge.SpongeFunction) (bool, error)

ValidateSignatureFragments validates the given signature fragments by checking whether the address computed from hashToSign and fragments validates the Merkle proof. Optionally takes the SpongeFunction to use. Default is Kerl.

Types

type MerkleCreateOptions

type MerkleCreateOptions struct {
	// CalculateAddressesStartCallback will be called at the start of leaf generation, with the total count of the leaves.
	CalculateAddressesStartCallback func(count uint32)
	// CalculateAddressesCallback will be called after each leaf generation, with the corresponding index.
	CalculateAddressesCallback func(index uint32)
	// CalculateAddressesFinishedCallback will be called after leaf generation is finished, with the total count of the leaves.
	CalculateAddressesFinishedCallback func(count uint32)
	// CalculateLayersCallback will be called before each layer generation, with the corresponding index.
	CalculateLayersCallback func(index uint32)
	// The number of parallel threads used by the generation routines.
	Parallelism int
}

MerkleCreateOptions is used to pass optional creation options to CreateMerkleTree.

type MerkleTree

type MerkleTree struct {
	// The depth of the Merkle tree.
	Depth int
	// The root address of the Merkle tree.
	Root trinary.Hash
	// Merkle tree layers indexed by their level.
	Layers []*MerkleTreeLayer
}

MerkleTree contains the Merkle tree used for the coordinator signatures.

func CreateMerkleTree

func CreateMerkleTree(seed trinary.Hash, securityLvl consts.SecurityLevel, depth int, opts ...MerkleCreateOptions) (*MerkleTree, error)

CreateMerkleTree creates a MerkleTree structure of the specified depth, using a SHAKE256 key of the the length specified by the supplied securitylevel, deriving subseeds from the provided seed. An optional MerkleCreateOptions struct can be passed to specify function's parallelism and progress callback.

func LoadMerkleTreeFile

func LoadMerkleTreeFile(filePath string) (*MerkleTree, error)

LoadMerkleTreeFile loads a binary file persisted with StoreMerkleTreeFile into a MerkleTree structure.

func (*MerkleTree) AuditPath

func (mt *MerkleTree) AuditPath(leafIndex uint32) ([]trinary.Hash, error)

AuditPath returns the Merkle audit path for the provided leaf. The audit path is the slice of missing hashes required to compute the nodes from the leaf to the root of the tree.

func (*MerkleTree) ReadFrom

func (mt *MerkleTree) ReadFrom(reader io.Reader) (n int64, err error)

ReadFrom parses the binary encoded representation of the Merkle tree from a buffer.

func (*MerkleTree) WriteTo

func (mt *MerkleTree) WriteTo(writer io.Writer) (n int64, err error)

WriteTo writes the binary representation of the Merkle tree to a buffer.

type MerkleTreeLayer

type MerkleTreeLayer struct {
	// The level of the layer in the tree.
	Level int
	// The nodes of the layer.
	Hashes []trinary.Hash
}

MerkleTreeLayer contains the nodes of a layer of a Merkle tree.

func (*MerkleTreeLayer) ReadFrom

func (mtl *MerkleTreeLayer) ReadFrom(reader io.Reader) (n int64, err error)

ReadFrom parses the binary encoded representation of the Merkle tree layer from a buffer.

func (*MerkleTreeLayer) WriteTo

func (mtl *MerkleTreeLayer) WriteTo(writer io.Writer) (int64, error)

WriteTo writes the binary representation of the Merkle tree layer to a buffer.