This document contains notes on Penumbra's upcoming decentralized zk-SNARK setup process. The setup process involves generating the proving and verification keys for each circuit. These circuit-specific parameters are $\sigma$ in the Groth16 paper, and elsewhere in the literature as the public parameters $pp$ or common reference string (CRS).

In Section 1 we discuss relevant previous work on MPC setup protocols. In Section 2 we describe the cryptographic details of the setup ceremony, generating the public parameters for the arkworks Groth16 crate. In Section 3 we describe the implementation details of the setup ceremony.

## 1. Previous Work

### Secure sampling of public parameters for succinct zero knowledge proofs *Ben-Sasson, Chiesa, Green, Tromer and Virza, 2015*

Key results:
* This is the setup that was used for the original ZCash setup ceremony, pre Groth16 (Sprout, Pinocchio).
* Contribution: Presents a ceremony that is secure provided only one participant is honest (i.e. a malicious majority can be present).
* Many round _synchronous_ ceremony where the number of rounds scaled with the number of participants e.g. for Zerocash $3n+3$ rounds (see end of Section I, subsection B in the paper).
* In the MPC protocol there is a precommitment phase, thus participants must be selected in advance when the protocol run begins.

Paper (PDF): https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=7163032

### Scalable multi-party computation for zk-snark parameters in the random beacon model *Bowe, Gabizon and Miers, 2017 (BGM17)*

Key results:
* Removes the precommitment phase required in Ben-Sasson et al. 2015, so participants do not need to be selected in advance
* New protocol "MMORPG": Massively multiparty open reusable parameter generation
* Scales to 100s-10,000s of participants
* 2 phase process: one generic and one circuit-specific
* Targets Groth16
* Requires a random beacon: "A random beacon produces publicaly available and verifiable random values at fixed intervals" - implementations often use something derived from the hash of a block
* System is open-participation: people can participate in phase 1, phase 2, or both. No private state needs to be maintained between messages.

impl: https://github.com/kobigurk/phase2-bn254/tree/master/powersoftau

Paper (PDF): https://eprint.iacr.org/2017/1050.pdf

### PLUMO Appendix C "Optimistic" SNARK setup

Key results:
* Builds on Bowe et al. 2017 (i.e. still uses random beacon).
* Targeted for doing a 2^27 size setup on ~700 bit curve, so needed optimizations.
* "Optimistic" setup means the participants can contribute simultaneously, instead of the Bowe et al. procedure wherein participant N+1 cannot contribute until participant N has finished.
* This is done by pipelining the contributions, e.g. if participant 1 is computing powers $i$ to $i + 10$, then participant 2 computes powers $i + 10$ to $i + 20$. Then they can exchange chunks.
* Has to carefully consider what happens when participants drop out during the pipeline. Adds complexity to handle this.

https://ethresear.ch/t/accelerating-powers-of-tau-ceremonies-with-optimistic-pipelining/6870
https://ethresear.ch/t/cheons-attack-and-its-effect-on-the-security-of-big-trusted-setups/6692 - attack on setups

impl: https://github.com/celo-org/snark-setup-operator

Paper (PDF): https://eprint.iacr.org/2021/1361.pdf

### Snarky ceremonies *Kohlweiss, Maller, Siim, and Volkhov, 2021*

Key results:
* Formally proves a modified version of BGM17 by not using a random beacon
* See Figure 6, page 17 (update algorithm), Figure 7, page 18 (verify algorithm)

Paper (PDF): https://eprint.iacr.org/2021/219.pdf

## 2. Setup

### Assumptions

* *Security assumption*: There exists at least one honest participant in the MPC setup ceremony. Honest means they follow the protocol, including destroying private data when required.

* If this security assumption is violated then the soundness of the proof system is broken, i.e. a malicious prover can generate proofs that will be accepted by the verifier.

### We need for `ark-groth16`:

* Per circuit the following structs:
https://docs.rs/ark-groth16/latest/ark_groth16/data_structures/struct.ProvingKey.html#
https://docs.rs/ark-groth16/latest/ark_groth16/data_structures/struct.VerifyingKey.html

* 0. Need to at pick some generators from each pairing group: $G \in G_1, H \in G_2$

* 1. Generate simulation trapdoor $\tau$:
* Sampled from Fq
* $\alpha$, $\beta$, $\gamma$, $\delta$
* $x$ evaluation point
* This is the toxic waste to be deleted

* ProvingKey ($G \in G_1, H \in G_2$):
* `beta_g1`: single element, $[\beta] G$
* `delta_g1`: single element, $[\delta] G$
* `a_query`: vec of elements, $[a_i] G$ ($a_i$ circuit-specific)
* `b_g1_query`: vec of elements, $[b_i] G$ ($b_i$ circuit-specific)
* `b_g2_query`: vec of elements, $[b_i] H$ ($b_i$ circuit-specific)
* `h_query`: vec of elements, $[h_i] G$ ($h_i$ circuit-specific)
* `l_query`: vec of elements, $[l_i] G$ ($l_i$ circuit-specific)

* VerificationKey:
* `alpha_g1`: single element, $[\alpha] G$
* `beta_g2`: single element, $[\beta] H$
* `gamma_g2`: single element, $[\gamma] H$
* `delta_g2`: single element, $[\delta] H$
* `gamma_abc_g1`: vec of elements, $[\gamma^{-1} (\beta a_i + \alpha b_i + c_i)] H$
* Notes compared with Groth16 paper (p.18):
* `alpha_g1`, `beta_g2` used to construct $[\alpha \beta]_T$

* Notation compared with Groth16 paper:
* $u_i$ in paper = $a_i$ in Groth16 lib
* $v_i$ in paper = $b_i$ in Groth16 lib
* $w_i$ in paper = $c_i$ in Groth16 lib

## MPC setup

We should use the MMORPG ceremony (Bowe et al. 2017), or the modified version presented for Groth16 in Kohlweiss21. The optimized ceremony presented in the PLUMO paper is targeted at very large circuits, but since our circuits are small, and the total contribution time is a few minutes (see back of the envelope numbers at the end of this document), then we don't really need this optimization.

### Parties

The parties involves are:
* N *participant*s $P$, who each add their contribution in order.
* The *Coordinator*, who verifies the contribution from each user after a new contribution is added, and hands out the latest version of the transcript to the next participant. The coordinator is untrusted.
* The *Verifier*, who checks that the coordinator acted correctly, i.e. they independently verify the transcript at every step.

The transcript is later published such that anyone can run the verifier code to check that the ceremony was performed correctly.

### Phase 1

The first phase is circuit-agnostic. Essentially this is powers of tau, i.e. wherein each participant generates $\tau_1$ (toxic waste), generates a vector ($\tau_1 G$, $\tau_1^2 G$, ..., $\tau_1^n G$). Each subsequent participant $i$ then takes the current vector and multiplies it by their own powers of $\tau_i$ such that we end up with: ($\prod_i \tau_i G$, $\prod_i \tau_i^2 G$, ..., $\prod_i \tau_i^n G$).

It would be good to start with a published powers of tau. Q: Is there a PoT that is BLS12-377? Probably Aleo?

Alternatively, we could run phase 1 and then phase 2 in series, e.g. phase 1 runs for 2 weeks, phase 2 runs for 2 weeks. Or, we run phase 1 until we have a target number of contributions.

If we follow Bowe et al. 2017, we use the protocol described in section 7.1:


Notes:
* Transcript here is a log of all messages from each participant $j$.
* "POK" here is a proof of knowledge that the participant actually knew the secret scalar, such that they cannot construct a maliciously crafted contribution that e.g. exactly cancels another or something similar.

### Phase 2

This phase is circuit-specific. This phase needs to be performed for each circuit, based on the results from phase 1.

If we follow Bowe et al. 2017, we use the protocol described in section 7.3:


## 3. Implementation

## Coordinator

* Rather than enqueue and contribute, the contribution command should idle. This way as soon as the previous contribution is complete, the ceremony will proceed. Thus the contribution process would occur very quickly.
* Single command `pcli zksetup contribute`:
* Open Grpc channel that holds a connection open and eventually hands the user the current transcript

### Coordinator needs to monitor for liveness

A malicious participant can try to prevent progress by buying a slot, and then taking a long time to complete the work, or never returning. We need to have a timeout such that we move on to the next participant if they do not provide their completed contribution within some time limit.

### Buying and selling contribution slots

Users should be able to buy contribution slots with testnet tokens:

* Coordinator wallet gets funds
* Coordinator wallet uses the sender field of the memo as the contributor ID
* Coordinator wallet can track which IDs are allowed to participate: coordinator stores a list sorted by amount of contribution grouped by address -- this sorted list is the contribution priority
* This prevents a malicious party from dominating the ceremony

* Coordinator in addition to `(contribution ID, amount of penumbra)` as described above also stores the latest version of the transcript, and the Penumbra address of contributor (i.e. contributor ID) is included as part of the transcript.

* We implement: `pcli zksetup contribute`:
* Provides latest version of the transcript
* Calls out to a crate we need to write (see below) that adds the user's contribution to the transcript

Could have a cool webapp like this if time permits: https://setup.aleo.org/

### Repos for reference

https://github.com/kobigurk/phase2-bn254/tree/master/powersoftau (Bowe et al. 2017 impl, i.e. uses beacon hash, audited at some point by NCC Group)

https://github.com/celo-org/snark-setup-operator/tree/main/src/bin (uses beacon hash)

https://github.com/iden3/snarkjs (not rust, no BLS12-377 support in phase 1)

https://github.com/AleoHQ/aleo-setup (uses beacon hash, not arkworks, audited at some point by Least Authority)

## Back of the envelope numbers

### Time

Using benchmark numbers in https://guide.penumbra.zone/main/dev/parameter_setup.html, our largest circuit (swap) is just shy of 38k constraints. So that's ~$2^{15}$ - $2^{16}$.

Using Figure 7.1, Bowe et al. 2017:
* Phase 1 time: ~2^6 seconds (1 minute), then about 3 minutes to verify
* Phase 2 proving time: ~2^4 seconds (16 seconds), then about 45 seconds to verify. We need to do phase 2 for each proof, but the other proofs are smaller and thus should be faster.

### Bandwidth

Using Table 1, page 21 in Bowe et al. 2017, the order of magnitude of the bandwidth cost is GBs (less in phase 2 but phase 2 needs to run for all circuits).

# TODOS

- [ ] e2e impl of phase 1 crypto (could be adapted from above repos)
- [ ] e2e impl of phase 2 crypto (could be adapted from above repos)
- [ ] impl of coordinator (server) role
- [ ] impl of verifier role (observes transcript and checks coordinator)
- [ ] pcli impl of `pcli zksetup contribute`