Kubuxu- Goals
- Motivation
- Solution - Poseidon CommD with Merkle Tree Translation Proof
- Merkle Tree Translation Proof
- Alternative SNARK and non-SNARK friendly commitment/hash schemes
SnapDeals project should successfully deliver the capacity to utilize CC sectors for data storage. Unfortunately, due to constraints of the existing system, SnapDeals in the current form will have a medium-high proving overhead of around 45 minutes to one hour. However, this can be reduced by a factor of approximately 40x with fundamental changes to deal-making.
Goals
- Reduce cost overhead of using SnapDeals to encourage Deal Data onboarding
- Reduce latency of SnapDeals for better usability and Product Market Fit
- Enable alternative use-cases of Data Commitment in the FVM world.
Motivation
Cost and Performance of SnapDeals suffered from the previous decision to adopt SHA based tree commitment for data (the same limitation affects proof of extra copy). In addition, the nature and SNARK performance of this commitment scheme limit its further usability for alternative use-cases like computation over data or generic on-chain data inclusion proof (alternatives proposed below can have 300x reduced proving cost).
Solution - Poseidon CommD with Merkle Tree Translation Proof
Poseidon Tree commitment is currently the best commitment scheme deployed by Filecoin.
The resulting improvement to SnapDeals is approximately 58x reduced number of constraints, which currently is the source of the majority of SnapDeals protocol cost.
A version of SnapDeals circuit using Poseidon CommD has piggybacked off SHA SnapDeals trusted setup.
Unfortunately due to the high cost for the client, we cannot rely on clients using Poseidon CommD.
Merkle Tree Translation Proof
The primary approach to solving this issue is Proof of Merkle Tree Translation or non-interactive Proof of Wrong Merkle Tree Translation (or a combination of both).
Both schemes are based on the idea of Client computing commitment A which is cheap on generic hardware and Storage Provider computing commitment B which in turn is cheap in SNARK.
In the case of Proof of Merkle Tree Translation, the SP proves to the Client that the data in both commitments is the same with probability. This is interactive, non-succinct proof because we want to avoid SHA inside a SNARK.
More precisely assuming bit security boundary and challenges the epsilon is equal to.
In the case of Proof of Wrong Merkle Tree Translation, the Client can at latter date, after retrieving the file, challenge the SP that the translation was performed wrong at some position. This challenge would be resolved on-chain, by the SP posting a proof that translation was performed correctly at the given position.
There is also an option of adopting a hybrid of both PoMTT and PoWMTT such that client has a recourse if their data is ever wrongly committed.
Alternative SNARK and non-SNARK friendly commitment/hash schemes
There exist alternatives to Poseidon which are choosing a different trade-off between performance inside and outside of SNARK.
Examples being ReinforcedConcrete or Sinsemilla (from ZCash Orchard)