Return-Path: Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137]) by lists.linuxfoundation.org (Postfix) with ESMTP id 9BC48C000E for ; Fri, 2 Jul 2021 22:20:31 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp4.osuosl.org (Postfix) with ESMTP id 7C4C642450 for ; Fri, 2 Jul 2021 22:20:31 +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 smtp4.osuosl.org ([127.0.0.1]) by localhost (smtp4.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id G5p7BJUbTwAX for ; Fri, 2 Jul 2021 22:20:30 +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 smtp4.osuosl.org (Postfix) with ESMTPS id B3B734244A for ; Fri, 2 Jul 2021 22:20:29 +0000 (UTC) Received: from mail-il1-f177.google.com (mail-il1-f177.google.com [209.85.166.177]) (authenticated bits=0) (User authenticated as jlrubin@ATHENA.MIT.EDU) by outgoing.mit.edu (8.14.7/8.12.4) with ESMTP id 162MKRDp017468 (version=TLSv1/SSLv3 cipher=AES128-GCM-SHA256 bits=128 verify=NOT) for ; Fri, 2 Jul 2021 18:20:28 -0400 Received: by mail-il1-f177.google.com with SMTP id g3so11123367ilj.7 for ; Fri, 02 Jul 2021 15:20:28 -0700 (PDT) X-Gm-Message-State: AOAM531kOk8QnFUQgLENkVFF/s/mICKzas5hJM+tOjm/IfVMEtEyJN9E HMwuI8O4FN+LVkaZLUOavtQXNAwl0CG2AE7tqIY= X-Google-Smtp-Source: ABdhPJxUNKzC1ONnmjRUidjBL/u7fmpkXvAAvZJ+fq4f4XlsP+BBDCHusa9Db034XQjvqZF3LJ64E8rvRMAMfOTFsOk= X-Received: by 2002:a05:6e02:1203:: with SMTP id a3mr1379472ilq.164.1625264427159; Fri, 02 Jul 2021 15:20:27 -0700 (PDT) MIME-Version: 1.0 From: Jeremy Date: Fri, 2 Jul 2021 15:20:16 -0700 X-Gmail-Original-Message-ID: Message-ID: To: Bitcoin development mailing list Content-Type: multipart/alternative; boundary="000000000000d8d76305c62b5cef" Subject: [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: Fri, 02 Jul 2021 22:20:31 -0000 --000000000000d8d76305c62b5cef Content-Type: text/plain; charset="UTF-8" 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 recall seeing it discussed elsewhere, but would be happy for a citation/reference 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 = sha256(preimage) if s == image_1: return (1 << idx) if s == image_0: return 0 else: assert False def get_signed_number(witnesses : List[Hash], keys : List[Tuple[Hash, Hash]]): acc = 0 for (idx, preimage) in enumerate(witnesses): acc += 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 ``` In order to sign a 16 bit value V, the owner of K simply puts on the stack the binary representation of V indexed into the K. E.g., to sign `53593`, first expand to binary `0b1101000101011001`, then put the appropriate K values on the stack. ``` K_15_1 K_14_1 K_13_0 K_12_1 K_11_0 K_10_0 K_9_0 K_8_1 K_7_0 K_6_1 K_5_0 K_4_1 K_3_1 K_2_0 K_1_0 K_0_1 ``` This technique is kind of bulky! It's around 80x16 = 1280 length for the gadget, and 528 bytes for the witnesses. So it is _doable_, if not a bit expensive. There might be some more efficient scripts for this -- would a trinary representation be more efficient? The values that can be signed can be range limited either post-hoc (using OP\_WITHIN) or internally as was done with the 16 bit value circuit where it's impossible to do more than 16 bits. Keys *can* be reused across scripts, but signatures may only be constructed one time because a third party could take two signed messages and construct an unintended value (e.g., if you sign both 4 and 2 then a third party could construct 6). There are certain applications where this could be used for an effect -- for example, an oracle might have a bonding contract whereby possessing any K\_i\_0 and K\_i\_1 allows the burning of funds. -- @JeremyRubin --000000000000d8d76305c62b5cef Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Dear Bitcoin Devs,
<= div class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif= ;font-size:small;color:#000000">
= 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 r= ecall seeing it discussed elsewhere, but would be happy for a citation/refe= rence to the technique.

blog post here, https://rubin.io/blog/2021/07/02/signing-5= -bytes/, text reproduced below=C2=A0

Ther= e are two insights in this post:

1. to use a bitwise expansion of th= e number
2. to use a lamport signature

Let's look at the cod= e in python and then translate to bitcoin script:

```python
def a= dd_bit(idx, preimage, image_0, image_1):
=C2=A0 =C2=A0 s =3D sha256(prei= mage)
=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], ke= ys : 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 generate= s 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 ma= tch one or the other.

During validation, the network adds up a weigh= ted 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 EN= DIF
SWAP sha256 DUP <H(K_1_1)> EQUAL IF DROP <1<<1> AD= D ELSE <H(K_1_0)> EQUALVERIFY ENDIF
SWAP sha256 DUP <H(K_2_1)&g= t; EQUAL IF DROP <1<<2> ADD ELSE <H(K_2_0)> EQUALVERIFY E= NDIF
SWAP sha256 DUP <H(K_3_1)> EQUAL IF DROP <1<<3> A= DD ELSE <H(K_3_0)> EQUALVERIFY ENDIF
SWAP sha256 DUP <H(K_4_1)&= gt; 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)> EQUALVERIF= Y 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)> EQUALV= ERIFY 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 DRO= P <1<<15> ADD ELSE <H(K_15_0)> EQUALVERIFY ENDIF
CHECK= SEQUENCEVERIFY
```

In order to sign a 16 bit value V, the owner o= f K simply puts on the stack the
binary representation of V indexed into= the K. E.g., to sign `53593`, first
expand to binary `0b110100010101100= 1`, then put the appropriate K values on the
stack.

```
K_15_1=
K_14_1
K_13_0
K_12_1
K_11_0
K_10_0
K_9_0
K_8_1
K_7= _0
K_6_1
K_5_0
K_4_1
K_3_1
K_2_0
K_1_0
K_0_1
<si= g>
```


This technique is kind of bulky! It's around 80= x16 =3D 1280 length for the
gadget, and 528 bytes for the witnesses. So = it is _doable_, if not a bit
expensive. There might be some more efficie= nt scripts for this -- would a
trinary representation be more efficient?=

The values that can be signed can be range limited either post-hoc= (using
OP\_WITHIN) or internally as was done with the 16 bit value circ= uit where it's
impossible to do more than 16 bits.

Keys *can*= be reused across scripts, but signatures may only be constructed one
ti= me because a third party could take two signed messages and construct anunintended value (e.g., if you sign both 4 and 2 then a third party could<= br>construct 6).

There are certain applications where this could be = used for an effect -- for
example, an oracle might have a bonding contra= ct whereby possessing any K\_i\_0
and K\_i\_1 allows the burning of fund= s.

<= /div>
--000000000000d8d76305c62b5cef--