ipld

package
v0.13.4 Latest Latest
Warning

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

 Go to latest Published: Apr 21, 2024 License: Apache-2.0 Imports: 32 Imported by: 0

Documentation

Index

Constants

View Source 
const (

	// NmtHashSize is the size of a digest created by an NMT in bytes.
	NmtHashSize = 2*share.NamespaceSize + sha256.Size

	// NMTIgnoreMaxNamespace is currently used value for IgnoreMaxNamespace option in NMT.
	// IgnoreMaxNamespace defines whether the largest possible Namespace MAX_NID should be 'ignored'.
	// If set to true, this allows for shorter proofs in particular use-cases.
	NMTIgnoreMaxNamespace = true
)

Variables

View Source 
var ErrNamespaceOutsideRange = errors.New("share/ipld: " +
	"target namespace is outside of namespace range for the given root")
View Source 
var ErrNodeNotFound = errors.New("nmt node not found")

ErrNodeNotFound is used to signal when a nmt Node could not be found.

View Source 
var NumConcurrentSquares = 8

NumConcurrentSquares limits the amount of squares that are fetched concurrently/simultaneously.

View Source 
var NumWorkersLimit = share.MaxSquareSize * share.MaxSquareSize / 2 * NumConcurrentSquares

NumWorkersLimit sets global limit for workers spawned by GetShares. GetShares could be called MaxSquareSize(128) times per data square each spawning up to 128/2 goroutines and altogether this is 8192. Considering there can be N blocks fetched at the same time, e.g. during catching up data from the past, we multiply this number by the amount of allowed concurrent data square fetches(NumConcurrentSquares).

NOTE: This value only limits amount of simultaneously running workers that are spawned as the load increases and are killed, once the load declines.

TODO(@Wondertan): This assumes we have parallelized DASer implemented. Sync the values once it is shipped. TODO(@Wondertan): Allow configuration of values without global state.

Functions

func AddShares added in v0.11.0 

func AddShares(
	ctx context.Context,
	shares []share.Share,
	adder blockservice.BlockService,
) (*rsmt2d.ExtendedDataSquare, error)

AddShares erasures and extends shares to blockservice.BlockService using the provided ipld.NodeAdder.

func BatchSize 

func BatchSize(squareSize int) int

BatchSize calculates the amount of nodes that are generated from block of 'squareSizes' to be batched in one write.

func CidFromNamespacedSha256 

func CidFromNamespacedSha256(namespacedHash []byte) (cid.Cid, error)

CidFromNamespacedSha256 uses a hash from an nmt tree to create a CID

func CtxWithProofsAdder added in v0.11.0 

func CtxWithProofsAdder(ctx context.Context, adder *ProofsAdder) context.Context

CtxWithProofsAdder creates context, that will contain ProofsAdder. If context is leaked to another go-routine, proofs will be not collected by gc. To prevent it, use Purge after Proofs are collected from adder, to preemptively release memory allocated for proofs.

func FilterRootByNamespace added in v0.11.0 

func FilterRootByNamespace(root *share.Root, namespace share.Namespace) []cid.Cid

FilterRootByNamespace returns the row roots from the given share.Root that contain the namespace.

func GetLeaf 

func GetLeaf(
	ctx context.Context,
	bGetter blockservice.BlockGetter,
	root cid.Cid,
	leaf, total int,
) (ipld.Node, error)

GetLeaf fetches and returns the raw leaf. It walks down the IPLD NMT tree until it finds the requested one.

func GetLeaves 

func GetLeaves(ctx context.Context,
	bGetter blockservice.BlockGetter,
	root cid.Cid,
	maxShares int,
	put func(int, ipld.Node),
)

GetLeaves gets leaves from either local storage, or, if not found, requests them from immediate/connected peers. It puts them into the slice under index of node position in the tree (bin-tree-feat). Does not return any error, and returns/unblocks only on success (got all shares) or on context cancellation.

It works concurrently by spawning workers in the pool which do one basic thing - block until data is fetched, s. t. share processing is never sequential, and thus we request *all* the shares available without waiting for others to finish. It is the required property to maximize data availability. As a side effect, we get concurrent tree traversal reducing time to data time.

GetLeaves relies on the fact that the underlying data structure is a binary tree, so it's not suitable for anything else besides that. Parts on the implementation that rely on this property are explicitly tagged with (bin-tree-feat).

func GetNode 

func GetNode(ctx context.Context, bGetter blockservice.BlockGetter, root cid.Cid) (ipld.Node, error)

func GetProof 

func GetProof(
	ctx context.Context,
	bGetter blockservice.BlockGetter,
	root cid.Cid,
	proof []cid.Cid,
	leaf, total int,
) ([]cid.Cid, error)

GetProof fetches and returns the leaf's Merkle Proof. It walks down the IPLD NMT tree until it reaches the leaf and returns collected proof

func GetShare added in v0.11.0 

func GetShare(
	ctx context.Context,
	bGetter blockservice.BlockGetter,
	rootCid cid.Cid,
	leafIndex int,
	totalLeafs int,
) (share.Share, error)

GetShare fetches and returns the data for leaf `leafIndex` of root `rootCid`.

func GetShares added in v0.11.0 

func GetShares(ctx context.Context, bg blockservice.BlockGetter, root cid.Cid, shares int, put func(int, share.Share))

GetShares walks the tree of a given root and puts shares into the given 'put' func. Does not return any error, and returns/unblocks only on success (got all shares) or on context cancellation.

func GetSharesByNamespace added in v0.11.0 

func GetSharesByNamespace(
	ctx context.Context,
	bGetter blockservice.BlockGetter,
	root cid.Cid,
	namespace share.Namespace,
	maxShares int,
) ([]share.Share, *nmt.Proof, error)

GetSharesByNamespace walks the tree of a given root and returns its shares within the given Namespace. If a share could not be retrieved, err is not nil, and the returned array contains nil shares in place of the shares it was unable to retrieve.

func ImportEDS added in v0.11.0 

func ImportEDS(ctx context.Context, square *rsmt2d.ExtendedDataSquare, adder blockservice.BlockService) error

func ImportShares added in v0.11.0 

func ImportShares(
	ctx context.Context,
	shares [][]byte,
	adder blockservice.BlockService,
) (*rsmt2d.ExtendedDataSquare, error)

ImportShares imports flattened pieces of data into Extended Data square and saves it in blockservice.BlockService

func MaxSizeBatchOption 

func MaxSizeBatchOption(size int) ipld.BatchOption

MaxSizeBatchOption sets the maximum amount of buffered data before writing blocks.

func MustCidFromNamespacedSha256 

func MustCidFromNamespacedSha256(hash []byte) cid.Cid

MustCidFromNamespacedSha256 is a wrapper around cidFromNamespacedSha256 that panics in case of an error. Use with care and only in places where no error should occur.

func NamespacedSha256FromCID 

func NamespacedSha256FromCID(cid cid.Cid) []byte

NamespacedSha256FromCID derives the Namespaced hash from the given CID.

func NewBlockservice added in v0.11.0 

func NewBlockservice(bs blockstore.Blockstore, exchange exchange.Interface) blockservice.BlockService

NewBlockservice constructs Blockservice for fetching NMTrees.

func NewMemBlockservice added in v0.11.0 

func NewMemBlockservice() blockservice.BlockService

NewMemBlockservice constructs Blockservice for fetching NMTrees with in-memory blockstore.

func RandNamespacedCID 

func RandNamespacedCID(t *testing.T) cid.Cid

func Translate 

func Translate(dah *da.DataAvailabilityHeader, row, col int) (cid.Cid, int)

Translate transforms square coordinates into IPLD NMT tree path to a leaf node. It also adds randomization to evenly spread fetching from Rows and Columns.

Types

type NamespaceData added in v0.8.0 

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

NamespaceData stores all leaves under the given namespace with their corresponding proofs.

func NewNamespaceData added in v0.8.0 

func NewNamespaceData(maxShares int, namespace share.Namespace, options ...Option) *NamespaceData

func (*NamespaceData) CollectLeavesByNamespace added in v0.8.0 

func (n *NamespaceData) CollectLeavesByNamespace(
	ctx context.Context,
	bGetter blockservice.BlockGetter,
	root cid.Cid,
) error

CollectLeavesByNamespace collects leaves and corresponding proof that could be used to verify leaves inclusion. It returns as many leaves from the given root with the given Namespace as it can retrieve. If no shares are found, it returns error as nil. A non-nil error means that only partial data is returned, because at least one share retrieval failed. The following implementation is based on `GetShares`.

func (*NamespaceData) Leaves added in v0.8.0 

func (n *NamespaceData) Leaves() []ipld.Node

Leaves returns retrieved leaves within the bounds in case `WithLeaves` option was passed, otherwise nil will be returned.

func (*NamespaceData) Proof added in v0.8.0 

func (n *NamespaceData) Proof() *nmt.Proof

Proof returns proofs within the bounds in case if `WithProofs` option was passed, otherwise nil will be returned.

type NmtNodeAdder 

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

NmtNodeAdder adds ipld.Nodes to the underlying ipld.Batch if it is inserted into a nmt tree.

func NewNmtNodeAdder 

func NewNmtNodeAdder(ctx context.Context, bs blockservice.BlockService, opts ...ipld.BatchOption) *NmtNodeAdder

NewNmtNodeAdder returns a new NmtNodeAdder with the provided context and batch. Note that the context provided should have a timeout It is not thread-safe.

func (*NmtNodeAdder) Commit 

func (n *NmtNodeAdder) Commit() error

Commit checks for errors happened during Visit and if absent commits data to inner Batch.

func (*NmtNodeAdder) Visit 

func (n *NmtNodeAdder) Visit(hash []byte, children ...[]byte)

Visit is a NodeVisitor that can be used during the creation of a new NMT to create and add ipld.Nodes to the Batch while computing the root of the NMT.

type Option added in v0.8.0 

type Option func(*NamespaceData)

Option is the functional option that is applied to the NamespaceData instance to configure data that needs to be stored.

func WithLeaves added in v0.8.0 

func WithLeaves() Option

WithLeaves option specifies that leaves should be collected during retrieval.

func WithProofs added in v0.8.0 

func WithProofs() Option

WithProofs option specifies that proofs should be collected during retrieval.

type ProofsAdder added in v0.11.0 

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

ProofsAdder is used to collect proof nodes, while traversing merkle tree

func NewProofsAdder added in v0.11.0 

func NewProofsAdder(squareSize int) *ProofsAdder

NewProofsAdder creates new instance of ProofsAdder.

func ProofsAdderFromCtx added in v0.11.0 

func ProofsAdderFromCtx(ctx context.Context) *ProofsAdder

ProofsAdderFromCtx extracts ProofsAdder from context

func (*ProofsAdder) Proofs added in v0.11.0 

func (a *ProofsAdder) Proofs() map[cid.Cid][]byte

Proofs returns proofs collected by ProofsAdder

func (*ProofsAdder) Purge added in v0.11.0 

func (a *ProofsAdder) Purge()

Purge removed proofs from ProofsAdder allowing GC to collect the memory

func (*ProofsAdder) VisitFn added in v0.11.0 

func (a *ProofsAdder) VisitFn() nmt.NodeVisitorFn

VisitFn returns NodeVisitorFn, that will collect proof nodes while traversing merkle 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.