path: root/0c/cab1f4528d5239c88ba09f3124779bbfc892bf

Return-Path: <jlrubin@mit.edu>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 9BC48C000E
 for <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>; Fri, 2 Jul 2021 18:20:28 -0400
Received: by mail-il1-f177.google.com with SMTP id g3so11123367ilj.7
 for <bitcoin-dev@lists.linuxfoundation.org>;
 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 <jlrubin@mit.edu>
Date: Fri, 2 Jul 2021 15:20:16 -0700
X-Gmail-Original-Message-ID: <CAD5xwhiqwqRjMboX8z_xapBq5=KOfP3eOSQzRcY-Cc7wq1gXUQ@mail.gmail.com>
Message-ID: <CAD5xwhiqwqRjMboX8z_xapBq5=KOfP3eOSQzRcY-Cc7wq1gXUQ@mail.gmail.com>
To: Bitcoin development mailing list <bitcoin-dev@lists.linuxfoundation.org>
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 <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: 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:


```
<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
```

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
<sig>
```


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 <https://twitter.com/JeremyRubin>
<https://twitter.com/JeremyRubin>

--000000000000d8d76305c62b5cef
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_default" style=3D"font-family:arial,he=
lvetica,sans-serif;font-size:small;color:#000000">Dear Bitcoin Devs,</div><=
div class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif=
;font-size:small;color:#000000"><br></div><div class=3D"gmail_default" styl=
e=3D"font-family:arial,helvetica,sans-serif;font-size:small;color:#000000">=
It recently occurred to me that it&#39;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&#39;t r=
ecall seeing it discussed elsewhere, but would be happy for a citation/refe=
rence to the technique.</div><div class=3D"gmail_default" style=3D"font-fam=
ily:arial,helvetica,sans-serif;font-size:small;color:#000000"><br></div><di=
v class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif;f=
ont-size:small;color:#000000">blog post here, <a href=3D"https://rubin.io/b=
log/2021/07/02/signing-5-bytes/">https://rubin.io/blog/2021/07/02/signing-5=
-bytes/</a>, text reproduced below<span class=3D"gmail-Apple-converted-spac=
e">=C2=A0</span><br></div><div class=3D"gmail_default" style=3D"font-family=
:arial,helvetica,sans-serif;font-size:small;color:#000000"><br></div><div c=
lass=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif;font=
-size:small;color:#000000"><span class=3D"gmail-Apple-converted-space">Ther=
e are two insights in this post:<br><br>1. to use a bitwise expansion of th=
e number <br>2. to use a lamport signature<br><br>Let&#39;s look at the cod=
e in python and then translate to bitcoin script:<br><br>```python<br>def a=
dd_bit(idx, preimage, image_0, image_1):<br>=C2=A0 =C2=A0 s =3D sha256(prei=
mage)<br>=C2=A0 =C2=A0 if s =3D=3D image_1:<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =
return (1 &lt;&lt; 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><br>def get_signed_number(witnesses : List[Hash], ke=
ys : 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><br>So what&#39;s going on here? The signer generate=
s a key which is a list of pairs of<br>hash images to create the script. <b=
r><br>To sign, the signer provides a witness of a list of preimages that ma=
tch one or the other.<br><br>During validation, the network adds up a weigh=
ted value per preimage and checks<br>that there are no left out values.<br>=
<br>Let&#39;s imagine a concrete use case: I want a third party to post-hoc=
 sign a sequence lock. This is 16 bits.<br>I can form the following script:=
<br><br><br>```<br>&lt;pk&gt; checksigverify<br>0<br>SWAP sha256 DUP &lt;H(=
K_0_1)&gt; EQUAL IF DROP &lt;1&gt; ADD ELSE &lt;H(K_0_0)&gt; EQUALVERIFY EN=
DIF<br>SWAP sha256 DUP &lt;H(K_1_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;1&gt; AD=
D ELSE &lt;H(K_1_0)&gt; EQUALVERIFY ENDIF<br>SWAP sha256 DUP &lt;H(K_2_1)&g=
t; EQUAL IF DROP &lt;1&lt;&lt;2&gt; ADD ELSE &lt;H(K_2_0)&gt; EQUALVERIFY E=
NDIF<br>SWAP sha256 DUP &lt;H(K_3_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;3&gt; A=
DD ELSE &lt;H(K_3_0)&gt; EQUALVERIFY ENDIF<br>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>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>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>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>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; EQUALVERIF=
Y ENDIF<br>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>SWAP sha256 DUP &lt;H(K_10=
_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;10&gt; ADD ELSE &lt;H(K_10_0)&gt; EQUALV=
ERIFY ENDIF<br>SWAP sha256 DUP &lt;H(K_11_1)&gt; EQUAL IF DROP &lt;1&lt;&lt=
;11&gt; ADD ELSE &lt;H(K_11_0)&gt; EQUALVERIFY ENDIF<br>SWAP sha256 DUP &lt=
;H(K_12_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;12&gt; ADD ELSE &lt;H(K_12_0)&gt;=
 EQUALVERIFY ENDIF<br>SWAP sha256 DUP &lt;H(K_13_1)&gt; EQUAL IF DROP &lt;1=
&lt;&lt;13&gt; ADD ELSE &lt;H(K_13_0)&gt; EQUALVERIFY ENDIF<br>SWAP sha256 =
DUP &lt;H(K_14_1)&gt; EQUAL IF DROP &lt;1&lt;&lt;14&gt; ADD ELSE &lt;H(K_14=
_0)&gt; EQUALVERIFY ENDIF<br>SWAP sha256 DUP &lt;H(K_15_1)&gt; EQUAL IF DRO=
P &lt;1&lt;&lt;15&gt; ADD ELSE &lt;H(K_15_0)&gt; EQUALVERIFY ENDIF<br>CHECK=
SEQUENCEVERIFY<br>```<br><br>In order to sign a 16 bit value V, the owner o=
f K simply puts on the stack the<br>binary representation of V indexed into=
 the K. E.g., to sign `53593`, first<br>expand to binary `0b110100010101100=
1`, then put the appropriate K values on the<br>stack.<br><br>```<br>K_15_1=
<br>K_14_1<br>K_13_0<br>K_12_1<br>K_11_0<br>K_10_0<br>K_9_0<br>K_8_1<br>K_7=
_0<br>K_6_1<br>K_5_0<br>K_4_1<br>K_3_1<br>K_2_0<br>K_1_0<br>K_0_1<br>&lt;si=
g&gt;<br>```<br><br><br>This technique is kind of bulky! It&#39;s around 80=
x16 =3D 1280 length for the<br>gadget, and 528 bytes for the witnesses. So =
it is _doable_, if not a bit<br>expensive. There might be some more efficie=
nt scripts for this -- would a<br>trinary representation be more efficient?=
 <br><br>The values that can be signed can be range limited either post-hoc=
 (using<br>OP\_WITHIN) or internally as was done with the 16 bit value circ=
uit where it&#39;s<br>impossible to do more than 16 bits.<br><br>Keys *can*=
 be reused across scripts, but signatures may only be constructed one<br>ti=
me because a third party could take two signed messages and construct an<br=
>unintended value (e.g., if you sign both 4 and 2 then a third party could<=
br>construct 6).<br><br>There are certain applications where this could be =
used for an effect -- for<br>example, an oracle might have a bonding contra=
ct whereby possessing any K\_i\_0<br>and K\_i\_1 allows the burning of fund=
s.<br></span></div><br clear=3D"all"><div><div dir=3D"ltr" class=3D"gmail_s=
ignature" data-smartmail=3D"gmail_signature"><div dir=3D"ltr">--<br><a href=
=3D"https://twitter.com/JeremyRubin" target=3D"_blank">@JeremyRubin</a><a h=
ref=3D"https://twitter.com/JeremyRubin" target=3D"_blank"></a></div></div><=
/div></div>

--000000000000d8d76305c62b5cef--