QCAP: A Bitcoin-Native Quantum Canary Alert

Protocol Design
1

Bitcoin’s security depends on the computational hardness of the discrete logarithm problem over elliptic curves (ECDLP). A sufficiently powerful cryptographic relevant quantum computer could easily solve the ECDLP, thus undermining the security assumptions underlying Bitcoin’s current digital signature schemes. Yet the timeline for such breakthrough remains fundamentally uncertain and estimations range from decades to “sooner than we think,” but there is no clear consensus within the field.

Moreover, the core challenge is not only estimating the timeline for such a breakthrough, but the absence of reliable and objective signals of progress. On one hand, markets reward hype, so companies are in that game and governments have incentives to hide their advancements. On the other hand, the technical community has no unified way to measure quantum progress against cryptographic hardness.

The Quantum Canary Address Generation Protocol (QCAP) proposes a practical answer: a Bitcoin taproot address that can only be spent by someone who can solve the discrete logarithm problem on a weaker elliptic curve. The protocol is decentralized, requires no trusted authority, and provides verifiable proofs of correct construction.

QCAP is executed by n participants, where any one of them may act as the coordinator. Each participant contributes a secret value d_i, such that \hat{d} = \sum_{i=1}^{n} d_i remains unknown as long as there exist one honest participant. The coordinator’s role is limited to verifying proofs, aggregating keys, and publishing the canary address.

The Core Idea: Two Curves, One Secret

The core of QCAP lies in a simple observation: we want to publish a challenge on the Bitcoin blockchain that is easier than breaking secp256k1, while remaining natively compatible with Bitcoin’s existing protocol. In practice, this means encoding it into a standard Bitcoin address. The naive approach, publishing a point on a weaker curve like secp192r1, fails because a quantum computer solving it learns nothing about Bitcoin’s curve. As a result, there is no cryptographic link to a standard Bitcoin address. Our approach instead uses the same secret scalar on both curves with the following structure:

  • Bitcoin curve (secp256k1): Publish public key P = \hat{d} \cdot G where \hat{d} is a distributedly computed secret scalar and G is the generator of Bitcoin’s curve.

  • Weaker curve (secp192r1): Publish public key P’ = \hat{d} \cdot G’ where G’ is the generator of the weaker curve.

If \hat{d} is small enough to fit in the scalar field of secp192r1 (which has order n_{192}), then solving ECDLP on the weaker curve reveals \hat{d}, which can immediately be used to spend from the Bitcoin address. The main challenge is designing the key-generation process such that no participant gains a computational or informational advantage over others, while ensuring that the protocol remains secure as long as at least one participant is honest.

Multi-Party Computation of the Shared Secret

QCAP generates \hat{d} using inputs from n different participants:

\hat{d} = d_1 + d_2 + \cdots + d_n \pmod{n_{192}}

Each participant, i, independently:

  • Chooses secret d_i from the weaker curve’s field.
  • Computes its Bitcoin public key: P_i = d_i \cdot G.
  • Computes its weaker curve public key: P’_i = d_i \cdot G’.
  • Publishes (P_i, P’_i).

The protocol’s public keys are then derived by aggregating participants’ public keys:

P = \sum_{i=1}^n P_i = \hat{d} \cdot G
P' = \sum_{i=1}^n P'_i = \hat{d} \cdot G'

As long as a single participant is honest and does not leak his d_i, nobody, not even the coordinator, learns \hat{d}. Even though no single party can obtain the key, a malicious participant may still introduce inconsistencies between the public key on the weaker curve and Bitcoin’s curve. It is therefore necessary to ensure that P and P’ really do share the same secret scalar.

Proving Consistency Across Curves: DLEQAG

The vulnerability: a malicious participant could choose one d_i for P_i and a different d’_i for P’_i. Then P’ would be derived from \hat{d}’ = \sum d’_i \neq \hat{d}, and solving ECDLP on the weaker curve would not reveal the correct secret needed to spend the corresponding Bitcoin output.

QCAP prevents this problem using Discrete Logarithm Equality Across Groups (DLEQAG), a zero-knowledge proof technique from Chase et al. (2022). This proof basically demonstrates that the scalar corresponding to two points (i.e. public keys) on two different curves is equal (without revealing the scalar).

The protocol only aggregates public keys with valid proofs. This prevents any participant from introducing mismatched secrets.

Bitcoin Integration: Taproot and OP_RETURN

Once all participants’ proofs have been verified and public keys have been aggregated into P, the coordinator creates a taproot address from a tweaked public key:

P_t = \text{tweak}(P, D)

where D is a hash commitment to all the protocol data (all participants’ proofs, public keys, and public information).

This serves two purposes:

  • Commits the protocol data to the address itself: anyone can verify the derivation was honest.
  • Enables spending with knowledge of the tweak: a quantum computer that solves the weaker ECDLP and finds \hat{d} can adjust it to account for the tweak and spend the output.

The funding transaction includes an OP_RETURN output linking to all protocol data stored on IPFS:

OP_RETURN <CID of proofs and public keys>

Anyone can:

  • Download the IPFS file using the CID.
  • Verify the cryptographic proofs.
  • Confirm the final address was generated honestly.
  • Check the Bitcoin bounty.

Implementation Notes

This approach is formalized in the research paper “QCAP: A Quantum Canary Address Generation Protocol”, authored by me and my coauthor @nebula-21, under the supervision of our advisors at DISCRYPT research group. A proof of concept implementation is also available, demonstrating that the core mechanics function as intended. For those interested in the deeper technical details or implementation specifics, both are available—but they’re worth reading after understanding the core idea from this post.

A sample of the generated address and corresponding proofs can also be found on testnet as follows:

Transaction on testnet: ebfcee0b5cd1a54f7079dd058d27a6d87316adc42438c6fc05ca64b0234a628c

IPFS link: https://ipfs.io/ipfs/bafybeid356uqgs7mvhotv7mcgfabbk7w7fglg3gctjabcsh47dym7gu2aa

The implementation demonstrates feasibility but isn’t production-ready. There are still several areas for hardening:

  • Decentralized participant coordination (currently out-of-band).
  • Robust network handling for malicious coordinators.
  • Engagement of community members in the QCAP execution.
  • Mainnet deployment and community fundraising.
9 Likes
2

Looks like a pretty solid idea to me, at least, in theory![1].

On the 2022 DLEQAG paper, I noticed when I was researching something similar recently, an MRL note with an algo attributed to Poelstra

The Chase et al Paper focuses on a case of bit length of the secret significantly smaller than the smaller of the two groups, and then offers ways to extend it.

Poelstra’s sort of vanilla-sigma-protocol approach won’t be super efficient, but that is not needed here afaict. While it should work for any value in the order of the smaller group.

(Correct me if some part of that is wrong!)

Another part: you didn’t mention how the multiparty secret generation algorithm will work? I guess there’s a range of slightly different approaches but the template of DKG as in FROST seems to fit well, albeit there is no thresholding here; the point is to have a PoK of the contribution[2], mainly. Maybe if you wanted to get serious, look into powers of tau setup ceremony engineering style considerations so that you could get like 100s to 1000s of free participants.

[1] In practice, I don’t find that canary ideas when it comes to real (and huge) financial risk are very convincing. But one thing’s for sure, they don’t hurt!

[2]To state the obvious, if you just add participants keys together you’re open to key subtraction attacks.

3

There are four elliptic curves, which were generated at the same time, and which have similar properties: secp160k1, secp192k1, secp224k1, and secp256k1. If you calculate half of the generator, then you can see this:

secp160k1:         48ce563f89a0ed9414f5aa28ad0d96d6795f9c62
secp192k1: 0554123b78ce563f89a0ed9414f5aa28ad0d96d6795f9c66
secp224k1:       3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63
secp256k1:       3b78ce563f89a0ed9414f5aa28ad0d96d6795f9c63

Currently, even secp160k1 was still not yet broken, so we probably should start from that. Maybe even there could be more curves, designed specifically as a challenge, for example something like that: curves1000/bits at master · vjudeu/curves1000 · GitHub

Which means, that we could have 128-bit curve, then 129-bit curve, and so on, up to some 255-bit curve.

2 Likes
4

The chosen curve was mainly selected because it has weaker security, and since we were aware that similar curves exist, this one had better support for the proof of concept implementation.

The idea of having multiple canary addresses is a good one and was never discarded. However, there is also the issue of how much the reward would be split. If the idea does not gain enough traction, the canary bounty being split among multiple addresses might not be sufficient to trigger a CRQC.

2 Likes
5

However, there is also the issue of how much the reward would be split.

There are existing N-bit private keys on Bitcoin, for example: mempool - Bitcoin Explorer

However, there are many issues with this setup:

  • Puzzles from 161 to 256 were cleared, and moved to easier unsolved ones, because the author thought, that going beyond 160-bit values doesn’t make sense. But it does, if keys are not hashed, so it was probably a mistake.
  • There is no proof, that private keys are weak. There are many examples, that it is probably the case, but even if the author could attach more proofs, by using weaker curves, he simply couldn’t have enough knowledge to do that.
  • The author can sweep all coins at any time. If you use for example secp160k1, then you know for sure, that all private keys are in range from 1 to 0x100000000000000000001b8fa16dfab9aca16b6b2. And if you have a DLEQ proof, then you know, that the same key is used for a given Bitcoin address. It is mathematically possible to create N-bit puzzles, where everyone would need to solve it, to move them, including the puzzle creator.
  • The progress is not proven trustlessly to everyone, but only to the creator: everyone else has to trust, that the author is not simply sweeping next coins every few months or years, and the actual progress is being made.

So, I think even preparing some code, which would allow attaching proofs for what we have today, would push us at least some steps forward. Because currently, we have just some examples, where people try to solve next puzzles, while heavily trusting the creator, that everything is prepared correctly. Which is far from ideal, but this is what we have here and now.

2 Likes
6

That’s a very interesting point, that : proving in ZK that a given curve point/pubkey/address corresponds to a secret within a fixed range like 1..2^k and then also use a convincing protocol to avoid “the creator knows the key”, are you achieving the same as doing what the OP suggests here, i.e. use a key chosen uniformly from a separate curve of order ~ 2^k and then do a DLEQAG, or is it different?

7

To attempt to answer my own question:

There’s some depth here; at least two questions: is Shor, or a variant of it, in the QC scenario, proportionately easier for smaller discrete logs in 1 group? And: is solving a “small discrete log”, size p, problem on a larger curve the same as solving a general discrete log problem on a smaller curve/group of order p?

For the first question apparently this paper shows an algo that allows you to use Shor/quantum to solve discrete log proportionately more quickly for a shorter discrete log. Apparently there are follow up papers that address cases where the discrete log is shorter but not half as short (i.e. I think that paper only covers where d, the discrete log is less than sqrt(curve order), i.e. half bit length or less; I think later papers more or less generalize the result to larger bit lengths).

For the second question I don’t know, seems a little less clear? If the Ekera algo in the above paper tweaks vanilla Shor, so it’s actually a different algo if admittedly still similar (period finding, aG + bP etc.; I don’t know the details). So is it “the same” to solve a 192 bit secret on secp, as to solve a same-size secret on secp192r1? My guess would be it should be very similar, but strictly not the same.

Given that lack of clarity on the last part, I’m not sure if there’s really much of an argument for using DLEQAG vs just a range proof of the size of the secret; I don’t see what it gains you?

8

is solving a “small discrete log”, size p, problem on a larger curve the same as solving a general discrete log problem on a smaller curve/group of order p?

This is a very interesting question, at the time of writing the proposal our assumption was that quantum computing algorithms for solving the discrete log for a “small discrete log”, with size p, on a larger curve is not the same as solving it for a smaller curve with order p. Having this assumption in mind, it does make sense to provide challenges for different curves with different orders to have challenges with different difficulties.

For the first question apparently this paper shows an algo that allows you to use Shor/quantum to solve discrete log proportionately more quickly for a shorter discrete log. Apparently there are follow up papers that address cases where the discrete log is shorter but not half as short (i.e. I think that paper only covers where d, the discrete log is less than sqrt(curve order), i.e. half bit length or less; I think later papers more or less generalize the result to larger bit lengths).

I just checked the paper and it does seem that the discrete log must be half the bit length of the original order of the curve for their algorithm to work. There are some follow-up papers, this one being the last update. The paper claims to “solve the short DLP in groups of unknown order” with the success probability as high as 1−10^{-10} for any short d. It does need an extra post-processing using classical random-walk algorithms.

Although this seems to be more efficient than the vanilla Shor algorithm, I’m not sure how easier it might be or what the requirements are for the algorithm to “actually” work.

I’ll read the papers more carefully and share a summary in this thread once I understand the details better.

9

Agree with all the above, the creation of these puzzles are completely trusted. This won’t serve in our scenario since the funds being moved from these addresses won’t necessarily signal the arrival of cryptographic relevant quantum computers and could just be the owner moving them.

Other than the points mentioned above, if we assume that solving “smaller discrete logarithms” in a curve with bigger curve order (in our scenario secp256k1) requires the same effort as solving “bigger discrete logarithms” having addresses within a specific smaller range won’t help us. In classical algorithms, we are searching within a range for the solution to discrete logarithm which will cause a smaller range to be easier to search than a bigger one, but that doesn’t necessarily hold for quantum computers (at least not for Shor’s algorithm and not to my knowledge).

As @AdamISZ mentioned, there are some papers suggesting that it could be easier, which I still need to read more carefully to fully understand.