Zerocoin: Anonymous Distributed E-Cash from Bitcoin

[Peter Todd]

Here's a concrete example of how a more flexible Bitcoin scripting language would allow the creation of a system with properties between Zerocoin, and conventional chaum banking systems. Credit goes to Gregory Maxwell for the basic concept:

First you deposit your funds with the chaum bank, and receive a chuam token back.

The bank maintains a txout on the blockchain with funds >= all outstanding tokens, and with a scriptPubKey of the following form:

Code:

if scriptSig contains proof of a valid token
   and spending transaction contains a txout with the same restrictions:
        return True

Now I can provide proof to the blockchain itself that I am entitled to receive the value of my token back, and I can do so without the co-operation of the bank.

Totally off-chain transactions, IE chaum-for-chaum exchanges, can be handled as well by having the bank include all outstanding tokens in a merkle tree, and signing the tip of that tree along with an ever increasing serial number:

Code:

if signature of the tip of the tree is valid:
    let n = serial number in the signature
    let m = existing serial number
    if n > m
       and spending transaction contains a txout with similar conditions, but n as the serial number:
           return True
else if block height > y:
    if spending transaction contains the redemption code (first example):
        return True

Now I can "spend" the txout with ever increasing serial numbers. This allows multiple different users, each of whom may have a different idea of what the outstanding token set is, to converge to the last valid set of tokens. If they do so randomly that will happen in about log2(n) steps.

After the timeout the txout goes into the state of allowing people to get their funds back, and again, without the co-operation of the service any token can be turned back into Bitcoins. Of course, some of the tokens may be of too small a value to economically redeem, but in that case we're just back to the "pure-punishment" case.

I'm leaving out a lot of details of course, but in general what's nice is we get the anonymity of Zerocoin and off-chain microtransactions in one system. The trust in the central bank maintaining the ledgers is fairly minimal, and there can be as many of these banks as you want. The system can easily scale to extremely large transaction volumes without a corresponding increase of the blocksize. There may also be some clever way to remove the requirement for the bank and maintain the ledger via an alt-coin consensus system.

We could implement this with a soft-fork to Bitcoin that extends the scripting language with new opcodes and merklized abstract syntax tree support. My very rough guess is that it's a year long project to get the new scripting code written and tested, and maybe another year to deploy on mainnet.

[cheesylard]

Has this been completed?

[Serith]

What ticked me off is the quote from Wikipedia in the context of adam3us signature

It [Hashcash proof-of-work system] is also used as the proof-of-work protocol in Bitcoin

Yes I invented hashcash, no I am not Satoshi  

I realized that I was wrong after adam3us clarified:

Also while it is true that I invented hashcash (1997 hashcash.org), I am not claiming bitcoin is some simple extension, bitcoin has actually several key innovations that no one succeeded with before.  And not for lack of trying: there were a number of people on the cypherpunks list who were exceedingly interested in ecash, viewed it as the holy grail, and tried hard for many years (say 1995-2005 range) to figure out how to deploy ecash.

Only Satoshi can tell what kind of influence it was, do you have any quotes? If you compare technical details of those two systems then it's like computer vs abacus

You should actually read Satoshi's paper before getting involved in such arguments. Adam's work is cited directly:

To implement a distributed timestamp server on a peer-to-peer basis, we will need to use a proofof-work system similar to Adam Back's Hashcash [6], rather than newspaper or Usenet posts.

My question about a quote from Satoshi was actually a serious one, there is a lot of things I missed or don't know.

P.S. sorry for the off topic, won't post about it here any more.

[adam3us]

Here's a concrete example of [...] a system with properties between Zerocoin, and conventional chaum banking systems. First you deposit your funds with the chaum bank, and receive a chuam token back.

The limitation I see with Chaum credentials, for off-chain transactions backed by bitcoin is that the transaction server could issue more chaum-coins than there are bitcoins, and you will never know until you find your chaum-coin is irredeemable because the bank is out of bitcoins, having redeemed them itself under a pseudonym with extra unadvertised chaum-coins it minted for the purpose.  Because they are not linkable you cant make a chaum-coin lock an on-chain bitcoin nor collectively all issued chaum-coins also cant lock a claim to the pool of on-chain backing bitcoins.  (Or more likely the bank gets away with it for a while, like an over-leveraged fiat bank with off-book liabilities until there is a run on the bank).

(And I guess its been tried, monetas OpenTransactions system implements David Wagner's blind MAC (in the form of Ben Laurie's lucre library) something similar to Chaum and I think is flexible enough to issue Chaum-alike credentials for bitcoin).

Thats because while the Chaum bank can demonstrate it is holding some bitcoins, the coins are blind and not linkable.  So you cant tell when an extra coin is used (that was not backed by bitcoin) to claim a not yet spent bitcoin, rightly belonging collectively to the set of bitcoin backed chaum-coins.

You may even be able to ditch the central bank aspect and turn it into an alt-coin consensus system where the participants come to consensus about the state of the ledger without having to trust any one participant.

That could be interesting, but the chaum-blinding doesnt directly work as the way bitcoin consensus is to put it inside a merkle hash inside a massive hashcash stamp.  Maybe you could put it inside an RSA accumulator instead, which is a more blinding friendly algebraic construct.  However that is basically what ZeroCoin is trying to optimize.

Adam

[Peter Todd]

Here's a concrete example of [...] a system with properties between Zerocoin, and conventional chaum banking systems. First you deposit your funds with the chaum bank, and receive a chuam token back.

The limitation I see with Chaum credentials, for off-chain transactions backed by bitcoin is that the transaction server could issue more chaum-coins than there are bitcoins, and you will never know until you find your chaum-coin is irredeemable because the bank is out of bitcoins, having redeemed them itself under a pseudonym with extra unadvertised chaum-coins it minted for the purpose.  Because they are not linkable you cant make a chaum-coin lock an on-chain bitcoin nor collectively all issued chaum-coins also cant lock a claim to the pool of on-chain backing bitcoins.  (Or more likely the bank gets away with it for a while, like an over-leveraged fiat bank with off-book liabilities until there is a run on the bank).

Yup, that's one of the important details I left out for brevity.

The chaum bank can be required to maintain a signed audit log of every chaum token created and destroyed in the system; obviously value in - value out <= backing funds is a condition that must be always maintained and proven by the log. We'll call the audit log A with A=a₀...a_n and every entry in that log in signed by the chaum bank. In particular, part of the process of obtaining or redeeming a chaum token is that the bank gives you the entry in that log applicable to the transaction.

Now if you can prove a_i ∉ A, you've shown that the bank commited fraud by signing an audit log entry that it did not include in the master log. Also if you can prove a_i ∈ A and a_i±1 ∈ A, yet a_i and a_i±1 are inconsistent, you've also proven that the bank is attempting to commit fraud, perhaps by creating a token not backed by funds on the blockchain.

The bank now creates a txout with the following scriptPubKey:

Code:

if scriptSig proves audit log fraud:
    return True

This txout acts as a fidelity bond, and anyone who can prove the bank committed fraud gets to collect a reward, but only by proving to the whole world that the fraud happened. The whole world can then get their money back via the mechanisms I outlined above. Now you'll actually want to do something a bit more subtle to ensure that it is never in the banks incentive to commit fraud, then report themselves for fraud with a scriptPubKey of the following from:

Code:

if scriptSig proves audit log fraud:
    if spendingTx contains a txout with value n with scriptPubKey "anyone can spend after 100 blocks":
        return True

For a bond of value m, the finder of the fraud collects m - n - fees, and n Bitcoins are given away to a random miner. Just make sure that m - n - fees is sufficiently low that perverse incentives do not exist.

Of course publishing this audit log and verifying that it is valid has some overhead, potentially O(n^2) roughly speaking, but because we can have an arbitrary number of these banks we keep n small and the system is scalable even without using any sophisticated cryptography. By creating an incentive to find and publish fraud, we ensure the auditing infrastructure exists and is actually done, and because it is entirely math-based the auditing can be done completely automatically (and hence cheaply) by all parties involved. This infrastructure can be something like a P2P flood-fill network that keeps participants up to date on log information, or something as simple as a central service - there are lots of options to explore. I'm sure that the act of checking these audit logs will pose some edge-cases with privacy implications, but in any case the privacy achieved is strictly better than provided by on-chain transactions.


Incidentally everything I described above is applicable to my fidelity-bonded bank concept, with the key difference being that with support in the Bitcoin scripting language the result of fraud can be that the clients of the service get their money back rather than just the bank gets shut down.

[mmeijeri]

Here's a concrete example of how a more flexible Bitcoin scripting language would allow the creation of a system with properties between Zerocoin, and conventional chaum banking systems. Credit goes to Gregory Maxwell for the basic concept:

Is there a write-up of this somewhere? I need a lot more detail to understand what you are describing.

First you deposit your funds with the chaum bank, and receive a chuam token back.

blinded chaum token = random "serial number" generated by you, encrypted with secret key known only to you, then signed with private key corresponding to well-known public key by bank?

The bank maintains a txout on the blockchain with funds >= all outstanding tokens, and with a scriptPubKey of the following form:

Maintains a single txout rather than a Bitcoin address with the required amount in several transactions? Is this to sever any link between a specific txout and a redemption? How does the bank update this single txout when it issues a new token? I see nothing about this in your proposed script.

Code:

if scriptSig contains proof of a valid token
   and spending transaction contains a txout with the same restrictions:
        return True

proof =  random "serial number" generated by you, directly signed with private key corresponding to well-known public key by bank through the magic of a blind signature and not already redeemed in a previous transaction?

same restrictions = new txout contains more than is necessary to cover all remaining oustanding tokens (i.e. previous amount minus what was just validly withdrawn) and requires a new not-yet-redeemed token?

Totally off-chain transactions, IE chaum-for-chaum exchanges, can be handled as well by having the bank include all outstanding tokens in a merkle tree, and signing the tip of that tree along with an ever increasing serial number:

Code:

if signature of the tip of the tree is valid:
    let n = serial number in the signature
    let m = existing serial number
    if n > m
       and spending transaction contains a txout with similar conditions, but n as the serial number:
           return True
else if block height > y:
    if spending transaction contains the redemption code (first example):
        return True

tip =
similar conditions =

[adam3us]

The chaum bank can be required to maintain a signed audit log of every chaum token created and destroyed in the system; obviously value in - value out <= backing funds is a condition that must be always maintained and proven by the log.

Its a desirable audit requirement but I think the blinding may prevent it.  Lets call the blind chaum coins c' and the normal (unblinded) chaum coins c.

(And it works because blind proto-coin p is sent to the bank p=r^es mod N, bank signs to create blind coin c'=p^d=rs^d, and user unblinds by dividing by blinding factor r: c=c'/r=rs^d/r=s^d.  So the bank sees c'=rs^d on withdrawal and c=s^d on deposit.  s is the serial number.)

The bank on withdrawal exchanging bitcoins (call those coins b) for blind coins can log (c'₁,b₁).

On deposit exchanging chaum coins for bitcoins the bank sees c and b, so it can log (c₁,b_R) for some random bitcoin b_R.

Finally on chaum->chaum off-chain transaction the bank swaps a non blind coin for a fresh blind coin, so logs (c₁,c'₂).

The problem is if the bank logs two withdrawals (c'₁,b₁),(c'₂,b₂) and then logs deposit
(c_fake,b_R) the auditor cant correlate c_fake with either c'₁ nor c'₂ because of the blinding, even user 1 and user 2 who know their respective blind factors can't tell that it isnt the other user doing the deposit without breaking their privacy.  Unless they somehow all club together to do a ZKP to prove that a withdrawl is none of their coins which might be possible, somehow prove they know the blinding factors in one of the withdrawals that matches the deposit.  However that sounds a lot like zerocoin set membership level of efficiency proofs.  Maybe could still be interesting if it is off-chain.

Incidentally everything I described above is applicable to my fidelity-bonded bank concept, with the key difference being that with support in the Bitcoin scripting language the result of fraud can be that the clients of the service get their money back rather than just the bank gets shut down.

Is that described on the bitcoin wiki under fidelity bonds?

Adam

[Peter Todd]

The problem is if the bank logs two withdrawals (c'₁,b₁),(c'₂,b₂) and then logs deposit
(c_fake,b_R) the auditor cant correlate c_fake with either c'₁ nor c'₂ because of the blinding, even user 1 and user 2 who know their respective blind factors can't tell that it isnt the other user doing the deposit without breaking their privacy.  Unless they somehow all club together to do a ZKP to prove that a withdrawl is none of their coins which might be possible, somehow prove they know the blinding factors in one of the withdrawals that matches the deposit.  However that sounds a lot like zerocoin set membership level of efficiency proofs.  Maybe could still be interesting if it is off-chain.

Embarassing, I should actually read my old notes before posting... Yeah we saw that problem months ago and figured the only good solution was to accept that whatever funds are tied up as chaum tokens directly aren't auditable to the same level as non-blinded funds. However once someone spends a chaum token in exchange for non-blinded credit, you are back into solid auditing again, so it basically becomes a trade-off between anonymity set size and the window for fraud. Of course, that problem is applicable only to chaum tokens, so as a micro-transactions system without strict anonymity the idea still works very nicely and is probably about the most minimal level of trust possible, especially in that you can get your money back even if the service simply vanishes.

We hadn't heard about zerocoin at that point. I agree that the idea is far more feasible as an off-chain system; the trick would be to determine what constitutes fraud, how to prove it, and how to turn those proofs into something short enough that a reasonably short scriptPubKey could evaluate it. I guess essentially fraud would be allowing a chaum token set change that is invalid, but I don't know enough about the applicable math to comment there. If you can construct systems where proving fraud is reasonably efficient then the idea is feasible. (detecting fraud and using the system as a whole can still be inefficient)

Incidentally everything I described above is applicable to my fidelity-bonded bank concept, with the key difference being that with support in the Bitcoin scripting language the result of fraud can be that the clients of the service get their money back rather than just the bank gets shut down.

Is that described on the bitcoin wiki under fidelity bonds?

It's mentioned, but not really described. Basically though the idea is really similar to what I wrote above, except that without scripting support the only action that can be taken when fraud is published is to stop using the bank. The trick is that provided the fidelity bond is worth something, you can know that the bank is in a position where committing fraud would be a net loss for them. Part of that involves being able to sell those bonds and transfer them to other parties - IE solving the retirement problem.

[adam3us]

[auditability limits of off-chain chaumcoin server..]  Unless they somehow all club together to do a ZKP to prove that a withdrawl is none of their coins which might be possible, somehow prove they know the blinding factors in one of the withdrawals that matches the deposit.  However that sounds a lot like zerocoin set membership level of efficiency proofs.  Maybe could still be interesting if it is off-chain.

I wonder if there is a way to use zerocoin off-chain to implement the auditable chaum-like thing, presumably zerocoin is the closest protocol.  Zerocoins are so far not transferable - you buy them with bitcoins and sell them for bitcoins.  But you could transfer a zerocoin - just sign the new accumulation with the old coin and put the old coins serial number in the double spent list.

Recalling when you accumulate you have to spend a bitcoin (sign the accumulated coin c), and that authorizes you (in the view of all full bitcoin clients) to add c to the accumulator:

sig(b,c) and A' = A^c

signature using the bitcoin key b from bitcoin b.

when you convert it back to bitcoin:

ZKSoK[R]{(w,c,r): A==w^c mod N and c==g^sh^r mod p}

w is witness (accumulator excluding c), c is the coin, s is serial number, r is random never disclose, R is the data the signature is over.  R in the case of conversion to bitcoin is a bitcoin b, and the new owners bitcoin address.

If we want to transfer zerocoin to zerocoin without going via bitcoins we could do that too.

Just set R to c the new accumulated value of the new owner, and update the set of spent serial numbers with s which is disclosed as part of the ZKP.  Now you have a replacement freshly unlinkable zerocoin.

Now why would you want to convert a zerocoin to a bitcoin?  Its purely an efficiency argument - zerocoins are more work to validate and bigger.

You could directly mine zerocoins also.  Just allow mining to a zerocoin accumulation directly.  Ie the winning miner in each block is allowed to include 25 coins in the accumulator.  

So we could build a zerocoin alt-coin that doesnt directly use bitcoins at all with zc mining, and zc-zc transfer, and its own zc serial number double-spend validation in place of bitcoins linkable double-spend validation.  Maybe its merge-mined  (though that creates a strange conflict where miners get both 25 zercoins and 25 bitcoins for the mining price of 25 coins) or just track bitcoins difficulty, and bitcoin mine with intentionally unspendable mine-to addresses, that are valid  zerocoin addresses.  I think a "fair" merged mining aiming for price parity would be done by the miner having to choose zc or btc at mine time, and zc chain considering btc unspendable and bitcoin considering zc unspendable.

Maybe one could trade zerocoins for bitcoins.  Probably zerocoins would sell above par because they are taint free, in the same way that fresh mined coins reportedly have sold above par.

If bitcoin main choses not to integrate zerocoin - and indications so far is it wont for compute and storage efficiency reasons, and perhaps other reasons, then maybe this would be something interesting for a new altcoin.

I think people have proposed methods to trade altcoins for bitcoins without an exchange through some kind of simultaneous trade protocol?

edit: seems to be something wrong with this - dont miners on bitcoin networks have to be aware of validation logic of zerocoin alt-coin network, otherwise they will accept merge-mine of invalid eg forged zerocoins

edit2: maybe we can say that a mergemine does not count as a validation of the network for the respective network unless there is serialization in the coinbase indicating that the network is validated.  In that way you could have zerocoin mined and zerocoin validated, zero mined and bitcoin validated (strange but possible), zerocoin mined and both zero and bit coin validated, and also the same for bitcoin mined and zerocoin validated (strange but possible), bitcoin mined and bitcoin validated (normal bitcoin ignoring zerocoin) and bitcoin mined and bitcoin and zerocoin validated.  Then the validation events on zerocoin network might not be as frequent.  Maybe miners will tend to validate both networks as then they can claim fees on both networks, even if the protocol prevents direct merged mining on both networks (one or the other mined, and whatever chains validated as indicated by coinbase serialization).

Adam

[HostFat]

We'll be publicly releasing libzerocoin (alpha version) on July 4th. We're looking for testers & integrators!
https://twitter.com/ZerocoinProject/status/352136561397215232

[marcus_of_augustus]

We'll be publicly releasing libzerocoin (alpha version) on July 4th. We're looking for testers & integrators!
https://twitter.com/ZerocoinProject/status/352136561397215232

Who's we? ... good news btw.

[Binford 6100]

Who's we? ... good news btw.

I'm not their spokesperson but I guess it's the university researchers (prof & his students) working on their papers and this is the implementation. I wonder if they heard of testnet and bothered to add a flag to run on testnet before potentially destroying real coins

[runeks]

Who's we? ... good news btw.

I'm not their spokesperson but I guess it's the university researchers (prof & his students) working on their papers and this is the implementation. I wonder if they heard of testnet and bothered to add a flag to run on testnet before potentially destroying real coins

My guess is that this library isn't in any way made for Bitcoin, but is simply a group of functions that handle the cryptographic aspects of zerocoin. Ie. it abstracts away the underlying cryptography into functions that can be used by programs that wish to use this functionality. It would be someone else's job to integrate this into Bitcoin, if so desired (which, I gather, it is not). But that's just my guess. If this weren't the case, I think they would announce a fork of Bitcoin-Qt and not something called "libzerocoin". But we shall see.

[mmeijeri]

The whole system was designed as an extension of Bitcoin, and there was a proof of concept implementation when they published their paper a while ago.

[Rassah]

So, is the only thing that will decide whether this is used or not is whether miners will be willing to include the larger transactions?

[runeks]

So, is the only thing that will decide whether this is used or not is whether miners will be willing to include the larger transactions?

We need a hard fork for this to work. Coins are changing owner based on some added cryptography.

[jl2012]

So, is the only thing that will decide whether this is used or not is whether miners will be willing to include the larger transactions?

We need a hard fork for this to work. Coins are changing owner based on some added cryptography.

gmaxwell said it could be a soft fork: https://bitcointalk.org/index.php?topic=216982.0

I don't really understand the math behind zerocoin. However, if the "added cryptography" is more restrictive than current rules, that would be a soft fork

[runeks]

So, is the only thing that will decide whether this is used or not is whether miners will be willing to include the larger transactions?

We need a hard fork for this to work. Coins are changing owner based on some added cryptography.

gmaxwell said it could be a soft fork: https://bitcointalk.org/index.php?topic=216982.0

I don't really understand the math behind zerocoin. However, if the "added cryptography" is more restrictive than current rules, that would be a soft fork

I don't understand the math either.

But as far as I can see, if I transfer X BTC from address Y and convert them to a zerocoin, which I then transfer to address Z, then clients need to know how X BTC went from address Y to address Z, and that involves the zerocoin code.

But at the same time I value gmaxwell's opinion greatly. I would be interested in seeing an explanation from him on exactly how this can be achieved with a soft fork.

Can the Zerocoin stuff be done in Bitcoin script?

[Mike Hearn]

No, it cannot be done in script. See my answer on the other thread for the soft vs hard fork issue. The brief answer is that in a soft fork you arrange things such that to old nodes, all ZeroCoin transactions always appear to be valid. It means those nodes can accept blocks that are incorrect according to the ZeroCoin rules, and the assumption is that as long as most hash power is upgraded, miners will eventually orphan the invalid blocks and old nodes will re-org onto the right chain. However those nodes might believe the bogus transactions for some arbitrary amount of time.

ZeroCoin is not mergable into Bitcoin as is. But if it was, you're right, it should be a hard fork. There aren't any compelling reasons to use soft forks, IMHO. It is at best controversial.

[Peter Todd]

There aren't any compelling reasons to use soft forks, IMHO. It is at best controversial.

Lol.

For the newbies reading this, basically Mike is saying there isn't any compelling reason for backwards compatibility, and every change should require that every single Bitcoin node upgrade all at once even when doing so in a backwards compatible way is trivial. Needless to say, it's not an opinion shared by many... For reference, here's Gavin's "Bitcoin Rule Update Process" guidelines: https://gist.github.com/gavinandresen/2355445 which were quite successfully used to implement BIP 34