Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138]) by lists.linuxfoundation.org (Postfix) with ESMTP id 6E84BC000E for ; 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 ; 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 ; 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 ; Sat, 3 Jul 2021 11:31:16 +0000 (UTC) Received: by mail-pl1-x62e.google.com with SMTP id h6so6116985plf.11 for ; 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: In-Reply-To: From: Erik Aronesty Date: Sat, 3 Jul 2021 07:31:04 -0400 Message-ID: To: Jeremy , Bitcoin Protocol Discussion 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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: >> > ``` >> > 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 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.... >> >> > ``` >> > 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 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
i may be ignorant here but i have a question:

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?

In other=C2=A0words, push the effort of combination and computation= off of the bitcoin network and nodes.


On Sat, Jul 3, 2= 021 at 12:01 AM Jeremy via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> wrot= e:
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 int= egers or op_cat you can also make a quantum proof signature by signing the = signature made with checksig with the lamport.

<= /div>
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.

On Fri, Jul 2, 2021, 4:58 PM ZmnSCPxj <ZmnSCPxj@protonma= il.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
_______________________________________________
bitcoin-dev mailing list
= bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mail= man/listinfo/bitcoin-dev
--000000000000fc4fc005c63668a6--