Skip to content

Voting on Bitcoin Cash using Traceable Ring Singatures

Status: DRAFT (Version 2)
Authors: dagurval@pvv.ntnu.no
Date: April 2020

Abstract

Minimalistic and anonymous voting protocol on top of Bitcoin Cash. Participating, verifying and tallying does not require a full node, but is fully SPV client compatible.

Enable creation of an election system that:

  • Does not enable traceability of a vote to a voters identity.

  • 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

  • A voter is able to prove what he voted on at any time after casting the vote.

  • Scaling limitations (TBD)

Conceptual walktrough: Traceable Ring Signatures in Elections

This video goes through what traceable ring signatures are and how they can be used for voting in an election on Bitcoin Cash.

Traceable Ring Signatures in Elections

Example

TBD

Specification

Overview

To hold a vote the following setup steps are taken:

  • One entity needs to create a proposal.
  • The proposal details is provided to all participants.

How the proposal is provided is not covered. Notably the same data is needed for every participant to participate. This allows any participant to provide this data to any other participant, not relying on a single entity.

The only information exchanged off-chain is the proposal details. The remaining participation happens on the blockchain.

To cast a vote the following steps are taken:

  • Participants sign their vote and submit it to the blockchain.

  • All votes are transparent to all participants, but it is not possible to derive who cast a vote from the group of decoy signers.

After the vote ends, each participant queries the blockchain to tally the vote result independently. Votes can also be tallied during the vote for a partial result.

Creating an election

To create a election, 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) and the vote includes votes at given height.

  • End height The block height at which the vote ends (inclusve). Height is zero-indexed (genesis is block 0) and the vote includes votes at given height.

  • Set of hashed vote options A list of valid vote options hashed with HASH160 (Example: HASH160(Yes), HASH160(No) ,HASH160(Don't care).

  • List of participants The public key of every participant.

Election ID

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

Each participants MUST know of all the data belonging to a vote. Without this, they cannot participate. Hashing this data into the Election ID allows each participant to verify that they have received it.

The Election ID is generated as follows:

Hash160(salt || description || endheight || options || participants)

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

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

  • participants is the participant list sorted by public key integer value and concatenated.

Casting a vote

The first input of a casting transaction contains the vote payload.

Any output of the casting transaction is a vote cast notification output.

Vote Payload

The payload is published on the blockchain using the Transaction Input Payload Contract.

Payload requires the following properties:

  • The signed message must contain the vote itself.

  • It must be a ring singature where it's not be possible to derive which participant cast the vote.

  • It must be possible to detect if the same private key was used to sign multiple messages.

Payload size and limitations

The vote payload size is:

Field Size
Vote hash 20 bytes
Constant 44 bytes
Signature (participants * 64) bytes

The Transaction Input Payload Contract supports payloads up to 1503 bytes. This effectively limits elections to 22 participants. To support more participants, we'll need a more efficient signature scheme or a different method to publish the payload on-chain.

Table of participants vs. payload size:

Participants Payload size
2 192
5 388
10 964
15 1028
22 1472
23 1536
1024 65604

Vote cast notification output

All participants agree on a vote cast notification output. This output is unique to the election. Its purpose is to be an address all participants can observe to detect votes.

The output is to a P2SH script and defined as follows:

Locking script (standard P2SH output)
OP_HASH160
<hash of redeemscript>
OP_EQUAL
Redeem script
<election id>
OP_EQUALVERIFY

This redeem script is a anyone can spend contract. Anyone who knows the Election ID can spent these coins, allowing the utxos created to be removed from the blockchain. The contract checks that a single input equals to the Election ID.

Unlocking script
<election id> <redeem script>

Tally

To tally up the vote, every transactions sending coins the the notification address is downloaded. Then the transaction is inspected to see if it contains a vote payload.

  1. Derive notification address

  2. Look up transactions sending coins to the address

    1. Ignore transactions confirmed after proposal end height.

  3. Sort transaction by confirmation height, then transaction ID. A transaction ID is always unique, so this sort is deterministic.

  4. Load the voting payload from the first input.

    1. If there is not a payload in the first input, ignore the transaction.

  5. Validate payload.

    1. Validate that it contains a valid vote option.

    2. Validate that all signing keys are part of participation list.

    3. Validate that keyimage has not been used before. If keyimage has been used before, ignore this transaction (previous is still a valid vote).

  6. Include the vote option in the tally.

Known attack vectors

Notification address flooding

Single notification address may be flooded, causing slower election tally.

Implementations

Implemented in libbitcoincashkotlin and used in VotePeer.

Acknowledgements

Thanks to the following for review and their valuable suggestions for improvements:

  • Tobias Bergkvist

Implementations

Not yet implemented.