Zerocoin when?

[luv2drnkbr]

Posting here in the hopes Gavin sees it...  Are there any plans for a zerocoin hard fork implementation in the future?  Not even the near future, but any future.  Or is that just not at all in the cards?

[1714801333]

1714801333

[1714801333]

1714801333

[gmaxwell]

Posting here in the hopes Gavin sees it...  Are there any plans for a zerocoin hard fork implementation in the future?  Not even the near future, but any future.  Or is that just not at all in the cards?

Plenty of people other than Gavin are perfectly competent to answer this question. I've split your post off of the 0.8.2rc3 thread. Please don't make off-topic posts just to try to reach specific parties.

As zerocoin is currently designed it is not viable as a production component in Bitcoin:

* >40kbyte signatures (the authors of the paper give some hand wave at a DHT but this doesn't meaningfully solve the problems created by enormous transactions: the parties interested in them and all full nodes must transfer them to validate them)
* Requires a trusted party to initialize the accumulator (there may be some multiparty computation trick to avoid this, but it's not clear how to apply one in the context of an anonymous system with users that come and go)
* Accumulator grows forever (unprunable, though you could rotate accumulators at the cost of the anonymity set size)
* Validation that runs on the order of 1-2 transactions per second.

Of course, computers get faster and techniques get better: If some combination of improved technology and improved techniques made it 1000x less intensive relative to now it would be pretty interesting. Also, if threats to fungibility aren't addressed through less expensive mechanisms it may become more interesting even if the cost is still somewhat prohibitive.

FWIW, inclusion of something like zerocoin would not require a hardfork. I believe it could be happily accomplished as a soft forking change. Bitcoin is designed to be extensible and able to incorporate new transaction rules without breaking compatibility.

[maaku]

Also, it's not clear yet that zerocoin is the best solution. There was a very interesting talk at the conference about SCIP, which would provide a more general zero-knowledge proof subsystem.

And if anonymous mixing is all you want, there are still lighter-weight solutions that achieve that goal.

[runeks]

FWIW, inclusion of something like zerocoin would not require a hardfork. I believe it could be happily accomplished as a soft forking change. Bitcoin is designed to be extensible and able to incorporate new transaction rules without breaking compatibility.

Will you expand on how this could be possible?

I don't know the cryptography behind Zerocoin, but - as far as I can see - if bitcoins can move from one address to another via Zerocoin, then all clients need to be able to verify this, right?

[Mike Hearn]

A "soft fork" is a hack. It means miners know about the new rule and other nodes don't, so those nodes can accept blocks that don't follow the new rules, but eventually those blocks will get re-orged away.

I don't personally like soft forks and think we shouldn't use them. The assumption that appearing in the block chain means the transaction is valid (according to everyone) is pretty fundamental. Breaking that by having transactions that are "valid" except that they're not going to actually be accepted by the majority undermines that principle. And so far there haven't been any compelling reasons to do it. P2SH has turned out to not be used so far, even though at the time it was deemed important enough to not want to wait for a scheduled hard fork. ZeroCoin isn't usable for the reasons gmaxwell cited back in May.

There are lots of ways to improve user privacy that don't involve any kind of fork at all - it'd be weird to use a complicated backwards-incompatible scheme before simpler backwards compatible schemes have been implemented.

[Qoheleth]

P2SH has turned out to not be used so far, even though at the time it was deemed important enough to not want to wait for a scheduled hard fork.

P2SH is used all the time. It's, like, the second most popular address type (after traditional hash(pubkey) addresses).

[Mike Hearn]

Given there are only two kinds of address, I guess that's not hard. Or did you mean scriptPubKey types?

What I meant is that I use Bitcoin as an end user pretty regularly and didn't yet encounter a P2SH address. They certainly have been used, but are they being used regularly? And if someone is using them regularly, would they continue after the payment protocol is available? These things aren't really clear.

[maaku]

What I meant is that I use Bitcoin as an end user pretty regularly and didn't yet encounter a P2SH address. They certainly have been used, but are they being used regularly? And if someone is using them regularly, would they continue after the payment protocol is available? These things aren't really clear.

We're wandering off-topic, but what does P2SH have to do with the payment protocol?

[etotheipi]

And if someone is using them [P2SH] regularly, would they continue after the payment protocol is available? These things aren't really clear.

For reference, when Armory implements multi-sig and linked wallets, P2SH will become a staple.  It's not that there isn't use for them, it's that you need existing, mature wallet software to build on top of, and there just isn't a whole lot of options for that.  If I hadn't made such poor scalability decisions in Armory two years ago when it was started as a pet project, I probably would've done it by now...

[Mike Hearn]

I think you'll find you don't need P2SH when you implement those features.

[Peter Todd]

What I meant is that I use Bitcoin as an end user pretty regularly and didn't yet encounter a P2SH address. They certainly have been used, but are they being used regularly? And if someone is using them regularly, would they continue after the payment protocol is available? These things aren't really clear.

We're wandering off-topic, but what does P2SH have to do with the payment protocol?

The payment protocol lets the receiver of funds tell the sender what scriptPubKey they want the payment made too; the protocol doesn't specify what form the scriptPubKey will take other than saying it normally would be a standard Bitcoin transaction script. A merchant could, for instance, choose to provide clients a OP_CHECKMULTISIG scriptPubKey directly for instance, or even something completely non-standard. However any sane client implementation is going to filter out anything other than totally standard transaction formats pubkey, pubkeyhash and P2SH because anything else risks getting your funds stuck while the merchant tries to get the transaction mined.

Overall a P2SH txout adds just 24 bytes to a transaction by the time you spend it. (21 bytes to encode the hash, 2 bytes of opcodes, and 1 byte to encode the length of the scriptPubKey when you eventually spend it) For the minimum size tx format, bare compressed pubkeys, it takes 158 bytes round-trip to create and spend a txout (44 bytes for the txout, 114 bytes to spend the txout) so the overhead of P2SH is just 15% Compared to the standard pay-to-pubkey-hash P2SH is actually 1 byte smaller because it doesn't need the OP_DUP, and it's still just as secure in terms of keeping pubkeys unknown against a ECDSA break.

There's a pretty good chance we'll eventually ban non-P2SH outputs entirely to prevent people from storing data in the UTXO set, possibly with Gregory Maxwell's P2SH^2 proposal. (obviously prunable OP_RETURN outputs would be exempt, and possibly also some type of anyone-can-spend) There are some niche use-cases where knowing the scriptPubKey is prior to spending is important, mainly auditing, but with clever protocols you can make the scriptPubKey be either deterministically generated, or put the required data in an OP_RETURN output in almost every case. We can also add "tearable" data that is temporarily stored in the UTXO set and is guaranteed to be relayed as part of a block, but is removed from the set after some defined time period. Interestingly one way to implement the latter is with time-locked anyone-can-spend outputs with minimum output amounts: with a reasonably large output amount after the time is up a miner will spend them and collect the output as a fee. Time-locked outputs can be done as a soft-fork adding a new instruction and are very useful for Bitcoin sacrifices as well.

[Mike Hearn]

For people reading along, Peter routinely says "we" will do things that he hasn't built any kind of consensus for at all, so I'd take things he writes with a pinch of salt.

I don't have any intention of filtering script types in the bitcoinj implementation of the payment protocol. If a merchant wants to use an exotic script type then it's up to them to get it mined (that's why you can submit transactions directly). I also don't intend to make P2SH used by default, indeed, bitcoinj does not support P2SH transactions at all today and nobody has ever complained. So requiring P2SH transactions is a long way from happening, if it ever happens at all. As pointed out, it imposes "only" a 15% bloat on the block chain.

[klee]

A "soft fork" is a hack. It means miners know about the new rule and other nodes don't, so those nodes can accept blocks that don't follow the new rules, but eventually those blocks will get re-orged away.

I don't personally like soft forks and think we shouldn't use them. The assumption that appearing in the block chain means the transaction is valid (according to everyone) is pretty fundamental. Breaking that by having transactions that are "valid" except that they're not going to actually be accepted by the majority undermines that principle. And so far there haven't been any compelling reasons to do it. P2SH has turned out to not be used so far, even though at the time it was deemed important enough to not want to wait for a scheduled hard fork. ZeroCoin isn't usable for the reasons gmaxwell cited back in May.

There are lots of ways to improve user privacy that don't involve any kind of fork at all - it'd be weird to use a complicated backwards-incompatible scheme before simpler backwards compatible schemes have been implemented.

Problem is that even if 0coin is not the most optimized solution it is the first - if Bitcoin won't adopt ASAP (yesterday) anonymity then 'Houston we have a problem'.

BTC Foundation: WRONG PRIORITIES!

SR was the first market, don't underestimate the need for anonymity. I wouldn't bet for the future of BTC in case D.P. Roberts decides to go with an alt+0coin (whether you rich & famous early adopters like it or not)!

EDIT: Not referring to Mike Hearn in particular!

[Mike Hearn]

It's not the first solution - there are other ways to mix up coins and preserve privacy. ZeroCoin is a very nice piece of work and there are all kinds of uses for advanced cryptography. Unfortunately as pointed out before, zerocoin is not only "not the most optimized", it's so slow as to be unusable. But crypto only ever gets faster. It might become feasible one day.

Until then, there are simpler approaches that can do a job that's nearly as good (or maybe even just as good).

[klee]

It's not the first solution - there are other ways to mix up coins and preserve privacy. ZeroCoin is a very nice piece of work and there are all kinds of uses for advanced cryptography. Unfortunately as pointed out before, zerocoin is not only "not the most optimized", it's so slow as to be unusable. But crypto only ever gets faster. It might become feasible one day.

Until then, there are simpler approaches that can do a job that's nearly as good (or maybe even just as good).

Please DO implement them!!!!  

EDIT: I will donate to your team (I am not rich BTW ) and I am sure many will...

[jdillon]

For people reading along, Peter routinely says "we" will do things that he hasn't built any kind of consensus for at all, so I'd take things he writes with a pinch of salt.

Funny that, I seem to remember Pieter Wuille, Matt Corallo and others arguing with Peter on IRC about P2SH, note how Peter's arguing against:

<sipa> if it were up to me, P2SH would be the only supported way of doing transactions in the first place
<maaku> sipa: agreed
<BlueMatt> sipa: lets make everything but p2sh non-standard in 0.9
<BlueMatt> or...maybe 1.0
<petertodd> sipa: It makes it a lot easier to do auditing in many cases, where OP_CHECKMULTISIG, for example, lets you easily see where funds are even when they're being semi-controlled by others, without requiring extensive communication.

http://bitcoinstats.com/irc/bitcoin-dev/logs/2013/06/03#l7531211

P2SH-only is also on the Bitcoin feature wishlist on the wiki, and Gregory Maxwell argued for it was well when he proposed P2SH^2. It'd probably just take some more child-porn related materials in the blockchain to get OP_CHECKMULTISIG disabled, remember that with it you can easily both insert data and make the txout spendable at the same time so that even if you decide you will blacklist txouts in response you are forced to blacklist spendable txouts and thus take peoples money. That is a much harder problem politically. Great fun could be had by someone creating time-locked announce-commit sacrifices spending those txouts in the future with large fees or to particular people. Do you really want to have a process by which we change the rules for how individual transactions can be spent by a central committee based on evidence that is illegal to examine, and thus illegal for the community at large to admit to auditing? Warning that P2SH and pay-to-script-hash (both are compatible with gmaxwells proposal) may one day be the only legal transaction types is a very reasonable thing to say.

It's what you write is what we need to take with a pinch of salt.

I don't have any intention of filtering script types in the bitcoinj implementation of the payment protocol. If a merchant wants to use an exotic script type then it's up to them to get it mined (that's why you can submit transactions directly). I also don't intend to make P2SH used by default, indeed, bitcoinj does not support P2SH transactions at all today and nobody has ever complained. So requiring P2SH transactions is a long way from happening, if it ever happens at all.

Unless you make stub transactions you will find your users getting their funds locked up because of merchants failing to get the transactions mined for whatever reason. For many merchants there isn't a strong incentive to get a transaction confirmed quickly because they either don't actually incur a cost immediately (shipping) or because anti-double-spend measures are working properly. At least with P2SH if miners do child-pays-for-parent the client can get the transaction mined that way regardless of what crazy scripts the merchant wants to use for txouts in their wallets.

As pointed out, it imposes "only" a 15% bloat on the block chain.

No, as Peter pointed out it is 1 byte more efficient than the pay-to-script-hash method used currently, a method that protects Bitcoin from an ECDSA compromise. The 15% comes from the theoretical minimum transaction size, which creates dangerous risks for Bitcoin as a whole.

Besides, since when did you care about blockchain bloat?

[jl2012]

Overall a P2SH txout adds just 24 bytes to a transaction by the time you spend it. (21 bytes to encode the hash, 2 bytes of opcodes, and 1 byte to encode the length of the scriptPubKey when you eventually spend it) For the minimum size tx format, bare compressed pubkeys, it takes 158 bytes round-trip to create and spend a txout (44 bytes for the txout, 114 bytes to spend the txout) so the overhead of P2SH is just 15% Compared to the standard pay-to-pubkey-hash P2SH is actually 1 byte smaller because it doesn't need the OP_DUP, and it's still just as secure in terms of keeping pubkeys unknown against a ECDSA break.

Isn't pay-to-pubkey-hash (P2PH) more secure than P2SH? Stealing bitcoin from a never-spent P2PH address requires breaking of ECDSA, SHA256, and RIPEMD160 at the same time. For P2SH, one "only" needs to break SHA256 and RIPEMD160 to create a valid serialized pay-to-anyone script, and mine his own blocks before broadcasting it. (I know it's hardly possible to completely break SHA256 and RIPEMD160 at the same time, but theoretically P2PH is still secure than P2SH)

[maaku]

If any one of those is broken, your coins are worthless anyway.

[n8rwJeTt8TrrLKPa55eU]

* >40kbyte signatures (the authors of the paper give some hand wave at a DHT but this doesn't meaningfully solve the problems created by enormous transactions: the parties interested in them and all full nodes must transfer them to validate them)

Looks like they've now excised some of the more obvious low-hanging fat:

RT @imichaelmiers: Good news, with optimizations and more efficient serialization, the #zerocoin spend tx's are 25kb, not 40kb

Still orders of magnitude away, unfortunately.  And further reductions requiring algorithmic breakthroughs will be much harder to come by.  But progress is progress...

[gmaxwell]

Indeed, as I said— it only gets better.

My most recent thinking is that the best way to drive this kind of technology forward would be to implement a joint transaction system that helps people anonymously make group payments to improve fungibility and decrease transaction costs (using the transaction pattern described here)  using libzerocoin for the parties to agree on who gets paid what.

E.g. N parties show up in a communications group and want to make a joint transaction. They each name an input they want to spend and signmessage for a zerocoin creation showing that they have the authority to spend that coin.  They then return anonymously and provide zerocoin spends that specify the outputs they're interested in. Everyone then knows what the final transaction should look like and they all sign.

In this case the zerocoin part is used to prevent parties from jamming up the mix, e.g. by joining and providing inputs but refusing to sign. If someone refuses to sign— it can only be because either zerocoin has been exploited (and their preferred output isn't in the mix) or because they're trying to jam it.  In any case, you just blacklist their input, and restart the process. Because zerocoin is only used for anti-dos in that context it also means that you could use a faster reduced security instance of it, also allowing some experimentation with the security boundaries.

The fact that the data is slow and big is harmless when its only among a small number of participating parties. This avoids a bunch of scalability concerns, it avoids the reorg risk of an altchain, the network risk of a (soft)fork, the complexity of a global scale decentralized consensus algorithm, allows rapid software evolution because only the participating users need compatible software (vs a blockchain which largely sets the software in stone), etc. but it also puts zerocoin in production use.  The downside is the smaller anonymity sets from small near-realtime mixes but thats also a consequence of ratelimiting a chain based zerocoin.