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
|
Return-Path: <aj@erisian.com.au>
Received: from smtp4.osuosl.org (smtp4.osuosl.org [IPv6:2605:bc80:3010::137])
by lists.linuxfoundation.org (Postfix) with ESMTP id 59894C0032
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 2 Oct 2023 15:10:22 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp4.osuosl.org (Postfix) with ESMTP id 2E47F41E41
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 2 Oct 2023 15:10:22 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 2E47F41E41
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.902
X-Spam-Level:
X-Spam-Status: No, score=-1.902 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, SPF_HELO_PASS=-0.001, 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 IXfmEMUSCjH1
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 2 Oct 2023 15:10:18 +0000 (UTC)
Received: from cerulean.erisian.com.au (azure.erisian.com.au [172.104.61.193])
by smtp4.osuosl.org (Postfix) with ESMTPS id 7015E41ADE
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 2 Oct 2023 15:10:18 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp4.osuosl.org 7015E41ADE
Received: from aj@azure.erisian.com.au
by cerulean.erisian.com.au with esmtpsa (TLS1.3) tls
TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384 (Exim 4.94.2)
(envelope-from <aj@erisian.com.au>)
id 1qnKYm-0006fh-H7; Tue, 03 Oct 2023 01:10:15 +1000
Received: by email (sSMTP sendmail emulation); Tue, 03 Oct 2023 01:10:08 +1000
Date: Tue, 3 Oct 2023 01:10:08 +1000
From: Anthony Towns <aj@erisian.com.au>
To: Johan =?iso-8859-1?Q?Tor=E5s?= Halseth <johanth@gmail.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <ZRrdULpZ2nYaDOV7@erisian.com.au>
References: <CAD3i26BAoN06rR=BnvNDDBCyMkKTcROGK7zaC784XV5FWYM+5w@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=iso-8859-1
Content-Disposition: inline
Content-Transfer-Encoding: 8bit
In-Reply-To: <CAD3i26BAoN06rR=BnvNDDBCyMkKTcROGK7zaC784XV5FWYM+5w@mail.gmail.com>
X-Spam_score: -0.0
X-Spam_bar: /
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: Mon, 02 Oct 2023 15:10:22 -0000
On Fri, Sep 29, 2023 at 03:14:25PM +0200, Johan Torås Halseth via bitcoin-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 = 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 = start_pc|start_i|start_x|end_pc|end_i|end_x|h(sub_node1)|h(sub_node2)
leaf = 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
|
