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

CC BY-SA 4.0
2020-01-30T17:58:02.507Z
2022-09-24T17:15:38.680Z
2022-09-24T17:15:38.680Z
Claris
<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>

CC BY-SA 4.0
2020-01-30T19:38:22.417Z
2020-01-30T19:38:22.417Z
Pieter Wuille
<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>

CC BY-SA 4.0
2020-01-30T17:41:54.367Z
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
CC BY-SA 4.0
2020-01-30T17:50:25.630Z
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
CC BY-SA 4.0
2020-01-30T17:53:08.017Z
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
CC BY-SA 4.0
2020-01-30T17:56:51.530Z
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
<schnorr-signatures><quantum-computing><taproot>
Could Taproot create larger security risks or even hinder future protocol adjustments re Quantum threats?
johnsmiththelird
# Could Taproot create larger security risks or even hinder future protocol adjustments re Quantum threats?

(Asked by: username_0 on 2020-01-30)

I am quoting here a user named "blk014" who responded to username_1'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.

**Tags:** schnorr-signatures, quantum-computing, taproot

> **Comments:**
> **username_1**: 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.  
> **username_0**: thx username_1! 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!!  
> **username_1**: 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.  
> **username_1**: 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).  

---

## 2 answers

### Answer by username_1 on 2020-01-30. Score: 5 | Accepted answer

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


---

### Answer by username_2 on 2020-01-30. Score: 4

This particular response is approximately tripe. Building on username_1 username_1'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](https://en.wikipedia.org/wiki/Lamport_signature), which predates even Schnorr in [1991](https://en.wikipedia.org/wiki/Schnorr_signature). 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.


---

