path: root/e8/99322939a597b79020edf958abf4192d1c75c4

Return-Path: <eth3rs@gmail.com>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 277B7C000E
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  9 Jul 2021 23:25:46 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp2.osuosl.org (Postfix) with ESMTP id 08BB240272
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  9 Jul 2021 23:25:46 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.1
X-Spam-Level: 
X-Spam-Status: No, score=-2.1 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 RCVD_IN_DNSWL_NONE=-0.0001, SPF_PASS=-0.001]
 autolearn=ham autolearn_force=no
Authentication-Results: smtp2.osuosl.org (amavisd-new);
 dkim=pass (2048-bit key) header.d=gmail.com
Received: from smtp2.osuosl.org ([127.0.0.1])
 by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
 with ESMTP id 7JBX4UzQSTF3
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  9 Jul 2021 23:25:44 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
Received: from mail-ed1-x52a.google.com (mail-ed1-x52a.google.com
 [IPv6:2a00:1450:4864:20::52a])
 by smtp2.osuosl.org (Postfix) with ESMTPS id 930B24015F
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  9 Jul 2021 23:25:44 +0000 (UTC)
Received: by mail-ed1-x52a.google.com with SMTP id v1so16197403edt.6
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 09 Jul 2021 16:25:44 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
 h=mime-version:references:in-reply-to:from:date:message-id:subject:to
 :cc:content-transfer-encoding;
 bh=l85IvvPuO+YkTJgFMR1IBr/bZpDuegKDME/neQkVzEg=;
 b=bqNa+T4L9XTdHtNczp4aOR5TpoRaD4xepZSGiBHV3UCEAOqkI4ZX9Rj01xCTD+SuYc
 dZjDHI1xhvJYffYT0aJ/l8WSlPnbGpX0fiBRf+P+ErCsO/NvuTh2IaJkTz6CMQ94LlFP
 dzqXXt5xO9d8a1xxACSUp5h3Ujczo7EVjadlBCVDlhJu6i/iazyQS933ggT+DPEq1SvJ
 GWPtyD5WOKBraFDer0keiC/PZrP1wxAgiyLwQ4+6rdH7JrmvzMdRBbYpuDRdQa4Kkf5u
 W4IJQcXCJLmv7+RBaOYdytTy7R6cCzNRY+y7YhrmM71C8Y4uJUDPNSDuud5kT+TENjUP
 fTLA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
 d=1e100.net; s=20161025;
 h=x-gm-message-state:mime-version:references:in-reply-to:from:date
 :message-id:subject:to:cc:content-transfer-encoding;
 bh=l85IvvPuO+YkTJgFMR1IBr/bZpDuegKDME/neQkVzEg=;
 b=XQmT9So4xiNV8M6RIRm2n2dqGmpsjU9fXnz4evqdHY1FrLZ4WUNazRHX1Tr1uj1AAh
 fI/sbsh+ekhX2f/PbutIEoYPTl0P7ADgqwG0VG8pokEOZk+jhQI1BFy5yyhijBbsjLwF
 on1hPMfDJaa2YHGUNRuglPf03WTuZh7V/eBdltceQ4GzgBn5toN+4Y+RVrm8pxjpIC/S
 8mThz6Lyq5hXczkI1PJ4eX0gePbj09tkwfL+QAvLVjtIfGS6khcdhwo6UJ5YJudGxqq4
 VG+bjDroYvTFrPjU0XS/aHaGf2gCBH0WYuniB8KsUTBCaldPsgWwp7khOK+WcWvtmhgP
 p8qg==
X-Gm-Message-State: AOAM532N4DL6KWyVlne9SkpCSGJrZlhifJgpZ5l/w4d/i3cRmw5M1qJ0
 4KaxT2u7UNE5nbZnPldeME3Qt6kzs5kz4/9XOig=
X-Google-Smtp-Source: ABdhPJzJ/Cljtbd0QxiW8oRGisHjPgQxca1DKhRadbTGEBuDdZ6loWen3dIG/xfomBsKWIVTjRfRdjzvUsAEZt2iGGo=
X-Received: by 2002:a05:6402:18c4:: with SMTP id
 x4mr21502231edy.350.1625873142745; 
 Fri, 09 Jul 2021 16:25:42 -0700 (PDT)
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]
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: Fri, 09 Jul 2021 23:25:46 -0000

>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
>
>