summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorErik Aronesty <erik@q32.com>2021-07-03 07:31:04 -0400
committerbitcoindev <bitcoindev@gnusha.org>2021-07-03 11:31:18 +0000
commit8f243eb49adbf82df0c6a7804091892dd6699f76 (patch)
tree36eaf81e1635a199e46e2397801cdd469a571503
parentc2d613e10326ee3a9ae59b78cafa231dfdabc877 (diff)
downloadpi-bitcoindev-8f243eb49adbf82df0c6a7804091892dd6699f76.tar.gz
pi-bitcoindev-8f243eb49adbf82df0c6a7804091892dd6699f76.zip
Re: [bitcoin-dev] CheckSigFromStack for Arithmetic Values
-rw-r--r--31/4e87511ecf3f367ec833e27105924a23fab0a4473
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&#39;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 &lt;<a href=3D"mailto:bitcoin-dev@li=
+sts.linuxfoundation.org">bitcoin-dev@lists.linuxfoundation.org</a>&gt; 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&#39;ll write it up soon =F0=9F=99=82 it also works better in se=
+gwit V0 because there&#39;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 &lt;<a =
+href=3D"mailto:ZmnSCPxj@protonmail.com" target=3D"_blank">ZmnSCPxj@protonma=
+il.com</a>&gt; 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>
+&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>
+_______________________________________________<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--
+