Hacker News Reader

Comment by q-base | Hacker News Reader

Could you elaborate on this flaw, or perhaps point to a link - especially with regards to Monero?

Yes, I'm pretty sure that neither Zcash or Monero allow double-spends. Wondering what the context of that statement could possibly be. Any successful cryptocurrency must solve the double-spend problem or there's no value in the ledger at all.

Here's a stack exchange question:

https://monero.stackexchange.com/questions/2158/what-is-mone...

TL;DR Monero requires every transaction input to include a "key image" (an elliptic curve point, looks like a public key). The key image is deterministically constructed from the actual coin being spent, without actually revealing which one it is. So making sure the chain never contains a repeated key image is sufficient to make sure that no coin is ever spent more than once, without actually knowing whether any one specific coin is spent. This is how Monero achieves its inflation/non-cloning guarantee.

(There was a famous double-spending bug in CryptoNote protocols you might have heard about that resulted in limitless inflation. This was because the Ed25519 signature scheme used has a co-factor of 8, a stupid performance "enhancement" that DJB should really re-think. As a result, a given key-image had a 1-in-8 chance of being malleable by adding a point of order 8. It's fixed by checking that the key image is actually contained in the group. These sorts of unexpected consequences are why serious cryptographers don't use co-factors other than 1, or other fiddly tricks that get you small constant implementation gains with risky not well studied trade-offs. This is also why the current push to standardize on DJB designed crypto solutions is borderline insanity. But I digress.)

The mathematics of what zerocash does is wildly different, but it serves essentially the same purpose. Each private/anonymous spend in zerocash has some bits associated with it that are generated in a non-linking way from the input being spent. As long as there are never two transactions in the entire block chain history with the same value for this field, there are no double-spends.

-----

The problem is that these can never go away. In bitcoin if a coin is spent, you can prune knowledge of that coin from your local history. This is what the "-prune" option does in recent versions of Bitcoin Core. You still need to receive and process the transaction once when you sync the chain, but you can then throw it away if you are space constrained. Mimblewimble potentially improves the situation even better by boiling down each transaction to just a single EC point, the script kernel, such that a client needs only the current UTXO set and the full history of all these kernels to do initial sync. The rest of the data can well and truly be forgotten. But although those kernels are needed for initial sync, pruning nodes can throw them away afterwards. They are not needed for the validation of future blocks in any way.

TL;DR: The amount of data a verifier needs to keep around to validate a new block in bitcoin depends only on the number of unspent outputs. The full block chain is only needed for initial sync. This is asymptotically O(current size of bitcoin ecosystem). The amount of data needed by Monero or Zerocash, on the other hand, is (a constant factor of) the entire block chain used by these systems. This is asymptotically O(every transaction ever). Monero and ZCash are chugging along now, but every single block found increases the amount of data a verifier needs to keep around. That doesn't scale....

Thank you very, very much for that long and thorough answer. I need to read it through more thoroughly when I return from work. But sounds like I may need to re-think my holdings of Monero :)

Mimblewimble used properly gets nearly the same benefits that you have in Monero (essentially non interactive coinjoin) but with scaling guarantees better than bitcoin. If it was possible to ring signatures like Monero has without the scaling difficulties, I guarantee you bitcoin developers would be working on it. Friends don’t let friends invest alt coins.

Thanks a lot once more! I need to read that Mimblewimble white paper.

Haha yeah the last sentence came a bit late as I have lost some money on Monero. I may just hold them until they perhaps gets even and then sell. Just liked the philosophy and idea behind. But thanks anyway :)

Doesn't it scale? Isn't it the case that the Merkle tree holding all the shielded coins can be pruned just as easily as the Merkle tree storing Bitcoin transactions? Pruning either tree eliminates the information needed to verify the claimed owner of a coin in a pruned branch, correct?

You can’t get rid of the requirement that this data be kept around. Either you implicitly have the validators keep it, which is what I assumed for simplicity, or you have the spender provide a Merkle proof, the generation of which requires access to that data set that scaled linearly with the entire block chain history. On the face of it this is a bad trade off because signers often need to be low power mobile or tamper resistant devices with limited bandwidth, whereas full validation nodes have access to high powered servers on low latency networks. A middle ground is to have a third party archivist maintain these records and provide proofs for a fee. That’s fine until running one of these becomes beyond the reach of individuals or scrappy organizations, as them you’ve introduced de facto centralized gateways.

This Merkle tree commitment approach is basically what zerocoin and zcash do — except with fancy zero knowledge proofs to achieve full cryptographic anonymity. But to make those proofs you still need the data...

Very good summary of the issue. This is actually a solveable problem. You use a tree of spent serial numbers and non-membership proofs. This basically eliminates the over head to the network of managing serial numbers and checking for double spends. However, it requires they be stored somewhere because some of that data is needed to make non-membership proofs and update the tree. To further reduce it, keep separate serial number data structures per some long epoch and reveal which epoch a coin was create in on spending. Now the burden epochs is only one people with coins in that epoch. For most reasonable scales, epochs can be very very long. Like 10 years.

As an aside, the fact that mimbelwimble does not have this issue should make you wonder just how much privacy it provides.

That doesn’t solve the issue. It just pushes the responsibility of holding all this data onto the signer instead of the validator, which is a free choice. But signers are usually more space constrained than validators.

And there is no connection between privacy guarantees and this issue. I’m not sure what you’re getting at there.

It not holding all the data though. Anyone with old coins has to hold at most 2kb of data. They do have to occasionally (think every 1 to 5 years) scan all spends from that epoch to update that data or get someone to do that on their behalf. But it really does reduce the work.

As to mimblewimble: yes, there is a connection. You are trying to prune provably spent things. But to do that, you must know what was spent. Which means, if I spend a coin with you in Mimblewimble, the set of possible coins it could be is orders of magnitude smaller than the set of coins it could be in zcash or even Monero. Because these don't prune.

How do you "scan all spends from that epoch" with having those spends ("the data")?

You essentialy just said: "It's not holding all the data though, you just have to have all the data." ...?

As I pointed out elsewhere in this thread (see cousin comments) relying an an external 3rd party archival service doesn't solve the issue because either (a) you want the system decentralized so it needs to be within the signer's capability to run such a service, or (b) you don't do that and now you've introduced central points of failure and then what's the point?

So the model is as follows: This network holds the last n blocks (where n is something on the order of months or years.). Spending coins within that time period is unchanged. For every coin outside of those n blocks, the user must hold about 2kb of data per coin. Every n blocks, they must scan the last n blocks before those blocks are discarded to update their state OR rely on a third party archiving service. So if n = 1 year, then oncee a year you must connect to the network and either download the years worth serial numbers from coins outside the current epoch (note that this is much smaller than the years blockchain) or just have a node scan on your behalf given your data.. If you wait longer than a year, then you are out of luck unless you find a copy.

So users must scan the entire block chain to maintain their balance. Note that this is a stronger requirement than bitcoin has! A similar amount of data needs to be synced for on bitcoin to see if the inputs were spent, but not to make a transaction. That's the key difference. There are many applications where it makes sense to have a wallet make spends while checking block data only when it is expecting a confirmation, e.g. because its keys are HSM protected. Vending machines, for example.

Bitcoin has about 2-4k inputs per block. Let's say 3k inputs every 600 seconds. A key image size depends on the crypto being used. A super conservative lower bound on size is 256 bits per key image -- smaller than either Monero or Zcash, I believe -- as general information theory says anything less than that cannot provide 128 bits of security. That's 4GB/yr or 330MB/mo. And again, that's a minimum -- Zcash for example is 9x this number as a theoretical minimum, larger when you add protocol and serialization overhead.

That's a lot of data to suck down a pay-as-you-use-it IoT 3G connection. And that's just at bitcoin's pre-segwit average usage, not even what segwit can do or levels people think bitcoin should eventually be scaled up to. However much bitcoin capacity limits are raised in the future will directly scale up these numbers.

> rely on a third party archiving service

This is not a solution. If you allow scaling to such a degree that third party archiving services are required, then you've centralized the network. Why even use a block chain at that point?

The assumption isn't that the entire blockchain is stored forever, its that users who keep year old coins can 1) receive blocks (either as they are created, or in some batched process where the batch size could be as large as you like up to e.g. 1 year) and 2) store 2k of state per coin. This is weaker assumption than that of a full node in Bitcoin (which stores the entire blockchain)but obviously stronger than an SPV client which doesn't receive blocks.

And remember, this only happens for really old coins. The data from looking at Monero's anonymous Tx's (recall there was a bug that leaked spending history) is that coins are typically spent with in a week. Not just does this mean few users will pay this cost, but the cost will actually be smaller. You don't need the entire block to update the non-memership proof for a given epoch, you only need all the serial numbers from that epoch that were in that block. Thats likely a small fraction of transactions. Zcash serial numbers are 256 bits by the way.

Yes, its a cost. But it is the price you pay for strong privacy. If you can prune transactions, its because you know their outputs have been spent. Which means those outputs don't contribute to your anonymity set.

Reply on news.ycombinator.com