### 3 releases

0.1.2 | Feb 23, 2022 |
---|---|

0.1.1 | Nov 24, 2021 |

0.1.0 | Nov 23, 2021 |

Used in **2** crates

**MIT/Apache**

680KB

15K
SLoC

# CESS Storage Proofs PoRep

The

is the reference implementation of `cess-sp-porep`* Proof-of-Replication* (

**PoRep**) and performs all the heavy lifting for

`cess-proofs`

.* Proof-of-Replication* proves that a Storage Miner is dedicating unique storage for each sector. The miners collect new client's data in a sector, run a slow encoding process (called

`Seal`

) and generate proof (`SealProof`

) that the encoding was generated correctly.PoRep provides two guarantees:

- Space-hardness: Storage Miners cannot lie about the amount of space they are dedicating to CESS Network to gain more power.
- Replication: Storage Miners are dedicating unique storage for each copy of their client's data.

The * Proof-of-Replication* uses Stacked DRG (SDR) designed by

**Ben Fisch at EUROCRYPT19**. SDR uses Depth Robust Graph to ensure the sector has been encoded with a slow and non-parallelizable sequential process.

The proof size in SDR is too large to store it in blockchain this is mostly due to the large amount of Merkle tree proofs required to achieve security. SDR verification algorithm is built using an arithmetic circuit and uses SNARKs to prove that SDR proof was evaluated correctly.

## PoRep Circuit

### Overview of entire PoRep Circuit

Credits to Star LI

### StackedCircuit

StackedCircuit is the over all circuit of PoRep, defined in proof.rs

`pub` `struct` `StackedCircuit``<``'a`, Tree`:` `'static` `+` MerkleTreeTrait, G`:` `'static` `+` Hasher`>`` ``{`
`public_params``:` `<`StackedDrg`<``'a`, Tree, G`>` `as` ProofScheme`<``'a``>``>``:``:`PublicParams,
`replica_id``:` `Option``<``<``Tree``::`Hasher `as` Hasher`>``::`Domain`>`,
`comm_d``:` `Option``<``G``::`Domain`>`,
`comm_r``:` `Option``<``<``Tree``::`Hasher `as` Hasher`>``::`Domain`>`,
`comm_r_last``:` `Option``<``<``Tree``::`Hasher `as` Hasher`>``::`Domain`>`,
`comm_c``:` `Option``<``<``Tree``::`Hasher `as` Hasher`>``::`Domain`>`,
`//` one proof per challenge
`proofs``:` `Vec``<`Proof`<`Tree, G`>``>`,
`}`

This includes

- public_params: StackedDrg (deep robust graph) related parameters, including the parameters of the graph itself and the number of challenges.
- replica_id: Sector copy id
- comm_d: the root of the binary tree of the original data
- comm_r: hash result of comm_r_last and comm_c
- comm_r_last: the root of the octree of the data after encoding
- comm_c: Root of the octree of column hash result
- proofs: Challenge the corresponding proof circuit

The construction of the entire circuit begins with the StackedCircuit

interface function.`synthesize`

`impl``<``'a`, Tree`:` MerkleTreeTrait, G`:` Hasher`>`` ``Circuit``<`Fr`>` `for`` ``StackedCircuit``<``'a`, Tree, G`>` `{`
`fn` `synthesize``<`CS`:` ConstraintSystem`<`Fr`>``>``(``self`, `cs``:` `&``mut` CS`)`` ``->` `Result``<``(``)`, SynthesisError`>` `{`
`let` StackedCircuit `{`
public_params`,`
proofs`,`
replica_id`,`
comm_r`,`
comm_d`,`
comm_r_last`,`
comm_c`,`
`..`
`}` `=` `self``;`
`//`... // function body.
`Ok``(``(``)``)`
`}`
`}`

This function divides the circuit into two parts:

- Tree root check circuit
- Challenge node information proof circuit

The

is fairly simple and is used for verifying comm_r is calculated currectly using comm_c and comm_r_last.
On the other hand `Tree root check circuit`

generates challenge node proof circuit based on the size of the sector. For a `Challenge node proof circuit`

sector `32GiB`

challenges are generated. Also called as 176 small circuits.`176`

`for` `(`i`,` proof`)` `in` proofs`.``into_iter``(``)``.``enumerate``(``)` `{`
proof`.``synthesize``(`
`&``mut` cs`.``namespace``(``|``|` `format!``(``"`challenge_`{}``"``,` i`)``)``,`
public_params`.`layer_challenges`.``layers``(``)``,`
`&`comm_d_num`,`
`&`comm_c_num`,`
`&`comm_r_last_num`,`
`&`replica_id_bits`,`
`)``?``;`
`}`

These small circuit of each challenge node is represented by

structure defined in params.rs.`Proof`

### Labeling

**Labeling a Node**
The labeling function for every node in a Stacked-DRG is

producing a 254-bit field element. A unique preimage is derived for each node-layer tuple in replicas' Stacked-DRG.`Sha254`

The proof circuit for Labeling calculation is to prove that a certain node is calculated correctly according to the SDR algorithm.

function describes how every Stacked-DRG node is labeled for a replica. Nodes in the first layer are labeled using only DRG parents' labels, nodes in every subsequent layers are labeled using both their DRG and expander parents' labels. The first node in every layer is `generate_labels`**not** labeled using parents.

The

object can be created by calling the below function`LabelingProof`

`impl``<`H`:` Hasher`>`` ``LabelingProof``<`H`>` `{`
`pub` `fn` `new``(``layer_index``:` `u32`, `node``:` `u64`, `parents``:` `Vec``<``H``::`Domain`>``)`` ``->` `Self` `{`
LabelingProof `{`
node`,`
layer_index`,`
parents`,`
_h`:` PhantomData`,`
`}`
`}`
`...`
`}`

The create_label function computes sha256 of

, `replica_id`

and the `layer_index`

concatinated in a buffer and hash of the parents itself.`node id`

The following code is used to verify all the labels generated on previous step. This function just checks for quality by comparing

with `labeling_proof``label_node`

`///` Verify all labels.
`fn` `verify_labels``(`
`&``self`,
`replica_id``:` `&``<``Tree``::`Hasher `as` Hasher`>``::`Domain,
`layer_challenges``:` `&`LayerChallenges,
`)`` ``->` `bool` `{`
`//` Verify Labels Layer 1..layers
`...`
`}`

### Encoding

Encoding is the process by which a sector is transformed into its encoding replica. The encoding function is node-wise prime field addition, where "**node-wise**" means that every distinct slice of the sector is discretely encoded. Each distinct slice belonging to a sector is interpreted as a field element and encoded into Replica by adding its key to the slice.

The function

is used to encode a sector (D) into replica (R) given an encoding key (K) derived from R's `encode``ReplicaId`

`pub` `fn` `encode``<`T`:` Domain`>``(``key``:` T, `value``:` T`)`` ``->` T `{`
`let` `mut` result`:` Fr `=` value`.``into``(``)``;`
`let` key`:` Fr `=` key`.``into``(``)``;`
result `+=` key`;`
result`.``into``(``)`
`}`

### Replication

Replication is the entire process by which a sector

is uniquely encoded into a replica `D`

. Replication encompasses Stacked-DRG labeling, encoding `R`

into `D`

, and the generation of trees `R`

over `TreeC`

and `Labels`

over `TreeR`

.`R`

A miner derives a unique

for each `ReplicaID`

using the commitment to the replica's sector `R`

(where `CommD = TreeD.root`

`TreeD`

is build over the nodes of the encoded sector `D`

associated with `R`

).Given a sector

and its commitment `D`

, replication proceeds as follows:`CommD`

Generate the

’s unique `R`

.
Generate `ReplicaID`

from `Labels`

, thus deriving the key `ReplicaID`

that encodes `K`

into `D`

.
Generate `R`

over the columns of `TreeC`

via the column commitment process.
Encode `Labels`

into `D`

using the encoding key `R`

.
Generate a `K`

over the replica `TreeR : OctTree`

`R`

.
Commit to `R`

and its associated labeling `Labels`

via the commitment `CommCR`

.The function

runs the entire replication process for a sector `replicate`

.`D`

### ReplicaID Generation

The function generate_replica_id describes how a miner having the

is able to generate a `ProverID`

for a replica `ReplicaID`

of sector `R`

, where `D`

has a unique `D`

and commitment `sectorID`

. The prover uses a unique random value `CommD` for each

`R`

`ReplicaID`

generated.### Sector Construction

A sector

is constructed from CESS client data where the aggregating of client data of has been preprocessed/bit-padded such that two zero bits are placed between each distinct 254-bit slice of client data. This padding process results in a sector `D`

such that every 256-bit slice represents a valid 254-bit field element.`D`

A Merkle tree

is constructed for sector `TreeD : BinTree`

`D`

whose leaves are the 256-bit slices Di. Each `TreeD`

is constructed over the preprocessed sector data `D`

### PoRep Challenges

The function derive_internal creates the PoRep challenge set for a replica

's partition-`R`

PoRep partition proof.`k`

## Bellman

*"zk-SNARKs are a cryptographic technique allowing a prover to efficiently convince verifiers that the prover knows something — but without revealing the information itself. zk-SNARKs allow for secure, private interaction with unknown and untrusted parties in a blockchain setting due to their (knowledge) soundness property: a valid proof cannot be created without knowledge of the correct statment, even if they are kept private."* by Filecoin. The main benifit of using zk-SNARKs is that it allow us to prove the validity of storage in much less space.

The

uses the "`cess-proving-system`**Bellman's zk-SNARs**" implementation, mainly based on **BLS12-381** elliptic curve and realizes **Groth16**'s zero-knowledge proof system. This library is used to verify whether the zero-knowledge proof is correct and the verification process takes around several milliseconds making it relatively fast.

## License

MIT or Apache 2.0

#### Dependencies

~**20–52MB**

~882K SLoC