CommD/CommP currently uses tree of 2-ary SHA. To verify 2200 challenges would mean the need to verify 2200 * 30 = 66,000 SHA evaluations. This results in more than 1.7B constrains (130% of PoRep constraints).

Below is list of proposed solutions with their trade-offs.

We are looking at 1.7B constraints, which is about 20% more work than PoRep or estimated 50 minutes of GPU compute. This makes the SnapDeals process compete for resources with on-boarding storage.

There are ways (mentioned below) to reduce the number of partitions down to 6 (60% of PoRep) at the cost of additional engineering on side of proofs.

There is minimal increase to complexity caused by the need to partition the proof. We may want to investigate aggregation of these proofs.

Major drawbacks: increased proving costs for the storage provider

Positives of this solutions: no changes to CommP/D calculation, low to medium complexity on proofs side

Apex Cut of 9 to layers would reduce the number of constraints from 1.7B to 1.27B (down to 10 partitions from 13) at the cost of more engineering work on the proofs side.

We estimate additional 2-4 weeks to complete the work in proofs necessary to implement apex cut.

Currently, we are using a 128-bit security factor for Fiat-Shamir transformation, it would be acceptable to reduce it to 80 bits.

This would reduce the number of challenges to 1375 and in combination with Apex Cut could reduce the number of partitions to 6, resulting in estimated 60% cost of PoRep GPU compute or 25-30min.

We can reduce the number of challenges by factor of 12.8 resulting in single partition (cost comparable to WindowPoSt computation) but introduces 75min wait period in the protocol.

In combination with Apex Cut we could reduce the number of constraints from 133M to 100M resulting in 70% of WindowPoSt cost.

We have two options if we stay with SHA CommP:

The core of the issue is caused by CommD tree (and thus CommP/PieceID) using SHA. The proposal is to change the CommD tree to be in part or whole based on Poseidon (or another SNARK friendly hash function if available).

This has the drawback of increasing the cost of client side PieceID/CommP computation about 100x (~6-12 minutes for 32GB deal) as well as engineering costs related to introduction of new CommP/CommD versions.

It would also require significant changes to deal making protocol, as the client needs to decide on Snap vs Normal deal before computing PieceID.

Solutions in this category would also require introduction of minimum deal size (on the order of 128MB or 256MB).

Major drawbacks: engineering complexity for lotus and proofs, CommP computation cost for the client, minimum deal size

Positives of this solutions: cheap proving

Given Poseidon CommPs chain would have to compute CommD.

Using just Poseidon makes the cost of that computation prohibitive (30-100M gas).

Hybrid SHA-Poseidon Tree

By limiting the minimum deal size to 128MB and making the top of the tree use SHA we could avoid the expensive Poseidon computation on-chain by performing Apex Cut. The Apex cut 7 layers deep would cost on the order of 3.6M constraints, thus not significantly increasing proving time.

This requires Apex Cut implementation in proofs increasing development time.

A way to avoid computing CommD on chain is making the proof accept PieceIDs/CommPs instead.

There are two ways to approach this problem: variable Merkle Trees or variable length inclusion proofs.

Both present high complexity of creation of new gadgets for proofs.

The computation cost of the client could be reduced by introducing hybrid tree with SHA bottom layer.

This reduces the required Poseidon hashes by half (for one layer) and 4x (for two layers), at the cost of 56M and 112M constraints.

Use Blake3 instead of SHA

Blake3 looks promising as fast but less costly in constraints hash function. Initial estimate seems to be 15,216 in comparison to SHA's 25,840, 42% reduction. Blake3 gadget is not currently implemented, while the Blake3 function is derivation of Blake2s (for which we have a gadget), there are also significant changes.

This would reduce the cost of doing last layer optimisations to 21M and 42M constraints.

Poseidon CommP is very interesting approach from the perspective of reducing proving overhead.

There are feasible ways to reduce client overhead by using faster hash function for critical areas.

Unfortunately the major complexity lies in introducing another version of CommP, changing deal making to use CommP v2 for SnapDeals and CommP v1 for normal deals.

Below are drafts and additional notes on solutions

Most solutions will have following drawbacks:

The reason why CommD/P are currently SHA is that CommP is tied to a deal and CommD is the combination of CommPs. Combining CommPs into CommD is performed on-chain in a verification step. Simply accepting CommD removes the guarantee that given CommP is included.

1.6B constraints is "doable" but not acceptable from product and CE perspective

Assuming 256MB min deal size, building on-chain CommD with 2-ary Poseidon would cost on the order of 100M gas, and would double for halving minimum deal size. It isn't great solution for this reason.

Higher arity tree root is undesirable as it increases deal size increments.

It is possible to reduce the number of hash evaluations by around 30-40% by apex cutting.

In case of pure SHA tree it doesn't gain us that much (1.0B constraints, similar to PoRep).

Could be useful as optimisation of another method.

Split the proof into two circuits, main circuit proving challenges and accessory circuit for swapping the Apex of SHA CommD tree into Poseidon.

The accessory circuit would prove transformation T(CommD) → CommD' where top L layers of CommD are removed and rebuilt as L/3 8-ary Poseidon Tree (CommD and CommD' are public inputs)

The main circuit would accept CommD'.

This technique is better than Apex Cut in cases where the proof has to be partitioned.

If we limited the minimum size of deals to 256MB, then on chain we could compute the top 7 layers of the tree using SHA (which would have same cost as ComputeUnsealedCID(CommP...)today).

Then in the circuit we would perform Apex cutting by computing full tree for all of SHA leafs (128*25e3 = 3.2Mconstraints), then the rest of the tree would be Poseidon inclusion proofs.

It is possible to apply this method without limiting the deal size but the constraint number or on-chain computation costs grows quickly.

The Poseidon part of the tree can be 8-ary to speed up the creation process.

TODO: maybe different parameters , figure out how to deal with bigger deals

Difficulty: 6/5

Idea Phase

A circuit that verifies that given set of CommPs is included in CommD to workaround building CommD on-chain.

Either as one circuit with variable length paths (then included in the update circuit), or N circuits with path lengths 1..N

Difficulty: 6/5

Idea phase

This solution inherently limits the minimum deals size.

Uses Poseidon based CommP

The idea is that circuit accepts limited number of CommPs as inputs (for example 128 CommP = 256MB min deal size) as well as condition bits describing high high the tree given CommP is placed.

Circut: full top tree computation, paths to CommP in the top of the tree by brute-forcing variable-length inclusion proofs

Difficulty: 1/5, Quality: 1/5

Don't do Fiat-Shamir and reduce the number of challenges 12.8x

Doesn't solve the issue on its own but would allow reducing constraints by ~50% for places where SHA is used.

Constraints: 21,518 for 64 bytes hash

Should cost ~55M constraints for single layer of blake, reducing the number of Poseidon hashes.

Very fresh and not reviewed.

A new SNARK friendly hash function supposedly 10x faster than Poseidon-128 outside of circuit.

Unfortunately based on lookup gates and not efficient in Groth16.

Notes:

Computing