Discussion notes #2.2: Commit-and-Prove Zero-Knowledge Proof Systems

![](https://i.imgur.com/WeIvTiX.png =150x) **Home Edition** # Discussion notes #2.2: Commit-and-Prove Zero-Knowledge Proof Systems Presenter: Matteo Campanelli Authors: * Matteo Campanelli (IMDEA) <matteo.campanelli@imdea.org> * Dario Fiore (IMDEA) <dario.fiore@imdea.org> * Daniel Benarroch (QEDIT) <daniel@qed-it.com> To be presented on 2020-04-23. Resources: * [Latest PDF version](https://docs.zkproof.org/pages/standards/accepted-workshop3/proposal-commit_and_prove.pdf) * [Miro Whiteboard](https://zkproof.org/workshop3-board) * [ZKProof WG_COMMIT_PROVE working group](https://community.zkproof.org/g/WG_COMMIT_PROVE) (open to joining) * [Additional related links](https://hackmd.io/@HtwXZr-PTFCniCs7fWFSmQ/B1AwbdI_8) ---- ## Real-time notes _Note taker:_ Anaïs Querol > Others are welcome to augment/annotate using notes. Add your name. ---MyName Problem statement: Standardization of Commit-and-Prove zk-SNARKs **PRELIMINARIES** - ZK: trust in properties about unknown data - CP-ZK: " " and data can be pointed to: - _V_ receives `com(msg)` - _P_ proves it knows `msg` such that `R(opn(com(msg))) = 1` **WHY CP-ZK** - **Compression / Fingerprinting**: _e.g._ train machine learning model with sensitive database from a hospital, and later prove the training was done correctly - **Commit-ahead-of-time**: At commit phase, you don't know what relation you will need to prove. (_e.g._ commit to your credential/identification, and use them in the future to prove things about yourself) - **Modular / efficient composition of proofs**: prove complex relations with specialized gadgets that are efficient for each component sharing a common element (_e.g._ [LegoSNARK](https://eprint.iacr.org/2019/142)) - **Applications**: - Anonymous credentials - Blockchains (with privacy, or proofs on data posted) - Anywhere data is referenced (privately or succinctly) **WHY STANDARDIZATION** - Interoperability (on what to prove and how to prove) - (_What to prove_) Among proof systems about the same data - (_How to prove_) Through time (today we commit to some data and tomorrow we will interact with this data) **WHAT TO STANDARDIZE** - Last year in ZKProof2: - Application - Motivation for standardizing - Definition of CP (focus on non-interactive - This year in ZKProof3: - More concrete proposals **1. Definitions** _Def._ (CP): Given a relation `R`, a CP-NIZK for `R` is a NIZK for `R_CP`. Syntax, properties: - `C.Setup() -> ck` - `C.Commit(ck, u) -> (c,u)` - `C.VfyOpen(ck,c,u,o) -> {0,1}` -> `R_CP` $\approx$ `R + C.VfyOpen` -> `R_CP^ck(c,u):= R(u) + C.VfyOpen(ck,c,u,o)` NIZK for R --> CP-NIZK for R - `ZK.Setup(R) -> srs` -> `CP.Setup(ck,R) -> srs'` - `ZK.Prove(srs, u) -> π` -> `CP.Prove(srs',c,u,o) -> π'` - `ZK.Verify(srs,π) -> {0,1}` -> `CP.Verify(srs',c,π') -> {0,1}` Commitments are a data format for CP as well as an invariant in the `R_CP` relation **2. CP Constructions** Ideal goal: reference implementation as a guide for practicioners - Either specific schemes <- (Pedersen?) - $\exists$ CP-like schemes that are unsuitable for some scenarios (_e.g._ `ck` depends on relation so cannot commit ahead of time) - $\exists$ efficient CPs for Pedersen: [AGM18](https://eprint.iacr.org/2018/557.pdf), [CFQ19](https://eprint.iacr.org/2019/142.pdf) (code has been recently released!) - Or general constructions for CP Approaches to CP: - Direct construction: encode `R`and `VfyOpen(ck)` into a circuit and use a standard proof scheme - Variant of LegoSNARK: $stdZK_R + cpZK_{ComOpen} \rightarrow cpZK_R$ - Advantage: efficient for Pedersen and some classes of ZK schemes such as Groth16 _Food for thoughts: do we want to standardize theoretical ideas?_ **3. Similar approaches**: Hash-n-Prove, Accumulate-n-Prove... - Achieve same motivations using hash or accumulators instead of commitments - Merkle trees and algebraic accumulators also used for fingerprinting - Most of what implies non-hiding commitments also applies here _QUESTION: opportunity to standardize other primitives?_ ---- Charter Ideas Goals: - Standardize commitment schemes (definitions, syntax, constructions) - Standardize other non-hiding methods? ---- ## Discussion topics _Suggestions welcome! Please append at the end, and the moderators will incorporate into the schedule._ ~15 minutes each, by default. (1) Should we standardize syntax/semantics of commitments? (2) If yes, should we standardize specific schemes? And which ones? (3) Should we standardize a lifting procedure that compiles "standard" (non commit-and-prove) schemes to commit-and-prove ones? (4) Should there be a reference implementation? And based on what scheme? (5) Should be separate extractable commitments from non-extractable commitments and if so how? (6) Should standards differ between commitments to small message spaces (e.g. a public list) and large message spaces (e.g. a field). (7) Some commit-and-prove schemes require a nullifier inside the commitment. Should we consider this extension to the standards. Q) ? A) (Daniel Benarroch) sensitive data will be stored in data bases and will be committed to other parties. There will be a waste to prove things about these data (visa statements, loans) but maybe they have different format and would like them to share the same one for interoperability Q) Daira: if we dont require homomorphic property maybe we can be more efficient... does it also extend to when you are computing commitment.... does it require to be of a particular form? (in order not to put it in the circuit) A) Dario Fiore: Yes, in LegoSNARK it is the case. The main point is that theres the folklore construction to put it in the circuit, or other more efficient constructions when the commitment has a specific form. In LegoSNARK it is a Pedersen like commitment sharing the same bilinear groups Q) Daira A) Dario: question for everybody: how much this standardization should ... Daira. If curves are compatible fine Mary: Cant think of a scenario where Pedersens are not efficient Daira: maybe factor of 2 or something in some curves Yuval: maybe want to design (commitment scheme?) circuit with low complexity. Would it be worth standardizing Daira: standardize (algebraic hashes, rescue mimc) to get more security Yuval: in the future someone will come with something that is more secure and more efficient, what you do now? Maybe some things cannot be standardized now. ZK-friendly commitments can be used as a link Daira: algebraic hash functions too early to std Daniel: not first time a hash function was std and later was proven insecure... (laughs) (someone) but if it is not standardized people wont use it and then wont find the bugs, and these competitions can be used to give visibility to all these candidates and attacking them is incentivized yuval: maybe interesting to have a competition for zk-friendly hash functions? Ariel Gabizon: coda, filecoin shifted to mimc or one of these, so motivation is large enough to use them even if they are not std yet. Daira: rescue was the most efficient thing they could use at the time of Halo Ariel: LegoGroth16 you can use that as a commitment, can be more efficient than using any hash function Daira: maybe a factor of 4 or 5 Daniel: hardware acceleration projects. Maybe hashes could be implemented in hardware Marymaller: pedersen hashes are efficient, but some cases where the input of the verifier is super compressed maybe not as efficient Daira: it will depend on the proof system Daniel: could there be any legogroth16 or something so that different proof systems could be used together. so commit data with different com schemes but using same relation? like replace the com scheme and the relation (maybe not the full relation) Daira: could link between opening of commitments Daniel: thats what we are doing for the accumulate RSA Dario: interesting in both directions: com schemes good for instantiating the generic construction (in circuit approach) but also interested in more dedicated constructions. Maybe these could be the pedersen like. I believe Ped com should be a candidate because used in so many constructions, and in some constructions that have nothing to do with snarks such as sigma protocols, and even used in some industrial products (ibm?) Carla Rafols: if you think of std ped com ... lagrangians at a poing, could think of pedersen with different key districution . would you also std the key distribution? Dario: good question, dont have an answer. There is a difference (the same that between structured and random reference string) Markluf: std terminology Daira: distribution, in certain curves you can use Use cases of cp: karim baghery: new paper where they are defining a relation and encryption of witness. Here committing to witness, say want to give a prove about this witness,... in thac construction the blackbox extractor extracts the witness from ciphertext, but the cipher text there basically can act as a commitment to the witness ... dario fiore: want to clarify some motivations. Many schemes have a commitment of the witness as part of the proof. what is not always the case is that this commitment is reusable. the main distinction is that you create this com with some randomness along with the proof. in real cp you should have this com as input of the statement so no control over the randomness. when you encrypt the witness for the sake of extractability you normally create this along with the proof karim: prover gives a proof that I know the witness encrypted in the ciphertext. Note that this is not flexible as CP but maybe we can rerandomize the proofs? This idea was used for building blackbox simulation extractable NIZK. yuval: stronger type of primitive you can think of being useful? karim: cp is more flexible but in some scenarios maybe the other approach could be more efficient. Since with this approach the commitment is a ciphertext of a CPA-secure encryption which for El-Gamal encryption is 2 group elements, and the proof for opening is only 3 group elements with GM17 paper. daira: what is restricted functionalities? karim: maybe want to keep the proof and then rerandomization of proof for the same commitment (reference to paper https://eprint.iacr.org/2019/480.pdf, page 12). In Fig.2, one can see that the proof $\pi':(\pi, c)$ where $c$ can be considered as a commitment and $\pi$ will be a proof for opening. One can send first $c$ as a commitment and later send $\pi$ as opening. > Updated my explanation about using such constructions as a commit-and-proof system.[name=Karim Baghery] yuval: [timed commitment](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.108.7127&rep=rep1&type=pdf), maybe prove about something in a time interval. mary: verifiable delay functions? yuval: old paper by boneh was time commitment, coin tossing being used in situtations where you do predictions about the future and in 10 days the world can see it. Maybe make the existing commitments weaker? maybe some hint that allows to open... statistically binding so must contain all information. zk makes perfect sense in this setting (no way to learn from comm). Or maybe think of a cpu computation done in the cp way. Daira: points out that for Pedersen commitments the generators *must* be independent. In fact, verifiably independent Kobi Gurkan: some of the algebraic hash functions omit the part of the prf.. maybe another nice point to standardize Daira: dont want to do specification by implementation (refering to Poseidon) Carla: Applications. Interesting to think the other way round. Dont see what is the point, what do you lose with this formalization. Why dont we do anything else but commit and prove? Yuval: any primitive has a simpler version of the primitive. good question whether this should be the main standard Daira: no gaining any simplicity Yuval: how can people in what portion of applications of zk is cp something that is universally used? Daira: most applications seen dont use commitments. yvual: com does it come from your proof system or somewhere in the blockchain? Dario: com should not depend on the proof system if you want interoperability. Daira: at least should have the option to use a com that is not tied to the relation Yuval: balance between simplicity of syntax and usability mary: if you have .. lifting transformation, would it not be simpler discrete log based systems, some way of specialize lifting? that applies to a set of constructions Dario: this is the theorem we prove in the paper. we define a class of schemes (commit carrying) so theres an element that you point to which may not be reusable commitment, and then you have a cp for the opening of that element, so you can show efficiently (1 multiexponentiation) Daira: general lifting would be useful if we are about to standardize cp systems Dario: the idea of standardizing a theoretical compiler sounds weird Daniel: definitely definitions should be there. also people should see how to use them more practically, and implementations (reviewed). we talked about concrete schemes, Yuval: should be compatible with the std for proofs. Daniel: there is no zk protocol that is standardized. maybe its a bit too early to std now Daira: good moment to get groth16 and see how it would look like yuval: what template would you follow? daira: maybe we will have a std for proof systems daniel: no need to reinvent the wheel, so lets look at the stds of ietf and check the format they are using. michele orru: what about std other concepts as sigma protocols? daniel: only one proposal related to that (sok) so welcome to start doing it kobi gurkan: templates, i have been using the one for the ietf (https://tools.ietf.org/html/draft-irtf-cfrg-bls-signature-00)