Technical Description
===

[TOC]

# Census & Census Proofs

The **census** is the set of NFT holders, as defined by the EVM Merkle Patricia Trie. The census is obtained directly from the Ethereum blockchain (using Etherum storage proofs) and does not need to be separately buit. This is arguably the most groundbreaking feature of our scheme.

The **census proof** will combine a ZKP of [ECDSA verification](https://github.com/noir-lang/noir/blob/master/noir_stdlib/src/ecdsa_secp256k1.nr) and an [Ethereum storage proof](https://aztecnetwork.notion.site/Storage-Proof-Ethereum-16bf3cc90612467ca1ca4638f3b7d5cd), which together proves token ownerships and delegations of voters without revealing the identites of voters.

The voter identity remains private as the proof proves that the voter knows a $privateKey$ for which its address holds a certain token for the given $root$ (i.e. at a particular block), without revealing the voter address nor keys.

A typical voting action starts with voters [retrieving Merkle proofs](https://eips.ethereum.org/EIPS/eip-1186) of their NFT ownership / delegation record from an Ethereum node / gateway, generating signatures with their Ethereum key, and feeding them as inputs of a Noir census proof.

:::info
**Contents of a Vote Package**

A vote package is the data sent to the contract to cast a vote. It is used to verify voting eligibility and store the vote in the contract.

It contains the following elements:
- A merged ZKP consists of:
- $zkOwnershipProof$ that proves the NFT is either owned by or delegated to the signer for a specified `EthPatriciaTrie_Root` corresponding to a given block number
- $correctVoteValueProof$ that proves:
- If vote is encrypted: `encrypted(vote_value)` has been correctly computed for the given `encryption_public_key`
- If vote is unencrypted: `vote_value` contains a valid value ($v_i \in \{0,1, 2\}$, {abstain, yes, no})
- $correctNullifierProof$ that prevents double-voting by proving the `nullifier` is:
- Well computed from the `voter_address_privateKey`
- Well computed from the NFT public data
- `nullifier`: linked to the NFT
- `vote_value`: the value of the vote, either encrypted or not (configurable)
:::

# Vote verification and tallying using a Hash-chain of encrypted_votes

A Hash-chain is used to guarantee that the voting smart contract knows the current state of the election and can check if the results of the election and the proof it recieves do indeed match the state of the election. It does not require homomorphic encryption. The

- Voter sends their encrypted_vote value to the SmartContract
- SC computes the `Hash(encrypted_vote)`
- SC stores `curr_hash = Hash(Hash(encrypted_vote), curr_hash`)
- the SC mantains `curr_hash` and stores `encrypted_vote` as events
- the `encrypted_vote` values are accessible through emit-events

At the end of the voting period, anybody (with a suitably powerful machine) can compute the tally:
- get all the `encrypted_votes` from the emit-events
- compute the hash-chain until the last `curr_hash`
- generate a results-proof which proves:
- correct decryption of all `encrypted_votes`
- all the `decrypted_votes` added give certain `result`
- the chain-hash for the given `encrypted_votes` corresponds to the onchain-living `curr_hash`
- the `proof` is sent onchain together with the `result`
- verification of proof:
- public-inputs: `curr_hash, result`

For the hash, we will use keccak256, as it is cheaper (in terms of gas costs) to compute in the contract. The result+proof will be a bit costly to generate, but this is not a problem as this needs to be done only once at the end of the voting process, and can be done on a 'powerful server'.

# Achieving Tally Fairness using a Public Time-lapse Cryptographic Service

To achieve tally fairness, i.e. to make it impossible to tally a proposal’s votes before the voting period ends, there are two main options:

* a commit/reveal process, which completely avoids off-chain dependency;
* encrypted ballots, with a mechanism for uncovering the secret encryption key after the voting period ends.

The first option is considered impractical because it requires two SC interactions for every voter. The second option is also less than ideal, as it usually requires a distributed key generation ceremony before the vote, and a secret key uncovering ceremony afterwards. To eliminate this problem, we propose to create a **public time-lapse cryptography service** for a range of public key cryptographic schemes. The idea is the following:

For a chosen scheme supported by the system and a future date (up to for example 1 year in the future), the system will already have published a specific public key whose corresponding private key is scheduled to be published on the desired future date.

At any moment, there will therefore be many publicly available keys, with new public keys published and new private keys uncovered daily.

In terms of trust assumptions:

* for some schemes, will need to trust the parties participating in the system to not collude and uncover the secret keys early.
* for other schemes, we will be able rely on existing external services (cf tlock which relies on an external randomness beacon) which will give us much higher trust guarantees.

One of our research tasks will be to determine which schemes can be secured by external data or schemes, such as randomness beacons or data from major blockchains.

# Private Gas Payment & Vote Power Obfuscation

## Prepaid voting with delay-relayer
We now describe an approach allowing a DAO to pay for the votes of its members. For a given election, funds are deposited into the voting contract and earmarked for that election. When a valid vote is submitted for that election, the corresponding gas costs as well as a small premium are returned to the submitter, for as long as funds are available. If any funds are left after the election, they can be reclaimed.

This way, NFT holders can submit votes to a relayer without needing to deal with gas costs.

## Voting power obfuscation

To prevent identification of voters by their voting power, there will be a unique vote per NFT. Users will still have to make sure these votes are submitted from another Etherum address, with the submissions spaced out over time. This can be done by the delay-relayers.

For accounts with multiple tokens, we will look into producing proofs for fixed amounts of tokens (e.g. 2, 5, 10 tokens). However, this feature is out of the scope of the current proposal (see [Further work](https://hackmd.io/L6oniVQNRh2eT2nLjOfKLA)).

# ZK Proving Analysis

This proposal targets at constructing ZK proofs in-browser via Noir’s multi-threaded WASM prover. This section analyses the feasibility of achieving so.

## Constraint Count

We estimate that the constraint count of this proposal's Noir circuit should not exceed ~600,000 constraints, and should be easily provable in a web browser.

The majority of the constraint cost will come from Ethereum storage proofs due to the heavy use of the Keccak algorithm. The cost of a Keccak hash in Noir is ~18,000 constraints. The majority of smart contracts do not have deep storage trees (for an NFT contract the tree depth is likely close to $log_2(\text{total number of NFTs})$). For an NFT contract with $2^{14}$ (i.e. >16,000) NFTs, we estimate that a storage proof of such an NFT balance should require ~8-14 Keccak hashes (i.e. ~140,000-250,000 constraints).

Another often-notable constraint cost comes from the act of validating an Ethereum signature within a Noir circuit. Noir supports an optimised ECDSA signature verification gadget that can validate a signature in ~36,000 constraints. Each voting action requires 1 ECDSA signature verification to be proved.

Considering the constraint count limit to prove Noir circuits in browser is ~$2^{20}$ (i.e. ~1,000,000) constraints, the resulting circuit of this proposal should be easily provable in a web browser, even if multiple storage proofs are required.

## Proving Time

We estimate that the proving time of this proposal's Noir circuit should not exceend 1-2 minutes.

With respect to proving times, the proving backend this project is expected to utilise with Noir is identical to what the current Aztec Connect circuits running in production are based on.

Using that as a frame of reference, it typically requires 5 seconds on a modern device to compute a proof of a circuit of size $2^{16}$ (i.e. ~65,000) constraints. Prover times are broadly linear in circuit size, meaning that proofs of this project should, in the worst case, take 1-2 minutes to compute.

# Gas Costs Analysis
The expected gas costs are as follows:

| Action | Gas estimation | Who pays |
| -------- | -------- | -------- |
| Voting process setup | 100-300k | Organiser |
| Cast a vote | 400-500k | Voter (or a [third party](https://hackmd.io/1MqXYKcrRRSnB7pvnY8jYA#Private-gas-payment-and-vote-origin-obfuscation)) |
| Submit the result of a voting process and its proof | 400-500k | Submitter (anyone) |