diff options
author | Erik Aronesty <erik@q32.com> | 2021-07-03 07:31:04 -0400 |
---|---|---|
committer | bitcoindev <bitcoindev@gnusha.org> | 2021-07-03 11:31:18 +0000 |
commit | 8f243eb49adbf82df0c6a7804091892dd6699f76 (patch) | |
tree | 36eaf81e1635a199e46e2397801cdd469a571503 | |
parent | c2d613e10326ee3a9ae59b78cafa231dfdabc877 (diff) | |
download | pi-bitcoindev-8f243eb49adbf82df0c6a7804091892dd6699f76.tar.gz pi-bitcoindev-8f243eb49adbf82df0c6a7804091892dd6699f76.zip |
Re: [bitcoin-dev] CheckSigFromStack for Arithmetic Values
-rw-r--r-- | 31/4e87511ecf3f367ec833e27105924a23fab0a4 | 473 |
1 files changed, 473 insertions, 0 deletions
diff --git a/31/4e87511ecf3f367ec833e27105924a23fab0a4 b/31/4e87511ecf3f367ec833e27105924a23fab0a4 new file mode 100644 index 000000000..3a3001405 --- /dev/null +++ b/31/4e87511ecf3f367ec833e27105924a23fab0a4 @@ -0,0 +1,473 @@ +Return-Path: <earonesty@gmail.com> +Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138]) + by lists.linuxfoundation.org (Postfix) with ESMTP id 6E84BC000E + for <bitcoin-dev@lists.linuxfoundation.org>; + Sat, 3 Jul 2021 11:31:18 +0000 (UTC) +Received: from localhost (localhost [127.0.0.1]) + by smtp1.osuosl.org (Postfix) with ESMTP id 69FF4842AD + for <bitcoin-dev@lists.linuxfoundation.org>; + Sat, 3 Jul 2021 11:31:18 +0000 (UTC) +X-Virus-Scanned: amavisd-new at osuosl.org +X-Spam-Flag: NO +X-Spam-Score: -1.402 +X-Spam-Level: +X-Spam-Status: No, score=-1.402 tagged_above=-999 required=5 + tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, + FREEMAIL_FORGED_FROMDOMAIN=0.248, FREEMAIL_FROM=0.001, + HEADER_FROM_DIFFERENT_DOMAINS=0.248, HTML_MESSAGE=0.001, + RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] + autolearn=no autolearn_force=no +Authentication-Results: smtp1.osuosl.org (amavisd-new); + dkim=pass (2048-bit key) header.d=q32-com.20150623.gappssmtp.com +Received: from smtp1.osuosl.org ([127.0.0.1]) + by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) + with ESMTP id mAfKWg6a-6VQ + for <bitcoin-dev@lists.linuxfoundation.org>; + Sat, 3 Jul 2021 11:31:17 +0000 (UTC) +X-Greylist: whitelisted by SQLgrey-1.8.0 +Received: from mail-pl1-x62e.google.com (mail-pl1-x62e.google.com + [IPv6:2607:f8b0:4864:20::62e]) + by smtp1.osuosl.org (Postfix) with ESMTPS id 07792842A6 + for <bitcoin-dev@lists.linuxfoundation.org>; + Sat, 3 Jul 2021 11:31:16 +0000 (UTC) +Received: by mail-pl1-x62e.google.com with SMTP id h6so6116985plf.11 + for <bitcoin-dev@lists.linuxfoundation.org>; + Sat, 03 Jul 2021 04:31:16 -0700 (PDT) +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=q32-com.20150623.gappssmtp.com; s=20150623; + h=mime-version:references:in-reply-to:from:date:message-id:subject:to + :cc; bh=azsXdPsborVQwAZWwSW5wTYeU69VnUjDpAJzoRzYgBA=; + b=iYvs1lPc0JPc7+XnDIL/G4c2ww2KufiG8NsOYT/u9PQv8Zo+xYJ8c5KB7QoeeBvpiX + 6ToiFXb66uT6bDwk7/edxhyH9Kj5b8F64By/3Zm3PuvK2PNgXQTKWXqx+0pcPfa/Jrn/ + mtZDE/sM1lk5j3Hqbg3e0E5R7cY979y9xVaAVU2bx9vjIB3nbsuvxD56LBkxX8Yk1Nnq + d6EQndJwxX5Hpq+vFrbazt8LHwAZfsVR20Z+gnY3aS+Nbmz92f9fBgtoXGgDrlOiYK6f + TnuDRya2PKX6m4e3KX6GV3tfVINwxsNkbLJ/fmjUZcYlFG1XsHhYTIE/XN/6S0GgYJu7 + F5MA== +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; + bh=azsXdPsborVQwAZWwSW5wTYeU69VnUjDpAJzoRzYgBA=; + b=pySjbL0PDtgitxhSZH1m8o2GnQ+ep/X2QyB7hxNcxLvvw4O+itZijav6QEdHrlcOK1 + UYtVkN1uLEonrtImhq8jyUHW77tvAItw/mTko1BMKHV7ZDvSmVp6GdkImS3UiCrUUNOm + S6eJ9oF2xnfHgRh4P+DP+w0IROs4Boo5E5mGjFuFo7iXtqwHbgRRwx2ypszZbHSAQkei + rDKAdTSQT8PHfxMN0yppxFfJv8W76fwhur6mJ05pdLIbc8WqeiS2CgnlakwsSBoJ2VsO + n4pC4ZhV0EKMpa9Y/dYGMBF/IGNHrtEsC81W3IOcNDGPn4jL3+jaWM1FFN3twJajzRvL + zl7g== +X-Gm-Message-State: AOAM533RcO9cNQaCg6yIqVD1pCAJLyj/vy4svefC1wx7Rz28exM7w9Kv + A4ZxJgs/XwuMRDceibswr8AdQ7PRPOj7WFixddSzcvw= +X-Google-Smtp-Source: ABdhPJwrEhF6o3UNoYw+k2/ix2iemz/8Iw9qweAohgg0gEnFLhlzvah/59I0zm8BqpDA8cjOqAsmgziVowvKIOSJRLw= +X-Received: by 2002:a17:902:f685:b029:129:4e14:6079 with SMTP id + l5-20020a170902f685b02901294e146079mr3718617plg.5.1625311875451; Sat, 03 Jul + 2021 04:31:15 -0700 (PDT) +MIME-Version: 1.0 +References: <CAD5xwhiqwqRjMboX8z_xapBq5=KOfP3eOSQzRcY-Cc7wq1gXUQ@mail.gmail.com> + <YEsEkExygpn5zEqfCXSt8duo9C0tgyx9YBTRejVn8ccwX2SQCPQVP5r2Nav6isQIbK8ED2Z-fYNwcN0VhXpxAIhCd3TWeU1et85cZFIVWdA=@protonmail.com> + <CAD5xwhggR_uC-Dx9S8kXj-j8L2EdXhmXdGmht05wC6nB3Xn_+w@mail.gmail.com> +In-Reply-To: <CAD5xwhggR_uC-Dx9S8kXj-j8L2EdXhmXdGmht05wC6nB3Xn_+w@mail.gmail.com> +From: Erik Aronesty <erik@q32.com> +Date: Sat, 3 Jul 2021 07:31:04 -0400 +Message-ID: <CAJowKgJxsknJ_TnQU1bvz3VyBHFaykXjDQAfsnxSzoeE1KJhbw@mail.gmail.com> +To: Jeremy <jlrubin@mit.edu>, + Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org> +Content-Type: multipart/alternative; boundary="000000000000fc4fc005c63668a6" +X-Mailman-Approved-At: Sat, 03 Jul 2021 11:38:11 +0000 +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 11:31:18 -0000 + +--000000000000fc4fc005c63668a6 +Content-Type: text/plain; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +i may be ignorant here but i have a question: + +Given that schnorr signatures now allow signers to perform complex +arithmetic signing operations out-of-band using their own communications +techniques, couldn't you just perform the publishing and accumulation of +these signature components without using a bitcoin script? + +In other words, push the effort of combination and computation off of the +bitcoin network and nodes. + + +On Sat, Jul 3, 2021 at 12:01 AM Jeremy via bitcoin-dev < +bitcoin-dev@lists.linuxfoundation.org> wrote: + +> 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 signatu= +re +> 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 keypath +> 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 signatur= +e +>> in script for arithmetic values by using a binary expanded representatio= +n. +>> There are some applications that might benefit from this and I don't rec= +all +>> seeing it discussed elsewhere, but would be happy for a citation/referen= +ce +>> 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 +>> match one or the other. +>> > During validation, the network adds up a weighted value per preimage +>> and checks +>> > that there are no left out values. +>> > Let's imagine a concrete use case: I want a third party to post-hoc +>> sign 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 mildl= +y +>> 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 (hop= +e?) +>> 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 muc= +h +>> 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 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 = +not +>> 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. +>> +>> Regards, +>> ZmnSCPxj +>> +> _______________________________________________ +> bitcoin-dev mailing list +> bitcoin-dev@lists.linuxfoundation.org +> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev +> + +--000000000000fc4fc005c63668a6 +Content-Type: text/html; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +<div dir=3D"ltr">i may be ignorant here but i have a question:<div><br></di= +v><div>Given that schnorr signatures now allow signers to perform complex a= +rithmetic signing operations out-of-band using their own communications tec= +hniques, couldn't you just perform the publishing and accumulation of t= +hese signature components without using a bitcoin script?</div><div><br></d= +iv><div>In other=C2=A0words, push the effort of combination and computation= + off of the bitcoin network and nodes.</div><div><br></div></div><br><div c= +lass=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">On Sat, Jul 3, 2= +021 at 12:01 AM Jeremy via bitcoin-dev <<a href=3D"mailto:bitcoin-dev@li= +sts.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>> wrot= +e:<br></div><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0= +.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir=3D"a= +uto">Yep -- sorry for the confusing notation but seems like you got it. C++= + templates have this issue too btw :)<div dir=3D"auto"><br></div><div dir= +=3D"auto">One cool thing is that if you have op_add for arbitrary width int= +egers or op_cat you can also make a quantum proof signature by signing 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 assumptions on= + that but I'll write it up soon =F0=9F=99=82 it also works better in se= +gwit V0 because there's no keypath spend -- that breaks the quantum pro= +ofness 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 ZmnSCPxj <<a = +href=3D"mailto:ZmnSCPxj@protonmail.com" target=3D"_blank">ZmnSCPxj@protonma= +il.com</a>> wrote:<br></div><blockquote class=3D"gmail_quote" style=3D"m= +argin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left= +:1ex">Good morning Jeremy,<br> +<br> +> Dear Bitcoin Devs,<br> +><br> +> It recently occurred to me that it'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= +9;t recall seeing it discussed elsewhere, but would be happy for a citation= +/reference to the technique.<br> +><br> +> 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> +><br> +> There are two insights in this post:<br> +> 1. to use a bitwise expansion of the number<br> +> 2. to use a lamport signature<br> +> Let's look at the code in python and then translate to bitcoin scr= +ipt:<br> +> ```python<br> +> def add_bit(idx, preimage, image_0, image_1):<br> +> =C2=A0 =C2=A0 s =3D sha256(preimage)<br> +> =C2=A0 =C2=A0 if s =3D=3D image_1:<br> +> =C2=A0 =C2=A0 =C2=A0 =C2=A0 return (1 << idx)<br> +> =C2=A0 =C2=A0 if s =3D=3D image_0:<br> +> =C2=A0 =C2=A0 =C2=A0 =C2=A0 return 0<br> +> =C2=A0 =C2=A0 else:<br> +> =C2=A0 =C2=A0 =C2=A0 =C2=A0 assert False<br> +> def get_signed_number(witnesses : List[Hash], keys : List[Tuple[Hash, = +Hash]]):<br> +> =C2=A0 =C2=A0 acc =3D 0<br> +> =C2=A0 =C2=A0 for (idx, preimage) in enumerate(witnesses):<br> +> =C2=A0 =C2=A0 =C2=A0 =C2=A0 acc +=3D add_bit(idx, preimage, keys[idx][= +0], keys[idx][1])<br> +> =C2=A0 =C2=A0 return x<br> +> ```<br> +> So what's going on here? The signer generates a key which is a lis= +t of pairs of<br> +> hash images to create the script.<br> +> To sign, the signer provides a witness of a list of preimages that mat= +ch one or the other.<br> +> During validation, the network adds up a weighted value per preimage a= +nd checks<br> +> that there are no left out values.<br> +> Let's imagine a concrete use case: I want a third party to post-ho= +c sign a sequence lock. This is 16 bits.<br> +> I can form the following script:<br> +> ```<br> +> <pk> checksigverify<br> +> 0<br> +> SWAP sha256 DUP <H(K_0_1)> EQUAL IF DROP <1> ADD ELSE <= +H(K_0_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_1_1)> EQUAL IF DROP <1<<1> ADD = +ELSE <H(K_1_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_2_1)> EQUAL IF DROP <1<<2> ADD = +ELSE <H(K_2_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_3_1)> EQUAL IF DROP <1<<3> ADD = +ELSE <H(K_3_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_4_1)> EQUAL IF DROP <1<<4> ADD = +ELSE <H(K_4_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_5_1)> EQUAL IF DROP <1<<5> ADD = +ELSE <H(K_5_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_6_1)> EQUAL IF DROP <1<<6> ADD = +ELSE <H(K_6_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_7_1)> EQUAL IF DROP <1<<7> ADD = +ELSE <H(K_7_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_8_1)> EQUAL IF DROP <1<<8> ADD = +ELSE <H(K_8_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_9_1)> EQUAL IF DROP <1<<9> ADD = +ELSE <H(K_9_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_10_1)> EQUAL IF DROP <1<<10> AD= +D ELSE <H(K_10_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_11_1)> EQUAL IF DROP <1<<11> AD= +D ELSE <H(K_11_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_12_1)> EQUAL IF DROP <1<<12> AD= +D ELSE <H(K_12_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_13_1)> EQUAL IF DROP <1<<13> AD= +D ELSE <H(K_13_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_14_1)> EQUAL IF DROP <1<<14> AD= +D ELSE <H(K_14_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_15_1)> EQUAL IF DROP <1<<15> AD= +D ELSE <H(K_15_0)> EQUALVERIFY ENDIF<br> +> CHECKSEQUENCEVERIFY<br> +> ```<br> +<br> +This took a bit of thinking to understand, mostly because you use the `<= +<` operator in a syntax that uses `< >` 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<<1` have also memorized the first few p= +owers of 2....<br> +<br> +> ```<br> +> <pk> checksigverify<br> +> 0<br> +> SWAP sha256 DUP <H(K_0_1)> EQUAL IF DROP <1> ADD ELSE <= +H(K_0_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_1_1)> EQUAL IF DROP <2> ADD ELSE <= +H(K_1_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_2_1)> EQUAL IF DROP <4> ADD ELSE <= +H(K_2_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_3_1)> EQUAL IF DROP <8> ADD ELSE <= +H(K_3_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_4_1)> EQUAL IF DROP <16> ADD ELSE <= +;H(K_4_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_5_1)> EQUAL IF DROP <32> ADD ELSE <= +;H(K_5_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_6_1)> EQUAL IF DROP <64> ADD ELSE <= +;H(K_6_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_7_1)> EQUAL IF DROP <128> ADD ELSE &l= +t;H(K_7_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_8_1)> EQUAL IF DROP <256> ADD ELSE &l= +t;H(K_8_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_9_1)> EQUAL IF DROP <512> ADD ELSE &l= +t;H(K_9_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_10_1)> EQUAL IF DROP <1024> ADD ELSE = +<H(K_10_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_11_1)> EQUAL IF DROP <2048> ADD ELSE = +<H(K_11_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_12_1)> EQUAL IF DROP <4096> ADD ELSE = +<H(K_12_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_13_1)> EQUAL IF DROP <8192> ADD ELSE = +<H(K_13_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_14_1)> EQUAL IF DROP <16384> ADD ELSE= + <H(K_14_0)> EQUALVERIFY ENDIF<br> +> SWAP sha256 DUP <H(K_15_1)> EQUAL IF DROP <32768> ADD ELSE= + <H(K_15_0)> EQUALVERIFY ENDIF<br> +> CHECKSEQUENCEVERIFY<br> +> ```<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 "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 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> +_______________________________________________<br> +bitcoin-dev mailing list<br> +<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">= +bitcoin-dev@lists.linuxfoundation.org</a><br> +<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" = +rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail= +man/listinfo/bitcoin-dev</a><br> +</blockquote></div> + +--000000000000fc4fc005c63668a6-- + |