Optimistic SnapDeals: A cost effective option for the SnapDeal protocol

[lucaniz]

@irenegia @lucaniz @Kubuxu @nicola

This proposal aims to introduce a cost effective option for current the SnapDeal protocol

Background

The introduction of the SnapDeals protocol made possible to inject deals inside CC sectors. SnapDeals made possible to take existing CC sectors in the network and fill them with datas.

Nevertheless, for technical reasons the SnapDeals cost in terms of proving overhead resulted similar to the cost of sealing a new sector. This fact partially limited SnapDeals massive adoption despite the realm of new possibilities that this protocol could have unblocked.

We want here to propose a new version of the SnapDeal protocol which aims to introduce a tradeoff between SnapDeals cost and SLA offered by the protocol.

We stress that this new version of the protocol is not aiming to replace the old one, but to introduce a low cost alternative at the price of accepting some compromise. It would be up to the single client to decide which version of the protocol is better fit his needs.

We are convinced that this new version, by drastically reducing cost overhead, can massively improve SnapDeals usability and adoption.

Optimistic SnapDeals in a nutshell

We propose an optimistic version of the SnapDeals protocol which would allow for massive cost saving on the SP side.

On Sha and Poseidon based CommD

The greatest part of the cost of the standard SnapDeal protocol comes from the fact that the CommD (which is unsealed sector CID in the protocol code) used is based on Sha, which makes checking against it expensive in terms of proving cost. On the other hand, Sha based CommD is needed in order to allow Clients to efficiently check it.

On the other hand, having SnapDeal using a Poseidon CommD would be beneficial in terms of proving efficiency but would be a up to 100x overhead for a client willing to check CommD

The best of two worlds

What we propose is an optimistic approach in order to get the best of the two worlds. Assume that the client computes the commitment to the data using Sha, thus preserving the efficiency on the client side, while we the SP uses Poseidon in the SnapDeals protocol, giving the possibility to the Client to submit a fraud proof if at some point he doubts that the SnapDeals sector actually contain the data he committed with Sha.

Protocol Overview

Step 0: SP receives some data D from a client, who can efficiently compute Sha based CommD

Step 1: SP posts onchain both the Sha and the Poseidon based CommD. Then he snaps D into a CC-sector proving the Snap using the Poseidon based CommD. Note that snarks become way cheaper than in the standard SnapDeals protocol, and thus also way cheaper than sealing a new sector (see product consideration below).

Step 2: As soon as a client retrieve the file (let's call the retrieved file D’), he can check that CommD == CommD' . Note that this check can happen using the Sha based CommD, thus in an efficient way for the client

Step 3: If CommD ≠ CommD' , then the client sends a fraud message onchain paying a fraud_fee (note that this is needed to prevent malicious behaviors on the client side). The prover has 24h hours of time to produce a SnapDeal proof using the Sha based CommD (which is, running the standard SnapDeal protocol from scratch). If the prover does not submit the proof, the sector is flagged as “wrongly SnapDealed” and the SP is slashed.

SLA Considerations

Note that in the optimistic protocol we described above, one can have evidence of a wrong SnapDealed sector only if (and when) the data D is retrieved (or if the Poseidon commitment is checked at the beginning of the protocol).

While this is actually changing the SLA (a priori, we can not ensure clients data are not modified before being sealed into a sector), here is why we think the Optimistic protocol is a (cheap) valid alternative to the standard one:

• It is enough to attempt to retrieve D once in order to realize if there is a mismatch in the stored data with respect to the original one. If the SP serves the data, then the Client can check against the Sha commD and eventually send a fraud proof request onchain. If the SP does not serve retrieval, then the client can proceed with a fraud proof directly.
• Even if retrieval is never requested (which means that the client is ok with the risk of a possible mismatch), the security of Filecoin is not at risk since space hardness is not put at risk by having any D’≠ D in the SnapDealed sector.

Product Considerations

Compared with the standard SnapDeal protocol, the Optimistic SnapDeal protocol allows for much better efficiency on the SP side and for much more flexibility on the client side.

Optimistic SnapDeals for SPs: a 54x cost improvement

On the Storage Provider side, the introduction of the Optimistic version of SnapDeals massively reduce the snark proving overhead currently due to SHA, given that the commitment used for proofs is based Poseidon hash.
A back on the envelope calculation reveals a ~54x improvement in terms of needed constraints (and thus proving overhead). The main savings come from MT path openings. Indeed:

• A MT path with Sha needs 30 sha evaluation (arity 2), and each evaluation needs ~44k constraints, for a total of ~30*44000 = 132k constraints
• A MT path with Poseidon needs 10 Poseidon evaluations (arity 8) and each evaluation costs 565 constraints, for a total of ~10*565 = 5650 constraints

Note that in case of fraud proof an SP is still required to run the standard SnapDeal protocol, but we need to take into account that this should happen only in case of wrong data snapped into a sector. Indeed, the fraud proof fee which the client has to pay in order to force the creation of a standard SnapDeal proof aims to discourage malicious client behaviors (assuming clients being rational actors).

Optimistic SnapDeals for Clients: full fledged flexibility

With Optimistic SnapDeals a client gets full flexibility, in the form of a tunable tradeoff between SLA guarantees, trust, fraud proof fee costs and computation overhead.

Indeed, a client has at his disposal several different options:

• Trust the SP and do not check the correct data injection in the sector (unless he retrieves the data at some point).
• Ensure the data is correctly injected by computing the Poseidon MT of the data (with ~100x computing overhead with respect to the MT computed with Sha).
  • Note that when using intermediaries, those intermediaries can be the ones in charge for this check (and not the final client)
• Retrieve the data on purpose during within the deal duration in order to check correct data injection and eventually pay the fraud proof fee and submit the fraud proof message, obtaining a standard SnapDeal proof.
• Pay the fraud proof fee directly without retrieving the data obtaining a standard SnapDeal proof

Moreover, the coexistence of both the standard SnapDeal and the Optimistic SnapDeal protocol does not prevent clients that are fine with the current protocol to keep using it.

A more detailed technical description of the protocol can be found here

[Fatman13]

Optimistic SnapDeals for SPs: a 230x cost improvement

Is there any test data on how much faster Optimistic SnapDeal would run on hardwares? Also would there be batched UpdateReplica messages to save gas too?

[lucaniz]

The 230x improvement calculation comes from the number of constraints needed in the snark circuit

[lucaniz]

Numbers updated, since there was a part of the circuits that was not taken into consideration in the preliminary analysis

[scotthconner]

Questions posted here for posterity:

• Does the SP now have to compute both forms of CommD on Snap? I can't imagine the SP just trusts the client so I'm not sure how two upfront computations instead of just one of them translates to savings? Help me fill the gap here.

• For interoperability, does the client have to do anything at all for the SP to get the theoretical Poseidon gains? Can the client continue to use Sha CommD protocol as usual but SPs ue Poseidon on the backend?

[lucaniz]

Does the SP now have to compute both forms of CommD on Snap? I can't imagine the SP just trusts the client so I'm not sure how two upfront computations instead of just one of them translates to savings? Help me fill the gap here.

SP would have to compute the Poseidon Commitment, yes. On the other hand, Poseidon Commitment are much faster with GPU. MOreover, the poving cost should be reduced by 54x (this is what circuit contraints suggest). Of course we need to check if this is worth by checking costs of Poseidon Commitment computation overhead Vs Proving savings.

For interoperability, does the client have to do anything at all for the SP to get the theoretical Poseidon gains? Can the client continue to use Sha CommD protocol as usual but SPs ue Poseidon on the backend?

This is basically the Optimistic approach: the client does nothing more than today while the SP used Poseidon to improve on proof costs. THe only guarantee that the client loses her is that the data he put in the Sha commD is the same that the SP snapped into the sector using poseidon (up unitl he either compute the poseidon by himself or submit a fraud proof)