hashtree

package
v0.8.2 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: May 20, 2026 License: Apache-2.0 Imports: 6 Imported by: 1

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

Examples

Constants

This section is empty.

Variables

This section is empty.

Functions

func DomainSeparator 

func DomainSeparator(t string) []byte

func ListPaths added in v0.4.4 

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

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

func Lookup added in v0.5.0 

func Lookup(n Node, path ...Label) ([]byte, error)

Lookup looks up a path in the 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)

func LookupSubTree added in v0.5.0 

func LookupSubTree(n Node, path ...Label) (Node, error)

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

type PathValuePair added in v0.4.5 

type PathValuePair[V any] struct {
	Path  []Label
	Value V
}

func AllChildren added in v0.4.5 

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

func AllPaths added in v0.4.5 

func AllPaths(n Node) ([]PathValuePair[[]byte], 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

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.