path: root/83/32df92bd79b8a5c775f925947a350581d9ba4a

Return-Path: <eth3rs@gmail.com>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 13E0AC000E
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  9 Jul 2021 19:02:55 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp1.osuosl.org (Postfix) with ESMTP id ECE9382A2D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  9 Jul 2021 19:02:54 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.999
X-Spam-Level: 
X-Spam-Status: No, score=-1.999 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001,
 URIBL_SBL_A=0.1] autolearn=ham autolearn_force=no
Authentication-Results: smtp1.osuosl.org (amavisd-new);
 dkim=pass (2048-bit key) header.d=gmail.com
Received: from smtp1.osuosl.org ([127.0.0.1])
 by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id kx7-MFV3lGXj
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  9 Jul 2021 19:02:54 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-ej1-x62b.google.com (mail-ej1-x62b.google.com
 [IPv6:2a00:1450:4864:20::62b])
 by smtp1.osuosl.org (Postfix) with ESMTPS id BC5A482919
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  9 Jul 2021 19:02:53 +0000 (UTC)
Received: by mail-ej1-x62b.google.com with SMTP id nd37so18063348ejc.3
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 09 Jul 2021 12:02:53 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc:content-transfer-encoding;
 bh=KXgMg4QUW0OGAtEJvnwRA+IPVqzZ50D8z8hf78Gwzi0=;
 b=MR9b9a/ntL4+eFmxhiuo7LxLAYbM028bJmzcHpbpeolQK9QDjJZ5uDFDp/P1ver4Na
 qFLYf5SDAExLj/+KzVDnb1DCEEfTIDXyD17Yh4T5wG9xQkigg4cNK29T0YmReQxRfjP7
 wpxd4B5Kat+pge6FwXPfZMi2yvV2skFuq+YT6yTm9cXdqxP5KPrsSI5WOrB9yRKPBnw4
 1xWPZ7peId23+Vyg1sdCI5TGoXZYWcHb487n/VdyuzUst7aY92+e+Be0yLGVN8wcaLN0
 Hy/n+nT0zxkQB5OYODb9+u4A1XqNYS0rKHclqAI2+CLg9DamPMyCojULxYbMZNerA37j
 +mhA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc:content-transfer-encoding;
 bh=KXgMg4QUW0OGAtEJvnwRA+IPVqzZ50D8z8hf78Gwzi0=;
 b=lzFkrMUCyjeY5CsJh5BfFdO6xR8qK57Xbwp9a0OorM3Z2dMVM1xmTCerOp5RX5zEd6
 GFEv/fTfWV6ylsY27FqUhGyjpyFec8aAZDN22PBZiLTr1n7SYbc4QcAAGGXCiepImSFt
 rCh52kGIqCagD3Q079oL/v5TlSMCImMwu8Hl2jC87WqK0saNkPo8nTSQCmnTF3gbFJi+
 7bxPSXeVYFVPloERJ4DGRur6X6AV3DwJRcQuJxsrP47Bz41lvLw2xVjF2iXiYsI0bdat
 gx+T3X6UKgtjnCdbgLaUPTmbMfMBrjgm8V5Lq3ERrK0nj8HEoa7kq13VVPa/r7hVmlKN
 9/zA==
X-Gm-Message-State: AOAM532tRVGCeJWC0ipG1LOaaTcdva6q1NXhc88hIJleAzRU8wxWOC8U
 +uzMHQbDmO6q3OFXao9z99cGX4dn5HXUX34819A=
X-Google-Smtp-Source: ABdhPJw1EU1U843PUI4GT5rR0Ou5ar5DjA7nMccDwJUbBPs19W3+EevbQr+uFPwL1Q6w2l6IfXidzLcsO87KgWgXwDE=
X-Received: by 2002:a17:906:e97:: with SMTP id
 p23mr1862297ejf.287.1625857372016; 
 Fri, 09 Jul 2021 12:02:52 -0700 (PDT)
MIME-Version: 1.0
References: <CAD5xwhgzR8e5r1e4H-5EH2mSsE1V39dd06+TgYniFnXFSBqLxw@mail.gmail.com>
 <MAfz2o3-uf5SfGKfMwONmT4TH4cmcAEJGyx21_dRQWBuCZZzFSXg38xyRY7HiMYMFB5zuTPorf_LYrnjE2K__uP578h7MZypf68yM0xjU3w=@protonmail.com>
In-Reply-To: <MAfz2o3-uf5SfGKfMwONmT4TH4cmcAEJGyx21_dRQWBuCZZzFSXg38xyRY7HiMYMFB5zuTPorf_LYrnjE2K__uP578h7MZypf68yM0xjU3w=@protonmail.com>
From: Ethan Heilman <eth3rs@gmail.com>
Date: Fri, 9 Jul 2021 15:02:15 -0400
Message-ID: <CAEM=y+WkG9razw6uEhkXtNCgonaw2GHp9oGB3J7uf9N_JVdPoQ@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>, 
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Subject: Re: [bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was
 CheckSigFromStack for Arithmetic Values]
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: Bitcoin Protocol Discussion <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=subscribe>
X-List-Received-Date: Fri, 09 Jul 2021 19:02:55 -0000

>Yes, quite neat indeed, too bad Lamport signatures are so huge (a couple k=
ilobytes)... blocksize increase *cough*

Couldn't you significantly compress the signatures by using either
Winternitz OTS or by using OP_CAT to build a merkle tree so that the
full signature can be derived during script execution from a much
shorter set of seed values?

On Thu, Jul 8, 2021 at 4:12 AM ZmnSCPxj via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
>
>
> Good morning Jeremy,
>
> Yes, quite neat indeed, too bad Lamport signatures are so huge (a couple =
kilobytes)... blocksize increase *cough*
>
> Since a quantum computer can derive the EC privkey from the EC pubkey and=
 this scheme is resistant to that, I think you can use a single well-known =
EC privkey, you just need a unique Lamport keypair for each UTXO (uniquenes=
s being mandatory due to Lamport requiring preimage revelation).
>
> Regards,
> ZmnSCPxj
>
>
> > Dear Bitcoin Devs,
> >
> > As mentioned previously, OP_CAT (or similar operation) can be used to m=
ake Bitcoin "quantum safe" by signing an EC signature. This should work in =
both Segwit V0 and Tapscript, although you have to use HASH160 for it to fi=
t in Segwit V0.
> >
> > See [my blog](https://rubin.io/blog/2021/07/06/quantum-bitcoin/) for th=
e specific construction, reproduced below.
> >
> > Yet another entry to the "OP_CAT can do that too" list.
> >
> > Best,
> >
> > Jeremy
> > -----
> >
> > I recently published [a blog
> > post](https://rubin.io/blog/2021/07/02/signing-5-bytes/) about signing =
up to a
> > 5 byte value using Bitcoin script arithmetic and Lamport signatures.
> >
> > By itself, this is neat, but a little limited. What if we could sign lo=
nger
> > messages? If we can sign up to 20 bytes, we could sign a HASH160 digest=
 which
> > is most likely quantum safe...
> >
> > What would it mean if we signed the HASH160 digest of a signature? What=
 the
> > what? Why would we do that?
> >
> > Well, as it turns out, even if a quantum computer were able to crack EC=
DSA, it
> > would yield revealing the private key but not the ability to malleate t=
he
> > content of what was actually signed.  I asked my good friend and crypto=
grapher
> > [Madars Virza](https://madars.org/) if my intuition was correct, and he
> > confirmed that it should be sufficient, but it's definitely worth close=
r
> > analysis before relying on this. While the ECDSA signature can be malle=
ated to a
> > different, negative form, if the signature is otherwise made immalleabl=
e there
> > should only be one value the commitment can be opened to.
> >
> > If we required the ECDSA signature be signed with a quantum proof signa=
ture
> > algorithm, then we'd have a quantum proof Bitcoin! And the 5 byte signi=
ng scheme
> > we discussed previously is a Lamport signature, which is quantum secure=
.
> > Unfortunately, we need at least 20 contiguous bytes... so we need some =
sort of
> > OP\_CAT like operation.
> >
> > OP\_CAT can't be directly soft forked to Segwit v0 because it modifies =
the
> > stack, so instead we'll (for simplicity) also show how to use a new opc=
ode that
> > uses verify semantics, OP\_SUBSTRINGEQUALVERIFY that checks a splice of=
 a string
> > for equality.
> >
> > ```
> > ... FOR j in 0..=3D5
> >     <0>
> >     ... FOR i in 0..=3D31
> >         SWAP hash160 DUP <H(K_j_i_1)> EQUAL IF DROP <2**i> ADD ELSE <H(=
K_j_i_0)> EQUALVERIFY ENDIF
> >     ... END FOR
> >     TOALTSTACK
> > ... END FOR
> >
> > DUP HASH160
> >
> > ... IF CAT AVAILABLE
> >     FROMALTSTACK
> >     ... FOR j in 0..=3D5
> >         FROMALTSTACK
> >         CAT
> >     ... END FOR
> >     EQUALVERIFY
> > ... ELSE SUBSTRINGEQUALVERIFY AVAILABLE
> >     ... FOR j in 0..=3D5
> >         FROMALTSTACK <0+j*4> <4+j*4> SUBSTRINGEQUALVERIFY DROP DROP DRO=
P
> >     ...  END FOR
> >     DROP
> > ... END IF
> >
> > <pk> CHECKSIG
> > ```
> >
> > That's a long script... but will it fit? We need to verify 20 bytes of =
message
> > each bit takes around 10 bytes script, an average of 3.375 bytes per nu=
mber
> > (counting pushes), and two 21 bytes keys =3D 55.375 bytes of program sp=
ace and 21
> > bytes of witness element per bit.
> >
> > It fits! `20*8*55.375 =3D 8860`, which leaves 1140 bytes less than the =
limit for
> > the rest of the logic, which is plenty (around 15-40 bytes required for=
 the rest
> > of the logic, leaving 1100 free for custom signature checking). The sta=
ck size
> > is 160 elements for the hash gadget, 3360 bytes.
> >
> > This can probably be made a bit more efficient by expanding to a ternar=
y
> > representation.
> >
> > ```
> >         SWAP hash160 DUP <H(K_j_i_0)> EQUAL  IF DROP  ELSE <3**i> SWAP =
DUP <H(K_j_i_T)> EQUAL IF DROP SUB ELSE <H(K_j_i_1)> EQUALVERIFY ADD  ENDIF=
 ENDIF
> > ```
> >
> > This should bring it up to roughly 85 bytes per trit, and there should =
be 101
> > trits (`log(2**160)/log(3) =3D=3D 100.94`), so about 8560 bytes... a bi=
t cheaper!
> > But the witness stack is "only" `2121` bytes...
> >
> > As a homework exercise, maybe someone can prove the optimal choice of r=
adix for
> > this protocol... My guess is that base 4 is optimal!
> >
> > ## Taproot?
> >
> > What about Taproot? As far as I'm aware the commitment scheme (`Q =3D p=
G + hash(pG
> > || m)G`) can be securely opened to m even with a quantum computer (find=
ing `q`
> > such that `qG =3D Q` might be trivial, but suppose key path was disable=
d, then
> > finding m and p such that the taproot equation holds should be difficul=
t because
> > of the hash, but I'd need to certify that claim better).  Therefore thi=
s
> > script can nest inside of a Tapscript path -- Tapscript also does not i=
mpose a
> > length limit, 32 byte hashes could be used as well.
> >
> > Further, to make keys reusable, there could be many Lamport keys comitt=
ed inside
> > a taproot tree so that an address could be used for thousands of times =
before
> > expiring. This could be used as a measure to protect accidental use rat=
her than
> > to support it.
> >
> > Lastly, Schnorr actually has a stronger non-malleability property than =
ECDSA,
> > the signatures will be binding to the approved transaction and once Lam=
port
> > signed, even a quantum computer could not steal the funds.
> >
> > --
> > @JeremyRubin
>
>
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev