SNARK Trusted Setup

[wisefool769]

The comparison chart between SNARK / STARK / Bullet suggests that SNARK's require a trusted setup, but this is no longer true with proving systems like Halo. This is the paper: https://eprint.iacr.org/2019/1021.pdf

[alfredonodo]

Right and with discrete log assumption over normal cycles of elliptic curves.

[htadashi]

I'd say that the chart is not wrong since here and other references differentiate zk-SNARKs and bulletproof systems, and Halo would be in the latter classification.

[alfredonodo]

Halo protocol is used by Zcash with zk-SNARK https://vitalik.ca/general/2021/11/05/halo.html

[htadashi]

Thanks for the reference @alfredonodo. It was very interesting to read Vitalik's text.

I disagree however that the row "Trusted setup required?" of the first column of the chart should be updated to "no". My rationale is that even if Halo has a constant verification time, the proof size is still O(log(N)) (please correct me if I am wrong, as I am not an expert). Thus, the protocol is not as succint as the ~O(1) alternatives.

In my opinion, it would be best to update the first column with the explicit names of the zk-SNARK proof systems (e.g. Pinocchio, Groth16, Plonk, etc.) to avoid confusion. Additionally, it might be helpful to add a note to the "algorithm complexity: verifier" row in the bulletproof column indicating that Halo aggregation can reduce the verification time.

[alfredonodo]

I miss the point. The table entry is about the need of trusted setup, not its efficiency. So, in my opinion, one should add no, with the associated computational cost.

Buterin https://vitalik.ca/general/2021/11/05/halo.html
Much of the initial work on this was done as part of designing the Halo protocol which is going into Zcash. These merging techniques are cheap, and a merged proof takes no longer to verify than a single one of the proofs that it's merging. This opens a way forward for IPAs to be useful: instead of verifying a size-n computation with a proof that takes still takes O(n) time to verify, break that computation up into smaller size-k steps, maken/k proofs for each step, and merge them together so the verifier's work goes down to a little more than O(k).

Zcash https://electriccoin.co/blog/explaining-halo-2/
There are a few polynomial commitment schemes described in the literature. The most efficient of them requires a trusted setup and was the focus of Sonic. However, a folklore technique for building a polynomial commitment scheme based on the inner product argument — famously used in Bulletproofs — did not require a trusted setup and had relatively small proof sizes, at the cost of poor verification performance.

In our Halo paper, we fully described this polynomial commitment scheme and realized that a special kind of aggregation technique existed in it that had not been spotted before. The technique allows a large number of independently created proofs to be verified nearly as quickly as verifying a single proof.

I am no expert, but I see no significant difference between halo and bulletproof in this respect.

[Vtalike]

The comparison chart between SNARK / STARK / Bullet suggests that SNARK's require a trusted setup, but this is no longer true with proving systems like Halo. This is the paper: https://eprint.iacr.org/2019/1021.pdf