managed

package
v1.1.0-1 Latest Latest
Warning

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

 Go to latest Published: Dec 8, 2022 License: MIT Imports: 19 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 

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

func NewChain 

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

func (*Chain) CollectSnapshot 

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

func (*Chain) Commit 

func (c *Chain) Commit() error

func (*Chain) Element 

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

func (*Chain) ElementIndex 

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

func (*Chain) Head 

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

func (*Chain) IsDirty 

func (c *Chain) IsDirty() bool

func (*Chain) Name 

func (c *Chain) Name() string

func (*Chain) Resolve 

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

func (*Chain) RestoreElementIndexFromHead 

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

func (*Chain) RestoreElementIndexFromMarkPoints 

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

func (*Chain) RestoreHead 

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

func (*Chain) RestoreMarkPointRange 

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

func (*Chain) RestoreSnapshot 

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

func (*Chain) States 

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

func (*Chain) Type 

func (c *Chain) Type() ChainType

type ChainType 

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 

func ChainTypeByName(name string) (ChainType, bool)

ChainTypeByName returns the named Chain Type.

func (ChainType) GetEnumValue 

func (v ChainType) GetEnumValue() uint64

GetEnumValue returns the value of the Chain Type

func (ChainType) MarshalJSON 

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

MarshalJSON marshals the Chain Type to JSON as a string.

func (*ChainType) SetEnumValue 

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

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

func (ChainType) String 

func (v ChainType) String() string

String returns the name of the Chain Type.

func (*ChainType) UnmarshalJSON 

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

UnmarshalJSON unmarshals the Chain Type from JSON as a string.

type DbHash 

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

type DbInt 

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

type DbManager 

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

type DbValue 

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

type GetIntermediateFunc 

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 

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 

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 

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 

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 

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

func (*MerkleState) UnmarshalBinaryFrom 

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

type MerkleTestCase 

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 

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 

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 

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 

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

func (*Receipt) Equal 

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

func (*Receipt) IsValid 

func (v *Receipt) IsValid() error

func (*Receipt) MarshalBinary 

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

func (*Receipt) MarshalJSON 

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

func (*Receipt) String 

func (r *Receipt) String() string

String Convert the receipt to a string

func (*Receipt) UnmarshalBinary 

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

func (*Receipt) UnmarshalBinaryFrom 

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

func (*Receipt) UnmarshalJSON 

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 

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 

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

func (*ReceiptEntry) Copy 

func (v *ReceiptEntry) Copy() *ReceiptEntry

func (*ReceiptEntry) CopyAsInterface 

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

func (*ReceiptEntry) Equal 

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

func (*ReceiptEntry) IsValid 

func (v *ReceiptEntry) IsValid() error

func (*ReceiptEntry) MarshalBinary 

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

func (*ReceiptEntry) MarshalJSON 

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

func (*ReceiptEntry) UnmarshalBinary 

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

func (*ReceiptEntry) UnmarshalBinaryFrom 

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

func (*ReceiptEntry) UnmarshalJSON 

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

type ReceiptList 

type ReceiptList struct {

	// MerkleState MerkleState at the beginning of the list.
	MerkleState      *MerkleState `json:"merkleState,omitempty" form:"merkleState" query:"merkleState" validate:"required"`
	Elements         [][]byte     `json:"elements,omitempty" form:"elements" query:"elements" validate:"required"`
	Receipt          *Receipt     `json:"receipt,omitempty" form:"receipt" query:"receipt" validate:"required"`
	ContinuedReceipt *Receipt     `json:"continuedReceipt,omitempty" form:"continuedReceipt" query:"continuedReceipt" validate:"required"`
	// contains filtered or unexported fields
}

func GetReceiptList 

func GetReceiptList(manager *MerkleManager, Start int64, End int64) (r *ReceiptList, err error)

GetReceiptList Given a merkle tree with a start point and an end point, create a ReceiptList for all the elements from the start hash to the end hash, inclusive.

func NewReceiptList 

func NewReceiptList() *ReceiptList

NewReceiptList Return a new ReceiptList with at least a MerkleState initialized

func (*ReceiptList) Copy 

func (v *ReceiptList) Copy() *ReceiptList

func (*ReceiptList) CopyAsInterface 

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

func (*ReceiptList) Equal 

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

func (*ReceiptList) Included 

func (r *ReceiptList) Included(entry []byte) bool

Included Tests an entry for inclusion in the given ReceiptList Note that while a ReceiptList proves inclusion in a Merkle Tree, and the fact that the list of elements proceed in order up to and including the anchor point, the ReceiptList does not necessarily prove the indices of the elements in the Merkle Tree. This could be solved by salting Receipts with the index of the hash at the anchor point.

func (*ReceiptList) IsValid 

func (v *ReceiptList) IsValid() error

func (*ReceiptList) MarshalBinary 

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

func (*ReceiptList) MarshalJSON 

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

func (*ReceiptList) UnmarshalBinary 

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

func (*ReceiptList) UnmarshalBinaryFrom 

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

func (*ReceiptList) UnmarshalJSON 

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

func (*ReceiptList) Validate 

func (r *ReceiptList) Validate() bool

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

type Snapshot 

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 

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 

func (v *Snapshot) Copy() *Snapshot

func (*Snapshot) CopyAsInterface 

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

func (*Snapshot) Equal 

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

func (*Snapshot) IsValid 

func (v *Snapshot) IsValid() error

func (*Snapshot) MarshalBinary 

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

func (*Snapshot) MarshalJSON 

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

func (*Snapshot) UnmarshalBinary 

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

func (*Snapshot) UnmarshalBinaryFrom 

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

func (*Snapshot) UnmarshalJSON 

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 

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 

type YamlHexString []byte

func (*YamlHexString) UnmarshalYAML 

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.