Topic: Zerocoin when? (Read 5028 times)

Wow, that CoinJoin thinger looks really interesting...

Zerocoin was really exciting when I first heard about it, and still is. I love the idea of forking bitcoin to use zerocoin proofs much better than CoinJoin, mainly because the anonymity pool would be larger by orders of magnitude, but sadly I have to agree with the earlier posts pretty much explaining why it can't easily happen (mainly, computation and storage overhead... orders of magnitude more cost for the network)

Thanks for whichever mod switched this post to being its own thread rather than off-topic. I otherwise wouldn't have seen this tangent discussion on whichever thread it was hiding in originally.

Here is CoinJoin, a followup authored by gmaxwell.

Indeed. Although there are simpler ways to hide the connection: e.g. Tor plus blind signatures:  parties provide inputs, get a blind signature from all other parties, reconnect and expose their blindsigned tokens to get into the output list, but they leave open a DOS attack without an even more complicated protocol.  Using ZC solves both the connections problem and gives you anti-DOS, which blind signatures themselves don't provide.

I was working under a (handwave handwave) assumption that the parties would meet over Tor, Bitmessage, or some other anonymity preserving transport.  Practically speaking, a direct usage Zerocoin requires something similar.

I'm not sure about the anonymity set impact, it's a bit hard to reason about. One of the scaling arguments for ZC is that you could use it infrequently for a fairly small set of high value transactions. This has an impact on the anonymity set too.  Because throughput isn't very limited in the joint-transaction case, and because it could potentially piggyback on regular transactions (E.g. I want to donate to Foo, but instead of donating directly I do it via a mix transaction), it should be possible to cascade many stages of mixing and increase the anonymity set size.

The zerocoin part does more than defend against DOS, doesn't it? It also provides a degree of anyonymity, if I understand it. In the conventional multi-party anti-taint protocol, every participant knows the mapping from inputs to outputs. But in your improved protocol using libzerocoin, nobody sees the mapping. Now, this requires more than two participants, so considerable organization is needed to coordinate.

Still, this an application of the zerocoin protocol which doesn't have an impact on the blockchain. OTOH, it has a small anonymity set, so the benefit is rather modest.

I hope next week I will publish my two years late AppeCoin paper. Appecoin is even more anonymous than Zerocoin since it hides the amounts (it doesn't require denominations).

The problem I see with Zerocoin and Appecoin when implemented on Bitcoin is that people trust Bitcoin because it relies in a very simple cryptographic scheme (ECDSA) that is well studied. Any other cryptographic protocol will only weaken the trust on the system.

Do people trust AppeCoin/ZeroCoin source code as much as they trust OpenSSL code ?
I don't think so.

For example, if you break AppeCoin you can create money from thin air, which you cannot do in Bitcoin.

AppeCoin and ZeroCoin are complex protocols, and require much more complex implementations. Trust on complex crypto protocol requires time and review for many years.

Best regards, Sergio
 

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.

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


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

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

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)

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:


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.


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?

Please DO implement them!!!!  

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

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

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!

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.

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.

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

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

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

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.

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

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.

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?

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.

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.

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?