From: "'conduition' via Bitcoin Development Mailing List" <bitcoindev@googlegroups.com>
To: waxwing/ AdamISZ <ekaggata@gmail.com>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Giving teeth to expected EC disabling: P2XX(-T)(-ML)
Date: Fri, 14 Aug 2026 18:33:14 +0000 [thread overview]
Message-ID: <wftCzgJs2k7H-4R22EOqdOhhXYdFPFhSZhsYHvlzejpJ5emoze0ACgL3rrYiTP-X5QQMpThdRW1cO7mr9IQvs2C4MHxSD2eu_gPFGv-yZs8=@proton.me> (raw)
In-Reply-To: <f6d78499-d551-45ea-89b1-2b9cbd52f5can@googlegroups.com>
[-- Attachment #1.1.1: Type: text/plain, Size: 18178 bytes --]
> An obvious question to raise: would we consider tripwiring a 192 bit group break of a similar type (NUMS)? I find that ... plausible?
A 192-bit curve i think should be reasonable as a canary, but consider this: If someone already has a QC that breaks 192-bit ECC, how long until they build one which breaks 256-bit ECC? A day, a week, a year? No way of knowing. If the delay is too long, users may see the canary as a false-positive, and migrate back to vulnerable addresses, and they might even be right. 192-bit canaries are vulnerable to classical attack with work approximately 2^96. We should bear in mind the possibility that such a canary could be activated possibly very early, well before Q-day, possibly even in the absence of any quantum computers.
Ideally we want a short gap between "192-bit is broken" and "256-bit is broken", but not so short as to make the 192-bit canary effectively fungible with a 256-bit canary (because then it's less likely to be activated before theft occurs).
> w.r.t. 'This guarantees that the NUMS point cannot predate G' yes based on SHA2 preimage resistance, but: isn't the real point that we're relying on SHA-2 not being a naughty function so that you couldn't find G = a * B and SHA2(G) = b*B for some base B in some feasible computation (sans CQRC of course, as was likely back then!). I have no idea what precise name you give to that property. OK, this is a ridiculous thing to discuss, perhaps, given when SHA2 and secp256k1 were standardized :) And given the encoding choices for our BIP341 NUMS (iirc the same as for Elements back in the day? using uncompressed encoding?) were able to be counted on the fingers of the hand which the sleeve does not cover :)
Anyone can find `G = a * B`. Just generate a key and invert your secret key.
`P = a * G`
G = a**-1 * P
The hard part is then finding some b such that `b*G = SHA256(G).`
---------
If we reflect on the requirement that `G` is fixed, we see `SHA256(G)` is also fixed as a pseudorandom challenge point. The reason for using SHA256 instead of, say, picking an arbitary point by committee or using digits of pi or some other trickery, is that hash outputs are supposed to be random and so `SHA256(G)` is (assumably) a random ECDLP challenge. This matches the classical definition of ECDLP more tightly: Given an arbitrary point `P`, find `p` such that `P = p * G`. The assumption is that if an attacker can factor an honestly-sampled challenge point, they can factor any point. SHA256 is just a stand-in for the "honestly-sampled" part.
However, the following two tasks are actually very different:
1. Given G, find scalar `a` such that `a*G = lift_x(SHA256(G))`.
2. Given G, find scalar `a` and message `m` such that `a*G = lift_x(SHA256(m))`.
In the case of task 1, if we assume SHA256 output is random, then this is more tightly equivalent to ECDLP, because the point we're trying to factor is a fixed target, as is the one sampled honestly by the ECDLP security game.
In the case of task 2, the attacker can sample arbitrary messages to create multiple target points, and the attacker wins if they succeed in factoring any of them. The attacker can attack all those target points concurrently if they want, and they get a speedup from doing so.
So I believe it is worth disambiguating canaries between the two cases, because they are different security notions. The first (1) I would call single-target ECDLP (ST-ECDLP), and the second (2) I would call multi-target ECDLP (MT-ECDLP).
It's pretty clear that MT-ECDLP is easier to break, because attackers can make progress against more than one target concurrently, and breaking any one is sufficient to win the security game.
For example, say I sample 2 different messages `m1` and `m2`, and compute ECDLP target points `T1 = lift_x(SHA256(m1))` and `T2 = lift_x(SHA256(m2))`. Then if I sample a random scalar `r` and compute `R = r*G`, I have two potential chances of success: `R == T1` OR `R == T2`. I can scale up this advantage by generating more targets, `T3`, `T4`, ... and so on.
MT-ECDLP also admits a more efficient basic unit of computation in brute force attacks (including Grover) by using hashes instead of EC point multiplications. If I instead start by picking scalar `t` and fix the target point `T = t*G`, then I can run a brute-force preimage search on SHA256 until I find `m` such that `SHA256(m) == x(T)`. This can also be scaled up using a multi-target attack [1].
With ST-ECDLP, we have only a single fixed message `m = G`, and so the attacker can't use those multi-target cheat codes. They can parallelize, use pollard-rho or Shor or other algorithms, but they have only a single target point that they must break to win the game.
The method Pieter suggested using for the canary construction is equivalent to single-target ECDLP.
I've heard others (e.g. Tadge in this thread) previously suggest using a script like `OP_SHA256 OP_CHECKSIG` as a canary, where any spend of such a script would trigger the canary. This would be multi-target ECDLP.
I'm not sure which is better.
- ST-ECDLP is less likely to be triggered early or mistakenly, and is more tightly equivalent to ECDLP.
- MT-ECDLP is more reflective of how real-world attackers behave on Bitcoin (e.g. with thousands-to-millions of public keys available to attack in parallel, and breaking even one is considered unacceptable).
I'm slightly leanings towards a construction like Pieter's, featuring ST-ECDLP, just because I'm not sure what other tricks could be used to potentially trigger MT-ECDLP classically or quantumly.
We could also engineer a compromise between the two, where we limit the number of targets. For example, define the game like this:
Given `G`, find scalar `a` and 32-bit integer `i` such that `a*G = lift_x(SHA256(G || i))`.
Then the adversary can only attack against at most 2^32 unique target points, and those targets are fixed forever, for any adversary. This is an easier problem than ST-ECDLP, but harder than MT-ECDLP. Maybe call it limited multi-target ECDLP (LMT-ECDLP)?
regards,
conduition
[1]: First, generate a bunch of target points. Sample scalar `t` and compute `T0 = t * G`, T1 = T0 + T0, and T2 = T1 + T1, and T3 = T2 + T2, etc. Why double each point? point doubling is cheaper than addition or multiplication, and still covers the whole curve. Then we run a multi-target SHA256 preimage search over all targets [x(T0), x(T1), x(T2), x(T3), ...]. If we have n targets and curve order N, then each message hash has an `n/N` chance of success. If we find a valid message `m`, such that `SHA256(m) == x(R_i)` for some target index `i`, then we have found `T_i = t * 2**i * G = lift_x(SHA256(m))`.
On Thursday, August 13th, 2026 at 2:02 AM, waxwing/ AdamISZ <ekaggata@gmail.com> wrote:
> This tripwire idea is interesting. Basically "canary in consensus".
> I agree it's valuable. In the scenario of adversarial actor(s) gaining access to CQRC first, i.e. no whitehats, only blackhats, obviously nothing to discuss; touching a NUMS ECDL is the last thing they'll do. So I'm slightly worried that the general userbase will not notice that point, instead thinking it's a solid defense when it ... depends.
>
> In the scenario of at least some whitehats, we get wires tripped, or canaries singing. Having it in consensus is nice. The blockchain then does its job of being an unambiguous signal and we can have all the arguments well ahead of time. [1]
>
> On the other hand, we traditionally design such systems adversarially, right, so you could argue that an overfocus on this might be suboptimal - it might be better to do other things.
>
> (Similar comment applies to the 'smaller group canary' - definitely nothing wrong with it, but it is not in itself a defence unless we strongly believe whitehats, and *active* whitehats at that, are keeping up). An obvious question to raise: would we consider tripwiring a 192 bit group break of a similar type (NUMS)? I find that ... plausible?
> > The BIP341 NUMS point (which I suggest using in this context) is the point whose X coordinate is the SHA256 hash of the generator point G. This guarantees that the NUMS point cannot predate G (if it did, it would be possible in theory that secp256k1's designers actually chose G in function of what we call that NUMS point, giving it a DLP known to them).
>
> w.r.t. 'This guarantees that the NUMS point cannot predate G' yes based on SHA2 preimage resistance, but: isn't the real point that we're relying on SHA-2 not being a naughty function so that you couldn't find G = a * B and SHA2(G) = b*B for some base B in some feasible computation (sans CQRC of course, as was likely back then!). I have no idea what precise name you give to that property. OK, this is a ridiculous thing to discuss, perhaps, given when SHA2 and secp256k1 were standardized :) And given the encoding choices for our BIP341 NUMS (iirc the same as for Elements back in the day? using uncompressed encoding?) were able to be counted on the fingers of the hand which the sleeve does not cover :)
>
> [1] I take Antoine's point that making it consensus means the miners are involved and there is a non-trivial collusion risk if the stakes are high, but I can't see how this scenario is *worse* than no tripwire?
>
> On Sunday, July 5, 2026 at 4:07:33 PM UTC-6 Antoine Riard wrote:
>
> > Hi Pieter,
> >
> > Thanks for the observations.
> >
> > When I was saying there is a problem with the game theory,
> > it's that strikingly, any activation of the tripwire logic
> > would rely on a "flag" transaction being mined in the chain
> > for the network nodes starting to enforce at the block N or
> > N+1 or whatever the EC disabling threshold.
> >
> > Any "flag" transaction can be itself re-orged out of the chain
> > to purely disable the effects of the EC disabling threshold,
> > therefore make it null and void as an effect. One might see
> > it as a competing race between a group of "sunsetting" users
> > and a (majority) coalition of miners in coordination with a
> > CRQC adversary, where the latter have an interest and the
> > hashrate capabilities to do a tx-withold [0].
> >
> > In pure terms of satoshi fee denominated calculus, empirically
> > global miners have won an average of $20 B yearly. If we only
> > consider that P2PK are going to be frozen by the tripwire effect,
> > as for most of them it might be assumed they will never move to
> > a safer format, we talk already about 1.7 M of coins or as of
> > today valuation $107 B (the information is on the chain and can
> > be verified).
> >
> > That's $107B can "burn" in revenue or income that a CRQC-enabled
> > miners coalition to constantly reorg-out the "flag" tx out of the
> > chain. In other terms, something like 5 years of income, and I
> > kindly do not count all the loss coins that are likely to amount
> > to a far bigger "tripwire" neutralization budget.
> >
> > In the name of what a majority of miners will gracefully let on
> > the table an opportunity of massive income ?
> >
> > Leveraging Shor the exploitation might be even done anonymously
> > as the mining process is done. Not even certainty, by who the
> > EC-protected coins could be covertly exfiltrated.
> >
> > That's the most striking problem when you think about the math
> > with any "tripwire" approach, or even an "hourglass" one relying
> > on a "flag" transaction [1]. I'm ruling out "checkpoints" and
> > any other trust-the-dev approach, as that's even worst [2].
> >
> > As you're introducing post is resounding, what the miners
> > are saying now, there are no guarantees on how they would use
> > their hashrate down the road, potentially 10 or 20 years from now.
> >
> > Beyond, and to answer back your point, I still think you can
> > manage an escape hatch of the "tripwire" effect, it's all depends
> > how the script tripwire logic is implemented, but if you have
> > two OP_SUCCESS of different kinds before your EC CHECKSIG, you
> > can always have a "soft-fork" after the "tripwire" to return
> > true on the stack, with an EC or hashlock as a success (I agree
> > using undefined op_success in a script is not safe at all) [3].
> >
> > Best,
> > Antoine
> > OTS hash: 4bc91d8dee1625f6e78b27c88bced8e405f25ef6d3d8fd59be8016db5b0fbe66
> >
> > [0] See naumenkog's https://www.bitmex.com/blog/txwithhold-smart-contracts
> > [1] This is sad, as the "hourglass" depending how the parameters are chosen
> > was a more acceptable trade-off than pure sunsetting.
> > [2] Given the amounts at stake to sunset, as a group of developers you
> > would just paint yourself a target, there are more even funds at stake
> > that Satoshi herself / himself is assumed to have.
> > [3] There is no security proof in BIP341 on the unforgeability of the
> > NUMS point, if it binds in the ROM or whatever.
> >
> >
> > Le sam. 4 juil. 2026 à 13:47, Sjors Provoost <sj...@sprovoost.nl> a écrit :
> >
> > >
> > >
> > > On Fri, Jul 3, 2026, at 23:23, Pieter Wuille wrote:
> > >
> > > [...]
> > >
> > > > * Just publishing the DLP in a transaction (e.g. OP_RETURN with a
> > > > specific marker). This is smaller than a full transaction input +
> > > > signature.
> > > >
> > > > * Similarly, but publishing in the coinbase, and requiring relay using
> > > > a separate message. Less places a node needs to check, but I'm
> > > > concerned about the difficulty of testing infrastructure that relay of
> > > > such a message works
> > >
> > > [...]
> > >
> > > >
> > > > On Saturday, June 27th, 2026 at 12:33 AM, Anthony Towns
> > > > <a...@erisian.com.au> wrote:
> > > >
> > > >> A slight variant of this approach would be to have a 128 byte value "aRsm", such that P = N+a*G, N is the BIP-341 NUMS point, and Rs is a BIP340 signature of m by P. That would allow the victim of post-quantum theft via a key-path spend of a BIP341 NUMS IPK to trigger the tripwire, in addition to someone who has direct access to a CRQC.
> > > >
> > > > Indeed, I had considered something similar, but see above for why I'm
> > > > not convinced supporting non-cooperative CRQCs is that useful.
> > > >
> > > > Also, in my view the tripwire isn't really a security feature on itself
> > > > (it's not expected to trigger...), but more something that sets
> > > > expectations around the output type for prospective users.
> > > >
> > > > In that sense, the question is really whether supporting
> > > > non-cooperative CRQCs helps set that expectation more than only
> > > > cooperative ones, which are definitely easier to support.
> > > >
> > > >> I think it could make sense to have the tripwire be included in the block via the coinbase witness commitment output, rather than having it be locked to a transaction, so you only having to check the coinbase for the magic rather than every transaction. That would require a separate P2P message to relay the necessary ECDL-break proof to miners, and would probably need stratumv2 or a getblocktemplate update in order for the node to be able to tell pools to actually include that info in the coinbase.
> > > >
> > > > I worry this is untestable, really. You'd need things like
> > > > fake-tripwires to be supported through the same message which don't
> > > > require an ECDLP break, and still propagate. And then that needs DoS
> > > > protection measures,
> > >
> > > I whipped something up last weekend:
> > > https://github.com/Sjors/bitcoin/pull/121
> > >
> > > It seems straightforward, but maybe I missed something:
> > > - for test code we use a fake NUMS point, so we can generate "proof" without a quantum computer
> > > - a p2p message floods the proof
> > > - nodes ignore the message if they already have *any* valid proof
> > > - verifying p2p proof candidates might need some rate limiting, but it's as cheap as verifying a transaction signature
> > > - mining code includes the proof in a coinbase op_return, until the freeze activates
> > > - with stratum v2 (and ipc mining clients in general this works out of the box, a small change is needed for getblocktemplate clients)
> > > - since the proof is not in the header, we can't use the normal bip9 style header scan to see if the rule activated. Instead the prototype stores it in a file along with a merkle inclusion proof, which is read when the node restarts.
> > >
> > > With this mechanism it doesn't really need to be in the coinbase transaction, but that does seem more convenient and miners can censor it anyway.
> > >
> > > - Sjors
> >
> > > --
> > > You received this message because you are subscribed to a topic in the Google Groups "Bitcoin Development Mailing List" group.
> > > To unsubscribe from this topic, visit https://groups.google.com/d/topic/bitcoindev/aWYtPLVPZ3U/unsubscribe.
> > > To unsubscribe from this group and all its topics, send an email to bitcoindev+...@googlegroups.com.
> > > To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/002f2395-7d5d-4cb6-852c-e991aa1f0eb3%40app.fastmail.com.
>
> --
> You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/f6d78499-d551-45ea-89b1-2b9cbd52f5can%40googlegroups.com.
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/wftCzgJs2k7H-4R22EOqdOhhXYdFPFhSZhsYHvlzejpJ5emoze0ACgL3rrYiTP-X5QQMpThdRW1cO7mr9IQvs2C4MHxSD2eu_gPFGv-yZs8%3D%40proton.me.
[-- Attachment #1.1.2.1: Type: text/html, Size: 26286 bytes --]
[-- Attachment #1.2: publickey - conduition@proton.me - 0x474891AD.asc --]
[-- Type: application/pgp-keys, Size: 649 bytes --]
[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 343 bytes --]
next prev parent reply other threads:[~2026-08-14 18:35 UTC|newest]
Thread overview: 12+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-06-25 17:42 [bitcoindev] Giving teeth to expected EC disabling: P2XX(-T)(-ML) Pieter Wuille
2026-06-26 3:40 ` Nagaev Boris
2026-06-26 11:06 ` Sjors Provoost
2026-06-26 14:10 ` Pieter Wuille
2026-06-26 18:20 ` 'conduition' via Bitcoin Development Mailing List
2026-07-03 21:23 ` Pieter Wuille
2026-07-04 11:57 ` Sjors Provoost
2026-07-05 21:55 ` Antoine Riard
2026-08-13 3:28 ` waxwing/ AdamISZ
2026-08-14 18:33 ` 'conduition' via Bitcoin Development Mailing List [this message]
2026-06-27 4:33 ` Anthony Towns
2026-06-29 2:17 ` Antoine Riard
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to='wftCzgJs2k7H-4R22EOqdOhhXYdFPFhSZhsYHvlzejpJ5emoze0ACgL3rrYiTP-X5QQMpThdRW1cO7mr9IQvs2C4MHxSD2eu_gPFGv-yZs8=@proton.me' \
--to=bitcoindev@googlegroups.com \
--cc=conduition@proton.me \
--cc=ekaggata@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox