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.pdfDoes 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).