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
|
Return-Path: <roconnor@blockstream.com>
Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138])
by lists.linuxfoundation.org (Postfix) with ESMTP id 6E4E4C0032
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 17 Oct 2023 18:00:41 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp1.osuosl.org (Postfix) with ESMTP id 3D1FF82094
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 17 Oct 2023 18:00:41 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org 3D1FF82094
Authentication-Results: smtp1.osuosl.org;
dkim=pass (2048-bit key) header.d=blockstream-com.20230601.gappssmtp.com
header.i=@blockstream-com.20230601.gappssmtp.com header.a=rsa-sha256
header.s=20230601 header.b=d6CH1gvG
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -1.899
X-Spam-Level:
X-Spam-Status: No, score=-1.899 tagged_above=-999 required=5
tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
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 smtp1.osuosl.org ([127.0.0.1])
by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id xxHwFD7OcHHB
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 17 Oct 2023 18:00:39 +0000 (UTC)
Received: from mail-oa1-x35.google.com (mail-oa1-x35.google.com
[IPv6:2001:4860:4864:20::35])
by smtp1.osuosl.org (Postfix) with ESMTPS id C407A8208A
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 17 Oct 2023 18:00:38 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp1.osuosl.org C407A8208A
Received: by mail-oa1-x35.google.com with SMTP id
586e51a60fabf-1e9d3cc6e7aso2966849fac.2
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 17 Oct 2023 11:00:38 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=blockstream-com.20230601.gappssmtp.com; s=20230601; t=1697565637;
x=1698170437; darn=lists.linuxfoundation.org;
h=to:subject:message-id:date:from:in-reply-to:references:mime-version
:from:to:cc:subject:date:message-id:reply-to;
bh=KRR3LOZoPVpWV58o8dJgjZiIdgsq3e7Xp97TLYnwCaE=;
b=d6CH1gvGCljo42rSjY65ToloG2osLSfjHZBodw9atyU6R5+nCx8wOBwuVHBCoIGefk
3jqVQAT8dd7JoN7iI2t9mbBZAtiqstamDRmnk4Y9UgTO4byd8dZCXqW3W62dEFxcQuAN
dBhK2Ik01s+p34+7at5EaeeAWhTl4xCxiQ9mp2fml1kK4OD/PB9K4cSx6KIUAjEsLQL+
apJaBxs2OrIzKZ+l2NZxoitlaDo82yDaRNHzVQ4G+9c3ZoNBrZGMIDYnbAk7VyqZXChg
jfDgUAaF7UYMDZAomaUeVGWJPCx6WKUXQMpCk6B+B0e8Ua8xpCIsVL6sAt+22jXThyoQ
q91Q==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1697565637; x=1698170437;
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=KRR3LOZoPVpWV58o8dJgjZiIdgsq3e7Xp97TLYnwCaE=;
b=K/oYrQVuyrWcQleOjSpHk6r1xchrK74gobpfgMFRKSkBwy4v2od2855T5yQ8VQu/i6
kpDKR5JgVTu2BhAV9enfpYdqtLtR5gOlbSTMRFeOxZvB8/FjOUNoEaCr1NuBGCUy70pk
z+noIbhc9aWhQ1GDH+jaEratH27BSSzwHQajhz/j72t2JOQTKNT5H7q2cPCvRcBY/z0f
ev/bnIGML0J/1954wALrfCkyKpPRZQwtFcFkF8zKlxiCZfvZvCeAU3ButAguwNSWzrRG
0qASIei05zHcL9mn/X6rIxTMxv/Q4ogAbdDHsu+2B6Qpc6laznQhzaenzHoORX0l23Ql
1QeA==
X-Gm-Message-State: AOJu0Yw1c0w4dFgYS8Nxy+nIB8EChqLeW4nmMptkTw7CPbfCNrsSW6+b
0VQ935l4TYrJ9FOyYBrCgC91ZOMlDbzDr1aNpkWvn0ViXXBRPws5
X-Google-Smtp-Source: AGHT+IELYiaKV16kp9cSh5kY/7XSPmJI+ekUxMRTEGcPeLBRPUSNOI/5ooZi2SekXeoZcMJmDUwf6WeEZULePAF8u6Q=
X-Received: by 2002:a05:6870:1017:b0:1e9:f73e:636c with SMTP id
23-20020a056870101700b001e9f73e636cmr3036843oai.43.1697565637699; Tue, 17 Oct
2023 11:00:37 -0700 (PDT)
MIME-Version: 1.0
References: <CCA561B6-A2DE-46FD-A2F8-98E0C34A3EEE@zerosync.org>
In-Reply-To: <CCA561B6-A2DE-46FD-A2F8-98E0C34A3EEE@zerosync.org>
From: "Russell O'Connor" <roconnor@blockstream.com>
Date: Tue, 17 Oct 2023 14:00:26 -0400
Message-ID: <CAMZUoKm56htx9Ux4D8CvgpQ+W_f1qw9HrkWBfkFPo699Esp--Q@mail.gmail.com>
To: Robin Linus <robin@zerosync.org>,
Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Content-Type: multipart/alternative; boundary="000000000000d17ff30607ed4c1c"
Subject: Re: [bitcoin-dev] BitVM: Compute Anything on Bitcoin
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, 17 Oct 2023 18:00:41 -0000
--000000000000d17ff30607ed4c1c
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
While I haven't looked at the BitVM in detail, I would like to mention that
Simplicity's core language (excluding introspection primitives) has the
same expressivity as Boolean circuits.
A few years ago I did some experiments to compile Simplicity expressions to
a system of polynomial constraints (R1CS). The experiments were
successful. For instance, I was able to compile our Sha256 compression
function specification written in Simplicity to a set of approximately
128,000 constraints. Under this "circuit" interpretation, Simplicity types
represent cables, which are a bundle of wires equal to the 'bit size' of
the given type. The 'case' combinator ends up being the only "active"
component (implementing a demux). The 'injr' and 'injr' combinators output
some fixed Boolean values. The rest of the combinations end up only
connecting, bundling and unbundling wires, and contribute no constraints at
all.
While my previous experiment was generating constraints, it is clear to me
that a similar interpretation could instead generate logic gates, and I
would expect the same order of magnitude in the number of gates generated
as the number of constraints generated above. Thus Simplicity could be
used as a source of ready made expressions to generate useful circuits for
the BitVM, should someone be interested in pursuing this angle.
On Mon, Oct 9, 2023 at 10:05=E2=80=AFAM Robin Linus via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:
> Abstract. BitVM is a computing paradigm to express Turing-complete Bitcoi=
n
> contracts. This requires no changes to the network=E2=80=99s consensus ru=
les.
> Rather than executing computations on Bitcoin, they are merely verified,
> similarly to optimistic rollups. A prover makes a claim that a given
> function evaluates for some particular inputs to some specific output. If
> that claim is false, then the verifier can perform a succinct fraud proof
> and punish the prover. Using this mechanism, any computable function can =
be
> verified on Bitcoin. Committing to a large program in a Taproot address
> requires significant amounts of off-chain computation and communication,
> however the resulting on-chain footprint is minimal. As long as both
> parties collaborate, they can perform arbitrarily complex, stateful
> off-chain computation, without leaving any trace in the chain. On-chain
> execution is required only in case of a dispute.
>
> https://bitvm.org/bitvm.pdf
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>
--000000000000d17ff30607ed4c1c
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
<div dir=3D"ltr"><div>While I haven't looked at the BitVM in detail, I =
would like to mention that Simplicity's core language (excluding intros=
pection primitives) has the same expressivity as Boolean circuits.</div><di=
v><br></div><div>A few years ago I did some experiments to compile Simplici=
ty expressions to a system of polynomial constraints (R1CS).=C2=A0 The expe=
riments were successful. For instance, I was able to compile our Sha256 com=
pression function specification written in Simplicity to a set of approxima=
tely 128,000 constraints.=C2=A0 Under this "circuit" interpretati=
on, Simplicity types represent cables, which are a bundle of wires equal to=
the 'bit size' of the given type. The 'case' combinator en=
ds up being the only "active" component (implementing a demux).=
=C2=A0 The 'injr' and 'injr' combinators output some fixed =
Boolean values. The rest of the combinations end up only connecting, bundli=
ng and unbundling wires, and contribute no constraints at all.</div><div><b=
r></div><div>While my previous experiment was generating constraints, it is=
clear to me that a similar interpretation could instead generate logic gat=
es, and I would expect the same order of magnitude in the number of gates g=
enerated as the number of constraints generated above.=C2=A0 Thus Simplicit=
y could be used as a source of ready made expressions to generate useful ci=
rcuits for the BitVM, should someone be interested in pursuing this angle.<=
br></div></div><br><div class=3D"gmail_quote"><div dir=3D"ltr" class=3D"gma=
il_attr">On Mon, Oct 9, 2023 at 10:05=E2=80=AFAM Robin Linus via bitcoin-de=
v <<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org">bitcoin-dev@=
lists.linuxfoundation.org</a>> wrote:<br></div><blockquote class=3D"gmai=
l_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,20=
4,204);padding-left:1ex">Abstract. BitVM is a computing paradigm to express=
Turing-complete Bitcoin contracts. This requires no changes to the network=
=E2=80=99s consensus rules. Rather than executing computations on Bitcoin, =
they are merely verified, similarly to optimistic rollups. A prover makes a=
claim that a given function evaluates for some particular inputs to some s=
pecific output. If that claim is false, then the verifier can perform a suc=
cinct fraud proof and punish the prover. Using this mechanism, any computab=
le function can be verified on Bitcoin. Committing to a large program in a =
Taproot address requires significant amounts of off-chain computation and c=
ommunication, however the resulting on-chain footprint is minimal. As long =
as both parties collaborate, they can perform arbitrarily complex, stateful=
off-chain computation, without leaving any trace in the chain. On-chain ex=
ecution is required only in case of a dispute.<br>
<br>
<a href=3D"https://bitvm.org/bitvm.pdf" rel=3D"noreferrer" target=3D"_blank=
">https://bitvm.org/bitvm.pdf</a><br>
_______________________________________________<br>
bitcoin-dev mailing list<br>
<a href=3D"mailto:bitcoin-dev@lists.linuxfoundation.org" target=3D"_blank">=
bitcoin-dev@lists.linuxfoundation.org</a><br>
<a href=3D"https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev" =
rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfoundation.org/mail=
man/listinfo/bitcoin-dev</a><br>
</blockquote></div>
--000000000000d17ff30607ed4c1c--
|