Skip to content

"Multi option vote" contract for Bitcoin Cash

Version: 1.0 DRAFT
Authors: Dagur Valberg Johannsson
Date: 2021-12-03

Abstract

"Multi option vote" is a minimalistic and transparent voting protocol on top of Bitcoin Cash and other blockchains supporting OP_CHECKDATASIGVERIFY. Participating, verifying and tallying does not require a full node, but is fully SPV client compatible. Votes are non-transferable.

The "Multi option vote" contract is derived from [two-option-vote-contract], supporting more vote options and improved scalability for large scale elections.

Requirements

Enable creation of an election system that:

  • Can prove to an individual that their vote was counted.

  • Can prove to an individual the non-existence of fake votes.

  • Does not enable a single entity control over tallying votes and determining election results.

  • Does only allow eligible individuals to vote in an election.

Limitations

With the multi option vote protocol, votes are traceable to voters identification (public key).

The system is arguably more susceptible to coerced voting as a dishonest voter cannot plausibly claim to have voted differently than he did.

Example

An organization's chairman needs to get an expense approved by majority vote of the organizations members.

Each member has a voting-enabled Bitcoin wallet on their phone. They receive a push notification that a new vote is available to them along with the data needed to participate. No more interaction is needed with the chairman. The remaining communication happens on the blockchain.

With the wallets, each member is able to cast their vote to the blockchain.

Each participant is able to observe all other votes cast in real time by observing the blockchain.

When the vote ends, each participant is able to tally the vote and determine the result by themselves.

Specification

Overview

To hold a vote the following steps are taken:

  1. One entity needs to create an election.
  2. The proposal details is provided to all participants, in full or compressed*.

To create a proposal, the following data is needed:

  • Salt A blob of randomly generated bytes. This helps to make each election unique on the blockchain.

  • Description A string describing what is voted for (Example: Toss a coin to your witcher?).

  • Begin height The block height at which the vote starts (inclusive). Height is zero-indexed (genesis is block 0).

  • End height The block height at which the vote ends (inclusive). Height is zero-indexed (genesis is block 0).

  • List of vote A list of valid vote options.

  • List of participants The public key of every participant.

Providing the proposal details to voters in full or compressed has trade-offs in how much trust is needed of voters to thid parties.

Notably, providing election details in full requires no trust and no further communication is required for the voter to participate or follow the election. He only needs to interact with the public block chain.

It is recommended to make both compact of full details available to a voter and let them decide on this tade-off between resource usage and trust.

A voter with full election details

A voter with full election details can cast a vote without third party interaction, submitting it directly to a public blockchain.

A voter with full election details is able to individually tally the entire election. Votes can also be tallied during the vote for a partial result. The voter is also able to take the role as a third-party tallier for other voters, including providing cryptographic proofs of their tally being correct.

The same data is needed for every participant to participate and tally the election. A voter with full data is able to provide it to other voters, giving them the same benifits. He can also create compact election details to other voters, including a compact merkle proof that they are part of the list of participants.

A voter with compact election details

A voter with compact election details can cast a vote without third party interaction, submitting it directly to a public blockchain. However, to know that they are eligible to cast a vote, meaning part of the participant list, they SHOULD have received a merkle proof that they are in the participant list.

The benifit of receiving compact election details is bandwith and computation savings, mainly with large elections. With compact election details, the full list of participants is replaced with a single merkle root hash of 32 bytes. Each participant public key is is 33 bytes, so the savings are:

(number of participants * 33 bytes) - 32 bytes. For elections with 100 000 participants, this equals to 3.3 MB of storage savings. In this case participation requires data of typically less than 1KB, rather than 3.3MB. Additionally, the voter does not have to compute the merkle root hash themselves, saving processing power.

When provided compressed election details, the voter needs a third party (that has the full details) to tally the election to get the results. However this tallyer provides cryptographic proofs that a voters vote was tallied or not tallied. They can also proof that accumulative vote count matches the number of ballots counted. If a tallier refuses to provide proofs, then the voter knows he cannot trust the result.

Election ID

The Election ID consist of a hash derived of all the data belonging to a vote.

With exception of full list of participants, each participants must the data belonging to a vote. For casting a vote, a participant must know the merkle tree root hash of participants, but for tallying the election, they need to have the full list of participants. Hashing the required data into the Election ID allows each participant to verify that they have received the correct data.

The Election ID is generated as follows:

Hash160(salt || description || beginheight || endheight || options || merkle tree root hash of participants)

  • beginheight is encoded as a unsigned big-endian 32-bit integer.

  • endheight is encoded as a unsigned big-endian 32-bit integer.

  • options is the list of vote options hashed with HASH160, sorted by interger value and concatinated.

  • participants is the merkle root hash of a list of the participants.

Participant merkle tally tree

Participant Merkle Tree is a type of merkle tree of all participants with the following properties:

  • All voter public keys are in the lowest layer, where if needed, null nodes are used to balance the tree. Null nodes are hash value is 32 bytes with 0.

  • Voter public keys are numerically sorted.

  • Leaf nodes (public keys) have a extra wrapper node above them.

Participant Merkle Tree

Participant Merkle Tree with 3 voters.

With a merkle tree with these properties, it is possible to generate merkle proofs proving:

  • A public key is part of participant list
  • A public key is not part of participant list
  • The number of public keys (number of participants)

Casting a vote

Each participant derives his own contract address (see deriving a contract address below). He then sends two transactions.

  1. Sends coins to the address (generates an output to the address).
  2. Spends the coins from the address (uses an input from the address).

The redeem script used to spend from the address also forces the user to cast a vote. User needs to cast a vote with a valid option, or it will be ignored.

If there are multiple spends at the same height, the one with the lowest transaction ID used.

All votes confirmed before begin height are ignored.

All votes confirmed after end height are ignored.

Locking script

The locking script is a standard P2SH locking script.

OP_HASH <hash of redeem script> OP_EQUAL

Unlocking script

The unlocking script follows the P2SH standard, with inputs pushed first, and finally the serialized redeem script.

Code line Description of pushed data
<Signature for vote> 64 byte Schnorr signature
<Election ID>   20 byte hash of election
<Vote> 20 byte hash of vote option
<Public Key> 33 bytes of compressed pubkey
<Signature fore transaction> 65 byte Schnorr signature (1 byte for flags)
<Redeem script> See section redeem script

Redeem script

Code line Description
OP_OVER Copy public key, to be consumed by OP_CHECKSIGVERIFY.
OP_CHECKSIGVERIFY Verify the transaction is signed by the voter.
OP_DUP Copy public key, to be consumed by OP_EQUALVERIFY.
OP_HASH160 Hash public key.
<PKH> Push hash of voters public key.
OP_EQUALVERIFY Verify public key belongs to voter.
<2> Push the value '2'
OP_PICK Copy the election ID, to be consumed by OP_EQUALVERIFY
<Election ID>   Push the election identifier.
OP_EQUALVERIFY Verify the election ID input is correct.
OP_ROT  
OP_ROT Move election ID into place on stack.
OP_CAT Concat election ID and vote, this is the message signed.
OP_SWAP Swap message and public key on stack.
OP_CHECKDATASIGVERIFY Verify the vote was signed by the voter
OP_DEPTH  
OP_NOT Check that there are no more inputs in unlocking script.

Deriving a contract address

Each voter has a unique contract address for casting a vote. This uniqueness comes from the users public key hash and the election identifier being part of the redeemscript.

The derive the address for each user, derive their redeem script and generate a standard P2SH locking script and address from it.

Tally

To tally up the vote, the contract address for every participant is derived.

For every participant:

- Derive contract address
- Look up transactions *spending* from the address
    - Ignore transactions confirmed before begin height.
    - Ignore transactions confirmed after end height.
- If there are no transactions, the participant has not voted.
- Sort transactions by confirmed height, then transaction ID.
- For each transaction:
    - Locate the vote in the scriptSig
    - End if vote is valid.

Known attack vectors

Vote withholding attack

A vote can be held without a voter in the participant list being given enough information to cast a vote.

This is mitigated by having all other participants needing the same information to participate. Any other honest participant is able to share this information.

Future research may be done on enforcing publication of proposal details on the blockchain before a proposal can be voted on.

Differences from "two option vote"

Relaxed vote option validation

When casting a vote with the two-option-vote contract, the vote option passed as input is validated in two ways.

  1. The option shall be signed by the voter and this siganture is validated.
  2. The option shall be valid for the election.

This ensures that any vote cast must be a valid one.

We relax the input validation, by technically allowing votes that are invalid to the election to be cast. Votes are then validatied during tallying and ignored if invalid.

When this is done, the contract becomes more flexible and allows for holding elections with any number of votes. The trade-off is that now the vote option cast is no longer validated on the blockchain and must instead be validated in the clients of the users who tally the election.

Participant merkle tree

See above

Implementations

Acknowledgements

TBD

Copyright 2021 Bitcoin Unlimited

This document is licensed under the MIT license.