Minimal S&W publicly verifiable BLS based PoR scheme

Summary

Proofs of Retrievability are a form of proof of possession that allows a verifier to tell with high probability whether a data set can be extracted given that a prover passed the verification phase. For a more in depth overview of PoRs refer to https://github.com/status-im/dagger-research/discussions/32.

Note: PoRs explicitly rely on MDS erasure codes (such as reed-solomon) for their high probabilistic guarantees, however given that the erasure coding scheme can be implemented independently this issues will not attempt to explicitly track it.

Architecture and Implementation Overview

The scheme should implement the algorithm outlined in section 3.3 of Schaham2008.

Implementation Outline

The original scheme outlines 3 discrete roles:

Client (uploader)
Verifier
Prover

The verifier role can be further split into two sub-roles:

Challenge generator
Verifier

Furthermore,

challenge generation does not require any private knowledge, only a "good" source of randomness
verification also does not require any private data, only the knowledge of the public parameters and the challenge itself

These two properties allow us to implement these roles separately, in a non-interactive scheme, as follows:

A client/uploader runs the setup phase and generates a correctly encoded set of chunks and homomorphic tags which are stored by the prover
There is no explicit challenge generation by a separate challenger. The prover itself periodically derives the verification parameters from some pseudo random seed, in this case the block hash, and generates the proof based on these
The generated proof is submitted to a smart contract for verification within some time limit
The smart contact verifies the proof, including also the verification of the self-generated challenge

This scheme is split into several steps:

The client/uploader encodes the data and generates a set of homomorphic tags
The prover generates proofs at predetermined intervals and submits them to the verifier
The verifier which is an "unattended" process that runs on chain verifies the generated proofs and challenges
- We believe that it will be simpler to implement the verification as an on-chain step, however, we expect to replace it with a more scalable off-chain approach in subsequent iterations

Functional Outline

All steps are outlined in [Schaham2008] section 3.3

[x] #16
[x] #17
[x] #18

Acceptance Criteria

[x] The data should be correctly encoded to produce chunks/blocks and homomorphic tags
[x] The homomorphic tags should be correct and reliably verify that the file is extractable if the verification passed
[x] Both the proofs and challenge generation and well as verification should happen in a non-interactive way

codex-storage / nim-codex