On 12/16/24 6:14 AM, Anthony Towns wrote:
On Sun, Dec 15, 2024 at 04:42:59PM -0500, Matt Corallo wrote:
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.
Some downsides of this approach:
- "OP_SPHINCS" signatures would be very large, at 8kB to 50kB. That
reduces inputs spent per block to a maximum of between 500 and 80,
given the existing constraints on witness data. Compared to bitcoin
blocks today, as I write, tx cf6391ca [0] is targetting the next block
and spends over 600 inputs on its own, while taking up only about 4%
of a block, so this seems like a big limitation. Probably better to
either pick something with much smaller signatures (which probably
means risky cryptographic assumptions, or single-use-pubkeys), or
to increase the block size in one way or another, eg as cryptoquick
proposes [1].
[0] cf6391ca2f3c361b666937fe7ae3e283850c9b81682755b7f5ab64bfd4c9503a
[1] https://github.com/cryptoquick/bips/blob/p2qrh/bip-p2qrh.mediawiki
Sure, of course. The point of this scheme is to provide an *option*. As mentioned in the
assumptions, it assumes that we have a decade or more before this is a pressing issue and thus, in
practice, the funds in these types of scripts will never use OP_SPHINCS. Instead, as PQC improves
over time (or confidence in lattice assumptions increases) other things will be added to replace it,
allowing for wallets in active use to be migrated to something more sensible.
Its intended to avoid the issue of funds that don't move for a decade. If we wait around and only
add PQC five years before its needed that leaves a lot of funds vulnerable to theft, vs if we give
wallets a decade or a decade and a half of time with a PQC option then the total funds vulnerable to
theft could be substantially decreased.
- There's a fair bit of bikeshedding you could do about OP_SPHINCS,
including choosing different parameters for SPHINCS+, different
encoding of pubkeys, different "sighash" selectors for what is to
be signed, and different PQ schemes entirely. Without real quantum
computers to optimise against, many of those variables probably can't
be chosen objectively.
Sure, I'm not sure "its bikeshedable" is a *downside* per se, but yea, either parameters would have
to be fixed with quite some guessing or it'd have to be configurable.
- Adding in secret OP_SPHINCS spend paths prior to an OP_SPHINCS
consensus change being active (or at least locked-in) seems very risky:
- it provides a way for insiders to cause you to lose all your
funds (prior to activation, selling your SPHINCS pubkey to a miner
allows the miner to claim all the funds), with little ability to
do a k-of-n multisig-like approach to prevent a single bad actor
from causing problems
Sure, if you lose your "private key" someone can steal your funds. Indeed, this wouldn't allow for
multisig until/unless OP_SPHINCS were active.
- if the parameters that are actually activated are different to
what you assumed, then your script path might be unspendable
anyway; if different groups are proposing different parameters,
and only one gets activated, their funds are accessible while
everyone else's isn't
Sure, it wouldn't make sense to use such a thing unless you have very strong confidence everyone
else is using the same opcode format.
- Disabling key path taproot spends via soft-fork is extremely
confiscatory -- for the consensus cleanup, we worry about even the
possibility of destroying funds due to transaction patterns never
seen on the network; here, shutting down key path spends would be
knowingly destroying an enormous range of utxos.
Indeed, I think there's a large debate to be had here, and really we can't make such a decision
today. There are a lot of specifica around exactly how a theoretical future QC operates that would
materially change this decision, I think, so I'm not sure how much its really worth debating today.
That said, if there's been two decades of all wallets having a hidden PQC script path it might be an
*option* in a way that just adding a lattice option five years before a QC is available simply would
not offer that option.
Hence it makes sense IMO to spec this out so wallets can use it *today* and we can figure this kinda
stuff out later.
- If you're avoiding the confiscatory approach by adding a hard-fork
in order to make keypath (and potentially ECDSA) funds accessible
to their owners via some post-quantum mechanism, then there's little
benefit to having an explicit script path method in advance.
Strongly disagree with this one. The hard-fork spend-via-future-PQC-proof-of-knowledge approach is
incredibly speculative, likely to require some vaguely sketchy crypto assumptions, and might well
require more on-chain footprint than a hash-based signature. I don't buy that it makes sense to
assume schemes that allow for this will exist in a way that we're happy with. Instead, having
wallets commit to some OP_SPHINCS buys us a lot of optionality, and could even allow for adding an
alternative spend-via-future-PQC-proof-of-knowledge long after "locking" keypath spends.
- This approach probably isn't compatible with smart contracts,
particularly if pre-signed transactions are involved. Probably the
only way to deal with that is to hope you will have enough warning
to say "in X months, all your smart contracts are broken, so shut
them down now". There probably isn't any feasible way to do anything
better than that, though.
Indeed, and I explicitly listed this as an assumption because it seems
incredibly likely to be the case.
(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.
I don't think this paragraph makes sense? In a post-quantum world,
a legitimate key-path spend could likely be replaced by an attacker
while it was sitting in the mempool, same as for a tx spending a p2pkh
or p2wpkh output.
This is very unclear. A lot needs to be figured out about exactly how a theoretical future QC
operates and there may well be some latency to the calculations.
Also, a script-path isn't a point at all, so having
it be a NUMS point doesn't make much sense.
Apologies, I had rewritten this sentence and that was a typo. I'd meant a NUMS
constant, eg a 0-hash.
Having it be unspendable
can make sense, and is already recommended in BIP 341 (search for
"unspendable"). Conditional key-path spends for taproot outputs is
probably most sensibly done as a hard fork; though it could be done as
a soft fork if the "condition" data was added somewhere other than in
the witness.
What about a different way of allowing wallets to pre-commit to a
post-quantum pubkey? eg, rather than generating a pubkey P directly from
an xprv/xpub and committing to a script path with their post-quantum
pubkey Q; wallets could generate the pubkey as R = P+H(P,Q)*G. At that
point, a hard-fork could be made to allow "R CHECKSIG" (or key path spends
where R is the sPK) to be satisfied via "<Qsig> <Q> <P>", validated
by checking that P+H(P,Q)*G=R, and that Qsig is a valid post-quantum
signature based on Q.
That retains many of the drawbacks above and is only useful if enabled
via a hard fork, however it removes these drawbacks:
- insiders can steal your funds if you adopt it prior to it becoming
consensus
I don't see why you consider "if your private key leaks someone can steal your
funds" to be a drawback.
- it marginally increases the size of non-post-quantum spends
- it breaks complicated scripts even without pre-signed transactions
These seem like drawbacks to your scheme.
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+unsubscr...@googlegroups.com.
To view this discussion visit
https://groups.google.com/d/msgid/bitcoindev/07134c47-5d44-446f-8bfb-9438026444cd%40mattcorallo.com.
