A Voting Protocol on Ethereum

Electronic voting, which uses systems to cast and count votes in an election, has been a topic of interest in cryptography over the last decade. Compared to traditional paper voting, electronic voting is environmentally friendly, can process and count in real time, and is less error-prone. As the effort and time required to participate in an election decreases, voter turnout may increase.

Currently, the only countries that use legally binding electronic voting are Belgium, Estonia, the United States, Brazil, the Philippines, India, and Venezuela. In countries such as Germany, Finland, the Netherlands, and Ireland, the use of electronic voting was banned after severe security and usability problems were found. (Read more)

Current electronic voting protocols rely on a public ledger to store the votes and on cryptographic proofs such as the Zero Knowledge Proof (ZKP), which establishes a method for some of the parties to prove to another that a statement is true, without revealing anything beyond the truth of the statement. The public ledger is commonly implemented as a relational database, which does not provide data integrity and immutability; this means that with current electronic voting protocols, where the systems are centralized, one would have to blindly trust the entity organizing the vote.

The centralization and data immutability problems of current systems could be solved with Blockchain technology, using it as the public ledger for the votes cast, achieving data integrity, transparency, and fault tolerance.

---

State of the art

Electronic voting protocols based on Blockchain technology use it solely to record the individual vote and to count votes with the help of a smart contract. Furthermore, these solutions are practical and scalable as long as Blockchain technology is, and they also allow for a secret ballot, an essential property declared a human right.¹

The Open Vote Network (OVN) protocol, implemented in a smart contract on the Ethereum Blockchain by Patrick McCorry², achieves ballot confidentiality. The main disadvantage of this protocol is that the computational cost of casting a vote is O(n) where n is the number of voters, which makes the implementation unsuitable for conducting elections with more than 50 people, since it would not be possible to count the votes.

The Ethereum network can only execute a limited number of computational instructions per block; on public Ethereum networks this limit is 4.3 million gas. On private networks that limit could be increased, but it remains computationally infeasible due to the computational cost involved. Another drawback of the protocol is that the last voter can compute the final tally and could act accordingly, approving or rejecting a vote since their ballot could be the deciding one.

Blind signatures were suggested by David Chaum, and electronic voting has been one of the main use cases for blind signatures. This is a solid solution for obtaining voter authorization while preserving anonymity. The first protocol using Blockchain technology with blind signatures was suggested in 2017 ³ . As a result of applying blind signatures, the protocol provides the voter with pseudo-anonymity (pseudo due to the nature of the Blockchain); even though the complexity of casting a vote is O(1), on the Ethereum Blockchain prior to the October 2017 hard fork it was not practical to verify blind signatures — after the hard fork it is possible to perform elliptic curve operations on-chain.

https://www.youtube.com/watch?v=2-sLbNHKhz8&ab_channel=Udacity

The blind signature protocol allows a voting scheme to decouple the vote from the voter while maintaining authentication. A brief recap of the electronic voting protocol would be:

• Voters: the list of voters

• Organizers: the set of election organizers, whose task is to register eligible voters and interact with them (blindly signing the ballots) over the course of the vote

Suppose Alice is a voter and Bob is an organizer.

We assume both parties have agreed to use elliptic curve cryptography with a sextuple of parameters predefined by the Barreto-Naehrig curve **(**altbn128)

$$\huge T= (p,a,b,G,n,h) \newline \color{gray} \tiny \text {Sextuple of parameters defining the domain of an elliptic curve}$$

Where the sextuple of parameters is defined as:

• p = an integer specifying the finite field of the function Fp

• a,b = integers ∈ Fp specifying an elliptic curve E(Fp) defined by the equation

$$\huge E: y^2 = (x^3+a*x+b)\space mod \space p \newline \color{gray} \tiny \text {Equation defining an elliptic curve}$$

• G = a generator point

• n = a prime number

• h = an integer

Where the values for the Barreto-Naehrig curve (altbn128) are:

p= 30644e72e131a029b85045b68181585d97816a916871ca8d3c208c16d87cfd47

The implementation has the following phases:

1. Alice obtains Bob's public key defined by P = Pkey* G and generates two random integers γ δ ∈ Z.

2. Bob generates a random integer r ∈ Z, computes the point R = r * G, and sends R to Alice.

3. Alice computes the point A = R + γ * G + δ * P, selects the x coordinate of A, and computes t= x mod(n) (if t = 0 mod n Alice has to regenerate the numbers γ δ ∈ Z from step 1)

4. Alice computes c = H ( m || t) mod n (the unblinded message) and c’ = c — δ mod n (the blinded message) and sends c’ to Bob.

5. Bob computes s’ = r-c’ * d mod n (the signature of the blinded message) and sends it to Alice

6. Alice computes s = s’ + γ mod n (the signature of the unblinded message)

7. The signature of the message m is (s,c)

---

Design

Ethereum Logo

The Ethereum Blockchain was chosen for the implementation of the blind signature protocol because, in contrast to Bitcoin, it is not only capable of storing data but also of enforcing the correct execution of the protocol thanks to its programmable nature through the development of a smart contract.

The issuance of blind signatures cannot be performed inside the Ethereum smart contract, since computing blind signatures requires the organizer to provide their private key. Due to the nature of the Ethereum Virtual Machine (EVM) execution environment, the organizer cannot sign the ballots without revealing their private key; therefore, only the verification of the signatures can be carried out inside the smart contract.

---

Verifying blind signatures on Ethereum

Several algorithms could have been used to implement blind signatures. The first option would have been to use RSA blind signatures, but given that the maximum string size in the EVM is 256 bits, using this method would be insecure since the signature could be factored within a few hours on a personal computer.

Blind signatures using Elliptic Curve Cryptography (ECC) use more compact key strings and can therefore provide a level of security even in an environment as constrained as the EVM. However, before the Ethereum network upgrade, verifying ECC blind signatures was not possible, which meant external libraries were needed to perform elliptic curve operations, since even verifying a blind signature would cost more than the gas limit available in a block — that is, it would never have left any change on the Blockchain.

As a result of the Byzantium hard fork, the addition of a point on an elliptic curve and the multiplication of a point by a scalar are natively supported in the EVM, which also means that such operations consume significantly less gas than before the hard fork. This change enables a practical implementation of ECC blind signatures on Ethereum.

function ecmul(uint256 x, uint256 y, uint256 scalar) public constant returns(uint256[2] p) {
    // With a public key (x, y), this computes p = scalar * (x, y).
    uint256[3] memory input;
    input[0] = x;
    input[1] = y;
    input[2] = scalar;

    assembly {
        // call ecmul precompile
        if iszero(call(not(0), 0x07, 0, input, 0x60, p, 0x40)) {
            revert(0, 0)
        }
    }
}

Multiplication of a point by a scalar

function ecadd(uint256 x1, uint256 y1, uint256 x2, uint256 y2) public constant returns (uint256[2] p) {
    uint256[4] memory input;
    input[0] = x1;
    input[1] = y1;
    input[2] = x2;
    input[3] = y2;

    assembly {
        if iszero(call(not(0), 0x06, 0, input, 0x80, p, 0x40)) {
            revert(0, 0)
        }
    }
}

Addition of points on an elliptic curve

/*
@dev Funcion para verificar firmas ciegas
@param m  mensaje sin cesgar
@param c mensaje ciego
@param s firma del mensaje ciego
*/
function verifyBlindSig(uint256 m, uint256 c, uint256 s) internal constant {
  uint[2] memory cP = eccPrecompiles.ecmul(pubKeyOfOrganizer[0], pubKeyOfOrganizer[1], c);
  uint[2] memory sG = eccPrecompiles.ecmul(generatorPoint[0], generatorPoint[1], s);
  uint[2] memory sum = eccPrecompiles.ecadd(cP[0], cP[1], sG[0], sG[1]);
  uint projection = sum[0] % n;
  require(c == uint(keccak256(abi.encodePacked(uintToString(m),uintToString(projection)))));
}

Function to verify blind signatures

---

Conclusions

The deployment of this protocol assumes the existence of a secure communication channel between the organizer and the voters. It also assumes the existence of a secure client.

Some security flaws in this protocol could be:

• The organizer could refuse to blind-sign some ballots or even generate an invalid signature

• The security of the blind signature scheme depends on the difficulty of solving the discrete problem in the altBN128 elliptic curve group.

• If the organizer's private key were stolen, double or fake votes could be generated.

• Ballot anonymity can be compromised using timing attacks; votes could be linked to the voter's identity if between the generation of the signature and the casting of the vote there are only a few or no votes cast.

Currently, it is not possible to implement a voting protocol on Blockchain (at least using the Ethereum platform) that can meet all the security requirements. However, with the advancement of technology and research, in the near future a more secure solution based 100% on Blockchain may be achievable.

---

References

1. Universal Declaration of Human Rights of 1948 | United Nations.

2. A Smart Contract for Boardroom Voting with Maximum Voter Privacy. Patrick McCorry. https://fc17.ifca.ai/preproceedings/paper_80.pdf

3. An E-voting Protocol Based on Blockchain. Yi Liu and Qi Wang. https://eprint.iacr.org/2017/1043.pdf