This is an interesting proposal. I'm curious to hear any thoughts on how it compares to the protocol in Section 7 of this academic paper: http://crypto.stanford.edu/~xb/fc12/bitcoin.pdf

Both it and CoinSwap appear to enable two party mixing, with unlinkable transactions, providing an anonymity set of all similar transactions happening concurrently. Both depend on what you call hash locking. Both are complex but the complexity is in different spots: in CoinSwap, it requires a number of rounds and a third party Carol. In the paper, it requires a complex setup, including the cut-and-choose.

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

It is build on top of Bitcoin.
Paper: http://people.scs.carleton.ca/~clark/papers/2012_fc.pdf
Discussion: https://bitcointalk.org/index.php?topic=59956.0;all

It is build on top of Bitcoin.
Paper: http://people.scs.carleton.ca/~clark/papers/2012_fc.pdf
Discussion: https://bitcointalk.org/index.php?topic=59956.0;all

I am one of the authors of CommitCoin. I wanted to add a few points of clarification about CommitCoin to the discussion. The paper is available here:

http://people.scs.carleton.ca/~clark/papers/2012_fc.pdf

Does CommitCoin fork the blockchain?

No. It uses the same blockchain as Bitcoin.

Does CommitCoin burn money?

No. CommitCoin is actually carefully designed to not burn money. Instead of doing the obvious thing, substituting a message for a public key fingerprint and sending coins to it, we propose substituting the message in for the private signing key of a new account. You then compute the resulting public key and public key fingerprint, and sending 2 small amounts of bitcoins (for example the minimum transaction) to the new account.

Then using the new account, we send the 2 amounts of bitcoins back to the original account one at a time. This does a few things: (1) it introduces the actual public key (not just fingerprint) into the transcript, (2) by sending the money back, nothing gets burned, and (3) we use a crypto trick: for the second transaction, we use the same randomness in the ECDSA signature as we did for the first signature. This causes the private key to leak: you can compute it by inspecting the values in the block chain. Since the private key is actually the message, you can thus compute the message.

Is this safe to do?

It is not exactly riskless. First you have to make sure that the message has enough randomness to function as a private key. We sidestep this issue by only putting "commitments" (which are randomized) into the block chain.

The first transaction sending the money back to the original account is safe.

The earliest peers to receive the second transaction can compute the private key, and thus create a different transaction (signed with the right key, which they just learned) sending the amount to themselves for instance. If they rebroadcast their fraudulent competing transaction fast enough, or include it in a block that they themselves solve, it may get put into the block chain instead the real one.

This still doesn't burn money (no impact on inflation) but users of CommitCoin should be prepared to "pay" a small amount if the nodes are dishonest.

How do you build a voting system from this?

The article may not have captured this fully: the verifiable voting example is 95% Scantegrity and only 5% CommitCoin. We are only adding a small amount of additional verification for a particular corner case in Scantegrity.

Scantegrity is an electronic optical scan voting system. You vote on paper and the paper is collected, but it is also scanned electronically (the tallies from both should match and this is standard optical scan). But even if someone were able to modify both the paper ballots and hack the database, Scantegrity will be able to detect it; it uses an additional layer of verification based on crypto. It is a very cool voting system and worth looking into more. The main designer is David Chaum, who pioneered cryptographic cash. Scantegrity on Wikipedia:
http://en.wikipedia.org/wiki/Scantegrity

CommitCoin is used only once in the election. It is used to commit to some election auditing data that must have been generated before the election starts for the audit to be valid. Since CommitCoin allows you to "carbon date" messages, you can come along after the election and be sure the election data was fixed prior to the voting period.

It is not the case that every voter is sending their votes into the block chain (although this could be an interesting modification).

Can you have both secret ballots and verifiable results?

Yes. Crypto can do seemingly impossible things. One of those things is having a voting system where ballot is anonymous (you can't prove how you voted) and yet you can make sure that your ballot is included unmodified in the final tally!  Crypto voting systems are often called E2E or end-to-end verifiable. Scantegrity is one, there are others. Scantegrity is the only one that has been used in an actual governmental election (two municipal elections in Takoma Park, Maryland, USA).

Is carbon dating just a fancy way of saying timestamping?

No, carbon dating is actually a very different concept. The block chain does both timestamping and carbon dating. Transactions are time-stamped and other nodes do some general vetting of the timestamp before accepting it for inclusion into the block chain. So if you generally trust the bitcoin network, the timestamp is enough.

But let's say you didn't trust the network at all (even in the extreme case of a 51% attack). If I show that we've put a commitment into block 145535 (which we did), there have been tens of thousands of blocks created since then. Even if I controlled the network, there is no way I could actually compute all those blocks in any time less than a certain amount of time (based on how much computational power you think I have). It would take on the order of months.

The accumulation of blocks after something is inserted is akin to the accumulation of carbon on a physical object. You have a sense of the rate of accumulation (and this can't be arbitrarily changed), you know how much accumulation there has been, and so you can estimate a date. It will be fuzzy. But its enough to distinguish, for example, something that happened a month before an election from something that happened a day after the election (if you are making the decision a few days after the election).

Hi everyone. I am a researcher in security and cryptography. I recently wrote a paper on using Bitcoin to "carbon-date" messages. It was covered by the New Scientist. The article is being discussed in this thread: https://bitcointalk.org/index.php?topic=59956.0 I am Jeremy Clark from the article.

I wanted to add some clarification to what our protocol does/does not do to that thread but am not authorized to reply there. I hope someone can grant me access to that thread.