trie

Documentation

Index

• Variables
• func HashDomains(domains ...string) []byte
• func HashDomainsPrefix(domains ...string) []byte
• type Action
• type Entry
• type Iterator
  • func (it *Iterator) Key() []byte
  • func (it *Iterator) Next() (bool, error)
  • func (it *Iterator) Value() []byte
• type IteratorState
• type MerkleProof
• type Trie
  • func NewTrie(rootHash []byte, storage storage.Storage, needChangelog bool) (*Trie, error)
  • func (t *Trie) Clone() (*Trie, error)
  • func (t *Trie) CopyTo(storage storage.Storage, needChangelog bool) (*Trie, error)
  • func (t *Trie) Del(key []byte) ([]byte, error)
  • func (t *Trie) Empty() bool
  • func (t *Trie) Get(key []byte) ([]byte, error)
  • func (t *Trie) Iterator(prefix []byte) (*Iterator, error)
  • func (t *Trie) Prove(key []byte) (MerkleProof, error)
  • func (t *Trie) Put(key []byte, val []byte) ([]byte, error)
  • func (t *Trie) Replay(ft *Trie) ([]byte, error)
  • func (t *Trie) RootHash() []byte
  • func (t *Trie) SyncPath(rootHash []byte, key []byte) error
  • func (t *Trie) SyncTrie(rootHash []byte) error
  • func (t *Trie) Verify(rootHash []byte, key []byte, proof MerkleProof) error

Variables

var (
	ErrNotFound           = storage.ErrKeyNotFound
	ErrInvalidProtoToNode = errors.New("Pb Message cannot be converted into Trie Node")
)

Errors

var (
	ErrNotIterable = errors.New("leaf node is not iterable")
)

errors constants

Functions

func HashDomains

func HashDomains(domains ...string) []byte

HashDomains for each variable in contract each domain will represented as 6 bytes, support 4 level domain at most such as, 4a56b7 000000 000000 000000, 4a56b8 1c9812 000000 000000, 4a56b8 3a1289 000000 000000, support iterator with same prefix

func HashDomainsPrefix

func HashDomainsPrefix(domains ...string) []byte

HashDomainsPrefix is same as HashDomains, but without tail zeros

Types

type Action

type Action int

Action represents operation types in Trie

const (
	Insert Action = iota
	Update
	Delete
)

Action constants

type Entry

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

Entry in log, [key, old value, new value]

type Iterator

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

Iterator to traverse leaf node in a trie

func (*Iterator) Key

func (it *Iterator) Key() []byte

Key return current leaf node's key

func (*Iterator) Next

func (it *Iterator) Next() (bool, error)

Next return if there is next leaf node

func (*Iterator) Value

func (it *Iterator) Value() []byte

Value return current leaf node's value

type IteratorState

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

IteratorState represents the intermediate statue in iterator

type MerkleProof

type MerkleProof [][][]byte

MerkleProof is a path from root to the proved node every element in path is the value of a node

type Trie

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

Trie is a Merkle Patricia Trie, consists of three kinds of nodes, Branch Node: 16-elements array, value is [hash_0, hash_1, ..., hash_f, hash] Extension Node: 3-elements array, value is [ext flag, prefix path, next hash] Leaf Node: 3-elements array, value is [leaf flag, suffix path, value]

func NewTrie

func NewTrie(rootHash []byte, storage storage.Storage, needChangelog bool) (*Trie, error)

NewTrie if rootHash is nil, create a new Trie, otherwise, build an existed trie

func (*Trie) Clone

func (t *Trie) Clone() (*Trie, error)

Clone the trie to create a new trie sharing the same storage

func (*Trie) CopyTo

func (t *Trie) CopyTo(storage storage.Storage, needChangelog bool) (*Trie, error)

CopyTo copy the trie structure into the given storage

func (*Trie) Del

func (t *Trie) Del(key []byte) ([]byte, error)

Del the node's value in trie

1. ext(ext->leaf-->leaf,ext->ext--->ext)

2. branch(branch->leaf-->leaf,branch->branch-->ext->branch,branch->ext-->ext)

   ext ext | | branch --> leaf --> leaf / \

[leaf] leaf

  	branch					 ext
	/	\					  |

[leaf] ext --> branch

		 |
	   branch

  	branch					 ext
	/	\					  |

[leaf] branch --> branch

/	\				/	\
leaf leaf			leaf leaf

func (*Trie) Empty

func (t *Trie) Empty() bool

Empty return if the trie is empty

func (*Trie) Get

func (t *Trie) Get(key []byte) ([]byte, error)

Get the value to the key in trie

func (*Trie) Iterator

func (t *Trie) Iterator(prefix []byte) (*Iterator, error)

Iterator return an iterator

func (*Trie) Prove

func (t *Trie) Prove(key []byte) (MerkleProof, error)

Prove the associated node to the key exists in trie if exists, MerkleProof is a complete path from root to the node otherwise, MerkleProof is nil

func (*Trie) Put

func (t *Trie) Put(key []byte, val []byte) ([]byte, error)

Put the key-value pair in trie

func (*Trie) Replay

func (t *Trie) Replay(ft *Trie) ([]byte, error)

Replay return roothash not save key to storage

func (*Trie) RootHash

func (t *Trie) RootHash() []byte

RootHash return the rootHash of trie

func (*Trie) SyncPath

func (t *Trie) SyncPath(rootHash []byte, key []byte) error

SyncPath from rootHash to key node from other servers Useful for verification quickly

func (*Trie) SyncTrie

func (t *Trie) SyncTrie(rootHash []byte) error

SyncTrie data from other servers Sync whole trie to build snapshot

func (*Trie) Verify

func (t *Trie) Verify(rootHash []byte, key []byte, proof MerkleProof) error

Verify whether the merkle proof from root to the associated node is right