How to enable provable computation over Filecoin data ?

[nikkolasg]

The goal of this document is to highlight the different avenues one could take to allow verifiable computing over client data stored in Filecoin.

Core Problem

PieceCID is not at all SNARK friendly, e.g. we can’t run any verifiable computation over it efficiently. The main reason is because it is being from SHA256.

The following sections each explores different strategies to enable verifiable computation over PieceCID using SNARKs and the modification or not required to Filecoin.

Status Quo: Single Commitment Version

👉 There is a single commD commitment used for both storage in Filecoin (as in now) but also verifiable computation over the data.

Pros:

- One can know if the FIL PieceCID that he wants to compute over is effectively stored in Filecoin
- Both commitment represents exactly the same data, with complete assurance

Cons:

• Retrieving a PieceCID is not ideal for clients using IPFS
• Not backward compatible for Filecoin storage proof
• Potential new commitment does not meet user-friendly practical requirement
• Suffers in case we upgrade PieceCID commitment scheme
• Binds us potentially to specific proof scheme or curve (ok)

Potential Directions

• Proving statements about IPFS CIDs is very hard right now but it could be tried, with recursive proof systems such as Nova.
• We could also change the IPFS CID to be Snark friendly and change the Filecoin PieceID to be that (requires research, difficult)

Multiple Commitments Vision

👉 There are multiple PieceCID commitments of the same data, one optimized for each usage (storage, computing, streaming etc)
For example, a streaming merkle tree is better than balanced merkle tree for videos, hence one might opt for two retrieval commitments instead of one.

The link between the two can be:

• 🤝 Trusted
• 🔐 Verifiable

🤝 Multiple Commitments (Trusted)

👉 In this world, we trust the client for having computed the right commitments.

The storage commitment is stored on Filecoin as usual. The other commitments can be either stored in the notes of a deal or in a smart contract or external db…

The assumption is that we trust the client is committing correctly to its data. Filecoin is used for storage and there is no link with the “computation” commitment for example.

Pros:

- Easy to implement a product directly now, no change at all on Filecoin side, mostly on client tooling

Cons:

• Cannot be known if a CID is stored into FIL, unless it’s the PieceCID
• However, given the client is trusted for its own data, then they can trust the link between PieceCID and other commitments

Example: Solana stores block data into FIL and writes the retrieval hash and the computation hash in a trusted channel (e.g. deal info label, mapping smart contract).
Those that want to use Solana data use the specific trusted hash

Potential Directions
There could be a standard way to add support for new commitments:
- Either via the “label” fields in the deal
- Or an external contract that creates the mapping,
- Or multiple contracts, standard interface …

🔐 Multiple Commitments (Verifiable)

👉 In this world, there is a cryptographic proof that shows another commitments commits to the same data as in the PieceCID

There are two types of verifiability:

• Perfectly Linked: 100% confidence that the link between PieceCIDs and other commitments are correct
  • unpractical today, for large sizes - especially for PieceCIDs using SHA (order of hours)
• Weakly Linked: It admits some variation of data between the two commitments
  • e.g. I can only be sure that 98% of the data I wish to compute on is correctly stored on Filecoin.

Some users independently store Wikipedia pages, you want to contribute and you don’t know what pages are missing using the Retrieval CID only - so you check on the filecoin network what data is missing.

Pros:

• Anyone can create the links using whatever technology of their preference
• Proofs can be stored anywhere, not necessary have to be verifiable onchain

Cons:

• Highly likely expensive - but doable (much better than single commitment version)
  • neither the user nor the SP will create these links

Potential Directions

• Find a way to weakly map SHA256 commitments into other commitments that are easier to prove.
  • We have done such exploration inside cryptonet
• Map IPFS CID into PieceCID (doesn’t have to be SNARK and can be interactive)

[LaurenSpiegel]

How does this relate to #562?