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
|
Delivery-date: Sun, 12 May 2024 18:54:24 -0700
Received: from mail-yb1-f185.google.com ([209.85.219.185])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBCXZ3LX45UKRBSHFQWZAMGQEXW45PQI@googlegroups.com>)
id 1s6KtU-0002ao-0Q
for bitcoindev@gnusha.org; Sun, 12 May 2024 18:54:24 -0700
Received: by mail-yb1-f185.google.com with SMTP id 3f1490d57ef6-de603db5d6asf7805861276.2
for <bitcoindev@gnusha.org>; Sun, 12 May 2024 18:54:23 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1715565257; x=1716170057; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-sender:mime-version
:subject:message-id:to:from:date:sender:from:to:cc:subject:date
:message-id:reply-to;
bh=eTxS7CA1CpIOmXhHiOffuw6Kojl+3c3a6Vq/fo0GrNc=;
b=xEvxOvoXQWnJTiloZXfvcqAtyrnPJxICmjBbA5G2fxgS9cRdtII315OqHrpYfyX6KM
TBAognfnQnLLqIYYHpbZJSrE+7/Ko6ybCkiAT8X1WB0QIBXTwu9fxAl84jnQOTMlIxCS
pR5+qvetvM/SNZkREGWAszqhO8e13xMm5NSNzk2Cjen7G7HRYeqKMB/IosdqrOXqEQQf
2UfofpvD6YOwkEGtYb+UDZsnPu4qAXXygzs/rg9xOQeV698DfTkbvVqgMQ2wrIZxZoNM
pxXDot76RgMFChkUdYicX3bK3Cw3mSE1kZkTQUt+dUVjf28pWbasocbmJzHlFC9lWkbb
0T9g==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=gmail.com; s=20230601; t=1715565257; x=1716170057; darn=gnusha.org;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-sender:mime-version
:subject:message-id:to:from:date:from:to:cc:subject:date:message-id
:reply-to;
bh=eTxS7CA1CpIOmXhHiOffuw6Kojl+3c3a6Vq/fo0GrNc=;
b=UWxnM98y8HZG2e35iilVQU2TfXaZCpkcHVhAuW6xag2CBGXfrjuuc+gKhZYHvaPXkn
2k/1PMqsx9AoBQP6khp1ppqI6kB9jWPj0PWUCE9wSFXHCkphU8YG5BptOQnsSsanz9KW
32nh9Xl7XEADphyJmzPXUz1wjiZHNDQUNO04aYvkVhJAssUltUxqyMVqQNQlWQJY0udg
xA/nW1TJcPi2ofeRdV4SiW2GO9ksnhMbUMB+exMjUzQMWujog996H5QrLDsd/+/CYg9L
n5PBi9+u7djUEO59vDoJyTUXTyjIBKz0+E6vFD9Y7fnzEjGW93OmgvOVZw98WfPqN5HE
sTNA==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1715565257; x=1716170057;
h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post
:list-id:mailing-list:precedence:x-original-sender:mime-version
:subject:message-id:to:from:date:x-beenthere:x-gm-message-state
:sender:from:to:cc:subject:date:message-id:reply-to;
bh=eTxS7CA1CpIOmXhHiOffuw6Kojl+3c3a6Vq/fo0GrNc=;
b=cccnB0Pk+G7C56HigcJ2azN2+DfYgOI0nhf6ZZYFgOv/1aP1r3nirHpLM6HJk3dAMX
cCRm5IMAtn+twaeGwclSd6S+xl77BOnWn22G6kdjbCvFxLZx2u7kuF6pNJuK+soZOj4X
Yx/YTvH/GWPdutq1+qlDkF6+O4txIiuYcksk8AxZZLIsjS6SdKm0ROzQsGtbEzRHQG7k
jHYCNRx3r3Qyz+4POtqL057CZzJ7stt/cgFo1LV5HFno9xy5fDGvFvjwSX9L3l2Ggvmt
Pj3E/3i1aiSWY3UshqcKfTI3klW6GhCHMmycaKZhvU4/LNAlbrlaFA9UxGqOwuu4ENgS
TkWA==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCVXoDGpmNuHnB3jmaYmgfNneTYUoMHdH4w6KnXFrW8mtodEBcMNEAKs4lKqY6R05WnGa7HNqWT4aBhpkNuwXGqpr10wreY=
X-Gm-Message-State: AOJu0YxXeE5lC64W1WpaRl+MOb2V8uiMV7NGxtj61J9HoGoZb1I0PTAc
F0WnZEA+9iPuqzZy/MKfNRh9vjzI4i9aVV+EbRatY3nTrFrj16Nh
X-Google-Smtp-Source: AGHT+IH197Q2G3VRlfsrRKUG+Qhk/awBwEyKdnnd6hSAWW06KC41S/QhaXpmH/nG0sxgv8zN2U7Wxg==
X-Received: by 2002:a25:c7cc:0:b0:de6:3bc:c21c with SMTP id 3f1490d57ef6-dee4f319110mr11355976276.6.1715565257411;
Sun, 12 May 2024 18:54:17 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com
Received: by 2002:a25:1d6:0:b0:dcc:37ed:efb1 with SMTP id 3f1490d57ef6-debd08a2ce5ls151952276.2.-pod-prod-00-us;
Sun, 12 May 2024 18:54:15 -0700 (PDT)
X-Received: by 2002:a05:6902:150d:b0:dc6:e884:2342 with SMTP id 3f1490d57ef6-dee4e5a1043mr2671752276.5.1715565255720;
Sun, 12 May 2024 18:54:15 -0700 (PDT)
Received: by 2002:a05:690c:97:b0:622:b23d:3cdf with SMTP id 00721157ae682-622b23d3d16ms7b3;
Sun, 12 May 2024 18:51:51 -0700 (PDT)
X-Received: by 2002:a05:690c:4d88:b0:61b:ec80:3137 with SMTP id 00721157ae682-622b01491d7mr21217747b3.9.1715565110710;
Sun, 12 May 2024 18:51:50 -0700 (PDT)
Date: Sun, 12 May 2024 18:51:50 -0700 (PDT)
From: Sergio Demian Lerner <sergio.d.lerner@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <5189939b-baaf-4366-92a7-3f3334a742fdn@googlegroups.com>
Subject: [bitcoindev] BitVMX: A Virtual CPU to optimistically execute
arbitrary programs on Bitcoin
MIME-Version: 1.0
Content-Type: multipart/mixed;
boundary="----=_Part_16146_1396980645.1715565110419"
X-Original-Sender: sergio.d.lerner@gmail.com
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com
List-ID: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
<https://groups.google.com/group/bitcoindev/subscribe>
X-Spam-Score: -0.5 (/)
------=_Part_16146_1396980645.1715565110419
Content-Type: multipart/alternative;
boundary="----=_Part_16147_1489622019.1715565110419"
------=_Part_16147_1489622019.1715565110419
Content-Type: text/plain; charset="UTF-8"
Hi!
I'd like to share with you a paper we published a few weeks ago, and was
presented in BTC++. Here is the abstract:
BitVMX is a new design for a virtual CPU to optimistically execute
arbitrary programs on Bitcoin based on a challenge/response game introduced
in BitVM. Similar to BitVM1 we create a general-purpose CPU to be verified
in Bitcoin script. Our design supports common architectures, such as RISC-V
or MIPS. Our main contribution to the state of the art is a design that
uses hash chains of program traces, memory mapped registers, and a new
challenge-response protocol. We present a new message linking protocol as a
means to allow authenticated communication between the participants. This
protocol emulates stateful smart contracts by sharing state between
transactions. This provides a basis for our verification game which uses a
graph of pre-signed transactions to support challenge-response
interactions. In case of a dispute, the hash chain of program trace is used
with selective pre-signed transactions to locate (via n-ary search) and
then recover the precise nature of errors in the computation. Unlike
BitVM1, our approach does not require the creation of Merkle trees for CPU
instructions or memory words. Additionally, it does not rely on signature
equivocations. These differences help avoid complexities associated with
BitVM1 and make BitVMX a compelling alternative to BitVM2. Our approach is
quite flexible, BitVMX can be instantiated to balance transaction cost vs
round complexity, prover cost vs verifier cost, and precomputations vs
round complexity. (1)
https://bitvmx.org/files/bitvmx-whitepaper.pdf
Note that since the paper publication we have already improved the protocol
and halved the number of rounds required, and a new paper presenting these
improvements will be published soon.
With our latest optimizations, verifying a SNARK would require ~19 rounds
(38 transactions) in the worst case, consuming ~400K weight units (WU) in
total (spread over all the transactions). This is as a back-of-the-envelope
estimation, as we're still researching, and the exact resources consumed
depend on many trade-offs that can be chosen by users.
Also, if we can set an upper bound on the money a party would be willing
sacrifice (and force the other parties to sacrifice too in equal amount) to
force the protocol to be extended one more round, then we can further
reduce both the round complexity or transaction cost (~50%).
regards, Sergio.
(1) Paper authors are Sergio Demian Lerner, Ramon Amela, Shreemoy Mishra,
Martin Jonas, and Javier Alvarez Cid-Fuentes
--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/bitcoindev/5189939b-baaf-4366-92a7-3f3334a742fdn%40googlegroups.com.
------=_Part_16147_1489622019.1715565110419
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
=09
=09
Hi!<br />I'd like to share with you a paper we published a few weeks ago,=
and was presented in BTC++. Here is the abstract:<div><br />BitVMX is a ne=
w design for a virtual CPU to optimistically execute arbitrary programs on =
Bitcoin based on a challenge/response game introduced in BitVM. Similar to =
BitVM1 we create a general-purpose CPU to be verified in Bitcoin script. Ou=
r design supports common architectures, such as RISC-V or MIPS. Our main co=
ntribution to the state of the art is a design that uses hash chains of pro=
gram traces, memory mapped registers, and a new challenge-response protocol=
. We present a new message linking protocol as a means to allow authenticat=
ed communication between the participants. This protocol emulates stateful =
smart contracts by sharing state between transactions. This provides a basi=
s for our verification game which uses a graph of pre-signed transactions t=
o support challenge-response interactions. In case of a dispute, the hash c=
hain of program trace is used with selective pre-signed transactions to loc=
ate (via n-ary search) and then recover the precise nature of errors in the=
computation. Unlike BitVM1, our approach does not require the creation of =
Merkle trees for CPU instructions or memory words. Additionally, it does no=
t rely on signature equivocations. These differences help avoid complexitie=
s associated with BitVM1 and make BitVMX a compelling alternative to BitVM2=
. Our approach is quite flexible, BitVMX can be instantiated to balance tra=
nsaction cost vs round complexity, prover cost vs verifier cost, and precom=
putations vs round complexity. (1)<br /><br />https://bitvmx.org/files/bitv=
mx-whitepaper.pdf<br /></div><div><br /></div><div>Note that since the pape=
r publication we have already improved the protocol and halved the number o=
f rounds required, and a new paper presenting these improvements will be pu=
blished soon.</div><div>=C2=A0</div><div>With our latest optimizations, ver=
ifying a SNARK would require ~19 rounds (38 transactions) in the worst case=
, consuming ~400K weight units (WU) in total (spread over all the transacti=
ons). This is as a back-of-the-envelope estimation, as we're still research=
ing, and the exact resources consumed depend on many trade-offs that can be=
chosen by users.</div><div><br /></div><div>Also, if we can set an upper b=
ound on the money a party would be willing sacrifice (and force the other p=
arties to sacrifice too in equal amount) to force the protocol to be extend=
ed one more round, then we can further reduce both the round complexity or =
transaction cost (~50%).</div><div><br /></div><div>regards, Sergio.</div><=
div><br /></div>(1) Paper authors are Sergio Demian Lerner, Ramon Amela, Sh=
reemoy Mishra, Martin Jonas, and Javier Alvarez Cid-Fuentes<div><br /></div=
>
<p></p>
-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List" group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion on the web visit <a href=3D"https://groups.google.c=
om/d/msgid/bitcoindev/5189939b-baaf-4366-92a7-3f3334a742fdn%40googlegroups.=
com?utm_medium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msg=
id/bitcoindev/5189939b-baaf-4366-92a7-3f3334a742fdn%40googlegroups.com</a>.=
<br />
------=_Part_16147_1489622019.1715565110419--
------=_Part_16146_1396980645.1715565110419--
|
