Date: Fri, 09 Jul 2021 22:38:18 +0000
To: Ethan Heilman <eth3rs@gmail.com>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <XFMgrCKhdCuJ7LJ2KLv-r8dAGNs89H3NkvZgio5X6evKQ506p54HUF0hyxq0kQ48QeNJzmc--fy5keaSrzUQ7ylteCxe9TJNXnqJvaDy_X4=@protonmail.com>
In-Reply-To: <CAEM=y+WkG9razw6uEhkXtNCgonaw2GHp9oGB3J7uf9N_JVdPoQ@mail.gmail.com>
References: <CAD5xwhgzR8e5r1e4H-5EH2mSsE1V39dd06+TgYniFnXFSBqLxw@mail.gmail.com>
 <MAfz2o3-uf5SfGKfMwONmT4TH4cmcAEJGyx21_dRQWBuCZZzFSXg38xyRY7HiMYMFB5zuTPorf_LYrnjE2K__uP578h7MZypf68yM0xjU3w=@protonmail.com>
 <CAEM=y+WkG9razw6uEhkXtNCgonaw2GHp9oGB3J7uf9N_JVdPoQ@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] OP_CAT Makes Bitcoin Quantum Secure [was
	CheckSigFromStack for Arithmetic Values]
Precedence: list

Good morning Ethan,

> > Yes, quite neat indeed, too bad Lamport signatures are so huge (a coupl=
e kilobytes)... 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?

To implement Winternitz we need some kind of limited-repeat construct, whic=
h is not available in SCRIPT, but may be emulatable with enough `OP_IF` and=
 sheer brute force.
But what you gain in smaller signatures, you lose in a more complex and lon=
ger SCRIPT, and there are limits to SCRIPT size (in order to limit the proc=
essing done in each node).

Merkle signatures trade off shorter pubkeys for longer signatures (signatur=
es need to provide the hash of the *other* preimage you are not revealing),=
 but in the modern post-SegWit Bitcoin context both pubkeys and signatures =
are stored in the witness area, which have the same weight, thus it is actu=
ally a loss compared to Lamport.


So yes, maybe Winternitz (could be a replacement for the "trinary" Jeremy r=
efers to), Merkle not so much.

Regards,
ZmnSCPxj

> 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 coupl=
e kilobytes)... blocksize increase cough
> > Since a quantum computer can derive the EC privkey from the EC pubkey a=
nd this scheme is resistant to that, I think you can use a single well-know=
n EC privkey, you just need a unique Lamport keypair for each UTXO (uniquen=
ess 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=
 make Bitcoin "quantum safe" by signing an EC signature. This should work i=
n both Segwit V0 and Tapscript, although you have to use HASH160 for it to =
fit in Segwit V0.
> > > See my blog for the specific construction, reproduced below.
> > > Yet another entry to the "OP_CAT can do that too" list.
> > > Best,
> > >
> > > Jeremy
> > >
> > > -------
> > >
> > > I recently published a blogpost about signing up to a5 byte value usi=
ng 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 dige=
st which
> > > is most likely quantum safe...
> > > What would it mean if we signed the HASH160 digest of a signature? Wh=
at 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 crypt=
ographer
> > > Madars Virza if my intuition was correct, and he
> > > confirmed that it should be sufficient, but it's definitely worth clo=
ser
> > > analysis before relying on this. While the ECDSA signature can be mal=
leated to a
> > > different, negative form, if the signature is otherwise made immallea=
ble there
> > > should only be one value the commitment can be opened to.
> > > If we required the ECDSA signature be signed with a quantum proof sig=
nature
> > > algorithm, then we'd have a quantum proof Bitcoin! And the 5 byte sig=
ning scheme
> > > we discussed previously is a Lamport signature, which is quantum secu=
re.
> > > Unfortunately, we need at least 20 contiguous bytes... so we need som=
e sort of
> > > OP\_CAT like operation.
> > > OP\_CAT can't be directly soft forked to Segwit v0 because it modifie=
s the
> > > stack, so instead we'll (for simplicity) also show how to use a new o=
pcode 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 EL=
SE <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 DR=
OP DROP
> > >         ...  END FOR
> > >         DROP
> > >     ... END IF
> > >
> > >     <pk> CHECKSIG
> > >
> > >
> > > That's a long script... but will it fit? We need to verify 20 bytes o=
f message
> > > each bit takes around 10 bytes script, an average of 3.375 bytes per =
number
> > > (counting pushes), and two 21 bytes keys =3D 55.375 bytes of program =
space and 21
> > > bytes of witness element per bit.
> > > It fits! `20*8*55.375 =3D 8860`, which leaves 1140 bytes less than th=
e limit for
> > > the rest of the logic, which is plenty (around 15-40 bytes required f=
or the rest
> > > of the logic, leaving 1100 free for custom signature checking). The s=
tack size
> > > is 160 elements for the hash gadget, 3360 bytes.
> > > This can probably be made a bit more efficient by expanding to a tern=
ary
> > > 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 shoul=
d 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=
 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 =3D=
 pG + hash(pG || m)G`) can be securely opened to m even with a quantum comp=
uter (finding `q`
> > > such that `qG =3D Q` might be trivial, but suppose key path was disab=
led, then
> > > finding m and p such that the taproot equation holds should be diffic=
ult because
> > > of the hash, but I'd need to certify that claim better). Therefore th=
is
> > > 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 comi=
tted inside
> > > a taproot tree so that an address could be used for thousands of time=
s before
> > > expiring. This could be used as a measure to protect accidental use r=
ather than
> > > to support it.
> > > Lastly, Schnorr actually has a stronger non-malleability property tha=
n ECDSA,
> > > the signatures will be binding to the approved transaction and once L=
amport
> > > 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