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 #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 #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 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.

[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: wasilibs/nottinygc#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

[Scratch-net]

tinygo 0.33 is just released and trying to compile my gnark code with it results only in CBOR errors

tinygo build -o main.wasm -target=wasip1 keygen.go 
# github.com/fxamacker/cbor/v2
../../../mnt/c/Users/Scratch/go/pkg/mod/github.com/fxamacker/cbor/[email protected]/encode_map.go:33:10: iterk.SetIterKey undefined (type *reflect.Value has no field or method SetIterKey)
../../../mnt/c/Users/Scratch/go/pkg/mod/github.com/fxamacker/cbor/[email protected]/encode_map.go:34:10: iterv.SetIterValue undefined (type *reflect.Value has no field or method SetIterValue)
../../../mnt/c/Users/Scratch/go/pkg/mod/github.com/fxamacker/cbor/[email protected]/encode_map.go:48:9: iterk.SetIterKey undefined (type *reflect.Value has no field or method SetIterKey)
../../../mnt/c/Users/Scratch/go/pkg/mod/github.com/fxamacker/cbor/[email protected]/encode_map.go:49:9: iterv.SetIterValue undefined (type *reflect.Value has no field or method SetIterValue)

I wonder if that's the only thing left that prevents Gnark from being compiled with tinygo? @p4u @gbotrel

[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 #600)

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

See the hackmd link here.

[Scratch-net]

Yes, I've seen that, thanks!
I was hoping to avoid doing the same steps you did to make it work on the latest versions of gnark and tinygo, considering that code is more than a year old

[fxamacker]

The build errors in fxamacker/cbor when compiling with TinyGo can be avoided now.

I created a new feature branch (in fxamacker/cbor) tested with tinygo v0.33 and go1.22. More details at:

• Mention new TinyGo feature branch in README fxamacker/cbor#582 (September 8, 2024)

The feature branch is based on cbor 2.7.0, which has memory & speed improvements compared to v2.5.0 used by gnark v0.10.

[Scratch-net]

Yes, thanks!
Now tinygo for some reason does not like encoding/gob which seems like wasn't an issue before. But that's another topic

at main.interface:{Align:func:{}{basic:int},AssignableTo:func:{named:reflect.Type}{basic:bool},Bits:func:{}{basic:int},ChanDir:func:{}{named:reflect.ChanDir},Comparable:func:{}{basic:bool},ConvertibleTo:func:{named:reflect.Type}{basic:bool},Elem:func:{}{named:reflect.Type},Field:func:{basic:int}{named:reflect.StructField},FieldAlign:func:{}{basic:int},FieldByIndex:func:{slice:basic:int}{named:reflect.StructField},FieldByName:func:{basic:string}{named:reflect.StructField,basic:bool},FieldByNameFunc:func:{func:{basic:string}{basic:bool}}{named:reflect.StructField,basic:bool},Implements:func:{named:reflect.Type}{basic:bool},In:func:{basic:int}{named:reflect.Type},IsVariadic:func:{}{basic:bool},Key:func:{}{named:reflect.Type},Kind:func:{}{named:reflect.Kind},Len:func:{}{basic:int},Method:func:{basic:int}{named:reflect.Method},MethodByName:func:{basic:string}{named:reflect.Method,basic:bool},Name:func:{}{basic:string},NumField:func:{}{basic:int},NumIn:func:{}{basic:int},NumMethod:func:{}{basic:int},NumOut:func:{}{basic:int},Out:func:{basic:int}{named:reflect.Type},OverflowComplex:func:{basic:complex128}{basic:bool},OverflowFloat:func:{basic:float64}{basic:bool},OverflowInt:func:{basic:int64}{basic:bool},OverflowUint:func:{basic:uint64}{basic:bool},PkgPath:func:{}{basic:string},Size:func:{}{basic:uintptr},String:func:{}{basic:string}}.Implements$invoke (jnark.wasm:0x9a37)
    at main.encoding/gob.implementsInterface (jnark.wasm:0x639b0)
    at main.encoding/gob.userType (jnark.wasm:0x2ab91)
    at main.encoding/gob.mustGetTypeInfo (jnark.wasm:0x28d15)
    at main.runtime.initAll (jnark.wasm:0x122c5)```

[Scratch-net]

Hey @ivokub Did you have a chance to look at this?

[ivokub]

Hey @ivokub Did you have a chance to look at this?

Not yet - currently working on #1318 and some work for small field solver. But it is on the todo list.