Topic: Thinking about Bitcoin and anonymous voting systems... (Read 2877 times)

Thanks very much for the links and explanation.

In another thread I refined the approach I outlined in this thread to solve a number of the problems you pointed out although in perhaps a quite different way.

In my approach I would group together a (large) number of voters into a "batch". The "ballots" would be sent as an encrypted payload to each voter in the batch where each ballot contained say 100 valid and 100 dummy encrypted vote keys for each candidate (with the batch member being able to know which are which by perhaps just the ordering of them). The idea behind this is that to create your actual ballot you randomly put together a vote (dummy or real) for each candidate and mix in a special vote that is actually something unique you can use later on to check your vote was actually delivered.

A completed ballot would be sent in an encrypted payload to a member of the following batch (without collusion it should not be possible for them to determine or change the vote without corrupting the content of the ballot). As the member of the following batch would be chosen randomly the idea would be that if you receive more than one vote you randomly choose to forward on all votes but one to another member of the same batch (this could be further worked out to make for better shuffling).

To qualify yourself as being able to have your vote delivered you must first have delivered a valid vote from the previous batch (apart from members of the first batch which could just be all dummy votes created by the system I guess). This would be determined by a "receipt" tx sent to the deliverer of the ballot that identifies who the vote was actually for and contains the unique data allowing the original voter to see that their vote was indeed delivered (and was not corrupted).

The final batch of voters would send their votes to the initial batch to complete the system. At the finish each voter will have a receipt tx containing a valid vote (for another voter). All votes can then be tallied publicly and each voter can verify that their own vote was correctly delivered.

I will check out the other information you mentioned - just putting this out as another possible approach.


Cheers,

Ian.

I think it could work!

Instant democracy!
Self-define democracy!

I tried to summarize my thoughts on using Bitcoin for anonymous & verifiable voting systems on the Bitcoin StackExchange. I could repost it here but for now I'll just link to it:

http://bitcoin.stackexchange.com/a/2874/512

I'm happy to discuss/clarify it further here. In summary, I suggest that voters register for an election with their real name and an encryption of a Bitcoin address they create for the purposes of voting. Voting is done by sending a transaction from this account to the account set-up by the candidate (the money can be returned). Since any unregistered voter can also send money the the account, you need a way to exclude all votes that were not sent from an address that was registered (and you can't see these addresses because they are encrypted). In short, you can throw some fancy crypto at the problem and only keep properly registered votes without ever decrypting the Bitcoin accounts.

I also wanted to respond to your comments on CommitCoin (I am one of the co-authors of it). Voting is just one application of CommitCoin and so we devoted the paper to discussing how "carbon-dating" commitments works in general and then how to do carbon-dating with Bitcoin.

In the voting example, the heavy lifting is done by the voting scheme Scantegrity. The technical details of Scantegrity are in the cited work. CommitCoin is just providing one simple service for Scantegrity: showing that certain commitments (to election date) made before an election are actually made before the election. We do describe specifically how these are inserted into the block chain in the appendix of the full version of the paper.

Our CommitCoin paper does rely on an understanding of Scantegrity to understand the voting example and wasn't written to be a stand-alone description of doing an entire voting protocol. Bitcoin factors in in only a small way.

Scantegrity with CommitCoin (and without) is a secret ballot voting system.

Finally, to comment on your suggested solution to step 3 of your voting scheme. It is similar to an anonymity service called Crowds. This type of system can be made to work but it will take some modifications:

• Votes must be encrypted under a key. If it is symmetric key, the voter and receiver must agree on a key. It is better to use public key encryption where I know how many hops my vote will go through before being decrypted.
• Voters are anonymous to a passive adversary. However if the adversary is one of the voters (or corrupts one), they will know how the voter who gave them the real vote will have voted.
• The above can be accounted for my having votes go through a number of voters before being sent to the actual candidate. This is the principle behind onion routing (Tor). However, the encrypted vote must change at every voter so you can't trace it through. This can be accomplished by layering a level of encryption on your vote for each hop, where each hop takes a level off. Alternatively, with public key encryption that is "homomorphic", you can simply rerandomize the encryption of the vote.
• The scheme has no integrity. Any voter can replace a vote they receive with a vote they generate. If even if there is a mechanism to detect the modification by the voter, the voter can't really prove what they did (without also being able to prove how they voted). If disputes cannot be proven, then anyone can spuriously dispute that their vote was modified to cast doubt on an election outcome they do not favor.
• As the number of voters grows, the number of dummy votes needs to grow to hide the origin of the votes. A better architecture is to use dedicated parties to filter the votes through. This is called a mix network. Mix networks can be constructed where the mixers can cryptographically prove they did not modify votes. Verifiable mix networks are the basis of many cryptographic voting systems.

http://en.wikipedia.org/wiki/Mix_network

Okay - have had an idea about how to do this step (which I guess it perhaps quite similar to what bitcoin anonymizers do).

Lets say we have three voters (voter_1, voter_2 and voter_3). Each voter will send at least two votes - one of them is a real vote (from a privately issued address) and the other is a dummy vote (from another privately issued address). The order of sending these votes will be randomly chosen.

Later voters will likely have received votes before they are going to cast their own so to mix things up these voters randomly decide when sending votes out to either send their own (real or dummy) vote or forward the others.

The following is an illustration of what might occur:

voter_1 ==> sends encrypted vote (xxx) to voter_2
voter_1 ==> sends encrypted dummy vote to voter_3
voter_2 ==> sends encrypted dummy vote to voter_1
voter_2 ==> sends encrypted vote (yyy) to voter_3
voter_2 ==> sends encrypted vote (xxx) to voter_3
voter_3 ==> sends encrypted vote (yyy) to voter_1
voter_3 ==> sends encrypted vote (zzz) to voter_1
voter_3 ==> sends encrypted vote (xxx) to xxx
voter_3 ==> sends encrypted dummy vote to dummy
voter_1 ==> sends encrypted dummy vote to voter_3
voter_1 ==> sends encrypted vote (zzz) to voter_2
voter_1 ==> sends encrypted vote (yyy) to yyy
voter_2 ==> sends encrypted vote (zzz) to zzz
voter_3 ==> sends encrypted dummy vote to dummy

So finally votes for xxx, yyy and zzz arrive but knowing who actually sent them (hopefully unless I've screwed up) should be impossible.

Correct?


Cheers,

Ian.

Yup - I did look at the article - absolutely zero detail about what they have actually done (technically).


Well foreign countries have not managed to manipulate Bitcoin yet, however, there hasn't been a fair paper ballot in many African countries and some Asian countries ever.


Cheers,

Ian.

I read about something called comittcoin, two researchers at a university implementing a voting system with a block chain, sorry don't have the link. But if interested, I guess googling should give some hits.

Everytime the feeble technocrats in my government tries to implement some sort of bullshit electronic voting method every university combines forces to attack it to prevent this from ever happening. It's just too easy to defraud or sabotage, no matter what electronic system you invent.

The good old anonymous hand ballots that can be physically recounted if there is a problem is the only sane solution and has held my country together for hundreds of years with this method. Mess with it and you risk reigniting separatist terrorism and possibly revolution if the vote is not seen as legitimate.

Even worse foreign countries could manipulate a digital method, or worse yet manipulate it then point the direction at another country starting some sort of fued/war. No thanks

Whether Bitcoin or an alternative block chain are actually used is not so much what I'm thinking about but instead whether the Nakamoto block chain combined with perhaps some other (maybe not yet invented?) technology can achieve free and fair voting.

Of course one does not want the government to know what your vote was - but unless we just want rule of the richest it is vital that both they and other 3rd parties can be certain that each voter had (or had the opportunity) to cast exactly one vote.


Cheers,

Ian.

I'm glad Satoshi's step 1 didn't involve government.

I don't think you would do it with bitcoin itself, you would make an alternative blockchain that stores votes instead of transactions.

I have read a few recent posts about using Bitcoin for some very different things such as for election vote tallying (with little or nothing in the way of any detail about how this can really work) and am not sure whether or not Bitcoin provides answers to the most challenging problems in this area.

To my mind most importantly one needs to ensure that each individual that is eligible to vote can vote, that no individual can vote more than once and that no authority can be (at least realistically) able to trace an individual's voting choice.

To my thinking this could be perhaps addressed in the following manner:

1) All eligible voters are sent an identifiable voting form (could be in the form of a small BTC payment made by the government that must be spent within a certain time frame).

2) An encrypted voting choice needs to be created by the individual (perhaps a newly generated BTC address created by your favorite party which would somehow need to be signed for the next step to work).

3) Encrypted voting choices to be anonymously exchanged by voters (with signature checks of these voting choices to ensure their validity).

4) Voting forms with the anonymous voter's voting choice are then returned to government (in the form of a BTC repayment).

I'm not sure if BTC is going to be a solution (and step 3 has perhaps little to do with it at all) but I think this kind of approach could lead to something quite important in the future.

Perhaps others can point out on any obvious faults and/or any better solutions to this idea?


Cheers,

Ian.