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
|
Return-Path: <johanth@gmail.com>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136])
by lists.linuxfoundation.org (Postfix) with ESMTP id E5D36C0032
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 3 Oct 2023 07:53:21 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp3.osuosl.org (Postfix) with ESMTP id B441260F0A
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 3 Oct 2023 07:53:21 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org B441260F0A
Authentication-Results: smtp3.osuosl.org;
dkim=pass (2048-bit key) header.d=gmail.com header.i=@gmail.com
header.a=rsa-sha256 header.s=20230601 header.b=NMsf0ijb
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -2.099
X-Spam-Level:
X-Spam-Status: No, score=-2.099 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,
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 w7h2cue7T-6t
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 3 Oct 2023 07:53:21 +0000 (UTC)
Received: from mail-yb1-xb31.google.com (mail-yb1-xb31.google.com
[IPv6:2607:f8b0:4864:20::b31])
by smtp3.osuosl.org (Postfix) with ESMTPS id D871860EE8
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 3 Oct 2023 07:53:20 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org D871860EE8
Received: by mail-yb1-xb31.google.com with SMTP id
3f1490d57ef6-d81adf0d57fso668510276.1
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 03 Oct 2023 00:53:20 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=gmail.com; s=20230601; t=1696319600; x=1696924400;
darn=lists.linuxfoundation.org;
h=content-transfer-encoding:cc:to:subject:message-id:date:from
:in-reply-to:references:mime-version:from:to:cc:subject:date
:message-id:reply-to;
bh=mz9HEnxMeHfNvgCgTR0R/tyjwMwejwUWALDWQfifP1k=;
b=NMsf0ijbZ4bp4+Ix4GYBkAf5HD+WQp0/aSfY8pUg0LqkyXwmvJOFfnv9HX6wS/DAbW
VizQaK7mvKJ/ouLcwRIF53dzk3m6bVYMilAhybOfiveYnD0uMEu5GbMlssgeIltKaUS6
ZPvFdxyhFshJ1l1rM88ik2CzScpi+XH3Blc+9h0s8hqYoku0aK6NvudRDgIHJQIrOnNb
H+sUsoDWWnJQgRNIsk8EcqyURZblNyBfR0kyhE9S86c0QzoJGL3l5oN2zw5hghqN73hO
Wa7XU7Q/yuMgD2vL9CzrNFFXdDpnSxfhqVFasmioycdBmkB5gYLCjfcV3DRCf3YILTeg
YnWg==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1696319600; x=1696924400;
h=content-transfer-encoding:cc: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=mz9HEnxMeHfNvgCgTR0R/tyjwMwejwUWALDWQfifP1k=;
b=s1+pC85gwUnAwyC3i+coCDu4onn521yXIILq9+gWqeGmraWFLU3/R9hoRJtM2wGPFm
R8i7No5Lup/2vxA1MNUTlIUFVE7+jGUtn38V0aSP+Qe9r3A502nr0UXwYrTQ80az+MTJ
FutNHrA1MGX39dt930KYGDmCNiY24H9EuQ0/JDfAT0bp3/R8YV8eFyME8T2o3ck3aluz
5PqSLMKPxo/7USdRdoOekdgXdNDtq8KqKRxNqY44rPURCI0lWlz3ZpIeJgdfLLZlvS5t
FRPXpVIIO44ICG6Mitm+VDbUBq1z0sLWje9ClLOPbJylPK7gfSqM/y6mo+r5OpbGAGef
Qdog==
X-Gm-Message-State: AOJu0YwoJL1wrz6c8vYd8XkAyA4pttsXkzeNf2xZBuSl069CHgxk4NG8
rr79qcAbXTgLANYrA1d/C9rnlJbC2MpoGsu5rUwI6OSDx2tJHA==
X-Google-Smtp-Source: AGHT+IHGV31rnm4Pv3P2i2u0prKX6TSNoLpaBhjWPI97MYIAikdsqsAXeRTAN2rrk6in+k4fmPGHMebwV+oLNIgjk+A=
X-Received: by 2002:a25:141:0:b0:d36:99eb:fc01 with SMTP id
62-20020a250141000000b00d3699ebfc01mr12844055ybb.15.1696319599551; Tue, 03
Oct 2023 00:53:19 -0700 (PDT)
MIME-Version: 1.0
References: <CAD3i26BAoN06rR=BnvNDDBCyMkKTcROGK7zaC784XV5FWYM+5w@mail.gmail.com>
<ZRrdULpZ2nYaDOV7@erisian.com.au>
In-Reply-To: <ZRrdULpZ2nYaDOV7@erisian.com.au>
From: =?UTF-8?Q?Johan_Tor=C3=A5s_Halseth?= <johanth@gmail.com>
Date: Tue, 3 Oct 2023 09:53:08 +0200
Message-ID: <CAD3i26BKejHjQ5-+H=oC6FzF7RAP-2keW1iwo8TY+FEoGNwk3Q@mail.gmail.com>
To: Anthony Towns <aj@erisian.com.au>
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
X-Mailman-Approved-At: Tue, 03 Oct 2023 08:22:00 +0000
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] MATT: [demo] Optimistic execution of arbitrary
programs
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: Tue, 03 Oct 2023 07:53:22 -0000
Hi, aj. Thanks for taking a look!
> "O(n log n)" sounds wrong? Isn't it O(P + log(N)) where P is the size
> of the program, and N is the number of steps (rounded up to a power of 2)=
?
Thanks, you are right. That's a typo, it should indeed be O(log n). n
being the number of steps in the program. I think P doesn't matter
here, as we never put the whole program on-chain, just break it down
into n steps.
> > node =3D h( start_pc|start_i|start_x|end_pc|end_i|end_x|h( h(sub_node1)=
|h(sub_node2) )
> But I don't think that works -- I think you want to know h(sub_node1)
> and h(sub_node2) directly, so that you can compare them to the results
> you get if you run the computation, and choose the one that's incorrect.
This denotes only how to create the commitment. When we traverse the
tree, the node scripts enforce that h(sub_n
ode{1,2}) that is consistent with the commitment is in the witness,
achieving exactly what you suggest.
> I'm not seeing what forces the prover to come up with a balanced state
> tree
To achieve this the participants agree up front (when the contract is
created) what is the exact length of the trace (or equivalent the
depth of the tree). If the actual execution is shorter, we fill the
rest with no-ops.
This means that we know the moment the challenge protocol starts the
transactions that are going to be played (kinda like a CTV tree), so
if one of the participants creates a trace from a non-balanced state
tree, it will be rejected by the script at that level. It is indeed
important that the state tree is built in a deterministic way.
> There seems to be an error in the "what this would look like for 4 state
> transitions" diagram -- the second node should read "0|0|2 -> 0|1|4"
Yes, fixed! Thanks :)
- Johan
On Mon, Oct 2, 2023 at 5:10=E2=80=AFPM Anthony Towns <aj@erisian.com.au> wr=
ote:
>
> On Fri, Sep 29, 2023 at 03:14:25PM +0200, Johan Tor=C3=A5s Halseth via bi=
tcoin-dev wrote:
> > TLDR; Using the proposed opcode OP_CHECKCONTRACTVERIFY and OP_CAT, we
> > show to trace execution of the program `multiply` [1] and challenge
> > this computation in O(n logn) on-chain transactions:
>
> "O(n log n)" sounds wrong? Isn't it O(P + log(N)) where P is the size
> of the program, and N is the number of steps (rounded up to a power of 2)=
?
>
> You say:
>
> > node =3D h( start_pc|start_i|start_x|end_pc|end_i|end_x|h( h(sub_node1)=
|h(sub_node2) )
>
> But I don't think that works -- I think you want to know h(sub_node1)
> and h(sub_node2) directly, so that you can compare them to the results
> you get if you run the computation, and choose the one that's incorrect.
> Otherwise you've got a 50/50 chance of choosing the subnode that's
> actually correct, and you'll only be able to prove a mistake with
> 1/2**N odds?
>
> Not a big change, it just becomes 32B longer (and drops some h()s):
>
> node =3D start_pc|start_i|start_x|end_pc|end_i|end_x|h(sub_node1)|h(sub=
_node2)
> leaf =3D start_pc|start_i|start_x|end_pc|end_i|end_x|null
>
> I'm not seeing what forces the prover to come up with a balanced state
> tree -- if they don't have to have a balanced tree, then I think there
> are many possible trees for the same execution trace, and again it would
> become easy to hide an error somewhere the challenger can't find. Adding =
a
> "start_stepcount" and "end_stepcount" would probably remedy that?
>
> There seems to be an error in the "what this would look like for 4 state
> transitions" diagram -- the second node should read "0|0|2 -> 0|1|4"
> (combining its two children), not "0|0|2 -> 1|0|2" matching its left
> child.
>
> I'm presuming that the counterparty verifies they know the program (ie,
> all the leaves in the contract taptree) before agreeing to the contract
> in the first place. I think that's fine.
>
> Cheers,
> aj
>
|
