managed

package
v0.0.24 Latest Latest
Warning

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

 Go to latest Published: Sep 11, 2021 License: MIT Imports: 8 Imported by: 3

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

View Source 
const BlkIdxOff = byte(2) // Offset to the chain holding the block indexes for the chain and the pending chain
View Source 
const PendingOff = byte(1) // Offset to the chain holding pending transactions for managed chains

Variables

This section is empty.

Functions

func Add2AppID added in v0.0.24 

func Add2AppID(AppID []byte, offset byte) (appID []byte)

Add2AppID Compute the AppID for a shadow chain for a Merkle Tree. Note that bumping the index of the AppID allows shadow chains to exist within a different application space, and allows the underlying Patricia Tree to maintain its balanced nature.

The reason for shadow chains is to track information about the construction and validation of entries in a main chain that we do not wish to persist forever. We track two shadow chains at present. The PendingOff implements managed chains where the rules for entries must be evaluated by the Identity before they are added to the chain. So other identities can write to the chain, but those entries get redirected to the PendingOff shadow chain until they are authorized by the Identity.

The BlkIdxOff collects the block indexes to track where the minor blocks end so that entries can be recognized as timestamped at this finer resolution even after the minor blocks are rewritten into major blocks. Parties interested in this finer resolution can preserve these timestamps by simply getting a receipt and preserving it off chain or on chain.

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 BlockIndex 

type BlockIndex struct {
	BlockIndex   int64 // index of the block
	MainIndex    int64 // index of the last element in the main chain
	PendingIndex int64 // index of the last element in the Pending chain
}

BlockIndex Holds a mapping of the BlockIndex to the MainIndex and PendingIndex that mark the end of the block

func (*BlockIndex) Marshal 

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

Marshal serialize a BlockIndex into a slice of data

func (*BlockIndex) UnMarshal 

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

UnMarshal Extract a BlockIndex from a given slice. Return the remaining slice

type ChainManager 

type ChainManager struct {
	Manager *database.Manager
	MS      MerkleState
}

ChainManager Represents a struct for maintaining a Merkle Tree. Most chains have two Merkle Trees, the main chain and a shadow chain tracking blocks

func (*ChainManager) AddHash 

func (m *ChainManager) AddHash(MarkMask int64, hash Hash)

AddHash Add a Hash to the Chain controlled by the ChainManager

type Hash 

type Hash [32]byte

This Stateful Merkle Tree implementation handles 256 bit hashes

func (Hash) Bytes 

func (h Hash) Bytes() []byte

Bytes Return a []byte for the Hash

func (Hash) Combine 

func (h Hash) Combine(hf func(data []byte) Hash, 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) CopyAndPoint 

func (h Hash) CopyAndPoint() *Hash

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

type MerkleManager 

type MerkleManager struct {
	RootDBManager *database.Manager // AppID-less Manager for writing to the general DBState
	MainChain     ChainManager      // The used to hold entries to be kept forever
	PendingChain  ChainManager      // Managed pend entries unsigned by validators in this Scratch chain to be signed
	BlkIdxChain   ChainManager      // Tracks the indexes of the minor blocks
	MarkPower     int64             // log2 of the MarkFreq
	MarkFreq      int64             // The count between Marks
	MarkMask      int64             // The binary mask to detect Mark boundaries
	// contains filtered or unexported fields
}

func NewMerkleManager 

func NewMerkleManager(
	DBManager *database.Manager,
	appID []byte,
	markPower int64) *MerkleManager

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)

AddHash Add a Hash to the MainChain

func (*MerkleManager) AddHashString 

func (m *MerkleManager) AddHashString(hash string)

AddHashString Often instead of a hash, we have a hex string, but that's okay too.

func (*MerkleManager) AddPendingHash 

func (m *MerkleManager) AddPendingHash(hash Hash)

AddPendingHash Pending transactions for managed chains or suggested transactions go into the Pending Chain

func (MerkleManager) Copy 

func (m MerkleManager) Copy(appID []byte) *MerkleManager

Copy Create a copy of the MerkleManager. The MerkleManager can be pointed to particular merkle trees by setting the AppID. While the AppID is generally the management of a particular merkle tree, it can be used to define any application context within the database.

Copy creates a MerkleManager that points it to a particular ChainID (use the chainID as the appID)

Copy creates a brand new MerkleManager pointed towards a particular chain and its shadow chains (chains that track information about the main chain, i.e. the pending chain and the block index 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) GetIndex 

func (m *MerkleManager) GetIndex(element []byte) (index int64)

GetIndex Get the index of a given element

func (*MerkleManager) GetNext 

func (m *MerkleManager) GetNext(element int64) (hash *Hash)

GetNext Get the next hash to be added to a state at this height

func (*MerkleManager) GetState 

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

GetState Get a MerkleState for a given index, i.e. the state stored for the given index. Note that not every element in the Merkle Tree has a stored state; states are stored at the frequency indicated by the Mark Power.

If no state exists for the given element, GetState returns nil

func (*MerkleManager) SetBlockIndex 

func (m *MerkleManager) SetBlockIndex(blockIndex int64)

SetBlockIndex Keep track of where the blocks are in the Merkle Tree.

type MerkleState 

type MerkleState struct {
	HashFunction func(data []byte) Hash // Hash function for this Merkle State
	Count        int64                  // Count of hashes added to the Merkle tree
	Pending      []*Hash                // Array of hashes that represent the left edge of the Merkle tree
	HashList     []Hash                 // 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 GetElementState 

func GetElementState(
	manager *MerkleManager,
	element Hash,
) (
	currentState, nextMark *MerkleState,
	height int,
	nextMarkIndex int64)

GetElementState Looks through the Merkle Tree, and finds the state just before the element has been added to the Merkle Tree, and the height in the Pending list of the derivative of the element. Returns a nil for the merkleState if the element is not in the Merkle Tree

func (*MerkleState) AddToMerkleTree 

func (m *MerkleState) AddToMerkleTree(hash_ [32]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 structures in the given Merkle State. This means copying any entries in the Pending slice

func (MerkleState) CopyAndPoint 

func (m MerkleState) CopyAndPoint() *MerkleState

CopyAndPoint Make a completely independent copy of the Merkle State that removes all references to 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) 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)

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

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) UnMarshal 

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

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 Node 

type Node struct {
	Right bool
	Hash  [32]byte
}

type Receipt 

type Receipt struct {
	Element Hash    // Hash for which we want a proof.
	Anchor  Hash    // Directory Block Height of the Object
	Nodes   []*Node // Apply these hashes to create an anchor
}

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

func GetReceipt 

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

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 (*Receipt) AddAHash 

func (r *Receipt) AddAHash(
	CurrentState *MerkleState,
	Height int,
	Right bool,
	v1 Hash,
) (
	height int)

func (*Receipt) AdvanceMarkToMark 

func (r *Receipt) AdvanceMarkToMark(manager *MerkleManager, anchorState, currentState *MerkleState, height int) (
	atAnchor bool, newHeight int)

AdvanceMarkToMark Once the currentState is at a Mark, it can be advanced directly to the next Mark. The next Mark is a mark at a 2^n step forward through the elements. These states can be combined directly without processing all the intermediate elements.

Returns true (that the currentState is now the anchorState) or false

func (*Receipt) AdvanceToMark 

func (r *Receipt) AdvanceToMark(
	manager *MerkleManager,
	currentState, nextMark, anchorState *MerkleState,
	height int,
	markIndex int64,
) (
	atAnchor bool,
	newHeight int)

AdvanceToMark Advance the currentState (from any element) to the next Mark. Receipt is updated, where our proof is expected to be at height in the currentState If advancing to the next mark would take the currentState past the AnchorState, then AdvanceToMark only advances to the anchorState and returns true.

Returns true (that currentState is now the anchorState) or false

func (*Receipt) ComputeDag 

func (r *Receipt) ComputeDag(manager *MerkleManager, currentState *MerkleState, height int, right bool)

func (*Receipt) String 

func (r *Receipt) String() string

String Convert the receipt to a string

func (Receipt) Validate 

func (r Receipt) Validate() bool

Receipt Take a receipt and validate that the

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.