node

package
v0.9.0 Latest Latest
Warning

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

 Go to latest Published: Mar 1, 2024 License: LGPL-3.0 Imports: 12 Imported by: 0

README

Trie node

Package node defines the Node structure with methods to be used in the modified Merkle-Patricia Radix-16 trie.

Codec

The following sub-sections precise the encoding of a node. This encoding is formally described in the Polkadot specification.

Header

Each node encoding has a header of one or more bytes. The first byte contains the node variant and some or all of the partial key length of the node. If the partial key length cannot fit in the first byte, additional bytes are added to the header to represent the total partial key length.

Partial key

The header is then concatenated with the partial key of the node, encoded as Little Endian bytes.

Remaining bytes

The remaining bytes appended depend on the node variant.

  • For leaves, the SCALE-encoded leaf storage value is appended.
  • For branches, the following elements are concatenated in this order and appended to the previous header+partial key:
    • Children bitmap (2 bytes)
    • SCALE-encoded node storage value
    • Hash(Encoding(Child[0]))
    • Hash(Encoding(Child[1]))
    • ...
    • Hash(Encoding(Child[15]))

Documentation

Overview

Package node defines the `Node` structure with methods to be used in the modified Merkle-Patricia Radix-16 trie.

Index

Constants

View Source 
const (
	// ChildrenCapacity is the maximum number of children in a branch node.
	ChildrenCapacity = 16
)

Variables

View Source 
var (
	// DefaultCopySettings contains the following copy settings:
	// - children are NOT deep copied recursively
	// - the Merkle value field is left empty on the copy
	// - the partial key field is deep copied
	// - the storage value field is deep copied
	DefaultCopySettings = CopySettings{
		CopyPartialKey:   true,
		CopyStorageValue: true,
	}

	// DeepCopySettings returns the following copy settings:
	// - children are deep copied recursively
	// - the Merkle value field is deep copied
	// - the partial key field is deep copied
	// - the storage value field is deep copied
	DeepCopySettings = CopySettings{
		CopyChildren:     true,
		CopyMerkleValue:  true,
		CopyPartialKey:   true,
		CopyStorageValue: true,
	}
)
View Source 
var (
	// ErrDecodeStorageValue is defined since no sentinel error is defined
	// in the scale package.
	ErrDecodeStorageValue        = errors.New("cannot decode storage value")
	ErrDecodeHashedStorageValue  = errors.New("cannot decode hashed storage value")
	ErrDecodeHashedValueTooShort = errors.New("hashed storage value too short")
	ErrReadChildrenBitmap        = errors.New("cannot read children bitmap")
	// ErrDecodeChildHash is defined since no sentinel error is defined
	// in the scale package.
	ErrDecodeChildHash = errors.New("cannot decode child hash")
)
View Source 
var (
	ErrPartialKeyTooBig = errors.New("partial key length cannot be larger than 2^16")
)
View Source 
var ErrReaderMismatchCount = errors.New("read unexpected number of bytes from reader")
View Source 
var ErrVariantUnknown = errors.New("node variant is unknown")

Functions

func MerkleValue 

func MerkleValue(encoding []byte, writer io.Writer) (err error)

MerkleValue writes the Merkle value from the encoding of a non-root node to the writer given. If the encoding is less or equal to 32 bytes, the Merkle value is the encoding. Otherwise, the Merkle value is the Blake2b hash digest of the encoding.

func MerkleValueRoot 

func MerkleValueRoot(rootEncoding []byte, writer io.Writer) (err error)

MerkleValueRoot writes the Merkle value for the root of the trie to the writer given as argument. The Merkle value is the Blake2b hash of the encoding of the root node.

Types

type Buffer 

type Buffer interface {
	io.Writer
	Len() int
	Bytes() []byte
}

Buffer is an interface with some methods of *bytes.Buffer.

type CopySettings 

type CopySettings struct {
	// CopyChildren can be set to true to recursively deep copy the eventual
	// children of the node. This is false by default and should only be used
	// in tests since it is quite inefficient.
	CopyChildren bool
	// CopyMerkleValue can be set to true to deep copy the Merkle value
	// field on the current node copied.
	// This is false by default because in production, a node is copied
	// when it is about to be mutated, hence making its cached Merkle value
	// field no longer valid.
	CopyMerkleValue bool
	// CopyPartialKey can be set to true to deep copy the partial key field of
	// the node. This is useful when false if the partial key is about to
	// be assigned after the Copy operation, to save a memory operation.
	CopyPartialKey bool
	// CopyStorageValue can be set to true to deep copy the storage value field of
	// the node. This is useful when false if the storage value is about to
	// be assigned after the Copy operation, to save a memory operation.
	CopyStorageValue bool
}

CopySettings contains settings to configure the deep copy of a node.

type Kind 

type Kind byte

Kind is the type of the node. 

const (
	// Leaf kind for leaf nodes.
	Leaf Kind = iota
	// Branch kind for branches (with or without value).
	Branch
)

func (Kind) String 

func (k Kind) String() string

type Node 

type Node struct {
	// PartialKey is the partial key bytes in nibbles (0 to f in hexadecimal)
	PartialKey   []byte
	StorageValue []byte
	MustBeHashed bool
	// IsHashedValue is true when the StorageValue is a blake2b hash
	IsHashedValue bool
	// Generation is incremented on every trie Snapshot() call.
	// Each node also contain a certain Generation number,
	// which is updated to match the trie Generation once they are
	// inserted, moved or iterated over.
	Generation uint64
	// Children is a slice of length 16 for branches.
	// It is left to nil for leaves to reduce memory usage.
	Children []*Node
	// Dirty is true when the branch differs
	// from the node stored in the database.
	Dirty bool
	// MerkleValue is the cached Merkle value of the node.
	MerkleValue []byte

	// Descendants is the number of descendant nodes for
	// this particular node.
	Descendants uint32
}

Node is a node in the trie and can be a leaf or a branch.

func Decode 

func Decode(reader io.Reader) (n *Node, err error)

Decode decodes a node from a reader. The encoding format is documented in the README.md of this package, and specified in the Polkadot spec at https://spec.polkadot.network/#sect-state-storage For branch decoding, see the comments on decodeBranch. For leaf decoding, see the comments on decodeLeaf.

func (*Node) CalculateMerkleValue 

func (n *Node) CalculateMerkleValue() (merkleValue []byte, err error)

CalculateMerkleValue returns the Merkle value of the non-root node.

func (*Node) CalculateRootMerkleValue 

func (n *Node) CalculateRootMerkleValue() (merkleValue []byte, err error)

CalculateRootMerkleValue returns the Merkle value of the root node.

func (*Node) ChildrenBitmap 

func (n *Node) ChildrenBitmap() (bitmap uint16)

ChildrenBitmap returns the 16 bit bitmap of the children in the branch node.

func (*Node) Copy 

func (n *Node) Copy(settings CopySettings) *Node

Copy deep copies the node. Setting copyChildren to true will deep copy children as well.

func (*Node) Encode 

func (n *Node) Encode(buffer Buffer) (err error)

Encode encodes the node to the buffer given. The encoding format is documented in the README.md of this package, and specified in the Polkadot spec at https://spec.polkadot.network/#sect-state-storage

func (*Node) EncodeAndHash 

func (n *Node) EncodeAndHash() (encoding, merkleValue []byte, err error)

EncodeAndHash returns the encoding of the node and the Merkle value of the node. See the `MerkleValue` method for more details on the value of the Merkle value. TODO change this function to write to an encoding writer and a merkle value writer, such that buffer sync pools can be used by the caller.

func (*Node) EncodeAndHashRoot 

func (n *Node) EncodeAndHashRoot() (encoding, merkleValue []byte, err error)

EncodeAndHashRoot returns the encoding of the node and the Merkle value of the node. See the `MerkleValueRoot` method for more details on the value of the Merkle value. TODO change this function to write to an encoding writer and a merkle value writer, such that buffer sync pools can be used by the caller.

func (*Node) HasChild 

func (n *Node) HasChild() (has bool)

HasChild returns true if the node has at least one child.

func (*Node) Kind 

func (n *Node) Kind() Kind

Kind returns Leaf or Branch depending on what kind the node is.

func (*Node) NumChildren 

func (n *Node) NumChildren() (count int)

NumChildren returns the total number of children in the branch node.

func (*Node) SetClean 

func (n *Node) SetClean()

SetClean sets the dirty status to false for the node.

func (*Node) SetDirty 

func (n *Node) SetDirty()

SetDirty sets the dirty status to true for the node.

func (*Node) StorageValueEqual 

func (n *Node) StorageValueEqual(stoageValue []byte) (equal bool)

StorageValueEqual returns true if the node storage value is equal to the storage value given as argument. In particular, it returns false if one storage value is nil and the other storage value is the empty slice.

func (*Node) String 

func (n *Node) String() string

func (*Node) StringNode 

func (n *Node) StringNode() (stringNode *gotree.Node)

StringNode returns a gotree compatible node for String methods.

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.