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
|
Return-Path: <gmaxwell@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id 46224BCA
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 30 Oct 2017 23:29:30 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-vk0-f53.google.com (mail-vk0-f53.google.com
[209.85.213.53])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 90F5B16A
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 30 Oct 2017 23:29:29 +0000 (UTC)
Received: by mail-vk0-f53.google.com with SMTP id h142so5802808vkf.7
for <bitcoin-dev@lists.linuxfoundation.org>;
Mon, 30 Oct 2017 16:29:29 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=mime-version:sender:in-reply-to:references:from:date:message-id
:subject:to:cc;
bh=5mZ3oNYI2N9LY+Bjgle/qq6RjxGYBrWxd0bND6rCsng=;
b=tQg47cO1mpOFTOk8VVFsw38ChxKLpQaIndcWNYwNGoQ0sOJ/AN+kvJQblQS0tugmzr
qv6OvHH1+fvp3LS+n4lhEu6NWOUI0U0FpJl9oCvO9DLZIVQKRimazWjVvn08LQgEIL+3
hpxqyHkxrAgq+iGqE8pEPrWGxtTU+q5ABWy+d+Ly2FYLCtmlN3FD1MJ7f04xCXG0T1Oi
yrE4r214FqNdcGXJN5I0CcVViEvRs6Vo0sKCSjAXCGGoEqvrHwFASuERDhv4YOpoU8q5
FWpD49gi85lOwU4ki0EngprgqY6wa9moZroCgb1Sw5xAbJ+z4GKUYUWymfQ/0Z707krk
RCRA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:mime-version:sender:in-reply-to:references:from
:date:message-id:subject:to:cc;
bh=5mZ3oNYI2N9LY+Bjgle/qq6RjxGYBrWxd0bND6rCsng=;
b=XPycGM8dZoox97uBAEUg1mKXQTiuyVhzqalnY/A4KgNBKeHC0jevIJfIidZs4GViKP
u3OsUzoj5z4o458uuvZVyB8j/L0TByWF3mjgEjMJVhQTKgq1IZuU+ZVA44WtdYA7cWs+
TWr4zEsI+sqWRj5r3GiTrAQU0Uy6L16mfErZ6tCuBUU8cH4beKOdtSj6qsWSbjlbECGu
tHWvI3qHeSmkfNEtMgaSkEX5Jb9xy6rBd0VoDWpEnro7Lne8OCbELooEdDcSjFZyb6u+
b1a+gX+k+SvbpG+MUVH1nDqgcQz9Atw/uFc2MKtj/z+ST/OGmBAMiVCcD6Zkf+kkFYJc
r9hQ==
X-Gm-Message-State: AMCzsaW4/Vxs7zGP9lUe8c2fegPCPFioAN/eJUGqxFmEOSY0NSXDiYfc
LRlJJ4GdbOSGyxVKTg9Hk/E02XucHz9UgaVdpVQ=
X-Google-Smtp-Source: ABhQp+Q37jo6I3wl8yB9940jgJ9sC78JvcpKrXdEUfvce0GNr78P1BKUDQlyuXXfQCmnQn2baFeTw6IDxE3H5My8GkU=
X-Received: by 10.31.50.136 with SMTP id y130mr8514052vky.15.1509406168635;
Mon, 30 Oct 2017 16:29:28 -0700 (PDT)
MIME-Version: 1.0
Sender: gmaxwell@gmail.com
Received: by 10.103.87.93 with HTTP; Mon, 30 Oct 2017 16:29:28 -0700 (PDT)
In-Reply-To: <E63C347E-5321-4F7F-B69C-75747E88AC06@mattcorallo.com>
References: <CAMZUoK=VNRMda8oRCtxniE6-vLwG-b=je2Hx+sD9sCzS--v9kQ@mail.gmail.com>
<E63C347E-5321-4F7F-B69C-75747E88AC06@mattcorallo.com>
From: Gregory Maxwell <greg@xiph.org>
Date: Mon, 30 Oct 2017 23:29:28 +0000
X-Google-Sender-Auth: mky1GdK1odlix0rlm8AVqJXPwKI
Message-ID: <CAAS2fgRUAh2GJWbG74pef5tmj4NmbHX3_fy-_GMYWP3Tj4TNWA@mail.gmail.com>
To: Matt Corallo <lf-lists@mattcorallo.com>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: text/plain; charset="UTF-8"
X-Spam-Status: No, score=0.0 required=5.0 tests=DKIM_SIGNED,DKIM_VALID,
FREEMAIL_FROM,RCVD_IN_DNSWL_NONE autolearn=disabled version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
Subject: Re: [bitcoin-dev] Simplicity: An alternative to Script
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
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, 30 Oct 2017 23:29:30 -0000
On Mon, Oct 30, 2017 at 9:42 PM, Matt Corallo via bitcoin-dev
<bitcoin-dev@lists.linuxfoundation.org> wrote:
> I admittedly haven't had a chance to read the paper in full details, but I
> was curious how you propose dealing with "jets" in something like Bitcoin.
> AFAIU, other similar systems are left doing hard-forks to reduce the
> sigops/weight/fee-cost of transactions every time they want to add useful
> optimized drop-ins. For obvious reasons, this seems rather impractical and a
> potentially critical barrier to adoption of such optimized drop-ins, which I
> imagine would be required to do any new cryptographic algorithms due to the
> significant fee cost of interpreting such things.
For some framing-- I think we're still a long way off from proposing
something like this in Bitcoin, and _how_ it's ultimately proposed is
an open question.
There are many ways to use simplicity, for an extreme example: one
could define a collection of high level operations and combinators at
the level of things in Bitcoin Script (op_sha256, op_equal, op_cat,
etc.) and make an interpreter that implements these operations as
discounted jets and ONLY these operations at all.
At that point you have a system which is functionally like Bitcoin
Script-- with the same performance characteristics-- but with a pretty
much perfectly rigorous formal specification and which is highly
amenable to the formal analysis of smart contracts written in it.
At the other extreme, you expose a full on Bitmachine and allow
arbitrary simplicity-- But this is probably slow enough to not be
very useful. Simplicity itself is so simple that it doesn't natively
have a concept of a _bit_, library code programs the concept of a bit,
then the concept of a half adder ... and so on. As a result a
completely unjetted implementation is slow (actually remarkably fast
considering that it's effectively interpreting a circuit constructed
from pure logic).
The most useful way of using it would probably be in-between: a good
collection of high level functions, and mid-level functions (e.g.
arithmetic and string operations) making a wide space of useful but
general software both possible and high performance. But to get there
we need enough experience with it to know what the requisite
collection of operations would be.
One challenge is that I don't think we have a clear mental model for
how nominal validation costs are allowed to be before there is a
negative impact. It's probably safe to assume 'pretty darn nominal'
is a requirement, but there is still a lot that can be done within
that envelope.
As far as consensus discounted jets goes:
From my perspective there are three related ideas around this:
Is a particular script-root jetted or not in an implementation?
-- In and of itself this is not of consensus consequence; esp.
because a major design feature of simplicity is that it should be
possible using to prove that an optimized C implementation of a
simplicity program is complete and correct (using VST+COQ).
Is a particular script-root 'standard and known' in the P2P network:
-- This means that you can skip communicating it when sending
witnesses to peers; but this is something that could be negotiated on
a peer by peer basis-- like compressing transactions, and isn't at all
consensus normative.
Is a particular jet discounted and what are the discounts:
-- This is inherently a consensus question; as the bitmachine costing
for a program is consensus normative (assuming that you allow
arbitrary simplicity code at all).
A script-versioning like mechanism can provide for a straight-forward
way to upgrade discounted cost tables in a compatible way-- if you're
running old software that doesn't have the required jets to justify a
particular discount collection -- well that's okay, you won't validate
those scripts at all. (so they'll be super fast for you!)
Another potential tool is the idea of sunsetting cost limits that
sunset; e.g. after N years, the limits go away with an assumption that
updated limits have been softforked in that ativate at that time and
themselves expire in N years. Old software would become slower
validating due to newly discounted code they lack jets for... but
would continue validating (at least until they run out of performance
headroom).
This is theoretically attractive in a number of regards, but
unfortunately I think our industry hasn't shown sufficient maturity
about engineering tradeoffs to make this a politically viable choice
in the mid-term-- I known I'm personally uncomfortable with the
outspokenness of parties that hold positions which I think can fairly
be summarized "We should remove all limits and if the system crashes
and burns as a result, we'll just make a new one! YOLO.". But it's
interesting to think about in the long term.
There are also hybrid approaches where you can imagine this decision
being made by node operators, e.g. continuing to validate code that
exceeds your effort limits on probabilistic and best effort basis;
even more attractive if there were a protocol for efficiently showing
others that an operation had an invalid witness. Though there is a lot
to explore about the brittleness to partitioning that comes from any
expectation that you'd learn about invalid updates by exception.
In any case, these are all options that exist completely independently
of simplicity. I think we should think of simplicity as a rigorous
base which we could _potentially_ use to build whatever future
direction of script we like out of... by itself it doesn't mandate a
particular depth or level of adoption.
And for the moment it's still also mostly just a base-- I don't
anticipate typical smart contracting end users programming directly w/
simplicity even if Bitcoin did support arbitrary simplicity-- I
expect they'd program in user friendly domain specific languages which
are formally tied to their implementations in simplicity that allow-
but do not force- closed loop formal reasoning about their contracts
all the way from their high level business rules straight through to
the machine code implementing the interpreter(s) that run in the
network.
But to get there we'll have to prove in practice that this is actually
workable. We have some evidence that it is, e.g. Roconnor's SHA2
implementation in simplicity is proven to implement the same function
that a C implementation implements (via the compcert formalization of
C). but there will need to be more.
|
