hashtree

Documentation

Overview

Example (B)

package main

import (
	"fmt"

	"github.com/aviate-labs/agent-go/certification/hashtree"
)

func main() {
	fmt.Printf("%x", hashtree.Leaf("good").Reconstruct())
}

Output:

7b32ac0c6ba8ce35ac82c255fc7906f7fc130dab2a090f80fe12f9c2cae83ba6

Example (C)

package main

import (
	"fmt"

	"github.com/aviate-labs/agent-go/certification/hashtree"
)

func main() {
	fmt.Printf("%x", hashtree.Labeled{
		Label: []byte("c"),
		Tree:  hashtree.Empty{},
	}.Reconstruct())
}

Output:

ec8324b8a1f1ac16bd2e806edba78006479c9877fed4eb464a25485465af601d

Example (Root)

package main

import (
	"fmt"

	"github.com/aviate-labs/agent-go/certification/hashtree"
)

var tree = hashtree.Fork{
	LeftTree: hashtree.Fork{
		LeftTree: hashtree.Labeled{
			Label: []byte("a"),
			Tree: hashtree.Fork{
				LeftTree: hashtree.Fork{
					LeftTree: hashtree.Labeled{
						Label: []byte("x"),
						Tree:  hashtree.Leaf("hello"),
					},
					RightTree: hashtree.Empty{},
				},
				RightTree: hashtree.Labeled{
					Label: []byte("y"),
					Tree:  hashtree.Leaf("world"),
				},
			},
		},
		RightTree: hashtree.Labeled{
			Label: []byte("b"),
			Tree:  hashtree.Leaf("good"),
		},
	},
	RightTree: hashtree.Fork{
		LeftTree: hashtree.Labeled{
			Label: []byte("c"),
			Tree:  hashtree.Empty{},
		},
		RightTree: hashtree.Labeled{
			Label: []byte("d"),
			Tree:  hashtree.Leaf("morning"),
		},
	},
}

func main() {
	fmt.Printf("%x", tree.Reconstruct())
}

Output:

eb5c5b2195e62d996b84c9bcc8259d19a83786a2f59e0878cec84c811f669aa0

Example (X)

Source: https://sdk.dfinity.org/docs/interface-spec/index.html#_example ─┬─┬╴"a" ─┬─┬╴"x" ─╴"hello"

│ │      │ └╴Empty
│ │      └╴  "y" ─╴"world"
│ └╴"b" ──╴"good"
└─┬╴"c" ──╴Empty
  └╴"d" ──╴"morning"

package main

import (
	"fmt"

	"github.com/aviate-labs/agent-go/certification/hashtree"
)

func main() {
	fmt.Printf("%x", hashtree.Fork{
		LeftTree: hashtree.Labeled{
			Label: []byte("x"),
			Tree:  hashtree.Leaf("hello"),
		},
		RightTree: hashtree.Empty{},
	}.Reconstruct())
}

Output:

1b4feff9bef8131788b0c9dc6dbad6e81e524249c879e9f10f71ce3749f5a638

Index

• func DomainSeparator(t string) []byte
• func ListPaths(n Node, path []Label) [][]Label
• func Serialize(node Node) ([]byte, error)
• type Empty
  • func (e Empty) Reconstruct() [32]byte
  • func (e Empty) String() string
• type Fork
  • func (f Fork) Reconstruct() [32]byte
  • func (f Fork) String() string
• type HashTree
  • func NewHashTree(root Node) HashTree
  • func (t HashTree) Digest() [32]byte
  • func (t HashTree) Lookup(path ...Label) ([]byte, error)
  • func (t HashTree) LookupSubTree(path ...Label) (Node, error)
  • func (t HashTree) MarshalCBOR() ([]byte, error)
  • func (t *HashTree) UnmarshalCBOR(bytes []byte) error
• type Label
  • func (l Label) String() string
• type Labeled
  • func (l Labeled) Reconstruct() [32]byte
  • func (l Labeled) String() string
• type Leaf
  • func (l Leaf) Reconstruct() [32]byte
  • func (l Leaf) String() string
• type LookupError
  • func NewLookupAbsentError(path []Label, index int) LookupError
  • func NewLookupError(path []Label, index int) LookupError
  • func NewLookupUnknownError(path []Label, index int) LookupError
  • func (l LookupError) Error() string
• type LookupResultType
• type Node
  • func Deserialize(data []byte) (Node, error)
  • func DeserializeNode(s []any) (Node, error)
• type PathValuePair
  • func AllChildren(n Node) ([]PathValuePair, error)
  • func AllPaths(n Node) ([]PathValuePair, error)
• type Pruned
  • func (p Pruned) Reconstruct() [32]byte
  • func (p Pruned) String() string

Examples

• Package (B)
• Package (C)
• Package (Root)
• Package (X)
• AllPaths
• Deserialize
• Pruned
• Serialize

Functions

func DomainSeparator

func DomainSeparator(t string) []byte

func ListPaths

func ListPaths(n Node, path []Label) [][]Label

ListPaths returns all paths from the root to a leaf node.

func Serialize

func Serialize(node Node) ([]byte, error)

Example

package main

import (
	"fmt"

	"github.com/aviate-labs/agent-go/certification/hashtree"
)

var tree = hashtree.Fork{
	LeftTree: hashtree.Fork{
		LeftTree: hashtree.Labeled{
			Label: []byte("a"),
			Tree: hashtree.Fork{
				LeftTree: hashtree.Fork{
					LeftTree: hashtree.Labeled{
						Label: []byte("x"),
						Tree:  hashtree.Leaf("hello"),
					},
					RightTree: hashtree.Empty{},
				},
				RightTree: hashtree.Labeled{
					Label: []byte("y"),
					Tree:  hashtree.Leaf("world"),
				},
			},
		},
		RightTree: hashtree.Labeled{
			Label: []byte("b"),
			Tree:  hashtree.Leaf("good"),
		},
	},
	RightTree: hashtree.Fork{
		LeftTree: hashtree.Labeled{
			Label: []byte("c"),
			Tree:  hashtree.Empty{},
		},
		RightTree: hashtree.Labeled{
			Label: []byte("d"),
			Tree:  hashtree.Leaf("morning"),
		},
	},
}

func main() {
	b, _ := hashtree.Serialize(tree)
	fmt.Printf("%x", b)
}

Output:

8301830183024161830183018302417882034568656c6c6f810083024179820345776f726c6483024162820344676f6f648301830241638100830241648203476d6f726e696e67

Types

type Empty

type Empty struct{}

func (Empty) Reconstruct

func (e Empty) Reconstruct() [32]byte

func (Empty) String

func (e Empty) String() string

type Fork

type Fork struct {
	LeftTree  Node
	RightTree Node
}

func (Fork) Reconstruct

func (f Fork) Reconstruct() [32]byte

func (Fork) String

func (f Fork) String() string

type HashTree

type HashTree struct {
	Root Node
}

HashTree is a hash tree.

func NewHashTree

func NewHashTree(root Node) HashTree

NewHashTree creates a new hash tree.

func (HashTree) Digest

func (t HashTree) Digest() [32]byte

Digest returns the digest of the hash tree.

func (HashTree) Lookup

func (t HashTree) Lookup(path ...Label) ([]byte, error)

Lookup looks up a path in the hash tree.

func (HashTree) LookupSubTree

func (t HashTree) LookupSubTree(path ...Label) (Node, error)

LookupSubTree looks up a path in the hash tree and returns the sub-tree.

func (HashTree) MarshalCBOR

func (t HashTree) MarshalCBOR() ([]byte, error)

MarshalCBOR marshals a hash tree.

func (*HashTree) UnmarshalCBOR

func (t *HashTree) UnmarshalCBOR(bytes []byte) error

UnmarshalCBOR unmarshals a hash tree.

type Label

type Label []byte

func (Label) String

func (l Label) String() string

type Labeled

type Labeled struct {
	Label Label
	Tree  Node
}

func (Labeled) Reconstruct

func (l Labeled) Reconstruct() [32]byte

func (Labeled) String

func (l Labeled) String() string

type Leaf

type Leaf []byte

func (Leaf) Reconstruct

func (l Leaf) Reconstruct() [32]byte

func (Leaf) String

func (l Leaf) String() string

type LookupError

type LookupError struct {
	// Type is the type of the lookup result.
	Type LookupResultType
	// Path is the path that was looked up.
	Path []Label
	// Index is the index in the path where the error occurred.
	Index int
}

LookupError is an error that occurs during a lookup.

func NewLookupAbsentError

func NewLookupAbsentError(path []Label, index int) LookupError

NewLookupAbsentError returns a new LookupError with type LookupResultAbsent.

func NewLookupError

func NewLookupError(path []Label, index int) LookupError

NewLookupError returns a new LookupError with type LookupResultError.

func NewLookupUnknownError

func NewLookupUnknownError(path []Label, index int) LookupError

NewLookupUnknownError returns a new LookupError with type LookupResultUnknown.

func (LookupError) Error

func (l LookupError) Error() string

type LookupResultType

type LookupResultType int

LookupResultType is the type of the lookup result. It indicates whether the result is guaranteed to be absent, unknown or is an invalid tree.

const (
	// LookupResultAbsent means that the result is guaranteed to be absent.
	LookupResultAbsent LookupResultType = iota
	// LookupResultUnknown means that the result is unknown, some leaves were pruned.
	LookupResultUnknown
	// LookupResultError means that the result is an error, the path is not valid in this context.
	LookupResultError
)

type Node

type Node interface {
	Reconstruct() [32]byte
	fmt.Stringer
}

func Deserialize

func Deserialize(data []byte) (Node, error)

Example

package main

import (
	"encoding/hex"
	"fmt"

	"github.com/aviate-labs/agent-go/certification/hashtree"
)

func main() {
	data, _ := hex.DecodeString("8301830183024161830183018302417882034568656c6c6f810083024179820345776f726c6483024162820344676f6f648301830241638100830241648203476d6f726e696e67")
	fmt.Println(hashtree.Deserialize(data))
}

Output:

{{a:{{x:hello|∅}|y:world}|b:good}|{c:∅|d:morning}} <nil>

func DeserializeNode

func DeserializeNode(s []any) (Node, error)

type PathValuePair

type PathValuePair struct {
	Path  []Label
	Value []byte
}

func AllChildren

func AllChildren(n Node) ([]PathValuePair, error)

func AllPaths

func AllPaths(n Node) ([]PathValuePair, error)

AllPaths returns all non-empty labeled paths in the hash tree, does not include pruned nodes.

Example

package main

import (
	"fmt"
	"strings"

	"github.com/aviate-labs/agent-go/certification/hashtree"
)

var tree = hashtree.Fork{
	LeftTree: hashtree.Fork{
		LeftTree: hashtree.Labeled{
			Label: []byte("a"),
			Tree: hashtree.Fork{
				LeftTree: hashtree.Fork{
					LeftTree: hashtree.Labeled{
						Label: []byte("x"),
						Tree:  hashtree.Leaf("hello"),
					},
					RightTree: hashtree.Empty{},
				},
				RightTree: hashtree.Labeled{
					Label: []byte("y"),
					Tree:  hashtree.Leaf("world"),
				},
			},
		},
		RightTree: hashtree.Labeled{
			Label: []byte("b"),
			Tree:  hashtree.Leaf("good"),
		},
	},
	RightTree: hashtree.Fork{
		LeftTree: hashtree.Labeled{
			Label: []byte("c"),
			Tree:  hashtree.Empty{},
		},
		RightTree: hashtree.Labeled{
			Label: []byte("d"),
			Tree:  hashtree.Leaf("morning"),
		},
	},
}

func main() {
	paths, _ := hashtree.AllPaths(tree)
	for _, path := range paths {
		var p []string
		for _, l := range path.Path {
			p = append(p, string(l))
		}
		fmt.Printf(
			"%s: %s\n",
			strings.Join(p, "/"),
			string(path.Value),
		)
	}
}

Output:

a/x: hello
a/y: world
b: good
d: morning

type Pruned

type Pruned [32]byte

Example

package main

import (
	"encoding/hex"
	"fmt"

	"github.com/aviate-labs/agent-go/certification/hashtree"
)

var pruned = hashtree.Fork{
	LeftTree: hashtree.Fork{
		LeftTree: hashtree.Labeled{
			Label: []byte("a"),
			Tree: hashtree.Fork{
				LeftTree: hashtree.Pruned(h2b("1b4feff9bef8131788b0c9dc6dbad6e81e524249c879e9f10f71ce3749f5a638")),
				RightTree: hashtree.Labeled{
					Label: []byte("y"),
					Tree:  hashtree.Leaf("world"),
				},
			},
		},
		RightTree: hashtree.Labeled{
			Label: []byte("b"),
			Tree:  hashtree.Pruned(h2b("7b32ac0c6ba8ce35ac82c255fc7906f7fc130dab2a090f80fe12f9c2cae83ba6")),
		},
	},
	RightTree: hashtree.Fork{
		LeftTree: hashtree.Pruned(h2b("ec8324b8a1f1ac16bd2e806edba78006479c9877fed4eb464a25485465af601d")),
		RightTree: hashtree.Labeled{
			Label: []byte("d"),
			Tree:  hashtree.Leaf("morning"),
		},
	},
}

func main() {
	fmt.Printf("%x", pruned.Reconstruct())
}

func h2b(s string) [32]byte {
	var bs [32]byte
	b, _ := hex.DecodeString(s)
	copy(bs[:], b)
	return bs
}

Output:

eb5c5b2195e62d996b84c9bcc8259d19a83786a2f59e0878cec84c811f669aa0

func (Pruned) Reconstruct

func (p Pruned) Reconstruct() [32]byte

func (Pruned) String

func (p Pruned) String() string