managed

package
v1.0.0 Latest Latest
Warning

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

 Go to latest Published: Oct 31, 2022 License: MIT Imports: 20 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 Chain added in v1.0.0 

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

func NewChain added in v1.0.0 

func NewChain(logger log.Logger, store record.Store, key record.Key, markPower int64, typ ChainType, namefmt, labelfmt string) *Chain

func (*Chain) CollectSnapshot added in v1.0.0 

func (c *Chain) CollectSnapshot() (*Snapshot, error)

func (*Chain) Commit added in v1.0.0 

func (c *Chain) Commit() error

func (*Chain) Element added in v1.0.0 

func (c *Chain) Element(index uint64) *record.Value[[]byte]

func (*Chain) ElementIndex added in v1.0.0 

func (c *Chain) ElementIndex(hash []byte) *record.Value[uint64]

func (*Chain) Head added in v1.0.0 

func (c *Chain) Head() *record.Value[*MerkleState]

func (*Chain) IsDirty added in v1.0.0 

func (c *Chain) IsDirty() bool

func (*Chain) Name added in v1.0.0 

func (c *Chain) Name() string

func (*Chain) Resolve added in v1.0.0 

func (c *Chain) Resolve(key record.Key) (record.Record, record.Key, error)

func (*Chain) RestoreElementIndexFromHead added in v1.0.0 

func (c *Chain) RestoreElementIndexFromHead(s *Snapshot) error

func (*Chain) RestoreElementIndexFromMarkPoints added in v1.0.0 

func (c *Chain) RestoreElementIndexFromMarkPoints(s *Snapshot, start, end int) error

func (*Chain) RestoreHead added in v1.0.0 

func (c *Chain) RestoreHead(s *Snapshot) error

func (*Chain) RestoreMarkPointRange added in v1.0.0 

func (c *Chain) RestoreMarkPointRange(s *Snapshot, start, end int) error

func (*Chain) RestoreSnapshot added in v1.0.0 

func (c *Chain) RestoreSnapshot(s *Snapshot) error

func (*Chain) States added in v1.0.0 

func (c *Chain) States(index uint64) *record.Value[*MerkleState]

func (*Chain) Type added in v1.0.0 

func (c *Chain) Type() ChainType

type ChainType added in v1.0.0 

type ChainType uint64

ChainType is the type of a chain belonging to an account. 

const ChainTypeAnchor ChainType = 2

ChainTypeAnchor holds chain anchors. 

const ChainTypeIndex ChainType = 4

ChainTypeIndex indexes other chains. 

const ChainTypeTransaction ChainType = 1

ChainTypeTransaction holds transaction hashes. 

const ChainTypeUnknown ChainType = 0

ChainTypeUnknown is used when the chain type is not known.

func ChainTypeByName added in v1.0.0 

func ChainTypeByName(name string) (ChainType, bool)

ChainTypeByName returns the named Chain Type.

func (ChainType) GetEnumValue added in v1.0.0 

func (v ChainType) GetEnumValue() uint64

GetEnumValue returns the value of the Chain Type

func (ChainType) MarshalJSON added in v1.0.0 

func (v ChainType) MarshalJSON() ([]byte, error)

MarshalJSON marshals the Chain Type to JSON as a string.

func (*ChainType) SetEnumValue added in v1.0.0 

func (v *ChainType) SetEnumValue(id uint64) bool

SetEnumValue sets the value. SetEnumValue returns false if the value is invalid.

func (ChainType) String added in v1.0.0 

func (v ChainType) String() string

String returns the name of the Chain Type.

func (*ChainType) UnmarshalJSON added in v1.0.0 

func (v *ChainType) UnmarshalJSON(data []byte) error

UnmarshalJSON unmarshals the Chain Type from JSON as a string.

type DbHash added in v1.0.0 

type DbHash interface {
	Get() (Hash, error)
	Put(Hash) error
}

type DbInt added in v1.0.0 

type DbInt interface {
	Get() (int64, error)
	Put(int64) error
}

type DbManager added in v1.0.0 

type DbManager interface {
	Int(key storage.Key) DbInt
	Hash(key storage.Key) DbHash
	State(key storage.Key) DbValue[*MerkleState]
}

type DbValue added in v1.0.0 

type DbValue[T encoding.BinaryValue] interface {
	Get() (T, error)
	Put(T) error
}

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 = Chain

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

func (m *MerkleManager) GetElementIndex(hash []byte) (int64, 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(begin, end int64) ([]Hash, 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

type MerkleState 

type MerkleState struct {
	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) CopyAsInterface added in v1.0.0 

func (m *MerkleState) CopyAsInterface() interface{}

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) MarshalBinary added in v1.0.0 

func (m *MerkleState) MarshalBinary() ([]byte, error)

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.

func (*MerkleState) UnmarshalBinary added in v1.0.0 

func (m *MerkleState) UnmarshalBinary(data []byte) error

func (*MerkleState) UnmarshalBinaryFrom added in v1.0.0 

func (m *MerkleState) UnmarshalBinaryFrom(rd io.Reader) error

type MerkleTestCase added in v1.0.0 

type MerkleTestCase struct {
	Root    YamlHexString
	Entries []YamlHexString
	Cascade []YamlHexString
}

type Receipt 

type Receipt struct {

	// Start is the entry for which we want a proof.
	Start      []byte `json:"start,omitempty" form:"start" query:"start" validate:"required"`
	StartIndex int64  `json:"startIndex,omitempty" form:"startIndex" query:"startIndex" validate:"required"`
	// End is the entry at the index where the anchor was created.
	End      []byte `json:"end,omitempty" form:"end" query:"end" validate:"required"`
	EndIndex int64  `json:"endIndex,omitempty" form:"endIndex" query:"endIndex" validate:"required"`
	// Anchor is the root expected once all nodes are applied.
	Anchor []byte `json:"anchor,omitempty" form:"anchor" query:"anchor" validate:"required"`
	// Entries is the list of hashes to apply to create an anchor.
	Entries []*ReceiptEntry `json:"entries,omitempty" form:"entries" query:"entries" validate:"required"`
	// contains filtered or unexported fields
}

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) Contains added in v1.0.0 

func (r *Receipt) Contains(other *Receipt) bool

Contains returns true if the 2nd receipt is equal to or contained within the first.

func (*Receipt) Copy 

func (v *Receipt) Copy() *Receipt

func (*Receipt) CopyAsInterface added in v1.0.0 

func (v *Receipt) CopyAsInterface() interface{}

func (*Receipt) Equal added in v1.0.0 

func (v *Receipt) Equal(u *Receipt) bool

func (*Receipt) IsValid added in v1.0.0 

func (v *Receipt) IsValid() error

func (*Receipt) MarshalBinary added in v1.0.0 

func (v *Receipt) MarshalBinary() ([]byte, error)

func (*Receipt) MarshalJSON added in v1.0.0 

func (v *Receipt) MarshalJSON() ([]byte, error)

func (*Receipt) String 

func (r *Receipt) String() string

String Convert the receipt to a string

func (*Receipt) UnmarshalBinary added in v1.0.0 

func (v *Receipt) UnmarshalBinary(data []byte) error

func (*Receipt) UnmarshalBinaryFrom added in v1.0.0 

func (v *Receipt) UnmarshalBinaryFrom(rd io.Reader) error

func (*Receipt) UnmarshalJSON added in v1.0.0 

func (v *Receipt) UnmarshalJSON(data []byte) error

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 ReceiptEntry added in v1.0.0 

type ReceiptEntry struct {
	Right bool   `json:"right,omitempty" form:"right" query:"right" validate:"required"`
	Hash  []byte `json:"hash,omitempty" form:"hash" query:"hash" validate:"required"`
	// contains filtered or unexported fields
}

func (*ReceiptEntry) Apply added in v1.0.0 

func (n *ReceiptEntry) Apply(hash Hash) Hash

func (*ReceiptEntry) Copy added in v1.0.0 

func (v *ReceiptEntry) Copy() *ReceiptEntry

func (*ReceiptEntry) CopyAsInterface added in v1.0.0 

func (v *ReceiptEntry) CopyAsInterface() interface{}

func (*ReceiptEntry) Equal added in v1.0.0 

func (v *ReceiptEntry) Equal(u *ReceiptEntry) bool

func (*ReceiptEntry) IsValid added in v1.0.0 

func (v *ReceiptEntry) IsValid() error

func (*ReceiptEntry) MarshalBinary added in v1.0.0 

func (v *ReceiptEntry) MarshalBinary() ([]byte, error)

func (*ReceiptEntry) MarshalJSON added in v1.0.0 

func (v *ReceiptEntry) MarshalJSON() ([]byte, error)

func (*ReceiptEntry) UnmarshalBinary added in v1.0.0 

func (v *ReceiptEntry) UnmarshalBinary(data []byte) error

func (*ReceiptEntry) UnmarshalBinaryFrom added in v1.0.0 

func (v *ReceiptEntry) UnmarshalBinaryFrom(rd io.Reader) error

func (*ReceiptEntry) UnmarshalJSON added in v1.0.0 

func (v *ReceiptEntry) UnmarshalJSON(data []byte) error

type Snapshot added in v1.0.0 

type Snapshot struct {
	Name       string         `json:"name,omitempty" form:"name" query:"name" validate:"required"`
	Type       ChainType      `json:"type,omitempty" form:"type" query:"type" validate:"required"`
	MarkPower  uint64         `json:"markPower,omitempty" form:"markPower" query:"markPower" validate:"required"`
	Head       *MerkleState   `json:"head,omitempty" form:"head" query:"head" validate:"required"`
	MarkPoints []*MerkleState `json:"markPoints,omitempty" form:"markPoints" query:"markPoints" validate:"required"`
	// contains filtered or unexported fields
}

func (*Snapshot) AddEntry added in v1.0.0 

func (c *Snapshot) AddEntry(hash Hash)

AddEntry adds an entry to the snapshot as if it were added to the chain. AddEntry's logic must mirror MerkleManager.AddHash.

func (*Snapshot) Copy added in v1.0.0 

func (v *Snapshot) Copy() *Snapshot

func (*Snapshot) CopyAsInterface added in v1.0.0 

func (v *Snapshot) CopyAsInterface() interface{}

func (*Snapshot) Equal added in v1.0.0 

func (v *Snapshot) Equal(u *Snapshot) bool

func (*Snapshot) IsValid added in v1.0.0 

func (v *Snapshot) IsValid() error

func (*Snapshot) MarshalBinary added in v1.0.0 

func (v *Snapshot) MarshalBinary() ([]byte, error)

func (*Snapshot) MarshalJSON added in v1.0.0 

func (v *Snapshot) MarshalJSON() ([]byte, error)

func (*Snapshot) UnmarshalBinary added in v1.0.0 

func (v *Snapshot) UnmarshalBinary(data []byte) error

func (*Snapshot) UnmarshalBinaryFrom added in v1.0.0 

func (v *Snapshot) UnmarshalBinaryFrom(rd io.Reader) error

func (*Snapshot) UnmarshalJSON added in v1.0.0 

func (v *Snapshot) UnmarshalJSON(data []byte) error

type SparseHashList 

type SparseHashList [][]byte

func (SparseHashList) BinarySize 

func (l SparseHashList) BinarySize(height int64) int

func (SparseHashList) Copy added in v1.0.0 

func (l SparseHashList) Copy() SparseHashList

func (SparseHashList) MarshalBinary 

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

func (*SparseHashList) UnmarshalBinary 

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

type YamlHexString added in v1.0.0 

type YamlHexString []byte

func (*YamlHexString) UnmarshalYAML added in v1.0.0 

func (s *YamlHexString) UnmarshalYAML(value *yaml.Node) 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.