shamatar / go-snarks

Set of functions for golang verification of zkSNARKs
31 stars 8 forks source link

Support 'short proofs' as generated by ethsnarks #1

Open HarryR opened 6 years ago

HarryR commented 6 years ago

The ethsnarks project has shorter proofs than the proof format you're using.

See:

This reduces on the on-chain cost of verifying a zkSNARK proof to ~450k gas + 40k gas per public input. Likewise, any Go implementation would be cheaper - requiring only four pairing operations and GT multiply operations.

This improvement reduces the size of both the verification key and the proving key, it's a modification of the Groth16 proving algorithm, but without the proof requiring any GT element.

The source code for the libsnark prover module is: https://github.com/HarryR/ethsnarks/tree/master/src/r1cs_gg_ppzksnark_zok

Any additional input would be appreciated ๐Ÿ‘

shamatar commented 6 years ago

Hello @HarryR

Thanks a lot, we were already considering to disembowel the libsnark to change the VK format for groth16!

Sincerely, Alex

Sent with GitHawk

HarryR commented 6 years ago

In the ethsnarks repo we have a stripped down verifier/prover which doesn't need to build most of libsnark/libff etc. Many thanks to the ZoKrates people for the _zok prover variant of Groth16, there is also work on libsnark to introduce the newer SE-SNARK variant (See https://eprint.iacr.org/2017/540.pdf ยง 5 which describes a similar method to removing the reliance upon GT, as is used by the links above).

What's the best way to make go-snarks and ethsnarks compatible with each other? We have lots of interesting stuff in the pipeline :D

A good one would be using JSON as the format for the verification key and proofs, e.g. https://gist.github.com/HarryR/1d79f1557aefaf09ee1452f37506336b

Where G1 points are represented as:

["0xhex...", "0xhex..."]

And G2 points as:

[["0x...", "0x..."], ["0x...", "0x..."]]

The ethsnarks tooling outputs the verification key and proofs in this format, string-encoded-hex is used to avoid problems with Javascript bigint conversion.

Having a common format which is interchangeable between tools could make it easier for everybody.