managed

package
v0.8.2-beta Latest Latest
Warning

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

 Go to latest Published: Jun 13, 2022 License: MIT Imports: 9 Imported by: 0

Documentation

Overview

For key value stores where buckets are not supported, we add a byte to the key to represent a bucket. For now, all buckets are hard coded, but we could change that in the future.

Buckets are not really enough to index everything we wish to index. So we have labels as well. Labels are shifted 8 bits left, so they can be combined with the buckets to create a unique key.

This allows us to put the raw directory block at DBlockBucket+L_raw, and meta data about the directory block at DBlockBucket+MetaLabel

Index

Constants

This section is empty.

Variables

This section is empty.

Functions

func GetSha256 

func GetSha256() func(data []byte) Hash

GetSha256 Get the a Sha256 function that can be used to create hashes compatible with a Stateful Merkle tree using sha256

Types

type AllowedMap 

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

func (*AllowedMap) Adh 

func (a *AllowedMap) Adh(hash []byte) []byte

Adh Add a hash to AllowedMap so we can check against it latter. Add a hash to a map so it can be allowed to be used latter. Passes back the same hash so it can be used inline.

func (AllowedMap) Chk 

func (a AllowedMap) Chk(hash []byte) []byte

Chk Return the same hash passed to Check so Check can be called inline anywhere a Hash is used. We hash our input so anything can be put in the map, not just hashes.

func (*AllowedMap) SetLock 

func (a *AllowedMap) SetLock(bool)

SetLock Lock the AllowedMap to ignore more additions to the set

type GetIntermediateFunc added in v0.5.1 

type GetIntermediateFunc func(element, height int64) (l, r Hash, err error)

type Hash 

type Hash []byte

This Stateful Merkle Tree implementation handles 256 bit hashes

func Sha256 

func Sha256(b []byte) Hash

func (Hash) BinarySize 

func (h Hash) BinarySize() int

func (Hash) Bytes 

func (h Hash) Bytes() []byte

func (Hash) Bytes32 

func (h Hash) Bytes32() [32]byte

func (Hash) Combine 

func (h Hash) Combine(hf HashFunc, right Hash) Hash

Combine Hash this hash (the left hash) with the given right hash to produce a new hash

func (Hash) Copy 

func (h Hash) Copy() Hash

Copy Make a copy of a Hash (so the caller cannot modify the original version)

func (Hash) Equal 

func (h Hash) Equal(g Hash) bool

func (Hash) MarshalBinary 

func (h Hash) MarshalBinary() ([]byte, error)

func (*Hash) UnmarhsalBinary 

func (h *Hash) UnmarhsalBinary(b []byte) error

type HashFunc added in v0.5.1 

type HashFunc func([]byte) Hash

type HashList 

type HashList []Hash

func (HashList) BinarySize 

func (l HashList) BinarySize() int

func (HashList) MarshalBinary 

func (l HashList) MarshalBinary() ([]byte, error)

func (*HashList) UnmarhsalBinary 

func (l *HashList) UnmarhsalBinary(b []byte) error

type MerkleManager 

type MerkleManager struct {
	Key       storage.Key         // ChainID (some operations require this)
	Manager   storage.KeyValueTxn // AppID based Manager
	MS        *MerkleState        // MerkleState managed by MerkleManager
	MarkPower int64               // log2 of the MarkFreq
	MarkFreq  int64               // The count between Marks
	MarkMask  int64               // The binary mask to detect Mark boundaries
}

func NewMerkleManager 

func NewMerkleManager(
	DBManager storage.KeyValueTxn,
	markPower int64) (*MerkleManager, error)

NewMerkleManager Create a new MerkleManager given a MainChain.Manager and markPower. The MainChain.Manager handles the persistence for the Merkle Tree under management The markPower is the log 2 frequency used to collect states in the Merkle Tree

func (*MerkleManager) AddHash 

func (m *MerkleManager) AddHash(hash Hash, unique bool) error

AddHash adds a Hash to the Chain controlled by the ChainManager. If unique is true, the hash will not be added if it is already in the chain.

func (*MerkleManager) Equal 

func (m *MerkleManager) Equal(m2 *MerkleManager) bool

Equal Compares the MerkleManager to the given MerkleManager and returns false if the fields in the MerkleManager are different from m2

func (*MerkleManager) Get 

func (m *MerkleManager) Get(element int64) (Hash, error)

Get the nth leaf node

func (*MerkleManager) GetAnyState 

func (m *MerkleManager) GetAnyState(element int64) (ms *MerkleState, err error)

GetAnyState We only store the state at MarkPoints. This function computes a missing state even if one isn't stored for a particular element.

func (*MerkleManager) GetChainState 

func (m *MerkleManager) GetChainState(key storage.Key) (merkleState *MerkleState, err error)

GetChainState Reads the highest state of the chain stored to the database. Returns nilTestCli if no state has been recorded for a chain

func (*MerkleManager) GetElementCount 

func (m *MerkleManager) GetElementCount() (elementCount int64)

GetElementCount Return number of elements in the Merkle Tree managed by this MerkleManager

func (*MerkleManager) GetElementIndex 

func (m *MerkleManager) GetElementIndex(hash []byte) (i int64, err error)

GetElementIndex Get an Element of a Merkle Tree from the database

func (*MerkleManager) GetIntermediate 

func (m *MerkleManager) GetIntermediate(element, height int64) (Left, Right Hash, err error)

GetIntermediate Return the last two hashes that were combined to create the local Merkle Root at the given index. The element provided must be odd, and the Pending List must be fully populated up to height specified.

func (*MerkleManager) GetRange 

func (m *MerkleManager) GetRange(key storage.Key, begin, end int64) (hashes []Hash, err error)

GetRange returns the list of hashes with indexes indicated by range: (begin,end) begin must be before or equal to end. The hash with index begin upto but not including end are the hashes returned. Indexes are zero based, so the first hash in the MerkleState is at 0

func (*MerkleManager) GetState 

func (m *MerkleManager) GetState(element int64) *MerkleState

GetState Query the database for the MerkleState for a given index, i.e. the state Note that not every element in the Merkle Tree has a stored state; states are stored at the frequency indicated by the Mark Power. We also store the state of the chain at the end of a block regardless, but this state overwrites the previous block state.

If no state exists in the database for the element, GetState returns nil

func (*MerkleManager) ManageChain 

func (m *MerkleManager) ManageChain(key storage.Key) (*MerkleManager, error)

ManageChain returns a copy of the manager with the key set to the given value.

func (*MerkleManager) ReadChainHead 

func (m *MerkleManager) ReadChainHead(key storage.Key) (ms *MerkleState, err error)

ReadChainHead Retrieve the current MerkleState from the given database, and set that state as the MerkleState of this MerkleManager. Note that the cache will be cleared.

func (*MerkleManager) SetKey 

func (m *MerkleManager) SetKey(key storage.Key) (err error)

SetKey adds the chainID to the MerkleManager for storing some chain specific key value pairs where the key is an index. Before any hash is added to a MerkleState, the ChainID should be set

func (*MerkleManager) WriteChainHead 

func (m *MerkleManager) WriteChainHead(key storage.Key) error

WriteChainHead Save the current MerkleState as the head of the chain. This does not flush the database, because all chains in an application need have their head of chain updated as one atomic transaction to prevent messing up the database

type MerkleState 

type MerkleState struct {
	HashFunction HashFunc       // Hash function for this Merkle State
	Count        int64          // Count of hashes added to the Merkle tree
	Pending      SparseHashList // Array of hashes that represent the left edge of the Merkle tree
	HashList     HashList       // List of Hashes in the order added to the chain
}

MerkleState A Merkle Dag State is the state kept while building a Merkle Tree. Except where a Merkle Tree has a clean power of two number of elements as leaf nodes, there will be multiple Sub Merkle Trees that make up a dynamic Merkle Tree. The Merkle State is the list of the roots of these sub Merkle Trees, and the combination of these roots provides a Directed Acyclic Graph (DAG) to all the leaves. 

                                                     Merkle State
1  2   3  4   5  6   7  8   9 10  11 12  13 --->         13
 1-2    3-4    5-6    7-8   0-10  11-12     --->         --
    1-2-3-4       5-6-7-8    0-10-11-12     --->     0-10-11-12
          1-2-3-4-5-6-7-8                   --->   1-2-3-4-5-6-7-8

Interestingly, the state of building such a Merkle Tree looks just like counting in binary. And the higher order bits set will correspond to where the binary roots must be kept in a Merkle state.

func (*MerkleState) AddToMerkleTree 

func (m *MerkleState) AddToMerkleTree(hash_ []byte)

AddToMerkleTree Add a Hash to the merkle tree and incrementally build the MerkleState

func (MerkleState) Copy 

func (m MerkleState) Copy() *MerkleState

Copy Make a completely independent copy of the Merkle State that removes all references to the structures in the given Merkle State. This means copying any entries in the Pending slice

func (*MerkleState) Equal 

func (m *MerkleState) Equal(m2 *MerkleState) (isEqual bool)

Equal Compares one MerkleState to another, and returns true if they are the same

func (*MerkleState) GetIntermediate added in v0.5.1 

func (m *MerkleState) GetIntermediate(hash Hash, height int64) (left, right Hash, err error)

GetIntermediate returns the last two hashes that were combined to create the local Merkle Root at the given index. The element Pending List must be fully populated up to height specified.

func (*MerkleState) GetMDRoot 

func (m *MerkleState) GetMDRoot() (MDRoot Hash)

GetMDRoot Compute the Merkle Directed Acyclic Graph (Merkle DAG or MerkleState) for the MerkleState at this point We take any trailing hashes in MerkleState, hash them up and combine to create the Merkle Dag Root. Getting the closing ListMDRoot is non-destructive, which is useful for some use cases.

Returns a nil if the MerkleSate is empty.

func (*MerkleState) InitSha256 

func (m *MerkleState) InitSha256()

InitSha256 Set the hashing function of this Merkle State to Sha256 TODO: Actually update the library to be able to use various hash algorithms

func (*MerkleState) Marshal 

func (m *MerkleState) Marshal() (MSBytes []byte, err error)

Marshal Encodes the Merkle State so it can be embedded into the Merkle Tree

func (*MerkleState) Pad 

func (m *MerkleState) Pad()

Pad Add a nil to the end of the Pending list if one isn't there. We need to be able to add an element to Pending if needed while building receipts

func (*MerkleState) PadPending 

func (m *MerkleState) PadPending()

PadPending Make sure the Pending list ends in a nil. This avoids some corner cases and simplifies adding elements to the merkle tree. If Pending doesn't have a last entry with a nil value, then one is added.

func (*MerkleState) PrintMR 

func (m *MerkleState) PrintMR() (mr string)

PrintMR For debugging purposes, it is nice to get a string that shows the nil and non nil entries in c.MerkleState Note that the "low order" entries are first in the string, so the binary is going from low order on the left to high order going right in the string rather than how binary is normally represented.

func (MerkleState) String 

func (m MerkleState) String() string

String convert the MerkleState to a human readable string

func (*MerkleState) Trim 

func (m *MerkleState) Trim()

Trim Remove any trailing nils from Pending hashes

func (*MerkleState) UnMarshal 

func (m *MerkleState) UnMarshal(MSBytes []byte) (err error)

UnMarshal Take the state of an MSMarshal instance defined by MSBytes, and set all the values in this instance of MSMarshal to the state defined by MSBytes. It is assumed that the hash function has been set by the caller.

type Receipt 

type Receipt struct {
	Element      Hash           // Hash for which we want a proof.
	ElementIndex int64          //
	Anchor       Hash           // Hash at the point where the Anchor was created.
	AnchorIndex  int64          //
	MDRoot       Hash           // Root expected once all nodes are applied
	Nodes        []*ReceiptNode // Apply these hashes to create an anchor
	// contains filtered or unexported fields
}

Receipt Struct builds the Merkle Tree path component of a Merkle Tree Proof.

func CombineReceipts added in v0.5.1 

func CombineReceipts(receipts ...*Receipt) (*Receipt, error)

CombineReceipts combines multiple receipts.

func GetReceipt 

func GetReceipt(manager *MerkleManager, element Hash, anchor Hash) (r *Receipt, err error)

GetReceipt Given a merkle tree and two elements, produce a proof that the element was used to derive the DAG at the anchor Note that the element must be added to the Merkle Tree before the anchor, but the anchor can be any element after the element, or even the element itself.

func NewReceipt 

func NewReceipt(manager *MerkleManager) *Receipt

func (*Receipt) BuildReceipt 

func (r *Receipt) BuildReceipt() error

BuildReceipt takes the values collected by GetReceipt and flushes out the data structures in the Receipt to represent a fully populated version.

func (*Receipt) BuildReceiptWith added in v0.5.1 

func (r *Receipt) BuildReceiptWith(getIntermediate GetIntermediateFunc, hashFunc HashFunc, anchorState *MerkleState) error

func (*Receipt) Combine 

func (r *Receipt) Combine(rm *Receipt) (*Receipt, error)

Combine Take a 2nd receipt, attach it to a root receipt, and return the resulting receipt. The idea is that if this receipt is anchored into another chain, Then we can create a receipt that proves the element in this receipt all the way down to an anchor in the root receipt. Note that both this receipt and the root receipt are expected to be good.

func (*Receipt) Copy 

func (r *Receipt) Copy() *Receipt

Copy Make a copy of this receipt

func (*Receipt) String 

func (r *Receipt) String() string

String Convert the receipt to a string

func (*Receipt) Validate 

func (r *Receipt) Validate() bool

Validate Take a receipt and validate that the element hash progresses to the Merkle Dag Root hash (MDRoot) in the receipt

type ReceiptNode 

type ReceiptNode struct {
	Right bool
	Hash  Hash
}

ReceiptNode Holds the Left/Right hash combinations for Receipts

func (*ReceiptNode) Copy 

func (n *ReceiptNode) Copy() *ReceiptNode

type SparseHashList 

type SparseHashList []Hash

func (SparseHashList) BinarySize 

func (l SparseHashList) BinarySize(height int64) int

func (SparseHashList) MarshalBinary 

func (l SparseHashList) MarshalBinary(height int64) ([]byte, error)

func (*SparseHashList) UnmarshalBinary 

func (l *SparseHashList) UnmarshalBinary(height int64, data []byte) error

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.