pmt

package
v1.2.10-rc.2 Latest Latest
Warning

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

 Go to latest Published: Dec 4, 2023 License: MIT Imports: 12 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	TNil       = iota + 1 // When persisting, this is the type for nils
	TNode                 // Type for Nodes
	TValue                // Type for values
	TNotLoaded            // When transitioning into a new Byte Block, the NotLoaded indicates a need to load from disk
)

Variables

View Source 
var FirstPossibleBptKey = [32]byte{
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
	255, 255, 255, 255, 255, 255, 255, 255,
}

FirstPossibleBptKey is the first possible BPT key.

Functions

func GetChildrenNodeKeys 

func GetChildrenNodeKeys(nodeKey [32]byte) (left, right [32]byte, ok bool)

GetLeftNodeKey Computes the nodeKey that a left branch from a BptNode must have

func GetHash 

func GetHash(e Entry) []byte

GetHash Makes the code just a bit more simple. Checks for nils

func GetHtKey 

func GetHtKey(nodeKey [32]byte) (height int, key [32]byte, ok bool)

GetHtKey Extract the height and Key fragment from a nodeKey. The reverse operation of GetNodeKey Mostly useful for debugging and testing

func GetNodeHash 

func GetNodeHash(n *BptNode)

GetNodeHash Compute the hash of a node from its children

func GetNodeKey 

func GetNodeKey(height int, key [32]byte) (nodeKey [32]byte, ok bool)

GetNodeKey We need a key to address nodes in the protocol. These nodes need a unique key for debugging purposes. We return the key with height number of bits followed by a one end bit followed by all bits clear Heights greater than 255 (0-254) bits are not supported.

func ReadSnapshot 

func ReadSnapshot(file ioutil2.SectionReader, storeState func(key storage.Key, hash [32]byte, reader ioutil2.SectionReader) error) error

ReadSnapshot reads a snapshot

Types

type BPT 

type BPT struct {
	RootHash  [32]byte              // Root hash of the BPT
	Root      *BptNode              // The root of the Patricia Tree, holding the summary hash for the Patricia Tree
	DirtyMap  map[[32]byte]*BptNode // Map of dirty nodes.
	MaxHeight int                   // Highest height of any node in the BPT
	Power     int                   // Power
	Mask      int                   // Mask used to detect Byte Block boundaries
	Manager   *Manager              // Pointer to the manager for access to the database
}

BPT Binary Patricia Tree. Two types of Entry in the Tree: 

Node - a node in a binary tree that ends in Values (Left and Right)
Value - a key / value pair where the key is a ChainID and the value
        is the hash of the state of the chain

The BPT can be updated many times, then updated in batch (which reduces the hashes that have to be performed to update the summary hash)

func NewBPT 

func NewBPT(manager *Manager) *BPT

New BPT Allocate a new BPT and set up the structures required to get to work with Binary Patricia Trees.

func (*BPT) Clean 

func (b *BPT) Clean(node *BptNode)

Clean Take a node out of the dirty tracking. Don't care if it is or isn't dirty

func (*BPT) CollectReceipt 

func (b *BPT) CollectReceipt(BIdx, bit byte, node *BptNode, key [32]byte, r *merkle.Receipt) (hash []byte)

CollectReceipt A recursive routine that searches the BPT for the given chainID. Once it is found, the search unwinds and builds the receipt.

Inputs: BIdx -- byte index into the key bit -- index to the bit node -- the node in the BPT where we have reached in our search so far key -- The key in the BPT we are looking for

func (*BPT) Dirty 

func (b *BPT) Dirty(node *BptNode)

Dirty Add a node to the dirty tracking

func (*BPT) EnsureRootHash 

func (b *BPT) EnsureRootHash()

func (*BPT) Equal 

func (b *BPT) Equal(b2 *BPT) (equal bool)

Equal Used to do some testing

func (*BPT) ForEach 

func (b *BPT) ForEach(fn func(key storage.Key, hash [32]byte) error) error

func (*BPT) Get 

func (b *BPT) Get(node *BptNode, key [32]byte) (highest *BptNode, entry *Entry, found bool)

Get Return the highest node that exists on the path to a particular node, and the entry along the path

func (*BPT) GetDirtyList 

func (b *BPT) GetDirtyList() (list []*BptNode)

GetDirtyList Convert the map to a list (must work down from the highest heights to the root (to keep from stomping on hashing orders; all hashes at the same height are independent of each other, but must be computed before we handle the next lowest height, and so forth.

func (*BPT) GetRange 

func (b *BPT) GetRange(startKey [32]byte, count int) (values []*Value, lastKey [32]byte)

Insert Starts the search of the BPT for the location of the key in the BPT

func (*BPT) GetReceipt 

func (b *BPT) GetReceipt(chainID [32]byte) *merkle.Receipt

GetReceipt Returns the receipt for the current state for the given chainID

func (*BPT) GetRoot 

func (b *BPT) GetRoot() (root *BptNode)

GetRoot Get the Root node for the BPT. This may load the BPT Root node from disk if not loaded yet.

func (*BPT) Insert 

func (b *BPT) Insert(key, hash [32]byte)

Insert Starts the search of the BPT for the location of the key in the BPT

func (*BPT) IsDirty 

func (b *BPT) IsDirty(node *BptNode) bool

IsDirty Sort if a node is in the dirty tracking. Allows batching updates for greater efficiency.

func (*BPT) LoadNext 

func (b *BPT) LoadNext(BIdx, bit byte, node *BptNode, key [32]byte)

LoadNext Load the next level of nodes if it is necessary. We build Byte Blocks of nodes which store all the nodes and values within 8 bits of a key. If the key is longer, certainly there will be more Byte Blocks 8 bits later.

Note if a Byte Block is loaded, then the node passed in is replaced by the node loaded.

func (*BPT) LoadSnapshot 

func (b *BPT) LoadSnapshot(file ioutil2.SectionReader, storeState func(key storage.Key, hash [32]byte, reader ioutil2.SectionReader) error) error

LoadSnapshot restores a snapshot to the BPT

func (*BPT) Marshal 

func (b *BPT) Marshal() (data []byte)

Marshal Must have the MaxNodeID at the very least to be able to add nodes to the BPT

func (*BPT) MarshalByteBlock 

func (b *BPT) MarshalByteBlock(borderNode *BptNode) (data []byte)

MarshalByteBlock Given the node leading into a byte block, marshal all the nodes within the block. A borderNode is a node that completes a byte boundary. So consider a theoretical key 03e706b93d2e515c6eff056ee481eb92f9e790277db91eb748b3cc5b46dfe8ca The first byte is 03, second is a7, third is 06 etc.

The node in block 03 that completes e7 is the board node. The Left path would begin the path to the theoretical key (a bit zero).

func (*BPT) MarshalEntry 

func (b *BPT) MarshalEntry(entry Entry, data []byte) []byte

MarshalEntry Recursive routine that marshals a byte block starting from an entry on the Left or on the Right. Calling MarshalEntry from the Left only marshals half the node space of a byte block. Have to call MarshalEntry from the Right to complete coverage.

func (*BPT) NewNode 

func (b *BPT) NewNode(key [32]byte, parent *BptNode) (node *BptNode)

NewNode Allocate a new Node for use with this BPT. Note that various bookkeeping tasks are performed for the caller.

func (*BPT) NewValue 

func (b *BPT) NewValue(parent *BptNode, key, hash [32]byte) (value *Value)

NewValue Allocate a new Value struct and do some bookkeeping for the user

func (*BPT) Print 

func (b *BPT) Print(entry Entry)

Print Print the BPT. Only works if the whole BPT is in memory.

func (*BPT) SaveSnapshot 

func (b *BPT) SaveSnapshot(file io.WriteSeeker, loadState func(key storage.Key, hash [32]byte) ([]byte, error)) error

SaveSnapshot Saves a snapshot of the state of the BVN/DVN. 1) The first thing done is copy the entire BVN and persist it to disk 2) Then all the states are pulled from the database and persisted. As long as the BVN is captured in its entirety within a block, the states can be persisted over other blocks (as long as we don't delete any of those states

Snapshot Format: 

8 byte count of nodes (NumNodes)
[count of nodes]node   -- each node is a Fixed length
[count of nodes]value  -- each value is variable length

node: 

32 byte Key    -- 8 byte offset from end of nodes to value
32 byte Hash   -- Hash of the value of the BPT entry
8  byte offset -- from end of list of nodes to start of the value

value: 

8  byte                  -- length of value
n  [length of value]byte -- the bytes of the value

func (*BPT) UnMarshal 

func (b *BPT) UnMarshal(data []byte) (newData []byte)

UnMarshal Load the BPT in support of initialization from disk. Note that an existing BPT will be over written completely.

func (*BPT) UnMarshalByteBlock 

func (b *BPT) UnMarshalByteBlock(borderNode *BptNode, data []byte) []byte

UnMarshalByteBlock

func (*BPT) UnMarshalEntry 

func (b *BPT) UnMarshalEntry(parent *BptNode, data []byte) (Entry, []byte)

func (*BPT) Update 

func (b *BPT) Update() error

Update the Patricia Tree hashes with the values from the updates since the last update

func (*BPT) WalkRange 

func (b *BPT) WalkRange(found *bool, node *BptNode, count int, key [32]byte, values []*Value) []*Value

WalkRange A recursive routine that pushes collisions towards the leaves of the binary patricia tree until the keys don't match any more. Note that this tree cannot handle duplicate keys, but that is an assumption of patricia trees anyway

Inputs: node -- the node in the BPT where the value (key, hash) is being inserted count -- the number of hashes to collect key -- The key in the BPT which determines were in the BPT the hash goes hash -- The current value of the key, as tracked by the BPT

type BptNode 

type BptNode struct {
	Height  int      // Root is 0. above root is 1. Above above root is 2, etc.
	NodeKey [32]byte // Byte Block Key.
	Hash    [32]byte // This is the summary hash for the tree
	Left    Entry    // The hash of the child Left and up the tree, bit is zero
	Right   Entry    // the hash to the child Right and up the tree, bit is one
	Parent  *BptNode // the Parent node "below" this node
}

func (*BptNode) Equal 

func (n *BptNode) Equal(entry Entry) (equal bool)

func (*BptNode) GetHash 

func (n *BptNode) GetHash() []byte

GetHash Returns the Hash value for computing the summary hash of the BPT. By being in the interface, it does eliminate some book keeping where a node easily has L and R nodes, but doesn't know if those are Node or Value instances.

func (*BptNode) Marshal 

func (n *BptNode) Marshal() (data []byte)

Marshal Serialize the fields of the Node. Note this doesn't do too much towards fitting the node into the actual BPT, but it helps a bit.

See (p *BPT)MarshalByteBlock

func (*BptNode) T 

func (n *BptNode) T() int

T Returns true if this node is really a Node, and false if the node is really a Value. We possibly want a way for Node to compress the distance to child nodes that have a long single path to leaves just because a key matches a number of bits before differentiating.

func (*BptNode) UnMarshal 

func (n *BptNode) UnMarshal(data []byte) []byte

UnMarshal Deserialize the fields of the Node. See (p *BPT)UnMarshalByteBlock

type Entry 

type Entry interface {
	T() int                       // Returns the type of entry
	GetHash() []byte              // Returns the Hash for the entry
	Marshal() []byte              // Serialize the state of the Node or Value
	UnMarshal(data []byte) []byte // Unmarshal the state into the Node or Value
	Equal(entry Entry) bool       // Return Entry == entry
}

Entry We only have two node types, a Node that builds the Patricia Tree, and a Value that holds the values at the leaves.

type Manager 

type Manager struct {
	DBManager storage.KeyValueTxn
	Dirty     []*BptNode
	Bpt       *BPT
}

func NewBPTManager 

func NewBPTManager(dbManager storage.KeyValueTxn) *Manager

NewBPTManager Get a new BPTManager which keeps the BPT on disk. If the BPT is on disk, then it can be reloaded as needed.

func (*Manager) FlushNode 

func (m *Manager) FlushNode(node *BptNode) error

FlushNode Flushes the Byte Block to disk

func (*Manager) GetRootHash 

func (m *Manager) GetRootHash() [32]byte

GetRootHash Note this provides the root hash (generally) of the previous hash of the entire BPT. If called JUST after a call to Update() then it returns the current root hash, which would be true up to the point that any node in the BPT is updated.

func (*Manager) InsertKV 

func (m *Manager) InsertKV(key, value [32]byte)

InsertKV Insert Key Value into Bpt

func (*Manager) LoadNode 

func (m *Manager) LoadNode(node *BptNode)

LoadNode Loads the nodes under the given node into the BPT

type NotLoaded 

type NotLoaded struct {
}

Node A node in our binary patricia/merkle tree

func (*NotLoaded) Equal 

func (n *NotLoaded) Equal(entry Entry) bool

func (*NotLoaded) GetHash 

func (n *NotLoaded) GetHash() []byte

func (*NotLoaded) Marshal 

func (n *NotLoaded) Marshal() []byte

func (*NotLoaded) T 

func (n *NotLoaded) T() int

func (*NotLoaded) UnMarshal 

func (n *NotLoaded) UnMarshal(data []byte) []byte

type Value 

type Value struct {
	Key  [32]byte // The key for the Patricia Tree value
	Hash [32]byte // The current value for the key
}

Value holds the key / hash mapping for the BPT. With Accumulate, the key represents a ChainID and a state Hash for a chain in the protocol

func (*Value) Equal 

func (v *Value) Equal(entry Entry) (equal bool)

Equal Return true if a given Entry is a Value instance, and has the same Key and Hash as this Value

func (*Value) GetHash 

func (v *Value) GetHash() []byte

GetHash Returns the hash as a slice

func (*Value) Marshal 

func (v *Value) Marshal() []byte

Marshal Return the concatenation of the Key and Hash of the value

func (*Value) T 

func (v *Value) T() int

Node Returns true if this is a Node, otherwise it is a value

func (*Value) UnMarshal 

func (v *Value) UnMarshal(data []byte) []byte

UnMarshal Load the Value with the state marshalled to the given data slice

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.