# al
Submitted on March 6, 2023

### Table of Contents
[1. Proposal's Team](https://hackmd.io/@H5U2gXZmRRugoNU0zaLeIg/S1cN94Q1n)
2. Summary of Private Governance Scheme
3. Aztec Noir
4. Optimistic Zero Knowledge
5. ECDSA
6. Storage Proofs
7. Vote Encryption and Tallying
8. Vote Decryption
9. Summary of Requirements Engineering (TL;DR:)

## Summary of Private Voting Scheme
@todo
## Aztec Noir
Mach 34, the applicant of this proposal, previously [partnered with Aztec for the proliferation of full-stack developer resources](https://www.youtube.com/watch?v=25_FzjlG7ZU&list=PLabpoAlaCBY3SM6xHmZCOhPHlmLB4EY6H). Aztec Noir is a new Zero Knowlede DSL (domain-specific language) that (in our opinion) is the closest attempt to ergonomic Zero Knowledge development in existence. Further, in-browser IVC recursion and the efficient UltraPlonk offers performance that begins to approach Halo 2.

**Why DSL's?**
Though Zero Knowledge DSL's will never be as efficient as pure SDK's for generating Zero Knowledge proofs like Halo2, they make up for it in ease of use. More specifically, DSL's try to make using zero knowledge proofs as close to traditional programming as possible. The ratio of ZK Devs capable of weilding DSL's to ZK Devs capable of working with the most complex proving systems will continue to grow in favor of DSL's. Therefore, unpredictable long-term maintenance costs will intrinsically be lower using DSL's.

Generally, DSL's also come with built-in onchain verification contract generation. This is the case for Aztec Noir on the EVM. UltraPlonk proofs cost about 400,000 gas to verify onchain, however this cost can largely be circumvented with optimistic zero knowledge.

**Why Aztec Noir**
There are a lot of features we like about Aztec Noir, however, this is not a sales pitch. Aztec Noir is the right choice for the job for two reasons:
* Aztec Noir's UltraPlonk is currently the only DSL to offer performance approaching that of Halo2
* Aztec UltraPlonk enables efficient ECDSA/ Keccak verification that [Circom currently can't facilitate](https://github.com/0xPARC/circom-ecdsa)

Beyond purely technical qualifications, (in case this proposal is funded) **This propsal is supported by Aztec Network. Most importantly, Aztec will commit developers to safely implementing any cryptographic **. Mach 34 has an open line of communication with Aztec and can also use the relationship to solicit advice on implementation details for the Nounsdao Private Voting Scheme.

## Optimistic Zero Knowledge
Zero Knowledge and Optimsm are not mutually exclusive. With Aztec Noir's UltraPlonk proofs coming in at a cost of 400,000 gas per proof, using Zero Knowledge alone will result in Nouns's gas usage skyrocketing. Nounsdao's governance has little need for instant finality for individual votes or proposal actions. Therefore, instead of verifying zero knowledge proofs onchain, we only post the proofs onchain. If a fraudulent ZK proof is posted, anyone with access to Ethereum can pay the gas fee to verify the invalidity of the proof in the EVM. Financial stake or bans can be used to punish adversarial behavior.

There are multiple places where optimistic zero knowledge can be integrated:
* Snapshot proof - account storage root caching when proposing
* Vote proof - ZK proof of nouns voting correctness
In this proposal, we only use optimism for the snapshot proof. This is not even a ZK proof verification, rather, it is a critical input to our vote proofs. The calculation of this root can be made optimistic since there is already a long voting period where the validity of the cached root can be challenged.

Credit to the [NounsVortex](https://prop.house/nouns/private-voting-research-sprint) proposal which proposes an "[Nounism](https://mizu-dao.github.io/vortex/chapter_4_2.html)", which uses an optimistic proving layer instead of verifying every proof. On that subject, we believe that this is the most powerful L1 scalability feature possible. The scope of our work will not cover integrating "Nounism" for vote proving, however, future iterations of our proposal use `@curryrasul`'s and `@levs57`'s novel ZK scalability technique.

## ECDSA
Most blockchains use ECDSA key pairs on the secp256k1 curve. In the past, [ECDSA in zero knowledge circuits has been prohibitively expensive](https://0xparc.org/blog/zk-ecdsa-1). However, these benchmarks reflect the cost of verifying ECDSA signatures inside Groth-16 circuits. [UltraPlonk](https://zcash.github.io/halo2/concepts/arithmetization.html), a PLONK variant optimized with “lookup tables” and “custom gates”, offers ECDSA signature verification in ~36,000 constraints (measured in Aztec Noir). This sort of verification can be performed in the browser in a matter of seconds. The desire for hardware compatibility combined with the recent innovations in ZK ECDSA verification led us to recommend the use of ECDSA over "Zero-Knowledge friendly" curves/ signing.

ECDSA is already used on-chain, so we need it to prove provenance over the nouns voting weight we proved to exist in the storage proof. In order to facilitate multisignature wallets, we need to employ a “[threshold signature scheme](https://blog.pantherprotocol.io/threshold-cryptography-an-overview/)”. Until recently, the underlying “[verifiable secret sharing](https://medium.com/nethermind-eth/a-tour-of-verifiable-secret-sharing-schemes-and-distributed-key-generation-protocols-3c814e0d47e1)” mechanic needed for the multiparty computation required synchronicity. In our context, this means that all the keyholders of a multisig that owns Nouns would need to be online at the same time to trustlessly compute a shared key. Novel innovations in “asynchronous verifiable secret sharing” [[GS23]](https://eprint.iacr.org/2022/506.pdf) have recently paved the way for [practical ECDSA threshold signatures](https://medium.com/dfinity/threshold-ecdsa-the-key-ingredient-behind-the-internet-computers-bitcoin-and-ethereum-cf22649b98a1) that meet the requirements of the Nounsdao private governance spec.

For total trustlessness, GS23 prescribes a consensus layer for the ordering and availability of the secret share commitments made by each key holder. However, GS23 considers distributed key generation in a highly adversarial environment. In the case of multisig wallets holding Nouns tokens, we believe that each keyholder’s incentives are aligned such that the holders can reach a consensus on secret commitment ordering through private but centralized means. Should research and/or experience reveal that incentives are misaligned, we would employ our novel Zero Knowledge State Channel construction to facilitate the correct ordering of transactions. These state channels can reside in centralized, end-to-end encrypted databases to ensure the liveliness and correctness of an ephemeral state computation without paying gas.

Note on Recursion: Aztec Noir will eventually support [PCD recursion](https://tlu.tarilabs.com/cryptography/trustless-recursive-zero-knowledge-proofs#proof-carrying-data); with this improvement, we will be able to construct a “Key Provenance” proof that allows an ECDSA key to prove ownership of an EdDSA key. This can be combined with the storage proof to authorize the use of voting weight for “free” (we needed to do this for key provenance anyways).

A similar construction can be used to enable true multisignature wallets, where this implementation proposes the use of multi-party computation to emulate the desired functionality of a multisignature wallet in Zero Knowledge. This would enable the key holders of a multisignature wallet to asynchronously commit their signatures to a given vote without the online requirements of MPC for distributed key generation.

PCD recursion allows us to [treat the process of a top-level proof recursing subproofs in a nearly identical way to main functions calling helper functions](https://www.youtube.com/watch?v=6mcCyQXm8vo), and the availability of PCD recursion should prompt Nouners to evaluate how the functionality of their private governance can be augmented.
## Storage Proofs
<div style="text-align:center;">
<img src="https://i.imgur.com/9tckCXx.png" alt="Storage Slots">
<p><em><a href="https://programtheblockchain.com/posts/2018/03/09/understanding-ethereum-smart-contract-storage/">Mental Model for EVM Storage Slots</a></em></p>
</div>

If you’re familiar with traditional operating systems, you might know that computers store information in “[memory addresses](https://www.techopedia.com/definition/323/memory-address)”, with each address holding 8 bits (1 byte). The Ethereum Virtual Machine (EVM) emulates this with “[storage slots](https://programtheblockchain.com/posts/2018/03/09/understanding-ethereum-smart-contract-storage/)”. Every piece of data residing on Ethereum’s blockchain is indexed in one or more storage slots. Storage proofs, which are a superset of account proofs, can convince a verifier of the state of some variable inside an Ethereum smart contract at a given point in time. In the case of NounsDao, it means that we can convince a zero knowledge verifier of a Nouns holder's vote weight.

Asides from an additional step of snapshotting the account storage proof (see below), ERC721Checkpointable.sol provides us with everything we need to extract the votes a given holder can control at any given point in time. Specifically, the [`Checkpoint` struct’s `votes` field](https://github.com/nounsDAO/nouns-monorepo/blob/master/packages/nouns-contracts/contracts/base/ERC721Checkpointable.sol#L49) is the data we are targeting for Nouns storage proofs. This enables intrinsic support for delegate voting using the existing sum of votes available to a given Nouner, rather than trying to evaluate the tokens held. This requires delegation to be public, however, we understand this to be acceptable or even desired tradeoff.

<div style="text-align:center;">
<img src="https://i.imgur.com/V3q05JH.png" alt="Account State Roots">
<p><em><a href="https://arxiv.org/pdf/2108.05513.pdf">Traversing the EVM to a storage slot</a></em></p>
</div>

The full traversal of the block header to the smart contract's account state root can be documented completely with the proof of concept, and of course be demonstrated in the codebase. Proofs can be locally verified using using the rpc method [eth_getProof](https://docs.alchemy.com/reference/eth-getproof), which returns the RLP-serialized account proof (merkle proof internal sibling nodes) and similar storage proofs for the targeted storage slot(s). Multiple storage slots will need to be queried to prove the [`numCheckpoints`](https://github.com/nounsDAO/nouns-monorepo/blob/ca4dbe199e835706636776ef201ffbaecfde8774/packages/nouns-contracts/contracts/base/ERC721Checkpointable.sol#L56) and [`checkpoints`](https://github.com/nounsDAO/nouns-monorepo/blob/ca4dbe199e835706636776ef201ffbaecfde8774/packages/nouns-contracts/contracts/base/ERC721Checkpointable.sol#L53) mappings for a given address to provably extract the latest state for a voter.

Storage proofs must [cache the account storage root](https://docs.axiom.xyz/axiom-architecture/caching-block-hashes) of the NounsToken smart contract for each block where a proposal is made. We can add a step to [`NounsDaoLogicV1.sol:propose()`](https://github.com/nounsDAO/nouns-monorepo/blob/ca4dbe199e835706636776ef201ffbaecfde8774/packages/nouns-contracts/contracts/governance/NounsDAOLogicV1.sol#L165-L267) that computes and caches the account state root. The on-chain Zero Knowledge verifier for a vote on a said proposal can then inject the account storage root as a public input to trustlessly verify that storage proofs of Nouns tokens were not forged with fake block hashes. This caching step can be thought of as a type of trustless snapshot.

We can save on gas by using optimistic zero knowledge for the cached account storage root. Anyone can easily compute, verify, and challenge the optimistically posted storage root by verifying the zero knowledge proof. The obvious slashing mechanism would be for a proposal to require some sort of financial stake that is forfeited if fraud is proven. A sufficient safety deposit would incentivize chain watching to claim free money if a false root is posted. However, if the NounsDao does not want to require financial stake on a proposal, a temporary/ permanent ban could be made on an address that sends an invalid state root.

While a storage proof convinces a verifier that a value exists at a certain point in time in the EVM, it has no concept of proving ownership associated with that data. Thus, a Nouns holder needs to produce an ECDSA signature from the pubkey holding the vote weight. As mentioned in **ECDSA**, this signature can be reasonably verified inside of an Aztec Noir UltraPlonk Zero Knowledge circuit.

Note: this construction was proposed to us by Aztec Network in February.

## Vote Encryption
One possible method for encrypted vote tallying is “[Homomorphic Encryption](https://homomorphicencryption.org/introduction/)”. There are varying levels of homomorphic encryption, though the type we need is “Partially Homomorphic Encryption” (PHE). PHE only allows one type of algebraic operation (either addition or multiplication), which can be executed an infinite number of times. In the case of vote tallying, we use addition to sum the votes. Thus, we need “additive homomorphism” which allows us to preserve the algebraic structure inside encrypted space while adding values together.

There are two options for additive homomorphism: [Pallier](https://deapsecure.gitlab.io/deapsecure-lesson05-crypt/21-paillier-he/index.html) and “in-the-exponent” ElGamal. Given small messages (vote weight + direction), ElGamal is an [order of magnitude more efficient](https://www.scitepress.org/Papers/2020/87709/87709.pdf) than Pallier. However, we understand that many teams are using ElGamal, and could just as easily implement Pallier for the purpose of experimentation. If accepted, we expect to drive this decision by conversations with both Nouns and other winning teams. Since we don't make use of ElGamal's DSA, the end user functionality should be the same for both algorithms. This is called *Genericness*. Therefore, we are going to simply refer to the scheme as our *PHE* moving forwards.

In order to facilitate *YES/NO/ABSTAIN* vote options, we adapt a `K-of-L` voting scheme [[Hirt10]](https://crypto.ethz.ch/publications/files/Hirt10.pdf). Hirt10 proposes a ballot with `L` candidates and `K` votes. This can be repurposed such that there are three "candidates" one can vote for- yes, no, and abstain. A side-effect of `K-of-L` ballots is that a voter could theoretically split their votes between outcomes. If this is an undesirable outcome, it can be prevented in Zero Knowledge.

We want to sign and homomorphically encrypt our votes. However, ECDSA keys are not the same as PHE keys. Therefore, we propose the implementation of [Elliptic Curve Generalized *Signcryption*](https://eprint.iacr.org/2006/126.pdf) (ECGSC). Signcryption enables us to sign and encrypt (or verify and decrypt) our message in a single operation. PHE keys are not related to ECDSA keys, but our signature over the PHE encryption allows us to demonstrate an Ethereum account's provenance over a PHE key.

[Nullifiers](https://hackmd.io/@liangcc/nullifier) are the mechanism for preventing double-spending in Zero Knowledge applications. While hashing is computationally binding, it requires an extra 'trapdoor' (private random [hash salt](https://)). Meanwhile, [commitment schemes like Pedersen ](https://findora.org/faq/crypto/pedersen-commitment-with-elliptic-curves/) are perfectly hiding, generally with more efficiency. To that end, this proposal will repurpose the [Nullifiers used in ZCash's Orchard circuit](https://zcash.github.io/orchard/design/nullifiers.html), using the hash of the Voter's address, voteId, and (maybe) checkpointId as the preimage of the commitment. Voting posts this nullifier onchain, where future votes must prove they don't reuse that nullifier.

## Vote Tallying
Additive homomorphic encryption allows us to sum the

## Vote Decryption

A future path we would like to explore is the removal of a tallying committee. Using the threshold ECDSA, we believe that ""

## Summary of Requirements Engineering
@todo