"Two option vote" contract for Bitcoin Cash

Version: 1.1
Authors: Dagur Valberg Johannsson, Jørgen Svennevik Notland
Date: 2020-09-04

Abstract

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

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 two 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

Before a vote, the participants are in agreement on the exact redeemscript to use. See Appendix A for the redeemscript we use.

The purpose of the redeemscript is to ensure a voter can only spend a coin from his contract address if he includes the correct information in the transaction to cast a valid vote.

To hold a vote the following steps are taken:

1. One entity needs to create a proposal.
2. 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.

No further communication is needed between stake holders. Voting happens independently on the blockchain.

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

Creating a proposal

To create a proposal, the following data is needed:

Salt A blob of randomly generated bytes. This helps to make each vote unique on the blockchain. If this data is only known to participants, it will increase the privacy of the vote, as outsiders cannot derive what is being voted on.

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

Option A An option to vote on (Example: Yes).

Option B Alternative option to vote on (Example: No).

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

List of participants The PKH (Hash160 of public key) of every participant.

Proposal ID

The proposal 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 proposal ID allows each participant to verify that they have received it.

The proposal ID is generated as follows:

Hash160(salt || description || option A || option B || endheight || participants)

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

participants is the participant list sorted by PKH value and concatenated.

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. To spend an input, the user must provide either option A, option B or blank option in the scriptsig.

If there are multiple spends at the same height, the user has spoiled his vote and cannot participate.

Otherwise, if a participant spends coins from the address multiple times, the earliestspend by block height is counted and the subsequent ignored. Rationale for ignoring subsequent votes, rather than spoiling the vote, is so that once a vote is cast, it cannot be spoilt at a much later time.

All votes must be confirmed at the votes end height or earlier.

Redeemscript

In CashScript, the cast vote function of the contract can be written as follows. For full contract and its Bitcoin Script equivalent, see Appendix A.

    /**
     * Cast vote
     *
     * @param pk The voters public key.
     * @param sig Transaction signature.
     * @param msg Proposal ID and option voted on, concatenated.
     * @param msg_sig Message signature.
     */
    function cast_vote(
        pubkey pk, sig tx_sig,
        bytes40 msg, datasig msg_sig)
    {
        require(hash160(pk) == voter_pkh);
        require(checkSig(tx_sig, pk));

        // The input arguments to this function are not signed, thus not
        // verified with the OP_CHECKSIGVERIFY above.
        //
        // To ensure the vote has not been tempered with, we additionally
        // sign the vote. The signature is verified with the OP_CHECKDATAVERIFY
        // call below.
        //
        // If we did not do this, the transaction would be malleable, and a
        // third-party malicious actor could swap out the vote with a different
        // one.
        require(checkDataSig(msg_sig, msg, pk));

        require(msg.split(20)[0] == proposal);
        bytes vote = msg.split(20)[1];
        require(
            vote == option_a
            || vote == option_b
            || vote == 0xBEEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF /* blank */);
    }

Code line	Description
require(hash160(pk) == voter_pkh)	Ensures public key belongs to voter
require(checkSig(tx_sig, pk))	Ensure transaction is signed by voter
require(checkDataSig(msg_sig, msg, pk))	Ensure that the vote is signed by voter
require(msg.split(20)[0] == proposal)	Ensure vote belong to proposal
require(vote == option_a && ..)	Ensure a valid vote option is cast

Deriving a contract address

Generate the hash of the full redeem script (parameters + redeemscript):

Hash160( OP_DATA_20 || proposal id || OP_DATA_20 || option B || OP_DATA_20 || option A || OP_DATA_20 || voters PKH || redeemscript)

Where

• OP_DATA_20 is 0x14 meaning "push next 20 bytes to stack".
• Voters PKH is the hash160 of a voters PKH.
• redeemscript, see Appendix A.

This hash is then used in a P2SH output and can be represented with an cashaddr.

A P2SH ScriptPubKey is as follows:

OP_HASH160 [20-byte-hash-value] OP_EQUAL

See BIP16 for more details.

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 above proposal end height.
- If there are no transactions, the participant has not voted.
- Find the transaction with lowest height
    - If there are multiple, spoil the vote.
- Locate all the inputs of the transaction that spend from the contract address.
    - If there are more than one, causing multiple votes to be cast, spoil the vote.
- Retrieve the option voted on from the scriptSig.

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.

Notes on design

Alternative - Relax 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.

It is possible to relax the input validation, by technically allowing votes that are invalid to the election to be cast. They must however still have valid signature.

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.

Alternative - More vote options

The contract can be extended to allow more options using the same design. How many options are possible is limited by the maximum length of transaction input scriptSig field. With the current network consensus rules, this field is limited to 10000 bytes on Bitcoin Cash.

The scriptSig needs to fit proposal ID, the PKH of a voter, all vote options and the redeemscript.

Adding more options increases the length of the redeemscript because of the additional comparisons, in addition to 21 bytes for each option (push + hash).

Implementations

• Reference implementation includes on-chain example vote script and support functionality.

• libbitcoincash Kotlin Bitcoin Cash library

• Used in VotePeer Mobile Application (via libbitcoincash)

Acknowledgements

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

• Donn Morrison
• John Nieri (emergent_reasons)
• Peter Rizun

Copyright

Copyright 2020 Bitcoin Unlimited

This document is licensed under the MIT license.

Appendix A - Two option vote redeemscript

Given that the value 0xBEEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF is used for casting a blank vote, using CashScript, the contract can be written as follows:

pragma cashscript ^0.4.0;

/**
 * Two-option-vote contract v1.1
 *
 * Contract for casting a vote on the blockchain. The contract supports
 * two options + blank vote.
 *
 * @param voter_pkh Hash160 of voters public key.
 * @param option_a Hash160 of the first option.
 * @param option_b Hash160 of the second option.
 * @param proposal Hash160 representing the proposal voted on.
 */
contract TwoOptionVote(
    bytes20 voter_pkh,
    bytes20 option_a, bytes20 option_b,
    bytes20 proposal) {

    /**
     * Cast vote
     *
     * @param pk The voters public key.
     * @param sig Transaction signature.
     * @param msg Proposal ID and option voted on, concatenated.
     * @param msg_sig Message signature.
     */
    function cast_vote(
        pubkey pk, sig tx_sig,
        bytes40 msg, datasig msg_sig)
    {
        require(hash160(pk) == voter_pkh);
        require(checkSig(tx_sig, pk));

        // The input arguments to this function are not signed, thus not
        // verified with the OP_CHECKSIGVERIFY above.
        //
        // To ensure the vote has not been tempered with, we additionally
        // sign the vote. The signature is verified with the OP_CHECKDATAVERIFY
        // call below.
        //
        // If we did not do this, the transaction would be malleable, and a
        // third-party malicious actor could swap out the vote with a different
        // one.
        require(checkDataSig(msg_sig, msg, pk));

        require(msg.split(20)[0] == proposal);
        bytes vote = msg.split(20)[1];
        require(
            vote == option_a
            || vote == option_b
            || vote == 0xBEEFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF /* blank */);
    }
}

The participants need to be in agreement on the exact redeem script. With CashScript 0.4.2 the above contract compiles to this bytecode:

OP_4 OP_PICK OP_HASH160 OP_EQUALVERIFY OP_4 OP_ROLL OP_4 OP_PICK
OP_CHECKSIGVERIFY OP_5 OP_ROLL OP_5 OP_PICK OP_5 OP_ROLL
OP_CHECKDATASIGVERIFY OP_3 OP_PICK 14 OP_SPLIT OP_DROP OP_3
OP_ROLL OP_EQUALVERIFY OP_ROT 14 OP_SPLIT OP_NIP OP_DUP OP_ROT
OP_EQUAL OP_OVER OP_3 OP_ROLL OP_EQUAL OP_BOOLOR OP_SWAP
beefffffffffffffffffffffffffffffffffffff OP_EQUAL OP_BOOLOR

This is generated with cashc-cli.js -A contracts/two-option-vote.cash