Related work comparison

[InaOana]

Reading LegoSNARK:
Additional properties to add to the LC paper intro/related work for a more in-depth description regarding CP-SNARKs (commit-and-prove SNARKs) and cc-SNARKs (commit-carrying SNARKS). A summary of these properties can be added to the intro/related work of RVRF paper/ZK continuation.

• CP-SNARKs have the commitment key chosen prior and independently of its crs. In contrast, for cc-SNARKs the commitment key is dependent on the relation that is given as input to KeyGen and both the commitment key as well as the crs are an output of KeyGen.

• The commitment computed using the independent commitment key related to a CP-SNARKs is part of the public input of that CP-SNARK and can be shared by multiple SNARKs/CP-SNARKs. In contrast, the commitment computed using the commitment key of a cc-SNARK is part of the proof for that SNARK and, is thus, tied to it; for example, for the cc-SNARK with double binding of Groth16, this commitment needs to be re-computed every time there is some new public input used.

• Regarding extraction from commitments in cc-SNARKs and in CP-SNARKS: since commitments in cc-SNARKs are part of the proof, the extractor corresponding to the cc-SNARK (for a given adversary), also extracts the witness/message committed in the respective commitment. This is not the case for CP-SNARKs as the commitment scheme in that case has its output used as public input.

======================================

Comparison with our the custom SNARKs in our LC paper:

• The commitment key for KZG commitments used with our custom SNARKs are relation-independent in the sense that it does not require a specific relation to be generated. However, since our custom SNARKs have an updatable and universal CRS, they are identical, or better said: In our case, the commitment key is part of the updatable and universal CRS for our SNARKs.

• The commitment created with the commitment key is public input for our custom SNARK and is not part of the proof.

• Regarding extraction: For our compiler for hybrid model SNARKs with mixed inputs, in the second compilation step, a crucial part of the security proof (Lemma 11) is the fact that the commitment scheme is not only binding but also has knowledge-soundness. This is thus an extra property that is not part of the definition of CP-SNARK as presented LegoSNARK.

• Maybe I can add more differences here related to how we define KS and why and related to the compilation step and the types of relations that are covered.

• In the LC paper we are not interested in interoperability with other SNARKs or proving composite and complex NP relations, but we are focused on designing custom SNARKs that are as efficient as possible for our use case. Maybe any other compilation step introduces additional costs compared with what we need.

======================================

Further notes:

• The compiler described in LegoSNARK can take a cc-SNARK, cc-SNARK with weak binding or a cc-SNARK with double binding and transform it into a CP-SNARK (under certain conditions, please see Theorem B.1, page 51).

• On page 18, there is a list of existing (as of early 2019) CP-SNARKs, cc-SNARKs, cc-SNARKs with weak binding (also called weak cc-SNARKs) --> Groth16 is such a SNARK. It is also mentioned that Groth16 can be compiled into a cc-SNARK with double binding. That is more efficient than compiling directly to CP-SNARK using the compiler in Theorem B.1.

======================================

Further questions:

• What kind of SNARKs are PLONK, Marlin etc w.r.t. CP-SNARK as in LegoSNARK framework?
  The answer is in the ECLIPSE paper (https://eprint.iacr.org/2021/934): their compiler creates CP-SNARKS for PLONK, Marlin and Sonic.

• How does item 1) on page 7 of LegoSNARK help us claim that our custom SNARKs in the LC paper are more efficient than alternatives? (@AlistairStewart)

• I need some clarification as to what and how/why/how general is the efficiency claim made in item 1) on page 7 of LegoSNARK. Same question and clarification needed to understand what is being compared in section 7.1 of LegoSNARK. How does that help our claims about efficiency claims for our LC related SNARKs? (@AlistairStewart)

[InaOana]

Read ECLIPSE. Here is the summary:

• In AHP to CP-SNARK compiler from ECLIPSE they start with a relation R and some set of witnesses {(w_i)}i \in [n] and they end up with R_com (defined on page 12 here) where {(w_i)}i \in [n] still remains a witness. In the case of our compiler in the LC paper, we start with a relation R with some public input input_1, which becomes witness for our relation R_com.
• This is related to the point above: The auxiliary inputs (as per their naming in ECLIPSE), are, in fact, in case of our compiler in the LC paper, part of the commitments computed by the SNARK verifier in the first compilation step (regular PLONK compiler). Or, if we look at them from the perspective of the underlying polynomial protocol, they are commitments to some of the polynomials sent by the polynomial protocol verifier to ideal party I. As per the point above, that is not the case in ECLIPSE.
• In our LC paper, the second compilation step is actually a misnomer as no compilation happens there. It's just a security proof that the SNARK compiled using regular PLONK compiler (updated to work for the definition of ranged polynomial protocols for conditional relations) is also a SNARK but for a different type of relation that includes both commitments and vectors. So, the LC paper compiler should be called ''an extension of the PLONK compiler for ranged polynomial protocols for conditional relations with a final SNARK re-casting phase for a mixed commitment and vector based relation".
• (from page 13 of ECLIPSE) <<On one hand, in order to prove R_com in ECLIPSE, their compiler will use a CP NIZKAOK subprotocol for an additional relation CP_link.>>On the other hand, due to re-casting of the output of standard PLONK compiler, we do not need this subprotocol in the LC paper. So our compilation is more efficient.
• Technical comparison between ECLIPSE compiler and our PLONK compilation plus re-casting:
  The ECLIPSE compiler requires that the AHP on which it is applied has straight-line extractor, disjoint witness carrying polynomials, unique extraction, decomposable witness carrying polynomials (see theorem 1, page 13, ECLIPSE paper). I think our polynomial protocols in the LC paper have all of those properties. In turn, just the SNARK re-casting in our case requires special conditions and those are strictly related to deterministically transforming from a set of polynomials to a certain vector of public inputs and vice-versa. These are much less stringent than the ECLIPSE conditions though, I think.

[AlistairStewart]

Another thing we need to compare with are short accountable subgroup multisignatures as defined by https://eprint.iacr.org/2018/483.pdf and https://eprint.iacr.org/2022/018.pdf . I can write something.

These give schemes that like ours use a compact key, which they confusingly call apk, to represent a group of signers. Given a representation of a subset of signers, there is a short signature (of size independent of the number of signers), that can be used with apk to verify that the subset signed the message.

Our comittee key scheme certainly satisfies their definition.

The downsides are that the setups for their schemes use secret scharing like those for threshold signatures with the accompanying downsides and that their verification will be slower. They use a hash to G_1 for each signer in verification and so verification time will scale badly compared to ours with the number of signers. Indeed, looking at https://eprint.iacr.org/2019/403.pdf which gives explcit numbers of field operations for hashes to BLS12-381, we can estimate that a hash to curve needs 1000 field operations. In contrast our basic accountable scheme requires 2 field operations per signer and packed accountable requires 1/128 fild operaions per signer.

[InaOana]

Skimming Lunar: It seems that Lunar just gives faster algorithms for the ones existing in LegoSNARK, maybe looking into more options for linking commitments. From ECLIPSE "Lunar [CFF+20] obtains CP-SNARKs with a universal and updatable SRS and presents proof systems for “linking” committed inputs to the polynomial commitments used in AHP-based arguments."; "Note that Lunar
constructions and ECLIPSE outperform each other in different settings."