# Offchain timed contrat

## Problem statement

We have a prover/miner $m_i$ that periodically must prove a statement $S_i$ over time by "showing" a proof $\pi_i$. In the context of Filecoin, the miner must prove that it is storing a given file, and post such a proof $\pi_i$ to the blockchain. We then extend the problem where there are $m$ miners that each needs to prove a statement at the same time.
The goal is to enable the miner to post a "summary" of all proofs after a fixed period of time $t$ to reduce communication and storage cost.

### Naive Solution

At each time $t_i$, $m$ simply posts the proof $\pi_i$ on chain.
For fixed period of time $t$, the (storage) cost is $O(mt)$.

## Solutions around VDF + zk-SNARK

This solution introduces the use of VDF and succints proofs (zk-SNARK) to reduce the storage and communication cost of posting on-chain.

There are three sub-solutions envisionned although the main logic is the following:

At time $t_i$, the miner creates the proof $\pi_i$ proving the miner knows a witness $S_i$ to the language
The miner then creates $h_i = H(\pi_i)$ and gives $h_i$ the VDF proving system (see below what is $y_i$). Using the [Wesolowski](https://eprint.iacr.org/2018/623.pdf) VDF construction, the miner computes $y_i = g^{2^T}$ with $g = h_i$ and $T$ being the time parameter of the VDF.
At time $t_{i+1}$, for statement $S_{i+1}$, the miner creates the proof $\pi_{i+1}$ from $S_i$ **and** as well $y_i$,i.e. the output of the $i$-th VDF becomes an input to create $\pi_{i+1}$ and hence creates a chain of $VDF \xrightarrow{} Proof \rightarrow{} VDF \xrightarrow{} Proof \dots$. The idea is to compress that chain of proofs into "something small" (ideally constant size, but not necessarily).

### 1. Complete zk-SNARK proof on-chain

In this solution, the miner *completely* prove the above protocol in a zk-SNARK. The proof size is then constant: the size of the zk-SNARK proof + some public parameters.

**Problem**: Proving VDF in a zk-SNARK is super expensive, since (1) the Wesolowski VDF works in a group $G$ of unknown order while zk-SNARK computations are inherently working in $Z_p$, and (2) modular exponentiation is expensive and would thus yield a huge circuit size.

**Question**: Could we use another VDF construction such as a Mimc-based VDF which is SNARK-friendly ? Are there any algebraic tricks we could use to make it snark-friendly ?

### 2. zk-SNARK provings $\pi_i$ and separate VDF outputs

In this solution, the miner proves that all $\pi_i$ are correct inside a zk-SNARK and separately gives the aggregated VDF proof. The miner do the following:
* The miner computes the zk-SNARK proof which takes as public inputs the list of tuple $(h_i,y_i)$ (size $t$), and as private input the list of $\pi_i$. It proves that
1. All $\pi_i$ are correct,
2. All $h_i = H(\pi_i)$
3. Each $y_i$ is the input to the proof system (PoRep for ex.) that produces $\pi_i$
* For the VDF part, the miner computes the aggregated VDF proof according the aggregation [protocol](https://eprint.iacr.org/2018/623.pdf) from the paper (**need more detail**).

The "combined" proofs contains:
* The tuples $(h_i,y_i)$: the $h_i$ and $y_i$ are independently aggregated into $h$ and $y$ respectively and are the inputs and outputs resp. to the aggregated VDF proof.
* Aggregated VDF proof
* zk-SNARK proof

The verifier needs first to receive the list of tuples $(h_i,y_i)$, verify the validity of the zk-SNARK proof from that list and then verify the aggregated VDF. The cost is $O(m * t)$ but the factors of $t$ are much (?) smaller than in the naive solution.

**Question**: How much smaller and for what values of $t$ ?

### 3. zk-SNARK combined with a RSA proof

The gist of this solution is to use a commitment to the list of tuples $(h_i,y_i)$ and prove that this commitment has been created from a valid list of tuples,i.e. that $y_i = VDF(h_i)$ for all $i$'s.

The miner needs to compute the following:
1. A commitment to the list of tuples $C = Comm([(h_i,y_i), \dots])$
2. A zk-SNARK proof that takes as *private* input the list of PoRep proofs $\pi_i$, list of tuples $(h_i,y_i)$, and as public input the commitment $C$. It proves
* the $\pi_i$ are correctly created from the $y_i$ (i.e. the $y_i$ are given as input when proving statment $S_{i+1}$ to create $\pi_{i+1}$).
* the list of tuples $[(h_i,y_i), \dots]$ is an opening to $C$
4. An RSA proof that takes as public input the aggregated VDF proof (as in previous section) and $C$, and as private inputs the list of tuples $(h_i,y_i)$. It proves that
* the aggregated VDF proof is correct according to the list of tuples
* the commitment to the list of tuples is equal to $C$.

The verifier now receives two proofs (the zk-SNARK one and the RSA-based one) as well as the commitment $C$. The cost is $O(1)$.

**Challenge**: RSA-based proofs are *slow* and large and it's not clear yet how to prove the second point `the commitment to the list of tuples is equal to $C$` in an RSA proof.

## Solutions around committee selection

In this solution, we assume a 51% honest majority amongst the miner.
The proving miner selects a sub-committee $M$ of all miners in the blockchain thanks to a secure random beacon, i.e. unpredictable and unbiasable. At each time $t_i$, the miner sends its proofs $\pi_i$ to nodes $C_i$ (the committee at time $t_i$). If the miner is honest, i.e. the proof $\pi_i$ is correct, the $j$-th member of $C_i$ replies with its individual signature $\sigma_{C_i}^j$ to the miner. Once the proving miner collects enough signatures (> 50%), it aggregates them into a single signature $\sigma_{C_i}$.

At the end of the period $P$, there are two solutions proposed:
1. The miner simply posts on-chain all the aggregated signatures $\sigma_{C_i}$ for all $t_i$. The cost is $O(t * \sigma_{agg})$ where $s_{agg}$ is the aggregated signature size (signature + bitset?). Cost is $O(t)$.
2. The miner aggregates the aggregated signatures $s_{C_i}$ into a global signature $\sigma$ and posts a single $\sigma$ on-chain. Obviously interesting solution since cost would be $O(1)$.

**Problem for 2**: How to aggregate signatures signed by different members of different committee ? One needs to have a *vector* of bitsets, so the verifier knows which members signed on each signature $\sigma_{C_i}$ ?

## Solutions around rationality

This solution is similar to the comittee selection although the miner is *periodically* selected instead of being *probabilistically* selected. The argument for this solution is really specific to how Filecoin file encoding works: we assume the encoding $E$ of the data $D$ with a challenge $c_i$ takes a long time to compute. $E$ is then the input to the the proof of replication that produces $\pi_i$.

However if the miner is malicious, he can *delete* the file for example. When being requested to submit its proof $\pi_i$, the miner now has to either (1) spend a lot of resources to make that proof $\pi_i$ in time or (2) will reply too late to the challenge. If (2) occurs, then the miner is deemed malicious. If (1) occurs, then the miners have to spend more resources (because the "offline" phase of PoRep, i.e. the encoding, is costly) and this approach is supposedly more costly than simply keeping the file around.

**Challenge**: Into what extent is it more costly to delete the file rather than keeping it ? (for ex. does the size of the file plays a role ?)