We propose here a variant of the current SnapDeal protocol, based on Poseidon Hash function rather than on SHA256.

Background

Current SnapDeal protocol is based on SHA256 to ease client's CommD computation, given SHA is very efficient to compute, even without having access to GPU.

This efficiency on the client side comes with a cost: proving SHA256 is not efficient inside a Snark and this proving inefficiency results into a SnapDeal overall cost being comparable with the cost of sealing a new sector in the network.

This aspect (along with user experience issues related to software unreliability reported by different SPs) represent a clear downside and drastically reduce the appeal of SnapDeal as the solution for injecting datas into sectors.

Proposal

We propose to keep the SnapDeal protocol as it is now, but changing the hash function used. Specifically, we would use Poseidon hash instead of SHA256.

Why Poseidon, why now

Poseidon is an algebraic hash function, and in particular it can be efficiently proven inside a Snark. Compared with Sha, we have a 54x improvement in proving overhead (see SnapDeal Constraints Comparison (Sha Vs Poseidon)).

On the other hand, computing poseidon is more expensive than computing Sha. This represent a downside when the Client has to compute a poseidon based CommD (and the SP should also compute it, eventually to check it). From initial benchmarks, we estimate a Poseidon CommD to be ~100x more expensive to compute than a SHA based one on CPU.

Nevertheless, we are confident that the massive gain in proving should counterbalance the computing overhead.

Who pays for Client's overhead?

The most controversial part of this proposal is of course the additional overhead required to the Client in order to allow for massive improvement at proving time for the SP.

One can wonder why a Client should decide to pick a more expensive path with apparently no gain on his side.

The Perfect Market Thesis

Here is where our thesis comes into play: we are convinced that, if the overall cost of the deal process is way lower than the current one, then it is in the interest of SP that the Poseidon based SnapDeal protocol is chosen by the Client. Moreover, in order to do so, if gains are remarkable, SP could potentially being subsidizing the Poseidon based CommD computation costs for the client, and still be gaining due to the 54x cost reduction in the proving step (either by providing access to their GPU or giving a discount to Clients, or paying them for choosing SnapDeal v2).

Of course this thesis needs to be confirmed, but we see an opportunity here for improving the entire deal process.

Costs Comparison

We present here the differences of the current SnapDeal protocol and the Poseidon based one, focusing on their costs.

Note that the SnapDeal protocol flow would not change (details can be found in SnapDeals Project ).

In what follows, we assume CommP = CommD (i.e. a single deal equal to sector size)

SnapDeal Cost with Sha

SnapDeal Cost with Poseidon

Cost details and comparison

Let

• Cost0: cost of data preparation, transfer and all other deal and replication overheads
• Cost1: cost of SHA data commitment computation (by either party)
• Cost2: cost of Poseidon data commitment computation (by either party)
• Cost3: cost of updating replica
• Cost4: cost of proof of replica update with SHA commitments
• Cost5: cost of proof of replica update with Poseidon commitments

We know that

• Cost4 ~ 54*Cost5, considering the number of constraints needed in a Snark circuit. See SnapDeal Constraints Comparison (Sha Vs Poseidon)
• The main gain is represented by proving MT Path opening. The number of MT paths opened is the same in both scenarios, and we know that:
• 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
• Cost1 ~ 8.15 min of CPU time (8 min and 9 sec) on AMD EPTC 7402P 24 core processor with 64GiB of RAM
• Cost2 ~ 20 min on a 24 cores, 32 GiB RAM, 24 core machine (for a total of 480min CPU time).
• Cost2 ~ 59*Cost1 (lower bound), by running benchmarks on a 32 GiB RAM, 24 core machine (for a total of 480 CPU time)
• Upper bound could be ~ 120*Cost1 (it might be hyperthreading/logical cores in play as well)

• Cost2 ~ 2 min on a machine with a Nvidia Quadro RTX 6000 (26GB of memory, 24 cores), Jake estimation for GPU time

We also expect that

• 2*Cost1 + Cost4 >> 2*Cost2 + Cost5
• Note that as a simplification we could compare Cost4 with 2*Cost2 + Cost5 only.

Nevertheless, in order to estimate the overall costs of the deal process, we need estimate the relation between MT computation and proving, in order to be able to estimate the overall gain of the entire process (basically: how cheaper is 2*Cost2 + Cost5 compared with 2*Cost1 + Cost4?)

Back on the envelope cost comparison estimation

Given all the above, we give present a rough cost estimation of the two strategies in order to have a dollar to dollar comparison

• Snark with sha = $0.1006 (~ C2)
• snark with poseidon = $0.1006/54
• MT with poseidon ≤ PC2/2 ~ $0.1006/2 [Note that PC2 computes CommR and CommC, we assume those two costs to be comparable]
• MT with poseidon ≥ 59*MT with sha

Costs of PC2 and C2 taken from here (status quo, before SN optimizations)

⇒ Overall cost of SnapDeal protocol using sha = Snark with Sha + 2*MT with sha = Snark with Sha + 2*MT with Poseidon/59 =0.1006 + 2*(0.1006/2)/59 = 0.102305

⇒ Overall cost with Poseidon = Snark with Poseidon + 2*MT with Poseidon = 0.1006/54 + 2*0.1006/2 = 0.10246296296

Conclusion: Overall costs with Poseidon are not better than with Sha (assuming GPU at least)

TODOs