merkle

Documentation

Overview

Package merkle provides Sia-specific Merkle tree utilities.

Index

• Constants
• func BuildDiffProof(actions []renterhost.RPCWriteAction, sectorRoots []crypto.Hash) (treeHashes, leafHashes []crypto.Hash)
• func BuildProof(sector *[renterhost.SectorSize]byte, start, end int, ...) []crypto.Hash
• func BuildSectorRangeProof(sectorRoots []crypto.Hash, start, end int) []crypto.Hash
• func ConvertProofOrdering(proof []crypto.Hash, index int) []crypto.Hash
• func DiffProofSize(actions []renterhost.RPCWriteAction, numLeaves int) int
• func MetaRoot(roots []crypto.Hash) crypto.Hash
• func PrecomputeAppendRoots(actions []renterhost.RPCWriteAction) []crypto.Hash
• func ProofSize(n, start, end int) int
• func ReaderRoot(r io.Reader) (crypto.Hash, error)
• func SectorRoot(sector *[renterhost.SectorSize]byte) crypto.Hash
• func VerifyDiffProof(actions []renterhost.RPCWriteAction, numLeaves int, ...) bool
• func VerifyProof(proof []crypto.Hash, segments []byte, start, end int, root crypto.Hash) bool
• func VerifySectorRangeProof(proof []crypto.Hash, rangeRoots []crypto.Hash, start, end, numRoots int, ...) bool
• type RangeProofVerifier
  • func NewRangeProofVerifier(start, end int) *RangeProofVerifier
  • func (rpv *RangeProofVerifier) ReadFrom(r io.Reader) (int64, error)
  • func (rpv *RangeProofVerifier) Verify(proof []crypto.Hash, root crypto.Hash) bool

Constants

const (
	// SegmentSize is the number of bytes in each leaf node of a sector's Merkle
	// tree. Although "LeafSize" would be a more accurate term, Sia refers to
	// leaves as "segments", so we will follow suit.
	SegmentSize = crypto.HashSize * 2

	// SegmentsPerSector is a convenience value.
	SegmentsPerSector = renterhost.SectorSize / SegmentSize
)

Functions

func BuildDiffProof

func BuildDiffProof(actions []renterhost.RPCWriteAction, sectorRoots []crypto.Hash) (treeHashes, leafHashes []crypto.Hash)

BuildDiffProof constructs a diff proof for the specified actions. ActionUpdate is not supported.

func BuildProof

func BuildProof(sector *[renterhost.SectorSize]byte, start, end int, precalc func(i, j int) crypto.Hash) []crypto.Hash

BuildProof constructs a proof for the segment range [start, end). If a non- nil precalc function is provided, it will be used to supply precalculated subtree Merkle roots. For example, if the root of the left half of the Merkle tree is precomputed, precalc should return it for i == 0 and j == SegmentsPerSector/2. If a precalculated root is not available, precalc should return the zero hash.

func BuildSectorRangeProof

func BuildSectorRangeProof(sectorRoots []crypto.Hash, start, end int) []crypto.Hash

BuildSectorRangeProof constructs a proof for the sector range [start, end).

func ConvertProofOrdering

func ConvertProofOrdering(proof []crypto.Hash, index int) []crypto.Hash

ConvertProofOrdering converts "left-to-right" proofs into the "leaf-to-root" ordering used in consensus storage proofs.

func DiffProofSize

func DiffProofSize(actions []renterhost.RPCWriteAction, numLeaves int) int

DiffProofSize returns the size of a diff proof for the specified actions.

func MetaRoot

func MetaRoot(roots []crypto.Hash) crypto.Hash

MetaRoot calculates the root of a set of existing Merkle roots.

func PrecomputeAppendRoots

func PrecomputeAppendRoots(actions []renterhost.RPCWriteAction) []crypto.Hash

PrecomputeAppendRoots computes the SectorRoots of any Append actions in the provided slice.

func ProofSize

func ProofSize(n, start, end int) int

ProofSize returns the size of a Merkle proof for the leaf range [start, end) within a tree containing n leaves.

func ReaderRoot

func ReaderRoot(r io.Reader) (crypto.Hash, error)

ReaderRoot returns the Merkle root of the supplied stream, which must contain an integer multiple of segments.

func SectorRoot

func SectorRoot(sector *[renterhost.SectorSize]byte) crypto.Hash

SectorRoot computes the Merkle root of a sector using SegmentSize bytes per leaf.

func VerifyDiffProof

func VerifyDiffProof(actions []renterhost.RPCWriteAction, numLeaves int, treeHashes, leafHashes []crypto.Hash, oldRoot, newRoot crypto.Hash, appendRoots []crypto.Hash) bool

VerifyDiffProof verifies a proof produced by BuildDiffProof. ActionUpdate is not supported. If appendRoots is non-nil, it is assumed to contain the precomputed SectorRoots of all Append actions.

func VerifyProof

func VerifyProof(proof []crypto.Hash, segments []byte, start, end int, root crypto.Hash) bool

VerifyProof verifies a proof produced by BuildProof. Only sector-sized proofs can be verified.

func VerifySectorRangeProof

func VerifySectorRangeProof(proof []crypto.Hash, rangeRoots []crypto.Hash, start, end, numRoots int, root crypto.Hash) bool

VerifySectorRangeProof verifies a proof produced by BuildSectorRangeProof.

Types

type RangeProofVerifier

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

A RangeProofVerifier allows for proofs to be verified in streaming fashion.

func NewRangeProofVerifier

func NewRangeProofVerifier(start, end int) *RangeProofVerifier

NewRangeProofVerifier returns a RangeProofVerifier for the sector range [start, end).

func (*RangeProofVerifier) ReadFrom

func (rpv *RangeProofVerifier) ReadFrom(r io.Reader) (int64, error)

ReadFrom implements io.ReaderFrom.

func (*RangeProofVerifier) Verify

func (rpv *RangeProofVerifier) Verify(proof []crypto.Hash, root crypto.Hash) bool

Verify verifies the supplied proof, using the data ingested from ReadFrom.