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
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
|
Return-Path: <salvatore.ingala@gmail.com>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136])
by lists.linuxfoundation.org (Postfix) with ESMTP id 9290EC002D
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 1 Dec 2022 08:47:37 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp3.osuosl.org (Postfix) with ESMTP id 6DBCE60E02
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 1 Dec 2022 08:47:37 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 6DBCE60E02
Authentication-Results: smtp3.osuosl.org;
dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
header.a=rsa-sha256 header.s=20210112 header.b=k/ZDILkK
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.098
X-Spam-Level:
X-Spam-Status: No, score=-2.098 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,
HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001,
SPF_PASS=-0.001] autolearn=ham autolearn_force=no
Received: from smtp3.osuosl.org ([127.0.0.1])
by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id veMXmumAd5N4
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 1 Dec 2022 08:47:36 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.8.0
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 188C360C05
Received: from mail-lf1-x134.google.com (mail-lf1-x134.google.com
[IPv6:2a00:1450:4864:20::134])
by smtp3.osuosl.org (Postfix) with ESMTPS id 188C360C05
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 1 Dec 2022 08:47:36 +0000 (UTC)
Received: by mail-lf1-x134.google.com with SMTP id bp15so1396396lfb.13
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 01 Dec 2022 00:47:35 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112;
h=to:subject:message-id:date:from:in-reply-to:references:mime-version
:from:to:cc:subject:date:message-id:reply-to;
bh=lI47GJAoyHjkvKC8TjDiSqNz9giQlUTaHdrUwjT3yWo=;
b=k/ZDILkKnqIEPWa9MLwPdfmH1LWNh3Nu3yz/lysTh5Sp3V7NytNU2y6aOOwUloLqSm
YlVkKpMyeAcvY7I88DBlm+qORz3IND3XAwRZJTE8bLaWTi15BGHEOFaWSSTNAeFV5ioH
mmRaeAxGfxL/It0iMy3pCSDnGPjpdEf3lg5bUUiPSjI4PmX0+qVwvSNzj0h8pSUMpFv3
Jg3mSEb2a8LQzRXpXHKt3XtKx25DJbkheIDArasINMNuQ9XabCrT+KdV/Lq+5z7fCp1M
U7/6S2znW2kkMZAqEBgnRe3b0b++sD9isRc7DsT8j2RAA4gbKWr2g5ohj03XBaU9wGFG
YHTA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20210112;
h=to:subject:message-id:date:from:in-reply-to:references:mime-version
:x-gm-message-state:from:to:cc:subject:date:message-id:reply-to;
bh=lI47GJAoyHjkvKC8TjDiSqNz9giQlUTaHdrUwjT3yWo=;
b=zmX6xrC0zswfo+eDM4qWrLif7rX4iz6o0HnLN0jtk7cE6ah9QQ/SWjVs3W70oveVc1
AECLIzCWKck3aJmGk5v26kBkm7XiMU7wn4y79mtZo4rvJQXVpMqqhKM8qrrPzeeq1KSv
dW7Gt+/G/HcMxz6jl/dkR9ms9BILKryq8GbJ0q/06cSfTkoZ4OYItQ/Z5QvRa2F43q1u
woGNScz/ui/SggruKQ8L0cD3mkJZEqROenr5AFMdbMBXhb9ykkxm1nkSP7b0iK9fNuKG
RUmerVvg9itg7hLw9DPFGC8emOcBaN4J6mx8TVpD1PUE2PtEh47PIhpawPuQnj8yGAoY
sm+Q==
X-Gm-Message-State: ANoB5pl9e+zyeDIk/qVuzkBQ9TLvVqZx20gnEv6s67sEpgQ/0u0YoN9Q
Z93gkaQKCFTs8tfDZwgDt5+VNXHxH0MwkvX3cff6n9ICgzk=
X-Google-Smtp-Source: AA0mqf7c25d6B3wRxavhxemfU4N8c/3Gcm+3utGeS0J9MwgmAJEzcjco5JKsyg9Yfm0YVZ+AwhCrZVHg1axhhNgxTCs=
X-Received: by 2002:a19:435c:0:b0:4b0:38f1:1784 with SMTP id
m28-20020a19435c000000b004b038f11784mr14697454lfj.335.1669884453390; Thu, 01
Dec 2022 00:47:33 -0800 (PST)
MIME-Version: 1.0
References: <CAMhCMoH9uZPeAE_2tWH6rf0RndqV+ypjbNzazpFwFnLUpPsZ7g@mail.gmail.com>
<CALZpt+GVe0XTdWqV=LAcOj=nq+k2DEFqc+sKyxAujLDBR7bYbQ@mail.gmail.com>
<CAMhCMoEONv3jriBU3qwm0pt75iF_sgra1H2Z4rOF8u+e7hs_cw@mail.gmail.com>
<0f352f70-c93a-614f-e443-67d198ec2c26@protonmail.com>
<7f3674d1-c1ad-9a82-e30f-7cf24d697faf@protonmail.com>
In-Reply-To: <7f3674d1-c1ad-9a82-e30f-7cf24d697faf@protonmail.com>
From: Salvatore Ingala <salvatore.ingala@gmail.com>
Date: Thu, 1 Dec 2022 09:47:22 +0100
Message-ID: <CAMhCMoGabEASO9CGc1hAMpYZn4nWH5D8XFs3eFcSSFAitSFUGA@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>,
Rijndael <rot13maxi@protonmail.com>
Content-Type: multipart/alternative; boundary="000000000000a90efd05eec04528"
X-Mailman-Approved-At: Thu, 01 Dec 2022 11:52:14 +0000
Subject: Re: [bitcoin-dev] Merkleize All The Things
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: Thu, 01 Dec 2022 08:47:37 -0000
--000000000000a90efd05eec04528
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Hello Rijndael,
On Wed, 30 Nov 2022 at 23:09, Rijndael <rot13maxi@protonmail.com> wrote:
> Hello Salvatore,
>
> I found my answer re-reading your original post:
> > During the arbitration phase (say at the i-th leaf node of M_T), any
> party can win the challenge by providing correct values for tr_i =3D (st_=
i,
> op_i, st_{i + 1}). Crucially, only one party is able to provide correct
> values, and Script can verify that indeed the state moves from st_i to
> st_{i + 1} by executing op_i. The challenge is over.
>
You are correct, the computation step encoded in a leaf needs to be simple
enough for Script to verify it.
For the academic purpose of proving completeness (that is, any computation
can be successfully "proved" by the availability of the corresponding fraud
proof), one can imagine reducing the computation all the way down to a
circuit, where each step (leaf) is as simple as what can be checked with
{OP_NOT, OP_BOOLAND, OP_BOOLOR, OP_EQUAL}.
In practice, you would want to utilize Script to its fullest, so for
example you wouldn't compile a SHA256 computation to something else =E2=80=
=93 you'd
rather use OP_SHA256 directly.
> That raises leads to a different question: Alice initially posts a
> commitment to an execution trace of `f(x) =3D y`, `x`, and `y`. Bob Disag=
rees
> with `y` so starts the challenge protocol. Is there a commitment to `f`? =
In
> other words, the dispute protocol (as I read it) finds the leftmost step =
in
> Alice and Bob's execution traces that differ, and then rewards the coins =
to
> the participant who's "after-value" is computed by the step's operation
> applied to the "before value". But if the participants each present valid
> steps but with different operations, who wins? In other words, Alice coul=
d
> present [64, DECREMENT, 63] and Bob could present [64, INCREMENT, 65].
> Those steps don't match, but both are valid. Is there something to ensure
> that before the challenge protocol starts, that the execution trace that
> Alice posts is for the right computation and not a different computation
> that yields a favorable result for her (and for which she can generate a
> valid merkle tree)?
>
The function f is already hard-coded in the contract itself, by means of
the tree of scripts =E2=88=92 that already commits to the possible futures.
Therefore, once you are at state S14, you know that you are verifying the
6th step of the computation; and the operation in the 6th step of the
computation depends solely on f, not its inputs. In fact, you made me
realize that I could drop op_i from the i-th leaf commitment, and just
embed the information in the Script of that corresponding state.
Note that the states S0 to S14 of the 256x game are not _all_ the possible
states, but only the ones that occurred in that execution of the contract
(corresponding to a path from the root to the leaf of the Merkle tree of
the computation trace), and therefore the ones that materialized in a UTXO.
Different choices made by the parties (by providing different data, and
therefore choosing different branches) would lead to a different leaf, and
therefore to different (but in a certain sense "symmetric") states.
=3D=3D=3D=3D=3D=3D=3D=3D
Since we are talking about the fact that f is committed to in the contract,
I'll take the chance to extend on this a bit with a fun construction on top=
.
It is well-known in the academic literature of state channels that you can
create contracts where even the function ("program", or "contract") is not
decided when the channel is created.
Since f is generic, we can choose f itself to be a universal Turing
machine. That is, we can imagine a function f(code, data) that executes a
program ("code") on the "data" given to it as input.
Since we can do fraud proofs on statements "f(code, data) =3D=3D output", w=
e
could build contracts where the "code" itself is chosen later.
For example, one could build a universal state channel, where parties can
enter any contract among themselves (e.g.: start playing a chess game)
entirely inside the channel. The state of this universal channel would
contain all the states of the individual contracts that are currently open
in the channel, and even starting/closing contracts can happen entirely
off-chain.
I believe these constructions are practical (the code of universal Turing
machines is not really complicated), so it might be worth exploring further
to figure out useful applications of this approach (supercharging
lightning?).
We should probably start by implementing testnet rock-paper-scissors in
MATT, though :)
Best,
Salvatore Ingala
--000000000000a90efd05eec04528
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div dir=3D"ltr">Hello Rijndael,<div><br></div><div><br></=
div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_at=
tr">On Wed, 30 Nov 2022 at 23:09, Rijndael <<a href=3D"mailto:rot13maxi@=
protonmail.com">rot13maxi@protonmail.com</a>> wrote:<br></div><blockquot=
e class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px s=
olid rgb(204,204,204);padding-left:1ex">
=20
=20
<div>
<p>Hello Salvatore,</p>
<p>I found my answer re-reading your original post:<br>
> During the arbitration phase (say at the i-th leaf node of
M_T), any party can win the challenge by providing correct values
for tr_i =3D (st_i, op_i, st_{i + 1}). Crucially, only one party is
able to provide correct values, and Script can verify that indeed
the state moves from st_i to st_{i + 1} by executing op_i. The
challenge is over.</p></div></blockquote><div><div>You are correct, t=
he computation step encoded in a leaf needs to be simple enough for Script =
to verify it.</div><div><br></div><div>For the academic purpose of proving =
completeness (that is, any computation can be successfully "proved&quo=
t; by the availability of the corresponding fraud proof), one can imagine r=
educing the computation all the way down to a circuit, where each step (lea=
f) is as simple as what can be checked with {OP_NOT, OP_BOOLAND, OP_BOOLOR,=
OP_EQUAL}.<br></div><div><br></div><div>In practice, you would want to uti=
lize Script to its fullest, so for example you wouldn't compile a SHA25=
6 computation to something else =E2=80=93 you'd rather use OP_SHA256 di=
rectly.</div></div><div>=C2=A0<br></div><blockquote class=3D"gmail_quote" s=
tyle=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);pad=
ding-left:1ex">
<p>That raises leads to a different question: Alice initially posts
a commitment to an execution trace of `f(x) =3D y`, `x`, and `y`.
Bob Disagrees with `y` so starts the challenge protocol. Is there
a commitment to `f`? In other words, the dispute protocol (as I
read it) finds the leftmost step in Alice and Bob's execution
traces that differ, and then rewards the coins to the participant
who's "after-value" is computed by the step's opera=
tion applied to
the "before value". But if the participants each present va=
lid
steps but with different operations, who wins? In other words,
Alice could present [64, DECREMENT, 63] and Bob could present [64,
INCREMENT, 65]. Those steps don't match, but both are valid. Is
there something to ensure that before the challenge protocol
starts, that the execution trace that Alice posts is for the right
computation and not a different computation that yields a
favorable result for her (and for which she can generate a valid
merkle tree)?</p></blockquote><div><br></div><div>The function f is a=
lready hard-coded in the contract itself, by means of the tree of scripts =
=E2=88=92 that already commits to the possible futures. Therefore, once you=
are at state S14, you know that you are verifying the 6th step of the comp=
utation; and the operation in the 6th step of the computation depends solel=
y on f, not its inputs. In fact, you made me realize that I could drop op_i=
from the i-th leaf commitment, and just embed the information in the Scrip=
t of that corresponding state.<br><br>Note that the states S0 to S14 of the=
256x game are not _all_ the possible states, but only the ones that occurr=
ed in that execution of the contract (corresponding to a path from the root=
to the leaf of the Merkle tree of the computation trace), and therefore th=
e ones that materialized in a UTXO. Different choices made by the parties (=
by providing different data, and therefore choosing different branches) wou=
ld lead to a different leaf, and therefore to different (but in a certain s=
ense "symmetric") states.<br><br>=3D=3D=3D=3D=3D=3D=3D=3D</div><d=
iv><br></div><div>Since we are talking about the fact that f is committed t=
o in the contract, I'll take the chance to extend on this a bit with a =
fun construction on top.</div><div>It is well-known in the academic literat=
ure of state channels that you can create contracts where even the function=
("program", or "contract") is not decided when the cha=
nnel is created.<br></div><div><br></div><div>Since f is generic, we can ch=
oose f itself to be a universal Turing machine. That is, we can imagine a f=
unction f(code, data) that executes a program ("code") on the &qu=
ot;data" given to it as input.</div><div>Since we can do fraud proofs =
on statements "f(code, data) =3D=3D output", we could build contr=
acts where the "code" itself is chosen later.</div><div><br></div=
><div>For example, one could build a universal state channel, where parties=
can enter any contract among themselves (e.g.: start playing a chess game)=
entirely inside the channel. The state of this universal channel would con=
tain all the states of the individual contracts that are currently open in =
the channel, and even starting/closing contracts can happen entirely off-ch=
ain.</div><div><br></div><div>I believe these constructions are practical (=
the code of universal Turing machines is not really complicated), so it mig=
ht be worth exploring further to figure out useful applications of this app=
roach (supercharging lightning?).</div><div><br></div><div>We should probab=
ly start by implementing testnet rock-paper-scissors in MATT, though :)</di=
v><div><br></div><div>Best,</div><div>Salvatore Ingala</div></div></div>
--000000000000a90efd05eec04528--
|