merkle

package
v1.0.1 Latest Latest
Warning

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

 Go to latest Published: Mar 1, 2020 License: Apache-2.0 Imports: 12 Imported by: 4

Documentation

Index

Constants

View Source 
const (
	SectorSize = uint64(1 << 22)
	LeafSize   = 64
)

LeafSize is the data size stored in one merkle leaf. the original data will be divided into pieces based on the merkleRootSize, and then be pushed into the merkle tree

Variables

This section is empty.

Functions

func CheckDiffStorageProof 

func CheckDiffStorageProof(lh LeafRoot, leafNumber uint64, h hash.Hash, limits []SubTreeLimit, storageProofList [][]byte, root []byte) error

CheckDiffStorageProof verify that the merkle diff is stored from the specified leaf interval.

func CheckLimitStorageProof 

func CheckLimitStorageProof(lh LeafRoot, h hash.Hash, left, right int, storageProofList [][]byte, root []byte) (bool, error)

CheckLimitStorageProof check the proof list

func CheckStorageProof 

func CheckStorageProof(h hash.Hash, merkleRoot []byte, storageProofList [][]byte, storageProofIndex uint64, number uint64) bool

CheckStorageProof check the merkle tree

func GetDiffStorageProof 

func GetDiffStorageProof(limits []SubTreeLimit, h SubtreeRoot, leafNumber uint64) (storageProofList [][]byte, err error)

GetDiffStorageProof proof of storage of merkle diff from the specified leaf interval

func GetLimitStorageProof 

func GetLimitStorageProof(left, right int, h SubtreeRoot) (storageProofList [][]byte, err error)

GetLimitStorageProof get a proof of storage for a limit of subtrees

func LeavesCount 

func LeavesCount(dataSize uint64) (count uint64)

LeavesCount will count how many leaves a merkle tree has

func Sha256CachedTreeRoot 

func Sha256CachedTreeRoot(roots []common.Hash, height uint64) (root common.Hash)

Sha256CachedTreeRoot will return the root of the cached tree

func Sha256CachedTreeRoot2 

func Sha256CachedTreeRoot2(roots []common.Hash) (root common.Hash)

Sha256CachedTreeRoot2 will return the root of the cached tree

func Sha256DiffProof 

func Sha256DiffProof(roots []common.Hash, rangeSet []SubTreeLimit, leavesCount uint64) (hashProofSet []common.Hash, err error)

Sha256DiffProof is similar to Sha256SectorRangeProof, the only difference is that this function can provide multiple ranges

func Sha256MerkleTreeProof 

func Sha256MerkleTreeProof(data []byte, proofIndex uint64) (proofData []byte, hashProofSet []common.Hash, leavesCount uint64, err error)

Sha256MerkleTreeProof will return the hash proof set of the proof based on the data provided. proofData represents the data that needs to be hashed and combined with the data hashes in the proof set to check the integrity of the data

func Sha256MerkleTreeRoot 

func Sha256MerkleTreeRoot(b []byte) (h common.Hash)

Sha256MerkleTreeRoot will calculates the root of a data

func Sha256RangeProof 

func Sha256RangeProof(data []byte, proofStart, proofEnd int) (hashPoofSet []common.Hash, err error)

Sha256RangeProof will create the hashProofSet for the range of data provided NOTE: proofStart and proofEnd are measured in terms of merkle leaves (64), meaning data[proofStart * 64:proofEnd * 64]

func Sha256SectorRangeProof 

func Sha256SectorRangeProof(roots []common.Hash, proofStart, proofEnd int) (hashProofSet []common.Hash, err error)

Sha256SectorRangeProof is similar to Sha256RangeProof. The difference is that the latter one is used to create proof set for range within the data pieces, which is divided from the data sector. The former one is used to create proof set for range within data sectors in a collection of data sectors stored in the contract. roots represents the collection of data sectors

func Sha256VerifyDataPiece 

func Sha256VerifyDataPiece(dataPiece []byte, hashProofSet []common.Hash, numLeaves, proofIndex uint64, merkleRoot common.Hash) (verified bool)

Sha256VerifyDataPiece will verify if the data piece exists in the merkle tree

func Sha256VerifyDiffProof 

func Sha256VerifyDiffProof(rangeSet []SubTreeLimit, leavesCount uint64, hashProofSet, rootsVerify []common.Hash, merkleRoot common.Hash) (err error)

Sha256VerifyDiffProof is similar to Sha256VerifySectorRangeProof, the only difference is that this function can provide multiple ranges

func Sha256VerifyRangeProof 

func Sha256VerifyRangeProof(dataWithinRange []byte, hashProofSet []common.Hash, proofStart, proofEnd int, merkleRoot common.Hash) (verified bool, err error)

Sha256VerifyRangeProof will verify if the data within the range provided belongs to the merkle tree dataWithinRange = data[start:end]

func Sha256VerifySectorRangeProof 

func Sha256VerifySectorRangeProof(rootsVerify []common.Hash, hashProofSet []common.Hash, proofStart, proofEnd int, merkleRoot common.Hash) (verified bool, err error)

Sha256VerifySectorRangeProof is similar to Sha256VerifyRangeProof. The difference is that the latter one is used verify data pieces, which is divided from the data sector. The former one is used to verify data sectors in a collection of data sectors stored in the contract. roots represents the collection of data sectors. NOTE: Unlike the range proof, the data is not divided into pieces, therefore, the roots need to be provided will be roots[proofStart:proofEnd] == rootsVerify

Types

type CachedSubtreeRoot 

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

CachedSubtreeRoot implements SubtreeRoot.

func NewCachedSubtreeRoot 

func NewCachedSubtreeRoot(roots [][]byte, h hash.Hash) *CachedSubtreeRoot

NewCachedSubtreeRoot return cachedSubtreeRoot

func (*CachedSubtreeRoot) GetSubtreeRoot 

func (csh *CachedSubtreeRoot) GetSubtreeRoot(leafIndex int) ([]byte, error)

GetSubtreeRoot implements SubtreeRoot.

func (*CachedSubtreeRoot) Skip 

func (csh *CachedSubtreeRoot) Skip(n int) error

Skip implements SubtreeRoot.

type CachedTree 

type CachedTree struct {
	Tree
	// contains filtered or unexported fields
}

CachedTree will store the leaf's data data instead of hash

func NewCachedTree 

func NewCachedTree(h hash.Hash, height uint64) *CachedTree

NewCachedTree return a cachedTree

func (*CachedTree) ProofList 

func (ct *CachedTree) ProofList(cachedTreeProofList [][]byte) (merkleRoot []byte, proofList [][]byte, storageProofIndex uint64, numLeaves uint64)

ProofList construct a storage proof result set for the cached tree that has established the storage proof index

func (*CachedTree) SetStorageProofIndex 

func (ct *CachedTree) SetStorageProofIndex(i uint64) error

SetStorageProofIndex must be called on an empty tree.

type LeafRoot 

type LeafRoot interface {
	//GetLeafRoot get the hash of the leaf node
	GetLeafRoot() ([]byte, error)
}

LeafRoot get root

type LeafRootCached 

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

LeafRootCached roots

func NewLeafRootCached 

func NewLeafRootCached(leafHashes [][]byte) *LeafRootCached

NewLeafRootCached return LeafRootCached

func (*LeafRootCached) GetLeafRoot 

func (clh *LeafRootCached) GetLeafRoot() ([]byte, error)

GetLeafRoot implements LeafRoot.

type LeafRootReader 

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

LeafRootReader read

func NewLeafRootReader 

func NewLeafRootReader(r io.Reader, h hash.Hash, leafSize int) *LeafRootReader

NewLeafRootReader return LeafRootReader

func (*LeafRootReader) GetLeafRoot 

func (rlh *LeafRootReader) GetLeafRoot() ([]byte, error)

GetLeafRoot implements LeafRoot.

type Sha256CachedTree 

type Sha256CachedTree struct {
	CachedTree
}

Sha256CachedTree is similar to Sha256MerkleTree, one obvious difference between them is that cached merkle tree will not hash the data before inserting them into the tree

func NewSha256CachedTree 

func NewSha256CachedTree(height uint64) (ct *Sha256CachedTree)

NewSha256CachedTree will create a Sha256CachedTree object with sha256 as hashing method.

func (*Sha256CachedTree) Prove 

func (ct *Sha256CachedTree) Prove(proofData []byte, cachedHashProofSet []common.Hash) (hashProofSet []common.Hash)

Prove will be used to generate a storage proof hash set, which is used in storage responsibility to submit the storageProof. The data field gives user more freedom to choose which data they want to do merkle proof with

func (*Sha256CachedTree) Push 

func (ct *Sha256CachedTree) Push(h common.Hash)

Push will push the data into the merkle tree

func (*Sha256CachedTree) PushSubTree 

func (ct *Sha256CachedTree) PushSubTree(height int, h common.Hash) (err error)

PushSubTree will insert a sub merkle tree and trying to combine it with other data

func (*Sha256CachedTree) Root 

func (ct *Sha256CachedTree) Root() (h common.Hash)

Root will return the merkle root of the Sha256CachedTree

type Sha256MerkleTree 

type Sha256MerkleTree struct {
	Tree
}

Sha256MerkleTree serves as a wrapper of the merkle tree, provide a convenient way to access methods associated with the merkle tree

func NewSha256MerkleTree 

func NewSha256MerkleTree() (mk *Sha256MerkleTree)

NewSha256MerkleTree will initialize a Sha256MerkleTree object with sha256 as the hashing method

func (*Sha256MerkleTree) Root 

func (mt *Sha256MerkleTree) Root() (h common.Hash)

Root will calculate and return the merkle root of the merkle tree

type SubTreeLimit 

type SubTreeLimit struct {
	Left  uint64
	Right uint64
}

SubTreeLimit range of intervals

type SubtreeRoot 

type SubtreeRoot interface {

	//GetSubtreeRoot get the root hash of the subtree of n leaf node combinations
	GetSubtreeRoot(n int) ([]byte, error)

	//Skip skip the subtree of n leaf node combinations
	Skip(n int) error
}

SubtreeRoot get the root hash

type SubtreeRootReader 

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

SubtreeRootReader implements SubtreeRoot.

func NewSubtreeRootReader 

func NewSubtreeRootReader(r io.Reader, leafNumber int, h hash.Hash) *SubtreeRootReader

NewSubtreeRootReader return SubtreeRootReader

func (*SubtreeRootReader) GetSubtreeRoot 

func (rsh *SubtreeRootReader) GetSubtreeRoot(leafIndex int) ([]byte, error)

GetSubtreeRoot implements SubtreeRoot.

func (*SubtreeRootReader) Skip 

func (rsh *SubtreeRootReader) Skip(n int) (err error)

Skip implements SubtreeRoot.

type Tree 

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

Tree the most basic structure of the merkle tree

func NewTree 

func NewTree(h hash.Hash) *Tree

NewTree return a tree

func (*Tree) ProofList 

func (t *Tree) ProofList() (merkleRoot []byte, storageProofList [][]byte, storageProofIndex uint64, numLeaves uint64)

ProofList construct a storage proof result set for the merkle tree that has established the storage proof index

func (*Tree) PushLeaf 

func (t *Tree) PushLeaf(data []byte)

PushLeaf the tree only saves the subtrees needed to calculate the merkle root. the process of the push will also include the path required for the storage certificate.

func (*Tree) PushSubTree 

func (t *Tree) PushSubTree(height int, sum []byte) error

PushSubTree there is no way to judge whether the inserted subtree is a balanced tree, which will bring unknown danger.

func (*Tree) Root 

func (t *Tree) Root() []byte

Root traverse all subtrees and calculate the sum of the hashes

func (*Tree) SetStorageProofIndex 

func (t *Tree) SetStorageProofIndex(i uint64) error

SetStorageProofIndex must be called on an empty tree.

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.