proof

package
v2.0.0-rc1 Latest Latest
Warning

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

 Go to latest Published: May 17, 2024 License: Apache-2.0 Imports: 22 Imported by: 0

README

Proof

This package enables proof queries for Celestia transactions and blobs.

Prerequisites

To understand the proof mechanisms, a good understanding of binary merkle proofs and namespace merkle proofs is required.

PFB transaction

When creating a PayForBlob transaction, the blob data is separated into a set of shares. This set of shares is used to generate a share commitment which commits to the data contained in the PFB, i.e., the blob.

Share commitment generation

Generating a share commitment starts with laying the shares into a merkle mountain range structure. For example, if the blob contains six shares, the following structure will be generated:

subtree roots generation from shares

The blob shares are colored in orange, and are used to generate a set of roots following the merkle mountain range structure. These roots are called subtree roots. In the above case, we end up with two subtree roots: SR1 and SR2.

Then, these subtree roots are used to generate the share commitment:

share commitment generation from subtree roots

The share commitment is the binary merkle root over the set of subtree roots generated from the shares.

Share to share commitment inclusion

Using the above merkle trees, share proofs can be generated to prove inclusion of a set of shares to the share commitment.

For instance, if we want to prove the first two shares, we will need two merkle proofs:

shares to share commitment inclusion proof
  • The first merkle proof is a namespace merkle inclusion proof from the first two shares to the subtree root SR1.
  • The second merkle proof is a binary merkle inclusion proof from SR1, which is the subtree root committing to the shares, to the share commitment.

Note: the nodes colored in red are the inner nodes used to construct the inclusion proof.

Square layout

Now that the share commitment is generated, the transaction gets broadcast to the Celestia network to be picked up by validators. Once it's included in a block, the transaction, without the blob, is placed in the transaction namespace and the blob is placed in the namespace specified in the PFB transaction.

If we use the same transaction from above, where the blob consists of six shares, an example Celestia square containing the blob and the PFB transaction can look like this:

celestia extended square containing the blob shares

The share range [5, 10], colored in orange, is the blob data.

Row roots

To compute the Celestia block data root, we first start by computing the row roots and column roots.

For instance, if we want to compute the first row root:

row root one generation

We use the first row of shares to generate a namespace merkle root. The first four shares, i.e., the shares [1, 4] are part of the square data, and the last four are parity shares.

Now if we take the second row, which contains four shares of the above blob [5,8]:

row root two generation

The inner node in purple is the same as the subtree root SR1 generated in the PFB transaction section.

Similarly, if we generate the third row, which contains the remaining two shares of the blob, and some other data:

row root three generation

We will see that the subtree root SR2 is an inner node of the tree used to compute the third row root.

This property holds for all the subtree roots computed for the blob data and is derived from applying Blob Share Commitment Rules when constructing the square. This means that it is possible to prove the inclusion of a blob to a set of row roots using the generated share commitment. The subtree roots used to generate it will be the same regardless of the square size. This proof will be discussed in the prove share commitment inclusion to data root section.

Column roots

Similar to row roots, column roots are the namespace merkle root of the set of shares contained in the column:

column root one generation

Generally, the column roots are only used for bad encoding fraud proofs, BEFP and won't be used concretely in inclusion proofs. They're only mentioned for completeness.

Data root

The Celestia block data root is computed by generating a binary merkle root over the set of row roots and column roots of the square:

data root generation

This allows inclusion proofs of the shares to the data root which will be discussed below.

Inclusion proof

Share to data root inclusion proof

To prove that a share was included in a Celestia block, we can create an inclusion proof from the share to the data root. This proof consists of the following:

Share to row root namespace merkle inclusion proof

First, we prove inclusion of the share in question to the row root it belongs to. If we take, for example, share three, its inclusion proof can be constructed using the inner nodes in red:

share to row root proof

Now, if we have this inclusion proof, and we verify it against the RowRoot1, the proof would be valid.

Row root to data root inclusion proof

Now that we proved the share to the row root, we will need to complete the proof with a row root to the data root inclusion proof. This means that we will be proving that the row root commits to the share, and the data root commits to the row root. Since share three is committed to by RowRoot1, we will be proving that row root to the data root.

row root to data root proof

The inner nodes in red are the nodes needed to construct the merkle inclusion proof.

So, if we have access to these two proofs, the share to row root inclusion proof and row root to data root inclusion proof, we can successfully prove inclusion of share three to the Celestia data root.

Prove share commitment inclusion to data root

To prove that a blob, referenced by its share commitment, was included in a Celestia block, we need the following proofs:

Subtree roots inclusion proof to the data root

As we've seen in the row roots generation section, the subtree roots are inner nodes of the namespace merkle tree used to generate the row root. This means that it's possible to create an inclusion proof of a subtree root to the row root:

subtree root to row root proof

The inner nodes in brown would be used to construct the SR2 node inclusion proof to the RowRoot3.

After having this proof, we will need to prove the RowRoot3 inclusion to the data root. This is described in the row root to data root inclusion proof section.

With this, we would be able to prove that SR2 was committed to by a Celestia data root.

Subtree roots inclusion proof to the share commitment

Now that we can prove SR2 inclusion to RowRoot3, what's left is proving that SR2 was committed to by the share commitment.

Proving inclusion of SR1 or SR2 to the share commitment goes back to creating a binary merkle inclusion proof to the share commitment:

share commitment generation from subtree roots

So, if we manage to prove that SR1 and SR2 were both committed to by the Celestia data root, and that the share commitment was generated using SR1 and SR2, then, we would have proven that the share commitment was committed to by the Celestia data root, which means that the blob data that generated the share commitment was included in a Celestia block.

[IMPORTANT] As of the current version, the API for generating and verifying share commitment proofs to data root is still not exposed. These proofs are only used as part of the Celestia consensus internally.

PFB proofs

More compact proofs can be generated to prove inclusion of a blob in a Celestia square, but are out of the scope of this document. More details can be found in ADR-011.

Documentation

Index

Constants

View Source 
const ShareInclusionQueryPath = "shareInclusionProof"
View Source 
const TxInclusionQueryPath = "txInclusionProof"

Variables

View Source 
var (
	ErrInvalidLengthProof        = fmt.Errorf("proto: negative length found during unmarshaling")
	ErrIntOverflowProof          = fmt.Errorf("proto: integer overflow")
	ErrUnexpectedEndOfGroupProof = fmt.Errorf("proto: unexpected end of group")
)

Functions

func ParseNamespace 

func ParseNamespace(rawShares []shares.Share, startShare int, endShare int) (appns.Namespace, error)

ParseNamespace validates the share range, checks if it only contains one namespace and returns that namespace ID.

func QueryShareInclusionProof 

func QueryShareInclusionProof(_ sdk.Context, path []string, req abci.RequestQuery) ([]byte, error)

QueryShareInclusionProof defines the logic performed when querying for the inclusion proofs of a set of shares to the data root. The share range should be appended to the path. Example path for proving the set of shares [3, 5]: custom/shareInclusionProof/3/5

func QueryTxInclusionProof 

func QueryTxInclusionProof(_ sdk.Context, path []string, req abci.RequestQuery) ([]byte, error)

Querier defines the logic performed when the ABCI client using the Query method with the custom prove.QueryPath. The index of the transaction being proved must be appended to the path. The marshalled bytes of the transaction proof (tmproto.ShareProof) are returned.

example path for proving the third transaction in that block: custom/txInclusionProof/3

Types

type NMTProof 

type NMTProof struct {
	// Start index of this proof.
	Start int32 `protobuf:"varint,1,opt,name=start,proto3" json:"start,omitempty"`
	// End index of this proof.
	End int32 `protobuf:"varint,2,opt,name=end,proto3" json:"end,omitempty"`
	// Nodes that together with the corresponding leaf values can be used to
	// recompute the root and verify this proof. Nodes should consist of the max
	// and min namespaces along with the actual hash, resulting in each being 48
	// bytes each
	Nodes [][]byte `protobuf:"bytes,3,rep,name=nodes,proto3" json:"nodes,omitempty"`
	// leafHash are nil if the namespace is present in the NMT. In case the
	// namespace to be proved is in the min/max range of the tree but absent, this
	// will contain the leaf hash necessary to verify the proof of absence. Leaf
	// hashes should consist of the namespace along with the actual hash,
	// resulting 40 bytes total.
	LeafHash []byte `protobuf:"bytes,4,opt,name=leaf_hash,json=leafHash,proto3" json:"leaf_hash,omitempty"`
}

NMTProof is a proof of a namespace.ID in an NMT. In case this proof proves the absence of a namespace.ID in a tree it also contains the leaf hashes of the range where that namespace would be.

func (*NMTProof) Descriptor 

func (*NMTProof) Descriptor() ([]byte, []int)

func (*NMTProof) GetEnd 

func (m *NMTProof) GetEnd() int32

func (*NMTProof) GetLeafHash 

func (m *NMTProof) GetLeafHash() []byte

func (*NMTProof) GetNodes 

func (m *NMTProof) GetNodes() [][]byte

func (*NMTProof) GetStart 

func (m *NMTProof) GetStart() int32

func (*NMTProof) Marshal 

func (m *NMTProof) Marshal() (dAtA []byte, err error)

func (*NMTProof) MarshalTo 

func (m *NMTProof) MarshalTo(dAtA []byte) (int, error)

func (*NMTProof) MarshalToSizedBuffer 

func (m *NMTProof) MarshalToSizedBuffer(dAtA []byte) (int, error)

func (*NMTProof) ProtoMessage 

func (*NMTProof) ProtoMessage()

func (*NMTProof) Reset 

func (m *NMTProof) Reset()

func (*NMTProof) Size 

func (m *NMTProof) Size() (n int)

func (*NMTProof) String 

func (m *NMTProof) String() string

func (*NMTProof) Unmarshal 

func (m *NMTProof) Unmarshal(dAtA []byte) error

func (*NMTProof) XXX_DiscardUnknown 

func (m *NMTProof) XXX_DiscardUnknown()

func (*NMTProof) XXX_Marshal 

func (m *NMTProof) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*NMTProof) XXX_Merge 

func (m *NMTProof) XXX_Merge(src proto.Message)

func (*NMTProof) XXX_Size 

func (m *NMTProof) XXX_Size() int

func (*NMTProof) XXX_Unmarshal 

func (m *NMTProof) XXX_Unmarshal(b []byte) error

type Proof 

type Proof struct {
	Total    int64    `protobuf:"varint,1,opt,name=total,proto3" json:"total,omitempty"`
	Index    int64    `protobuf:"varint,2,opt,name=index,proto3" json:"index,omitempty"`
	LeafHash []byte   `protobuf:"bytes,3,opt,name=leaf_hash,json=leafHash,proto3" json:"leaf_hash,omitempty"`
	Aunts    [][]byte `protobuf:"bytes,4,rep,name=aunts,proto3" json:"aunts,omitempty"`
}

Proof is taken from the merkle package

func (*Proof) Descriptor 

func (*Proof) Descriptor() ([]byte, []int)

func (*Proof) GetAunts 

func (m *Proof) GetAunts() [][]byte

func (*Proof) GetIndex 

func (m *Proof) GetIndex() int64

func (*Proof) GetLeafHash 

func (m *Proof) GetLeafHash() []byte

func (*Proof) GetTotal 

func (m *Proof) GetTotal() int64

func (*Proof) Marshal 

func (m *Proof) Marshal() (dAtA []byte, err error)

func (*Proof) MarshalTo 

func (m *Proof) MarshalTo(dAtA []byte) (int, error)

func (*Proof) MarshalToSizedBuffer 

func (m *Proof) MarshalToSizedBuffer(dAtA []byte) (int, error)

func (*Proof) ProtoMessage 

func (*Proof) ProtoMessage()

func (*Proof) Reset 

func (m *Proof) Reset()

func (*Proof) Size 

func (m *Proof) Size() (n int)

func (*Proof) String 

func (m *Proof) String() string

func (*Proof) Unmarshal 

func (m *Proof) Unmarshal(dAtA []byte) error

func (*Proof) Verify 

func (p *Proof) Verify(rootHash []byte, leaf []byte) error

func (*Proof) XXX_DiscardUnknown 

func (m *Proof) XXX_DiscardUnknown()

func (*Proof) XXX_Marshal 

func (m *Proof) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*Proof) XXX_Merge 

func (m *Proof) XXX_Merge(src proto.Message)

func (*Proof) XXX_Size 

func (m *Proof) XXX_Size() int

func (*Proof) XXX_Unmarshal 

func (m *Proof) XXX_Unmarshal(b []byte) error

type RowProof 

type RowProof struct {
	RowRoots [][]byte `protobuf:"bytes,1,rep,name=row_roots,json=rowRoots,proto3" json:"row_roots,omitempty"`
	Proofs   []*Proof `protobuf:"bytes,2,rep,name=proofs,proto3" json:"proofs,omitempty"`
	Root     []byte   `protobuf:"bytes,3,opt,name=root,proto3" json:"root,omitempty"`
	StartRow uint32   `protobuf:"varint,4,opt,name=start_row,json=startRow,proto3" json:"start_row,omitempty"`
	EndRow   uint32   `protobuf:"varint,5,opt,name=end_row,json=endRow,proto3" json:"end_row,omitempty"`
}

RowProof is a Merkle proof that a set of rows exist in a Merkle tree with a given data root.

func (*RowProof) Descriptor 

func (*RowProof) Descriptor() ([]byte, []int)

func (*RowProof) GetEndRow 

func (m *RowProof) GetEndRow() uint32

func (*RowProof) GetProofs 

func (m *RowProof) GetProofs() []*Proof

func (*RowProof) GetRoot 

func (m *RowProof) GetRoot() []byte

func (*RowProof) GetRowRoots 

func (m *RowProof) GetRowRoots() [][]byte

func (*RowProof) GetStartRow 

func (m *RowProof) GetStartRow() uint32

func (*RowProof) Marshal 

func (m *RowProof) Marshal() (dAtA []byte, err error)

func (*RowProof) MarshalTo 

func (m *RowProof) MarshalTo(dAtA []byte) (int, error)

func (*RowProof) MarshalToSizedBuffer 

func (m *RowProof) MarshalToSizedBuffer(dAtA []byte) (int, error)

func (*RowProof) ProtoMessage 

func (*RowProof) ProtoMessage()

func (*RowProof) Reset 

func (m *RowProof) Reset()

func (*RowProof) Size 

func (m *RowProof) Size() (n int)

func (*RowProof) String 

func (m *RowProof) String() string

func (*RowProof) Unmarshal 

func (m *RowProof) Unmarshal(dAtA []byte) error

func (RowProof) Validate 

func (rp RowProof) Validate(root []byte) error

Validate performs checks on the fields of this RowProof. Returns an error if the proof fails validation. If the proof passes validation, this function attempts to verify the proof. It returns nil if the proof is valid.

func (RowProof) VerifyProof 

func (rp RowProof) VerifyProof(root []byte) bool

VerifyProof verifies that all the row roots in this RowProof exist in a Merkle tree with the given root. Returns true if all proofs are valid.

func (*RowProof) XXX_DiscardUnknown 

func (m *RowProof) XXX_DiscardUnknown()

func (*RowProof) XXX_Marshal 

func (m *RowProof) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*RowProof) XXX_Merge 

func (m *RowProof) XXX_Merge(src proto.Message)

func (*RowProof) XXX_Size 

func (m *RowProof) XXX_Size() int

func (*RowProof) XXX_Unmarshal 

func (m *RowProof) XXX_Unmarshal(b []byte) error

type ShareProof 

type ShareProof struct {
	Data             [][]byte    `protobuf:"bytes,1,rep,name=data,proto3" json:"data,omitempty"`
	ShareProofs      []*NMTProof `protobuf:"bytes,2,rep,name=share_proofs,json=shareProofs,proto3" json:"share_proofs,omitempty"`
	NamespaceId      []byte      `protobuf:"bytes,3,opt,name=namespace_id,json=namespaceId,proto3" json:"namespace_id,omitempty"`
	RowProof         *RowProof   `protobuf:"bytes,4,opt,name=row_proof,json=rowProof,proto3" json:"row_proof,omitempty"`
	NamespaceVersion uint32      `protobuf:"varint,5,opt,name=namespace_version,json=namespaceVersion,proto3" json:"namespace_version,omitempty"`
}

ShareProof is an NMT proof that a set of shares exist in a set of rows and a Merkle proof that those rows exist in a Merkle tree with a given data root.

func NewShareInclusionProof 

func NewShareInclusionProof(
	dataSquare square.Square,
	namespace appns.Namespace,
	shareRange shares.Range,
) (ShareProof, error)

NewShareInclusionProof takes an ODS, extends it, then returns an NMT inclusion proof for a set of shares belonging to the same namespace to the data root. Expects the share range to be pre-validated.

func NewShareInclusionProofFromEDS 

func NewShareInclusionProofFromEDS(
	eds *rsmt2d.ExtendedDataSquare,
	namespace appns.Namespace,
	shareRange shares.Range,
) (ShareProof, error)

NewShareInclusionProofFromEDS takes an extended data square, and returns an NMT inclusion proof for a set of shares belonging to the same namespace to the data root. Expects the share range to be pre-validated.

func NewTxInclusionProof 

func NewTxInclusionProof(txs [][]byte, txIndex, appVersion uint64) (ShareProof, error)

NewTxInclusionProof returns a new share inclusion proof for the given transaction index.

func (*ShareProof) Descriptor 

func (*ShareProof) Descriptor() ([]byte, []int)

func (*ShareProof) GetData 

func (m *ShareProof) GetData() [][]byte

func (*ShareProof) GetNamespaceId 

func (m *ShareProof) GetNamespaceId() []byte

func (*ShareProof) GetNamespaceVersion 

func (m *ShareProof) GetNamespaceVersion() uint32

func (*ShareProof) GetRowProof 

func (m *ShareProof) GetRowProof() *RowProof

func (*ShareProof) GetShareProofs 

func (m *ShareProof) GetShareProofs() []*NMTProof

func (*ShareProof) Marshal 

func (m *ShareProof) Marshal() (dAtA []byte, err error)

func (*ShareProof) MarshalTo 

func (m *ShareProof) MarshalTo(dAtA []byte) (int, error)

func (*ShareProof) MarshalToSizedBuffer 

func (m *ShareProof) MarshalToSizedBuffer(dAtA []byte) (int, error)

func (*ShareProof) ProtoMessage 

func (*ShareProof) ProtoMessage()

func (*ShareProof) Reset 

func (m *ShareProof) Reset()

func (*ShareProof) Size 

func (m *ShareProof) Size() (n int)

func (*ShareProof) String 

func (m *ShareProof) String() string

func (*ShareProof) Unmarshal 

func (m *ShareProof) Unmarshal(dAtA []byte) error

func (ShareProof) Validate 

func (sp ShareProof) Validate(root []byte) error

Validate runs basic validations on the proof then verifies if it is consistent. It returns nil if the proof is valid. Otherwise, it returns a sensible error. The `root` is the block data root that the shares to be proven belong to. Note: these proofs are tested on the app side.

func (ShareProof) VerifyProof 

func (sp ShareProof) VerifyProof() bool

func (*ShareProof) XXX_DiscardUnknown 

func (m *ShareProof) XXX_DiscardUnknown()

func (*ShareProof) XXX_Marshal 

func (m *ShareProof) XXX_Marshal(b []byte, deterministic bool) ([]byte, error)

func (*ShareProof) XXX_Merge 

func (m *ShareProof) XXX_Merge(src proto.Message)

func (*ShareProof) XXX_Size 

func (m *ShareProof) XXX_Size() int

func (*ShareProof) XXX_Unmarshal 

func (m *ShareProof) XXX_Unmarshal(b []byte) error

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.