Otdfbt

I have read that Nomadic Labs is working on incorporating some flavor of zksnarks into tezos for future amendment proposal (presumably in 2019).

Looking at the literature i see there are many flavors of zero-knowledge which are being either already implemented in other blockchains (zcash, ethereum) or being studied in the academic literature including some without trusted setup.

Given that all these implementations have relative advantages (see this question for great resources) i would like to know what are the technical assumptions/requests/constraints that drive the design choice of the one or multiple implementation of zkp in tezos:

1. Can tezos benefit from having multiple schemas available (some being geared to more security others geared to better performance) ?


2. Would potential implementation issue cause an integrity problem for the entire chain or only the collection of private transactions ?


3. Tezos is meant to self-amend so if one schema is chosen and down the road a new schema is found superior, do certain kinds of zk proofs allow themselves to be “ported” to a new scheme ?

I am one of the developper working on the integration of some privacy features based on ZKP at Tezos.

Yes there are many trade off in ZKP.
I can try to sum up some them and explain our choices.

The first is interactive vs non interactive (ie. the prover and verifier exchange several messages).

In a blockchain context since people can go on and offline, non interactive is much easier to handle, thus we are not looking at any interactive schemes (altough they could theoretically be implemented, every round of communicaiton being in a different block).

Second tradeoff is what is called trusted setup (ie. dishonest generation of the initial parameters could result in the possibility for the dishonest generators to produce false proofs) vs not trusted setup.

However, making a big multi party ceremony offers really good resilience since you can allow a big number of participant (whoever wants to join actually) and if they don't ALL decide to be dishonnest TOGETHER, everything is fine. See for example the Zcash ceremony : https://z.cash/fr/blog/completion-of-the-sapling-mpc/

The other trades offs are verifier complexity, prover complexity and size of the proofs.

For a blockchain context we want to minimize the verifier complexity and size of the proofs, since this is what will be on chain and therefore executed/stored by the whole network (and payed for in gas and tez).

For more see : https://eprint.iacr.org/2019/550.pdf
(Page 4 figure 1 contains an interesting summary of the different trade offs.)
The one used in Zcash and that we will use in tezos belongs to the first line denoted [GGPR] based (reference [57]).

Now to answer the questions :

1. 
   

   Can tezos benefit from having multiple schemas available (some being geared to more security others geared to better performance) ?

   
   
   

   Yes it can, and most probably will in the future. However this is not an issue of performances vs security, but will probably be more about composability (eg. https://eprint.iacr.org/2017/1066.pdf), untrutested setup (eg. https://eprint.iacr.org/2018/046.pdf) (or updatable setup : https://eprint.iacr.org/2018/280.pdf). No choice have been made yet for another system than Groth's one which we will use for private transactions (http://www0.cs.ucl.ac.uk/staff/J.Groth/ShortNIZK.pdf), but investigations have begun.

   
   



2. Would potential implementation issue cause an integrity problem for the entire chain or only the collection of private transactions ?

Of course it can for the collection of private transaction, in the same way than an error in a signature scheme for example could allow to steal money in a regular blockchain.

In our case, an error in the prover would not matter too much since it would only block people for some time until a fix is released (the prover is in the client so no vote is needed to fix).

If the verifier accepts incorrect proofs, we could create fake private money, which in turn would result in stealing from honest user who created real private money.

If the verifier rejects correct proofs, this would freeze the assets of honest users of ZKP.

However there will be no possibility of infinite real money (tez) creation, and everyone NOT using ZKP could NOT be affected by a bug in ZKP.

3. 
   

   Tezos is meant to self-amend so if one schema is chosen and down the road a new schema is found superior, do certain kinds of zk proofs allow themselves to be "ported" to a new schema

   
   
   

   The self amendement could allow to port from one system from another for the implementation of private transactions we are working on now. In general it is not possible to answer since it does not only depends on the ZKP system but also on what you are doing with it.

   
   

Hope this clarify a bit the choices we made and their implication. We will shortly post a detailed explanation of all this.

PS : For those interested in the topic I would highly recommend this more historical paper which is the first system allowing ZKP for all NP languages : https://people.csail.mit.edu/silvio/Selected%20Scientific%20Papers/Zero%20Knowledge/Proofs_That_Yield_Nothing_But_Their_Validity_or_All_Languages_in_NP_Have_Zero-Knowledge_Proof_Systems.pdf