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
|
Return-Path: <robin@zerosync.org>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [140.211.166.136])
by lists.linuxfoundation.org (Postfix) with ESMTP id 602B7C0032
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 7 Nov 2023 23:22:49 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp3.osuosl.org (Postfix) with ESMTP id 33F7960A5B
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 7 Nov 2023 23:22:49 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org 33F7960A5B
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, HTML_MESSAGE=0.001, 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 0icVBd7MvRhJ
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 7 Nov 2023 23:22:47 +0000 (UTC)
Received: from www382.your-server.de (www382.your-server.de [78.46.146.228])
by smtp3.osuosl.org (Postfix) with ESMTPS id B6D11608A5
for <bitcoin-dev@lists.linuxfoundation.org>;
Tue, 7 Nov 2023 23:22:47 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp3.osuosl.org B6D11608A5
Received: from sslproxy01.your-server.de ([78.46.139.224])
by www382.your-server.de with esmtpsa (TLS1.3) tls TLS_AES_256_GCM_SHA384
(Exim 4.94.2) (envelope-from <robin@zerosync.org>)
id 1r0VPB-000AtV-C8
for bitcoin-dev@lists.linuxfoundation.org; Wed, 08 Nov 2023 00:22:45 +0100
Received: from [2001:9e8:8a6a:7000:3470:5b98:b585:72ae] (helo=smtpclient.apple)
by sslproxy01.your-server.de with esmtpsa
(TLSv1.2:ECDHE-RSA-AES256-GCM-SHA384:256) (Exim 4.92)
(envelope-from <robin@zerosync.org>) id 1r0VPB-000LL7-5r
for bitcoin-dev@lists.linuxfoundation.org; Wed, 08 Nov 2023 00:22:45 +0100
From: Robin Linus <robin@zerosync.org>
Content-Type: multipart/alternative;
boundary="Apple-Mail=_84154666-4795-43F9-B279-712CABD8B5CA"
Mime-Version: 1.0 (Mac OS X Mail 14.0 \(3654.120.0.1.13\))
Message-Id: <91D40E43-526E-42BC-BBBF-AABBD4F158F4@zerosync.org>
Date: Wed, 8 Nov 2023 00:22:44 +0100
To: bitcoin-dev@lists.linuxfoundation.org
X-Mailer: Apple Mail (2.3654.120.0.1.13)
X-Authenticated-Sender: robin@zerosync.org
X-Virus-Scanned: Clear (ClamAV 0.103.10/27086/Tue Nov 7 09:39:18 2023)
X-Mailman-Approved-At: Tue, 07 Nov 2023 23:47:30 +0000
Subject: [bitcoin-dev] Implementing Blake3 in Bitcoin Script
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, 07 Nov 2023 23:22:49 -0000
--Apple-Mail=_84154666-4795-43F9-B279-712CABD8B5CA
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
charset=us-ascii
Good morning mailing list,
We implemented a hash function in Bitcoin Script to verify Merkle =
inclusion proofs in the BitVM. This allows the VM to have sheer infinite =
memory, which doesn't have to get represented in expensive bit =
commitments.
The following transaction demonstrates on-chain a Blake3 hash lock, =
which is unlocked by providing the preimage in the unlocking script: =
https://blockstream.info/tx/d8a091a7f5ffa4993681b3df688968fd274bc76897b8b3=
953309ffad6055f4b0?expand =
<https://blockstream.info/tx/d8a091a7f5ffa4993681b3df688968fd274bc76897b8b=
3953309ffad6055f4b0?expand> If you're curious, here you can find the =
source code: =
https://github.com/BitVM/BitVM/blob/main/opcodes/examples/blake3.js=20
We chose Blake3 as it seems to be one of the most simple modern hash =
functions in terms of instruction count. We implemented only a single =
round performed over a 64 byte message, because that's sufficient for us =
to verify Merkle paths. Our implementation represents u32 words as 4 =
separate bytes on the stack, because that seemed to be the optimal =
tradeoff to implement u32 addition, u32 bitwise XOR, and u32 bitwise =
rotations, as required for Blake3.=20
We used JavaScript as templating language, to assemble complex programs =
from relatively simple opcodes. You can find the implementation of our =
u32 opcodes here: https://github.com/BitVM/BitVM/tree/main/opcodes/u32 =
<https://github.com/BitVM/BitVM/tree/main/opcodes/u32> In particular, =
for the bitwise XOR we used some cool hacks with a lookup table for a =
helper function: =
https://github.com/BitVM/BitVM/blob/main/opcodes/docs/u8_xor.md =
<https://github.com/BitVM/BitVM/blob/main/opcodes/docs/u8_xor.md>
Furthermore, we added a simple memory management, which allows us to =
have identifiers for variables, which we can read and write, and keep =
track of them while they're moved on the stack. For example, this allows =
us to implement the permutations of the Blake state simply by relabeling =
the identifiers of variables, instead of actually moving them around on =
the stack.
In total, the script is about 100kB or 25k vBytes. That's fine for now =
to build a toy-version of BitVM, but the actual plan is to split up the =
Blake code, such that verifier and prover can reduce the required =
onchain data significantly by bisecting the execution in a =
challenge-response game instead of executing it fully.
Cheers,=20
- Robin
Co-Founder and President
ZeroSync
6300 Zug
Switzerland
https://zerosync.org | https://twitter.com/zerosync_
--Apple-Mail=_84154666-4795-43F9-B279-712CABD8B5CA
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
charset=us-ascii
<html><body style=3D"word-wrap: break-word; -webkit-nbsp-mode: space; =
-webkit-line-break: after-white-space;" class=3D""><div class=3D"">Good =
morning mailing list,</div><div class=3D""><br class=3D""></div><div =
class=3D"">We implemented a hash function in Bitcoin Script to verify =
Merkle inclusion proofs in the BitVM. This allows the VM to have sheer =
infinite memory, which doesn't have to get represented in expensive bit =
commitments.</div><div class=3D""><br class=3D""></div><div class=3D"">The=
following transaction demonstrates on-chain a Blake3 hash lock, which =
is unlocked by providing the preimage in the unlocking script: <a =
href=3D"https://blockstream.info/tx/d8a091a7f5ffa4993681b3df688968fd274bc7=
6897b8b3953309ffad6055f4b0?expand" =
class=3D"">https://blockstream.info/tx/d8a091a7f5ffa4993681b3df688968fd274=
bc76897b8b3953309ffad6055f4b0?expand</a> If you're curious, here =
you can find the source code: <a =
href=3D"https://github.com/BitVM/BitVM/blob/main/opcodes/examples/blake3.j=
s" =
class=3D"">https://github.com/BitVM/BitVM/blob/main/opcodes/examples/blake=
3.js</a> </div><div class=3D""><br class=3D""></div><div =
class=3D"">We chose Blake3 as it seems to be one of the most simple =
modern hash functions in terms of instruction count. We implemented only =
a single round performed over a 64 byte message, because that's =
sufficient for us to verify Merkle paths. Our implementation represents =
u32 words as 4 separate bytes on the stack, because that seemed to be =
the optimal tradeoff to implement u32 addition, u32 bitwise XOR, and u32 =
bitwise rotations, as required for Blake3. </div><div class=3D""><br =
class=3D""></div><div class=3D"">We used JavaScript as templating =
language, to assemble complex programs from relatively simple opcodes. =
You can find the implementation of our u32 opcodes here: <a =
href=3D"https://github.com/BitVM/BitVM/tree/main/opcodes/u32" =
class=3D"">https://github.com/BitVM/BitVM/tree/main/opcodes/u32</a> I=
n particular, for the bitwise XOR we used some cool hacks with a lookup =
table for a helper function: <a =
href=3D"https://github.com/BitVM/BitVM/blob/main/opcodes/docs/u8_xor.md" =
class=3D"">https://github.com/BitVM/BitVM/blob/main/opcodes/docs/u8_xor.md=
</a></div><div class=3D""><br class=3D""></div><div =
class=3D"">Furthermore, we added a simple memory management, which =
allows us to have identifiers for variables, which we can read and =
write, and keep track of them while they're moved on the stack. For =
example, this allows us to implement the permutations of the Blake state =
simply by relabeling the identifiers of variables, instead of actually =
moving them around on the stack.</div><div class=3D""><br =
class=3D""></div><div class=3D"">In total, the script is about 100kB or =
25k vBytes. That's fine for now to build a toy-version of BitVM, but the =
actual plan is to split up the Blake code, such that verifier and prover =
can reduce the required onchain data significantly by bisecting the =
execution in a challenge-response game instead of executing it =
fully.</div><div class=3D""><br class=3D""></div><div class=3D""><br =
class=3D""></div>Cheers, <div class=3D""><span style=3D"caret-color: =
rgb(0, 0, 0); color: rgb(0, 0, 0);" class=3D"">- Robin</span></div><div =
class=3D""><font color=3D"#000000" class=3D""><span style=3D"caret-color: =
rgb(0, 0, 0);" class=3D""><br class=3D""></span></font></div><div =
class=3D""><font color=3D"#000000" class=3D""><span style=3D"caret-color: =
rgb(0, 0, 0);" class=3D""><br class=3D""></span></font></div><div =
class=3D""><font color=3D"#000000" class=3D""><span style=3D"caret-color: =
rgb(0, 0, 0);" class=3D""><br class=3D""></span></font></div><div =
class=3D""><font color=3D"#000000" class=3D""><span style=3D"caret-color: =
rgb(0, 0, 0);" class=3D""><br class=3D""></span></font><div =
class=3D""><div dir=3D"auto" style=3D"caret-color: rgb(0, 0, 0); color: =
rgb(0, 0, 0); letter-spacing: normal; text-align: start; text-indent: =
0px; text-transform: none; white-space: normal; word-spacing: 0px; =
-webkit-text-stroke-width: 0px; text-decoration: none; word-wrap: =
break-word; -webkit-nbsp-mode: space; line-break: after-white-space;" =
class=3D""><div>Co-Founder and President</div><div><br =
class=3D"">ZeroSync</div><div>6300 =
Zug</div><div>Switzerland</div><div><br class=3D""><a =
href=3D"https://zerosync.org" class=3D"">https://zerosync.org</a> | <a =
href=3D"https://twitter.com/zerosync_" =
class=3D"">https://twitter.com/zerosync_</a><br class=3D""></div></div>
</div>
<br class=3D""></div></body></html>=
--Apple-Mail=_84154666-4795-43F9-B279-712CABD8B5CA--
|
