path: root/75/2b0a16724c2b14a4fcb3f6506ff836b37530d9

Return-Path: <jlrubin@mit.edu>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 9B2D9C000E
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat,  3 Jul 2021 04:01:17 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp2.osuosl.org (Postfix) with ESMTP id 77CDB401C7
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat,  3 Jul 2021 04:01:17 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -4.2
X-Spam-Level: 
X-Spam-Status: No, score=-4.2 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_MED=-2.3,
 SPF_PASS=-0.001] autolearn=ham autolearn_force=no
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 9E_G6IBXda-O
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat,  3 Jul 2021 04:01:16 +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 smtp2.osuosl.org (Postfix) with ESMTPS id C87424018A
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Sat,  3 Jul 2021 04:01:15 +0000 (UTC)
Received: from mail-io1-f48.google.com (mail-io1-f48.google.com
 [209.85.166.48]) (authenticated bits=0)
 (User authenticated as jlrubin@ATHENA.MIT.EDU)
 by outgoing.mit.edu (8.14.7/8.12.4) with ESMTP id 16341D9X014406
 (version=TLSv1/SSLv3 cipher=AES128-GCM-SHA256 bits=128 verify=NOT)
 for <bitcoin-dev@lists.linuxfoundation.org>; Sat, 3 Jul 2021 00:01:14 -0400
Received: by mail-io1-f48.google.com with SMTP id y76so14064822iof.6
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri, 02 Jul 2021 21:01:14 -0700 (PDT)
X-Gm-Message-State: AOAM532RlhKFkrl4o2CHDU1FUDH+Oij1gCz/X3U5R30qDHG0GZMoeGbh
 u7ZQAr93Qn+ka1Krr4ab5FkvpBVuPa1FOZ9ywsY=
X-Google-Smtp-Source: ABdhPJweGeB24MJMYxoIykOfuvsJxBoa3EYDOfCGl3jmui7Yei133ix+ty/sp5f47Fz7O9MxlUoa2HgO42bpkdGdBXM=
X-Received: by 2002:a05:6602:89c:: with SMTP id
 f28mr2524819ioz.170.1625284873539; 
 Fri, 02 Jul 2021 21:01:13 -0700 (PDT)
MIME-Version: 1.0
References: <CAD5xwhiqwqRjMboX8z_xapBq5=KOfP3eOSQzRcY-Cc7wq1gXUQ@mail.gmail.com>
 <YEsEkExygpn5zEqfCXSt8duo9C0tgyx9YBTRejVn8ccwX2SQCPQVP5r2Nav6isQIbK8ED2Z-fYNwcN0VhXpxAIhCd3TWeU1et85cZFIVWdA=@protonmail.com>
In-Reply-To: <YEsEkExygpn5zEqfCXSt8duo9C0tgyx9YBTRejVn8ccwX2SQCPQVP5r2Nav6isQIbK8ED2Z-fYNwcN0VhXpxAIhCd3TWeU1et85cZFIVWdA=@protonmail.com>
From: Jeremy <jlrubin@mit.edu>
Date: Fri, 2 Jul 2021 21:01:01 -0700
X-Gmail-Original-Message-ID: <CAD5xwhggR_uC-Dx9S8kXj-j8L2EdXhmXdGmht05wC6nB3Xn_+w@mail.gmail.com>
Message-ID: <CAD5xwhggR_uC-Dx9S8kXj-j8L2EdXhmXdGmht05wC6nB3Xn_+w@mail.gmail.com>
To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Content-Type: multipart/alternative; boundary="0000000000008bd2e905c6301f7b"
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] 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: Sat, 03 Jul 2021 04:01:17 -0000

--0000000000008bd2e905c6301f7b
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

Yep -- sorry for the confusing notation but seems like you got it. C++
templates have this issue too btw :)

One cool thing is that if you have op_add for arbitrary width integers or
op_cat you can also make a quantum proof signature by signing the signature
made with checksig with the lamport.

There are a couple gotchas wrt crypto assumptions on that but I'll write it
up soon =F0=9F=99=82 it also works better in segwit V0 because there's no k=
eypath
spend -- that breaks the quantum proofness of this scheme.

On Fri, Jul 2, 2021, 4:58 PM ZmnSCPxj <ZmnSCPxj@protonmail.com> wrote:

> Good morning Jeremy,
>
> > Dear Bitcoin Devs,
> >
> > It recently occurred to me that it's possible to do a lamport signature
> in script for arithmetic values by using a binary expanded representation=
.
> There are some applications that might benefit from this and I don't reca=
ll
> seeing it discussed elsewhere, but would be happy for a citation/referenc=
e
> to the technique.
> >
> > blog post here, https://rubin.io/blog/2021/07/02/signing-5-bytes/, text
> reproduced below
> >
> > There are two insights in this post:
> > 1. to use a bitwise expansion of the number
> > 2. to use a lamport signature
> > Let's look at the code in python and then translate to bitcoin script:
> > ```python
> > def add_bit(idx, preimage, image_0, image_1):
> >     s =3D sha256(preimage)
> >     if s =3D=3D image_1:
> >         return (1 << idx)
> >     if s =3D=3D image_0:
> >         return 0
> >     else:
> >         assert False
> > def get_signed_number(witnesses : List[Hash], keys : List[Tuple[Hash,
> Hash]]):
> >     acc =3D 0
> >     for (idx, preimage) in enumerate(witnesses):
> >         acc +=3D add_bit(idx, preimage, keys[idx][0], keys[idx][1])
> >     return x
> > ```
> > So what's going on here? The signer generates a key which is a list of
> pairs of
> > hash images to create the script.
> > To sign, the signer provides a witness of a list of preimages that matc=
h
> one or the other.
> > During validation, the network adds up a weighted value per preimage an=
d
> checks
> > that there are no left out values.
> > Let's imagine a concrete use case: I want a third party to post-hoc sig=
n
> a sequence lock. This is 16 bits.
> > I can form the following script:
> > ```
> > <pk> checksigverify
> > 0
> > SWAP sha256 DUP <H(K_0_1)> EQUAL IF DROP <1> ADD ELSE <H(K_0_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_1_1)> EQUAL IF DROP <1<<1> ADD ELSE <H(K_1_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_2_1)> EQUAL IF DROP <1<<2> ADD ELSE <H(K_2_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_3_1)> EQUAL IF DROP <1<<3> ADD ELSE <H(K_3_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_4_1)> EQUAL IF DROP <1<<4> ADD ELSE <H(K_4_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_5_1)> EQUAL IF DROP <1<<5> ADD ELSE <H(K_5_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_6_1)> EQUAL IF DROP <1<<6> ADD ELSE <H(K_6_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_7_1)> EQUAL IF DROP <1<<7> ADD ELSE <H(K_7_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_8_1)> EQUAL IF DROP <1<<8> ADD ELSE <H(K_8_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_9_1)> EQUAL IF DROP <1<<9> ADD ELSE <H(K_9_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_10_1)> EQUAL IF DROP <1<<10> ADD ELSE <H(K_10_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_11_1)> EQUAL IF DROP <1<<11> ADD ELSE <H(K_11_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_12_1)> EQUAL IF DROP <1<<12> ADD ELSE <H(K_12_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_13_1)> EQUAL IF DROP <1<<13> ADD ELSE <H(K_13_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_14_1)> EQUAL IF DROP <1<<14> ADD ELSE <H(K_14_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_15_1)> EQUAL IF DROP <1<<15> ADD ELSE <H(K_15_0)>
> EQUALVERIFY ENDIF
> > CHECKSEQUENCEVERIFY
> > ```
>
> This took a bit of thinking to understand, mostly because you use the `<<=
`
> operator in a syntax that uses `< >` as delimiters, which was mildly
> confusing --- at first I thought you were pushing some kind of nested
> SCRIPT representation, but in any case, replacing it with the actual
> numbers is a little less confusing on the syntax front, and I think (hope=
?)
> most people who can understand `1<<1` have also memorized the first few
> powers of 2....
>
> > ```
> > <pk> checksigverify
> > 0
> > SWAP sha256 DUP <H(K_0_1)> EQUAL IF DROP <1> ADD ELSE <H(K_0_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_1_1)> EQUAL IF DROP <2> ADD ELSE <H(K_1_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_2_1)> EQUAL IF DROP <4> ADD ELSE <H(K_2_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_3_1)> EQUAL IF DROP <8> ADD ELSE <H(K_3_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_4_1)> EQUAL IF DROP <16> ADD ELSE <H(K_4_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_5_1)> EQUAL IF DROP <32> ADD ELSE <H(K_5_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_6_1)> EQUAL IF DROP <64> ADD ELSE <H(K_6_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_7_1)> EQUAL IF DROP <128> ADD ELSE <H(K_7_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_8_1)> EQUAL IF DROP <256> ADD ELSE <H(K_8_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_9_1)> EQUAL IF DROP <512> ADD ELSE <H(K_9_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_10_1)> EQUAL IF DROP <1024> ADD ELSE <H(K_10_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_11_1)> EQUAL IF DROP <2048> ADD ELSE <H(K_11_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_12_1)> EQUAL IF DROP <4096> ADD ELSE <H(K_12_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_13_1)> EQUAL IF DROP <8192> ADD ELSE <H(K_13_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_14_1)> EQUAL IF DROP <16384> ADD ELSE <H(K_14_0)>
> EQUALVERIFY ENDIF
> > SWAP sha256 DUP <H(K_15_1)> EQUAL IF DROP <32768> ADD ELSE <H(K_15_0)>
> EQUALVERIFY ENDIF
> > CHECKSEQUENCEVERIFY
> > ```
>
> On the other hand LOL WTF, this is cool.
>
> Basically you are showing that if we enable something as innocuous as
> `OP_ADD`, we can implement Lamport signatures for **arbitrary** values
> representable in small binary numbers (16 bits in the above example).
>
> I was thinking "why not Merkle signatures" since the pubkey would be much
> smaller but the signature would be much larger, but (a) the SCRIPT would =
be
> much more complicated and (b) in modern Bitcoin, the above SCRIPT would b=
e
> in the witness stack anyway so there is no advantage to pushing the size
> towards the signature rather than the pubkey, they all have the same
> weight, and since both Lamport and Merkle are single-use-only and we do n=
ot
> want to encourage pubkey reuse even if they were not, the Merkle has much
> larger signature size, so Merkle sigs end up more expensive.
>
> Regards,
> ZmnSCPxj
>

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

<div dir=3D"auto">Yep -- sorry for the confusing notation but seems like yo=
u got it. C++ templates have this issue too btw :)<div dir=3D"auto"><br></d=
iv><div dir=3D"auto">One cool thing is that if you have op_add for arbitrar=
y width integers or op_cat you can also make a quantum proof signature by s=
igning the signature made with checksig with the lamport.</div><div dir=3D"=
auto"><br></div><div dir=3D"auto">There are a couple gotchas wrt crypto ass=
umptions on that but I&#39;ll write it up soon =F0=9F=99=82 it also works b=
etter in segwit V0 because there&#39;s no keypath spend -- that breaks the =
quantum proofness of this scheme.</div></div><br><div class=3D"gmail_quote"=
><div dir=3D"ltr" class=3D"gmail_attr">On Fri, Jul 2, 2021, 4:58 PM ZmnSCPx=
j &lt;<a href=3D"mailto:ZmnSCPxj@protonmail.com">ZmnSCPxj@protonmail.com</a=
>&gt; wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0 0=
 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Good morning Jeremy,<b=
r>
<br>
&gt; Dear Bitcoin Devs,<br>
&gt;<br>
&gt; It recently occurred to me that it&#39;s possible to do a lamport sign=
ature in script for arithmetic values by using a binary expanded representa=
tion. There are some applications that might benefit from this and I don&#3=
9;t recall seeing it discussed elsewhere, but would be happy for a citation=
/reference to the technique.<br>
&gt;<br>
&gt; blog post here, <a href=3D"https://rubin.io/blog/2021/07/02/signing-5-=
bytes/" rel=3D"noreferrer noreferrer" target=3D"_blank">https://rubin.io/bl=
og/2021/07/02/signing-5-bytes/</a>, text reproduced below<br>
&gt;<br>
&gt; There are two insights in this post:<br>
&gt; 1. to use a bitwise expansion of the number<br>
&gt; 2. to use a lamport signature<br>
&gt; Let&#39;s look at the code in python and then translate to bitcoin scr=
ipt:<br>
&gt; ```python<br>
&gt; def add_bit(idx, preimage, image_0, image_1):<br>
&gt; =C2=A0 =C2=A0 s =3D sha256(preimage)<br>
&gt; =C2=A0 =C2=A0 if s =3D=3D image_1:<br>
&gt; =C2=A0 =C2=A0 =C2=A0 =C2=A0 return (1 &lt;&lt; idx)<br>
&gt; =C2=A0 =C2=A0 if s =3D=3D image_0:<br>
&gt; =C2=A0 =C2=A0 =C2=A0 =C2=A0 return 0<br>
&gt; =C2=A0 =C2=A0 else:<br>
&gt; =C2=A0 =C2=A0 =C2=A0 =C2=A0 assert False<br>
&gt; def get_signed_number(witnesses : List[Hash], keys : List[Tuple[Hash, =
Hash]]):<br>
&gt; =C2=A0 =C2=A0 acc =3D 0<br>
&gt; =C2=A0 =C2=A0 for (idx, preimage) in enumerate(witnesses):<br>
&gt; =C2=A0 =C2=A0 =C2=A0 =C2=A0 acc +=3D add_bit(idx, preimage, keys[idx][=
0], keys[idx][1])<br>
&gt; =C2=A0 =C2=A0 return x<br>
&gt; ```<br>
&gt; So what&#39;s going on here? The signer generates a key which is a lis=
t of pairs of<br>
&gt; hash images to create the script.<br>
&gt; To sign, the signer provides a witness of a list of preimages that mat=
ch one or the other.<br>
&gt; During validation, the network adds up a weighted value per preimage a=
nd checks<br>
&gt; that there are no left out values.<br>
&gt; Let&#39;s imagine a concrete use case: I want a third party to post-ho=
c sign a sequence lock. This is 16 bits.<br>
&gt; I can form the following script:<br>
&gt; ```<br>
&gt; &lt;pk&gt; checksigverify<br>
&gt; 0<br>
&gt; SWAP sha256 DUP &lt;H(K_0_1)&gt; EQUAL IF DROP &lt;1&gt; ADD ELSE &lt;=
H(K_0_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_1_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;1&gt; ADD =
ELSE &lt;H(K_1_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_2_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;2&gt; ADD =
ELSE &lt;H(K_2_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_3_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;3&gt; ADD =
ELSE &lt;H(K_3_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_4_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;4&gt; ADD =
ELSE &lt;H(K_4_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_5_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;5&gt; ADD =
ELSE &lt;H(K_5_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_6_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;6&gt; ADD =
ELSE &lt;H(K_6_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_7_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;7&gt; ADD =
ELSE &lt;H(K_7_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_8_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;8&gt; ADD =
ELSE &lt;H(K_8_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_9_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;9&gt; ADD =
ELSE &lt;H(K_9_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_10_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;10&gt; AD=
D ELSE &lt;H(K_10_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_11_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;11&gt; AD=
D ELSE &lt;H(K_11_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_12_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;12&gt; AD=
D ELSE &lt;H(K_12_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_13_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;13&gt; AD=
D ELSE &lt;H(K_13_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_14_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;14&gt; AD=
D ELSE &lt;H(K_14_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_15_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;15&gt; AD=
D ELSE &lt;H(K_15_0)&gt; EQUALVERIFY ENDIF<br>
&gt; CHECKSEQUENCEVERIFY<br>
&gt; ```<br>
<br>
This took a bit of thinking to understand, mostly because you use the `&lt;=
&lt;` operator in a syntax that uses `&lt; &gt;` as delimiters, which was m=
ildly confusing --- at first I thought you were pushing some kind of nested=
 SCRIPT representation, but in any case, replacing it with the actual numbe=
rs is a little less confusing on the syntax front, and I think (hope?) most=
 people who can understand `1&lt;&lt;1` have also memorized the first few p=
owers of 2....<br>
<br>
&gt; ```<br>
&gt; &lt;pk&gt; checksigverify<br>
&gt; 0<br>
&gt; SWAP sha256 DUP &lt;H(K_0_1)&gt; EQUAL IF DROP &lt;1&gt; ADD ELSE &lt;=
H(K_0_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_1_1)&gt; EQUAL IF DROP &lt;2&gt; ADD ELSE &lt;=
H(K_1_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_2_1)&gt; EQUAL IF DROP &lt;4&gt; ADD ELSE &lt;=
H(K_2_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_3_1)&gt; EQUAL IF DROP &lt;8&gt; ADD ELSE &lt;=
H(K_3_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_4_1)&gt; EQUAL IF DROP &lt;16&gt; ADD ELSE &lt=
;H(K_4_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_5_1)&gt; EQUAL IF DROP &lt;32&gt; ADD ELSE &lt=
;H(K_5_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_6_1)&gt; EQUAL IF DROP &lt;64&gt; ADD ELSE &lt=
;H(K_6_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_7_1)&gt; EQUAL IF DROP &lt;128&gt; ADD ELSE &l=
t;H(K_7_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_8_1)&gt; EQUAL IF DROP &lt;256&gt; ADD ELSE &l=
t;H(K_8_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_9_1)&gt; EQUAL IF DROP &lt;512&gt; ADD ELSE &l=
t;H(K_9_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_10_1)&gt; EQUAL IF DROP &lt;1024&gt; ADD ELSE =
&lt;H(K_10_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_11_1)&gt; EQUAL IF DROP &lt;2048&gt; ADD ELSE =
&lt;H(K_11_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_12_1)&gt; EQUAL IF DROP &lt;4096&gt; ADD ELSE =
&lt;H(K_12_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_13_1)&gt; EQUAL IF DROP &lt;8192&gt; ADD ELSE =
&lt;H(K_13_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_14_1)&gt; EQUAL IF DROP &lt;16384&gt; ADD ELSE=
 &lt;H(K_14_0)&gt; EQUALVERIFY ENDIF<br>
&gt; SWAP sha256 DUP &lt;H(K_15_1)&gt; EQUAL IF DROP &lt;32768&gt; ADD ELSE=
 &lt;H(K_15_0)&gt; EQUALVERIFY ENDIF<br>
&gt; CHECKSEQUENCEVERIFY<br>
&gt; ```<br>
<br>
On the other hand LOL WTF, this is cool.<br>
<br>
Basically you are showing that if we enable something as innocuous as `OP_A=
DD`, we can implement Lamport signatures for **arbitrary** values represent=
able in small binary numbers (16 bits in the above example).<br>
<br>
I was thinking &quot;why not Merkle signatures&quot; since the pubkey would=
 be much smaller but the signature would be much larger, but (a) the SCRIPT=
 would be much more complicated and (b) in modern Bitcoin, the above SCRIPT=
 would be in the witness stack anyway so there is no advantage to pushing t=
he size towards the signature rather than the pubkey, they all have the sam=
e weight, and since both Lamport and Merkle are single-use-only and we do n=
ot want to encourage pubkey reuse even if they were not, the Merkle has muc=
h larger signature size, so Merkle sigs end up more expensive.<br>
<br>
Regards,<br>
ZmnSCPxj<br>
</blockquote></div>

--0000000000008bd2e905c6301f7b--