TL;DR: we want to apply rational proofs to PoRep and/or PoSt in Filecoin. This could get interesting tradeoffs such as a faster verifier (no pairings involved) and a faster prover running on cheaper hardware. More in general, though, understanding how to exploit rationality in proofs might reveal new and more efficient approaches in cryptographic protocols.

Current Team

Matteo Campanelli (DRI); Rosario Gennaro; Irene Giacomelli; Luca Nizzardo; Anca Nitulescu

Current Status

• We first explored as an internal effort some of the most highest-impact avenues. Unfortunately, according to our analysis, some of the most immediate approaches are not as promising as they look.
• This project is currently continued as an external collaboration. Goals of this effort are: to investigate other avenues to apply rational proofs to Filecoin and improving our understanding of rational protocols. Several of the ideas of this collaboration stem from our initial internal study.

Here is a post-mortem describing (part of) our internal effort, some of the ideas we explored and why they did not keep to their promise (see also rest of this document).

Here is a short list of some of the general directions we find important to further understand rationality in proofs.

What are rational proofs?

Rational proofs (e.g. here, here and here) are a different approach to probabilistic proofs where a prover is economically incentivized. They can be simpler, more efficient and rely on “nicer” assumptions than other types of cryptographic proofs.

How could one apply them to, e.g., Filecoin?

Filecoin proofs already have elements of rationality built into them (e.g. it is rational to keep the file stored, rather than erase it and recompute it). However we then build traditional cryptographic proofs (SNARKs) on top of them (mostly for succinctness reasons). The question is if we can use a rational type of proof on this “second layer” as well, to improve efficiency.

Note that besides improving the efficiency of the “cryptographic proofs” themselves, we might be able to improve the efficiency of the overall sealing process, e.g. if we were able to remove Poseidon hashes and replace them with SHA (the reason we use Poseidon is that they yield better SNARKs, but that may not be necessary if we replace the SNARKs with other types of proofs).

Goals (of past internal effort)

1. Making sealing faster by constructing concretely usable rational proofs for SHA
2. Reducing the costs of creating SNARKs in PoRep/PoSt by applying them to a verifier of a rational proof

More Technical Details

The general idea

The basic idea is from this paper by Matteo Campanelli and Rosario Gennaro. For simplicity we show how this adapt to prove the opening of a Merkle Tree (MT) leaf. Let R be the root of the tree and L be the leaf we want to open. Normally the opening contains d pairs (where d is the height of the tree) $[A_i,B_i]$ where $A_0=L, A_d=R, B_d=\bot$ and $B_i$ is the “sibling” of $A_i$ in the MT. Verification checks that $H(A_i,B_i)=A_{i+1}$ Assuming collision resistance this proof has negligible soundness error (the prover cannot open a wrong leaf with good probability unless it breaks collision resistance of $H$).

A different proof would be for the prover to present $A_{d/2},B_{d/2}$ and then the verifier asks “left or right” at random. If “left” the proof recurses on the indices $i=0,\ldots,d/2$ otherwise it recurses on $i=d/2\ldots d$ At the end the verifier has $A_i,B_i,A_{i+1},B_{i+1}$ and checks herself that $H(A_i,B_i)=A_{i+1}$

This proof has soundness probability $1-1/d$ if you assume that the prover can prepare a chain that has only one mistake in a random point.

We can make the proof rational if when the verifier finds a contradiction it will not pay the prover or assess a penalty.

Pros and Cons

The positive aspects of applying the approach above yields:

• a very fast verifier running in D hashes (D is the depth of a Merkle tree we are opening)
• a prover that is super fast and runs roughly in the size of the computation (virtually no overhead)
• No cryptographic SNARK (no need to use Poseidon)

The challenges

• Larger proofs; we can improve that through slashing and/or applying SNARKs on top. If the latter that might re-introduce Poseidon but not on the sealing process, and in any case only on a much smaller number of instances
• Very high error probability which may lead to unreasonable large slashing. But the above analysis uses a worst case model that may not be the most appropriate one to use for the case of Proof of Space-Time that we are considering. In fact if the adversary has erased too many blocks I believe we might be able to prove that the probability of being caught is larger under some reasonable assumptions. The analysis from this other paper may be useful here.