It's been a while since I last did any hacking on Solon Voting. Solon is my project to implement secure e-voting for delegated democracy platforms. You can read previous blogs here.

When I started Solon, I was first focused on just tweaking Liquid Feedback in order to enable use of cryptographically secure e-voting algorithms. I wasn't aware that an open source implementation of a homomorphic e-voting algorithm actually exists. But then a couple of people introduced me to Helios Voting. This has been great news. What remains now is basically to glue together Helios with the already existing Solon-LiquidFeedback combination, and we will have a first ever cryptographically secure voting solution for delegated democracy. Of course, this is a very rough prototype, but it will properly encrypt the votes and will produce verifiably correct results.

Last week I had some vacation, so I finally had time to play with Helios a bit more. The results of this week's hacking are now committed on Github.

For a first proof of concept I took the approach of treating Helios like a black box. I used Wireshark to dump all HTTP traffic related to creating a referendum, then used Analyze > Follow TCP Stream to copy paste the HTTP data into a text file (see github). Then I've created a sample python script that is able to create a new referendum, add questions, add eligible voters and finally open the referendum for voting. This code can then be used (and refined!) to implement an actual Solon Voting secure e-voting backend that will make HTTP calls to Helios.

What remains to do (Summer vacation, maybe?) is still to close the referendum and compute and extract the results.

Also there will eventually have to be some hacking on Helios to try to support preferential voting (Schulze method). I will explain below how I think I can do that without having to write a single line of crypto code, but it would be nice to still provide a similar user interface as exists in Liquid Feedback, where user can move the alternatives up or down to show his preferences: best alternative on top, worst alternative at the bottom.

Encoding preferential voting as approval voting

Update: Below is a first, and working albeit naive, attempt at this problem. Please also read this post with a better proposal.

Ok, the last remaining problem is how to map a preferential voting method (Schulze, in Liquid Feedback) to an e-voting algorithm that supports approval voting (Helios). (Approval voting is just "pick 1 out of N alternatives" or "M out of N", exactly how we usueally vote in elections.)

Let's first recap the voting rules in Liquid Feedback:

Suppose you can vote for 3 different alternatives. Let's call them A, B and C. Now, in Schulze method a sixth alternative is always present, called the implicit Status Quo alternative. I will call it Q, below. The point with Status Quo is that should it ever win a referendum, it means "do nothing" or "nobody wins" is preferred over all the given alternatives.

Liquid Feedback encodes (and I believe this is directly from the Schulze method too...) your vote with an integer adhering to the following rules:

1. Status Quo is always 0.
2. You can give each alternative a rating from +N to -N (ie +3 to -3 in our example).
3. Many alternatives can be rated as equals. For example, the following is permitted: (A, B, C, Q) = (1, 1, 0, 0)
4. No gaps are allowed. For example, the following is not permitted: (A, B, C, Q) = (3, 1, 0, 0) but the following is permitted: (A, B, C, Q) = (3, 2, 1, 0)

(The observant reader will notice that number 2 actually follows from the other requirements. But I tend to mention it on its own as it helps to understand how the encoding works. I'm an engineer, not a mathematician!)

Now, the obvious way to use an approval voting system like Helios is simply to map all possible combinations of (A, B, C, Q) into their own choices in Helios. This is feasible for a small number of alternatives, it's no coincidence I used only 3 here. So we could create a referendum in Helios where the choices are:

(0, 0, 0, 0)
(-1, 0, 0, 0)
(-1, -1, 0, 0)
(-1, 0, -1, 0)
(-1, -1, -1, 0)
(1, 0, 0, 0)
(1, 1, 0, 0)
(1, 0, 1, 0)
(1, 1, 1, 0)
(-2, -1, 0, 0)
(-2, 0, -1, 0)
(-2, -1, -1, 0)
(-2, -2, -1, 0)
(-2, -1, -2, 0)
(2, 1, 0, 0)
(2, 0, 1, 0)
(2, 1, 1, 0)
(2, 2, 1, 0)
(2, 1, 2, 0)
(-3, -2, -1, 0)
(-3, -1, -2, 0)
(3, 2, 1, 0)
(3, 1, 2, 0)
(0, -1, 0, 0)
(0, -1, -1, 0)
(0, 1, 0, 0)
(0, 1, 1, 0)
and so on...

Already you can see this is rather wasteful, but the point is that it can be done. The above is of course not very user friendly, rather we would need to implement a nice user interface where the user can express his preference by ordering the alternatives (like in Liquid Feedback) and then some JavaScript code will find the correct encoding from the above list, that matches the graphical ordering performed by the user.

For the academics reading this: Note that providing a too large list of candidates opens up possiblities for various coercion / forced abstention attacks. Otoh, so does the next idea too:

If there are a large number of alternatives to order into a preferential list, the above naive method will not work. The Acquisti paper describes an idea for providing write-in votes in a homomorphic election, where the idea is to use an anonymizing mix-net to propose the candidate/alternative you intend to vote for, which is then listed as a candidate/alternative, after which you can cast your vote with the homomorphic algorithm as usual.

This idea could be used to enable preferential voting and would be usable also when there is a larger number of alternatives. It would not be necessary to encode all possible combinations up front, rather combinations would be added to the Helios referendum on-demand. Instead of implementing a mix-net, one could also take the approach that it is possible to cast secret votes only using such combinations that somebody has already cast a public vote for. (See private vs public votes here.) Still, note that Helios in any case doesn't actually support such on-demand additions at the moment. The ballot is frozen at the start of voting.

There's probably some much more efficient way to encode preferential voting into a homomorphic e-voting algorithm. As far as I know, such a solution has never been presented in the academic literature. If you're a researcher in the area of e-voting crypto, consider this a challenge!