Zerocoin: Anonymous Distributed E-Cash from Bitcoin

[mmeijeri]

Hmm, on reflection, obscuring couldn't work, because you do need to know which inputs are now spent. Netting of successive transactions might still work.

[1713577479]

1713577479

[mmeijeri]

Hmm, on further reflection the SIGHASH_SINGLE + SIGHASH_ANYONECANPAY idea might not work either. It seems to me that either SIGHASH_SINGLE is somehow linked to a specific output, in which case it doesn't help anonymise transactions, or it is unsafe, which isn't helpful either. I guess I'll have to read up some more to see if anything can be salvaged from my suggestions.

[adam3us]

Greg Maxwell also and others proposed taint mixing using multiple coin inputs.

I believe that the idea is that instead of how blocks are created now for the blockchain, the network nodes will create "mixed" blocks in 3 rounds of communication, instead of 1 round.

Greg also said something like that:

https://bitcointalk.org/index.php?topic=139581.0

but as a multi-user/multi-input transaction to complicate simplistic tracing taint back to a the owner on the assumption that all inputs from spends are from the different addresses of the same sender.  So in that case there is no unsigned input statement, just a multisig with multiple inputs (from a variety of people) and multiple outputs, so there's not really any doubt about who put money into the mix or who took money out (presuming each person takes out what they put in), just that any tracing identities has to account for this existing mixed owner inputs possibility.

You could view the version when all the transactions in a block are mixed as something like zerocoin except with a fresh anonymity-set for every block.  And the output goes directly to the recipient which I guess could be done with zerocoin also (put recipients address rather than your own on cashing out of the pool).

[description of 3-round: 1 users broadcast unsigned intended recipients and amounts, 2 miner broadcasts collated recipients and amounts, 3 users do a multisig to fund and publish]

Interesting but limitations with DoS vulnerability & also multi-round.  Also presumably if the amounts are uneven you can pair spends and change amounts that match to inputs, and conclude one is the recipient of that sender and on the change to self.  However I see that's what the ref to a post by Mike Hearn was about, splitting the payments to lot of keys in small enough payments to create ambiguity.

https://bitcointalk.org/index.php?topic=93390.msg1036406#msg1036406


Towards a more efficient solution, maybe we could use a ring signature scheme so that groups of users can spontaneously form groups, and sign on behalf of the group without revealing which user they are.  (Ring signatures are like 1 of n multisig but do not reveal which user signed).

When all the outputs are group signed, the users sign their respective inputs to fund the transaction and publish it.

http://people.csail.mit.edu/rivest/RivestShamirTauman-HowToLeakASecret.pdf

To produce a ring signature, the actual signer declares an arbitrary set of possible signers that
includes himself, and computes the signature entirely by himself using only his
secret key and the others’ public keys.

That same set of users can then sign (with normal ECDSA) the inputs to fund the transaction.  Doesnt completely solve the DoS problems, but you cant just spam you have to join or be elected as a group member by the initiator (just one user).  The process of choosing which users will be in the group is flexible from the ring signature perspective - the other users dont even have to cooperate.  The ring signature concept was extended by others to cover DL based signatures (and EC) so I think you could simply enough add ECDSA ring signatures.

The point is you dont want to know who proposed each output, but the inputs have to be signed to release the funds.  And yet you dont want a spam free-for-all of proposed inputs, the ring signature keeps the proposed outputs unidentified as to which user proposed them.  The sender retains control however as he wont sign the input unless the outputs match the requirements of his payment and change.  The group setup doesnt need to involve the miner in this way either so everything can be done in one round.

[edit] btw the ring signatures are exceedingly computationally efficient, barely any more than the underlying signature in the case of Rivest's and its actually a simple concept here's a simplified example RSA ring signature: something like if an RSA signature is presentation of a s=H(m)^d then a simplified 2 user ring signature could be eg s1,s2 where s2=r and s1=(H(m) xor r')^d, r = random, r' = r^e then to verify the verifier calculates s1^e=H(m) xor r' and s2^e = r' and test with (s1^e xor s2^e =? H(m)).  Now you cant tell if s1 or s2 is random, and so it could have been signed by either person.  The other person you implicate in this "could have signed" game doesnt even have to participate, but the verifier and anyone can be convinced that the message must have been signed by one of them.  (Technically r is an existential signature forgery of "message" r'.)

Adam

[Serith]

Yes I invented hashcash, no I am not Satoshi 

Wikipedia article about Hashcash has the next line "It [Hashcash proof-of-work system] is also used as the proof-of-work protocol in Bitcoin" Wiki:Hashcash, which was added by you on November 2012. I think you have quite an ego considering there is no much similarities between the two apart from the name.

[mmeijeri]

Adam is justifiably proud of Hashcash, and it was an important influence on Bitcoin.

[Serith]

Adam is justifiably proud of Hashcash, and it was an important influence on Bitcoin.

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

[maaku]

Adam very well was in a position to be Satoshi - bitcoin is just a different application of the same technical ideas. I will take his word that he is not. If you want to debate it, you should probably do it somewhere else.

[adam3us]

Adam very well was in a position to be Satoshi - bitcoin is just a different application of the same technical ideas. I will take his word that he is not. If you want to debate it, you should probably do it somewhere else.

Taking a leaf from Meni Rosenfeld  https://bitcointalk.org/index.php?topic=121314 I figured I'd create a thread for people such as Serith (and he seems not alone) to dis me in. 

https://bitcointalk.org/index.php?topic=225463.msg2371674#msg2371674

Go for it


And now back to the ring signature sub-thread.  Ring signatures and accumulators are closely related with the convenient exception that ring signatures are directly anonymous (not requiring a ZKP of set membership like zerocoin and Sander & Ta-Shma's auditable electronic cash that predates zerocoin in its auditability.)

Most of the ring signatures are however also not compact (with signature size linear in the number of members of the ring).  With bitcoin thats the anonymity set size, analogous to the total number of zerocoins so in any real use thats probably worse than zerocoin.

This Shoup ring signature however has a small constant size:

http://www.shoup.net/papers/subring.pdf

(trying to decipher now) however it is based on an accumulator and sigma-proof (ZKP) not figured out how efficient that proof is yet to understand if its better or worse than zerocoins set membership proof, nor even if it could be directly used (membership proofs dont have to prevent multiple-uses, zerocoin does).

Adam

[mustyoshi]

Call me crazy, but if the algorithm is able to determine that you own the blinded coins, couldn't you in effect determine which blinded coins? By just doing the proof of work for each mint? And just use that to connect the dots?

[adam3us]

Call me crazy, but if the algorithm is able to determine that you own the blinded coins, couldn't you in effect determine which blinded coins? By just doing the proof of work for each mint? And just use that to connect the dots?

The ZKP in zerocoin is able to prove you know a w and c such that A=w^c (where w=witness, c=commitment/coin and A is the global accumulator value at a given point in time) without revealing w and c.  c has the form c=g^s*h^r where s is the coin serial number (revealed) and r is a random number never revealed.  c=g^s*h^r is a pedersen commitment, you can think of it like a hash function c=H(s,r) in that its hard to find either s or r (because it one way).  Also its collision resistant so its hard to find another s,r value eg to find g^s*h^r==g^s'*h^r' even if you know what s and r are.  That like symmetric hash function also hard to find H(s,r)==H(s',r').  The difference is pedersen commitments involve algebraic operations on big numbers and the hardness of discrete logs and so are easier to prove things about (ie because you can usefully multiply them etc - hash functions like SHA256 just make a big mess of their inputs to achieve collision resistance.)

So putting that together zerocoin have a ZK signature of knowledge ZKSoK[tx]{(c,w,r):A==w^c and c==g^s*h^r} ie c,w,r are not revealed, tx is the transaction that is revealed and signed by the zerocoin spend/signature (eg tx = spend this zerocoin to this bitcoin address), s is revealed and stored and is the serial number that is recorded to avoid double-spending.  ie combining it shows that A==w^(g^s*h^r) and they were able to find a somewhat large way to prove that without revealing c,w,r.  Its large because it involves multiple cut-and-choose rounds as each round is only 50:50 convincing that what the prover claims is true.  After 80 rounds its security is 1/2^80 which is quite good.  (Though bitcoin aims for 2^128 which is more, they only used 80 to save space - 40kB was already unfortunately large for the zerocoin spend ZK "signature".

s is revealed and is the coin serial number, so its important that r is not revealed otherwise anyone could calculate c=g^s*h^r and just scan for that in the list of zerocoins de-anonymize the coin spends .  Fortunately because of the collision resistance of the pedersen commitment (hash function) not even the owner of the coin can create different s, r equal to the same c so he cant get two coins from one that way.  But to prevent the owner of the coin creating c=g^s'*h^r' * g^s * h^r and then proving two separate coins (and that would work because A = u^(c1*c2 *... cn) for all zerocoins ci) they further require that c be a prime number.  So you're not proving its prime via the ZKP when spending, but you are proving it when you create the zerocoin - all the miners check if c is prime (as c is revealed at that point).  So thats why c is prime.  (I had to ask Matthew Green that it was puzzling me as making c prime is moderately expensive, and why it takes 0.5 - 2 seconds to just create a zerocoin, and the Camenisch and Lysyanskaya paper the zerocoin accumulator comes from uses c prime only for  different reason that zero coin doesnt need - membership deletion).

It seems counter-intuitive that you can prove things without revealing them but thats what ECDSA does too - it proves that the signer knows the EC discrete log.  Its basically because you can see that only someone who knew the discrete log could have computed the signature, and yet anyone can see that the signature is valid.  The ZKP is the same just more complicated.

Adam

[apetersson]

thank you for that concise explanation. i think i am 70% "there" to understand the basic properties of zerocoin.

can you elaborate or give links on the operators "^" and "*" is this the actual power and multiplication? then how can c be prime if it is defined as a multiplication of two powers?

[Rassah]

Sorry if this is somewhat off-topic, but could OpenTransaction's off-chain transactions and blind signatures help with this at all? (even though it would depend on some third party running an OT server)

[caveden]

Sorry if this is somewhat off-topic, but could OpenTransaction's off-chain transactions and blind signatures help with this at all? (even though it would depend on some third party running an OT server)

OT already have its cash-only mode which is as anonymous as it gets.

The point of ZeroCoin, AFAICT, is precisely not to depend on a server and just use the blockchain to achieve the same result. (I confess I haven't read ZeroCoin's paper and I have no idea how it works)

[adam3us]

thank you for that concise explanation. i think i am 70% "there" to understand the basic properties of zerocoin.

can you elaborate or give links on the operators "^" and "*" is this the actual power and multiplication? then how can c be prime if it is defined as a multiplication of two powers?

[edit used sup and sub for exponent and subscripts]
^ is power modulo some prime or RSA modulus depending on the situation and * is modular multiplication.

So the A=u^{c₁c₂...c_n} is modulo N an RSA modulus N=P*Q two primes P & Q.  A is the accumulator.   Note c₁c₂..c_k gets pretty big as users cant reduce it as they dont know phi(N) = (P-1)(Q-1) - no one does as its deleted after parameter generation.  u is some fairly chosen quadratic residue (square numbers mod N) ie there exists u' st u=u'² mod N.

This is the P & Q where you unfortunately get to trust someone to delete them.

Next for each coin c=g^sh^r mod p, where p is a fixed prime (not the same prime as P) actually a strong prime (where p = 2q+1, or even p=2^wq+1 for some integer w, to get a smaller q).  Because c=g^sh^r mod p c can be prime ie g^sh^r is clearly not prime by definition (it divides by g, h, g² etc) but g^sh^r mod p can be prime.  It quite a bit of work of trying random commitments to find a prime c though.  I tried coding it in openSSL and it wasnt that fast eg c=g^sh^r check if its prime, if not c'=c h mod p (so that c'=g^sh^r+1 mod p) and repeat.  Prime density is not so great at those sizes.

g and h are two generators in the shnorr group of size q.

So its curiously using two completely different groups - an RSA group for the accumulator and a Schnorr group for the pedersen commitment sounds odd but it doesnt really matter they are independent.

Now you can easily choose a c with two commitments in it (trying to get two zerocoins for the price of one bitcoin): prime c=g^s₁h^r₁ g^s₂h^r₂ mod p=g^s₁+s₂h^r₁+r₂ mod p.  

However to cheat and prove/spend two separate witnesses and zerocoins paid for with one bitcoin you need to prove you know A=w₁^c₁ mod N and also A=w₂^c₂ mod N with w1=u^{c₂c₃...c_n} mod N and w2=u^{c₁c₃...c_n} mod N.  However A=u^{c c₂c₃...c_n)} mod N because we paid for zerocoin c with our bitcoin.

So the only way to cheat is find c₁,c₂ such that c=c₁ c₂ or c=c₁c₂ mod phi(N).  You cant find c=c₁ c₂ because c is prime.  And you cant find c=c₁ c₂ mod phi(N) because you dont know phi(N) = (P-1)(Q-1) because P & Q are deleted during zercoin genesis.

If you could find such a c₁ and c₂ you would have found phi(N) by definition, and using that you can factor N trivially - ie thats impossible unless you can break RSA.  (You need phi(N) because you have to reduce the exponent by phi(N) with RSA ie A = u^c₁c₂ mod N = u^c₁c₂ mod N = u^{c₁c₂ mod phi(N))} mod N.

Now if you did know phi(N) = (P-1)(Q-1) you could clearly create multiple zerocoins for the price of one bitcoin.  So thats the trust in the person who sets up the value of N during zerocoin genesis.

Adam

[marcus_of_augustus]

Adam : any chance you can get that stuff into Latex or some equation displayer ... my eye's are allergic to math with ascii text

One way is to write them at this site
http://www.codecogs.com/latex/eqneditor.php

... and link them into the text here either as gif or html if the forum supports it.(bit hacky but it works)

[Mike Hearn]

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.

See section 4.

And yes, discussions about p2p mixing are quite old, that thread I'm quoted in is from July 2012.

I'm not sure Gavin is correct when he says ordinary people don't care about privacy. They care very much, hence the proliferation of scare stories in the media, the success of Facebook over MySpace, etc. That doesn't mean people will go to any lengths to get it from any and all parties though. Not all privacy adversaries are created equal.

[maaku]

I thought Gavin said ordinary people don't care much about anonymity. I'm not sure I concur, but it is a valid and important distinction between privacy and anonymity. With the right tools bitcoin does well with the former. Zerocoin addresses the latter.

[adam3us]

I thought Gavin said ordinary people don't care much about anonymity. I'm not sure I concur, but it is a valid and important distinction between privacy and anonymity. With the right tools bitcoin does well with the former. Zerocoin addresses the latter.

You can get privacy without anonymity, eg as with the committed coins idea https://bitcointalk.org/index.php?topic=206303.0, only the sender and the recipient get to see the coins and who is spending to who.  (Unfortunately the committed coin privacy is not ideal because later people in the transaction chain of committed-form respends necessarily have to learn all previous details for validation reasons).

Some of the privacy focused ecash systems distinguished between payer anonymity and payee anonymity.  As a buyer you dont necessarily want all your payments to allow the public, the (ecash) bank nor the merchant to track which say ebooks you are reading.  It none of their business.

However the usual argument to blackmail crime scenario is that the criminal cant do that if there is only conditional payee anonymity (ie the spender colluding with the ecash bank can identify who the receiver is).  In bitcoin there is no bank to collude with, but you could imagine arbitrators in that role, or that the payee is identified to the payer (but no one else).  And of course the identify the recipient ignores identity theft, and assumes criminals are mindless non-adaptive automatons so its a fairly weak argument IMO.  In any system that strips privacy, the people who suffer loss of dignity and privacy invasion are the normal users, the criminals can still get privacy via identity theft, fake identities, buying fake identities from corrupt employees of government id issuers etc.  And criminals still launder money en-masse even with regular banks.   HSBC which reportedly laundered $880m of significantly dirty mexican drug cartel and even terrorist money and faces a $1.9b fine.  http://www.guardian.co.uk/business/2013/may/23/hsbc-court-threat-money-laundering-charges  Probably HSBC are going to walk away with the fine only (too big to jail despite the posturing).

Another possibility is it would be technically possible for the spender to be convinced who the recipient is without being able to prove it to other people eg with a ring signature, non-transferable signature, or designated verifier signature (the spender being the designated verifier).

Being able to sell things anonymously is a different and actually separable feature.  But people have also made pretty convincing arguments about why individuals should have the right to retain privacy while selling physical or virtual goods in a free society.

But I do think bitcoin ideally needs to find an efficient way to fix the fungibility problems with taint.  Payer privacy without payee privacy might not fully fix that as a payer who claims he didnt make the payment (claims the thief made the payment using the victims wallet to the thief) the victim would then identify the recipient.  If there were identities separate from coin addresses, you could imagine payee/recipient losing privacy on payer complaint, without the payee losing ability to make further payments with payment privacy.  ie the payee is expected to repay the value, not that the coins themselves become traceable.  However even then when identity is some random public key with no certification, its really not much of a threat to burn an identity.  Fidelity bonds perhaps are closer to network identities with some cost to losing.

Even in the physical world with conventional banks, once non-petty criminals are involved "identifying the perpetrator" becomes a fuzzy and useless fig-leaf fast as they identify a victim, or a fake identity bought from a corrupt government employee, or dupe the issuer - the RA stage is usually inherently pretty weak.  Criminals rent identities (money mule), buy or create fake identities, shell companies etc.

Finally to note a payment system could obviously have emergency tracability added to it as noted in the zerocoin paper.  Its typically easy technically to selectively weaken a protocol.  The problem is if you want it at all, you want emergency tracabiliy to be restricted to genuine emergencies, not drag-net fishing, not tracing of petty crimes.  Law enforcement are not always so clever about drawing lines there so you get mission creep until jay walking is an emergency.  eg in the UK I read a local council abused crime surveillance cameras to trace people who were bending the rules about which area they lived in to get their kids into a better school!  Next up people not pooper scooping their dog.  You know those things were weakly approved by society for terrorism clean up and maybe, arguably, serious organized crime.

Some ecash crypto papers have talked about system limits like payments are fully untraceable if they are under some amount (eg $10k like paper cash reporting limits) or under some amount per day per user.  Another limit can be the "emergency" access is limited to 1% of traffic period, more is not cryptographically possible.  Or I think alternatively and more simply access requires cooperation from involved users would be a nice balance.  Everyone has to transact with someone, and most transacting parties have no particular interest to protect some organized crime activity that rented a server or car from them.

Anyway the whole thing is a big mess.  And it's hard to maintain binary fungibility in the face of grey fuzzy privacy/traceability, and court ordered mission creep.  Computers do binary well so to me that is the natural physics of crypto and p2p virtual payments: irreverasable is cheaper than charge-backs (cash over credit cards), and there is no partially irrevocable.

Probably in an actual free society, people would understand that more people being killed by furniture falling on them than by terrorists should be sort of factored in in terms of spending and focus, and societal balance.  Obviously the people charged with cleaning up and infiltrating these things are too involved for perspective, but they work for society not the other way around.

The UK had its share of history with IRA blowing various stuff up, the US news typically in that era referred to the IRA as freedom fighters, some US factions even funded them, and yet the sky did not fall, eventually the UK lost their face of "we do not talk with terrorists", the IRA became involved  in the political process, some political prisoners were freed, and now things are not blowing up.  The UK government got up to some pretty shady things in the history of the troubles also.  Its just possible that the current problems have an element of blow-back and two sides to any argument also.  Its kind of interesting from inability to learn from history that the UK government finally admitted and will compensate victims of its past torture of kenyan resistance fighters and civilians including Obama's grandfather in kenya troubles, and here is Obama presiding over the next generation of the same picture (the powerful torturing the weak for attempting asymmetric and reactive warfare).  That still seems to me like a retrograde step, trials were heard at nuremberg about such activities in the past for good reason.

Adam

[adam3us]

So apart from the political blather this bit seems to be like a potentially interesting idea, perhaps other people had the same idea before

But I do think bitcoin ideally needs to find an efficient way to fix the fungibility problems with taint.  [...] If there were identities separate from coin addresses, you could imagine payee/recipient losing privacy on payer complaint, without the payee losing ability to make further payments with payment privacy.  ie the payee is expected to repay the value, not that the coins themselves become traceable.

ie why not as a design objective try to separate identity from coins.  So you make the coins payee and payer anonymous, and then each user has a wallet identity/pseudonym that maybe optionally disclosed to the other party, or revealed to other party or to the auditor in event of dispute.  In that way we avoid taint, and yet the privacy and anonymity of the payment system becomes more arbitrarily tunable and even negotiable between parties, or set by system default.  Taint and tracability of taint is bad because it affects fungibility (in a p2p respendable ecash system like bitcoin, random users end up holding retroactively tainted and reduced value or unspendable coins through no fault of their own, and this erodes confidence).  But a system may like to offer or aim for a specific privacy level or traceability of amounts and identities.  Those things thereby become separable.  Nice

Now all we have to do is find a way to make zerocoin efficient.  (And that seems to be the question of the hour - its not at all obvious how to do that).

Actually its an open question how far bitcoin direct chain transactions scale, so maybe there is some hierarchy of off-chain (or sub-chain) that evolves eg around miners, exchanges, or p2p sub-chains that offer lower value coins, that backed by the main chain but not detail validated by it.  The supposition being that if bitcoin does hit a scalability limit (fails to scale as fast as its adoption), the minimum effective transaction value amount that is economical to send due to fees will go up, a lot.  Maybe the main chain is used for inter-chain clearing and investment level bitcoin holdings.

So maybe the privacy policy types of things get decided by competing sub-chains and off-chain transactions in such a bitcoin world.  And seemingly its not obvious how to do sub-chains and off-chain transactions without trust for double-spend protection.  (Which is why things like fidelity bonds come up in this scenario).

Adam

[Peter Todd]

So maybe the privacy policy types of things get decided by competing sub-chains and off-chain transactions in such a bitcoin world.  And seemingly its not obvious how to do sub-chains and off-chain transactions without trust for double-spend protection.  (Which is why things like fidelity bonds come up in this scenario).

A good way to think about the issue is that a digital currency can be either based on consensus, authority, or detection and punishment.

Authority is the easiest to understand, that's just how PayPal works. Authority-based currencies have the best scaling properties because with 1 authority, n transactions results in n work. Trust in an authority-based system is absolute at the protocol level.

Consensus is how Bitcoin works, but because everyone needs to have the full transaction history, n transactions results in n^2 work. Of course, you can cheat and reduce the number of full nodes out there, but it starts looking increasingly like an authority based currency. Trust here is again absolute, but you are only trusting a majority of participants in the consensus voting scheme.

Detection and punishment systems are a mixture of the two. You trust some local authority, but you maintain automated ways to detect that fraud has occurred, and automated ways to punish that fraud. Unfortunately in Bitcoin as it stands the best way we can punish fraud seems to be to just stop doing business; fidelity bonds make that action expensive for the fraudulent party, but they aren't perfect. With some changes to how Bitcoin scripts work we can turn a proof of fraud into a direct punishment, or even an action that triggers a refund of the funds held by the third party, but that will require a soft-fork at least and a new scripting system. How these systems scale really depends on how efficient detection is, but n*log(n) work appears to be a good rough estimate.

We do need more work on the mechanics of detection, especially with looking into the possibly of changing the scripting language so that punishment/refunds can be done directly.

At the same time, at worst the scaling approach many are advocating turns Bitcoin into an authority based system in the long run, and at best turns it into a detection and punishment system, albeit one with fairly limited punishments that themselves can cause serious problems for the system in terms of technical complexity and stability.