path: root/af/2e70422643415fbcee141dd40bd9e95327ab24

Delivery-date: Mon, 16 Dec 2024 14:22:47 -0800
Received: from mail-oo1-f64.google.com ([209.85.161.64])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBAABBLOQQK5QMGQEPH7A23Y@googlegroups.com>)
	id 1tNJUE-0005vh-8h
	for bitcoindev@gnusha.org; Mon, 16 Dec 2024 14:22:46 -0800
Received: by mail-oo1-f64.google.com with SMTP id 006d021491bc7-5f3339a3bbfsf529550eaf.3
        for <bitcoindev@gnusha.org>; Mon, 16 Dec 2024 14:22:46 -0800 (PST)
ARC-Seal: i=2; a=rsa-sha256; t=1734387760; cv=pass;
        d=google.com; s=arc-20240605;
        b=AnGQhhkR/Ru7x6HNDpe721V+CTbYkXXbujlI05MfvyV0QPip5Ktvrf5wp8wJfMP7oC
         mUinPxGKmzioNIAq2bzmfScpAjxPpNtTGsROiGOV2rKL3YdECZvdat72nN8XvnPyWqnK
         JsMgAfFAGReo+TIjCTM/XbG4XfssgMf7uBh8clHChKRaDxBiy49MEPwZj3TgpjAzQzGv
         Aig9KGuk8vswURmQQ4QPl2t4Lyo99Q45JaOg+dpldFrFxDhr3jaWhc+S3NSrq0oxRvVU
         UWTs3+xDDdCovArY1Pbun5nD4kXGiRObjTOX4/pz8PHhS14nj65xkEJil9/ijBIUeX7w
         wIVQ==
ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:in-reply-to:from:content-language
         :references:cc:to:subject:mime-version:date:message-id:sender
         :dkim-signature;
        bh=IBy6TFn4ioFvlfNtvto1Cm3GddS01r+tKTdM50zkat8=;
        fh=lMAfUnybWdYe1ThTGEps9RvmlpwYkEC1hNEibUQYP3Y=;
        b=fLzs8s2heDMRMQsG3AIr9rhRTeDpd+CRw6u21qNkciRhER5N2DHVO+woDiFrXH3iiM
         F81QIw2VHYsAyJn8V9sceOuzQW+JAUZFPojjPkEt5dTy9UMY6v9eBPi46EXAIsYoQXP9
         B9hj3m7MqXvzrFEpcaukjrmTZNpiBF8aKnz6UsTleK5q1+5iUF45iCsFfWoNgXwwh1Cx
         PimK4pvj24BfoaGyQLs4qvKpZ8+XA7PLVIB0VR/55rWS11iiZQ/+BosH5DRnbJ/fwyGi
         FCR3XyoB3zrR1gVGdsElVTTrONcCRyH9WVZucRhCMfn/vbJ0azIu9Y8Es/dbMW+REpkX
         64Hg==;
        darn=gnusha.org
ARC-Authentication-Results: i=2; gmr-mx.google.com;
       dkim=pass header.i=@mattcorallo.com header.s=1734362463 header.b=rFNDUbG9;
       dkim=pass header.i=@clients.mail.as397444.net header.s=1734362466 header.b=wlQtux1i;
       spf=pass (google.com: domain of lf-lists@mattcorallo.com designates 69.59.18.99 as permitted sender) smtp.mailfrom=lf-lists@mattcorallo.com;
       dmarc=pass (p=NONE sp=REJECT dis=NONE) header.from=mattcorallo.com
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1734387760; x=1734992560; darn=gnusha.org;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:in-reply-to:from:content-language:references:cc
         :to:subject:mime-version:date:message-id:sender:from:to:cc:subject
         :date:message-id:reply-to;
        bh=IBy6TFn4ioFvlfNtvto1Cm3GddS01r+tKTdM50zkat8=;
        b=dIFiXcAnLGuql+wYYjxaPkN0QXimYaS1N/JW6ACIZLAd3TlxjoeGRb6Z6tFjqqDl9y
         tdg8P6RNDbs887ROPX2cGoZ8V2H8DcYmSgtvnqGftagmwQF/FyU8mNr9FA0PkULRCbTS
         TgsPZd70FDAGUJ4oB85DzCrygJS7xKwyXAkbjPfJSJQ+N28Ivf3DGe0UU0FxU6fzAjJL
         aWjJEEakD8NCoPhMbmZR0LjDaQK4j0IQriyhYpxfCO0FMbQdbXiYLA8WyxLHD8Ly3qDl
         WmbHdEbRb0r5F9W59MOb0zcUXfK4rxls//cc+NotMd/ELoXMihjJ54EGSBxOa0J0H7I8
         RxBQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1734387760; x=1734992560;
        h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
         :list-id:mailing-list:precedence:x-original-authentication-results
         :x-original-sender:in-reply-to:from:content-language:references:cc
         :to:subject:mime-version:date:message-id:x-beenthere
         :x-gm-message-state:sender:from:to:cc:subject:date:message-id
         :reply-to;
        bh=IBy6TFn4ioFvlfNtvto1Cm3GddS01r+tKTdM50zkat8=;
        b=cBBHH1GxafFELGe1fLxPobt2kTZTXXxqLJAJqQ00/G7YBmlYd5Jf9NURryl0wDTZ0T
         XXTfWPvubebVTNQtm8iX827Kqp0VmrN16suVO9bEtptkKYk4vcHlxcqXQXkG3YlyWuRL
         D/Oy2mHEjQTjyH1U/Netu7eUS3qJvwyuHFkviysM+koJ3TGbOSMGp3xxcqxUhuAXaIol
         MWCS3/SAGyUIsNf/cy6eQMVZ8pToC73AVnlMfruGOBks6p+AGVxZh2EHnEl3wckMtTvr
         Lyys8gsGLbb2uayLDiahD5Y5OM/xoQmUauqF0TxYjBPxhT1by7nq+avudpaqNJ/7vnWZ
         rZ6A==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=2; AJvYcCXskZVuski+2acY0soQRz7/cRw14Ho8jQkGG5Lyhz9UnhVh0NYulJiRScm7XtWOY0konILFTK4A4ttf@gnusha.org
X-Gm-Message-State: AOJu0YzkBfSsggIYkKFn2uMvJytp/IkNHXqJYAZv9bT0S2kof3s1r/iG
	NyJqeP3PRSQ82QOTZN/hZdnU5zfo9isQ1Th85QsvplpuvpntbS1f
X-Google-Smtp-Source: AGHT+IHaUyE/aQ3xcHIWjMYtxJ/dm4EDI9iYYQnNUU08axrFRelleulR81Q23YuN0xC+OSHrNiomfA==
X-Received: by 2002:a05:6870:2c8d:b0:29f:b09d:d93a with SMTP id 586e51a60fabf-2a3ac6c398fmr7911627fac.16.1734387760065;
        Mon, 16 Dec 2024 14:22:40 -0800 (PST)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a05:6870:1689:b0:2a0:218e:bd25 with SMTP id
 586e51a60fabf-2a3af94fa49ls908646fac.2.-pod-prod-04-us; Mon, 16 Dec 2024
 14:22:37 -0800 (PST)
X-Received: by 2002:a05:6808:15a1:b0:3e9:1750:426d with SMTP id 5614622812f47-3ebcb2770e6mr331857b6e.13.1734387757663;
        Mon, 16 Dec 2024 14:22:37 -0800 (PST)
Received: by 2002:a05:6808:1c1:b0:3eb:7446:f871 with SMTP id 5614622812f47-3eba5444a98msb6e;
        Mon, 16 Dec 2024 07:57:41 -0800 (PST)
X-Received: by 2002:a17:90b:4d08:b0:2ee:e113:815d with SMTP id 98e67ed59e1d1-2f28fa55bd7mr19855093a91.8.1734364660013;
        Mon, 16 Dec 2024 07:57:40 -0800 (PST)
ARC-Seal: i=1; a=rsa-sha256; t=1734364660; cv=none;
        d=google.com; s=arc-20240605;
        b=I+FKn5/xkD4E6nvI2xQ1ajcZUPfpoEqK0KkKw+//Yp8/Q1HlFDiK+9/0bB6YHtm8+q
         AonnCkx7TOIHsx0EuCrm25FZCIF8P/XpuUQVga2pPVkRufo+sZUJYVorix7jdQ6aVu4N
         S3OoUudoKXNeBggu3BlgpwJgAsGR42U1Wv5uGD7BDDLgrQ6+ZYzfAIM+dfrY9rC1xU4s
         uIWO0DJc4AEeB63eAtFHm+YkE9CF0KlIZMcp2mxv1fpam7sq/kKJZP8bTXxV6OAZmGD3
         z3s5p0mMgaJ6xEnmis8DZtuK/XT+MXSalfgntesGot6Vrmb5zt2Y+RJJYoAFFG3wmDsS
         eCKQ==
ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605;
        h=content-transfer-encoding:in-reply-to:from:content-language
         :references:cc:to:subject:mime-version:date:message-id
         :dkim-signature:dkim-signature;
        bh=H2vDuTThNMWsd15Ggjdj3FfFor4SFkgen5QWFO5VZvY=;
        fh=eQwyrPB7DiKLZfk3HA1+IBNTG62m+FxzJ3AFq+zftRc=;
        b=gDokoXxRfpgqfPcv3fKsYumL/TyrXTSG697jcC8E5Pn0oq4VA3G7p4l/b+ndwbNdVq
         PMDw4FuiOG14xKAMzO9WqZx/J3ZsdvUnlfzuRosriSlE0KiM06SX17bdmcgEgAmFL2CP
         SaazWmhkrzg5Sx0iheP8JVkOcOBAS61K9S3yzb3WS9YSIE87vzb+wfECZaGgh1z7aRIp
         6kVZlXjnoTxVv2jeSi5fhzRvTxbq16OKhIS8AtoSoMrug1aI+9uvEqq9K5WFPTM8JZiG
         kpsrsLYIbL71qrq8XpaN08PgLUCScK6RYzsn6qM4kWoa2BOGs3AqUo0PktdGxk9O3sq6
         txIQ==;
        dara=google.com
ARC-Authentication-Results: i=1; gmr-mx.google.com;
       dkim=pass header.i=@mattcorallo.com header.s=1734362463 header.b=rFNDUbG9;
       dkim=pass header.i=@clients.mail.as397444.net header.s=1734362466 header.b=wlQtux1i;
       spf=pass (google.com: domain of lf-lists@mattcorallo.com designates 69.59.18.99 as permitted sender) smtp.mailfrom=lf-lists@mattcorallo.com;
       dmarc=pass (p=NONE sp=REJECT dis=NONE) header.from=mattcorallo.com
Received: from mail.as397444.net (mail.as397444.net. [69.59.18.99])
        by gmr-mx.google.com with ESMTPS id 98e67ed59e1d1-2f142e752d4si360781a91.2.2024.12.16.07.57.39
        for <bitcoindev@googlegroups.com>
        (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256);
        Mon, 16 Dec 2024 07:57:39 -0800 (PST)
Received-SPF: pass (google.com: domain of lf-lists@mattcorallo.com designates 69.59.18.99 as permitted sender) client-ip=69.59.18.99;
X-DKIM-Note: Keys used to sign are likely public at
X-DKIM-Note: https://as397444.net/dkim/mattcorallo.com and
X-DKIM-Note: https://as397444.net/dkim/clients.mail.as397444.net
X-DKIM-Note: For more info, see https://as397444.net/dkim/
Received: by mail.as397444.net with esmtpsa (TLS1.3) (Exim)
	(envelope-from <lf-lists@mattcorallo.com>)
	id 1tNDTV-006mFd-28;
	Mon, 16 Dec 2024 15:57:37 +0000
Message-ID: <07134c47-5d44-446f-8bfb-9438026444cd@mattcorallo.com>
Date: Mon, 16 Dec 2024 10:57:36 -0500
MIME-Version: 1.0
Subject: Re: [bitcoindev] Trivial QC signatures with clean upgrade path
To: Anthony Towns <aj@erisian.com.au>
Cc: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
References: <c2684826-6c93-419b-9a96-c0f0a791c9ac@mattcorallo.com>
 <Z2ALlBGIyZLVbfVG@erisian.com.au>
Content-Language: en-US
From: Matt Corallo <lf-lists@mattcorallo.com>
In-Reply-To: <Z2ALlBGIyZLVbfVG@erisian.com.au>
Content-Type: text/plain; charset="UTF-8"; format=flowed
X-Original-Sender: lf-lists@mattcorallo.com
X-Original-Authentication-Results: gmr-mx.google.com;       dkim=pass
 header.i=@mattcorallo.com header.s=1734362463 header.b=rFNDUbG9;
       dkim=pass header.i=@clients.mail.as397444.net header.s=1734362466
 header.b=wlQtux1i;       spf=pass (google.com: domain of lf-lists@mattcorallo.com
 designates 69.59.18.99 as permitted sender) smtp.mailfrom=lf-lists@mattcorallo.com;
       dmarc=pass (p=NONE sp=REJECT dis=NONE) header.from=mattcorallo.com
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 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+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/07134c47-5d44-446f-8bfb-9438026444cd%40mattcorallo.com.