MIME-Version: 1.0
References: <CAD5xwhgzR8e5r1e4H-5EH2mSsE1V39dd06+TgYniFnXFSBqLxw@mail.gmail.com>
 <MAfz2o3-uf5SfGKfMwONmT4TH4cmcAEJGyx21_dRQWBuCZZzFSXg38xyRY7HiMYMFB5zuTPorf_LYrnjE2K__uP578h7MZypf68yM0xjU3w=@protonmail.com>
 <CAEM=y+WkG9razw6uEhkXtNCgonaw2GHp9oGB3J7uf9N_JVdPoQ@mail.gmail.com>
 <XFMgrCKhdCuJ7LJ2KLv-r8dAGNs89H3NkvZgio5X6evKQ506p54HUF0hyxq0kQ48QeNJzmc--fy5keaSrzUQ7ylteCxe9TJNXnqJvaDy_X4=@protonmail.com>
In-Reply-To: <XFMgrCKhdCuJ7LJ2KLv-r8dAGNs89H3NkvZgio5X6evKQ506p54HUF0hyxq0kQ48QeNJzmc--fy5keaSrzUQ7ylteCxe9TJNXnqJvaDy_X4=@protonmail.com>
From: Ethan Heilman <eth3rs@gmail.com>
Date: Fri, 9 Jul 2021 19:25:06 -0400
Message-ID: <CAEM=y+U4EsS+gLyEqtxkG-8pEDtmMV8NEug5uQ_q0niwDHmkEw@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
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

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

Using depth 4 Winternitz would increase the number of instructions in
SCRIPT by 4*(signature bits/2) instructions, but decrease the
signature size by (signature bits/2) hash preimages. Given that
instructions are significantly smaller in size than the hash preimages
used, it seems like this would significantly reduce total size.

>Merkle signatures trade off shorter pubkeys for longer signatures (signatu=
res 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 act=
ually a loss compared to Lamport.

I wasn't proposing using plain merkle signatures, rather I was
thinking about something where if particular chunks of the message fit
a pattern you could release a seed higher in the commitment tree. For
instance 1,1,1 could be signed as by releasing H(01||H(01||H(01||x))),
 H(11||H(11||H(11||x))), H(21||H(21||H(21||x))), or by releasing X.
However, you would want to only release X in that one specific case
(1,1,1) but no others. Again this would bloat the SCRIPT and decrease
signature size but at a favorable ratio.

I am not convinced anyone should do these things, but they are fun to
think about and I suspect with more thought such signature sizes and
SCRIPT sizes could be even further reduced.

On Fri, Jul 9, 2021 at 6:38 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:
>
> Good morning Ethan,
>
> > > Yes, quite neat indeed, too bad Lamport signatures are so huge (a cou=
ple 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, wh=
ich is not available in SCRIPT, but may be emulatable with enough `OP_IF` a=
nd sheer brute force.
> But what you gain in smaller signatures, you lose in a more complex and l=
onger SCRIPT, and there are limits to SCRIPT size (in order to limit the pr=
ocessing done in each node).
>
> Merkle signatures trade off shorter pubkeys for longer signatures (signat=
ures need to provide the hash of the *other* preimage you are not revealing=
), but in the modern post-SegWit Bitcoin context both pubkeys and signature=
s are stored in the witness area, which have the same weight, thus it is ac=
tually a loss compared to Lamport.
>
>
> So yes, maybe Winternitz (could be a replacement for the "trinary" Jeremy=
 refers 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 cou=
ple 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-kn=
own EC privkey, you just need a unique Lamport keypair for each UTXO (uniqu=
eness 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=
 in both Segwit V0 and Tapscript, although you have to use HASH160 for it t=
o 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 u=
sing Bitcoin script arithmetic and Lamport signatures.
> > > > By itself, this is neat, but a little limited. What if we could sig=
n longer
> > > > messages? If we can sign up to 20 bytes, we could sign a HASH160 di=
gest 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 crac=
k ECDSA, it
> > > > would yield revealing the private key but not the ability to mallea=
te the
> > > > content of what was actually signed. I asked my good friend and cry=
ptographer
> > > > Madars Virza if my intuition was correct, and he
> > > > confirmed that it should be sufficient, but it's definitely worth c=
loser
> > > > analysis before relying on this. While the ECDSA signature can be m=
alleated to a
> > > > different, negative form, if the signature is otherwise made immall=
eable there
> > > > should only be one value the commitment can be opened to.
> > > > If we required the ECDSA signature be signed with a quantum proof s=
ignature
> > > > algorithm, then we'd have a quantum proof Bitcoin! And the 5 byte s=
igning scheme
> > > > we discussed previously is a Lamport signature, which is quantum se=
cure.
> > > > Unfortunately, we need at least 20 contiguous bytes... so we need s=
ome sort of
> > > > OP\_CAT like operation.
> > > > OP\_CAT can't be directly soft forked to Segwit v0 because it modif=
ies 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 splic=
e 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 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 pe=
r number
> > > > (counting pushes), and two 21 bytes keys =3D 55.375 bytes of progra=
m space 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=
 stack size
> > > > is 160 elements for the hash gadget, 3360 bytes.
> > > > This can probably be made a bit more efficient by expanding to a te=
rnary
> > > > 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 AD=
D  ENDIF ENDIF
> > > >
> > > >
> > > > This should bring it up to roughly 85 bytes per trit, and there sho=
uld 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 c=
omputer (finding `q`
> > > > such that `qG =3D Q` might be trivial, but suppose key path was dis=
abled, then
> > > > finding m and p such that the taproot equation holds should be diff=
icult 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 n=
ot impose a
> > > > length limit, 32 byte hashes could be used as well.
> > > > Further, to make keys reusable, there could be many Lamport keys co=
mitted inside
> > > > a taproot tree so that an address could be used for thousands of ti=
mes 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 t=
han ECDSA,
> > > > the signatures will be binding to the approved transaction and once=
 Lamport
> > > > 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
>
>