groth16.Verify should be able to verify bellman-generated proof

[gbotrel]

See #29 for more context.

Need to parse bellman verifying key and proof data structures, and ensure 100% compatibility with groth16.Verify (and the pairing check).

[whyrusleeping]

Anything I can do to put this on the roadmap?

[esuwu]

https://github.com/esuwu/groth16-verifier-bls12381
You can find something useful from this. It works but not so fast. There are for bn256 and bls12-381

[gbotrel]

Anything I can do to put this on the roadmap?

@whyrusleeping This is already on the roadmap :-) Unless we hit some unexpected issues, should be on a experimental branch in few weeks max.

https://github.com/esuwu/groth16-verifier-bls12381
You can find something useful from this. It works but not so fast. There are for bn256 and bls12-381

@esuwu interesting thanks for the link --> I see you added gurvy as a dep in the go.mod but repo is using another lib, is it because of the serialization / point compression or did you encounter other issues?

[esuwu]

@gbotrel Actually I tried to use gurvy at the beginning but after I realised I don't need it. Decompression based on
https://github.com/kilic/bls12-381 - method FromCompressed(). But I forgot there is only decompression for bls12-381. https://github.com/wavesplatform/gowaves/blob/master/pkg/crypto/groth16 have full decompression for the points on both curves bn256 and bls12-381

[gbotrel]

@whyrusleeping can you point me to the code for the circuit you want to verify? (+VerifyingKey and curve)

[esuwu]

@gbotrel seems like it's not finished yet, you're still working on it I mean bellman-generated {vk,proof, inputs}, are you?

[gbotrel]

@esuwu didn't start yet, few other things to wrap up first.

[gbotrel]

@esuwu did a first pass, things went quite well. I re-used your test vectors, and some are failing, will investigate, it might be coming from a slight difference in pairing implementation.

Code is here
Tests and benches (adapted from https://github.com/esuwu/groth16-verifier-bls12381 ) .

Our VerifyingKey struct is similar to what bellman calls PreparedVerifyingKey . Except gnark expect the witness to be a map of named inputs, not just an ordered slice of elements.

Proof are the same, just needed to change encoding order of the elements.

@esuwu where did you get your test vectors from? Encoding of the bellman VerifyingKey don't match what I expect from bellman's code . (2 elements are missing, and the Ic length is not encoded).

For benchmarks, did compare with your code on BLS381 (unfair, as you didn't use a MultiExp but unitary ScalarMultiplication, and pairing check could be optimized):

benchmark                               old ns/op     new ns/op     delta
BenchmarkGroth16Verify0inputsBLS-8      5450681       3758780       -31.04%
BenchmarkGroth16Verify1inputsBLS-8      5744233       3853617       -32.91%
BenchmarkGroth16Verify15inputsBLS-8     10997517      4394762       -60.04%
BenchmarkGroth16Verify16inputsBLS-8     11370409      4318493       -62.02%

This is the measurement that accounts for point decompression. If we don't benchmark point decompression but only the verifier:

benchmark                               old ns/op     new ns/op     delta
BenchmarkGroth16Verify0inputsBLS-8      5450681       1979130       -63.69%
BenchmarkGroth16Verify1inputsBLS-8      5744233       2016906       -64.89%
BenchmarkGroth16Verify15inputsBLS-8     10997517      2120993       -80.71%
BenchmarkGroth16Verify16inputsBLS-8     11370409      2134322       -81.23%

notes on perf; should likely be twice faster on bn256, didn't bench.

@whyrusleeping --> so, I'm wondering if gnark is a good home for this code. Checking a proof is basically a function that takes Verify(proof, verifyingKey, witness) as parameters.
proof encoding is 100% the same between gnark and bellman.
the witness must live in the caller code (i.e Go) and re-encoding for gnark or having gnark offer a trivial utility method to convert from a slice of element to a map[string]Element is easy (can even be done with big.Int)
the verifyingKey is similar to what bellman calls PreparedVerifyingKey, with an extra element. The conversion from bellman vk to gnark vk needs to be done once only, and will be like 20lines of code in rust, I believe.

Bottom line; verifying a bellman proof in gnark (modulo we solve this failing test) should probably be managed by caller code (encoding in gnark expected format, couple dozen lines of code) rather than by gnark itself. Any thoughts?

[esuwu]

@gbotrel hello again. The test vectors are generated from this repo:
https://github.com/snjax/groth16verify/blob/master/src/bin/show_test_vectors.rs

You don't have to encode Ic length because VK size depends only on that instance so you always may figure this parameter out.

"2 elements are missing": alpha, beta, gamma, delta and IC[] in VK struct are enough to check snarks. There are extra elements for its work.

Our way of serializing objects is for Ride, it's slightly different. Bellman way of serializing is LE, but we have BE.

VK and Proof are serialized compatible with bellman. However there is serializing to BE for Inputs for compatibility with Ride. Probably that's why some of your tests failed. We made implementation like in Ephereum, it's common way, for example circom uses similar implemetation.

Actually it's not going to be a problem to convert from LE to BE and vice-versa. It's a uint256 array, so you should cut into chunks, convert every chunk and it will be like in bellman.

Finally, you might have noticed that points are compressed, didn't you forget to uncompress them? Anyway you can always find methods FromCompressed() in Waves repo for both curves. https://github.com/wavesplatform/gowaves/blob/master/pkg/crypto/groth16.go