From: Weikeng Chen <weikeng.chen@l2iterative•com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Trivial QC signatures with clean upgrade path
Date: Sun, 15 Dec 2024 17:30:22 -0800 (PST) [thread overview]
Message-ID: <3b50081e-1a00-4d18-aee3-1cefde230a78n@googlegroups.com> (raw)
In-Reply-To: <52f3bfc0-9446-4400-bf7a-7e38e5777c56@dashjr.org>
[-- Attachment #1.1: Type: text/plain, Size: 8132 bytes --]
I actually think this is a good reason to open OP_CAT because its ability
to do general-purpose covenants allow different parties to experiment their
own PQ signature algorithms before the Bitcoin core settles on one of them
(which I believe would take longer).
OP_CTV does not enable it. It just needs to be a full transaction hash and
the ability to reconstruct it.
If we think we will be able to add QC signatures in 3 years, then we don't
need to do that.
But if we don't think it is easy to settle down on one QC signature, then
it is better to let everyone make their own decisions on PQ solutions.
It is okay to start with some less efficient but provably post-quantum
algorithm, for example, Winternitz signatures in BitVM.
With OP_CAT, the public key can be reduced into a single hash, 32 bytes.
The signature would still be 1KB. This is not too different from other PQ
proposals.
Verifying a Winternitz signature costs about 4KB in Bitcoin script. A major
limitation of Winternitz signatures is that it is one-time, and therefore
the keys need to be protected in a very careful way.
Although this is still expensive and would better be handled by a native
opcode, at least MicroStrategy and institutions as well as many individuals
can move their "long-term" wallet for Bitcoin into PQ ones and provide
enough time for Bitcoin core to decide on a post-quantum algorithm, ideally
when one of them get mainstream adoption (e.g., replaced ECDSA and RSA in
web browsers).
Nevertheless, the major issue right now with PQ is only P2WSH can be
"post-quantum" while P2TR is not post-quantum. It may be necessary to have
a P2TR new version where the key route is removed (script-only) or replaced
with a PQ signature.
On Monday, December 16, 2024 at 8:01:55 AM UTC+8 Luke Dashjr wrote:
> One thing to add: the post-QC script path does not require a softfork to
> commit to, as long as it is well-defined. So wallets could begin
> implementing this fallback immediately, without waiting for _any_
> softfork activation, as soon as the spec is final. They _would_ need to
> guard the post-QC script as if it were itself a private key, which could
> be an issue for hardware wallets - but I suspect there's probably a way
> around that too...
>
> On 12/15/24 4:42 PM, Matt Corallo wrote:
> > There's been a few rough ideas for QC robustness in the signature
> > scheme over Bitcoin transactions over the past many years, but many of
> > them have a number of fairly major drawbacks.
> >
> > First, some base assumptions:
> >
> > (a) QCs that can break EC will take a while (probably closer to a
> > decade or two than a few years). This lines up with NSA and other
> > recommendations. We have time to upgrade, but we might consider having
> > an option today for wallets to get QC security later.
> > (b) Its entirely possible that fundamental scaling constraints will
> > emerge and QCs that break EC simply won't ever be reality. We might
> > not want to bet on this, but its possible.
> > (c) We'll get some reasonable warning before QCs are there - QC
> > development requires immense resources, so much so that only a few
> > organizations in the world can afford to hire the talent required and
> > fund the lab. This type of development has and will likely continue to
> > lead to announcements as progress continues, and we'll have a few
> > years warning as QCs get closer and closer.
> > (d) post-QC security assumptions (like Lattices and obviously
> > Supersingular Elliptic Curve Isogeny) are insufficient to secure coins
> > today, and are bad candidates for inclusion in Bitcoin's consensus due
> > to the likelihood of future cryptography research. This implies the
> > only candidates for post-QC signature security in Bitcoin's consensus
> > today are hash-based signatures (basically SPHINCS/SPHINCS+).
> > (e) its not worth waiting on OP_CAT and the other more general script
> > opcode additions for this, as those seem stuck in bikeshed hell, not
> > to mention questions around MEVil and Bitcoin's future abound.
> > Further, doing this via dedicated opcode simplifies wallet adoption,
> > which is likely to struggle already given the additional workload for
> > wallet developers for no immediate user-facing features.
> >
> >
> > Given these assumptions, it seems ill-advised for wallets today to
> > start locking funds up in a way where they need to pay the on-chain
> > footprint cost to get post-QC security for their transactions *today*,
> > but given upgrade cycles in Bitcoin it also seems ill-advised to not
> > have some option for wallets to have "emergency" paths.
> >
> > Luckily, taproot provides a great way to build such a scheme! Because
> > taproot script-path spends are strongly-bound (the taproot script-path
> > hash t includes the internal key in its hash), a future QC could
> > determine the associated private key and script-path merkle root, but
> > it cannot forge an alternative script-path merkle-root.
> >
> > This provides a compelling hook for post-QC security - with the simple
> > addition of an OP_SPHINCS (or equivalent post-QC non-one-time-use
> > (i.e. not Lamport/Winternitz) signature verification opcode,
> > functioning in much the same was OP_CHECKSIG works today), wallets
> > simply need to construct their taproot outputs to always contain a
> > script-path alternative spending condition. When QCs are becoming a
> > reality, key-path taproot spends could be disabled via soft-fork,
> > forcing spends to be done using the QC-secure path.
> >
> > This scheme obviously has the major drawback of non-upgraded funds
> > confiscation at the time of QC existence, but:
> >
> > (a) we could instead require explicit opt-in for this scheme. This has
> > the drawback of yet another on-chain fingerprint and would require a
> > new scriptPubKey format (but keeping the existing bech32m address
> > format, hopefully most wallets support that without any code changes
> > today). Of course if we do, substantial quantities of Bitcoin which
> > are unlikely to ever be spent could lead to supply shock, severely
> > damaging Bitcoin's utility in other ways,
> > (b) alternatively, we could allow key-path spends for wallets which
> > prove the script-path is a NUMS point (via some new keypath+proof
> > spend variant). I doubt many wallets today bother committing to a NUMS
> > point for their taproot output pubkeys, so this would break existing
> > wallets, but it would allow for an opt-out scheme.
> >
> > This scheme has the incredibly nice property of not bloating existing
> > use-cases nearly at all (just one extra taproot script-path branch,
> > but that's not a huge deal generally).
> >
> > There's a few things to bike-shed on here, though - first of all
> > whether to require opt-in or provide an opt-out and secondly whether
> > to also fail any script-paths that hit an ECDSA signature validation
> > (probably yes?).
> >
> > I assume this has been written up elsewhere but I couldn't find it.
> > Most of this is due to not_nothingmuch, I'm just writing it up here
> > and taking credit for it.
> >
> > This doesn't address the questions around PoW in a post-QC world, of
> > course, but that likely isn't something that can be answered until we
> > see more practical limitations of QCs (eg what is the minimal latency
> > of a QC gate? If its particularly low, can we simply complexify
> > Bitcoin's PoW hash function in order to delay QC results far past when
> > traditional hardware is able to mine a block?)
> >
> > Matt
> >
>
--
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/3b50081e-1a00-4d18-aee3-1cefde230a78n%40googlegroups.com.
[-- Attachment #1.2: Type: text/html, Size: 9266 bytes --]
next prev parent reply other threads:[~2024-12-16 1:33 UTC|newest]
Thread overview: 9+ messages / expand[flat|nested] mbox.gz Atom feed top
2024-12-15 21:42 Matt Corallo
2024-12-15 23:54 ` Luke Dashjr
2024-12-16 1:30 ` Weikeng Chen [this message]
2024-12-16 1:40 ` Matt Corallo
2024-12-16 11:14 ` Anthony Towns
2024-12-16 15:57 ` Matt Corallo
2024-12-16 22:20 ` Tadge Dryja
2024-12-17 5:31 ` 'conduition' via Bitcoin Development Mailing List
2024-12-18 3:29 ` 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=3b50081e-1a00-4d18-aee3-1cefde230a78n@googlegroups.com \
--to=weikeng.chen@l2iterative$(echo .)com \
--cc=bitcoindev@googlegroups.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
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