Zerocoin: making Bitcoin anonymous

When I started this post, the value of a single bitcoin had surged upwards of $250. It’s corrected a bit since then (down $100 or so), but it’s pretty clear that we live in a very different world than we did two weeks ago.

And I’m not sure I really like this world. It’s a world where I have to listen to CNBC reporters try to understand Bitcoin. Ouch. I think we can all agree that we were better off before this happened.

The explosion of interest in Bitcoin is both wonderful and terrible. It’s wonderful because Bitcoin is an amazing technical innovation — the first decentralized electronic currency to actually make something of itself. It’s terrible because Bitcoin has some technical rough edges that really need to be filed off before we start using it for anything.

The rough edge that particularly interests me is user privacy. Or rather, Bitcoin’s troubling lack of it.

In this post I’m going to describe a new piece of research out of my lab at Johns Hopkins that provides one potential solution to this problem. This is joint work led by my hardworking students Ian Miers and Christina Garman, along with my colleague Avi Rubin. Our proposal is called Zerocoin, and we’ll be presenting it at this year’s IEEE S&P.

For those who just want the TL;DR, here it is:

Zerocoin is a new cryptographic extension to Bitcoin that (if adopted) would bring true cryptographic anonymity to Bitcoin. It works at the protocol level and doesn’t require new trusted parties or services. With some engineering, it might (someday) turn Bitcoin into a completely untraceable, anonymous electronic currency.

In the rest of the post I’m going to explain Zerocoin, what it can do for Bitcoin, and how far away that ‘someday‘ might be. This is going to be a long, wonky post, so I won’t be offended if you stop here and take my word that it’s all true.

For everyone else, strap in. I need to start with some background.

Bitcoin in 300 words

Before I get to Zerocoin I need to give the world’s shortest explanation of how Bitcoin works. (See here for a slightly less terrible explanation.)

At its heart, Bitcoin is a transaction network with a distributed public ledger. Transactions are files that contains messages like “User X transfers 3 bitcoins to user Y” and “User Y transfers 2.5 of those bitcoins to user Z”. Users aren’t identified by name. Instead, their identities are public keys for a digital signature scheme.* This allows users to sign their transactions, and makes it very difficult to forge them.

Now none of this stuff is really new. What makes Bitcoin special is the way it maintains the transaction ledger. Rather than storing the whole thing on a single computer, the ledger — called a block chain — is massively replicated and updated by a swarm of mutually distrustful parties running in a peer-to-peer network.

To make this work, nodes pull transactions off of a peer-to-peer broadcast network, then compete for the opportunity to tack them on the end of the chain. To keep one party from dominating this process (and posting bad transations), competition is enforced by making the parties solve hard mathematical problems called ‘proofs of work‘. The integrity of the block chain is enforced using hash chaining, which makes it very difficult to change history.

Now the block chain is fascinating, and if you’re interested in the gory details you should by all means see here. This post mostly isn’t going to get into it. For now all you need to know is that the block chain works like a global ledger. It’s easy to add (valid) transactions at the end, but it’s astonishingly difficult to tamper with the transactions that are already there.

So what’s the problem?

The block chain is Bitcoin’s greatest strength. Unfortunately from a privacy perspective, it’s also the currency’s greatest weakness.

This is because the block chain contains a record of every single Bitcoin transaction that’s ever been conducted. Due to the way Bitcoin works, this information can’t be limited to just a few trustworthy parties, since there are no trusted parties. This means all of your transactions are conducted in public.

Illustration of a Bitcoin block chain. Each transaction is tied to the one that precedes it.
The transaction at far left is almost certainly a drug deal.

In a sense this makes Bitcoin less private than cash, and even worse than credit cards. If you choose to engage in sensitive transactions on Bitcoin, you should be aware that a record will be preserved for all eternity. Spend with care.

Now some will say this is unfair, since Bitcoin users are not identified by name — the only identifier associated with your transactions is your public key. Moreover, you can make as many public keys as you’d like. In other words, Bitcoin offers privacy through pseudonymity, which some argue is almost as good as the real thing.

But don’t get too comfortable. Already several academic works have succeeded in de-anonymizing Bitcoin transactions. And this work is just getting started. You see, there’s an entire subfield of computer science that can roughly be described as ‘pulling information out of things that look exactly like the Bitcoin transaction graph’, and while these researchers haven’t done much to Bitcoin yet — that’s only because they’re still fighting over the grant money. We will see more.

If you’re a Bitcoin user who values your privacy, this should worry you. The worst part is that right now your options are somewhat limited. Roughly speaking, they are:

Just be careful. Generate lots of public keys and make sure your client software is extremely careful not to use them in ways that could tie one to another (e.g., getting ‘change’ from one key sent to another). This seems to be the major privacy thrust of the current Bitcoin development effort, and we’re all waiting to see how it pans out.

Use a laundry. For the more paranoid, there are services called ‘laundries that take in bitcoins from a whole bunch of users, mix them up and shuffle them back out. In theory this makes it hard to track your money. Unfortunately, laundries suffer from a few problems. First, they only work well if lots of people are using them, and today’s laundries have relatively low volume. More importantly, you’re entirely dependent on the honesty and goodwill of the laundry itself. A dishonest (or hacked) laundry can steal your coins, or even trace its inputs and outputs — which could completely undermine your privacy.

Use a Chaumian e-cash system. On the wonkier side, there have been attempts to implement real anonymous cryptographic e-Cash for Bitcoin. I’ve written about these systems before and while I think they’re neat, the existing schemes (from Chaum on forward) have one critical flaw: they all rely on a central ‘bank’ to issue and redeem e-Cash tokens. The need for this bank has been a major stumbling block in getting these systems up and running, and it’s almost unworkable for Bitcoin — since trusted parties are antithetical to Bitcoin’s decentralized nature.

In short, the current solutions aren’t perfect. It would be awfully nice if we had something better. Something with the power of cryptographic e-Cash, but without the need to change Bitcoin’s network model. And this is where Zerocoin comes in.

Zerocoin

Zerocoin is not intended as a replacement for Bitcoin. It’s actually a separate anonymous currency that’s designed to live side-by-side with Bitcoin on the same block chain. Zerocoins are fully exchangeable on a one-to-one basis with bitcoins, which means (in principle) you can use them with existing merchants.

Zerocoins themselves can be thought of literally as coins. They’re issued in a fixed denomination (for example, 1 BTC), and any user can purchase a zerocoin in exchange for the correct quantity of bitcoin. This purchase is done by placing a special new ‘Zerocoin Mint’ transaction onto the block chain.

Once a Mint transaction has been accepted by the Bitcoin peers, the same user can later redeem her zerocoin back into bitcoins. She simply embeds a (preferably new) destination Bitcoin address into a ‘Zerocoin Spend’ transaction, then sends it into the network. If the transaction checks out, the Bitcoin peers will treat it just like a normal Bitcoin transfer — meaning that she’ll receive the full bitcoin value of the coin (minus transaction fees) at the destination address.

Now you’re probably wondering what any of this has to do with privacy. To explain that, I need to give you one more piece of information:

Aside from educated guesswork, there’s no way to link a Zerocoin Mint transaction to the Zerocoin Spend transaction that redeems it.

Redeeming a zerocoin gives you a completely different set of bitcoins than the ones you used to purchase it. In fact, you can think of Zerocoin like the world’s biggest laundry — one that can handle millions of users, has no trusted party, and can’t be compromised. Once as user converts her bitcoins into zerocoins, it’s very hard to determine where she took them back out. Their funds are mixed up with all of the other users who also created zerocoins. And that’s a pretty powerful guarantee.

Illustration of a Bitcoin/Zerocoin block chain. A user transforms bitcoins into a zerocoin,
then (at some unspecified later point) ‘Spends’ it to redeem the bitcoins. The linkage between Mint
and Spend (dotted line) cannot be determined from the block chain data.

The key to the whole process is to make it all work at the protocol level — meaning, without adding new trusted parties. And doing that is the goal of Zerocoin.

How does it work?

Zerocoin uses a combination of digital commitments, one-way accumulators and zero-knowledge proofs, and some extensions to the existing Bitcoin protocol. It also shares some similarities to a previous work by Sander and Ta-Shma. For the details, you can see our paper. Here I’m going to try to give a very high-level intuition that avoids the muck.

The key idea in Zerocoin is that each coin commits to (read: encrypts) a random serial number. These coins are easy to create — all you need to do is pick the serial number and run a fast commitment algorithm to wrap this up in a coin. The commitment works like encryption, in that the resulting coin completely hides the serial number . At the same time this coin ‘binds’ you to the number you’ve chosen. The serial number is secret, and it stays with you.

To ‘Mint’ the new coin you post it to the network along with a standard Bitcoin transaction containing enough (normal) bitcoins to ‘pay for’ it. The Mint transaction adds some new messages to the Bitcoin protocol, but fundamentally there’s no magic here. The Bitcoin network will accept the transaction into the block chain as long as the input bitcoins check out.**

The Zerocoin ‘Spend’ transaction is a little bit more complicated. To redeem your zerocoin, you first create a new transaction that contains the coin’s serial number (remember that you kept it secret after you made the coin). You also attach a zero-knowledge proof of the following two statements:

  1. You previously posted a valid zerocoin on the block chain.
  2. This particular zerocoin contained the serial number you put in your transaction.
The key to making this all work is that zero-knowledge proof. What you need to know about these is that anyone can verify such a proof, and she’ll be absolutely convinced that you’re telling the truth about these statements. At the same time, the proof reveals absolutely no other information (hence the ‘zero’ knowledge).
This means anyone who sees your Spend transaction will be convinced that you really did previously Mint a zerocoin, and that it contained the serial number you just revealed. They can then check the block chain to make sure that particular serial number has never been Spent before. At the same time, the zero knowledge property ensures that they they have absolutely no idea which zerocoin you’re actually spending. The number of such coins could easily run into the millions.
All of this leads us to one final question: where do your bitcoins go after you Mint a zerocoin, and how do you get them back when you Spend?
The simple answer is that they don’t go anywhere at all. The bitcoins used in a ‘Mint’ transaction just sit there on the block chain. The Zerocoin protocol semantics require that nobody can access those coins again except by publishing a valid Zerocoin ‘Spend’. When you publish a Spend, the protocol allows you to ‘claim’ any of the previously-committed bitcoins — regardless of who posted them. In other words, you Mint with one set of bitcoins, and you leave with someone else’s.

When will Zerocoin be available?

For those looking to use Zerocoin tomorrow, I would advise patience. We’ve written a proof-of-concept implementation that extends the C++ bitcoind client to support Zerocoin, and we’ll be releasing a cleaned up version of our code when we present the paper in May. (Update: available here.)

But before you get excited, I need to point out some pretty serious caveats.

First of all, Zerocoin is not cheap. Our current zero-knowledge proof averages around 40KB, and take nearly two seconds to verify. By the standards of advanced crypto primitives this is fantastic. At the same time, it poses some pretty serious engineering challenges — not least of which is: where do you store all these proofs?

This probably isn’t the end of the world. For one thing, it seems likely that we’ll be able to reduce the size and cost of verifying the proof, and we think that even the current proof could be made to work with some careful engineering. Still, Zerocoin as currently construed is probably not going to go online anytime soon. But some version of Zerocoin might be ready in the near future.

Another problem with Zerocoin is the difficulty of incrementally deploying it. Supporting the new Mint and Spend functionality requires changes to every Bitcoin client. That’s a big deal, and it’s unlikely that the Bitcoin folks are going to accept a unilateral protocol change without some serious pushback. But even this isn’t a dealbreaker: it should be possible to start Zerocoin off using some training wheels — using a trusted central party to assist with the process, until enough Bitcoin clients trust it and are willing to support it natively.

In fact, one of the biggest barriers to adoption is human beings themselves. As complicated as Bitcoin is, you can explain the crypto even to non-experts. This makes people happy. Unfortunately Zerocoin is a different animal. It will take time to convince people that these new techniques are safe. We hope to be there when it happens.

In conclusion

I realize that this blog post has run slightly longer than usual. Thanks for sticking with me!

As regular readers of this blog know, I have a passion for anything that gets interesting crypto out into the world. Bitcoin is a great example of this. It would be wonderful if this gave us an opportunity to do even more interesting things. Perfectly untraceable e-Cash would definitely fit that bill.

But even if we don’t get there, the fact that reputable computer science conferences are accepting papers about ‘that crazy Bitcoin thing’ tells you a lot about how much it’s grown up. In the long run, this is good news for everyone.

Notes:

* There are a lot of simplifications in here. Identities are the hash of your public key. The block chain is really computed using a Merkle tree for efficiency reasons. The peer-to-peer network isn’t quite a broadcast network. Did I mention you should read the paper?

** Note that for those who ‘know’ their Bitcoin, you can think of the Zerocoin as a piece of extra data that gets added to a Bitcoin transaction. The inputs are still standard bitcoins. There’s just no output. Instead, the transaction contains the coin data.

71 thoughts on “Zerocoin: making Bitcoin anonymous

  1. When you say 40kb do you mean kilobit, or kilobyte? Usually lower case b is used for bit, but in this context bytes would be more common.

  2. Are there measures to avoid correlations between the amounts minted and spent? (ie. 2.13btc -> zc mint -> zc spend -> 2.13btc)

  3. @Arlo: Presumably this is why “they're issued in a fixed denomination”. So they're all the same (or there are a small number of denominations, say powers of 2 or 10, and within a denomination they're all the same.)

  4. if i get the idea right, you can't do transactions with zerocoin, you can only disconnect them from your address, and reconnect someone else's to your new secret address. it's like thousands of bitcoins get locked and unlocked, and nobody knows by whom.

    using Zerocoins means making money disappear from the ledger for an indefinite time – you can't trade with disappeared money. there's suddenly no money, thats why we call the mechanism _Zero_coins.

  5. Right now the idea is that all Zerocoins have the same denomination (1 BTC in the example I gave). This means there's no way to correlate Bitcoin value from Mint to Spend, because all transactions have the same value. (Of course, if I see you Mint a certain number of zerocoins, then spend them all at the same time… that would be a giveaway.) It's possible to create zerocoins with variable denominations, but there are privacy risks as you point out.

  6. “They can then check the block chain to make sure that particular serial number has never been Spent before.”

    Does this solution rely on scanning the entire block chain to prevent a double spend? Have you considered how much load this would introduce if deployed widely?

  7. This design would work on a Bitcoin clone just as well. Why not deploy it on one of the smaller cryptocurrencies (Litecoin or Bitcoin testnet) or create a new one for the purpose? You'd get to demonstrate whether it works without risk to Bitcoin.

  8. You mint zero coins in fixed denominations. So everyone agrees that we have a 1btc zerocoin, a .25btc zerocoin, etc.

    The exact denominations don't matter so much and will most definitely include fractional sizes. The important thing is that everyone agrees which sizes are valid.

  9. >>Our protocol assumes a trusted setup process for generating
    >>the parameters… accumulator trapdoor (p; q) can be destroyed >>immediately after the parameters are generated.

    This is a serious flaw. All past transactions can be revealed with knowledge of (p,q). How can i trust the developers to destroy the (p,q)?

    >>Alternatively, implementers can use the technique of
    >>Sander for generating so-called RSA UFOs
    >>for accumulator parameters without a trapdoor [26].

    I looked the paper and noticed: 1) this is probabilistic algo; 2) it can be performed by a single person — and again we need to trust. How exactly can it be implemented in p2p network like bitcoin?

    Moreover: if trapdoor (p,q) will eventually recovered by some factorization method all past transaction will be revealed and new setup procedure will be required.

  10. I registered the domain zeroco.in last week… It's a total coincidence, sorry. Was planning to develop a lightweight bitcoin client. Oh well, back to finding a name for my project.

  11. Which sub-field of computer science can be described as “pulling information out of things that look exactly like the Bitcoin transaction graph”?

  12. Maybe you said it, do the 40 kB relate to the mint or the spend, and if it is on the spend side, do the 40 kB really need to be stored in the block chain (or can it purge after a safe number of blocks) ?

  13. Accumulators are just bookkeeping devices, made to publicly reproduce the “gather all zerocoins from the blockchain” step. In this paper (p,q) are the factors related to the *accumulator*, and they have no shared-secret relationship with any of the minted zerocoins.

    > All past transactions can be revealed with knowledge of (p,q).

    All past *mints* can be revealed this way, but that's exactly what's publicly published in the blockchain anyway. The accumulator does not have access to the per-coin trapdoor skc necessary to spend an arbitrary zerocoin.

    > How can i trust the developers to destroy the (p,q)?

    If the ledger is accurate, then it doesn't matter. The accumulator is a once-in-a-while bookkeeping exercise made to turn O(N) into amortized O(1) when spending zerocoins.

    The potential problems with accumulators come in from dishonest accumulators:

    1) An accumulator could intentionally leave out a previously-published zerocoin, making it effectively disappear from valid-to-spend coins, or
    2) An accumulator could forge a false zerocoin, adding one to the accumulator that has not been published in the blockchain.

    Fortunately, these don't appear to be fatal flaws, since the action of the accumulator can be verified. The only *used* parameters are u and N, and both of those are published.

  14. I'm a little confused about the scalability of the spending side. The paper says that spending must:

    1) Compute A <- Accumulate ( (N; u); C) and
    2) Compute w <- GenWitness (N; u); c; C) where GenWitness is pretty much “the accumulator of every zerocoin except the one I'm spending”. Doesn't this make the spender perform a lot of computational work, especially for an “old” zerocoin? The accumulator itself can be updated incrementally and publicly, but the witness must be updated by the spender. This means that the spender Alice must have access to the full set of zerocoin transactions, or at least:
    1) The accumulator checkpoint at the time of minting Alice's zerocoin
    2) The public (c) for every other zerocoin minted in the same block as Alice
    3) The full set of mints published *after* Alice's coin.

    Even though accumulators can be updated incrementally, the updates for the full accumulator A and an arbitrary witness (w) will be different, so the accumulator-checkpointers can't precompute anything of use for public use.

    If zerocoins become a high-volume item, this means that “old” coins become computationally harder to spend. For an attacker able to inject a high volume (but otherwise fully legitimate) set of zerocoin transactions into the blockchain at arbitrary intervals, this could lead to a couple attacks against zerocoin users:

    a) By injecting too many zerocoins, it might be possible to make it not-worth-it to “spend” early-minted zerocoins, or
    b) For a zerocoin-spender under surveillance, where an attacker can determine the moment at which the zerocoin-spend computation started and when it finished (by posting the transaction publicly), this timing interval could reveal hidden information about the coin being spent – namely roughly how many mints ago it was formed.

  15. > spend side, do the 40 kB really need to be stored in the block chain (or can it purge after a safe number of blocks) ?

    The block chain is immutable, so there's no way to purge information from it after the fact.

    The 40kB seems to constitute the zero-knowledge proof, which says “I'm not telling you how I know this but I know that one of the minted zerocoins has serial number C and here's how you can check that.” It must be published in the first place in order for the transaction to be verified.

  16. (Amending my previous post here)

    After further reading, you're not entirely off the mark. It looks like if (p,q) is known after the generation of N, then it would be possible for an attacker to forge a (v,w) pair that “proves” the existence of a zerocoin (v) that isn't really in the accumulator A. This would then allow for forged spends, since it would be further possible to make a validly-checking spend proof based on a coin that doesn't exist.

    While this would break zerocoin, I still am not convinced that it de-anonymizes previous spends. I think you have to beat the zero-knowledge proof to do that.

  17. Okay, each bitcoin is worth a fair amount. But, bitcoin is easily divisible to 8 places. For zerocoin, it can't be divisible. So, we need to fix it to a lower number. Also, it is bad to have multiple zerocoin chains. This gives you less security as a whole for each one (more usage more anonymity). For Zerocoin, it can't be too small also. Transactions will still cost transaction fees. So, the denomination can't be too small. Also, lots of work, time, and space is needed to verify transactions. This will not be a microtx currency and it can't be too small. We could also say that it costs +0.0005 for each zerocoin you mint. This will be for when you spend the zerocoin.

  18. They don't disappear from the ledger. Zerocoins are random claims on bitcoins that breaks the transaction chain, thereby making them untraceable.
    The amount of bitcoins claimed is equivalent to the amount “locked” by the user.

  19. Now I'm no BitCoin expert (hell, I've hardly looked into it at all until this blog post, and I still have hardly any idea about how it all works in detail), BUT I'm pretty sure that the name comes from the fact that it revolves around the concept of a *zero*-knowledge proof.

  20. That's not a great idea either. Size/processing tradeoffs are not necessarily an improvement. That sort of trade is beneficial *when it takes load off of a bottleneck*. In a situation like this, some people will have processing bottlenecks, some people will have networking bottlenecks. There isn't really a correct tradeoff here.

  21. It doesn't help your cause when one of the zerocoin developers goes on record as saying that a backdoor could be added to assist governments in tracking where coins are sent.

  22. Knowing the factorization of N does allow you to spend every minted zerocoin (you could spend even more, but you'd exhaust the pool of escrowed bitcoins). There are techniques for creating accumulators that don't let anyone actually know N. They are called RSA UFO's and are mentioned in the paper. See[0]

    Even if the factorization of N is known, the zero knowledge proof output by Spend(…) is still a zero knowledge proof that only reveals the serial number. You are still anonymous.

    [0] T. Sander, “Efficient accumulators without trapdoor extended
    abstract,” in Information and Communication Security, vol.
    1726 of LNCS, 1999, pp. 252–262.

  23. Why do you need to use the complex double exponentiation in your ZKP? I thought maybe you wanted to show some structure in S, but it's just a random value. Pedersen commitments can be proven very simply, without cut and choose. Thanks!

  24. The witness can be updated incrementally, as long as the zerocoin user sees all the transactions. He would have to keep a running update of each of all of his outstanding zerocoin transaction's witnesses. This would require one exponentiation for each outstanding zerocoin transaction, whenever a new zerocoin transaction came in. As long as he is running a full node, in Bitcoin parlence, he sees every transaction.

  25. sure, but a backdoor could also be added to the bitcoin clients in the same manner – that's why we use open source software – everyone can read it and that is assurance that it is working as desired

  26. Are we sure additional privacy is desirable? It makes it easier to commit crimes using bitcoin… think child porn, human trafficking, contract killing, terrorism, illegal arms sales.

    BTW, good to see you Hal!

  27. There are crypto schemes by which a P2P network can generate an RSA modulus such that they all would have to collude to know the factorization. If there is at least one honest participant, the secret is safe.They aren't especially efficient, but it would only have to be run once. Of course, future generations would have to trust that their ancestors were honest.

    As far as the Sander paper, trust can be minimized by seeding a random number generator from a public headline. The real problem with this approach is that it generates ridiculously large RSA moduli. One example they give in their paper is 40,000 bits!

  28. Co-author here. We could do a simple proof for the spend if we could safely reveal the raw coin( which is just a Pedersen commitment). But since that's the same coin we minted, doing so would make spend trivially linkable to the mint.

    Instead, we prove that a commitment to a coin was accumulated. Then we have to prove we know the serial number of the committed coin. This requires the double discrete exponentiation ZPK. Believe me, we wish it didn't. We have some ideas for more efficient techniques, but as of right now its the best we got.

  29. This may be a better explanation, or a misunderstanding:

    zerocoin can be thought informally as some automated wallet.

    When you make a zerocoin, there is a trace of what btc went into it. When you spend a zerocoin, we only know that such a zerocoin existed, and that it hasn't been spent before, and so we don't know which zerocoin was just spent, even if there is a trace of the btc that come out of the spending transaction.

    Is all that right?

    If it works that way, this is pretty good. Its nice to know that btc came from zerocoin because it gives you deniability if the source is persecutable, and then implicates you for aiding and abedding that source.

    Can you transfer a zerocoin… that is can you verify that an unspent zerocoin exists without spending it?

  30. Thanks for your work on this!

    It would be interesting to see how the blockchain would deal with such an increase in size. But the concept of true anonymity is very worthwhile and would add a lot of value to bitcoin by removing the need to trust individuals who run mixers. An 'honest', open source protocol like you're proposing that does this would be great!

  31. How does this protect from checking the zerocoin withdrawals against the entire zerocoin spend history to see when it becomes valid? If zerocoin spends can't be withdrawn if the blockchain is reversed back to a previous point, before the zerocoin was spent, then doesn't that mean you can link the withdrawal to the spend?

    Am I missing something important here? (Haven't read the PDF yet, but I will soon. If it's discussed there, then I'm mostly wondering why this haven't been mentioned already here as well.)

  32. After a second look, it seems like the published zero-knowledge proof specifically refers to a group of zerocoins, and only can be verified against that group as specified.

  33. I actually really enjoyed this read and learnt a lot.

    There's some points that aren't covered, but as for the technical information I think this may be some of the most accurate information I've read.

    I may use some of your information on my own blog, http://www.mybitcoins.info , I'll of course ask in advance and reference when and if needed.

  34. Nice article, this looks like some pretty clever work, but I'd love to know more about how the zero-proofs are performed. The trick of it I'm missing is that she can't reveal which coin she's identifying, or the anonymity breaks down as Ian Miers posted. Something about a “double discrete exponentiation ZPK”

    1) I create a mint transaction with my “commit” value. The commit value has to be published with my transaction so that there will be a unique coin only I can spend. Since we assume the network is mistrusted, the transaction and the commit value two are tied together forever.
    2) Time passes. Other people make coins.
    3) I'm ready to spend my coin, so I create my spend transaction with my SN. I assume a portion of my commit algorithm must be kept secret (the encryption key) otherwise, anyone could generate my “commit” vale and tie my “mint” & “Spend” transactions together.
    4) The network will want to see that I minted a coin previously (but not which one) and that my SN represnts one of the minted coins. (i.e. the two zero knowledge proofs.) Some magic happens here where I proove I have the key without giving away my commit value or encryption key. If I give either one away, I can be identified.
    5) The network can't know which coin I'm spending, they'll need a way to make sure I don't double spend. The SN will be recorded for all time in the Spend transaction block chain. Assuming that no encryption/SN pair can be brute forced to look like a proof of a valid commit, then the SN can only exist once in the transaction log making a double spend impossible.

    So in the end, the network will never know which coin I was spending. They'll always know how many are still valid, but not which ones to remove from the valid group to simplify future validations.

    Am I right so far?

  35. It might be better to build an scrypt based altcoin based on the premise of total anonymity, rather than attempting to get people to accept a modified version of one they're already running.

    I think that you would be more successful this way.

  36. some?'s

    1.
    “Zerocoins are random claims on bitcoins that breaks the transaction chain”

    Bitcoin transaction chain – protect value and it becames value. where zerocoin value?
    transaction key history is not the same as users owning history.
    why change bitcoin? better change environment: tor- trade communications+pass <> virtual world- bitcoin <> real world- gift/virtual world encrypted file+pass from tor.
    (You can have different addresses in order to receive payments.) it is enough options to be anonymous i think. Just need more bitcoin popularity its like paper cache you cant get/ask for it if your friends don't have it or you dont have work for bitcoins.

    2.
    “The amount of bitcoins claimed is equivalent to the amount “locked” by the user.”

    so you spend someones others money without his agreement? how it can be secure? if what- all currency on system trust in risk.

    3. bitcoin – no tax currency:), zerocoin you want tax for every transfer? 😦

    bitcoin is like tor, safe inside network, but unsafe on exit nodes(exchangers) 🙂 but that strategy works for tor many years!

  37. Why does this have to be incorparated into all bitcoin clients? Why can't it be an addon? Just create your own ledger which only refers to certain hashes in the bitcoin chain…

  38. Hello!
    I'm a bit confused as to what parts of the system would cause bloat.

    There are, basically:
    1) accumulator itself, which can be incrementally updated
    2) ZC “mint” transactions
    3) proofs aka spends.

    My question is thus – does the accumulator proper (1) increase in size during updates ?

  39. Actually I was going to say everyone could indeed only use Zerocoins, but now I've realised that's probably not true. Surely if your claim to any specific Zerocoin is your knowledge of a serial number, then it would be impossible to safely sell a Zerocoin, since the buying party couldn't force you to forget the serial number.
    I was going to say there would be practical, technical performance reasons to only use Zerocoins when anonymity was required.
    And Squeakneb is surely right!

  40. Hey hey, I think you made a mistake on your paper, you say

    one bitcoin = 10^9 Satoshi

    BTW I really hope this takes off

  41. Bitcoin is also still up for manipulation like a junior penny stock. People that attack exchanges can sell their holdings only to buy them up with their attack is finished.

  42. A lot of people here are living in fantasy land. If zerocoin and/or bitcoin gains significant traction, do you really think governments and established the financial players will just let it slide? No, it will be crushed by the players or regulated out of existence by gov'ts.

  43. It's a problem, for sure.

    The thing is, right now Bitcoin isn't private *at all*. Anyone with enough computing power to do any serious amount of data mining can essentially read your bank statements. If everyone used Bitcoin, a “background check” company could dig through the blockchain and discover that you bought some perfectly legal (but embarrassing) steamy videos a few years ago. Or, on a less personal level, there's plenty of humanitarian operations that can't operate publicly in this or that dictatorship – Bitcoin can no longer be used to support them because if they ever spend it their government will be able to figure out who was doing the spending. This isn't sci-fi; the tech exists to do it already.

    If you're okay with these consequences, then Zerocoin-style anonymity is obviously not desirable. If you're not okay with them, though… well, then either the trust-free blockchain is an unsuitable dream and the sooner we stop bothering with it the better, or the trust-free blockchain needs to have some ability to anonymize (which, like any tool, will then be available to both the just and the unjust).

    It's a thorny question.

  44. Without the logic living in the Bitcoin ledger, the transfer of bitcoins from the 0c minting address to the 0c redeeming address cannot take place. As far as I know, there's no known mechanism by which the values on Blockchain A can control the balances on another unrelated Blockchain B without B's cooperation.

  45. Hey man, was just browsing through the internet looking for some information and came across your Cryptographic Engineering blog. I am impressed by the information that you have on this blog. It shows how well you understand this subject.Bookmarked this page, will come back for more click here bitcoin classifieds

  46. What worries me is the fixed denomination of Zerocoin. Right now a transaction that redeems 1 bitcoin doesn't look suspicious, but in the near future bitcoin price will go up and the average amount of spent bitcoins in each transaction will most likely go down, making Zerocoin Spent transaction look suspicious. Therefore it would be nice to write an algorithm that would tie a denomination of Zerocoin with the average amount of spent bitcoins in each transaction.

  47. Many people including myself are just starting to hear about Bitcoins even though they have been around since 2008-2009. They are a very new “currency” and will allow you to profit without ANY fees of transfer, any freezing of funds, doesn't require banks and is currently feared by established financial institutions to the way of trying to ban it. The funny thing is that is it`s impossible to ban or prohibit because no one owns it!

    There are a group of clever developers are working on a tool that will allow people to make bitcoins every single day! There is a nice short to the point video that explains the “Human Greed” factor and why this is an entirely new and unexplored market!

    This is unlike anything you have ever seen or heard off and it makes perfect sense that early birds knowing this info will make alot of money off the backs of people that come into a new moneymaking market too late. The beauty of this is that you stay anonymous and in nowadays world flying under the radar is important. The recent scandals of governments spying on its citizens are making “transparency” a scary thing so don`t let anyone meddle in your private affairs!

    There is a free presentation seat to be grabbed so you can be the first to learn more about this bitcoin robot that is due to be released very soon to a small circle of people that follow its development.

    Check it out now: http://ezhomefunds.com/btcsm

Comments are closed.