webb-tools/zk-saas

zkSNARKs as a service using secure multi-party computation.

zk-SaaS

Rust implementation of the zkSaaS protocol based on zkSaaS: Zero-Knowledge SNARKs as a Service. Originally derived from https://github.com/guruvamsi-policharla/zksaas.

zkSaaS is a protocol (and more generally a service) that leverages secure multi-party computation to generate zkSNARKs. It does so by distributing the core computations used in the zero-knowledge prover of the target protocols. The protocol itself is a $(t,N)$-threshold protocol, meaning it tolerates up to $t$ corruptions out of $N$ nodes. In this protocol $t$ is usually assigned to be $N/4$ where $N$ is the number of participating nodes in the computation. Currently, this repo supports the Groth16 prover and we plan to support other protocols as we further benchmark this protocol.

WARNING: This implementation has not been audited. The risk posed by vulnerabilities is a loss of privacy in the witness used for proof generation.

Dependencies

This project relies on the arkworks project for finite field and elliptic curve arithmetic. For communication we use an adapted mpc-net crate from collaborative-zksnark.

Overview

• secret-sharing/: A packed secret sharing and reed solomon error correcting decoder library built on top of the finite field generics in arkworks.
• dist-primitives/: Contains implementations of the distributed fast-fourier transform, multiscalar multiplication and partial products, complete with correctness tests.
• groth16/: Contains a distributed and local version of groth16 used for benchmarking timings.
• scripts/: Contains shell scripts to run various tests and benchmarks.
• fixtures/: Circom circuit and proving key fixtures for local proving tests.

Network Topology

The network topology of the MPC computation is modelled as a star topology. There are two types of nodes in the MPC, denoted king and client. The king is the center node and is expected to have the highest computational throughput. It is tasked with evaluating the $O(N)$ computations such as the FFTs. The clients are the nodes that connect to the king and are expected to have lower computational throughput. The workload of the prover is distributed across clients who run in time $O(N/(l\cdot\log{N}))$

Testing

The testnet requires mutual TLS for ensuring security as well as enforcing the network topology. The network topology is a star graph, and as such, the center node (i.e., the "king") must be started first with a list of valid certificates that each individually represent the client nodes that will connect to the king.

Thus, we must first generate identities for each of the nodes, including the king. This can be done with the following command:

cargo run --example gen_cert -- ./certs/public_n.cert.der ./certs/private_n.key.der 127.0.0.1

• Note: change public_n and private_n to the desired name for each node.
• Note: we do not need certificates backed by a CA like LetsEncrypt, since we are the only ones who will be using these certificates and trust ourselves to create them.
• Note: the final argument, 127.0.0.1, will need to be changed to the IP address of the node you plan to pin the identity to. For localhost testing, 127.0.0.1 is acceptable since each node is running with a bind address on 127.0.0.1.

With these public key documents (in the form of certificates), we start the king by passing in the king's private key and public key, as well as a list of all the client's public keys. For the clients, we pass the public and private key of the client, followed by the public key of the king. Since we are using mutual TLS, we enforce that the king can receive packets from the list of identities passed in, and that the clients can only receive packets from the king.

An example of this network being set up, including the generation of all certificates and private keys, can be found in ./scripts/prod_net_example.sh. This example network sets up the nodes, then performs a protocol where each node sends its ID to the king, then, the king sums the IDs and returns the result to each client.

Integration

An example integration occurring against a blockchain can be found in our gadget. Here we hook up the mpc-net to an existing gossip network for a Substrate blockchain.

License

This library is released under the MIT License.

zk-saas's Issues

[TASK] Add packed secret sharing w/ randomness

Overview

Need to do packed secret sharing w/ randomness. Find and identify where in the paper or how that should be done in practice.

[TASK] Update the secret-sharing crate to account for missing shares

Liveness

Currently the code aborts if any party goes offline/sends the wrong share. Given that we use packed secret sharing, the degree of the polynomial used when secret sharing ist+l-1. When shares are multiplied the degree increases to 2(t+l-1). Thus if n>2(t+l)-1, we can tolerate parties dropping out.

Currently we use t=n/4, l=n/4, which means we can tolerate exactly one party dropping out, but this can be tuned based on network reliability, etc.

This requires some changes to the secret-sharing and mpc-net crates.

• Implement a time out for send_to_king(). When the king party is waiting to receive shares, they currently wait indefinitely to receive all the shares. Instead we should have a time out (can be chosen depending on network conditions etc.) When timeout occurs, there are two possible situations:
  1. fewer than threshold shares were received. In this case, we are forced to abort. Note that threshold needs to be specified by the calling function as sometimes, the threshold is t+l and at other times it is 2(t+l)-1.
  2. a threshold number of shares were received. In this case, we run the erasure correction algorithm with the shares that we have.
• Implement erasure correction in the secret-sharing crate.

Note about error correction: There is a lowerbound (Error Correction in the Exponent) showing that error correction in the exponent is not possible (apart from the naive exponential time solution). For small number of parties (10-20) we can potentially just carry out the brute force approach without too much overhead as the number of group elements we reconstruct is independent of the circuit size (at least in groth16).

[TASK] Fix Distributed FFT and Distributed MSM tests

Once we upgraded the networking, we were able to use intra-process tests instead of inter-process testing. Whereas the inter-process testing left room for errors not propagating, the intra-process tests did not. This allowed us to catch errors in the existing functions.

The DPP test (dist-primitives/examples/dpp_test.rs) works, and uses both the overhauled send_to_king and recv_from_king async functions. Thus, based on this test, we know these two functions work. However, the dFFT and dMSM tests (dist-primitives/examples/dfft_test.rs and dist-primitives/examples/dmsm_test.rs, respectively) fail at the very end when the assertions are made between expected and obtained results. Both these tests also use send_to_king and recv_from_king, which lead me to further believe that the issue lies not in the networking, but rather, the underlying mathematics somewhere.

[TASK] Compute `C` portion of Groth16 proof

Overview

Depends on #10, #11, #12

Computation

Paper

Page 38: https://eprint.iacr.org/2023/905

cannot enable `parallel` feature for groth16 crate.

Log:

error[E0596]: cannot borrow `*rng` as mutable, as it is a captured variable in a `Fn` closure
  --> /Users/shady/.cargo/git/checkouts/zk-saas-ea01b41c4efcba93/66c89b5/groth16/src/proving_key.rs:61:59
   |
61 |             .map(|chunk| pp.pack::<E::G1>(chunk.to_vec(), rng))
   |                                                           ^^^ cannot borrow as mutable

error[E0596]: cannot borrow `*rng` as mutable, as it is a captured variable in a `Fn` closure
  --> /Users/shady/.cargo/git/checkouts/zk-saas-ea01b41c4efcba93/66c89b5/groth16/src/proving_key.rs:64:59
   |
64 |             .map(|chunk| pp.pack::<E::G1>(chunk.to_vec(), rng))
   |                                                           ^^^ cannot borrow as mutable

error[E0596]: cannot borrow `*rng` as mutable, as it is a captured variable in a `Fn` closure
  --> /Users/shady/.cargo/git/checkouts/zk-saas-ea01b41c4efcba93/66c89b5/groth16/src/proving_key.rs:67:59
   |
67 |             .map(|chunk| pp.pack::<E::G1>(chunk.to_vec(), rng))
   |                                                           ^^^ cannot borrow as mutable

error[E0596]: cannot borrow `*rng` as mutable, as it is a captured variable in a `Fn` closure
  --> /Users/shady/.cargo/git/checkouts/zk-saas-ea01b41c4efcba93/66c89b5/groth16/src/proving_key.rs:70:59
   |
70 |             .map(|chunk| pp.pack::<E::G1>(chunk.to_vec(), rng))
   |                                                           ^^^ cannot borrow as mutable

error[E0596]: cannot borrow `*rng` as mutable, as it is a captured variable in a `Fn` closure
  --> /Users/shady/.cargo/git/checkouts/zk-saas-ea01b41c4efcba93/66c89b5/groth16/src/proving_key.rs:73:59
   |
73 |             .map(|chunk| pp.pack::<E::G2>(chunk.to_vec(), rng))
   |                                                           ^^^ cannot borrow as mutable

[TASK] Architecting networking layer and unimplemented work for zkSaaS

Overview

There's likely a lot in this repo that doesn't mesh with our existing architecture. We should identify them and implement what we can.

• https://github.com/guruvamsi-policharla/zksaas

Tasks

• Identify existing networking zkSaaS uses (it's likley for demo purposes)
• Identify if we want to implement MpcNet
• Implement MpcNet or solution.
• Identify how the existing distributed protocols work, and how we can best architect them for the future.

[TASK] Change the secret sharing crate to work over DomainCoeff

This would unify the secret-sharing methods for both field elements and group elements avoiding packexp and unpackexp

[BUG] PSS of Proving Key does not work if `L=2` but works if `L=4`

Basically the title of this issue.
In our test here proving_key::tests::packed_pk_from_arkworks_pk creating the PackedSharingParams with L=4 works, however, changing that to 2 makes this test panic with the following error message:

thread 'proving_key::tests::packed_pk_from_arkworks_pk' panicked at 'index out of bounds: the len is 14911 but the index is 14911', groth16/src/proving_key.rs:94:31

The error message clearly indicates a bug here:

zk-SaaS/groth16/src/proving_key.rs

Line 94 in 8701968

w_shares.push(packed_w[j][i].into());

Expected Beauvoir:
Test should work with any value of L.

[TASK] Compute the CRS share from the proving key by party index

Overview

Currently, we do compute the crs shares in the king and send the shares to the parties. However, to lower the set-up costs and the networking overhead, each party could just compute their share from the full proving key.

Task Checklist

• Refactor the code to compute the Proving Key share from the proving key
• Test the workflow with the new changes

[TASK] Compute `h(x)`

Overview

Computation

Assumptions

• Give every party the same $t(x)$. We don't need to worry about privacy right now.

Paper

Page 37: https://eprint.iacr.org/2023/905

[TASK] Test and verify against Sha256 circuit

[TASK] Audit and ensure privacy aspects are met

Overview

The foundation of the protocol is implemented but we may not have all parts of privacy handled, i.e. the f_rand protocol for secret sharing r,s of the Groth16 proof. We should audit/and task out what's remaining within this document and/or implement it if its not too challenging.

• Identify missing implementations for privacy purposes
• Update integration tests

[TASK] Add batch proof generation according to spec

Overview

From earlier discussions with @guruvamsi-policharla, we should implement a batched version of the protocol.

[TASK] Compute `B` portion of Groth16 proof

Overview

Computation

Paper

Page 38: https://eprint.iacr.org/2023/905

[TASK] Add process proving key from circom/snarkjs encoding

Overview

We have the packed process for the arkworks proving key, we should also add one for the circom key.

[TASK] Finish groth16 prover when using the libsnark witness map

The groth16 prover has been implemented end-to-end when using the circom wtiness map. When using the libsnark version, there is a slight difference in what is computed in the what's output, which requires a modification in the later "MSM" section of groth16.

[TASK] Add timers to packed proving key sharing / benchmarks

Overview

Add start and end timers to the process for sharing each portion so we can get idea of how long it takes wrt to the size of the proving key.

[TASK] Implement multi-threading at the King Server

The FFT2, packing/unpacking of shares should make use of multi-threading available at the king party. This should be trivially parallelizable (for the many secret being packed) and we can use the parallel implementation of FFT directly from arkworks for FFT2.

[TASK] Compute h

Currently, we do use h generated by the client on the preprocessing step and just PSS that to the parties. Instead, the goal of this task that we also have a way to compute h using the QAP, and it must match the h value from arkworks.

Task checklist

1. Make sure that P, Q, and W values are correctly computed.
2. Make sure we use a valid value of t(x) (refer to arkworks repo on how that gets generated)
3. Compare the generated h to the one from arkworks.
4. try to get the RHS to match the LHS somehow
   $$A.B - C = h(x).t(x)$$

[TASK] Find and integrate shamir secret sharing into zkSaaS repo

https://www.notion.so/hicommonwealth/zkSaaS-2f24ee23b31a449a9773f1e4c7756db9?pvs=4

Very possible Guru will add this this week although it might not be production worthy.

https://github.com/mikelodder7/vsss-rs (could be good to look into).

[TASK] Packed secret sharing the extended witness

Overview

Learn what the extended witness is and benchmark packed secret sharing

Packed secret sharing extended witness

• Witness are secret inputs
• Extended witness are the wire values of every single wire in the circuit.
• (Long-term optional MPC protocol) Many round computation
  • Secret share witness
  • Use MPC to compute the wire values

[TASK] Generate a Proving Key for the simple sha256 circuit example

We added a Simple sha256 circom circuit example for testing, we need to generate the proving key (zkey) for this circuit and put it in the solidity fixtures S3 so we can use during testing.

Use the scripts for phase 2 from https://github.com/webb-tools/protocol-solidity/blob/main/scripts/bash/groth16/phase2_circuit_groth16.sh or follow the instructions directly from https://github.com/iden3/snarkjs#7-prepare-phase-2

Tasks

• Bring in solidity-fixtures to this repo
• Use scripts to generate the setups
• Upload sha256 circuit fixtures
• PSS and setup the PackedProvingKeyShare structs.

[TASK] Asyncify and productionize the networking

Overview

Our stack relies on async networking so we ought to convert these distributed operations into async rust. All dist-primitives would be candidates for conversion.

First-order tasks

Make the networking usable and safe to operate in a production environment

• Async each distributed function
• Use cfg iter on iterators and parallelize as much as possible for multi-threaded performance
• Work over any Arkworks field and hash digest
• Streaming-friendly interfaces/functions. Large messages (millions of group elements) should be able to be streamed to receivers.
• Secure the transport layer (mTLS)

Second-order tasks

Integrate the ProdNet into a zkGadget

• Create a JobManager repository that can be used by both the DKG gadget and this repo
• Design protocol for handling job requests from a source (later, this source will be the blockchain)
• Combine both the job protocol and the ProdNet implementation to create a zkGadget

Misc tasks

• Benchmark and wrap long-running computations (>10ms) inside tokio::task::spawn_blocking to improve performance

[TASK] Fix how h is computed

The current version is insecure because the extended witness is reveal in the clear to the King. The correct way to do this can be found at https://github.com/arkworks-rs/groth16/blob/c7e8adec6101f0c51a042fa73f0e31dc344d1ab4/src/r1cs_to_qap.rs#L150.

• Cleanup the distributed FFT implementation and implement a coset FFT
• Fix how h is computed as described in the arkworks implemenation of groth16

[TASK] Reorganize tests

The tests could be organized better. Currently, we have them spread across dist-primitives/examples and individual modules such as dist-primitives/dfft/tests.rs. This was an artifact of the original zksaas repo needing a shell script to enable networking.

Given that we are no longer constrained by this, we can place all of the tests within individual modules -- dfft/dmsm/dpp and get rid of dist-primitives/examples entirely.

Also, dist-primitives/examples/dfft_test.rs is redundant in light of the more extensive set of tests in dist-primitives/dfft/tests.rs.

[TASK] Compute `A` portion of Groth16 proof

Overview

Computation

Paper

Page 37: https://eprint.iacr.org/2023/905

[CHECKLIST] Compute the Groth16 proof

Overview

The remaining steps to implement before we have a proof actually verifying (with/without privacy) in this repo is to compute h, A, B, and C. We can likely split this down separately and deliver separately.

Tasks

• #10
• #11
• #12
• #13
• #14