jmt

package
v0.0.0-...-5510b13 Latest Latest
Warning

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

 Go to latest Published: Oct 16, 2025 License: MIT Imports: 8 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	MaxBinaryTreeDepth = MaxHexTreeDepth * 4
	MaxProofLength     = MaxBinaryTreeDepth
)
View Source 
const MaxBoundingLeaves = 2
View Source 
const MaxHexTreeDepth = len(Digest{}) * 2

Variables

View Source 
var (
	MinDigest = Digest{}
	MaxDigest = Digest(bytes.Repeat([]byte{0xff}, len(Digest{})))
)
View Source 
var InternalDomainSeparator = []byte("JMT::IntrnalNode") // sic
View Source 
var LeafDomainSeparator = []byte("JMT::LeafNode")
View Source 
var SparseMerklePlaceholderDigest = Digest([]byte("SPARSE_MERKLE_PLACEHOLDER_HASH__"))

Functions

func Read 

func Read(
	rootReader RootReader,
	nodeReader NodeReader,
	version Version,
	key []byte,
) ([]byte, error)

Read returns the undigested value for the undigested key in the tree at version. If the key does not exist, nil is returned, and no error.

func VerifySubrange 

func VerifySubrange(
	expectedRootDigest Digest,
	startIndex Digest,
	endInclIndex Digest,
	keyValues []KeyValue,
	boundingLeaves []BoundingLeaf,
) error

VerifySubrange verifies that the key-value pairs in keyValues are the only ones included in the key digest subrange [startIndex, endInclIndex], in the tree rooted at expectedRootDigest.

Types

type BoundingLeaf 

type BoundingLeaf struct {
	Leaf     LeafKeyAndValueDigests
	Siblings []Digest
}

func ProveSubrange 

func ProveSubrange(
	rootReader RootReader,
	nodeReader NodeReader,
	version Version,
	startIndex Digest,
	endInclIndex Digest,
) ([]BoundingLeaf, error)

ProveSubrange returns the bounding leafs required to verify inclusion of the vector of all the key-values of which the digests fall in the subrange [startIndex, endInclIndex], using VerifySubrange.

type Child 

type Child struct {
	Version Version
	Digest  Digest
	IsLeaf  bool
}

func (*Child) String 

func (c *Child) String() string

type Digest 

type Digest = [sha256.Size]byte

func DecrementDigest 

func DecrementDigest(digest Digest) (Digest, bool)

func DigestKey 

func DigestKey(key []byte) Digest

func DigestValue 

func DigestValue(value []byte) Digest

func IncrementDigest 

func IncrementDigest(digest Digest) (Digest, bool)

func ProveInclusion 

func ProveInclusion(
	rootReader RootReader,
	nodeReader NodeReader,
	version Version,
	key []byte,
) ([]Digest, error)

ProveInclusion returns the proof siblings for the inclusion proof of the undigested key in the tree at version.

func ReadRootDigest 

func ReadRootDigest(
	rootReader RootReader,
	nodeReader NodeReader,
	version Version,
) (Digest, error)

ReadRootDigest returns the digest of the root node of the tree at version. If digest is SparseMerklePlaceholderDigest, the tree is empty. The caller must be careful to only call this method for versions that exist and roots have indeed been written. Versions that are not written are implied to represent an empty tree.

type InternalNode 

type InternalNode struct {
	Children [16]*Child
}

func (*InternalNode) String 

func (n *InternalNode) String() string

type KeyValue 

type KeyValue struct {
	// Key length must be greater than 0.
	Key []byte
	// Value of nil is permitted and indicates a desire to delete Key.
	Value []byte
}

func ReadRange 

func ReadRange(
	rootReader RootReader,
	nodeReader NodeReader,
	version Version,
	minKeyDigest Digest,
	maxKeyDigest Digest,
	keysPlusValuesBytesLimit int,
	lenLimit int,
) (keyValues []KeyValue, truncated bool, err error)

ReadRange returns all key-value pairs in the range [minKeyDigest, maxKeyDigest] in the tree at version. This is useful for state synchronization where a verifier expects to build the tree from scratch in order from the leftmost to the rightmost leaf. We return the key-value pairs instead of the digests to give the verifier the most flexibility. If there were more key-value pairs in the range that we could not fit in the limits, we return truncated=true.

func ReadRangeAscOrDesc 

func ReadRangeAscOrDesc(
	rootReader RootReader,
	nodeReader NodeReader,
	version Version,
	minKeyDigest Digest,
	maxKeyDigest Digest,
	keysPlusValuesBytesLimit int,
	lenLimit int,
	order ReadRangeOrder,
) (keyValues []KeyValue, truncated bool, err error)

ReadRangeAscOrDesc is a variant of ReadRange that allows the caller to specify the order in which to read the key-value pairs.

type LeafKeyAndValueDigests 

type LeafKeyAndValueDigests struct {
	KeyDigest   Digest
	ValueDigest Digest
}

type LeafNode 

type LeafNode struct {
	KeyDigest   Digest
	Key         []byte
	ValueDigest Digest
	Value       []byte
}

func (*LeafNode) String 

func (n *LeafNode) String() string

type NibblePath 

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

func NewNibblePath 

func NewNibblePath(numNibbles int, bytes []byte) (NibblePath, bool)

func NibblePathFromDigest 

func NibblePathFromDigest(digest Digest) NibblePath

func (NibblePath) Append 

func (np NibblePath) Append(nibble byte) NibblePath

func (NibblePath) Bytes 

func (np NibblePath) Bytes() []byte

func (NibblePath) Compare 

func (np NibblePath) Compare(np2 NibblePath) int

func (NibblePath) Equal 

func (np NibblePath) Equal(np2 NibblePath) bool

func (NibblePath) Get 

func (np NibblePath) Get(index int) byte

func (NibblePath) NumNibbles 

func (np NibblePath) NumNibbles() int

func (NibblePath) Prefix 

func (np NibblePath) Prefix(count int) NibblePath

func (NibblePath) String 

func (np NibblePath) String() string

type Node 

type Node interface {
	// contains filtered or unexported methods
}

type NodeKey 

type NodeKey struct {
	Version    Version
	NibblePath NibblePath
}

func BatchUpdate 

func BatchUpdate(
	rootReadWriter RootReadWriter,
	nodeReadWriter NodeReadWriter,
	staleNodeWriter StaleNodeWriter,
	oldVersion Version,
	newVersion Version,
	keyValueUpdates []KeyValue,
) (NodeKey, error)

BatchUpdate performs the updates indicated by keyValueUpdates on top of the tree at oldVersion. If oldVersion coincides with newVersion, the updates are performed in place and no stale nodes are written. If oldVersion is less than newVersion, we perform copy-on-write, and stale nodes might be written that might need to be reaped in the future using ReapStaleNodes. Using an oldVersion that is greater than newVersion is an error.

keyValueUpdates must be unique in Key.

BatchUpdate returns the NodeKey of the new root node at newVersion.

func (NodeKey) Equal 

func (nk NodeKey) Equal(nk2 NodeKey) bool

type NodeReadWriter 

type NodeReadWriter interface {
	NodeReader
	NodeWriter
}

type NodeReader 

type NodeReader interface {
	ReadNode(nodeKey NodeKey) (nodeOrNil Node, err error)
}

type NodeWriter 

type NodeWriter interface {
	// Implementers should check whether node is nil first. nil indicates an
	// empty tree, and should effectively cause a deletion of the node key.
	// Implementers should make sure to not be affected by later mutations to
	// Node.
	WriteNode(nodeKey NodeKey, nodeOrNil Node) error
}

type ReadRangeOrder 

type ReadRangeOrder int
const (
	ReadRangeOrderAsc ReadRangeOrder
	ReadRangeOrderDesc
)

type RootReadWriter 

type RootReadWriter interface {
	RootReader
	RootWriter
}

type RootReader 

type RootReader interface {
	ReadRoot(version Version) (nodeKey NodeKey, err error)
}

type RootWriter 

type RootWriter interface {
	WriteRoot(version Version, nodeKey NodeKey) error
}

type StaleNode 

type StaleNode struct {
	StaleSinceVersion Version
	NodeKey           NodeKey
}

type StaleNodeWriter 

type StaleNodeWriter interface {
	WriteStaleNode(staleNode StaleNode) error
}

type Version 

type Version = uint64

When starting from scratch, you can safely use version 0 as the "old version" contains an empty tree.

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.