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

It has begun!

I saw this: https://github.com/Zerocoin/libzerocoin

Rule changes could be backwards compatible, e.g. allowing homosexual marriage would not make any existing or future heterosexual marriage illegal. The opposite is true for bitcoin: tightening rules would not make existing clients obsolete

The ability to soft-fork is one of the most visionary design in bitcoin

Rule changes are, by definition, not "backwards compatible". That is the whole point of Bitcoin. You are SUPPOSED to get hard forked off if the rules change and the fact that blocks stop being processed at that point is deliberate.

Yes, if you were to introduce something like ZeroCoin, ordinary users would expect it to be a hard fork. Soft forks are a nasty hack that violates peoples expectations of how their nodes will behave in the face of rule changes.

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

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.

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?

gmaxwell said it could be a soft fork: https://bitcointalksearch.org/topic/zerocoin-when-216982

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

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

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?

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.

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.

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

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

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

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

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)



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.

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.


Is that described on the bitcoin wiki under fidelity bonds?

Adam

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


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?


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.


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?


tip =
similar conditions =

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:


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:


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.