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

user24925: This particular response is approximately tripe. Building on Pieter Wuille'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.

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

92394: <p>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 <strong>"Schnorr's linearity"</strong> can be in the future process of finding quantum resistant solutions? And how possibly mitigate or <strong>prevent this risks in advance?</strong></p>

<blockquote>
  <p>While both, ECDSA as well as Schnorr signatures are unsafe vs quantum
  computers, <strong>Taproot exploits Schnorr's linearity for which no
  quantum-safe replacement is known</strong> today. While making Bitcoin
  quantum-safe is already hard, making Bitcoin-Taproot quantum-safe will
  be a nightmare.</p>
  
  <p>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, ...</p>
  
  <p>what to do with ignorant/dead user that wont upgrade (Satoshi, address
  re-users) whose UTXOs become vulnerable by (1)</p>
  
  <p>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.</p>
  
  <p>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.</p>
  
  <p>On a final note: I'm not personally against activating taproot (it's
  very elegant), but I would also <strong>like to have consensus on a rational
  assessment of the risks that are being accepted here [with Taproot].</strong></p>
</blockquote>

<p>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:</p>

<blockquote>
  <p>I think there are <strong>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 <em>linear</em> PQ-DSA.</strong> Items (1)-(2) have to be
  solved in any case, as long as you believe QCs will become large
  eventually.</p>
  
  <p>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.</p>
  
  <p>it might push the the time to make Bitcoin quantum-secure <strong>from 5-10 to
  10-20 years, as much more research is needed.</strong> Risk assessment should
  conclude whether we have the time and want to take the risk.</p>
</blockquote>

<p>Thanks for your expert views on this issue.</p>
 24925: <p>This particular response is approximately tripe. Building on Pieter Wuille's comment.</p>
<blockquote>
<p>find an appropriate post-quantum DSA</p>
</blockquote>
<p>and</p>
<blockquote>
<p>it might push the the time to make Bitcoin quantum-secure from 5-10 to 10-20 years, as much more research is needed.</p>
</blockquote>
<p>We really know what to do to make Bitcoin Quantum safe, there's been methods for doing hash based cryptography in varying forms since <a href="https://en.wikipedia.org/wiki/Lamport_signature" rel="nofollow noreferrer">1979</a>, which predates even Schnorr in <a href="https://en.wikipedia.org/wiki/Schnorr_signature" rel="nofollow noreferrer">1991</a>. 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).</p>
<p>I personally wrote a patch for adding <code>OP_LAMPORTVERIFY</code> 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.</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>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.</p>
<p>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.</p>
 208: <p><strong>Let me start by addressing the misconceptions in the posts you're quoting.</strong></p>

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

<p>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 <em>simple</em> key aggregation, so that a single key can represent the consent of multiple parties.</p>

<p><strong>So, does starting to rely on Schnorr's linearity make it harder to migrate to PQC signatures?</strong></p>

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

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

<p><strong>Ideally, how would all these features carry over to PQC systems?</strong></p>

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

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

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

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