Are there any truly anonymous cryptocurrencies?

Question

I've been looking into Bitcoin recently and stumbled upon numerous notes how Bitcoin is not anonymous at all, or how it's only partially anonymous and you can easily trace your funds.

So, this brings us to my question: is there any true anonymous cryptocurrencies which I can use and there will be no trace left.

I am a fairly new member to the cryptoworld, so please, keep it simple. :)

Answer 1

The short answer is no. The long answer is split into three parts, each headed by a bold word.

1. I will talk about the existing privacy tools in Bitcoin.
2. I will talk about some pie-in-the-sky theoretical crypto which would achieve full anonymity (but which can't be done feasibly today).
3. I will talk about CryptoNote, its limitations, and feasible ways around it that could be implemented today, specifically those that have already been implemented by Monero.

Today, you can do a lot relative to stock Bitcoin in the direction of privacy. Two strategies I should mention are CoinJoin and CoinSwap.

1. CoinJoin works by effectively pasting together transactions. In Bitcoin, each transaction is a list of inputs tied (by digital signature) to a list of outputs. The transaction is valid if the total output value is less than or equal to the total input value (any difference is a "transaction fee" claimed by miners), and if every input is a valid (not already spent) output of an old transaction. CoinJoin takes transactions from two or more users, combines the input and output lists, and has both users sign the resulting transaction. The result is that the standard flow analysis idiom of "all inputs are owned by the same person" and "all outputs are owned by the same person, except maybe for a change output" is broken. CoinJoin is tricky to implement well: output values should be as uniform as possible to avoid grouping them and matching them to input values; the resulting outputs should not be spent at the same time, since this also groups them; the join should involve two distinct parties, neither of whom is some central server participating in every join. Currently there are no good tools out there which satisfy all these requirements, but there are several in development (such as DarkWallet). Keep an eye open.
2. CoinSwap does trustless mixing, even across different blockchains (as long as each has a sufficiently rich scripting system). It is too complex to summarize here, but the result is the same as if two parties switched private keys in person, except that there is no room for cheating. That is, coins are moved between parties but the blockchain does not see this and therefore chain analysis cannot link them — except to the extent that they look funny, so if there are almost no users doing this, their transactions can be linked on this fact alone. To the best of my knowledge, there are no tools which support this. I am developing a Bitcoin wallet for experimental features such as this that will support it, but it may be several months or years away.

Total anonymity, in the sense that when you spend money there is no trace of where it came from or where it's going, is theoretically possible by using the cryptographic technique of zero-knowledge proofs. As an extreme example, you could imagine that rather than publishing blocks mapping old outputs to new ones (which is what transactions are in Bitcoin), miners published zero-knowledge proofs that they had a valid set of transactions which, in aggregate, mapped the old set of all outputs to the new set of all outputs. You could further obscure this by having the recipient choose the destination address(es) and pass different ones to every miner. That way, only the miner who gets the block (who is probably different for every block) and the recipient knows where money is going.

In what I've described, the values of all coins would still be visible, and perhaps tracking could be done by linking similarly-valued coins. We can fix this with homomorphically-encrypted values, say.

The point of this musing is that there are no strong theoretical reasons that what you want is impossible. But I'm going to burst the bubble I just created and talk about practical problems: firstly, to do this kind of general computation is zero-knowledge even remotely feasibly, you need to use a system which has a trusted setup (in cryptographic terms, the scheme is secure only in the CRS (common reference string) model). This means that some party, the scheme's creator probably, has access to secret data which will allow them to produce false proofs, effectively allowing them to undetectably print money for all time. A recent example of such a thing is the paper SNARKs for C by Eli Ben-Sasson et. al., which provides a lot of historical context.

Secondly, even with this fatal flaw, these schemes are not all that computationally feasible. Zerocoin, now superceded by Zerocash, took this approach and needed to create serious restrictions: all coins have the same value, there is no scripting (even for multisignature transactions, I believe), and even so some serious work went into special optimizations to do whatever was left (such as hashing) in zero knowledge. For ZeroCash research is going into doing the initial setup in a multi-party computation so that no individual has the secret material needed to print coins; there would be several, and as long as even one securely destroyed their data, the currency would be safe from forgery.

However, ZeroCash's trusted setup is orders of magnitude more complex than any other MPC that has ever been done. And the most efficient MPC schemes known depend on a trusted-setup as well, so we haven't gained anything.

Having said that, we can get something weaker than total anonymity, and it looks like we can do it in a feasible way. As has been mentioned, CryptoNote-based currencies use ring signatures (contrast group signatures, which involve a trusted party) rather than plain old ECDSA signatures in the proof-of-ownership part of their transaction signature scheme. Arguably the most well-known cryptocurrency that was originally based on CryptoNote is Monero. Whilst Monero has subsequently deviated substantially from its CryptoNote origins, it still implements many of the key concepts below, and additionally improves a lot of the problem areas originally highlighted in this answer.

To understand how CryptoNote works we must first recap how Bitcoin transactions work. Essentially, in Bitcoin each transaction output has a public key associated to it (identified, though not revealed, by the Bitcoin address on the output), and to spend that output you need to produce a small script including a digital signature using this key. When everyone sees that transaction, they see that the old output(s) are spent (so they can forget about it, except as far as keeping historical blockchain data for new users) and that new unspent output(s) have been created. Ring signatures, on the other hand, are associated to an arbitrary set of public keys, and knowledge of only one is required to make a signature. CryptoNote uses this by having each transaction input be a set of potential unspent outputs of the same value, signed by a ring signature using all those outputs' associated keys. It is impossible to determine which one is the "real" one that the signer is actually spending.

You might ask, if it's impossible to determine which outputs are being spent, how can double-spending by prevented? CryptoNote solves this using a special ring signature algorithm (which is a modified version of existing signatures, so this is original cryptography and their security proof should be scrutinized — fortunately it is not too complicated) in which the real signing key has a key image associated to it, which must be published alongside the signature. This key image cannot be reversed to get the original key and deanonymize the sender, but if a double-spend is attempted, users will see that the same key image is used twice and reject the second attempt.

This provides good anonymity, but even with the improvements listed presently, this is not a zero-knowledge scheme. This means that linkability is confounded but an adversary with good analysis tools will certainly be able to glean a non-zero (literally, infinity times as much as zero) amount of information.

This is a very promising direction, and these signatures are feasible to verify by ordinary computers (though they are more difficult, so scaling will be worse than Bitcoin's), but there are some serious limitations. Fortunately, all are fixable. The following list is the result of conversations between myself, Greg Maxwell, Peter Todd, Mark Friedenbach, Adam Back and several others (who I'm sure will contact me to be listed :)), and to the best of my knowledge hasn't been published anywhere. So aspiring anonymous altcoins developers, here is a wishlist:

• In Bitcoin, because transaction outputs are incontrovertibly spent, the total list of unspent outputs grows only very slowly. Nodes with limited storage are able to store this, and basically nothing else: when they see a new block, they verify it then update their list of unspent outputs accordingly. In CryptoNote this is impossible since transaction outputs are never definitely spent: there is a giant list of potentially spendable outputs, and a giant list of spent key images, and both of these grow very quickly and never shrink. Current CryptoNote implementations, except for Monero, store this all in RAM, which puts a pretty serious cap on their scalability today. One of Monero's scalability improvements is to store this set on disk in a very fast LMDB database, but the set of mixable outputs is still unbounded and is expected to grow faster than Bitcoin's comparable utxoset.

However, this can be further be improved by having users store only the outputs whose keys they own (plus some extras for anonymity) and only a subset of spent key images, which I will describe. The set of outputs would be stored in an insertion-ordered Merkle tree (so a user storing almost none of the tree can easily verifiably append new outputs, but can't detect duplicates, which is fine). The set of images would be stored in a image-ordered Merkle tree (so a user storing almost none of the tree can easily add a new key image and verify that it didn't exist before, given a proof of insertion, which is basically a path from the new node to the root of the tree, along with the siblings of each node along the way). To spend an output, the user provides a ring signature including the output, with appropriate key image and proof-of-new-insertion.

Note that to produce a proof of insertion for the new key image, the user needs to store all its neighbors in the key image tree. Since key images are random-looking, how can this be done without storing the whole thing? The answer is prefix-filtering. When a user creates a new key, he creates one whose first 10 bits (say) are a specific ten-bit sequence that all his key images will have. He stores every key image that starts these ten bits so that he can produce proof-of-insertion of such images. The result is a reduction in anonymity (by a factor of $2^{10}$) since everyone will know that nearby key images are more likely to be owned by the same person than are far-away ones, but a corresponding reduction in storage requirements (by a factor of $2^{10}$) and an increase in key generation time (since on average $2^{10}$ keys will need to be generated before one with the right prefix comes along). This is a tradeoff that every user will have to make.

Peter Todd has suggested choosing a new prefix every few months or years, and retiring those in which every known key image has been used. This gets more privacy for the storage hit than simply decreasing the prefix length, since two key images in different prefix sets don't reveal their common owner.

• With ring signatures, the anonymity set is only as large as you make it, probably just two or three potential keys per signature.

We can improve this to effectively CoinJoin all transactions in each block (with the caveats that (a) miners can deanonymize the CoinJoin, reducing anonymity to the smaller set provided by the ring signatures, and (b) it is possible to miners to detectably cheat, so there is a small window after mining in which block content might be invalidated by revealing its cheating, which increases complexity) (the complexity hit is because it is important that the block content, not the block itself, be invalidated, since otherwise miners could deliberately cheat then reveal the cheating later, giving them a large window in which everyone else is mining a bad chain). The exact scheme is described at the very top of this IRC log.

(The same security can be provided with fancy cryptography, specifically one-way aggregatable signatures ("just the math" by Greg Maxwell), which depends on pairing-based cryptography, which is slow and requires new security assumptions that make some people uncomfortable. The exact way these would be used is described from 21:24:58 onward in these IRC logs. It is very cool that we can get the same security with no new crypto.)

• With ring signatures, your anonymity can be compromised after the fact by others in your anonymity set. For example, if you spend an output using a ring signature along with two other outputs, then those other outputs' owners spend them with a single-signature ring signature (so they are incontrovertibly spent), it is now clear which of the three you used is yours, since each can be spent only once. This can be done long after the fact, which complicates analysis.

This can be fixed by requiring a minimum size of anonymity set, as Monero has done on a protocol level since March, 2016. But then we have a new problem — there are only so many outputs of any given size, and since all outputs in an anonymity set must be the same size (so the network knows how much you are spending), this might not be possible. This can be fixed by allowing outputs of any size in the anonymity set, and taking the minimum size to be the spend amount. But then given a ring signature across several outputs' keys, people will know that the output with smallest size will be the "real" one. This is because each output can only be spent once, so if you mix it with smaller outputs, you are basically shrinking it to the size of those outputs since the network will only recognize the smaller value.

All these problems are addressed in the next point.

• With ring signatures, you need all potential inputs to have same (or similar) value, which greatly restricts your anonymity set.

In fact, Greg Maxwell and I found a way such that every single output can be read as any uniform distribution of outputs (so 1BTC might be spendable as a single 1BTC output, or two 0.5 BTC outputs, or three 0.33 BTC outputs, etc.) There is a single "real" distribution, but only the creator of the output knows this, and it is not revealed except in the case of leaked keys. Therefore, literally every single output size can plausibly be claimed to be created by every output, and therefore all outputs can participate in each anonymity set. This scheme is described in this writeup.

With this is place, it is feasible to set a minimum anonymity set size, preventing people from using keys with no anonymity set and compromising their own and others' anonymity. They can still do this compromise by revealing their secret key, but it's not clear to me that this is even possible to prevent.

Monero has addressed this issue in a similarly powerful manner, by implementing a scheme based on Greg Maxwell's Confidential Transactions. This novel scheme and implementation is called Ring Confidential Transactions. Because the value of outputs is no longer known under this RingCT scheme, you are no longer forced to only mix with a small subset of outputs (ie. those of the same denomination, which in CryptoNote and pre-RingCT Monero are all ^10 denominated outputs). This massively increases the potential anonymity set, and ensures that even large outputs are not "stuck" with only a handful of matching, mixable outputs.

And by the way, Dash (formerly Darkcoin) does not provide anonymity. They attached a (broken) implementation of CoinJoin to the ordinary Bitcoin client, and at least initially released it as a closed-source software. I haven't looked into Anoncoin, but the best advice I have for folks looking into altcoins is to assume they are uninteresting (and probably dangerously broken) until someone has demonstrated a concrete technical innovation.

Answer 2

First of, I am a Monero core developer. I'll try to remain as factual and objective as possible, though.

Now, for the simple answer: use Monero

And for the longer answer: read Andrew Poelstra's very informative reply.

I would also add the following:

• Zero-Knowledge Proof has several of fundamental issues that may not even be fixable (from the less critical to the most critical): trusted accumulator, lack of academic research, obscuring the whole economy means that it is impossible to notice a bug until the economy had already been badly damaged. See our comparison on Monero ANN.
• The CryptoNote technology is sound, but most actual implementation of it are not -- Boolberry and particularly Monero being the only ones worth considering, on the grounds of market confidence, activity and volume.
• Monero also works with the i2p initiative to obsfuscate IP (the only thing left visible once CryptoNote is in action).

Answer 3

first of all, you can continue using Bitcoin, simply use coin mixer websites to send your funds like Sharecoin and others. It’s really easy to use and it provides much more anonymity compared to default sending.

In the Altcoin world: I would recommend you to check out the CryptoNote protocol. It uses Ring Signatures to mix the outputs of transactions which makes it practically impossible to trace the funds. (I understand it’s your biggest concern)

As the example of CN implementation you should look into Bytecoin (BCN). It was started back in the 2012 and mined by approximately 2-3k people which were divided in teams.

Since it’s a crypto portal you probably know Adam Back, he mentioned CryptoNote as a new generation of alt coins.

Also, I feel obligated to mention few more anonymous coins to look into: Darkcoin, Anoncoin and their forks.

Answer 4

And by the way, Darkcoin does not provide anonymity. They attached a (broken) implementation of CoinJoin to the ordinary Bitcoin client, and at least initially released it as a closed-source software.

This is a total crock. Darkcoin's anonymity is the closest to actual implementation among all anonymity-centered alts. RC4 is in testing as we speak right now and will feature DarkSend+.

All coins will be automatically anonymized at interval, not just when they are being sent. This means the entire population of coins will be an anonymous mist.

In addition, the masternode system will be utilized to chain multiple DarkSend+ passes together in order to increase anonymity, so that even in the unlikely event multiple nodes are compromised the probability of compromising all of nodes in the sequence is nearly impossible.

I would also like to add that the code is currently being audited by Kristov Atlas, a well respected security expert, and that the only thing that is closed-source is DarkSend. Once the code has been vetted and refined, it will then be open-sourced.

I don't know where you get your information from, but it's obviously not very good or you didn't do your research as what you said is disingenuous and not true.