path: root/e5/3ea258ad6b5b6df88481d92863d7514b68e97f

Return-Path: <ZmnSCPxj@protonmail.com>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 8B772C000E
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  8 Jul 2021 08:12:13 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp1.osuosl.org (Postfix) with ESMTP id 7384083104
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  8 Jul 2021 08:12:13 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: 0.4
X-Spam-Level: 
X-Spam-Status: No, score=0.4 tagged_above=-999 required=5
 tests=[BAYES_20=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 FROM_LOCAL_NOVOWEL=0.5, RCVD_IN_MSPIKE_H4=0.001,
 RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-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 (1024-bit key) header.d=protonmail.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 mMb8ZcgsdojT
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  8 Jul 2021 08:12:10 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0
Received: from mail-4324.protonmail.ch (mail-4324.protonmail.ch [185.70.43.24])
 by smtp1.osuosl.org (Postfix) with ESMTPS id D45F382F6F
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Thu,  8 Jul 2021 08:12:09 +0000 (UTC)
Date: Thu, 08 Jul 2021 08:12:01 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com;
 s=protonmail; t=1625731926;
 bh=LqyRtd/90F1VNDq832MSuVP5f968NbeoRR4FEM4X610=;
 h=Date:To:From:Reply-To:Subject:In-Reply-To:References:From;
 b=j7moGfRymXOMhpYHucrXZe4O86WKSG3f1qwFWN5e6FGDdiwEXuN6N1m7GHi9tc6hY
 3PRd4hmkCRTygZBtR+vP7K/E4vlX4EX7L8NpVkMRhQnhZrg68t5eXay/JKCCvYBgGd
 2sCuRIlTrlRSGmVxH447ra5PaYkALMak6qHJZV+4=
To: Jeremy <jlrubin@mit.edu>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <MAfz2o3-uf5SfGKfMwONmT4TH4cmcAEJGyx21_dRQWBuCZZzFSXg38xyRY7HiMYMFB5zuTPorf_LYrnjE2K__uP578h7MZypf68yM0xjU3w=@protonmail.com>
In-Reply-To: <CAD5xwhgzR8e5r1e4H-5EH2mSsE1V39dd06+TgYniFnXFSBqLxw@mail.gmail.com>
References: <CAD5xwhgzR8e5r1e4H-5EH2mSsE1V39dd06+TgYniFnXFSBqLxw@mail.gmail.com>
MIME-Version: 1.0
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: Thu, 08 Jul 2021 08:12:13 -0000


Good morning Jeremy,

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

Since a quantum computer can derive the EC privkey from the EC pubkey and t=
his 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 (uniqueness =
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 mak=
e Bitcoin "quantum safe" by signing an EC signature. This should work in bo=
th Segwit V0 and Tapscript, although you have to use HASH160 for it to fit =
in Segwit V0.
>
> See [my blog](https://rubin.io/blog/2021/07/06/quantum-bitcoin/) for the =
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 long=
er
> messages? If we can sign up to 20 bytes, we could sign a HASH160 digest w=
hich
> is most likely quantum safe...
>
> What would it mean if we signed the HASH160 digest of a signature? What t=
he
> what? Why would we do that?
>
> Well, as it turns out, even if a quantum computer were able to crack ECDS=
A, it
> would yield revealing the private key but not the ability to malleate the
> content of what was actually signed.=C2=A0 I asked my good friend and cry=
ptographer
> [Madars Virza](https://madars.org/) if my intuition was correct, and he
> confirmed that it should be sufficient, but it's definitely worth closer
> analysis before relying on this. While the ECDSA signature can be malleat=
ed to a
> different, negative form, if the signature is otherwise made immalleable =
there
> should only be one value the commitment can be opened to.
>
> If we required the ECDSA signature be signed with a quantum proof signatu=
re
> algorithm, then we'd have a quantum proof Bitcoin! And the 5 byte signing=
 scheme
> we discussed previously is a Lamport signature, which is quantum secure.
> Unfortunately, we need at least 20 contiguous bytes... so we need some so=
rt of
> OP\_CAT like operation.
>
> OP\_CAT can't be directly soft forked to Segwit v0 because it modifies th=
e
> stack, so instead we'll (for simplicity) also show how to use a new opcod=
e that
> uses verify semantics, OP\_SUBSTRINGEQUALVERIFY that checks a splice of a=
 string
> for equality.
>
> ```
> ... FOR j in 0..=3D5
> =C2=A0 =C2=A0 <0>
> =C2=A0 =C2=A0 ... FOR i in 0..=3D31
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 SWAP hash160 DUP <H(K_j_i_1)> EQUAL IF DROP <=
2**i> ADD ELSE <H(K_j_i_0)> EQUALVERIFY ENDIF
> =C2=A0 =C2=A0 ... END FOR
> =C2=A0 =C2=A0 TOALTSTACK
> ... END FOR
>
> DUP HASH160
>
> ... IF CAT AVAILABLE
> =C2=A0 =C2=A0 FROMALTSTACK
> =C2=A0 =C2=A0 ... FOR j in 0..=3D5
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 FROMALTSTACK
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 CAT
> =C2=A0 =C2=A0 ... END FOR
> =C2=A0 =C2=A0 EQUALVERIFY
> ... ELSE SUBSTRINGEQUALVERIFY AVAILABLE
> =C2=A0 =C2=A0 ... FOR j in 0..=3D5
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 FROMALTSTACK <0+j*4> <4+j*4> SUBSTRINGEQUALVE=
RIFY DROP DROP DROP
> =C2=A0 =C2=A0 ...=C2=A0 END FOR
> =C2=A0 =C2=A0 DROP
> ... END IF
>
> <pk> CHECKSIG
> ```
>
> That's a long script... but will it fit? We need to verify 20 bytes of me=
ssage
> each bit takes around 10 bytes script, an average of 3.375 bytes per numb=
er
> (counting pushes), and two 21 bytes keys =3D 55.375 bytes of program spac=
e and 21
> bytes of witness element per bit.
>
> It fits! `20*8*55.375 =3D 8860`, which leaves 1140 bytes less than the li=
mit for
> the rest of the logic, which is plenty (around 15-40 bytes required for t=
he rest
> of the logic, leaving 1100 free for custom signature checking). The stack=
 size
> is 160 elements for the hash gadget, 3360 bytes.
>
> This can probably be made a bit more efficient by expanding to a ternary
> representation.
>
> ```
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 SWAP hash160 DUP <H(K_j_i_0)> EQUAL =C2=A0IF =
DROP =C2=A0ELSE <3**i> SWAP DUP <H(K_j_i_T)> EQUAL IF DROP SUB ELSE <H(K_j_=
i_1)> EQUALVERIFY ADD =C2=A0ENDIF 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 bit =
cheaper!
> But the witness stack is "only" `2121` bytes...
>
> As a homework exercise, maybe someone can prove the optimal choice of rad=
ix 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 pG =
+ hash(pG
> || m)G`) can be securely opened to m even with a quantum computer (findin=
g `q`
> such that `qG =3D Q` might be trivial, but suppose key path was disabled,=
 then
> finding m and p such that the taproot equation holds should be difficult =
because
> of the hash, but I'd need to certify that claim better).=C2=A0 Therefore =
this
> script can nest inside of a Tapscript path -- Tapscript also does not imp=
ose a
> length limit, 32 byte hashes could be used as well.
>
> Further, to make keys reusable, there could be many Lamport keys comitted=
 inside
> a taproot tree so that an address could be used for thousands of times be=
fore
> expiring. This could be used as a measure to protect accidental use rathe=
r than
> to support it.
>
> Lastly, Schnorr actually has a stronger non-malleability property than EC=
DSA,
> the signatures will be binding to the approved transaction and once Lampo=
rt
> signed, even a quantum computer could not steal the funds.
>
> --
> @JeremyRubin