The project aims to address the challenges associated with determining the winner of an electoral process while ensuring trust, transparency, and security. It focuses on implementing cryptographic tools and a declaration system secured by asymmetric encryption. The project also involves handling a centralized declaration database, implementing a consensus mechanism, and managing a decentralized declaration base. The core concept is that citizens use pairs of keys to create and verify vote declarations, ensuring the authenticity of the voting process through encryption and decryption processes.
In this project, we address the issue of determining the winner of an electoral process. In an electoral process, each participant can declare their candidacy for the election and/or vote for a declared candidate. Electoral processes have historically raised challenging questions about trust and transparency, as elections are typically organized by the incumbent executive system, which is often a candidate for re-election and therefore suspected of interference. Additionally, the counting of votes involves poll workers, making it a time-consuming process with limited reliability since not everyone can verify that the count was conducted honestly. Furthermore, the anonymity of paper ballots means that no one can verify afterward whether their vote was counted for the correct candidate.
Another aspect to consider is the user-friendliness for voters. Specifically, a decentralized system would enable remote voting, which has long been considered a tool to combat voter abstention, which reached historic levels in the June 2021 regional and departmental elections in France (66.7% overall and up to 87% among those under 25). A bill was also submitted to the National Assembly on September 21, 2021, to allow postal voting. This bill represents a first step towards electronic voting, with the main argument being that postal voting has been in place in Germany since 1957, potentially justifying the difference in voter turnout between France and Germany (where it does not exceed 33%).
The objective of this project is to propose a framework for considering the protocols and data structures to effectively implement the process of designating the election winner while ensuring the integrity, security, and transparency of the election.
In this project, we consider the organization of an electoral process by single-member majority voting in two rounds (like here in France).
- Part 1: Implementation of cryptography tools.
- Part 2: Creation of a declaration system secured by asymmetric encryption.
- Part 3: Handling of a centralized declaration database.
- Part 4: Implementation of a consensus mechanism.
- Part 5: Handling a decentralized declaration base
In our model, each citizen has an electoral card defined by a pair of keys:
- A secret (or private) key used to sign their vote declaration. This key should only be known to the citizen.
- A public key allowing other citizens to verify the authenticity of their declaration (signature verification). This key is also used to identify them in a vote declaration, not only when they vote but also when someone wishes to vote on their behalf.
In this exercise, we will see that signing a declaration is done by encrypting the content (using the secret key), and verifying a signature is simply done by decrypting it (using the public key).
Furthermore, in our context, a vote declaration simply involves transmitting the public key of the candidate being voted for. In an election process, it's necessary for each person to be able to produce signed vote declarations to verify their authenticity. This signature consists of an array of integers that can only be generated by the sender of the declaration (using their secret key) but can be verified by anyone (using the sender's public key). Specifically, we will use the following vote declaration protocol:
-
A voter E wishes to vote for candidate C. In this case, E's vote declaration is the message "mess" obtained by converting candidate C's public key into a string representation (using the "key to str" function).
-
Before publishing their declaration, voter E uses a signature function (referred to as "sign" here) to generate the signature associated with their vote declaration. This signature will take the form of an array of integers obtained by encrypting the message "mess" with voter E's secret key (using the "encrypt" function).
-
The voter can then publish a secure declaration, consisting of their message "mess," the associated signature, and their public key. In this way, anyone wishing to verify the authenticity of the declaration can do so by decrypting the signature with voter E's public key: the result obtained should exactly match the message "mess."
For a first implementation, in this section, we consider a centralized voting system in which all vote declarations are sent to the voting system. The role of the voting system is to collect all votes and announce the election winner to all citizens. In practice, vote declarations are recorded in a file called "declarations.txt" as they arrive, and once the election is closed, this data is loaded into a linked list. To verify the integrity of the data and count the votes, the system must also retrieve the set of public keys of citizens and candidates, which are stored in files called "keys.txt" and "candidates.txt," respectively.
Limitations: it is supposed that the set of candidats is already known
In the previous section, we examined and implemented a centralized voting system where vote declarations were collected and managed by a regulatory authority. However, for trust reasons, it would be preferable to use a decentralized voting system, enabling each citizen to verify the vote results independently. Therefore, we will now turn to a blockchain, a decentralized and secure database where all network participants possess a copy of the base. In our context, the data comprises signed vote declarations, and the network participants are the citizens.
The focus is on the following voting protocol:
- Vote: Citizens must send their signed vote declarations over the network between the opening and closing of the election.
- Block Creation: Throughout the election, at regular intervals, voluntary citizens (assessors) collect and verify the latest declarations sent on the network, group valid declarations into a block, and send this block over the network.
- Data Update: When a citizen receives a new block from the network, they add this block to their database (which is in the form of a blockchain).
To deter fraud, a consensus mechanism known as proof of work, based on a cryptographic hash function, is employed. The general principle is described below, and we will work through the steps:
To create a block containing data (such as vote declarations), the creator must partially reverse a cryptographic hash function. The creator needs to find an integer nonce so that the hashed value of data concatenated with the nonce begins with a certain number of leading zeros. This partial inversion can only be achieved through brute force, and the time required grows exponentially with the number of zeros. However, when the nonce is known, it can be quickly verified that the result begins with the correct number of zeros. Therefore, the nonce serves as a "proof of work," verifying that the block creator performed significant computation for this partial inversion. A block is considered valid only if accompanied by a proof of work (i.e., a nonce). The choice of the number of zero bits limits the number of created blocks and implicitly defines the average time interval between successive blocks in the blockchain.
To limit fraud possibilities, a block creator must include in the data the hashed value of the previous block. This not only orders vote declarations chronologically but also aids in fraud detection. For instance, if a malicious citizen M wants to send false data to citizen C, and Bi is the latest block received by all citizens, M must include in their fraudulent block the hashed value of block Bi. However, citizen C will receive two blocks with the same predecessor: the fraudulent block and block Bi+1 (containing the sequence of legitimate data). At this point, citizen C doesn't know which one is fraudulent, but waiting reveals the answer. To deceive C, citizen M must continue sending fraudulent blocks, each containing the hashed value of the previous fraudulent block. As creating a block is resource-intensive, and other citizens continue to create blocks collaboratively, the chain composed of fraudulent blocks cannot progress as quickly as the one composed of legitimate data. Therefore, each citizen needs to follow the rule: at any given time, trust the longest chain of blocks received.
To set up the election, it is necessary to first generate a unique electoral card for each citizen, including their public and private keys, and record all the public keys from these electoral cards. To ensure the anonymity of the vote, the system should not know to whom these public keys belong. Additionally, citizens are responsible for keeping their private keys and must use them when voting to transmit a signed vote declaration. The voting system collects the signed declarations as they arrive and verifies the authenticity of each vote before counting it. The system also needs to verify that each citizen has voted at most once.
In the context of this project, we will simulate this voting process using three files: one containing the keys of all citizens, one indicating the candidates, and one containing signed declarations.
As part of this project, we will simulate the operation of a blockchain as following:
- Blockchain: directory representing the blockchain that a citizen has built locally, from blocks that it received from the network. This directory contains one file per block of the blockchain.
- Pending block: file containing the last block created and sent by one of the assessors. This block is waiting to be added to the blockchain.
- Pending votes.txt: text file containing the votes waiting to be added to a block. Start by creating the "Blockchain" directory. In this exercise we will simulate submissions voting by citizens and the creation of valid blocks by assessors (volunteer citizens). Then, we will create the corresponding tree of blocks, and calculate the winner of the election by trusting to the longest chain in the tree.
It is required to install
sudo apt-get install libssl-dev
After compiling (make), one simply has to run the following command: ./bin/main . Where represents the number of citizens, and the number of candidates.