Date: Thu, 08 Jul 2021 08:12:01 +0000
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]
Precedence: list


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