path: root/17/4a92905cab68ce5fe636f7e9ee40fa60ff07f9

Return-Path: <jlrubin@mit.edu>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 2B055C000E
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed,  7 Jul 2021 05:58:31 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp4.osuosl.org (Postfix) with ESMTP id 0B46640583
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed,  7 Jul 2021 05:58:31 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.477
X-Spam-Level: 
X-Spam-Status: No, score=-2.477 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_MED=-2.3,
 SPF_PASS=-0.001, URIBL_SBL=1.623, URIBL_SBL_A=0.1]
 autolearn=ham autolearn_force=no
Received: from smtp4.osuosl.org ([127.0.0.1])
 by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id 7ZHXGfSv4cdz
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed,  7 Jul 2021 05:58:29 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0
Received: from outgoing.mit.edu (outgoing-auth-1.mit.edu [18.9.28.11])
 by smtp4.osuosl.org (Postfix) with ESMTPS id 2BA9540580
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Wed,  7 Jul 2021 05:58:28 +0000 (UTC)
Received: from mail-io1-f46.google.com (mail-io1-f46.google.com
 [209.85.166.46]) (authenticated bits=0)
 (User authenticated as jlrubin@ATHENA.MIT.EDU)
 by outgoing.mit.edu (8.14.7/8.12.4) with ESMTP id 1675wQB3021730
 (version=TLSv1/SSLv3 cipher=AES128-GCM-SHA256 bits=128 verify=NOT)
 for <bitcoin-dev@lists.linuxfoundation.org>; Wed, 7 Jul 2021 01:58:27 -0400
Received: by mail-io1-f46.google.com with SMTP id b1so1569595ioz.8
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Tue, 06 Jul 2021 22:58:27 -0700 (PDT)
X-Gm-Message-State: AOAM5303AteO7+0GeJCqgeXDd7tHEbLbfvetUmDW3kcQFpb8w+gUWZ8J
 vU8k1cVm7G5M6RfyfaqAF45FGwc5SUl0g7PN5fQ=
X-Google-Smtp-Source: ABdhPJyXBWXZBJaJDv1i+1f6D/l53IrNg1vesrU+5HGxcu1W6876IkNlVFO2QyDoVrWraPsYgGtNxp9ykFXRTH9RRus=
X-Received: by 2002:a6b:f91a:: with SMTP id j26mr9947549iog.97.1625637506766; 
 Tue, 06 Jul 2021 22:58:26 -0700 (PDT)
MIME-Version: 1.0
From: Jeremy <jlrubin@mit.edu>
Date: Tue, 6 Jul 2021 22:58:15 -0700
X-Gmail-Original-Message-ID: <CAD5xwhgzR8e5r1e4H-5EH2mSsE1V39dd06+TgYniFnXFSBqLxw@mail.gmail.com>
Message-ID: <CAD5xwhgzR8e5r1e4H-5EH2mSsE1V39dd06+TgYniFnXFSBqLxw@mail.gmail.com>
To: Bitcoin development mailing list <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="0000000000001fdde005c6823aa5"
Subject: [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: Wed, 07 Jul 2021 05:58:31 -0000

--0000000000001fdde005c6823aa5
Content-Type: text/plain; charset="UTF-8"

Dear Bitcoin Devs,

As mentioned previously, OP_CAT (or similar operation) can be used to make
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 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 longer
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 ECDSA,
it
would yield revealing the private key but not the ability to malleate the
content of what was actually signed.  I asked my good friend and
cryptographer
[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 malleated
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 signature
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 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 opcode
that
uses verify semantics, OP\_SUBSTRINGEQUALVERIFY that checks a splice of a
string
for equality.

```
... FOR j in 0..=5
    <0>
    ... FOR i in 0..=31
        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..=5
        FROMALTSTACK
        CAT
    ... END FOR
    EQUALVERIFY
... ELSE SUBSTRINGEQUALVERIFY AVAILABLE
    ... FOR j in 0..=5
        FROMALTSTACK <0+j*4> <4+j*4> SUBSTRINGEQUALVERIFY DROP DROP DROP
    ...  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 number
(counting pushes), and two 21 bytes keys = 55.375 bytes of program space
and 21
bytes of witness element per bit.

It fits! `20*8*55.375 = 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 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.

```
        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) == 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 radix
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 = pG +
hash(pG
|| m)G`) can be securely opened to m even with a quantum computer (finding
`q`
such that `qG = 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).  Therefore this
script can nest inside of a Tapscript path -- Tapscript also does not
impose 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
before
expiring. This could be used as a measure to protect accidental use rather
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 Lamport
signed, even a quantum computer could not steal the funds.






--
@JeremyRubin <https://twitter.com/JeremyRubin>
<https://twitter.com/JeremyRubin>

--0000000000001fdde005c6823aa5
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_default" style=3D"font-family:arial,he=
lvetica,sans-serif;font-size:small;color:#000000">Dear Bitcoin Devs,</div><=
div class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif=
;font-size:small;color:#000000"><br></div><div class=3D"gmail_default" styl=
e=3D"font-family:arial,helvetica,sans-serif;font-size:small;color:#000000">=
As mentioned previously, OP_CAT (or similar operation) can be used to make =
Bitcoin &quot;quantum safe&quot; by signing an EC signature. This should wo=
rk in both Segwit V0 and Tapscript, although you have to use HASH160 for it=
 to fit in Segwit V0.</div><div class=3D"gmail_default" style=3D"font-famil=
y:arial,helvetica,sans-serif;font-size:small;color:#000000"><br></div><div =
class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif;fon=
t-size:small;color:#000000">See [my blog](<a href=3D"https://rubin.io/blog/=
2021/07/06/quantum-bitcoin/">https://rubin.io/blog/2021/07/06/quantum-bitco=
in/</a>) for the specific construction, reproduced below.</div><div class=
=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif;font-siz=
e:small;color:#000000"><br></div><div class=3D"gmail_default" style=3D"font=
-family:arial,helvetica,sans-serif;font-size:small;color:#000000">Yet anoth=
er entry to the &quot;OP_CAT can do that too&quot; list.</div><div class=3D=
"gmail_default" style=3D"font-family:arial,helvetica,sans-serif;font-size:s=
mall;color:#000000"><br></div><div class=3D"gmail_default" style=3D"font-fa=
mily:arial,helvetica,sans-serif;font-size:small;color:#000000">Best,</div><=
div class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif=
;font-size:small;color:#000000"><br></div><div class=3D"gmail_default" styl=
e=3D"font-family:arial,helvetica,sans-serif;font-size:small;color:#000000">=
Jeremy</div><div class=3D"gmail_default" style=3D"font-family:arial,helveti=
ca,sans-serif;font-size:small;color:#000000">-----</div><div class=3D"gmail=
_default" style=3D"font-family:arial,helvetica,sans-serif;font-size:small;c=
olor:#000000"><br></div><div class=3D"gmail_default" style=3D"font-family:a=
rial,helvetica,sans-serif;font-size:small;color:#000000"><br>I recently pub=
lished [a blog<br>post](<a href=3D"https://rubin.io/blog/2021/07/02/signing=
-5-bytes/">https://rubin.io/blog/2021/07/02/signing-5-bytes/</a>) about sig=
ning up to a<br>5 byte value using Bitcoin script arithmetic and Lamport si=
gnatures.<br><br>By itself, this is neat, but a little limited. What if we =
could sign longer<br>messages? If we can sign up to 20 bytes, we could sign=
 a HASH160 digest which<br>is most likely quantum safe...<br><br>What would=
 it mean if we signed the HASH160 digest of a signature? What the<br>what? =
Why would we do that?<br><br>Well, as it turns out, even if a quantum compu=
ter were able to crack ECDSA, it<br>would yield revealing the private key b=
ut not the ability to malleate the<br>content of what was actually signed.=
=C2=A0 I asked my good friend and cryptographer<br>[Madars Virza](<a href=
=3D"https://madars.org/">https://madars.org/</a>) if my intuition was corre=
ct, and he<br>confirmed that it should be sufficient, but it&#39;s definite=
ly worth closer<br>analysis before relying on this. While the ECDSA signatu=
re can be malleated to a<br>different, negative form, if the signature is o=
therwise made immalleable there<br>should only be one value the commitment =
can be opened to.<br><br>If we required the ECDSA signature be signed with =
a quantum proof signature<br>algorithm, then we&#39;d have a quantum proof =
Bitcoin! And the 5 byte signing scheme<br>we discussed previously is a Lamp=
ort signature, which is quantum secure.<br>Unfortunately, we need at least =
20 contiguous bytes... so we need some sort of<br>OP\_CAT like operation.<b=
r><br>OP\_CAT can&#39;t be directly soft forked to Segwit v0 because it mod=
ifies the<br>stack, so instead we&#39;ll (for simplicity) also show how to =
use a new opcode that<br>uses verify semantics, OP\_SUBSTRINGEQUALVERIFY th=
at checks a splice of a string<br>for equality.<br><br>```<br>... FOR j in =
0..=3D5<br>=C2=A0 =C2=A0 &lt;0&gt;<br>=C2=A0 =C2=A0 ... FOR i in 0..=3D31<b=
r>=C2=A0 =C2=A0 =C2=A0 =C2=A0 SWAP hash160 DUP &lt;H(K_j_i_1)&gt; EQUAL IF =
DROP &lt;2**i&gt; ADD ELSE &lt;H(K_j_i_0)&gt; EQUALVERIFY ENDIF<br>=C2=A0 =
=C2=A0 ... END FOR<br>=C2=A0 =C2=A0 TOALTSTACK<br>... END FOR<br><br>DUP HA=
SH160<br><br>... IF CAT AVAILABLE<br>=C2=A0 =C2=A0 FROMALTSTACK<br>=C2=A0 =
=C2=A0 ... FOR j in 0..=3D5<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 FROMALTSTACK<br>=
=C2=A0 =C2=A0 =C2=A0 =C2=A0 CAT<br>=C2=A0 =C2=A0 ... END FOR<br>=C2=A0 =C2=
=A0 EQUALVERIFY<br>... ELSE SUBSTRINGEQUALVERIFY AVAILABLE<br>=C2=A0 =C2=A0=
 ... FOR j in 0..=3D5<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 FROMALTSTACK &lt;0+j*4=
&gt; &lt;4+j*4&gt; SUBSTRINGEQUALVERIFY DROP DROP DROP<br>=C2=A0 =C2=A0 ...=
=C2=A0 END FOR<br>=C2=A0 =C2=A0 DROP<br>... END IF<br><br>&lt;pk&gt; CHECKS=
IG<br>```<br><br>That&#39;s a long script... but will it fit? We need to ve=
rify 20 bytes of message<br>each bit takes around 10 bytes script, an avera=
ge of 3.375 bytes per number<br>(counting pushes), and two 21 bytes keys =
=3D 55.375 bytes of program space and 21<br>bytes of witness element per bi=
t.<br><br>It fits! `20*8*55.375 =3D 8860`, which leaves 1140 bytes less tha=
n the limit for<br>the rest of the logic, which is plenty (around 15-40 byt=
es required for the rest<br>of the logic, leaving 1100 free for custom sign=
ature checking). The stack size<br>is 160 elements for the hash gadget, 336=
0 bytes.<br><br>This can probably be made a bit more efficient by expanding=
 to a ternary<br>representation.<br><br>```<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =
SWAP hash160 DUP &lt;H(K_j_i_0)&gt; EQUAL =C2=A0IF DROP =C2=A0ELSE &lt;3**i=
&gt; SWAP DUP &lt;H(K_j_i_T)&gt; EQUAL IF DROP SUB ELSE &lt;H(K_j_i_1)&gt; =
EQUALVERIFY ADD =C2=A0ENDIF ENDIF<br>```<br><br>This should bring it up to =
roughly 85 bytes per trit, and there should be 101<br>trits (`log(2**160)/l=
og(3) =3D=3D 100.94`), so about 8560 bytes... a bit cheaper!<br>But the wit=
ness stack is &quot;only&quot; `2121` bytes...<br><br>As a homework exercis=
e, maybe someone can prove the optimal choice of radix for<br>this protocol=
... My guess is that base 4 is optimal!<br><br>## Taproot?<br><br>What abou=
t Taproot? As far as I&#39;m aware the commitment scheme (`Q =3D pG + hash(=
pG<br>|| m)G`) can be securely opened to m even with a quantum computer (fi=
nding `q`<br>such that `qG =3D Q` might be trivial, but suppose key path wa=
s disabled, then<br>finding m and p such that the taproot equation holds sh=
ould be difficult because<br>of the hash, but I&#39;d need to certify that =
claim better).=C2=A0 Therefore this<br>script can nest inside of a Tapscrip=
t path -- Tapscript also does not impose a<br>length limit, 32 byte hashes =
could be used as well.<br><br>Further, to make keys reusable, there could b=
e many Lamport keys comitted inside<br>a taproot tree so that an address co=
uld be used for thousands of times before<br>expiring. This could be used a=
s a measure to protect accidental use rather than<br>to support it.<br><br>=
Lastly, Schnorr actually has a stronger non-malleability property than ECDS=
A,<br>the signatures will be binding to the approved transaction and once L=
amport<br>signed, even a quantum computer could not steal the funds.<br><br=
><br><br><br><br></div><br clear=3D"all"><div><div dir=3D"ltr" class=3D"gma=
il_signature" data-smartmail=3D"gmail_signature"><div dir=3D"ltr">--<br><a =
href=3D"https://twitter.com/JeremyRubin" target=3D"_blank">@JeremyRubin</a>=
<a href=3D"https://twitter.com/JeremyRubin" target=3D"_blank"></a></div></d=
iv></div></div>

--0000000000001fdde005c6823aa5--