Project Proposal

Pitch: A one-liner elevator pitch version of your proposal

Coin Voting using Orchard funds for Governance, Airdrops and Proofs of Balance

Total Request: 200,000 USD

Details

Applicant background

I am a frequent contributor in the zcash community.

Description of Problem or Opportunity

There are several possible applications besides elections

• referendums
• polls
• airdrops
• proving ownership of a balance of coins

With this scheme, users can keep their funds shielded at all times. It is not necessary to move funds before or after voting.

Voters can delegate their voting power to other electors.

Proposed Solution

• Use Orchard notes to prove balance
• Leverage Halo 2 and implement a voting mechanism based on the Orchard transaction system

For more details, refer to the section Design and the Example section.

Solution Format

The Election Authority setups a Voting Server and Voters can vote using their shielded Orchard coins. Wallets such as Ywallet has a voting pannel, users vote by virtually sending ZEC to a candidate or a delegate. Their balance does not change.

The implementation is described in the section Implementation.

Technical Approach

sequenceDiagram
    actor Election Authority
    actor Elector
    Election Authority->>Vote Server: Election Definition
    Elector-->>Vote Server: Get Election Definition
    Elector-->>Zcash Blockchain: Send Transaction
    Elector-->>Zcash Blockchain: Sync Notes
    Zcash Blockchain-->>Zcash Holders: Transactions
    Elector-->>Vote Blockchain: Submit Vote
    Elector-->>Vote Blockchain: Sync Votes
    Vote Blockchain-->>Elector: Votes
    Election Authority->>Vote Server: Tally Results
    Vote Server->>Election Authority: Vote Counts

The Technical Approach is described in the section Design

Collaboration and Upstream Dependencies

The project depends on the Rust crates:

• librustzcash
• orchard
• halo2_proofs
• halo2_gadgets

Only orchard has source code dependencies, the other are library dependencies.

Execution risks

There is little execution risk since a prototype was made (with a few limitations), and several elections were carried out.

The participation was high, several hundred thousand of ZEC were used in the votes.

Unintended Consequences

I do not see any unintended consequences.

Evaluation plan

Any organization or individual can use these tools to start an election or poll the community of Zec Holders.

Coins that want to airdrop Zcash holders (such as Namada) could use this too.

Finally, Exchanges could prove their balance in ZEC using this code.

Budget

Justification for the total hardware/software budget

The budget is justified by the amount and complexity of the work proposed. Also, the value it brings to the community is particularly valuable.

It gives a voice to all the Zcash Holders out there, while keeping their privacy.

No other cryptocurrency has reached this remarkable milestone, a testament to the unparalleled strength of Orchard and the Halo 2 proving system.

Services total budget

There is no service budget.

Schedule

Milestone 1 - Prototype

Deliverables

• Orchard Circuit for airdrops only and direct vote, no delegation and no Vote Blockchain
• Prototype Vote Server
• Vote client integrated with Ywallet
• Multiple Devfund pools

Proposed USD Value: 100,000 USD

This part is Retroactive.

Milestone 2 - Circuit

Deliverables

• Full Voting Circuit

Proposed USD Value: 40,000 USD

From 01-12-2024 to 01-02-2025

Milestone 3 - Server

Deliverables

• Vote Validation
• Block Producer
• Audit Tools
• Vote Server RPC
• Sample Website

Proposed USD Value: 30,000 USD

From 01-02-2025 to 01-04-2025

Milestone 4 - Client

Deliverables

• Vote Creation
• Block Download
• Reference Data Cache
• Client Library
• Voting Command Line Utility
• Wallet Integration into YWallet

Proposed USD Value: 30,000 USD

From 01-04-2025 to 01-06-2025

Coin Voting v2

Vote anonymously using your shielded ZEC, where your stake equals your voting power.

Opportunities

• Governance
• Proof of Balance
• Polls
• Airdrops

High Level Description

I organized a few coin-weighted votes last summer about the devfund.

• The Last Minute Shielded Petition
• Coin Weighted Poll

1. The pollster, in this case, me, would like to have the opinion of the community of Zcash holders.
2. He defines an eligibility window of blocks. Only Orchard notes created during these blocks can be used for voting.
3. At the end of the window, zcash holders can "cast" their votes using the ZEC they have.
4. They can vote using their wallet app (Ywallet at the moment)

This was Coin Voting v1.

Learning from these experiments, I am proposing an improved version.

Coin Voting V2

1. The eligibility window may be extended to cover all of the Orchard notes at the expense of requiring more compute and bandwidth
2. Splitting notes is not necessary. Voters can cast multiple ballots (for different options)
3. Voters can delegate their voting power to other people
4. Some voters can be granted voting power not associated with ZEC
5. The pollster can prove in ZK that the tally of the votes is correct

Mindmap

mindmap
    root((Coin Voting))
        Election Authority
            Public Parameters
                Question
                Choices
            Technical Parameters
                Election ID
                Window Start
                Snapshot Height
                Note Filter
        Election Node
            Reference Data
                Note Commitment Tree
                Nullifier Exclusion Tree
            Updates
        Voters
            Grantees
            Zcash Holdings
        Blockchain
            Pre-Snapshot
            Fork
                Ballots
                Grants
                Delegations
            Termination
                Tally
                Proof

Here's a short description on the role of each major component.

Election Authority

The Election Authority is the governing body responsible for overseeing the administration of the elections. Normally, its main duties include:

• Managing Voter Registration: Ensuring that only eligible ZEC holders can participate. This is done through cryptography instead.
• Administering Elections: Organizing and managing the logistics of the process. Running the Election Nodes and the information website if any.
• Counting Votes: Using the software and publishing the results
• Certifying Election Results: Providing the cryptographic proofs and the means to verify them

Voters/Electors

• Any Zcash holder can vote with a voting power equal to their holdings.
• Only coins in the Orchard pool at the time of the snapshot are usable.
• Voters cast their votes using an app or their wallet (if it integrates the voting library)
• Individuals may receive additional voting power from the Election Authority.
• Voting Power can be delegated, i.e. sent to another user.

::: info Voting Power has no monetary value and can be only used in a particular election :::

::: warning At this time, there is no mechanism to restrict voting to a particular group of users. It may be considered if there is an interest for a model of indirect elections with super representatives. :::

Blockchain

Most of the data comes from the blockchain. Conceptually, the coin voting considers transaction outputs from Orchard as source of voting power (VP), transaction inputs as a destruction of voting power.

Then at the snapshot height, the blockchain forks and a different "timeline" forms. On this branch, participants trade VP (delegations) and eventually spend it on proposals.

The fork is managed by the Election Authority via the Vote Server.

Vote Server

The Vote Server implements the Voting Protocol. It has similar responsibilities to the Zcash full node but without mining, p2p and block schedule.

Via the Vote Server,

• Voters receive delegated VP
• Voters submit their ballots

Election Authority / Pollster

On July 2024, The community wanted to poll the Zcash Holders regarding the future of the DevFund past Nov 24.

"What of the following proposals do you support?"

The options were:

• "None of these options",
• "Manufacturing Consent; Re-Establishing a Dev Fund for ECC, ZF, ZCG, Qedit, FPF, and ZecHub (by NoamChom)",
• "Establishing a Hybrid Dev Fund for ZF, ZCG and a Dev Fund Reserve (by Jack Gavigan)",
• "Lockbox For Decentralized Grants Allocation (perpetual 50% option) (by Skylar Saveland)",
• "Hybrid Deferred Dev Fund: Transitioning to a Non-Direct Funding Model (by Jason McGee, Peacemonger, GGuy)",
• "Lockbox For Decentralized Grants Allocation (20% option) (by Kris Nuttycombe)",
• "Masters Of The Universe? (by NoamChom)",
• "End the Dev Fund and return 100% of block rewards to miners"

From YWallet, users could use their funds to vote for their favorite proposal.

Voting in YWallet

The results were published on the forums.

What did we do to make it happen?

All the parameters that define the election/vote are stored in a JSON file.

For instance, the previous vote had these settings:

{
    "id": 2,
    "name": "Devfund Poll Proposals 2",
    "start_height": 2540000,
    "end_height": 2574200,
    "close_height": 2576000,
    "submit_url": "/submit/2",
    "question": "What proposal do you support?",
    "candidates": [
        "None of these options",
        "Manufacturing Consent; Re-Establishing a Dev Fund for ECC, ZF, ZCG, Qedit, FPF, and ZecHub (by NoamChom)",
        "Establishing a Hybrid Dev Fund for ZF, ZCG and a Dev Fund Reserve (by Jack Gavigan)",
        "Lockbox For Decentralized Grants Allocation (perpetual 50% option) (by Skylar Saveland)",
        "Hybrid Deferred Dev Fund: Transitioning to a Non-Direct Funding Model (by Jason McGee, Peacemonger, GGuy)",
        "Lockbox For Decentralized Grants Allocation (20% option) (by Kris Nuttycombe)",
        "Masters Of The Universe? (by NoamChom)",
        "End the Dev Fund and return 100% of block rewards to miners"
    ],
    "cmx": "233ea22fc2067c7141bb418f6cb71c308933eac205c3d79879c1c6acbed0a357",
    "nf": "03517198be86743e34ee057d5f41dc97b0a68da7d58eab0fee072af00288d472",
    "status": "Opened"
}

It was made manually but Coin Voting V2 will have a tool to assist in its creation.

Let's look at its content.

This section discusses the definition of an election from the perspective of the participants.

Name

The name of the election is displayed on the voting UI and must uniquely identify the election. It gets hashed and serves as a way to distinguish between ballots.

It is important to make sure that another election does not use the same name.

Examples

• Good choices: "Devfund 2024 - ZCG - Jul 2024"
• Bad choices:
  • "Devfund 2024", no mention of the Election Authority
  • "Devfund 2024 - ZCG" - there was going to be more than one vote
• Questionable choice:
  • "Devfund 2024 - ZCG - 2671000" - implies that the snapshot height is set (could be intentional)

Motion and Choices

question and candidates are the question asked and the possible answers. Voting does not support free-form answers. The voters must choose amongst one of the given options.

However, there is no limit on the number of options.

Next, let's discuss the blockchain heights.

Blockchain Windows

{
    "start_height": 2540000,
    "end_height": 2574200,
    "close_height": 2576000,
}    

Registration Window

If the end of the interval is in the future, the election definition must be updated after the blockchain reaches that height.

However, the longer the range, the more notes need to be downloaded and processed.

Refer to the technical section for more information on the calculations required.

The election does not necessarily have to include every output from the blockchain; it may choose to skip some based on publicly agreeable criteria. For example, notes that are part of transactions with more than 20 outputs could be omitted to avoid the spam. However, skipping notes based on shielded data is not possible.

Election Window

The close height is when the election stops accepting ballots. The client software should not send votes after this height. The check is enforced on the server side. If a faulty client sends votes past the close height, the election server rejects them.

This interval is covered in more details in the next section.

Status

The status is one of the following.

• Registration: the current height is in the election window. Voters should move their funds and leave them unspent until the window closes. They cannot vote yet because the window has not ended.
• Opened: Voters can vote.
• Closed: Ballots are not accepted anymore.

This is a recommendation for the client app. The server decides whether to accept or reject, based on the ballot content and the time it received it.

Note

Heights are not included in the calculation of the election hash and therefore may be adjusted after the election starts.

However, the Election Authority should clearly announce any change as it may affect the results.

If the Election Authority wants to commit to a given window they should explicitly include it in the name of the election.

Election Window

Logically speaking, voters acquired voting power during the registration window. In the election window, they use their voting power by sending it to another user or voting for a candidate or a motion.

The system leverages Orchard receivers. The candidates have "addresses" in the JSON file.

Direct Election

Votes sent to these addresses are final. At the end, the Election Authority tallies the votes and the winner is decided.

Indirect Election

However, an election scheme could be "indirect" or in stages, where these candidates proceed to vote further using the votes they received in a previous stage.

flowchart LR
    ZHolders --> Candidates
    Candidates --> Winner

Spend Signature

The Election Authority can decide to accept unsigned notes from the voters.

However, the full viewing key is still needed.

Allowing unsigned votes has the advantage of not requiring coins to be retrieved from cold storage.

Misc Other Data

The id differentiates between several concurrent elections that the server is hosting. It does not have to be globally unique since it is specific to a given server deployment.

The submit URL is where the client sends the ballots. It is a relative URI to the server URL that hosts the election definition file.

So far, we have not discussed Coin Voting from any technical perspective. The next chapter's topic deals with the design and implementation.

Design

Coin Voting is essentially the same as a token system, i.e., the same as Zcash itself, with some adjustments. Instead of coins, we have tokens that represent the voting power. We want to distribute the voting power based on a verified amount of ZEC.

In principle, we are airdropping voting power.

Transactions are exchanges of voting power between participants. Essentially, we allow electors to delegate their vote. The election's winner is the candidate or the choice with the most votes at the end.

The Coin Voting leverages the Orchard system and uses its transaction system to support delegation.

It extends it with the ability to include existing notes from the Orchard pool. Coinbase transactions add grants that reward critical organizations and influential individuals.

Otherwise, Voting Power is a self-contained system: There is no minting or burning.

Vote "Blockchain"

This is not a typical blockchain in the sense that no mining takes place. The Election Authority maintains the blockchain. It is not decentralized.

It goes through the following states.

stateDiagram-v2
    a : Genesis
    b : Premine
    c : Orchard Notes
    c2 : Snapshot
    d : Votes (+Delegations)
    e : Results

    a --> b : Add Grants
    b --> c : Add from Registration Window
    c --> c2 : Fork
    c2 --> d : Add Voting Transactions
    d --> e : Show Balance

Concepts

Election Hash

The Election Hash EH is 32-byte hash that uniquely identifies a given election.

EH: \( \mathbb{F}_{q_\mathbb P} \)

\[ \mathsf{EH} = \operatorname{ToBase}^{\mathsf{Orchard}}( \operatorname{Blake2b-512}_{\mathsf {PersoEH}}(name)) \]

where name is the UTF-8 byte representation of the election name, and PersoEH is b"ZcashVote_domain"

Recap on Zcash

The main state of the zcash cryptocurrency is a set of notes that record the association of an amount of ZEC to an address¹.

A user indirectly owns ZEC by knowing the secret key matching the address of a note. The secret is needed when building transactions.

A transaction expresses the destruction of a previous note owned by the sender and the creation of a new note owned by the recipient.

Before Zcash, notes were "transparent." The address and the amount of a note are public information and are recorded in the blockchain. This lets node validators verify the transactions. They eliminate any invalid transactions and keep the blockchain clear.

However, this mechanism exposes everyone's transaction history. Zcash adds privacy by encrypting the notes, making them "shielded."

Before Zcash

A transaction has inputs and outputs, where outputs are newly created notes (address & value), and inputs are old notes referenced by the transaction that created them: transaction hash & output index².

With Zcash

The shielded transactions use note commitments in place of plain notes. The plain notes are encrypted and only the recipient (and optionally the sender) can decrypt them. Since the encrypted notes are unreadable, they cannot be part of the validation scheme.

Instead, Zero Knowledge Proofs enforce the correct calculation and the validity of the note commitments.

Also, Zcash does not use direct references to previous notes as inputs because it would reveal the transaction history. Instead, inputs are hashes (called nullifiers). They are different but derived uniquely from the note commitments.

In summary, note commitments and their and their nullifiers (i.e. anti-note commitments) make but hide the transaction graph.

Voting Notes

Voting Notes are memo-less Orchard Notes. They have an address and a value. The value is the voting power.

Before the Election Snapshot (at end of the registration window), voting notes are taken to be the Orchard notes.

After the Snapshot, electors and delegates can make transactions that destroy and create Voting notes.

Obviously, these voting notes are not equivalent to the Orchard notes from the main Zcash chain.

Voting transactions have a different structure than Zcash transactions and cannot be replayed on the main chain.

Data Diagram

Keys

To be able to use a voting note, the voter must know the Spending Key. The other keys are derived from it as follows.

The data in orange are secret inputs to the Voting circuit. Data in blue is derived and used later. Data in purple are public values.

flowchart TD
    sk["Spending Key (sk)"]
    ask["SpendAuth Secret Key (ask)"]
    ak["SpendAuth Public Key (ak)"]
    nk["Nullifier Key (nk)"]
    rivk["Randomizer Incoming Viewing Key (rivk)"]
    fvk["Full Viewing Key"]
    ivk["Incoming Viewing Key"]
    sk --> ask
    ask --> ak
    sk --> nk
    sk --> rivk
    ak:::secret --> fvk
    nk:::secret --> fvk
    rivk:::secret --> fvk
    fvk --> ivk:::derived
    classDef secret fill:#f96
    classDef derived fill:#78b3d0

Spent Note

The spent note has an address, value, random seed rseed, and \(\rho\), the nullifier of the action that created it. The voting software or wallet decrypted the note with the Incoming Viewing Key and was able to store all these values.

The address is a combination of the diversifier (d) and the public key (pkd)

Address Integrity

The Address Integrity Statement checks that pkd comes from d and the ivk.

flowchart TB
    d[d]
    Gd[G_d]
    ivk
    pkd[pk_d]
    d:::secret --> Gd
    Gd --> pkd
    ivk:::derived --> pkd:::derived
    classDef secret fill:#f96
    classDef derived fill:#78b3d0

Note Commitment

The Note Commitment Integrity Statement checks that cmx is calculated from the note and the full viewing key.

flowchart TB
    rseed["Note Random Seed"]
    psi
    v["Note Value"]
    rho["Note rho"]
    cmx["Note commitment"]
    rseed:::secret --> psi
    G_d --> cmx:::public
    pk_d --> cmx
    v:::secret --> cmx
    rho:::secret --> cmx
    rho:::secret --> psi
    psi --> cmx
    classDef secret fill:#f96
    classDef derived fill:#78b3d0
    classDef public fill:#d999ff

Nullifier Check

The Nullifier Integrity Statement checks that the nullifier comes from the nullifier key nk and the spent note properties. It is built from the note commitment cmx.

nf is the Zcash nullifier from the Main chain. It is public over there and secret in the Voting chain.

flowchart TB
    nk:::secret --> nf:::derived
    rho --> nf["Nullifier"]
    psi --> nf
    cmx --> nf
    classDef secret fill:#f96
    classDef derived fill:#78b3d0

Election Domain Nullifier Check

This ED nullifier replaces the Zcash Nullifier in the Voting Chain.

flowchart TB
    nk:::secret --> nf:::derived
    edh["Election Domain Hash"]
    edh:::public --> nf["Domain Nullifier"]
    rho --> nf
    psi --> nf
    cmx --> nf
    classDef secret fill:#f96
    classDef derived fill:#78b3d0
    classDef public fill:#d999ff

Nullifier Non-Inclusion Check

The secret nullifier nf must not be included in the transactions from the Registration Window¹. Otherwise, the note is spent. It is fine for the nullifier to appear after the snapshot height.

All the nullifiers from the Registration Window are sorted as an LSB 256-bit integer to form a list: \( (n_0, n_1, \dots, n_N) \)

We want to prove that nf is not in the list.

If we want to prove that nf was in the list, we would use a Merkle Tree. For an exclusion proof, we still use a Merkle Tree but a slightly different one.

Instead of having the leaves \( (n_0, n_1, \dots, n_N) \), we first form intervals that do not contain a nullifier.

Since \(n_0\) is the first nullifier, \([0, n_0-1]\) does not contain a nullifier. Then \([n_0+1, n_1-1]\) is the next interval, and so on so forth².

The condition nf is not spent becomes equivalent to

1. there is an i such as \([n_i+1, n_{i+1}-1]\) is one of these intervals, and
2. \(nf \gt n_i\)
3. \(nf \lt n_{i+1}\)

The nullifiers are public information. Therefore, so are the intervals.

The non-inclusion proof becomes the following. There is a secret value n, such as:

1. n is a leaf of the Merkle Tree MT made of \[0, n_0-1, n_0+1, n_1-1, n_1+1, \dots, F_p-1\] where \(F_p\) is the order of the base field of the Pallas curve.
2. n has an even position (i.e it is the start of an interval)
3. n' is the sibling leaf.
4. \(nf \gt n\)
5. \(nf \lt n'\)
6. The root of MT is the nullifier tree anchor. It is publicly computed.

Or equivalently,

We know secret values \(n\) and merkle path \(np\) such as

1. \(n\) and \(np\) hash to the root,
2. \(nf \gt n\)
3. \(nf \gt np[0]\)

because the first element of the Merkle Path is the sibling leaf.

Alternate Implementation

Another, somewhat easier, way to implement a non-inclusion tree is to use a Sparse Merkle Tree.

The Tree has \( 2^{256} \) leaves and 256 levels where every used nullifier nf takes the spot at position nf³.

That's about 99.99999999999999999999999999999999999999999999999999999999999999999999%⁴ empty.

So even if the tree is too large, it is still possible to compute the Merkle Paths.

Let \(n_i = (p_i, h_i)\), the list of nullifiers with their position p and hash h.

For depth d from 0 to 256, go through the list

1. If the current element and the next are part of the same pairs of nodes, combine them and skip the next item,
2. otherwise, calculate the position of the item.
   • If it is the left node, merge with the "empty" root of depth d on the right;
   • If it is the right node, merge with the "empty" root of depth d on the left.

Empty roots of depth d are the root hash of the empty trees of height d. They can be computed in constant time (relative to the number of notes), or precached.

The path is 256 hashes long but contains in average the same number of non-empty hashes than the previous implementation.

Comparison between both approaches

Tree of ranges

Pros

• Same length of Merkle Tree Path
• Same verification complexity for the path

Cons

• Additional range check in circuit

Sparse Tree

Pros

• Same Verification Logic

Cons

• 256 vs 32 hashing in circuit

Spending Signature Public Key

Every input is signed using the secret key associated with its address. The signature is built from the hash of the transaction, the public key of the address and the secret key of the address.

In Bitcoin, the address is an encoding of the hash of the public key. It is revealed in the spending transaction.

However, in Zcash, the public key should remain hidden. If it was included in the spending transaction, it would establish a link between all the transactions coming from the same address.

Therefore, Zcash randomizes the public key. The spender signs using a public key rk that is offset to the actual public key pk by a random factor \(\alpha\).

The statement spend-authority of the ZKP enforces that \(\alpha\) is known to the spender and the signature on rk is as good as a signature on pk.

\[ \begin{align} \mathsf{rk} &= \mathsf{pk} + \alpha.G \\ \mathsf{rsk} &= \mathsf{sk} + \alpha \end{align} \]

Net Value Commitment Integrity

The value of the spent note contributes Voting Power v. This is hidden by a Pedersen Hash that uses a trapdoor randomizer rcv.

\[ \mathsf{cv} = v.G + \mathsf{rcv}.H \]

Consensus Rules

In layman terms, a cryptocurrency system must enforce the following rules in some way.

1. Output Note must go to the recipient
2. Input Notes must exist
3. Input Notes must be yours
4. Input Notes must not be spent
5. Total value of the inputs must be equal to the total value of the outputs & fee (Conservation of Value)

Output Note must go to the recipient

In Bitcoin, the transaction output have the address of the recipient¹.

In Zcash, outputs are note commitments, i.e. hashes. However, the note commitment is checked by the statement note-commitment-integrity of the ZKP.

Input Notes must exist

In Bitcoin, the transaction inputs are references to the output note by transaction id and output position. This can easily be checked by keeping a database of all the transactions.

In Zcash, the existence is proven by the statement merkle-path-validity

In this case, the public list is the list of all the note commitments, spent or not (there is no way of telling them apart). Usually, the prover would present the element and a Merkle Path. The verifier checks the proof by calculating the root hash and matching it against the public root value.

With Zcash, this verification is made in a ZKP which hides the element and the Merkle Path.

In layman terms, the ZKP states that the note exists because the creator of the transaction can provide the note commitment and a Merkle Path that leads to the public root. In a sense, the ZKP is a proof of a proof.

Input Notes must be yours

Both Bitcoin and Zcash use the same technique. The address is derived from a secret key. Knowing that secret key proves that the sender owns the address.

The sender proves they have the secret key by signing the note².

Technically speaking, proving ownership of the address of a note is not the same as proving ownership of the note.

It just proves ownership at some point in time. It is possible that the note is already spent.

Input Notes must not be spent

This prevents double spending, i.e issuing two or more payments that use the same note (with a correct signature).

In Bitcoin, it is avoided by simply checking that the output is at most used once. There cannot be two transactions that use inputs that refer to the same previous output.

In Zcash, the inputs do not refer directly to a previous output, therefore we cannot check double spending with a database lookup.

Instead, Zcash uses nullifiers. A nullifier is another hash value associated with a note. The first hash is the note commitment.

Every note has a note commitment and a nullifier, but obviously there are not the same.

The creator of a note, the person who created the payment transaction, can compute the note commitment. But the nullifier can only be computed by the recipient, i.e the owner.

Zcash transactions expose the nullifiers nf and the note commitments cmx.

Voting transactions do the same thing but with different nullifiers. If the votes shared the same nullifier, then votes could be linked between different elections.

Consider the case of a voter who keeps a stash of ZEC and votes on two different elections with the same notes.

The Voting system eliminates this issue by defining a new nullifier derivation rule that includes the Election Hash.

The same note has distinct Election nullifiers and cannot be linked with the nullifier from any other election or the Zcash main chain.

However, the Election nullifier cannot be used to prevent voting with spent note.

Before Snapshot (in Zcash chain)

Zcash Nullifiers must not be used more than once

After Snapshot (in Vote chain)

Election Domain Nullifiers must not be used more than once. The statements merkle-path-validity, domain-nullifier-integrity, and range-check-on-nf of the ZKP prevents reusing the Zcash Nullifier.

Conservation of Value

The Conservation of Value establishes that a transaction does not create or destroy funds/votes while keeping the values hidden.

The idea is that when we have a point P such as \[ P = v.G + x.H \] where G and H are known points³, v (value of the note) and x (random value) are not the secret keys to P because of the other term.

But if there are summed over the whole transactions, taking v for inputs and -v for outputs, the sum of P, let's call it Q has only a term in H, because \( \sum(v) = 0 \)

\[ Q = \sum{v}.G + \sum{x}.H = \sum{x}.H \]

Then \(\sum{x}\) is the secret key for Q and can be used to sign the transaction. This signature is the binding signature as it binds the total value of the transaction.

There is one binding signature for the whole transaction.

• The statement value-commitment of the ZKP enforces the creator computed P (called value commitment cv) correctly.
• The binding signature ensures that overall, the value of the transaction is zero⁴.

Recap

The transaction is valid when the following conditions are met.

After the Snapshot, the consensus have additional rules to stop double spending.

1. Input Note has the Election nullifier domain_nf.
2. nf has not been used before in the Main Zcash chain.
3. domain_nf and cmx are public (nf is no longer public).

The note commitments are the same before the Snapshot and diverge because the voting transactions are different from the payment transactions.

Ballot

The Ballot is the data sent from the Client to the Voting Server that represents a vote for a candidate/question or a delegation to another user(s).

The voter partially use their voting power by adding a "change" vote output similarly to standard payment transactions.

BallotEnvelope

The BallotEnvelope is the binary representation of the ballot.

It has the following data.

• Ballot Payload (see next paragraph),
• Binding Signature
• ZK proofs of the Ballot Actions

BallotPayload

The Ballot Data is the non-malleable part of the Ballot. The SigHash is calculated on the Ballot Data.

It is a vector of Ballot Actions.

BallotAction

The Ballot Action represents an individual transfer of voting power. It burns a previous output and mints a new one. If there are more spends than outputs, the action includes dummy data. Dummy notes have a value equal to 0.

The Ballot Action has the following fields.

• cv: Value commitment,
• rk: Public key of the rerandomized authorization key,
• nf: Input Note Election domain nullifier,
• cmx: Output Note commitment,
• epk: Ephemeral Public Key
• enc: Encrypted New Note

Note that it does not have cout and enc does not have a memo.

VoteInput

In addition to the BallotData that is public information, the ballot app has the notion of a VoteInput and VoteOutput in the decrypted Vote.

A Vote Input has the following fields.

• sk: The spending key used to sign the input,
• fvk: The corresponding full viewing key,
• pos: The position of the note in the note commitment tree,
• note: The note as an Orchard plain note,
  • address
  • value
  • nullifier (in the Zcash chain)
  • random seed
• nf_start: The lower bound of the nullifier range where this note belongs,
• nf_path: The Merkle Authentication Path for nf_start
• cmx_path: The Merkle Authentication Path for the note commitment cmx

VoteOutput

A vote output has the following fields:

• address
• value

(no memo field)

Encrypted Note

The encrypted note is the encryption of (d, pkd, value) using the same algorith as Orchard.

Implementation

The Implementation section describes the circuit statements and the workflow for:

• the preparation of an election by the Election Authority,
• the voting process by an Elector,
• the collection and counting of the votes by the Election Authority & Auditors.

Circuit

Public Parameters

• Anchor (cmx): cmx_root
• Anchor (nf): nf_root
• Value Commitment X, Y
• Randomized Public Key X, Y
• Election Domain nf
• Note Commitment cmx
• Election Domain Hash

Secret Inputs

• Nullifier Range Lower Bound: nf_start
• nf_start Nullifier Merkle Path: nf_mp (nf_pos + nf_path)
• cmx Merkle Path: cmx_mp (pos + auth_path)
• Value Commitment Trapdoor: rcv
• Spent note (old)
  • rho: nullifier of the action that created the note (not the nullifier of the note)
  • psi: derived from rho and rseed and used for cmx and nf
  • rcm: also derived from rho and rseed and used for the value commitment
  • nf = nullifier of the note, derived from the full viewing key
  • v = value of the note
  • address: gd and pkd. gd is derived from the address diversifier d.
  • cmx: derived from address, v and psi
• Signature rerandomization
  • alpha
• Address integrity
  • full viewing key: ak, nk, rivk
• Output note (new)
  • rho = nullifier of spent note
  • psi = rseed.psi(rho)
  • rcm = rseed.rcm(rho)

Actions are pairs of spends & output (with dummies if needed). The rho of the new note is the nullifier of the spent note.

Statements

Merkle Path Validity

• cmx_mp is a Merkle Path from cmx to cmx_root
• nf_mp is a Merkle Path from nf_start to nf_root

Value Commitment

\[ cv = \operatorname{ValueCommitment}_\mathsf{rcv}(\mathsf{vold} - \mathsf{vnew}) \]

Nullifier Integrity (old note)

\[ \mathsf{nf} = \operatorname{DeriveNullifier}_\mathsf{nk}(\rho, \psi, \mathsf{cmx}) \]

Domain Nullifier Integrity (old note, after Snapshot)

\[ \mathsf{dnf} = \operatorname{DeriveDomainNullifier}_\mathsf{nk}^\mathsf{edh}(\rho, \psi, \mathsf{cmx}) \]

Spend Authority

\[ \mathsf{rk} = \mathsf{ak} + \alpha * G \]

Address Integrity of Old Note

\[ \begin{align} \mathsf{ivk} &= \operatorname{CommitIvk}(\mathsf{ak}, \mathsf{nk}, \mathsf{rivk}) \\ \mathsf{pkd} &= \mathsf{ivk}.\mathsf{gd} \\ \end{align} \]

Note Commitment Integrity

The old and new notes must have a note commitment of:

\[ cmx = \operatorname{NoteCommitment}( \mathsf{gd}, \mathsf{pkd}, \mathsf{v}, \rho, \psi) \]

• gd comes from the diversifier d (part of the address);
• pkd is part of the address;
• v is the value of the note;
• \( \rho, \psi \) are derived from the random seed, rseed of the note.

Therefore to calculate the note commitment, you must know be able to decrypt the note.

Range Check on nf

• nf in [nf_start, nf_end]
• nf_end = nf_path[0]

Other Orchard Constraints

net_cv = v_old - v_new cmx_root = advice nf_root = advice nf_pos is even

Notes

DeriveDomainNullifier is new though.

\[ \begin{align} \operatorname{DeriveNullifier} &= ( \operatorname{PH}(\mathsf{nk}, \rho) + \psi).\mathsf{Nk} + \mathsf{cm} \\ \operatorname{DeriveDomainNullifier} &= ( \operatorname{PH}(\mathsf{nk}, \operatorname{PH}(\mathsf{edh}, \rho) ) + \psi).\mathsf{Nk} + \mathsf{cm} \\ \end{align} \]

where PH is the Posseidon Hash.

The parameters of PH used in the Orchard circuit is proven secure for hashing two elements of Fp, not three.

Vote to Ballot

Prepare Election

The Election Authority:

• Decides the Registration Window (and the note filtering if used)
• States the Purpose (or Question) and Choices

The server:

• Generates a random seed phrase
• Derives an Orchard address per answer
• Builds the initial cmx & nf trees
• Monitors the Blockchain and update trees until the snapshot is reached. The setup is described in Server Setup

Optional:

• The Election Authority sets up a website for the election with information about the purpose, the candidates, etc.
• The URL of the voting server is published online. Alternatively, the URL is sent by email, etc.

Elector Registration

• Elector moves coins into Orchard or refreshes existing Orchard notes if necessary.

A wide window of registration reduces the need to move Orchard Notes but increases the reference data set that electors need to download and process.

Vote Preparation

• Voting app VA (or wallet with voting capabilities) downloads election definition from server
• VA downloads cmx and nf tree from either
  • server
  • lightwalletd, and process the raw block data to reconstruct the election data¹
  • get a bootstrap file from torrent or from ipfs
• VA caches the trees
• Once the snapshot height is reached, VA can compute the tree hashes and cache the result

Vote or Delegation

• User selects a candidate or candidates and a quantity of ZEC
• VA builds a voting transaction with 1 or many recipients
• VA adds a change output if needed
• VA computes ZKP for each action
• VA computes binding signature
• VA signs each input
• VA transmits transaction to Voting Server

Counting & Audit

Important Note about nf Tree

The nf tree is a non-inclusion tree. It is not an incremental merkle tree like the cmx and cannot be optimized because nullifier nodes are not only appended.

The client has to download and keep the complete set of nullifiers because the tree is sorted and new nullifiers can end up anywhere.

Every action has a nullifier and a note commitment. Some of them are dummies but there is no way to tell which ones.

Both nullifier nf and note commitment cmx take 32 bytes each. An action takes 64 bytes to download. The cmx does not need to be kept, but the nf does. Therefore it takes about 32 bytes of storage. It takes about N hash calculations to compute the Merkle Path when N is the number of leaves. We can compute the paths for multiple notes simultaneously. But when new leaves are added, the intermediate hashes must be recalculated². The nf tree has 2N leaves and the cmx tree has N leaves.

Ballot Verification

• Voting Server (VS) receives the vote
• VS checks the ZKP of each action
• VS checks the signatures (spend + binding)
• VS checks that the election domain nullifier was not used before
• If VS can decrypt the encrypted note, it checks that it is valid
  • correct address
  • correct cmx
• VS stores the nf and the encrypted note

The encrypted note does not have the zip-212 flag or a memo.

Vote Counting & Audit

At the end of the election, the Election Authority releases the full viewing keys of the candidate addresses.

This allows anyone to trial decrypt and decipher the votes for the candidates.

The Election Authority publishes the election report.

Audit

In additional to checking the results, the complete list of transaction data is available for download from the Voting Server.

This allows auditors (or any user) to verify that the election was carried out correctly (no double voting, no unregistered votes, no counterfeit votes, etc.)

Vote Client

The client is responsible for creating and submitting votes to the server.

A Ballot is built:

• from the (secret) data associated with an Orchard Note that the voter owns,
• and the note commitment and nullifier trees that the client obtains from the public Zcash & Voting chains.

Trees

Blockchain Data

From zcashd, zebrad or lightwalletd, download Blocks or CompactBlocks and extract the OrchardAction

#![allow(unused)]
fn main() {
type Hash = [u8; 32];

struct Action {
    nf: Hash,
    cmx: Hash,
}

async fn download_blocks_lwd(url: &str, start: u32, end: u32) -> Vec<Action>;
async fn download_blocks_zcashd(url: &str, start: u32, end: u32) -> Vec<Action>;
}

Orchard Hash Function

The commitment tree hash function that combines two nodes or two leaves is the following.

#![allow(unused)]
fn main() {
/// Orchard hash of two nodes of the CMX tree
pub fn cmx_hash(level: u8, left: &Hash, right: &Hash) -> [Hash] {
    let left = MerkleHashOrchard::from_bytes(left).unwrap();
    let right = MerkleHashOrchard::from_bytes(right).unwrap();
    let h = MerkleHashOrchard::combine(Altitude::from(level), &left, &right);
    h.to_bytes()
}
}

where level is 0 for the leaves, and increments by 1 on every layer.

If the tree has an odd number of leaves, it should be padded by adding an empty leaf with the "empty leaf" hash value.

#![allow(unused)]
fn main() {
/// Empty Orchard CMX hash
pub fn empty_hash() -> [u8; 32] {
    MerkleHashOrchard::empty_leaf().to_bytes()
}
}

Logically speaking, the tree is a binary tree of depth 32 and starts full of empty leaves. The cmx_hash combines leaves on depth 0 to depth 1, then depth 1 to depth 2, and so on so forth, until we reach the root.

At this point, every level of the tree has the same value obtained by hashing two identical values from the previous layer.

As nodes are added, they replace empty leaves, progressively from the position 0. However, empty subtrees have the same hash value as before.

Merkle Root

The Root hash of the tree is a public value. Transactions must include it in their transactions.

It must match the root hash calculated at the end of a block (from zcash or vote chain).

Merkle Path

The Merkle Path is the combination of the following data.

• The value of the leaf (cmx or nf),
• The position of the leaf (starting at 0 for the first leaf),
• The list of 32 ommers. They are the sibling nodes on the direct path from the leaf to the root.

The Merkle Path is an input to the ZKP circuits and should not be sent out.

#![allow(unused)]
fn main() {
pub struct MerklePath {
    pub value: Hash,
    pub position: u32,
    pub path: [Hash; DEPTH],
}

pub fn calculate_merkle_paths(
    positions: &[u32],
    hashes: &[Hash],
) -> (Hash, Vec<MerklePath>);

}

where DEPTH = 32

calculate_merkle_paths takes a list of leaf positions and the list of leaves and calculates the Merkle Path for every leaf position given.

CMX Tree

The CMX Tree is the Merkle Tree where each leaf is the cmx value from the Action in the order they appear on the Blockchain.

NF Tree

The NF Tree is the Merkle Tree of nullifiers. They must be sorted and a list of complement intervals created. \[ \forall i, n_i \not\in \bigcup {[a_i, b_i]} \]

Nullifiers are integers in the base field of the Pallas curve.

#![allow(unused)]
fn main() {
type Nullifier = Fp;

fn build_nf_ranges(nfs: impl IntoIterator<Item = Nullifier>) -> Vec<Nullifier>;
}

build_nf_ranges returns a list of flatten intervals as a list \([a_0, b_0, a_1, b_1, \dots ]\).

Action

Election Domain Hash

Compute the edh from the Election name

Inputs

#![allow(unused)]
fn main() {
struct VoteInput {
    sk: Option<SpendingKey>,
    fvk: FullViewingKey,
    pos: u32,
    note: Note,
    nf_start: Nullifier,
    nf_pos: u32,
    nf_path: MerklePath,
    cmx_path: MerklePath,
}
}

• sk is needed if the election requires "Spend Signatures",
• pos is the position of the note in the cmx tree¹,
• nf_start is the \(a_i\) of the interval \([a_i, b_i]\) where nf belongs,
• nf_pos is the position of nf_start in the NF tree,
• nf_path and cmx_path are the Merkle Path obtained in the previous step.

Calculate the domain nullifier dnf.

#![allow(unused)]
fn main() {
let dnf = spend.note.nullifier_domain(&fvk, &edh);
}

Output

The output is a voting note.

#![allow(unused)]
fn main() {
struct VoteOutput(Address, u64);
}

Encrypted Note

The encrypted note corresponds to the CompactAction of Orchard. For reference, it is composed of the following fields.

• zip-212 version byte: 1 byte
• address diversifier: 11 bytes
• address pkd: 32 bytes
• value: 8 bytes For a total of 52 bytes.

It can be built using OrchardNoteEncryption from LRZ.

In pseudo-code

1. Set rho as the nullifier (or domain diversifier on the Vote Chain) of the spent note
2. Pick rseed with the OsRng
3. Create an Orchard Note Note::from_parts(recipient, NoteValue::from_raw(value), rho, rseed)
4. Encrypt the node

#![allow(unused)]
fn main() {
let rseed = RandomSeed::random(&mut rng, &rho);
let note = Note::from_parts(recipient, NoteValue::from_raw(value), rho, rseed);
let encryptor = OrchardNoteEncryption::new(None, output.clone(), candidate, [0u8; 512]);
}

Get the ephemeral public key epk, the encrypted note encand the note commitmentcmx`.

#![allow(unused)]
fn main() {
let epk = encryptor.epk();
let enc = encryptor.encrypt_note_plaintext()[0..52];
let cmx = note.commitment();
}

1. Calculate the vote net value as input value - output value.
2. Pick a random trapdoor value rcv
3. Accumulate rcv over the transaction
4. Derive the net value commitment

#![allow(unused)]
fn main() {
let value_net = spend.note.value() - output.value();
let rcv = ValueCommitTrapdoor::random(&mut rng);
total_rcv = total_rcv + &rcv;
let cv_net = ValueCommitment::derive(value_net, rcv.clone());
}

Randomized public key

1. Pick a random scalar \( \alpha \) in Fq (scalar field of Pallas)
2. Derive the spend authorizing key from the spending key
3. Add \( \alpha \) and derive the public key

#![allow(unused)]
fn main() {
let alpha = Fq::random(&mut rng);
let spk = SpendAuthorizingKey::from(&spend.sk);
let rk = spk.randomize(&alpha);
}

Zero Knowledge Proof

Collect the public data (instance data):

• cmx_root, nf_root
• cv_net
• dnf
• rk
• cmx
• edh

And the secret data (advice data)

• dnf
• nf_start
• nf_path
• fvk
• spend_note
• cmx_path
• output_note
• alpha
• rcv

Then call the ZKP builder for the voting circuit as described in Circuit.

Ballot Action

Collect

• cv
• rk
• dnf
• cmx
• epk
• enc

and form the BallotAction

#![allow(unused)]
fn main() {
struct BallotAction {
    cv: Hash,
    rk: Hash,
    nf: Hash,
    cmx: Hash,
    epk: Hash,
    enc: [u8; 52],
}
}

Ballot Data

Collect all the BallotActions into a BallotData

#![allow(unused)]
fn main() {
struct BallotData {
    actions: Vec<BallotAction>,
}
}

Sighash

Compute the sighash of the BallotData as

#![allow(unused)]
fn main() {
fn sig_hash(&self) -> Hash {
    let bin_data = serde_cbor::to_vec(&self).unwrap();
    let p = Params::new()
        .hash_length(32)
        .personal(b"Ballot______Data")
        .hash(&bin_data);
    p.as_bytes().try_into().unwrap()
}
}

It is the Blake2b-256 hash of the CBOR serialization of BallotData with Personalization Ballot______Data.

Binding Signature

Use the sighash and total_rcv to compute the Binding Signature

#![allow(unused)]
fn main() {
let bsk: SigningKey<Binding> = rcv.to_bytes();
let binding_signature = bsk.sign(&mut rng, sig_hash);
}

Spend Signature

Sign the sighash using the public key rk, sighash and SpendAuth.

Ballot Envelope

Combine the Ballot Data, Binding Signature, Input Signatures and proofs into the Ballot Envelope.

#![allow(unused)]
fn main() {
type Signature = [u8; 64];

struct BallotEnvelope {
    data: BallotData,
    input_signature: Vec<Signature>,
    binding_signature: Signature,
    proofs: Vec<Vec<u8>>,
}
}

Send to Server

Serialize BallotEnvelope as CBOR and send the bytes to the Voting Server.

Delegation

Once the Snapshot height is reached, the Voting Server VS will start building an alternate Blockchain with just the election ballots.

Delegates must monitor the new Blockchain which is downloadable through one of the VS RPC endpoints.

If they find output notes that gives them Voting Power, they can use it to vote for a candidate (or delegate to another user).

Grant

If the Election want to give more Voting Power to certain distinguished users, they can do so by adding a voting transaction that does not balance its value to 0 but to the grant amount.

To receive a grant, grantees must give an address and its incoming viewing key.

Library

The voting code will be provided as an independent rust crate so that developers can integrate in their wallet/apps.

We will provide an integration in Ywallet and a standalone command line utility.

At the moment, the circuit has dependencies on private members of the orchard crate.

Vote Server

The Vote Server receives ballots from the electors and maintains the status of the election.

It is REST server with public endpoints for the voters and authenticated endpoints for the officials.

Server Setup

Seed

After deciding on the Election Measure and the Candidates, the Election Officials generate a random seed phrase.

Using ZIP-32, they derive a secret key for each candidate using the standard derivation path for accounts: m/32/133/<candidate>/0

The addresses associated with the candidates are made public[^1]. They are included in the Election JSON too.

cmx and nf roots

Once the snapshot height is reached, i.e. when voting starts, the Voting Server (VS) should start keeping track of the cmx and nf roots at regular intervals.

• At the snapshot height, which is also the Genesis of the Voting Blockchain
• At frequent intervals, the VS should emit new blocks of votes and the resulting cmx, nf hash. For example, once every 10 minutes when there is at least 1 vote.

The VS does not need to keep all the intermediate hash calculations of every tree for verification. Only the root hash is required.

Vote Processing

Vote Verification

Once a vote is received, the Voting Server VS validates it.

1. The binary structure of the vote must be correct, and it should parse into the BallotEnvelope, BallotData, etc.
2. The binding signature must match the sighash
3. The ZKP must be valid
4. The spend signatures must match the sighash and rk

The votes are available (in encrypted form) to everyone in the forms of blocks produced by the VS.

Block Producer

The Voting Server VS gathers votes (and delegations) it receives and puts them into blocks. Unlike cryptocurrency blockchains, the Election Authority are sorely responsible for managing the election and the VS produces the Vote blocks.

The Election Authority signs each block.

It uses the same signature scheme as the vote binding signature.

Clients can download blocks and verify every transaction.

At the end of the Election, the complete blockchain may be offered as a single download to facilitate audits.

Block Structure

• size of block as u32 (including this field)
• CBOR of VoteBlock
• signature

#![allow(unused)]
fn main() {
struct VoteBlock {
    prev_hash: Hash,
    cmx_root: Hash,
    nf_root: Hash,
    votes: Vec<BallotEnvelopeBytes>,
}
}

The signature is placed after the binary serialization of the VoteBlock as CBOR.

The sighash is the Blake2b-256 hash of the CBOR serialization of VoteBlock with Personalization VoteBlockSigHash.

RPC

API Definition in JSight API documentation format.

Available online through the link above.

JSIGHT 0.3

INFO
  Title "Zcash Coin Vote API"
  Version 1.0

URL /vote
  Protocol json-rpc-2.0
 
  Method submit // Submit a vote
    Params
      @vote
    Result
      "hex" // Transaction ID
 
  Method getLatestHeight // Get the latest block height
    Params
      @blockRequest
    Result
      100 // Block height
      
  Method getBlock // Get a block by height
    Params
      @blockRequest
    Result
      @block

  Method getBlocks // Get a range of blocks
    Params
      @blockRequestRange
    Result
      [@block]

  Method getVote // Get a ballot by ID
    Params
      "hex"
    Result
      @vote

#======================== TYPES ==========================

TYPE @vote
{
  "electionId": 1,
  "data": "base64string"
}

TYPE @blockRequest
{
  "electionId": 1,
  "height": 100
}

TYPE @blockRequestRange
{
  "electionId": 1,
  "start": 100,
  "end": 200
}

TYPE @block
{
  "electionId": 1,
  "height": 100,
  "data": "base64string"
}