# DeFROST: Poseidon 🀝 βŒβ—¨-β—¨ ## TLDR We have designed a custom cryptographic scheme we call DeFROST to satisfy all Nouns DAO private voting requirements. The design grants voters an experience that is virtually identical to the DAO's current public voting experience. A crucial aspect of our design enables voting directly using a multisig (without requiring delegation), and supports delegate voting as well. Voting and tallying is done completely on Ethereum, with zero dependencies on other blockchains. Once voting is finished, tallying is triggered on-chain by a Nouns chosen (via Proposal) committee, requiring $t$ of $n$ committee members to submit a transaction enabling the governance contract to tally the votes. Chosen committee members can automate vote tallying transactions via an open-source script that will be provided. ## Team **DigitalOil.nftr** is a 2x Nouner. *Background*: B.S. EE @ Georgia Tech, S.M. EECS @ MIT. *Pre-Crypto*: Researcher @ MIT Retinal Implant Project, Satellite Communications engineer, iOS developer, Logistics conglomerate owner. Crypto: Investor since 2014. Founder of [NFTR](https://nftr.name), building Nouns (Props [199](https://nouns.wtf/vote/199), [241](https://nouns.wtf/vote/241), [The Panama DAO](https://prop.house/builder/dao-incubator-round-2/3300) -- winner of Nouns Builder Incubator), focus on ZK. **Shumo Chu** is a Nouner. *Background*: Ph.D. CS @ University of Washington. *Crypto*: Core contributor of [Poseidon](https://pdn.xyz/) and [Manta](https://www.manta.network/), ex-Research Scientist [Algorand](https://www.algorand.com/). *Academic*: ex-Assistant Professor at UCSB CS. Author of [ZEN](https://eprint.iacr.org/2021/087), one of the first ZKML papers (major technique was adopted by [WorldCoin](https://fc21.ifca.ai/index.php)), has published papers in major cryptographic conferences such as [ITC](https://itcrypto.github.io/2021/), [Financial Cryptography](https://fc21.ifca.ai/index.php). **Brandon H. Gomes** *Background*: Bachelor Physics and Math @ Rutgers University *Crypto*: Core Contributor of [Poseidon](https://pdn.xyz) and [Manta](https://www.manta.network) and creator of [OpenZL](https://openzl.org) **Boyuan Feng** *Background*: Ph.D. CS @ University of California, Santa Barbara *Crypto*: Core Contributor of [Poseidon](https://pdn.xyz) and [Manta](https://www.manta.network) and architect of [ZPrize](https://www.zprize.io/prizes/accelerating-elliptic-curve-operations-and-finite-field-arithmetic-wasm). Author of [ZEN](https://eprint.iacr.org/2021/087), one of the first ZKML papers, and [zkShuffle](https://hackmd.io/xj--HI7sTl2T3fbK1NONtQ) for enabling fully-onchain poker games. **Lucy Qiu** *Background*: Bachelor CS @ Rutgers University *Crypto*: Twice Eth Hackathon Sponsor Prizes Winner including top prizes from The Graph, Push Protocol, OP, Gnosis Chain, Covalent. **Sam Hu** *Background*: B.S. CS @ Tianjin University, S.M. CS @ Fudan University. *Pre-Crypto*: Maintainer @ Linux Kernel Network, Compiler Engineer, Hardware Designer. *Crypto*: Building IEEE 802.11i for wireless chips, four zk-based projects from scratch including spot/perpetual zk-rollup DEXs and ZK-privacy social/gaming. *[DigitalOil](https://twitter.com/0xDigitalOil) and [Poseidon](https://pdn.xyz) come together for this proposal, merging good understanding of the Nouns ecosystem, culture and its necessities with a cutting-edge ZK research team.* ## Poseidon Prior Work [Poseidon](https://pdn.xyz/)'s vision is to democratize zkDapps on Ethereum. Poseidon enables developers to build scalable zkDapps using pure solidity by leveraging our zkContract, SDKs, and ZK-ZK Rollup. Poseidon has partnered with [Consensys zkEVM](https://goerli.zkevm.consensys.net/explore) and [Cysic](https://cysic.xyz/) to build the next generation ZK Layer 3 which enables developers to build zkDApps on EVM The project most relevant to this proposal is our ZK Vote Demo App powered by Poseidon's zkContract and [semaphore](https://semaphore.appliedzkp.org/). This demo is deployed on Optimism Goerli / Consensys zkEVM Goerli: * DApp: https://www.zkvote.app/ * Demo video: https://www.youtube.com/watch?v=cS_YX8UHk74&t=1s * Code: * Frontend: https://github.com/Poseidon-ZKP/zkVote-web * Contract: https://github.com/Poseidon-ZKP/zkvote-contract * Snap/Prover: https://github.com/Poseidon-ZKP/zkVote-snap * Subgraph: https://github.com/Poseidon-ZKP/zkvote-subgraph * Relayer: https://github.com/Poseidon-ZKP/zkvote-relayer Note that the demo above is nearly compliant with the [requirements](https://hackmd.io/SVyDLBq7QSWNl0LaYIuqHA?view) for this round. The main issues with the scheme are: 1. It doesn't allow keeping voting power secret; 2. It isn't multisig friendly. For these reasons we have designed a custom scheme that complies with all specs. Our scheme is presented below. ## Background ### Which properties of Nouns DAO voting are currently public? 1. Voter's address 2. Voter's ballot (vote & voting weight). We define voting weight as: $$v_i = \# \text{ owned nouns} + \# \text{ delegated nouns} $$ As a result, there are 3 ways to make voting private: 1. Hide voter's address 2. Encrypt voter's ballot 3. Hide both ## Design Tradeoffs ### Hiding Voter's Address To hide a voter's address, the voting scheme must validate the voter's eligibity as well as prevent double voting. There are currently two schemes that allow for this: 1. [Semaphore](https://semaphore.appliedzkp.org/): Semaphore is a protocol designed by Ethereum Foundation's Privacy & Scaling Explorations group. It combines a private identity group (anonymity set) with a nullifier scheme. 2. [ECDSA ZKP](https://github.com/0xPARC/circom-ecdsa) + [Deterministic Nullifers](https://github.com/zk-nullifier-sig/zk-nullifier-sig): Semaphore requires keeping an extra secret and private identity in addition to the user's Ethereum private key. This scheme solves provides an alternative solution by directly generating a ZKP of the voter's Ethereum account combined with a ZK nullifier based on a deterministic signature scheme over ECDSA. Despite solving for lower user friction, existing ECDSA ZKP and ZK nullifier implementations are far from practical due to the burden of expensive non-native arithmetics (secp). For example, the most efficient ECDSA proof on a native Ethereum curve requires a ~1GB proving key and has a 45 sec proof generation time on a 16-core 3.0GHz, 32G RAM machine (AWS c5.4xlarge instance). There are more efficient ECDSA proofs on non-Ethereum native curves such as Spartan-ECDSA [[4](#Reference)]. However, to use Spartan-ECDSA, you would need to build a rollup scheme to transform the Spartan-ECDSA proof to a Groth16/Plonk Proof on Ethereum's native BN256 curve. There are two common pitfalls with both schemes: 1. Hiding only addresses won't give the scheme a sound privacy guarantee. For example, if a Nounder holds a great number of Nouns, despite the voting address being hidden, an external observer can still infer their vote from their voting weight. 2. Both schemes cannot support Nouns held in smart contract wallets such as Gnosis SAFE. Both schemes requires a explicit delegation from a smart contract account to either a EOA (ECDSA ZKP approach) or Semaphore Identity (Semaphore approach). ### Encrypting Ballots An alternative design option is to encrypt the voting ballots instead of the voter's address. There are two challenges with designing a ballot encryption scheme for private voting: 1. The final vote tally should only disclose the aggregated voting result instead of individual votes. 2. The decryption/tallying should only happen after voting ends. For example, if the scheme reveals the aggregated result in "real time", then individual votes will still leak via the diff of two aggregated contiguous results. ### Our Design Choice Our proposed scheme, called [DeFROST](#DeFROST-Design), solves these challenges by combining FROST [[1](#Reference)]'s distributed key generation (DKG) scheme and threshold homomorphic encryption (tHE) to encrypt ballots, but keeps the voting account public. The scheme is trustless in two senses: 1. The soundness of the scheme is guaranteed by the cryptographic construction. 2. The confidentiality of the ballots is guaranteed if no more than $t-1$ out of $n$ tally committee members collude. The great benefit of encrypting ballots while keeping the voting account public is that it allows users to vote using their public account (i.e. EOAs or smart contract wallets). That is, this solution supports vote delegation and smart contract wallets such as Gnosis SAFE without introducing any user friction. Nouns DAO governance currently depends heavily on delegation + a vast number of Nouns are held in smart contract wallets. Below is the onchain data at snapshot of block 16672087. ![](https://i.imgur.com/SoLwPg8.png) ![](https://i.imgur.com/VtgXUny.png) ~15% of nouns are held in smart contract wallet, and ~55% nouns holders delegate their voting power. ### Hiding both voting addresses and ballots We could combine the approaches of [hiding voters' addresses](#Hiding-Voter's-Address) and [encrypting ballots](#Encrypting-Ballots). This would gain further privacy guarantees: not only the ballot is private, the fact that whether a user has voted or not is also hidden. However, it is debatable whether DAO governance benefits enough given the friction it introduces. It is even arguable that Nouners do want visibility of who voted and who didn't. For these reasons, our design sticks to ballots being private but keeping voter addresses public. ## DeFROST Design $\newcommand{\FF}{\mathbb F} \newcommand{\GG}{\mathbb G} \newcommand{\ggen}{G} \newcommand{\ZZ}{\mathbb Z}$ ### Overview This design has two types of participant: - **committee members** ($n_{com}$ members in total) who hold a secret share, used to decrypt vote totals - **users** or **voters** (a total of $n_{user}$) who cast votes (Nouns holders and delegates) Committee members need to perform a one-time **Distributed Key Generation (DKG)** to setup $1$ shared public key $Pk$ and $n_{com}$ secret keys $sk_i$. The public key is public to all committee members and voters. Each secret key is owned by a committee member and used for the final vote on-chain tally. Once users have the public key, they can use it for private voting with **Threshold Homomorphic Encryption**. Once the voting ends, we require $t$ out of $n_{com}$ commitee members to each submit an on-chain transaction. ### Distributed Key Generation by Committee We use FROST [[1](#Reference)] for a two-round distributed key generation. This requires only commitee members to participate, and happens only once. The generated public key and secret keys are reused for voting across multiple proposals. Before distributed key generation, the threshold $t$ must be determined. This represents the number of committee members required to fully decrypt the vote tally. Let $\GG$ be the **subgroup** of the BabyJubjub curve of prime order $r_B = 2736030358979909402780800718157159386076813972158567259200215660948447373041$, with generator a chosen generator $\ggen$. Let $r_{BN}$ be the scalar field of the BN128 curve, which is also the base-field of the BabyJubjub curve. We note that $\FF_{r_B}$ is a field, but since $r_B < r_{BN}$, elements in $\FF_{r_B}$ may have multiple representations in $\FF_{r_{BN}}$. Care must therefore be taken to ensure that: - a prover cannot choose multiple witnesses satisfying a given circuit, and - scalar multiplication (in particular where the scalar factors are the result of field operations) is correctly performed. Committee members are indexed $1, \ldots, n_{com}$, and we often refer to participants by their index (which is also used as an ID for the participant). **Round 1** Each participant $i = 1, \ldots, n_{com}$: - generates $a_{i,0} \in \FF_{r_B}$ in a deterministic way, using their Ethereum wallet - samples $t-1$ random values $(a_{i,1}, \cdots, a_{i, t-1}) \leftarrow \FF_{r_B}$ and defines a degree $t-1$ polynomial $$f_i(x) = \sum_{j=0}^{t-1}a_{i,j}*x^j \in \FF_{r_B}[x]$$. - computes a public commitment $\vec{C_i} = \langle C_{i,0}, \cdots, C_{i,t-1}\rangle \in \GG^t$ to the coefficients of $f_i$, where $C_{i,j} = a_{i,j}\cdot \ggen$, and submits $\vec{C_i}$ to a DKG contract on-chain. The DKG contract checks the well-formedness of the commitments and stores them on-chain. It also computes the *committee public key* $PK = \sum_{i=1}^{n_{com}} C_{i,0}$. **Round 2** For $i=1,\ldots,n_{com}$, participant $i$ performs the following operations: - for each participant index $l=1,\ldots, n_{com}$ (including $i$): - compute $f_i(l)$, which is $l$'s share of $i$'s secret $a_{i,0}$ from Round 1 - encrypt $f_i(l)$ using $l$'s public key $C_{l,0}$ (read from the DKG contract) as follows: 1. \\( eph_{sk} \overset{\$}\leftarrow \FF_{r_B} \\) 1. $eph_{pk} \leftarrow eph_{sk} \times \ggen$ 1. $SK \leftarrow eph_{sk} \times C_{l,0}$ 1. $b \leftarrow poseidon(SK[0])$ - **Note (confirm):** No need for a sponge or more complex structure, since we'll use a ZKP to ensure correctness of the ciphertext. - **Note:** the types here are: $eph_{pk}$ has coordinates in $\FF_{r_{BN}}$, and the output of poseidon is an element $b \in \FF_{r_{BN}}$ 1. $c \leftarrow \FF_{r_{BN}}(f_i(l)) + b$ - **Note:** $b \in \FF_{r_{BN}}$, so addition should be mod $r_{BN}$ here 1. return $(c, eph_{pk})$ - denote the encrypted share for participant $l$ by $(c_{i,l}, eph_{pk_{i,l}})$ - compute the commitment $PK_{i,l} = f_i(l) \cdot \ggen \in \GG$ to $f_i(l)$ - create a ZKP $\pi_{i,l}$: - public inputs: $c_{i,l}$, $eph_{pk_{i,l}}$, $PK_{i,l}$, $l$, $\{ C_{i,k} \}_{k=0}^{t-1}$ - statement: - $PK_{i,l} = f_i(l) \cdot \ggen = \sum_{k=0}^{t-1} l^k\cdot C_{i,k}$ - **Note:** Use Horner's method to avoid computing $l^k \mod r_B$ (non-native arithmetic) in the circuit. - **Note:** $PK_{i,l}$ can be computed by any observer, using the public $C_{i,k}$ terms. By including this in the ZKP, the contract can verify and store $PK_{i,l}$ without having to perform BabyJubjub arithmetic in the EVM. - $c_{i,l}, eph_{pk_{i,l}}$ is generated as in the encryption algorithm above. In particular, the statement must show that $eph_{pk} = eph_{sk} \cdot \ggen$. - send $(c_{i,l}, eph_{pk_{i,l}}, PK_{i,l}, \pi_{i,l})$ to the DKG contract. On receipt of $(c_{i,l}, eph_{pk_{i,l}}, PK_{i,l}, \pi_{i,l})$ from participant $i$, the DKG contract must: - verify $\pi_{i,l}$, where the public inputs $\{ C_{i,k} \}_{k=0}^{t-1}$ are provided using the values stored by the contract during Round 1. - accumulate $PK_l \leftarrow PK_l + PK_{i,l}$. After all shares for all pariticipants have been submitted, the contract holds $PK_l$ for each $l=1,\ldots,n_{com}$, which is $l$'s public share of the ephemeral secret $sk = \sum_{i=1}^{n_{com}} a_{i,0}$. The contract also holds the public key $PK$, computed during Round 1, where $PK = \sum_{i=1}^n C_{i,0} = sk \cdot \ggen$. Finally, each participant $i$ calculates their long-lived secret key $sk_i \in \FF_{r_B}$ by decrypting each $c_{l,i}$ to reveal $f_l(i)$ and computing $sk_i = \sum_{l=1}^{n_{com}} f_l(i)$. $sk_i$ is stored securely. - **Note:** the use of $\FF_{r_{BN}}$ arithmetic in decrypting the secrets in $\FF_{r_B}$. As a result, each commitee member holds a secret key $sk_i \in \FF_{r_B}$ with corresponding public key $PK_i \in \GG$, which is a Shamir share of the *committee public key* $PK$. Voters will this use when submitting their private votes on-chain. > Note: Since all encrypted secret shares are retained on-chain, any committee member $i$ may reconstruct their secret key $sk_i$ as long as they retain access to their coefficient $a_{i,0}$. By generating this coefficient from their committee members Ethereum key in a deterministic way, committee members are provided with a recovery process (as long as they retain control of their Ethereum address). > Note: The *committee secret key* $sk \in \FF_{r_B}$ corresponding to $PK$ could theoretically be used to decrypt private votes encrypted with $PK$, however it is unknown to any individual participant. $sk$ could only be reconstructed if $t$ or more of the total $n_{com}$ members collude by sharing their secret keys $sk_i$. ### Committee Process Flow The committee setup process will be fully on-chain. A proposer will submit a proposal to the DAO that sets the following parameters in the committee contract: $n$, $t$, and committee member wallet addresses. To modify those parameters (i.e. do key rotation), a new Nouns prop would need to be submitted and pass. The software required to run a committee "node" will be open-source and a GUI will be provided to facilitate key generation (for Rounds 1 & 2), submit the transaction for vote tally, as well as setting up a committee instance that performs these processes on AWS or a trustless computation environment. ## Snapshot Voting Power The governance contract takes a snapshot at the block number when the proposer submits the proposal on-chain. This snapshot stores a mapping between Ethereum addresses (could be either EOA or contract) and their corresponding voting power. ## Private Voting by Users Voters use the shared public key $PK$, generated during the DKG, for private voting protected by ZKPs and Threshold Homomorphic Encryption. During voting, users need only send 1 message to the governance contract. Let $v_i$ be the voting power of the $i$-th user, according to the snapshot. Voter $i$ performs the following steps: - sample random \\(\vec{r_i} \overset{\$}{\leftarrow} \FF_{r_B}^3\\) - encode the vote as a (secret) $o_i \in \{0,1\}^3$ using the *1-hot* format, where: - *yes* is represented as $o_i = 100$, - *no* is represented as $o_i = 010$, - *abstain* is represented as $o_i = 001$. - generate $(\vec{R_i}, \vec{M_i}) \in (\GG^3 \times\GG^3)$ where: - $R_{i,k} \leftarrow r_{i,k} \cdot \ggen$ for $k=1,2,3$. - $M_{i,k}=(o_{i,k}*v_i)\cdot \ggen + r_{i,k} \cdot PK$ for $k=1,2,3$. - generate a ZKP $\pi$: - public inputs: $PK$, $v_i$, $\vec{R_i}$, $\vec{M_i}$ - statement: - knowledge of $\vec{r_i} \in \FF_{r_B}^3$ such that $\vec{R_i} = \vec{r_i} \cdot \ggen$ - knowledge of vote $o_i = (o_{i,1}, o_{i,2}, o_{i,3}) \in \{0,1\}^3$ such that: - $o_{i,k} * (1 - o_{i,k}) = 0$ for each $k=1,2,3$ (in other words, $o_{i,k} \in \{0,1\}$) - $o_{i,1} + o_{i,2} + o_{i,3} = 1$ (exactly one bit of $o_i$ takes value 1) - $M_{i,k}=(o_{i,k}*v_i)\cdot \ggen + r_{i,k} \cdot PK$ for $k=1,2,3$. - call the governance contract passing $(\pi, \vec{R_i}, \vec{M_i})$. On receiving $(\pi, \vec{R_i}, \vec{M_i})$ from the voter, the governance contract: - checks that the voter's account has not already voted for the proposal - verifies the proof $\pi$, where public inputs $PK$ come from the contract's on-chain storage, and $v_i$ is verified on-chain against a snapshot. - accumulates $\vec{R} \leftarrow \vec{R} + \vec{R_{i}}$ and $\vec{M} \leftarrow \vec{M} + \vec{M_i}$ When all participants have voted, the contract holds $\vec{R} = \sum_{i=1}^{n_{u}} \vec{R_{i}}$ and $\vec{M} = \sum_{i=1}^{n_{u}} \vec{M_i}$. Denoting $\vec{r} = \sum_{i=1}^{n_{u}} \vec{r_i}$ and $\vec{v} = \sum_{i=1}^{n_{u}} v_i * \vec{o_i}$, we have $\vec{R} = \vec{r}\cdot \ggen \in \GG$ and $\vec{M} = \vec{v}\cdot \ggen + \vec{r}\cdot PK \in \GG$. During the vote tally process, $t$ committee members will reveal the vote totals $\vec{v}$. > Note: Any number of users could participate in voting by using the same $PK$. #### Vote Delegation From the design, DeFROST supports vote delegation by default. Since the addresses are public, DeFROST handles the delegation exactly the same as the existing Nouns governance contract. #### Smart Contract Wallet DeFROST supports smart contract wallets in a straight forward manner: the smart contract wallet signs the enrypted vote. Take a 2/3 Gnosis SAFE multisig as an example, 3 members negotiate offchain about the voting result, encrypt it with the public key, and then simply sign the encrypted vote using the Gnosis SAFE in the same way a usual transaction is signed. #### Modalities DeFROST supports both public and private voting modalities. The governance contract can use DeFROST to incorporate optional private voting due to our public address / private ballot design choice. Public votes and private votes can be tallied separately and subsequently added together within the contract. ## Vote Tally by Committee Members Vote tally requires that $t$ out of $n_{com}$ committee members to participate. Committee members communicate with the governance contract and do not require secure p2p communication channels. During the vote tally, each committee member (indexed by $i$): - queries $\vec{R}$ from the chain - computes $\vec{D_i} \in \GG^3$ as $D_{i,k} = sk_i * R_k$ for $k=1,2,3$. - creates a ZKP $\pi$: - public inputs: $\vec{D_i}$, $\vec{R}$, $PK_i$ - statement: knowledge of $sk_i$ s.t. - $\vec{D_i} = sk_i \cdot \vec{R}$ - $PK_i = sk_i \cdot \ggen$ - sends a transaction containing $(i, \vec{D_i}, \pi)$ to the voting contract The voting contract, on recipt of $(i, \vec{D_i}, \pi)$: - verifies the proof, where the public input $PK_i$ and $\vec{R}$ are taken from on-chain storage, - write $(i, \vec{D_i})$ into contract storage When $t$ such messages have been received, the contract should also: - let $I$ be the subset of ID of committee members who have sent such a message (where $|I| = t$). - compute $\vec{D} = \sum_{i \in I} \lambda_i \cdot \vec{D_i}$ where $\lambda_i = \prod_{j\in I, j\neq i}\frac{j}{j-i}$ is the Lagrange coefficient for $i$ over the set $I$. - reveal the encoding of the vote totals: $\vec{v}\cdot G = \vec{M} - \vec{D}$ - use a lookup table to extract $\vec{v}$ from $\vec{v} \cdot G$ > Note 1: The indices $i\in I$ must match those used during Distributed Key Generation. > Note 2: The expression for $\lambda_i$ comes from the use of Lagrange interpolation to recover $sk \times \vec{R}_i$. This process uses Lagrange polynomials $\lambda_i(x) = \prod_{j\in I, j\neq i}\frac{x-j}{i-j}$ evaluated at $0$, whereby $\lambda_i = \lambda_i(0) = \prod_{j\in I, j\neq i}\frac{j}{j-i}$. ### Voter/Committee Workflow ```mermaid sequenceDiagram participant U as Voter participant CC as Contract participant C as Committee rect rgba(0, 220, 220, .3) C -->> C : a[N_COM] as secret C -->> C : f[N_COM] = langrange-poly(a) C -->> C : C = a * G C -->> CC : C[N_COM] as public Commitments CC -->> CC : PK += C[0] end rect rgba(0, 110, 220, .3) C -->> CC : (proof, enc(f0[1])) = zkp(r0, f0[1], C1[0]) CC -->> C : f1[0] = dec(enc(f1[0]), C0[0]) C -->> C : sk0 = f0[0] + f1[0] end rect rgba(0, 220, 110, .3) U -->> CC : (proof, R, M, v) = zkp(r, o, v, PK) CC -->> CC : check user using valid vote power CC -->> CC : R_sum += R, M_sum += M end rect rgba(0, 110, 110, .3) C -->> CC : D = sk * R_SUM CC -->> CC : D_SUM += D CC -->> CC : reveal v by lookup v * G = M_SUM - D_SUM end ``` ### Protoype Contracts and Circuits We developed prototype contracts and circuits with voting and tallying working end-to-end (not including a front-end). DeFROST Prototype: 1. Circuits: https://github.com/Poseidon-ZKP/zkvote-contract/tree/nouns/circuits 2. Contracts: https://github.com/Poseidon-ZKP/zkvote-contract/tree/nouns/contracts/nouns 3. SDK: https://github.com/Poseidon-ZKP/zkvote-contract/tree/nouns/scripts/nouns ## Proving Compute & Gas Requirements Suppose $n_{com} = 21$, $t = 10$, and jubjub $scalar_{mul} =$ ~$1000$，posedion hash ~$300$ 1. Round 2 has a larger but only 1-time ZKP constraints 2. Smaller ZKP for user voting 3. ～$200$k fixed Groth16 verification gas, $6$k more gas for each public input 4. The estimate doesn't include basic circuit overhead (~$6$k) and contract decrypt / reveal logic cost |Stage| add/mul/exp| Scalar mul (jubjub) | Posedion hash | Constraint | Public Input | Verify Gas | | --- | ---- | --- | ---- | --- | --- | --- | | Round2 | $(n-1)*t$ | $(n-1)*t$|$(n-1)*4$ | $224$k | $2t+1$ | $326$k | | Voting | | $5$ | | $5$k | $10$ |260k | | Tally & Reveal | $(n-1)$ | $1$ | $(n-1)*4$ | $2$k | $2*n+2$ |464k| ### Further Reducing Gas Cost Gas cost could be further reduced: 1. Snapshoting voting power using zk-coprocessor Axiom [[5](#Reference)]. 2. Using Poseidon's ZK-ZK Rollup [[6](#Reference)] to reduce ZKP verification cost. ## How Does DeFROST Meet Nouns DAO Requirements? | Requirement | Type | Met | Notes | | -------- | -------- | -------- |-------- | | Privacy preserved forever | Must |βœ“ | [source](https://hackmd.io/6ZFxxxnKT0iH-GJHUxKekw#Overview) | | Voting power unexposed | Must |βœ“ | [source](https://hackmd.io/6ZFxxxnKT0iH-GJHUxKekw#Overview) | | Impossible to tally before voting period ends | Must |βœ“ | [source](#Vote-Tally-by-Committee-Members) | | Should support delegates | Must |βœ“ | [source](#Vote-Delegation) | | Double voting impossible | Must |βœ“ | [source](#Encrypting-Ballots) | | Support multisigs | Must |βœ“ | [source](#Supporting-Delegate-and-Smart-Contract-Wallet) | | Avoid centralized dependencies | Must |βœ“ | [source](#Distributed-Key-Generation-by-Committee); tallying trigger depends on a sufficiently decentralized committee if $t$ and $n$ are chosen large enough. Committee member work can be automated.| | Should not require a per-prop trusted setup | Must |βœ“ | [source](#Private-Voting-by-Users) | | Should be scalable | Must |βœ“ | [source](#Proving-Compute-amp-Gas-Requirements) | | Not every token holder required to vote | Must |βœ“ | [source](#Optionalities) | | Should not require admin to trigger steps during voting | Must | βœ“ | [source](#VoterCommittee-Workflow) | | The output must be the vote tally of each proposal| Must | βœ“ | by ZKP | | should not have to transfer voting power to a 3rd party smart contract | Nice to have | βœ“ | [source](#VoterCommittee-Workflow) | | should not have to bridge Nouns to a rollup or another chain | Nice to have | βœ“ | [source](#VoterCommittee-Workflow) | | should be able to vote with a single submission of an Ethereum tx | Nice to have | βœ“ | [source](#VoterCommittee-Workflow) | | should not be required to perform additional pre-voting steps | Nice to have | βœ“ | [source](#VoterCommittee-Workflow) | | Support some voters choosing to vote publicly | Nice to have | βœ“ | [source](#Optionalities) | | Voting (proof submission) should occur on Ethereum mainnet | Nice to have | βœ“ | [source](#VoterCommittee-Workflow) | | Should rely solely on proofs, and not include a dispute period to achieve finality | Nice to have | βœ“ | [source](#VoterCommittee-Workflow) | ## Reference [1] Chelsea Komlo and Ian Goldberg, *FROST: Flexible Round-Optimized Schnorr Threshold Signatures* [[paper](https://eprint.iacr.org/2020/852)] [2] Dmitry Khovratovich, *Encryption Using Poseidon*, [[paper](https://dusk.network/uploads/Encryption-with-Poseidon.pdf)] [3] Aayush Gupta and Kobi Gurkan, *An ECDSA Nullifier Scheme for Unique Pseudonymity within Zero Knowledge Proofs*, [[paper](https://eprint.iacr.org/2022/1255)] [4] Personae Labs, *Introducing Spartan-ECDSA*.[[blog](https://personaelabs.org/posts/spartan-ecdsa/)],[[code](https://github.com/personaelabs/spartan-ecdsa)] [5] Axiom's Nouns Voting Proposal: https://hackmd.io/@yisun/SkJd0bz6s [6] Poseidon ZK-ZK Rollup. [[website](https://pdn.xyz/#rollup)]