zkSNARKs in WebAssembly - running demo and discussion

Research
1

Generating proofs, verifying proofs and even generating keys in WebAssembly may hold many benefits:

  • It makes deployment of circuits very easy - the major browsers, both in desktop and mobile, support WebAssembly and show good performance when running it. It’s especially useful for smaller proofs which can run fast.

  • It allows re-using the same vetted libraries, such as bellman, that you use when running natively. This lowers the surface of danger and auditing needed.

  • In the cryptocurrency case, it allows for building web wallets for currencies such as Zcash. It also opens up the possibility for Ethereum dapps that use zkSNARKs that don’t need local installation.

  • Some techniques and new schemes, such as Sonic and Bulletproofs, make it secure to run new circuits without a new trusted setup each time, make deployment even easier.

  • It opens up the possibility for use-cases which are currently hard to deploy:

    • Login using zkSNARKs - i.e., prove you know the pre-image of your password, with having to pass it over the wire.
    • Zero-Knowledge Contingent Payment
    • Proving you’re not in a blacklist or in a whitelist.
    • And more…

Check out this demo on zkwasm.kobi.one, running a “knowledge of discrete log” proof for baby jubjub. It can:

  • Generate proving and verification keys, allowing to save them to file or load from file to allow for sharing.
  • Prove knowledge of discrete log by providing the exponent and getting as output the resulting element.
  • Verification of the proof with the resulting element.

The demo uses Stefan Deml’s version of bellman, which adds support for single-threaded mode, and The Matter’s version of sapling-crypto which adds a bellman implementation of baby jubjub.

That said, this doesn’t come for free, and there are aspects that require consideration before using it for anything real:

  • Random number generation - although the major browsers have access to the Web Crypto API, it’s not integrated with the Rust code. Currently, the code uses XorShiftRng, which is not suitable for cryptographic applications. The Rust WebAssembly target doesn’t support OsRng.
  • Side channels attacks on javascript opens up a new attack surface.
  • XSS, CSRF and other OWASP goodies are also possible problems now.
  • Code integrity should be carefully done, to make sure you are working on the proof that you want - i.e., using SRI.
  • Probably many other more considerations needed when running in a browser.

It would be nice to discuss the following in the context of ZKP in WebAssembly:

  • What do you think could make it practical?
  • What are more interesting use-cases for it?
  • What are other considerations that we should all think about?
9 Likes
2

Nice work Kobi. Ah, and an extra thank you for your quick response on the error messages and the mod issue I faced.

3 Likes
3

Great post, regarding possible use cases:

  • One great use case for this is the ability to verify the entire blockchain in real-time on pc / mobile using recursive snarks as we can see in the Coda project: https://codaprotocol.com/

  • Another use case might be a light client for Zcash or similar asset transfer solution.

2 Likes
4

This is really cool :slight_smile:

I don’t know a lot about crypto, esp zk crypto protocols, but I have a few questions…

Regarding WASM: is the advantage that WASM is fast and also compiles so you can check the validity of the computation, or are there other benefits of using WASM in this context too?

Regarding random number generation: my initial impression was that Web Crypto API works for JS and Rust Crypto or openssl work for Rust. Is this incorrect or is there a specific reason those libraries wouldn’t work with WASM and/or the context of this zk snark demo?

Regarding interesting use-cases: if there was a script that was needed to collect data from a website (via API or web scraper), and that script was made public so there was a verified “correct” script that should be run, would this zk crypto system allow you to run that script in the browser and then also prove that the script you ran was the “correct” and not an altered version? And if so, would this also allow people to check the proof of that computation easily without having to re-run the entire script?

  • hope that makes sense, but if not my apologies and I’ll try to explain again

Thanks!

1 Like
5

hey @burrrata, thanks!

I see a few advantages - fast enough to perform even non-trivial zkSNARKs, single implementation that can be used on desktop and on browser and so can be audited once, to name a few immediate ones.

I actually already use the Web Crypto API to get a good random seed, but the pseudo random number generator in Rust, XorShiftRNG is not suitable for cryptographic applications. This can be improved, and I’m not sure which is the way to go - making an interface-compatible PRNG that calls the Web Crypto API or just a better PRNG in Rust.

I’ll try to answer assuming I understood correctly. If you have data that you can publicly verify came from an authentic source (i.e., it’s public, signed or hashed and published), you can indeed process it in the browser and provide only the result with a proof that the result was computed correctly. The crucial part is showing the data integrity - as the script can only run “locally” (it cannot call external systems), it has to provide some “anchor to reality” - i.e., the hash of the dataset the data is taken from.

If I’m on the direction of your question, let me know :slight_smile:

2 Likes
6

Again, sorry if this is redundant, but I think randomness is really neat and would like to learn more! Looking through the Rust Rand Book it looks like they have options beyond XorShifting, but recommend ring, openssl, or Rust Crypto for more security/hardness. Are you looking for a harder version of the same XORShiftRNG or just a harder generator for random value?

That’s very helpful. Thank you :slight_smile:

I’m currently exploring protocols to get data from centralized web2 platforms/databases to decentralized blockchain platforms/databases. This requires verifying the source of the data as well as verifying that the script used to pull/scrape the data was executed correctly. Once the data has been verified, it’s added to the state of the blockchain and then anyone can build contracts or applications on-top that work with that data. That’s the idea anyways.

ATM I’m thinking to have a publicly released script that people can use to scrape a website and submit that data to the blockchain. Then there needs to be a way to verify that this script is run as intended and not a modified version. When you say that “it cannot call external systems”,

  • is this because the input/result of the external system cannot be verified and thus it breaks the whole thing?
  • or could you at least verify that the publicly released scraping script was compiled and run correctly, even if you can’t verify the data it will return? For example the script was not modified, it was run, and then this is the data it returned? This could maybe even be integrated into the script where the website to crawl (or API to connect to) is hard coded in, and the values it returns are stored in a HashMap of the script, and the script returns the HashMap. It can’t verify what’s in the HashMap, but it can verify that the script ran, got some values from the website it called, and those values are in the HashMap it’s returning. Is that possible?

Another approach I’m exploring is pulling the SSL cert of the website along with the other data the script pulls in order to verify the source of data. Or maybe using the TLS handshake to verify the connection. While those might help, ultimately we need to verify that the script was run correctly in the first place.


Also another usecase might be linking usernames on websites to wallets on the blockchain in an anonymous or pseudo anonymous way. For example:

  • a program is created that mints tokens for users based on Reddit karma/upvotes. Then, anyone who wants to access those tokens creates a wallet, posts a random string to Reddit, and then also sends that same random string to an account contract on the blockchain. The next time the scraping/API script runs the account verification contract checks the data to see if the random string is found in the data, and if so, the wallet is tied to that username and receives tokens accordingly.
  • edit: this could actually be augmented by posting a 1-time use public key to Reddit that anyone can verify, but then sending the corresponding private key to the verification contract (because only the person who created the public key would have the private key)

A few problems with this such as timing attacks, but mainly, that it forces a public link of identity.

Thinking that with a login system that uses zkSNARKs, you could prove that you know the pre-image of a key without having to reveal what that key is. This could help move towards pseudo anonymous verification of off-chain identities for on-chain systems. Of course someone could still do a network analysis and correlate which on-chain accounts receive tokens that match the karma of Reddit users, but it’s a little better than just a direct public link.


Anyways, these seemed related to usecases for ZK Proofs on the web so thought I’d share, but I’m more of a crypto enthusiast than anything so I apologize if some of this is obviously incorrect, redundant, or tangential at best lol

1 Like
7

About RNGs - I haven’t checked if ring or openssl compile to WebAssembly, and they might be a good option. Would be cool if anyone checked :slight_smile:

I see where you’re going with this.
In SNARKs, much like smart contract, you rely on the input you receive. Any interaction with the data from the “real world” depends on the prover providing that input.

What you usually do is provide some anchor to reality - in Zcash, you provide a merkle root of all the commitments that have ever been published. Some of your suggestions go in that direction as well:

  • If you get signed data from the website, you might be able to verify this signature inside the SNARK and thus establish the authenticity. It might not be trivial inside the SNARK, since it might be expensive to express it in arithmetic constraints, but not necessarily.
  • TLSNotary goes in the direction of being able to verify the authenticity of the TLS stream by a third-party.

About verifying that the script ran correctly, you can verify that a program, depending on its inputs, ran as expected. That said, as I mentioned before, a larger program would be harder to verify, as SNARKs are slow to run. Offloading computation to cloud and being certain of its correct execution was the premise in some SNARK papers, such as Pinnochio.

3 Likes
8

Thanks for your feedback. That’s really helpful :slight_smile:


RNGs:

Looked into it a bit and I’m getting conflicting stories so I dunno, but here’s what I found:

According to the Rust WASM Book it looks like Rust does compile to WASM, but any library that requires a source of entropy (like the ring::rand RNG that defaults to /dev/urandom) won’t work because the compiled WASM exists on a VM without access to the hardware layer.

According to the Rust WASM Docs, it looks like there are functions that call the Web Crypto API

Asked the Parity guys who are working on Substrate/Polkadot (blockchain protocol written in Rust that compiles to WASM) and they seemed to say that it was possible to inject randomness into WASM, but that they don’t do so within their protocol to keep it deterministic.


ZK Data Proofs:

  • The current script pulls the certificate chain along with the website data so that might work. In general though, the protocol you described here could verify that a script is run right? For example: the input to the zk snark is the scraping script that has the destination website to scrape as well as the website’s CA certificate (and certificate chain) hard coded into it. One proof could check that the script was run without any modifications, and another proof could check that the correct cert chain was returned with the result. Would that work?
  • TLSNotary is awesome and that was originally the protocol I was going to replicate, but the trusted execution environments and chrome extensions would have to go. Started to prototype what it might look like, but it looked like even if the handshake between the client and server are verified the exact script being run also needs to be verified. Also, the blockchain I’m building this on is Substrate/Polkadot which is also written in Rust and compiles to WASM for runtime verification so it seemed like a natural fit.

Ideally I’d like to write the whole thing in Rust and have an arbitrary framework so that “collator nodes” can scrape and submit data to a be checked deterministically by “validator nodes” via a simple proof check, but people watching the blockchain from the outside can also open up a website (block explorer w WASM) and check the proofs themselves (even if it takes a min or two). This is just a prototype so it doesn’t have to be super fast or anything, it just has to work. IF this works, then the model could (potentially) be optimized and generalized to other on-chain usecases as well.

2 Likes
9

Hey Kobi, I’m looking at the current additions to the codebase. I’m curious why you aren’t providing a merkle path as a private input the to the TreeCircuit? Instead it appears you are hashing data with the zero point. What is the intent of the TreeCircuit, perhaps I’m missing something entirely?

I’ve starting working on something similar here. If I’m trying to prove knowledge of a leaf in a merkle tree as I suppose your circuit is also doing, don’t you need to pass in the root and proof as public inputs?

`

2 Likes
10

Hey Drew,

Cool you checked it out :slight_smile:

You are right to be curious! I wanted the demo to be easy to use, so I chose a fixed path consisting of N path elements which are zeros, where N is the depth of the tree.

Normally, you would receive this array as a private input. The circuit today takes a leaf and has the root as a public input.

You don’t specifically have to add the root as an additional public input, as it’s implicitly calculated in the circuit and flows to the public input. If the verifier puts an incorrect root as a public input, the proof will not verify. You can see that the verification part receives the proof and the root.

2 Likes
11

I upgraded the RNG to ChaChaRng which should be good cryptographyically :slight_smile: Also, I think it’d be pretty easy to do a bridge to web crypto if ever needed. I take a good seed from the web crypto API and feed it into ChaChaRng.

About the ZK Data Proofs:

  • I suspect that if you try to convert the entire script to a zkSNARK it will be very hard, and you should probably only do the subset that is required for data integrity (i.e., verifying signature, cert chain and so on) and transformations (convert one binary format to another). A warning - SNARKs are very inefficient, so you can’t do a whole lot. Even verifying an elliptic curve signature of an arbitrary curve might be expensive.
  • Yeah, it’s not pleasant to use. I’m not sure you can verify a TLS stream without doing something of the sort though.

I think that if you want something that works to prove the concept, you’d probably need to choose one specific use case where the data is convenient to transform and easy to verify (i.e., hmac).

3 Likes
12

Forgot to mention - although I use fixed zeros, I still allocated the variables in the constraint system, so there shouldn’t be any difference in performance between these zeros and a path in a real tree.

1 Like