Delivery-date: Mon, 16 Dec 2024 04:35:54 -0800
Sender: bitcoindev@googlegroups.com
Received-SPF: pass (google.com: domain of aj@erisian.com.au designates 172.104.61.193 as permitted sender) client-ip=172.104.61.193;
Date: Mon, 16 Dec 2024 21:14:28 +1000
From: Anthony Towns <aj@erisian.com.au>
To: Matt Corallo <lf-lists@mattcorallo.com>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Subject: Re: [bitcoindev] Trivial QC signatures with clean upgrade path
Message-ID: <Z2ALlBGIyZLVbfVG@erisian.com.au>
References: <c2684826-6c93-419b-9a96-c0f0a791c9ac@mattcorallo.com>
MIME-Version: 1.0
Content-Type: text/plain; charset="UTF-8"
Content-Disposition: inline
In-Reply-To: <c2684826-6c93-419b-9a96-c0f0a791c9ac@mattcorallo.com>
X-Spam_score: -0.0
X-Spam_bar: /
X-Original-Sender: aj@erisian.com.au
X-Original-Authentication-Results: gmr-mx.google.com;       spf=pass
 (google.com: domain of aj@erisian.com.au designates 172.104.61.193 as
 permitted sender) smtp.mailfrom=aj@erisian.com.au
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
 <https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.8 (/)

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

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

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

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

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

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

> (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. Also, a script-path isn't a point at all, so having
it be a NUMS point doesn't make much sense. 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
  - it marginally increases the size of non-post-quantum spends
  - it breaks complicated scripts even without pre-signed transactions

Cheers,
aj

-- 
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/Z2ALlBGIyZLVbfVG%40erisian.com.au.