Topic: Zerocoin: Anonymous Distributed E-Cash from Bitcoin - page 6. (Read 37806 times)

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.

Greg also said something like that:

https://bitcointalksearch.org/topic/i-taint-rich-raw-txn-fun-and-disrupting-taint-analysis-51kbtc-linked-139581

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


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://bitcointalksearch.org/topic/m.1036406


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


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

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.

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.

Maybe this could even be combined with homomorphic encryption to obscure the incoming amounts and to consolidate chains of transactions? The combined effect would be netting of transactions with obscured incoming amounts.

Could we simplify this by creating a new hash type combining the effects of SIGHASH_SINGLE and SIGHASH_ANYONECANPAY? It would mean "as long as my output is included, I'll release my input". A further step would be to require valid blocks to consolidate all such transactions into a single transaction.

Not sure what's the proposal that you have in mind, I remember others talking about such ideas in 2011 in #bitcoin-dev (link), and these ideas could be a lot more efficient than using ZK proofs.

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. Suppose Alice wants to send 5 bitcoins to Bob, Carol wants to send 4 bitcoins to Dave, Ellen wants to send 3 bitcoins to Frank, and we now wish to construct the next block with these three transactions. So in round 1 Alice broadcasts a message that declares that she intends to send 5 bitcoins to Bob's address (without signing this message with her privkey), and Carol and Ellen do the same. Now in round 2 the miners prepares a single transaction with the inputs of Alice,Carol,Ellen (12 bitcoins in total) and the outputs of 5 bitcoins to Bob's address, 4 bitcoins to Dave's address, 3 bitcoins to Frank's address, and broadcast this single transaction. In round 3 Alice signs this single transaction and broadcasts her signature, and Carol and Ellen do the same. Now the miners can do PoW work on a block that contains this transaction, and finally broadcast the valid block that they solved. This way the block is created in a mixed fashion, in the sense that the data that resides in the blockchain doesn't specify whether Alice's (possibly tainted) coins were sent to Bob or Dave or Frank. After iterating this same process with the next blocks, it would be practically impossible to tell where Alice's tainted coins ended up at. An attacker can eavesdrop on the network and know that Alice sent her coins to Bob, but he cannot prove anything because Alice's message in round 1 isn't signed and therefore can be forged by anyone.

Problems with this idea:
1) Alice must send a fee as a secondary signed transaction in round 1, otherwise if Alice is malicious then she could refuse to participate in round 3 to carry out a denial of service attack, because the single mixed transaction is valid only if both Alice and Carol and Ellen sign it. On the other hand, malicious miners could now collect fees without including txns in blocks. Maybe it can work if the fee in round 1 is smaller than the fee that Alice would pay for the actual transaction where she transfer her coins Bob, so the miners will have an incentive to generate non-empty blocks (i.e. not to generate blocks that contain only the fees of round 1) ?
2) When the miners are working on the PoW, if other transactions (with high fees) were broadcasted in the meanwhile, then in order to include the extra transactions they'd have to prepare another single mixed transaction (because the signatures for the first mixed transaction have already been provided). So it appears that this process will work in batches, where a block could contain several such mixed transactions. We should be careful that the default behavior of nodes is to prefer signing mixed transactions with many inputs, otherwise malicious miners could attempt to reduce the overall privacy.

Any suggestions on how to improve this idea?

Edit: Looking at another thread (link), I see that here too we'll have to do the knapsack-style random value splits. I suppose that it means that Alice should request several receiving addresses from Bob before she sends her coins to him? Or maybe just one pubkey and chaincode, if Bob is using type-2 deterministic wallet.

Whats taint?

this question does not really belong to this thread because exactly the same happens with zerocoin or without.
if you lose the password of a protected wallet and it is the only backup - the money is gone. with zerocoin or without.

I have a weird question...what happens to password protected wallet of dead person or person who forgot his password? Are these bitcoins lost forever?

Yes I had the same thought - seems awfully expensive for a mix.  You can view zerocoin as a private keyless p2p mix.  Several people have proposed non-p2p mixing protocols where the mix cant steal your coins.  Whats wrong with that?  I guess the main limit is the mix disappears and your coins get locked.  Probably that could be fixed with smart contracts/multisig.

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

(Other than mixing you may also aim to taint all, equally as a protocol).


I agree that is likely the end game for mixes.


The committed coins idea that temporarily keeps the taint decision private allows people to at least retain p2p decisions about taint without any a priori restrictions.  However the privacy is either short-lived (fairly immediately decommit the coin) or the privacy shrinks over time (if you keep spending the coin in committed form) as more people get to see the transaction history, as each recipient must see all details prior for validation.  A posteriori sanctions after decommit may come into play to if the user is identifiable - if your IP address is logged as posting the reveal of a tainted coin, maybe that matters also.

Fairly efficient/low overhead but still some limitations there.


It seems like users who are doing high value bitcoin things should be using ToR to hide their IP address which geolocates them.  And servers also should to add resistance to network split types of attacks.  Maybe in a 2.0 bitcoin it might include the minimal defenses of encryption, tunneled relaying and hard to influence remote connections for double-checking local claims.

Adam

my thoughts in response to "doubting gavin's" post:

i think this idea has merit for these reasons:

Today taint is irrelevant for 99,99% of transactions. if someone tips you would you go back and try to trace that and will you try to "remove" that money from your wallet? i guess not. likewise most payment processors would not care. i don't know if mtgox performs any checks, but i would guess yes.

it improves fungibility of coins - if a block includes a valid input it should not matter where they come from. having zerocoin out there working removes all doubt about fungibility and "solves" this issue.

I see many valid use cases why someone would love to use zerocoin.

Just one example: in the year 2023 Gavin and family want to go to vacation to Mexico. Books a 4* hotel for 3 mBTC for two weeks using his desktop wallet.
The wallet of the hotel is of course a HD Wallet where Los Zetas control the master private seed. Thanks to trivial blockchain analysis and entity merging they are informed that someone with 10+ Bitcoins *gasp* is coming, and know their exact location and time.

Once he arrives access to his wallet is obtained via rubber-hose cryptanalysis.

If there was Zerocoin you could trivially create a "holiday spending" identity it would be very hard to estimate someone's net worth in bitcoins just by obtaining one transaction. Put 10 mBtc there and have two nice weeks.


Yes the proofs might be large and therefore most transactions would be expensive - this is why fees are calculated by KB. i would say, we should let the a free fee market decide if it is worth using and worth of inclusion in blocks.

hopefully we can explore this interesting topic further reducing the overhead further. i am still trying to understand the details of how it works but so far - i think it is absolutely worth including something like zerocoin into the mainline client, once we have a "good enough" solution.

I have a feeling that anything on this front that will work in the end will:1. require no change to the code of the Bitcoin client;2. interoperate seamlessly with the current infrastructure;3.have adjustable level of paranoia/usability ;4. backed by competent and transparent developers.

I've started and then stopped writing about Zerocoin three or four times now; my thoughts about it are still muddled.

It adds a whole lot of complexity to transaction creation/verification to solve one problem:  how to mix coins/transactions with zero trust in the mixing process.  That's technically nifty, but I wonder if it is the best engineering solution.

I wonder if just using a couple of semi-trusted mixers would be a lot faster/smaller/simpler.

And then I start thinking about "tainted coins" in general. If we imagine a world with either mandatory or voluntary "taint tracking" (I have no idea whether or not that will ever happen), then it seems to me any mixing scheme that isn't "always on" is likely to fail in practice-- all coins coming out of the mix will be considered tainted.

Why? I assume that most users (if you are reading this are NOT "most users") don't care much about privacy/anonymity. So I would assume most people would choose the lowest cost, fastest, most convenient method for their transactions. Anybody using a mixer will be either a weirdo, principled privacy nut (like us) or a criminal. I don't see other "privacy first" projects taking over the world, but do see lots of big, successful "quick and easy and free" projects.

Then my thoughts get muddled, because "it is hopeless, just give up" is not an answer I'm willing to accept. But it feels to me like finding an essentially zero-cost way to increase transaction privacy that everybody uses by default is the best answer. Making your network connection more private is the other piece of the puzzle, though, and all of the solutions for that (either route through a couple of semi-trusted proxies or use Tor or i2p) add significant convenience/speed/financial costs.

So one thing you could think of and I think it has been mentioned a few times is that you could replace the merkle tree in bitcoin with an accumulator based tree.  Now a problem with accumulators is someone or some set of n people only 1 of whom has to be trusted, have to create n = p*q two primes p, q and then delete p, q; which is not great but could be entertained perhaps if accumulators made some big saving.

Consider accumulator hashes: then an SPV client can be convinced a coin is in a block by receiving Bi and xi.  Each Bi is 384 bytes (3072bit RSA n is about the same security margin as the rest of bitcoin, considered about as secure as 128-bit symmetric keys and 256-bit EC keys).  Then a proof of membership within a block is 384 bytes + the hash say 20 bytes + the transaction detail whatever that is a hundred bytes say 512bytes.  

The merkle tree approach requires log2(k) hashes each 32 bytes, k the number of transactions in a block.  I guess a block could hold ~10,000 transactions best case with 1MB blocks.  However this page https://en.bitcoin.it/wiki/Scalability says transactions per second is currently limited to 7 = 4200/block.  log2(4200) ~12 and 12*32=384 bytes.  No saving for accumulators!

However another trick could be to not start a new accumulator with each block, just keep going, then you only need the last block in the chain.  (SPV clients download all blocks, or some set of recent blocks for confidence?)   So with accumulators to catch up an SPV client just download the latest block, cross-check a few peers agree its the latest block.  However someone (each full node?) would have to update Bi for all unspent coins.  Updating Bi is a 3072-bit to a 256-bit modexp operation which has some cost.   That might start to get unreasonably CPU expensive, unless the network shares out the work.  The benefit would be faster catchup for SPV clients.

I suppose alternatively blocks themselvs could be placed into a sorted merkle tree, and then SPV clients could download blocks as needed (log2(b) blocks where b is 23866 blocks so far http://blockexplorer.com/q/getblockcount) ~15 blocks to test a given block.  But its probably not a big saving because transactions are made from multiple outputs and an SPV client if it does a few transactions per day will soon have to download all blocks anyway.

Or you could have an accumulator tree of blocks, with the accumulator hashed in the latest block.  Then you can download any historic block and instantly check it belongs in the history of the current block without downloading the rest of the block chain, nor 15 blocks for log2(b) verification if the block were organized as a merkle tree.  Cost is each full node needs to update (or fullnodes cooperatively update) the Bi values for all 23866 blocks every block (10mins).

Some possibilities in there but nothing very impressive, plus the problem of there temporarily existing an accumulator private key that must be deleted (spread across the RAM of n users during accumulator genesis/generation, only one of which needs to be trustworthy).

Adam

Btw I made a summary of the zerocoin paper here.  

http://www.mail-archive.com/[email protected]/msg04117.html

Not sure it helps understand it or not, but there you go.

About ZKP of set-membership the first thing to understand is the RSA accumulator of Benaloh.  

http://www.cs.stevens.edu/~mdemare/pubs/owa.pdf

Its like a commutative hash function but using RSA.  With discrete log (or EC discrete log) if i give you A = xG (G is base point x some random number) I can prove I know the discrete log by showing you x and G is fixed.  But if you are allowed to use any generator H then you can start with A divide it by some random number x and call the result H.  Now you can prove xH = A but that doesnt prove anything as anyone can do that if they can prove the discrete log to some random base its an x-th root not a discrete log, which is easy .  How you "divide" A by x is multiply by x^-1 mod n (n is the order of the curve a public known value for a EC parameter set).  And you can compute x^-1 mod n easily with euclidean algorithm (normal modular math, no EC).

However the analogous division is not possible with RSA, in RSA computing x-th roots is also hard (as well as discrete log).  eg If I give you A you cant compute A^(x^-1) because x^-1 has to be mod phi(n) = (p-1)*(q-1), and in the case of RSA phi(n) is secret and in the case of an accumulator p, q, phi(n) are supposed to be deleted after setup so no-one knows them.  So if I can show you H and x and H^x = A that proves you I had an influence in producing A.  

each step is done by the user after receiving the previous accum set.  Users can go in any order as exponentiation is commutative.

G and n is published, p, q deleted
step0: accum set = {G}
user1: private x1, accum set = {G,A"=G^x1}
user2: private x2, accum set = {G^x2,G^x1,A'=G^x1^x2}
user3: private x3, accum set = {G^x2^x3,G^x1^x3,G^x1^x2,A=G^x1^x1^x3}

The accum set is broadcast by each user and each user raises every element except the last to his private exponent xi, and appends the last element raised to his private exponent xi.

You notice that the base of each user is missing the exponent of his respective xi, user1 base is missing x1 (first item in set), user 2 is missing x2 (second item in set), user 3 is missing x3 (third item in set).  Consequently a user can raise his private base call it Bi for user i, to power xi and get A the global accumulator Bi^xi = A.  Because discrete log and x-th roots are hard in RSA he cant do that unless he was involved in this process.

That involves a lot of sending of sets.  If alternatively each user broadcasts his xi, everyone can compute his own Bi and the final A, however now anyone can compute any Bi and all xi are public.  Its a lot more communication efficient however.  To combat the fact that xi are public, xi has to be chosen eg as xi = H( yi ) where yi is secret.  Then a user can prove that by revealing yi and having the verifier check xi = H( yi ) and Bi^xi = A.

Or as its hard to efficiently make ZKP about (symmetric) one way hash functions a discrete log "hash" function could be used eg xi = H^yi.  Now the user could prove knowledge of yi without revealing yi (via a Schnorr signature see below).

So lots of people compute and pass those messages around then they can prove simply that their zerocoin is in the set until there is a final A that includes contributions from all users who produced zerocoins in this time period.  And each user knows a Bi such that Bi^xi = A for the single A value so they can prove membership.  The order is commutative so it doesnt matter which comes first.  A is small - just 2048 bits = 256bytes no matter how any serial numbers are provable against it.  Bi is also small 256bytes as well as is xi.  And the user need only store Bi and xi because he can compute A from it.

So that provides a proof that you had an influence on an accumulator (some non-secret value of yours was included "hashed" into an accumulator).  Its rather like a merkle tree except that you dont need to provide log n path in the three to prove, just prove you know Bi^xi = A.

So far thats not private as all Bi values are recognizable to anyone who saw them.  However using an extended blind schnorr signature like proof where you can prove you must know such an xi and Bi without actually revealing them.  Its ZKP because the verifier could even create a fake if he choose the challenge himself so therefore you can argue he couldnt learn anything about Bi nor xi from something he could've created yourself.  

A schnorr proof of knowledge to get an idea how you could prove something similar is related to a DSA signature and relatively simple eg here.  http://en.wikipedia.org/wiki/Schnorr_signature and its the same concept as DSA, ECDSA etc - ie you can prove you know the discrete log of something, without actually revealing the discrete log!

A schnorr proof only hides xi, the zerocoin enhanced proof also hides Bi but the basic idea is the same.

The efficiency problem in zerocoin is that each run of the ZKP has a 1/2 chance of being unconvincing.  So you have to run it like 128-times to get probability 1/2^128 kinds of cryptographic assurance.  This repetition is called cut-and-choose.  Fortunately it can be made non interactive (by fixing the challenges based on a one-way hash of the parameters), but thats still 128 x 2048-bit RSA things which is like 10s of kB.  Probably they are doing a bit less than 128 cut-and-choose rounds because they say that proof size is 45kB for 2048-bit and I presume a proof includes at least 2x 2048-bit values.  Actually I see they say 80x, so that comes out to 2.2 so maybe there is some auxilliary info, eg the serial number?

To prevent double spending they just keep a public list of spent zerocoin serial numbers, and you cant influence the serial number after the fact.

So I guess the other thing you can do if that is unnecessarily complicated is just say ok there's a ZKP of set membership which proves your coin is one of that set, but not which one and trust that people have figured out how to make that work.

btw Benaloh's accumulator paper is quite readable

[edit: fix error about xi vs Bi and give a small example]
[edit2: more communication efficient public xi = H^yi, secret yi or xi = H( yi ) version]

Adam

Haha, well thanks anyway.

Yeah, I'm afraid you would have to delve into zero knowledge proofs. There are some good papers on the internet, but I can't say I fully grasp how it works just yet.

Okay, is there a way for me to comprehend this without venturing into the world of digital commitments, one-way accumulators and zero-knowledge proofs? I mean, I can explain the inner working of Bitcoin to quite a level of detail (at least to anyone with a technical degree) before someone has to take my word for it. Is it possible to explain how I can prove I own 'some unredeemed Zerocoin in the blockchain' without specifying which one without a PhD is cryptography?

I want to believe but I need to be convinced I guess

You can't trace the proof back to the specific coin, all you can see is that to a high degree of probability the person redeeming the zerocoin possesses the secret trapdoor associated with one of blinded coins.