trie

Documentation

Overview

Copyright (C) 2018 go-cloudcard authors

This file is part of the go-cloudcard library.

the go-cloudcard library is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

the go-cloudcard library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with the go-cloudcard library. If not, see <http://www.gnu.org/licenses/>.

Copyright (C) 2018 go-cloudcard authors

This file is part of the go-cloudcard library.

the go-cloudcard library is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

the go-cloudcard library is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with the go-cloudcard library. If not, see <http://www.gnu.org/licenses/>.

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 cdb.Storage, needChangelog bool) (*Trie, error)
  • func (t *Trie) Clone() (*Trie, error)
  • func (t *Trie) CopyTo(storage cdb.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) Verify(rootHash []byte, key []byte, proof MerkleProof) error

Variables

var (
	ErrNotFound           = cdb.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 cdb.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 cdb.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) 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