Return-Path: Received: from smtp2.osuosl.org (smtp2.osuosl.org [140.211.166.133]) by lists.linuxfoundation.org (Postfix) with ESMTP id 9B2D9C000E for ; 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 ; 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 ; 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 ; 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 ; Sat, 3 Jul 2021 00:01:14 -0400 Received: by mail-io1-f48.google.com with SMTP id y76so14064822iof.6 for ; 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: In-Reply-To: From: Jeremy Date: Fri, 2 Jul 2021 21:01:01 -0700 X-Gmail-Original-Message-ID: Message-ID: To: ZmnSCPxj Content-Type: multipart/alternative; boundary="0000000000008bd2e905c6301f7b" Cc: Bitcoin Protocol Discussion 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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: > > ``` > > checksigverify > > 0 > > SWAP sha256 DUP EQUAL IF DROP <1> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <1<<1> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <1<<2> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <1<<3> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <1<<4> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <1<<5> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <1<<6> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <1<<7> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <1<<8> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <1<<9> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <1<<10> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <1<<11> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <1<<12> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <1<<13> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <1<<14> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <1<<15> ADD ELSE > 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.... > > > ``` > > checksigverify > > 0 > > SWAP sha256 DUP EQUAL IF DROP <1> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <2> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <4> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <8> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <16> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <32> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <64> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <128> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <256> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <512> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <1024> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <2048> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <4096> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <8192> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <16384> ADD ELSE > EQUALVERIFY ENDIF > > SWAP sha256 DUP EQUAL IF DROP <32768> ADD ELSE > 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
Yep -- sorry for the confusing notation but seems like yo= u got it. C++ templates have this issue too btw :)

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.

There are a couple gotchas wrt crypto ass= umptions on that but I'll write it up soon =F0=9F=99=82 it also works b= etter 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 ZmnSCPx= j <ZmnSCPxj@protonmail.com> wrote:
Good morning Jeremy,
> Dear Bitcoin Devs,
>
> 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.
>
> blog post here, https://rubin.io/bl= og/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 scr= ipt:
> ```python
> def add_bit(idx, preimage, image_0, image_1):
> =C2=A0 =C2=A0 s =3D sha256(preimage)
> =C2=A0 =C2=A0 if s =3D=3D image_1:
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 return (1 << idx)
> =C2=A0 =C2=A0 if s =3D=3D image_0:
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 return 0
> =C2=A0 =C2=A0 else:
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 assert False
> def get_signed_number(witnesses : List[Hash], keys : List[Tuple[Hash, = Hash]]):
> =C2=A0 =C2=A0 acc =3D 0
> =C2=A0 =C2=A0 for (idx, preimage) in enumerate(witnesses):
> =C2=A0 =C2=A0 =C2=A0 =C2=A0 acc +=3D add_bit(idx, preimage, keys[idx][= 0], keys[idx][1])
> =C2=A0 =C2=A0 return x
> ```
> So what's going on here? The signer generates a key which is a lis= t of pairs of
> hash images to create the script.
> To sign, the signer provides a witness of a list of preimages that mat= ch one or the other.
> During validation, the network adds up a weighted value per preimage a= nd checks
> that there are no left out values.
> Let's imagine a concrete use case: I want a third party to post-ho= c 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> AD= D ELSE <H(K_10_0)> EQUALVERIFY ENDIF
> SWAP sha256 DUP <H(K_11_1)> EQUAL IF DROP <1<<11> AD= D ELSE <H(K_11_0)> EQUALVERIFY ENDIF
> SWAP sha256 DUP <H(K_12_1)> EQUAL IF DROP <1<<12> AD= D ELSE <H(K_12_0)> EQUALVERIFY ENDIF
> SWAP sha256 DUP <H(K_13_1)> EQUAL IF DROP <1<<13> AD= D ELSE <H(K_13_0)> EQUALVERIFY ENDIF
> SWAP sha256 DUP <H(K_14_1)> EQUAL IF DROP <1<<14> AD= D ELSE <H(K_14_0)> EQUALVERIFY ENDIF
> SWAP sha256 DUP <H(K_15_1)> EQUAL IF DROP <1<<15> AD= D 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 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....

> ```
> <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 &l= t;H(K_7_0)> EQUALVERIFY ENDIF
> SWAP sha256 DUP <H(K_8_1)> EQUAL IF DROP <256> ADD ELSE &l= t;H(K_8_0)> EQUALVERIFY ENDIF
> SWAP sha256 DUP <H(K_9_1)> EQUAL IF DROP <512> ADD ELSE &l= t;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_A= DD`, we can implement Lamport signatures for **arbitrary** values represent= able 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 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.

Regards,
ZmnSCPxj
--0000000000008bd2e905c6301f7b--