smt

package
v0.0.15 Latest Latest
Warning

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

 Go to latest Published: Mar 30, 2021 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 BoolBytes 

func BoolBytes(b bool) []byte

BoolBytes Marshal a Bool

func BytesBool 

func BytesBool(data []byte) (f bool, newData []byte)

BytesBool() Unmarshal a Uint8

func BytesInt64 

func BytesInt64(data []byte) (int64, []byte)

BytesInt64 Unmarshal a int64 (big endian) We only need this function on top of BytesUint64 to avoid a type conversion when dealing with int64 values

func BytesUint16 

func BytesUint16(data []byte) (uint16, []byte)

BytesUint16 Unmarshal a uint32 (big endian)

func BytesUint32 

func BytesUint32(data []byte) (uint32, []byte)

BytesUint32 Unmarshal a uint32 (big endian)

func BytesUint64 

func BytesUint64(data []byte) (uint64, []byte)

BytesUint64 Unmarshal a uint64 (big endian)

func GetHomeDir 

func GetHomeDir() string

GetHomeDir() Used to find the Home Directory from which the configuration directory for the ValAcc application to use for its database. This is not a terribly refined way of configuring the ValAcc and may be refined in the future.

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

func Int64Bytes 

func Int64Bytes(i int64) []byte

Int64Bytes Marshal a int64 (big endian) We only need this function on top of Uint64Bytes to avoid a type conversion when dealing with int64 values

func Uint16Bytes 

func Uint16Bytes(i uint16) []byte

Uint16Bytes Marshal a int32 (big endian)

func Uint32Bytes 

func Uint32Bytes(i uint32) []byte

Uint32Bytes Marshal a int32 (big endian)

func Uint64Bytes 

func Uint64Bytes(i uint64) []byte

Uint64Bytes Marshal a uint64 (big endian)

Types

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)

func (*Hash) Extract 

func (h *Hash) Extract(data []byte) []byte

Extract Pull out a hash from a byte slice, and return the remaining bytes

type MerkleManager added in v0.0.13 

type MerkleManager struct {
	DBManager *database.Manager // Database for holding the Merkle Tree
	MS        MerkleState       // The Merkle State Managed
	MarkPower int64             // log2 of the MarkFreq
	MarkFreq  int64             // The count between Marks
	MarkMask  int64             // The binary mask to detect Mark boundaries
	HashFeed  chan [32]byte     // Feed of hashes to be put into the Merkle State under management
}

func (*MerkleManager) AddHash added in v0.0.15 

func (m *MerkleManager) AddHash(hash []byte)

AddHash Add a hash to the Merkle Tree. Often instead of a hash, we have a byte slice, but that's okay too.

func (*MerkleManager) AddHashString added in v0.0.15 

func (m *MerkleManager) AddHashString(hash string)

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

func (*MerkleManager) GetElementCount added in v0.0.13 

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

getElementCount() Return the number of elements in the Merkle Tree managed by this MerkleManager

func (*MerkleManager) GetIndex added in v0.0.13 

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

GetIndex Get the index of a given element

func (*MerkleManager) GetNext added in v0.0.13 

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 added in v0.0.13 

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

GetState Get a MerkleState for a given index

func (*MerkleManager) Init added in v0.0.13 

func (m *MerkleManager) Init(DBManager *database.Manager, markPower int64)

Init Create a Merkle Tree manager to collect hashes and build a Merkle Tree and a database behind it to validate hashes and create receipts

func (*MerkleManager) Update added in v0.0.13 

func (m *MerkleManager) Update()

Update Pull from the HashFeed channel and add to the Merkle Tree managed by the MerkleManager

type MerkleState 

type MerkleState struct {
	HashFunction func(data []byte) Hash
	Count        int64   // Count of hashes added to the Merkle tree
	BlockNumber  int64   // Count of the blocks in the Stateful 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 added in v0.0.13 

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 added in v0.0.9 

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

AddToMerkleTree Add a Hash to the chain and incrementally build the MerkleState

func (MerkleState) Copy added in v0.0.11 

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 added in v0.0.13 

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

func (m *MerkleState) EndBlock() (MSBytes []byte, hash Hash)

EndBlock Data is added to a Merkle State over time. Entries can be grouped into Merkle Blocks. Each Merkle Block begins with the Merkle State describing the state of the Merkle Tree prior to that Merkle Block. Each Merkle block holds the hash of the Previous Merkle State.

Ending a Merkle Block means adding the Current Merkle State to the Merkle Tree. So every Merkle Block begins with the hash of the Merkle State of the end of the Previous Merkle Block.

NOTE: The caller is responsible for being able to match the Merkle State to the block by putting it in a database or memory map.

func (MerkleState) Equal added in v0.0.4 

func (m MerkleState) Equal(m2 MerkleState) (errorFlag 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 Close off the Merkle Directed Acyclic Graph (Merkle DAG or MerkleState) 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.

func (*MerkleState) InitSha256 

func (m *MerkleState) InitSha256()

InitSha256 Set the hashing function of this Merkle State to Sha256

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 added in v0.0.10 

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 added in v0.0.12 

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 added in v0.0.13 

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

type Receipt added in v0.0.13 

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 added in v0.0.13 

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 added in v0.0.13 

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

func (*Receipt) AdvanceMarkToMark added in v0.0.13 

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 added in v0.0.13 

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 added in v0.0.13 

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

func (*Receipt) String added in v0.0.13 

func (r *Receipt) String() string

String Convert the receipt to a string

func (Receipt) Validate added in v0.0.13 

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.