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 LeafHash(leaf [32]byte) [32]byte
• func NodeHash(left, right [32]byte) [32]byte
• func Root(leaves [][32]byte) [32]byte
• func Verify(leaf [32]byte, path Path, root [32]byte) bool
• type Path
  • func Prove(leaves [][32]byte, index int) (Path, error)
• type Step

Examples

• Prove
• Root

Variables

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

ErrIndex reports an index outside the leaf set.

Functions

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 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 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.

Types

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

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.