First I want to express my admiration for the Zcash team (big fan of @daira especially!).
I’ve been studying the anonymity and privacy aspects of Zcash in detail. I apologise as I’m not a cryptography pro, I’m just a really serious user trying to understand it as well as I can. My goal is to be post-quantum private, i.e. not have my transactions publicly traceable or linkable by a quantum computer, based on what we know so far about QC.
If you do it right, Zcash appears to be by far the most private/anonymous cryptocurrency. Way superior to Monero, though I think using both in tandem is smart for current-day OPSEC. (Take advantage of the far bigger anonymity set of Monero in terms of physical transaction traffic per day, to increase resistance to timing analysis attacks, but still use Zcash’s post-quantum zk-SNARK privacy mechanism as the final layer). After much research, I learned Monero is a sitting duck waiting to be completely stripped naked by a quantum computer, probably in our lifetime. Monero feels like a religion, and Zcash closer to science. Smart to exploit both.
Zcash has so much potential, thank you for the upcoming Halo2 improvements like trust-free setup and reference wallets defaulting to shielded tx by default. I understand your adoption incentives to include AML compliance capability, and that’s OK if it’s transparently and solely in the control of end users.
I know perfection doesn’t exist - human-level factors are the final frontier of any OPSEC - but we need better clarification on Zcash’s technical post quantum privacy, and there are alarming observations about it (if @str4d is right in this thread, which would mean @Daira and @Zooko have been wrong in their statements), indicating that fully shielded Zcash is absolutely not (currently) quantum private, because only 1 of the big 3 identifying components of all shielded transactions is so (the sender address).
This is long post so I thought to make this an OP for easier accessibility. Please merge into other thread if you prefer that.
There are contradictions from members of the Zcash team that need clearing up. Comments saying that fully shielded ZEC is inherently quantum private:
@daira, Mar 2016:
[A future] quantum attacker could ... [on the current Zcash protocol blockchain] break the Curve25519-based encryption **(for known addresses)** and obtain past transaction metadata- my emphasis added - is Daira indicating that if shielded addresses are not known, the Curve25519 isn’t vulnerable or relevant to QC attacking? And in same GitHub issue, as indicated by this other discussion, Daira’s further words:
I'd like to reiterate that Zcash as it stands, already is conjectured to be post-quantum forward private **when addresses are kept secret**.(emphasis added)
@daira, Apr 2017:
The overall encryption scheme is post-quantum key-private(Apologies if I’m taking that out of context) but what gives me hope:
If the KDF hides its unknown inputs, then it doesn't reveal any useful information about which pk_enc has been usedAlso see 2019 Daira: Include argument about post-quantum privacy for unknown addresses in the spec · Issue #203 · zcash/zips · GitHub
@str4d, Oct 2018:
They can’t arbitrarily decrypt transactions on the block chain, because what they actually need to do is break the Diffie-Hellman part of the output key derivation, which requires either knowing the address and recovering the private part of the ephemeral public key in each transaction (to then compute DH(pk_d, esk)), or recovering the incoming viewing key from the address (to then compute DH(epk, ivk)).- Is str4d saying that, no matter the type of brute-forcing adversary (quantum or not), the actual, correct ivk correlating to what took place in a transaction can only be derived (AND proved to be such), if the attacker first knows the correct, real zaddr? That would corroborate Daira and Zooko above.
@daira, Sep 2019:
pk_enc varies between diversified addresses for the same ivk[etc.] - is there deniability and not absolute discoverability of original note value / memo contents / recipient address, based on ivk discovery? (It’s extremely low chance if QC stumbles on the actual original values that correspond to the ivk?)
Based on some brief Internet searching of “google’s quantum computer”, 2^88 (ops per second?) seems not much work at all for an attacker - very quantum vulnerable given the progress being made in QC. Maybe I’m wrong about how many physical qubits are actually needed, but Google’s existing quantum computer has 72 physical qubits - I see that 72 qubit QC means 2^72 values at once. (Per second?) So this means Goog’s QC can already crack any shielded ZEC tx’s recipient address, output value, or memo, in just 18 hours (2^88/2^72/60/60)? Hardly the future, this is today.
Perhaps I’m confusing physical qubits with logical qubits, but clearly QC is quickly evolving: IBM now has 127-qubit computer: First quantum computer to pack 100 qubits enters crowded race. Let’s say there’s 1 million shielded ZEC transactions in the pools. It only takes 4 minutes for a 100-qubit computer to unmask the entire Zcash shielded pools’ output amounts, recipient addresses, and any actual memos inputted into the memo fields (
1,000,000*2^88/2^100/60 = 4.07). Or if there’s a second extra step to do, or a third, or six more, you sill get the point: it’s only another 4 mins of crunching on top of that. 1000 qubit QCs are planned in next few years. Maybe we should even be scared about AES-256, they say it only needs a million physical qubits to crack it. 1000 x 1000 doesn’t seem too far.
(Indeed, an existing classical supercomputer right now can already do 537 petaFLOPs, i.e. 537 quadrillion ops per second. To perform 2^88 ops only takes 18 years.
(2^88/(537*10^15)/60/60/24/365) ) Shouldn’t key lengths be longer in any case? But because of current QCs like IBM, I am very, very concerned if my calculation assumptions above are correct.
Output values alone (and I assume ‘action’ values in Orchard) being unmaskable by an existing QC is a major and retroactive deanonymisation of Sprout and Sapling (and I assume Orchard) shielded pools. Not only can analysis map out plausible links between many or most transactions in general, but transactions early on in a shielded pool’s launch are especially linkable, even more so than just from the fact that not many transactions will have happened in time yet. If str4d is right, we already have amounts known to powerful adversaries. Can’t we already buy quantum computes on the cloud? When will Chainalysis do that?
So this matter is really important to get to the bottom of. Can Daira and str4d clarify? Even in 2017 @str4d seemed to be disagreeing with @daira about ZEC’s inherent PQ privacy. Who’s correct? QCs are here already.
Also: no amount of off-chain / out-of-band / inherently quantum-secure note transferring (1, 2) would improve PQ anonymity/untraceability, in fact it would probably make it worse. Such modified transactions would stand out from all other (regular) tx unmasked by a QC, and thus be highly linkable. They might be extremely private in terms of having certain impenetrable, quantum-resistant ciphertexts (which is cool for certain uses - likewise one could AES-256 pre-encrypt the text placed inside a ZEC memo - fun and cool!), but unless many people are doing similar modified note tx’ing, and in the exact same way, unlinkability/financial privacy relating to those transactions/zaddrs is severely reduced. No one should trust a potential anonymity set whose size they can’t verify.
At least we can publicly see how big the fully shielded ZEC pool currently is (casually check at https://zcha.in/statistics/usage). It’s about 100 per day right now. I can live with that using certain Zcash churning practices, even with a future quantum unmasking of receiver addresses and note output/action values.
But I hope we don’t have to do that! So clarification is appreciated, please. Thank you for your time.
PS. if str4d is right, then why isn’t the sender address/input note also vulnerable to quantum extraction (or indeed other non-zk-hashed values)?
PPS. do these findings show that some aspects should be tightened generally, and quantum privacy/security should be strongly prioritised for the next version, given the advancement of QC? Zcash should lead the way (QRL seems not to have enough support), it would make waves in crypto world and build on the trustless fix with Halo2. I want to see many move from Monero to Zcash in next two years. The long journey pays off!