merkle

package
v0.0.0-...-4f0ab6e Latest Latest
Warning

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

 Go to latest Published: Nov 29, 2021 License: MIT Imports: 12 Imported by: 16

Documentation

Index

Constants

View Source 
const (
	// HashSize defines the length of hash array.
	HashSize = 32
	// Left points to the left subtree path of the merkle tree.
	Left byte = 0
	// Right points to the right subtree path of the merkle tree.
	Right byte = 1
	// UnknownSize means size of merkle tree is unknown.
	UnknownSize = -1
)
View Source 
const (
	// NilKey means there is no merkle node the same to this.
	NilKey = 0
	// HashOffset is the offset of hash，used to analyze the hash for given byte slice.
	HashOffset = 32
	// PidOffset is the offset of parent id ，used to analyze the pid for given byte slice.
	PidOffset = HashOffset + 8
	// LidOffset is the offset of left id ,used to analyze the lid for given byte slice.
	LidOffset = PidOffset + 8
	// RidOffset is the offset of right id ,used to analyze the rid for given byte slice.
	RidOffset = LidOffset + 8
	// ValueInDbLength is the length for one merkle node data in level db.
	ValueInDbLength = RidOffset
)

Variables

View Source 
var EmptyHash = MerkleHash{}

EmptyHash defines a default merkle hash.

Functions

func VerifyLastNodeMerklePath 

func VerifyLastNodeMerklePath(merkleRoot *MerkleHash, size int64, lastNodeMerklePath *MerklePath) error

VerifyLastNodeMerklePath verify a merkle path is the merkle path for the last leaf node in the merkle tree before updating. This method has the assumption that the size is trustworthy.

Types

type DeltaMerkleTree 

type DeltaMerkleTree struct {
	MerkleTree
}

DeltaMerkleTree is a data structure used by normal node to calculate the delta updates to ledger's merkle tree without knowing the tree itself. It's able to update leaves' hash using its merkle path, append new node into the tree, and given a merkle path from old merkle tree, create a new merkle path corresponding to the new tree. One tree instance is corresponding to one block's update to ledger's merkle tree. Create a new one when handling a new block.

func NewDeltaMerkleTree 

func NewDeltaMerkleTree(merkleRoot *MerkleHash) *DeltaMerkleTree

NewDeltaMerkleTree creates a delta merkle tree.

func (*DeltaMerkleTree) Append 

func (deltaMerkleTree *DeltaMerkleTree) Append(leaves ...*MerkleHash) error

Append add leaves to delta merkle tree.

func (*DeltaMerkleTree) GetMerklePath 

func (merkleTree *DeltaMerkleTree) GetMerklePath(hash *MerkleHash) (*MerklePath, error)

GetMerklePath returns the merkle path.

func (*DeltaMerkleTree) GetMerkleRoot 

func (deltaMerkleTree *DeltaMerkleTree) GetMerkleRoot() *MerkleHash

Returns the merkle root after updates.

func (*DeltaMerkleTree) GetShardDataMerklePath 

func (deltaMerkleTree *DeltaMerkleTree) GetShardDataMerklePath(oldHash, newHash *MerkleHash) (*MerklePath, error)

GetShardDataMerklePath update a leaf node's hash to a new hash.

func (*DeltaMerkleTree) RefreshMerklePath 

func (deltaMerkleTree *DeltaMerkleTree) RefreshMerklePath(merklePath *MerklePath) (*MerklePath, error)

RefreshMerklePath refresh an old merkle path which points to the old merkle root to a new merkle path that points to the new merkle root.

func (*DeltaMerkleTree) SetSizeAndLastNodeMerklePath 

func (deltaMerkleTree *DeltaMerkleTree) SetSizeAndLastNodeMerklePath(size int64, lastNodeMerklePath *MerklePath) error

SetSizeAndLastNodeMerklePath is in order to append node into merkle tree, this tree needs to know the size of tree and last node's merkle path.

func (*DeltaMerkleTree) UpdateLeaf 

func (deltaMerkleTree *DeltaMerkleTree) UpdateLeaf(merklePath *MerklePath, newHash *MerkleHash) error

UpdateLeaf update a leaf node's hash to a new hash.

type FullMerkleTree 

type FullMerkleTree struct {
	MerkleTree
}

FullMerkleTree is the data structure of full merkle tree.

func NewClippedMerkleTree 

func NewClippedMerkleTree(
	size int64, startIndex int64, numLeaves int64, leaves []*MerkleHash,
	leftMerklePath *MerklePath, rightMerklePath *MerklePath) (*FullMerkleTree, error)

NewClippedMerkleTree create a clipped merkle tree given:

  • size of total leaves.
  • a list of leaves
  • merkle path of the first element of the give leaves.
  • merkle path of the last element of the given leaves.

func NewFullMerkleTree 

func NewFullMerkleTree(leaves ...*MerkleHash) *FullMerkleTree

NewFullMerkleTree create a full merkle tree given all the leaves. This will be used to build merkle tree for outs in a block.

func NewOnDiskFullMerkleTree 

func NewOnDiskFullMerkleTree(db db.DB) *FullMerkleTree

NewOnDiskFullMerkleTree create a full merkle tree given all the leaves. Data in this merkle tree is saved on disk.

func (*FullMerkleTree) Append 

func (merkleTree *FullMerkleTree) Append(leaves ...*MerkleHash) error

Append is to add new leaves and update merkle tree's root.

func (*FullMerkleTree) GetMerklePath 

func (merkleTree *FullMerkleTree) GetMerklePath(hash *MerkleHash) (*MerklePath, error)

GetMerklePath returns the merkle path.

func (*FullMerkleTree) HasNode 

func (merkleTree *FullMerkleTree) HasNode(hash *MerkleHash) bool

HasNode checks whether there is the node in full merkle tree.

func (*FullMerkleTree) HookSecondLayerTree 

func (merkleTree *FullMerkleTree) HookSecondLayerTree(subtree *FullMerkleTree) error

HookSecondLayerTree is to build a two layer merkle tree. A leaf node of top layer tree is root node of a second layer tree.

func (*FullMerkleTree) UpdateLeaf 

func (merkleTree *FullMerkleTree) UpdateLeaf(originalHash *MerkleHash, newHash *MerkleHash) error

UpdateLeaf update the leaf and merkle root.

type MerkleHash 

type MerkleHash [HashSize]byte

MerkleHash defines the data structure for the leaves and root fo the merkle tree. TODO: merge chainhash.Hash and MerkleHash

func ComputeMerkleHash 

func ComputeMerkleHash(b []byte) *MerkleHash

ComputeMerkleHash returns its merkle hash.

func Hash 

func Hash(hash *MerkleHash, siblingHash *MerkleHash, pos byte) *MerkleHash

Hash returns the left(or right) child and it sibling's merkle hash.

func (*MerkleHash) Equal 

func (hash *MerkleHash) Equal(x *MerkleHash) bool

Equal returns whether x is length same and value same to hash.

func (*MerkleHash) IsEmptyHash 

func (hash *MerkleHash) IsEmptyHash() bool

IsEmptyHash check whether the merkle hash is empty.

func (MerkleHash) String 

func (hash MerkleHash) String() string

String returns the Hash as the hexadecimal string of the byte-reversed hash.

type MerklePath 

type MerklePath struct {
	// The first hash is the leaf hash. Rest of them are merkle proof.
	// Note. This slice should always have at least one item.
	Hashes []*MerkleHash
	// Path is an array of position, either left or right. Left = 0 and Right = 1
	ProofPath []byte
}

MerklePath is a series of merkle hash from a merkle leaf to merkle root.

func (*MerklePath) GetLeaf 

func (merklePath *MerklePath) GetLeaf() *MerkleHash

GetLeaf returns the leaf node of the merkle path.

func (*MerklePath) Verify 

func (merklePath *MerklePath) Verify(expectedHash *MerkleHash) error

Verify this merkle path's merkle root is same as expected hash.

type MerkleTree 

type MerkleTree struct {
	Size       int64
	MerkleRoot *MerkleHash
	// contains filtered or unexported fields
}

MerkleTree has an assumption that there's never two nodes have same hash value.

func (*MerkleTree) GetLastNodeHash 

func (merkleTree *MerkleTree) GetLastNodeHash() *MerkleHash

GetLastNodeHash returns the last node hash.

func (*MerkleTree) GetLastNodeMerklePath 

func (merkleTree *MerkleTree) GetLastNodeMerklePath() (*MerklePath, error)

GetLastNodeMerklePath returns the merkle path of the last node.

func (*MerkleTree) String 

func (merkleTree *MerkleTree) String(depth int) string

type RootHashMismatchError 

type RootHashMismatchError struct {
	ExpectedHash *MerkleHash
	ActualHash   *MerkleHash
}

RootHashMismatchError defines the detail of root hash mismatch error.

func (RootHashMismatchError) Error 

func (err RootHashMismatchError) Error() string

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.