smt

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

• func BoolBytes(b bool) []byte
• func BytesBool(data []byte) (f bool, newData []byte)
• func BytesInt64(data []byte) (int64, []byte)
• func BytesUint16(data []byte) (uint16, []byte)
• func BytesUint32(data []byte) (uint32, []byte)
• func BytesUint64(data []byte) (uint64, []byte)
• func GetHomeDir() string
• func GetSha256() func(data []byte) Hash
• func Int64Bytes(i int64) []byte
• func Uint16Bytes(i uint16) []byte
• func Uint32Bytes(i uint32) []byte
• func Uint64Bytes(i uint64) []byte
• type Hash
  • func (h Hash) Bytes() []byte
  • func (h Hash) Combine(hf func(data []byte) Hash, right Hash) Hash
  • func (h Hash) Copy() Hash
  • func (h Hash) CopyAndPoint() *Hash
  • func (h *Hash) Extract(data []byte) []byte
• type MDReceipt
  • func (mdr *MDReceipt) BuildMDReceipt(MerkleDag MerkleState, data Hash)
  • func (mdr *MDReceipt) Validate() bool
• type MerkleState
  • func (m *MerkleState) AddToChain(hash_ [32]byte)
  • func (m *MerkleState) EndBlock() (MSBytes []byte)
  • func (m MerkleState) Equal(m2 MerkleState) bool
  • func (m MerkleState) GetCount() int64
  • func (m MerkleState) GetCurrentCount() int64
  • func (m *MerkleState) GetMDRoot() (MDRoot *Hash)
  • func (m MerkleState) GetPrevious() Hash
  • func (m *MerkleState) InitSha256()
  • func (m *MerkleState) Marshal() (MSBytes []byte)
  • func (m *MerkleState) PrintMR() (mr string)
  • func (m *MerkleState) UnMarshal(MSBytes []byte)
• type ReceiptNode

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 MDReceipt

type MDReceipt struct {
	EntryHash Hash           // Entry Hash of the data subject to the MDReceipt
	Nodes     []*ReceiptNode // Path through the data collected by the MerkleDag
	MDRoot    Hash           // Merkle DAG root from the Accumulator network.

}

func (*MDReceipt) BuildMDReceipt

func (mdr *MDReceipt) BuildMDReceipt(MerkleDag MerkleState, data Hash)

BuildMDReceipt Building a receipt is a bit more complex than just computing the Merkle DAG. We look at the stream of hashes as we build the MerkleState, and detect when the Hash for which we need a receipt shows up. Then we track it through the intermediate hashes, tracking if it is combined from the right or from the left. Then when we have to calculate the Merkle DAG root, we do one more pass through the combining of the trailing hashes to finish off the receipt.

func (*MDReceipt) Validate

func (mdr *MDReceipt) Validate() bool

Validate Run down the Merkle DAG and prove that this receipt self validates

type MerkleState

type MerkleState struct {
	HashFunction func(data []byte) Hash

	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
	// contains filtered or unexported fields
}

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 roots. The combination of these roots provides a Directed Acyclic Graph (DAG) to all the leaves.

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

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

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

func (*MerkleState) EndBlock

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

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.

We

func (MerkleState) Equal

func (m MerkleState) Equal(m2 MerkleState) bool

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

func (MerkleState) GetCount

func (m MerkleState) GetCount() int64

GetCount Get the count of elements in the Merkle Tree

func (MerkleState) GetCurrentCount

func (m MerkleState) GetCurrentCount() int64

GetCurrentCount Get the count of the hashes added in the current Merkle Block

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

func (m MerkleState) GetPrevious() Hash

GetPrevious Get the hash of the Previous MerkleState

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

type ReceiptNode struct {
	Right bool // The given Hash will be on the Right (right==true) or on the left (right==false)
	Hash  Hash // hash to be combined at the next level
}