summaryrefslogtreecommitdiff
path: root/f5/c6bb89e2fcb60f3faa55d98e147bbc15b3e42a
blob: 4710e562a9a7642629d68a2a9a75410a017b3301 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
Return-Path: <ZmnSCPxj@protonmail.com>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 3878EC000E
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  2 Jul 2021 23:58:25 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
 by smtp2.osuosl.org (Postfix) with ESMTP id 1ADD8400EF
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  2 Jul 2021 23:58:25 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.599
X-Spam-Level: 
X-Spam-Status: No, score=-1.599 tagged_above=-999 required=5
 tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
 DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
 FROM_LOCAL_NOVOWEL=0.5, RCVD_IN_MSPIKE_H4=0.001,
 RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001]
 autolearn=ham autolearn_force=no
Authentication-Results: smtp2.osuosl.org (amavisd-new);
 dkim=pass (1024-bit key) header.d=protonmail.com
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 cxKcX-Uv0pVK
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  2 Jul 2021 23:58:22 +0000 (UTC)
X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0
Received: from mail-40130.protonmail.ch (mail-40130.protonmail.ch
 [185.70.40.130])
 by smtp2.osuosl.org (Postfix) with ESMTPS id 9A75D40259
 for <bitcoin-dev@lists.linuxfoundation.org>;
 Fri,  2 Jul 2021 23:58:22 +0000 (UTC)
Date: Fri, 02 Jul 2021 23:58:14 +0000
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com;
 s=protonmail; t=1625270299;
 bh=BwmJK0ioikbQymotCRGL3brfF8yJ2QLMPQYm95+Elm8=;
 h=Date:To:From:Reply-To:Subject:In-Reply-To:References:From;
 b=FNzdIFNoCZvb+M/s1JC1hGY9a8clto8XQ/rBnJdl7swvsUjRJxA13CmvtSnvj3RBF
 W3dGuhm+srlYMaHE7exA2CIr6sH1JoyLYsJN9kNQDtKsv2+ECxmFnuGo0LCWiXWOqX
 fws3K0DLk1D+RsvAL8ybpGaqWsQWZDNk8vUysPy8=
To: Jeremy <jlrubin@mit.edu>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Reply-To: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <YEsEkExygpn5zEqfCXSt8duo9C0tgyx9YBTRejVn8ccwX2SQCPQVP5r2Nav6isQIbK8ED2Z-fYNwcN0VhXpxAIhCd3TWeU1et85cZFIVWdA=@protonmail.com>
In-Reply-To: <CAD5xwhiqwqRjMboX8z_xapBq5=KOfP3eOSQzRcY-Cc7wq1gXUQ@mail.gmail.com>
References: <CAD5xwhiqwqRjMboX8z_xapBq5=KOfP3eOSQzRcY-Cc7wq1gXUQ@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
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: Fri, 02 Jul 2021 23:58:25 -0000

Good morning Jeremy,

> Dear Bitcoin Devs,
>
> It recently occurred to me that it's possible to do a lamport signature i=
n script for arithmetic values by using a binary expanded representation. T=
here 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 r=
eproduced 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):
> =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, Has=
h]]):
> =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 list of pa=
irs 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)> EQUALVER=
IFY ENDIF
> SWAP sha256 DUP <H(K_1_1)> EQUAL IF DROP <1<<1> ADD ELSE <H(K_1_0)> EQUAL=
VERIFY ENDIF
> SWAP sha256 DUP <H(K_2_1)> EQUAL IF DROP <1<<2> ADD ELSE <H(K_2_0)> EQUAL=
VERIFY ENDIF
> SWAP sha256 DUP <H(K_3_1)> EQUAL IF DROP <1<<3> ADD ELSE <H(K_3_0)> EQUAL=
VERIFY ENDIF
> SWAP sha256 DUP <H(K_4_1)> EQUAL IF DROP <1<<4> ADD ELSE <H(K_4_0)> EQUAL=
VERIFY ENDIF
> SWAP sha256 DUP <H(K_5_1)> EQUAL IF DROP <1<<5> ADD ELSE <H(K_5_0)> EQUAL=
VERIFY ENDIF
> SWAP sha256 DUP <H(K_6_1)> EQUAL IF DROP <1<<6> ADD ELSE <H(K_6_0)> EQUAL=
VERIFY ENDIF
> SWAP sha256 DUP <H(K_7_1)> EQUAL IF DROP <1<<7> ADD ELSE <H(K_7_0)> EQUAL=
VERIFY ENDIF
> SWAP sha256 DUP <H(K_8_1)> EQUAL IF DROP <1<<8> ADD ELSE <H(K_8_0)> EQUAL=
VERIFY ENDIF
> SWAP sha256 DUP <H(K_9_1)> EQUAL IF DROP <1<<9> ADD ELSE <H(K_9_0)> EQUAL=
VERIFY ENDIF
> SWAP sha256 DUP <H(K_10_1)> EQUAL IF DROP <1<<10> ADD ELSE <H(K_10_0)> EQ=
UALVERIFY ENDIF
> SWAP sha256 DUP <H(K_11_1)> EQUAL IF DROP <1<<11> ADD ELSE <H(K_11_0)> EQ=
UALVERIFY ENDIF
> SWAP sha256 DUP <H(K_12_1)> EQUAL IF DROP <1<<12> ADD ELSE <H(K_12_0)> EQ=
UALVERIFY ENDIF
> SWAP sha256 DUP <H(K_13_1)> EQUAL IF DROP <1<<13> ADD ELSE <H(K_13_0)> EQ=
UALVERIFY ENDIF
> SWAP sha256 DUP <H(K_14_1)> EQUAL IF DROP <1<<14> ADD ELSE <H(K_14_0)> EQ=
UALVERIFY ENDIF
> SWAP sha256 DUP <H(K_15_1)> EQUAL IF DROP <1<<15> ADD ELSE <H(K_15_0)> EQ=
UALVERIFY 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 confus=
ing --- at first I thought you were pushing some kind of nested SCRIPT repr=
esentation, but in any case, replacing it with the actual numbers is a litt=
le 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....

> ```
> <pk> checksigverify
> 0
> SWAP sha256 DUP <H(K_0_1)> EQUAL IF DROP <1> ADD ELSE <H(K_0_0)> EQUALVER=
IFY ENDIF
> SWAP sha256 DUP <H(K_1_1)> EQUAL IF DROP <2> ADD ELSE <H(K_1_0)> EQUALVER=
IFY ENDIF
> SWAP sha256 DUP <H(K_2_1)> EQUAL IF DROP <4> ADD ELSE <H(K_2_0)> EQUALVER=
IFY ENDIF
> SWAP sha256 DUP <H(K_3_1)> EQUAL IF DROP <8> ADD ELSE <H(K_3_0)> EQUALVER=
IFY ENDIF
> SWAP sha256 DUP <H(K_4_1)> EQUAL IF DROP <16> ADD ELSE <H(K_4_0)> EQUALVE=
RIFY ENDIF
> SWAP sha256 DUP <H(K_5_1)> EQUAL IF DROP <32> ADD ELSE <H(K_5_0)> EQUALVE=
RIFY ENDIF
> SWAP sha256 DUP <H(K_6_1)> EQUAL IF DROP <64> ADD ELSE <H(K_6_0)> EQUALVE=
RIFY ENDIF
> SWAP sha256 DUP <H(K_7_1)> EQUAL IF DROP <128> ADD ELSE <H(K_7_0)> EQUALV=
ERIFY ENDIF
> SWAP sha256 DUP <H(K_8_1)> EQUAL IF DROP <256> ADD ELSE <H(K_8_0)> EQUALV=
ERIFY ENDIF
> SWAP sha256 DUP <H(K_9_1)> EQUAL IF DROP <512> ADD ELSE <H(K_9_0)> EQUALV=
ERIFY ENDIF
> SWAP sha256 DUP <H(K_10_1)> EQUAL IF DROP <1024> ADD ELSE <H(K_10_0)> EQU=
ALVERIFY ENDIF
> SWAP sha256 DUP <H(K_11_1)> EQUAL IF DROP <2048> ADD ELSE <H(K_11_0)> EQU=
ALVERIFY ENDIF
> SWAP sha256 DUP <H(K_12_1)> EQUAL IF DROP <4096> ADD ELSE <H(K_12_0)> EQU=
ALVERIFY ENDIF
> SWAP sha256 DUP <H(K_13_1)> EQUAL IF DROP <8192> ADD ELSE <H(K_13_0)> EQU=
ALVERIFY ENDIF
> SWAP sha256 DUP <H(K_14_1)> EQUAL IF DROP <16384> ADD ELSE <H(K_14_0)> EQ=
UALVERIFY ENDIF
> SWAP sha256 DUP <H(K_15_1)> EQUAL IF DROP <32768> ADD ELSE <H(K_15_0)> EQ=
UALVERIFY 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 s=
maller 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 to=
wards 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 much larger s=
ignature size, so Merkle sigs end up more expensive.

Regards,
ZmnSCPxj