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.

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

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.

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.

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).

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.

The positive aspects of applying the approach above yields:

The challenges