commit

Documentation

Overview

Package commit computes RFC 6962 Merkle roots and inclusion paths: the root a store reference commits to, one per named store, over the commitments (carrier txids) of that store's members.

Domain separation is the point of RFC 6962's prefixes: a leaf hash and an interior node hash can never collide, so a member cannot be passed off as a subtree or the other way round. The prefixes are frozen at an application's first mint along with everything else a reader recomputes.

Index

• Variables
• func HashLeaf(leaf []byte) [32]byte
• func LeafHash(leaf [32]byte) [32]byte
• func NodeHash(left, right [32]byte) [32]byte
• func PathLen(index, size uint64) (int, error)
• func Root(leaves [][32]byte) [32]byte
• func RootOfBytes(leaves [][]byte) [32]byte
• func RootOfLeafHashes(hashes [][32]byte) [32]byte
• func RootOfSubtrees(roots [][32]byte) ([32]byte, error)
• func SegmentRoot(content []byte, size int) ([32]byte, error)
• func Verify(leaf [32]byte, path Path, root [32]byte) bool
• func VerifyAt(leafHash [32]byte, index, size uint64, siblings [][32]byte, root [32]byte) bool
• func VerifyBytes(leaf []byte, path Path, root [32]byte) bool
• type Builder
  • func (b *Builder) Add(leafHash [32]byte)
  • func (b *Builder) AddBytes(leaf []byte)
  • func (b *Builder) Root() [32]byte
  • func (b *Builder) Size() uint64
• type Path
  • func Prove(leaves [][32]byte, index int) (Path, error)
  • func ProveBytes(leaves [][]byte, index int) (Path, error)
  • func ProveLeafHashes(hashes [][32]byte, index int) (Path, error)
  • func ProveSubtrees(roots [][32]byte, index int) (Path, error)
  • func (p Path) Siblings() [][32]byte
• type SegmentWriter
  • func NewSegmentWriter(size int) (*SegmentWriter, error)
  • func (w *SegmentWriter) Root() [32]byte
  • func (w *SegmentWriter) Segments() uint64
  • func (w *SegmentWriter) Write(p []byte) (int, error)
• type Step

Examples

• Prove
• Root

Variables

var ErrIndex = errors.New("commit: index out of range")

ErrIndex reports an index outside the leaf set.

var ErrNoSubtrees = errors.New("commit: no subtree roots")

ErrNoSubtrees reports RootOfSubtrees over no subtrees.

var ErrSegmentSize = errors.New("commit: segment size must be positive")

ErrSegmentSize reports a segment size that is not positive.

Functions

func HashLeaf

func HashLeaf(leaf []byte) [32]byte

HashLeaf is SHA-256(0x00 || leaf) for a leaf of any length. For a 32-byte leaf it equals LeafHash.

func LeafHash

func LeafHash(leaf [32]byte) [32]byte

LeafHash is SHA-256(0x00 || leaf).

func NodeHash

func NodeHash(left, right [32]byte) [32]byte

NodeHash is SHA-256(0x01 || left || right).

func PathLen

func PathLen(index, size uint64) (int, error)

PathLen is the length of the RFC 6962 audit path of leaf index in a tree of size leaves: what a verifier checks a compact path's length against before it hashes anything. Index and size are 64-bit so that a tree of more than 2^31 leaves is described on every platform.

func Root

func Root(leaves [][32]byte) [32]byte

Root is the RFC 6962 root over leaves in order. The empty tree's root is SHA-256 of the empty string, as the RFC defines it, so an empty store still has one well-defined commitment.

Example

Root is the RFC 6962 Merkle Tree Hash over the leaves in order. The root printed here is the independent generator's root for the same five leaves.

package main

import (
	"crypto/sha256"
	"fmt"

	"github.com/lightwebinc/bcommon/commit"
)

// leaves returns n 32-byte leaves, SHA-256 of the single byte i for leaf i:
// the first n leaves of testdata/vectors/rfc6962-v1.json.
func leaves(n int) [][32]byte {
	out := make([][32]byte, n)
	for i := range out {
		out[i] = sha256.Sum256([]byte{byte(i)})
	}
	return out
}

func main() {
	fmt.Printf("%x\n", commit.Root(leaves(5)))
	// The empty tree's root is SHA-256 of the empty string.
	fmt.Printf("%x\n", commit.Root(nil))
}

Output:
6b313b611b40676b9e1dfd70c4503f2379f88f0f1c2740fb7e1cacc32c113465
e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855

func RootOfBytes

func RootOfBytes(leaves [][]byte) [32]byte

RootOfBytes is the RFC 6962 root over leaves of any length, in order. The empty tree's root is SHA-256 of the empty string.

func RootOfLeafHashes

func RootOfLeafHashes(hashes [][32]byte) [32]byte

RootOfLeafHashes is the RFC 6962 root over leaves already hashed with HashLeaf (or LeafHash), in order: what a holder that kept only the leaf hashes recomputes. The empty tree's root is SHA-256 of the empty string.

func RootOfSubtrees

func RootOfSubtrees(roots [][32]byte) ([32]byte, error)

RootOfSubtrees is the RFC 6962 split applied to subtree roots, each taken as a node and never hashed again as a leaf. It equals the root over the subtrees' leaves only when every subtree but the last covers the same power-of-two number of leaves and the last covers at most that many: an object cut into fixed blocks of 2^k leaves, one root per block. Then RFC 6962's split at the largest power of two below the leaf count always falls on a block boundary, and the two descriptions are one tree. No subtrees is ErrNoSubtrees, since the empty tree has no subtree roots.

func SegmentRoot

func SegmentRoot(content []byte, size int) ([32]byte, error)

SegmentRoot is the RFC 6962 root over content cut into segments of size bytes from offset 0, the last holding the remainder unpadded. Content of no bytes has no segments and its root is SHA-256 of the empty string.

func Verify

func Verify(leaf [32]byte, path Path, root [32]byte) bool

Verify recomputes the root from leaf and path and compares it with root.

func VerifyAt

func VerifyAt(leafHash [32]byte, index, size uint64, siblings [][32]byte, root [32]byte) bool

VerifyAt checks a compact audit path: leafHash (HashLeaf of the leaf) at index in a tree of size leaves, with siblings leaf to root and no sides, against root. Every side follows from index and size, by the inclusion check of RFC 9162 section 2.1.3.2. A path longer or shorter than PathLen fails.

func VerifyBytes

func VerifyBytes(leaf []byte, path Path, root [32]byte) bool

VerifyBytes recomputes the root from a leaf of any length and its path and compares it with root.

Types

type Builder

type Builder struct {
	// contains filtered or unexported fields
}

Builder computes an RFC 6962 root over leaves added one at a time, holding one hash per set bit of the count: a root over more leaves than fit in memory, such as the segments of a large object read as a stream.

func (*Builder) Add

func (b *Builder) Add(leafHash [32]byte)

Add appends a leaf already hashed with HashLeaf.

func (*Builder) AddBytes

func (b *Builder) AddBytes(leaf []byte)

AddBytes appends a leaf of any length.

func (*Builder) Root

func (b *Builder) Root() [32]byte

Root is the RFC 6962 root over the leaves added so far: the complete subtrees folded right to left, which is the RFC's split at the largest power of two at every level. With no leaves it is SHA-256 of the empty string. Adding more leaves afterwards is allowed.

func (*Builder) Size

func (b *Builder) Size() uint64

Size is the number of leaves added.

type Path

type Path []Step

Path is an inclusion path from a leaf to the root.

func Prove

func Prove(leaves [][32]byte, index int) (Path, error)

Prove returns the inclusion path for leaves[index].

Example

Prove gives the inclusion path of one leaf, and Verify recomputes the root from the leaf and the path. A path verifies only its own leaf.

package main

import (
	"crypto/sha256"
	"fmt"

	"github.com/lightwebinc/bcommon/commit"
)

// leaves returns n 32-byte leaves, SHA-256 of the single byte i for leaf i:
// the first n leaves of testdata/vectors/rfc6962-v1.json.
func leaves(n int) [][32]byte {
	out := make([][32]byte, n)
	for i := range out {
		out[i] = sha256.Sum256([]byte{byte(i)})
	}
	return out
}

func main() {
	ls := leaves(5)
	root := commit.Root(ls)

	path, err := commit.Prove(ls, 2)
	if err != nil {
		fmt.Println(err)
		return
	}
	for _, s := range path {
		fmt.Printf("sibling %x... left=%t\n", s.Hash[:4], s.Left)
	}
	fmt.Println("leaf 2 verifies:", commit.Verify(ls[2], path, root))
	fmt.Println("leaf 3 on leaf 2's path verifies:", commit.Verify(ls[3], path, root))

	_, err = commit.Prove(ls, 5)
	fmt.Println(err)
}

Output:
sibling 36e4970e... left=false
sibling 604d540f... left=true
sibling 12d24297... left=false
leaf 2 verifies: true
leaf 3 on leaf 2's path verifies: false
commit: index out of range

func ProveBytes

func ProveBytes(leaves [][]byte, index int) (Path, error)

ProveBytes returns the RFC 6962 audit path of leaves[index], leaf to root.

func ProveLeafHashes

func ProveLeafHashes(hashes [][32]byte, index int) (Path, error)

ProveLeafHashes returns the audit path of the leaf at index from the leaf hashes alone.

func ProveSubtrees

func ProveSubtrees(roots [][32]byte, index int) (Path, error)

ProveSubtrees returns the path of subtree root roots[index] up to RootOfSubtrees(roots), under the same condition on the subtrees. A leaf's whole audit path is its path within its subtree followed by this one.

func (Path) Siblings

func (p Path) Siblings() [][32]byte

Siblings returns a path's hashes without their sides: the compact form a proof sends when the verifier knows the index and the leaf count, from which every side follows (VerifyAt).

type SegmentWriter

type SegmentWriter struct {
	// contains filtered or unexported fields
}

SegmentWriter is SegmentRoot over content written in pieces of any size. It holds at most one segment.

func NewSegmentWriter

func NewSegmentWriter(size int) (*SegmentWriter, error)

NewSegmentWriter returns a writer that cuts what it is given into segments of size bytes.

func (*SegmentWriter) Root

func (w *SegmentWriter) Root() [32]byte

Root is the root over the content written so far, a partial last segment included as it is. Writing more afterwards is allowed.

func (*SegmentWriter) Segments

func (w *SegmentWriter) Segments() uint64

Segments is the number of segments the content written so far makes, counting a partial last one.

func (*SegmentWriter) Write

func (w *SegmentWriter) Write(p []byte) (int, error)

Write takes content in order. It never fails.

type Step

type Step struct {
	Hash [32]byte
	// Left is true when the sibling sits to the LEFT of the node being
	// proven, so the verifier hashes NodeHash(sibling, current).
	Left bool
}

Step is one sibling on an inclusion path.