common

Documentation

Overview

package common contains common interfaces and methods used across the merkle package.

Index

• Variables
• func BytesToNibbles(s []byte) (nibbles []byte)
• func CompactEncode(b []byte, isLeaf bool) (r []byte)
• func Concat(a, b []byte) (r []byte)
• func ExtractCommonPrefix(a, b []byte) (r []byte)
• func HasPrefix(seq, prefix []byte) bool
• type MPT
• type Trie

Variables

var (
	ErrKeyNotFound = fmt.Errorf("key not found")
)

Functions

func BytesToNibbles

func BytesToNibbles(s []byte) (nibbles []byte)

bytesToNibbles transforms the given []byte-ified hex string to a byte slice where each byte is exactly in the range of 0-f (i.e, a nibble - half a byte or 4 bits).

func CompactEncode

func CompactEncode(b []byte, isLeaf bool) (r []byte)

CompactEncode prepends the appropriate flags to the provided path. See the table below for details. It returns the path in bytes instead of nibbles.

hexchar | bits | node type partial | path length

0       |  0000    |       extension       |       even
1       |  0001    |       extension       |       odd
2       |  0010    |   terminating (leaf)  |       even
3       |  0011    |   terminating (leaf)  |       odd

func Concat

func Concat(a, b []byte) (r []byte)

func ExtractCommonPrefix

func ExtractCommonPrefix(a, b []byte) (r []byte)

func HasPrefix

func HasPrefix(seq, prefix []byte) bool

Types

type MPT

type MPT interface {
	Trie
	types.TrieHasher
	// Root returns the merkle root (i.e hash) of the entire MPT.
	Root() []byte
	ProofFor(key []byte) (proofDB ethdb.KeyValueReader)
}

MPT stands for "Merkle-Patricia Trie", which is a fusion of the merkle tree and patricia trie data structures.

The intent is to provide a key-value store that provides merkle proofs of membership.

type Trie

type Trie interface {
	// Get returns the value set for the provided key, if the key is in the trie.
	Get(key []byte) (value []byte, err error)
	// Put inserts a key-value pair into the trie.
	Put(key, value []byte) error
	// Delete removes the values associated with the provided key from the trie.
	Delete(key []byte) error
}

Trie defines the interface for a trie data structure. A trie is a search tree that implements a key-value store.