2

I am quoting here a user named "blk014" who responded to Pieter's Taproot tweets from 24JAN. I find this user's comments very interesting and would like to ask a developer expert how much of a security issue this "Schnorr's linearity" can be in the future process of finding quantum resistant solutions? And how possibly mitigate or prevent this risks in advance?

While both, ECDSA as well as Schnorr signatures are unsafe vs quantum computers, Taproot exploits Schnorr's linearity for which no quantum-safe replacement is known today. While making Bitcoin quantum-safe is already hard, making Bitcoin-Taproot quantum-safe will be a nightmare.

Enabling taproot now should be supported by a rational risk assessment. The outcome depends on your choice of the following parameters: (1) time until QCs break ECC (2) time until QC-safe taproot replacement developed+vetted (3) time to upgrade network, ...

what to do with ignorant/dead user that wont upgrade (Satoshi, address re-users) whose UTXOs become vulnerable by (1)

Given these risks, an upgrade to tap root is not very risk averse, which is the appropriate approach in developing safety-critical systems, and which was followed so far.

It's not just a matter of priorities, because without taproot achieving QC-safety is hard, but a path is at least on the horizon (cf. current NIST standardization efforts). After taproot, the problem is completely open.

On a final note: I'm not personally against activating taproot (it's very elegant), but I would also like to have consensus on a rational assessment of the risks that are being accepted here [with Taproot].

The user goes on to describe 3 step approach to a solution, where without Taproot only 2 steps would be needed. But with Taproot a much more difficult 3rd step comes into play:

I think there are 3 major QC problems to solve: (1) find an appropriate post-quantum DSA (2) solve the transition problem before QCs become large, (3) find a linear PQ-DSA. Items (1)-(2) have to be solved in any case, as long as you believe QCs will become large eventually.

And Goolge's recent Quantum Supremacy experiment is significant evidence that we are on that track. With taproot activated, we also need to solve (3). If we solve (1) and (3) together, this may take too long to achieve (2). That's the risk we take by activating taproot now.

it might push the the time to make Bitcoin quantum-secure from 5-10 to 10-20 years, as much more research is needed. Risk assessment should conclude whether we have the time and want to take the risk.

Thanks for your expert views on this issue.

  • 2
    I have a hard time answering this because it contains so many misconceptions. DSA is inherently vulnerable to quantum computers, linearity is not the problem, "linear DSA" makes no sense to me - DSA doesn't have the linearity property, and a solution for all these problems exists in the form of post-quantum zero-knowledge proofs ... they're just really big for now, so not really usable. – Pieter Wuille Jan 30 at 17:41
  • thx Pieter! this sounds very confident from you! but since I have literally no clue, the other user's arguments sounded equally confident. But nice to hear there are solutions in your mind. i did not know that zk proofs can be used for QC resistancy. If this is the case, maybe another zk proof concept called "ZK-Starks" could also be of help. Or a concept called "trustless recursive zk-proofs" developed by the Zcash team, its called "HALO". They claim "small proof sizes". Maybe interesting when your main problem is "big for now". Good luck tackling QC!! – johnsmiththelird Jan 30 at 17:50
  • There are dozens of zero-knowledge proof systems being developed (the field has really exploded the past few years), and some of them (including zkSTARKs) can be made PQC. However, all the ones that can have very large proof sizes. The compact ones (like Bulletproofs, Halo, ...) cannot be PQC. – Pieter Wuille Jan 30 at 17:53
  • And I'm not sure confidence is the right word. I don't think we have PQC solutions for Bitcoin with acceptable tradeoffs right now, but QC that can break cryptography are also not a real threat (it's unclear if the engineering challenges can be overcome at all, and if they do, we'll likely see them coming decades in advance). – Pieter Wuille Jan 30 at 17:56
3

Let me start by addressing the misconceptions in the posts you're quoting.

DSA (and Schnorr) are inherently based on the discrete logarithm problem, which is vulnerable to (sufficiently powerful) quantum computers. As a result, there is no such thing as a "post-quantum DSA". DSA also doesn't have Schnorr's linearity property - if "linear DSA" means anything it would just be a weird way to refer to Schnorr (DSA is a modification of Schnorr that was intended to circumvent his patent). There do exist digital signature schemes that are (plausibly) post-quantum secure, but they are not based on the discrete logarithm problem, and they're generally very large.

Another misconception is that Taproot relies on Schnorr's linearity. It does not - Taproot could be built using ECDSA as well; it would just be much less useful. The linearity property is needed for simple key aggregation, so that a single key can represent the consent of multiple parties.

So, does starting to rely on Schnorr's linearity make it harder to migrate to PQC signatures?

Linearity is just used as a tool to increase the privacy (and efficiency) of Bitcoin's scripting system without changing much. However, linear signatures aren't the only way those abstract goals can be reached. A PQC replacement wouldn't try to shoehorn the properties of Schnorr in another signature scheme - it'd just be built for private multisignatures (or more) in the first place. If such a scheme cannot be found, we'd just lose those privacy advantages (efficiency gains would generally not translate anyway), and not be worse off than if we never adopted Schnorr/Taproot in the first place.

There are obstacles though to doing so that are unrelated to Schnorr/Taproot. Probably the biggest one is how key derivation works today. PCQ signature schemes don't have anything similar to BIP32, and it's nontrivial to carry over much of the infrastructure that exists today around key generation (xpubs, derivation paths, PSBT, hardware wallets, ...). I suspect this will be a far harder problem to address than the constructions Taproot permits on a script-by-script basis.

Ideally, how would all these features carry over to PQC systems?

Before answering that, let me point out that in many ways, Schnorr/Taproot are just one step towards hiding a few things from scripts. It only brings advantages when outputs can be spent by a single party or cooperatively by many. In an ideal world, they'd be replaced with a zero-knowledge proof that whatever properties the receiver of a coin wanted to encumber their storage with, was satisfied when spending it, without revealing anything else.

Once you look at the problem this way, it becomes clear that what we need is in fact a zero-knowledge proof, not a signature. A signature is restricted to a single party proving something to a single verifier, who knows what they want. This isn't what we need: generally multiple parties are involved, and the verifiers (full nodes that enforce consensus rules) do not actually care about what policy was fulfilled - only that it matches the policy set by the coin's owner.

Zero-knowledge proof systems exist that could do this (to smaller or larger extent) today, though they come with performance/size tradeoffs or security assumptions that may be hard for the ecosystem to adopt right now. However, this domain of science has progressed enormously the past few years, and I expect it will keep doing so.

Back to PQC, some of these zero-knowledge proof schemes can be made PQC. Like PQC signature schemes, they're generally large (even more so than signatures), but improvements are being made. For QC, we're speaking about events that are likely decades away (or won't happen at all), and a lot can happen in such amounts of time.

| improve this answer | |
4

This particular response is approximately tripe. Building on Pieter Wullie's comment.

find an appropriate post-quantum DSA

and

it might push the the time to make Bitcoin quantum-secure from 5-10 to 10-20 years, as much more research is needed.

We really know what to do to make Bitcoin Quantum safe, there's been methods for doing hash based cryptography in varying forms since 1979, which predates even Schnorr in 1991. Adding a new signature type to Bitcoin can be done with a soft fork, even though the specifics of how this would work (they would likely be a merkle tree of public keys).

I personally wrote a patch for adding OP_LAMPORTVERIFY as a project while bored on a plane in 2015, other than coming up with something sensible for the formats and desperately trying to convince people not to re-use addresses (for real this time!), it's engineering that can be done on a short international flight.

With taproot activated, we also need to solve (3). If we solve (1) and (3) together, this may take too long to achieve (2). That's the risk we take by activating taproot now.

The two are basically orthogonal, there's no difference between migrating between outputs stored with taproot and those using raw ECDSA. The existence of taproot doesn't make this any more or less difficult functionally.

If any quantum computing was a significant threat (ie, wasn't just theoretical or slower than classical computing), we would have a lot more to worry about than just Bitcoin regardless.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.