Proof creation and verification in Wasm

[gbotrel]

Identify any issues.

Measure performance of Groth16 proof creation and/or verification.

[gbotrel]

see https://play.gnark.io ; WASM + Groth16 works fine for small circuits, but doesn't scale well at all.

[p4u]

Hello. After some testing, we've found that both Gnark prover and verifier (both Groth16 and Plonk) can be compiled successfully using the latest tinygo development version. This is a significant milestone for Gnark browser compatibility, and we can't wait to see what new possibilities this opens up for decentralized applications.

We have been driving our testing efforts on this repository: https://github.com/vocdoni/gnark-prover-tinygo. The resulting webassembly file is only 900 KiB, and there's no need to strip the Gnark code.

Going forward, we're proposing to include a compilation test into the Gnark repository CI once the development tinygo is released. This will help us to ensure that no commit introduces a new dependency that could potentially break the support for webassembly.

[ivokub]

Nice. What version of Tinygo did you use? Have you benchmarked the performance vs native implementation? I think it is even possible to have some good estimates with WASM runtimes in Go a la wasmer-go etc. Have you tried in browser? How does it benchmark?

I think this is really sought-for feature, but difficult to get just right imo. It is good to see people are working on it independently.

[p4u]

The current tinygo develop branch, which fixes an issue with Reflect.

With llvm 15 installed in your system:

git clone https://github.com/tinygo-org/tinygo.git
git switch dev
git submodule update --init
make wasi-libc
go install

We will run some benchmarks and post the results.

[p4u]

So we managed to make it work with a good enough performance!!

See here the results, conclusions, and benchmarks: https://hackmd.io/@vocdoni/B1VPA99Z3

Here the code: https://github.com/vocdoni/gnark-prover-tinygo

Thanks to @ivokub for the help (on this issue https://github.com/ConsenSys/gnark/issues/600)

We would love to have your feedback and to discuss potential further steps.

[ivokub]

So we managed to make it work with a good enough performance!!

See here the results, conclusions, and benchmarks: https://hackmd.io/@vocdoni/B1VPA99Z3

Here the code: https://github.com/vocdoni/gnark-prover-tinygo

Thanks to @ivokub for the help (on this issue https://github.com/ConsenSys/gnark/issues/600)

We would love to have your feedback and to discuss potential further steps.

Wow, this is amazing! Great work! I'm offline this week but will provide feedback next week. Seems definitely something we could do in gnark (-crypto). We have stumbled on some problems independently e.g. serialization with cbor etc.

[gbotrel]

🔥 that looks awesome!

re: serialization with cbor, I recall at the time gob was discarded because it didn't handle our largest circuits (100M+ constraints). I think we could use gob for most of the constraint system structure for easier maintainability, and append the constraints themselves in binary encoding at the end.

finishing a (sigh...) refactoring of the constraint/ package. Agree with the issue wit hintID (have the same one for blueprintID ).

the sooner we upstream changes that would make gnark/gnark-crypto more wasm/tinygo friendly, the easier it will be to maintain 👍

[gbotrel]

@p4u would https://mobile.twitter.com/JohanBrandhorst/status/1645953226494324737 help perf? (doesn't seem to help with binary size in wasm)

[p4u]

@p4u would https://mobile.twitter.com/JohanBrandhorst/status/1645953226494324737 help perf? (doesn't seem to help with binary size in wasm)

I don't think so. Actually we already tested WASI (since tinygo supports it already), see https://hackmd.io/@vocdoni/B1VPA99Z3#WASM-or-WASI

WASI has better support for system calls, but it did not provide any performance advantage.

IMHO the way to go is tinyGo. The main issue on the WASM scope is the memory allocation (and parallelization but this is not going to be solved anytime soon). TinyGo performs many memory optimizations at compile-time which actually makes a big difference on performance.

[p4u]

Tinygo 0.28 and this https://github.com/wasilibs/nottinygc might be a game changer.

[p4u]

By the way, currently we are blocked by two things:

1. Hints are still using the reflect mechanism, named hints are already implemented but not used. Maybe tinygo 0.28 might solve that, but it is yet not sure.
2. Cbor is now serializing an object that cannot be easy replaced by Gob or other tools, that breaks our attempts to test the last develop gnark code.

[fxamacker]

Hi, I stumbled across this thread while adding TinyGo support to fxamacker/cbor.

I created branch fxamacker/cbor-tinygo this weekend based on fxamacker/cbor v2.5.0-beta4.

It passes codec tests when compiled with TinyGo 0.28.1 patched with PR https://github.com/tinygo-org/tinygo/pull/3795.

A tradeoff is the removal of one feature: codec cannot decode CBOR tag to Go interface when compiled with TinyGo. Instead, it will return UnmarshalError for now. This tradeoff is caused by TinyGo v0.28.1 not fully implementing Type.AssignableTo.

It would be useful to add TinyGo and WASM support to fxamacker/cbor. Please let me if this works out for you.

[p4u]

Hi, I stumbled across this thread while adding TinyGo support to fxamacker/cbor.

I created branch fxamacker/cbor-tinygo this weekend based on fxamacker/cbor v2.5.0-beta4.

It passes codec tests when compiled with TinyGo 0.28.1 patched with PR tinygo-org/tinygo#3795.

A tradeoff is the removal of one feature: codec cannot decode CBOR tag to Go interface when compiled with TinyGo. Instead, it will return UnmarshalError for now. This tradeoff is caused by TinyGo v0.28.1 not fully implementing Type.AssignableTo.

It would be useful to add TinyGo and WASM support to fxamacker/cbor. Please let me if this works out for you.

That's great @fxamacker, I will give it a try.

An update for the efforts of running Gnark on Browser.

I have removed all concurrency of the gnark/gnark-crypto code, so it can be now compiled without a scheduler.

By tweaking some functions and prioritizing reduction of memory allocation, I have achieved a Groth16 Prover able to solve a circuit of 45k constraints using 1.75 GiB of memory. It takes between 10 and 20 seconds on Android mobile phones with at least 3-4 GiB of RAM.

The big issue and the current stopper is iOS. For some reason, iOS browsers do not allow allocating 2 GiB of memory for WASM execution. I have read somewhere that the limit is 256 MiB (which I hope is not true).

To this end I am currently trying to use a custom garbage collector for tinyGo that could reduce memory allocation, since the standard "conservative" GC is quite naive, a more optimized GC could make a difference.

However, we have currently some issues when trying to use it: https://github.com/wasilibs/nottinygc/issues/13

---

If that does not help on iOS devices, my next attempt might be to write a parser from the Gnark proving key and witness to SnarkJS zkey format. That would allow building the circuit and generating the witness using Gnark and solving the proof using SnarkJS js/wasm. Some initial work is already done here https://github.com/vocdoni/go-snark/blob/gnark/parsers/gnark/parser.go but just as a non-functional PoC.

We have already tested the same circuit on Circom/SnarkJS and it works properly on iOS and mobile devices. Its code is very optimized for browsers.

IMHO the whole Gnark ecosystem would benefit from such a parser. But the SnarkJS zkey format is very raw and would require some effort... We are considering creating a public bounty for such a task. Let me know if Consensys would be interested in partially funding it. You can also find me at pau at vocdoni dot io.

[p4u]

Umm, great news! This makes part of the job already: https://github.com/dcbuild3r/ptau-deserializer