4

Normally, in zk-SNARK, we need to generate two public keys: one for prover and one for verifier. However, the input parameter of this generator algorithm must be secret, meaning that it must be hidden for both prover and verifier.

And because of this, the process of those public generation is done by a trusted third party.

Since using a trusted third party is not desirable for decentralized blockchain, I am looking for a decentralized approach of those public key generation. Is there ? or it's impossible to have a decentralized zk-SNARK ?

P.S. More information about zk-SNARK is found here: https://media.consensys.net/introduction-to-zksnarks-with-examples-3283b554fc3b

Questioner
  • 2,670
  • 2
  • 33
  • 62

3 Answers3

4

Yes, the verification key can be computed using multiparty computation (MPC). In this setup, n people participate in the construction and each independently and randomly generate the secret input. The system is set up such that so long as at least one of the participants discards their secret then the resulting keys are secure.

You can find details about the original ZCash key generation "ceremony" here:

Tjaden Hess
  • 37,046
  • 10
  • 91
  • 118
  • Thank you, Is this approach used only for verification key (key used by verifier) ? or for both proving key (key used by prover) and verification key ? Thanks – Questioner Aug 28 '18 at 13:30
  • Btw your second link: (ZCash Paramater Generation Overview) does not work (The webpage at https://z.cash/technology/paramgen.html might be temporarily down or it may have moved permanently to a new web address. "ERR_TUNNEL_CONNECTION_FAILED"). Thanks – Questioner Aug 28 '18 at 13:34
  • The proving key doesn't need anything secret, so it doesn't really apply. The link works for me – Tjaden Hess Aug 28 '18 at 15:37
3

You also might want to check out the following resources.

The ING blockchain team has submitted their proposal for efficient ZKP's to ethereum. It's not a SNARK but a range proof.

https://github.com/ing-bank/zkrangeproof

There is also Zokrates but it's 10x more expensive.

https://github.com/JacobEberhardt/ZoKrates

Nico Vergauwen
  • 1,004
  • 7
  • 11
  • Thank you, but what do you mean by "expensive" ? Do you mean "time complexity" ? Zokrates is apparently an Ethereum toolbox for zk-SNARK. – Questioner Aug 28 '18 at 14:53
  • 1
    The ING system doesn't work on the public blockchain. It would require a hard fork to implement. – Tjaden Hess Aug 28 '18 at 15:40
  • I Mean expensive as in gast cost for the verification contract. The ING contract costs 3 Million gas for verification. The Zokrates implementation costs about 30 million gas.

    @Tjaden, Are you sure , It's based on byzantium precompiles so it should work on main net.

     – Nico Vergauwen Aug 28 '18 at 16:06
  • Oh, you're right they updated it apparently. Older versions predate byzantium. Of course, range proofs are strictly less expressive than SNARKs – Tjaden Hess Aug 28 '18 at 20:04
  • @NicoVergauwen really? given the current 8 million gas limit, how could the verification cost 30 million gas? i – nrek Oct 13 '18 at 13:08
  • My bad , ZKRP 180k gas , ZK-SNARK 1.6 mil gas – Nico Vergauwen Oct 13 '18 at 17:21
  • in a private network you can increase the blockgas limit so it wouldnt be an issue – 0xsegfault Nov 12 '18 at 13:25
  • True, but you would also have less of a need for ZKRP in a private network. – Nico Vergauwen Nov 13 '18 at 13:55
  • The AZTEC protocol which allows to do ZK transfers with any token is based on ZKRP https://www.aztecprotocol.com/ – Nico Vergauwen Jan 07 '19 at 10:35
1

ZK-STARKs are addressing the issue of the trusted setup in ZK-SNARKs. There is a blog post from Vitalik on this topic:

https://vitalik.ca/general/2017/11/09/starks_part_1.html

Hopefully many people by now have heard of ZK-SNARKs, the general-purpose succinct zero knowledge proof technology that can be used for all sorts of usecases ranging from verifiable computation to privacy-preserving cryptocurrency. What you might not know is that ZK-SNARKs have a newer, shinier cousin: ZK-STARKs. With the T standing for “transparent”, ZK-STARKs resolve one of the primary weaknesses of ZK-SNARKs, its reliance on a “trusted setup”. They also come with much simpler cryptographic assumptions, avoiding the need for elliptic curves, pairings and the knowledge-of-exponent assumption and instead relying purely on hashes and information theory; this also means that they are secure even against attackers with quantum computers.

ivicaa
  • 7,519
  • 1
  • 20
  • 50