ZIP:publicly verifiable anonymous voting on the Zcash blockchain (with minimal protocol changes)

[arielgabizon]

I feel anonymous voting - whose result can be verified by anyone seeing the blockchain, could really be a killer-app for Zcash.
Here's an idea how to do it with no circuit changes and a simple minimal change to the protocol.
I've been thinking about this for a while, and it seemed it could be done with no circuit change,
but requiring that nodes keep track of more note commitment trees and nullifier sets corresponding to other tokens.
I think now that neither is necessary.
I give details next, but the basic idea is that for voting it's enough to have tokens where

• there is a single one-time issuance of coins,
• the nodes do not need to protect against double spend - they only need to check that each spend is legitimate in itself. (Actually, even this is not strictly necessary if the vote counter can verify SNARKs, but I feel this makes it smoother and there could be a potential DoS attack without it)

How it works:

I assume the set of legitimate voters, and their public keys, is known in advance to the 'vote issuer'.
The vote issuer creates a 1$ note (of this custom currency) for each voter with his public key, i.e.,
something that looks like (a_pk,1,rho,r) for random rho and r
and sends that note to the voter.

The vote issuer computes the commitment of these notes, and computes the resulting note commitment tree, and its root rt.

The idea is that now each voter will make a transaction with his note,
and indicate in that transaction who he is voting for (by, e.g., a signed message in the memo field, details later on)

For this to work on the blockchain we require the following change:
The transaction should have a boolean variable check_root such that
New Consensus rule: If (check_root == false) and (vpub_new==1) and (miner fee>=t), skip checking if the rt included in the transaction is a valid past root.

Here t is some appropriate value we chose;
and miner fee only includes value from additional transparent input as, obviously, we don't want to allow someone to pay a miner fee with a custom token that is not zec.

An advantage (for Zcash) of this approach is that the voter will need to spend some (real, not custom) zec to cast his vote.

Now, to cast a vote, the voter makes a joinsplit with his note and rt he got from the issuer,
together with a transparent input to cover the miner fee of at least t.
He will indicate his vote by a message signed by JoinSplitPrivKey
(this signed message can be shoved into the encrypted memo field)

Now, there will be a deadline for casting a vote.
After this deadline, to count the votes the vote counter (anyone who wishes to verify the vote) will scan the blockchain for all transactions with the root rt published by the vote issuer.
If he sees more than one transaction with the same nullifier nf, he will discard all those transactions;
otherwise, he will sum the various votes and get the result

[nathan-at-least]

See also some notes on building voting protocols on top of UDA: https://drive.google.com/file/d/0BwDmGb8qpc8RdjBELTRLWGVIcHM/view