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
|
Return-Path: <ZmnSCPxj@protonmail.com>
Received: from smtp2.osuosl.org (smtp2.osuosl.org [IPv6:2605:bc80:3010::133])
by lists.linuxfoundation.org (Postfix) with ESMTP id 2F53AC0032
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 15 Oct 2023 15:15:59 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp2.osuosl.org (Postfix) with ESMTP id 0209E40600
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 15 Oct 2023 15:15:59 +0000 (UTC)
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 0209E40600
Authentication-Results: smtp2.osuosl.org;
dkim=pass (2048-bit key) header.d=protonmail.com header.i=@protonmail.com
header.a=rsa-sha256 header.s=protonmail3 header.b=XLpP1DyE
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: 0.3
X-Spam-Level:
X-Spam-Status: No, score=0.3 tagged_above=-999 required=5
tests=[BAYES_40=-0.001, DKIM_SIGNED=0.1, DKIM_VALID=-0.1,
DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001,
FROM_LOCAL_NOVOWEL=0.5, RCVD_IN_MSPIKE_H5=0.001,
RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001]
autolearn=ham autolearn_force=no
Received: from smtp2.osuosl.org ([127.0.0.1])
by localhost (smtp2.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id EvbbNHi_oG56
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 15 Oct 2023 15:15:54 +0000 (UTC)
X-Greylist: delayed 5981 seconds by postgrey-1.37 at util1.osuosl.org;
Sun, 15 Oct 2023 15:15:54 UTC
DKIM-Filter: OpenDKIM Filter v2.11.0 smtp2.osuosl.org 9B115404ED
Received: from mail-40138.protonmail.ch (mail-40138.protonmail.ch
[185.70.40.138])
by smtp2.osuosl.org (Postfix) with ESMTPS id 9B115404ED
for <bitcoin-dev@lists.linuxfoundation.org>;
Sun, 15 Oct 2023 15:15:54 +0000 (UTC)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=protonmail.com;
s=protonmail3; t=1697382952; x=1697642152;
bh=VHBiOH1+lOjF4TiMV9HD82rvv3LSxsQY3wBAJF0dLTM=;
h=Date:To:From:Cc:Subject:Message-ID:In-Reply-To:References:
Feedback-ID:From:To:Cc:Date:Subject:Reply-To:Feedback-ID:
Message-ID:BIMI-Selector;
b=XLpP1DyEk6URZ/y6eOMChlnJuh+IJtzkQRmz7cSpTjBFQhaiJ3BaSNf5G2yUhLr0n
pwgymgLp4d7ODQ4cJ5ax4trP8QxRrF1jaQGhRomPW6n1syQ36k+h0kstedmnYPDrwh
0xsyGG3mna4VvDqIyHwLoc30qVOoC8b4W+p44QF8v4V4pT/FGW27Wvo0CBhm5/f2hb
UEd7rZ+oZ+eDiAjlq+ppCeRMT8cLBGuybXg4rFan/4JfTyAjDAe4X10zOAWj5XXeHr
0R1EDnP3PwN6GvzA7rhtpzPPt0VLAOBqNi+lqJD395T6j6UbSrSpNcUgQuoIQwk0ea
4xl2vhnF1YJOw==
Date: Sun, 15 Oct 2023 15:15:49 +0000
To: Robin Linus <robin@zerosync.org>
From: ZmnSCPxj <ZmnSCPxj@protonmail.com>
Message-ID: <0J6o-j9oKRfD8-D3VURz4e1Ke8-DD3YhHQu4QvElrwd84meA1yvTs9KdQaTatpAfgXAPLfGn78MxitDT1AF76UE4yy53Ym6rOyy0B-4ey5k=@protonmail.com>
In-Reply-To: <CCA561B6-A2DE-46FD-A2F8-98E0C34A3EEE@zerosync.org>
References: <CCA561B6-A2DE-46FD-A2F8-98E0C34A3EEE@zerosync.org>
Feedback-ID: 2872618:user:proton
MIME-Version: 1.0
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
Cc: bitcoin-dev@lists.linuxfoundation.org
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: Sun, 15 Oct 2023 15:15:59 -0000
Good morning Robin et al,
It strikes me that it may be possible to Scriptless Script BitVM, replacing=
hashes and preimages with points and scalars.
For example, equivocation of bit commitments could be done by having the pr=
over put a slashable fund behind a pubkey `P` (which is a point).
This slashable fund could be a 2-of-2 between prover and verifier `P && V`.
Then the prover provides a bit-0 point commitment `B`, which is a point.
If the prover wants to assert that this specific bit is 0, it has to provid=
e `b` such that `B =3D b * G`.
If the prover wants to instead assert that this bit is 1, it has to provide=
`b + p` such that `B =3D b * G` and `P =3D p * G`.
If `b` (and therefore `B`) is chosen uniformly at random, if it makes exact=
ly one of these assertions (that the bit is 0, or that the bit is 1) then i=
t does not reveal `p`.
But if it equivocates and asserts both, it reveals `b` and `b + p` and the =
verifier can get the scalar `p`, which is also the private key behind `P` a=
nd thus can get the fund `P && V`.
To create a logic gate commitment, we have the prover and validator provide=
public keys for each input-possibility and each output-possibility, then u=
se MuSig to combine them.
For example, suppose we have a NAND gate with inputs I, J and output K.
We have:
* `P[I=3D0]` and `V[I=3D0]`, which are the public keys to use if input I is=
0.
* `P[I=3D1]` and `V[I=3D1]`, which are the public keys to use if input I is=
1.
* ...similar for input `J` and output `K`.
In the actual SCRIPT, we take `MuSig(P[I=3D0], V[I=3D0])` etc.
For a SCRIPT to check what the value of `I` is, we would have something lik=
e:
```
OP_DUP <MuSig(P[I=3D1], V[I=3D1])> OP_CHECKSIG
OP_IF
OP_DROP
<1>
OP_ELSE
<MuSig(P[I=3D0], V[I=3D0])> OP_CHECKSIGVERIFY
<0>
OP_ENDIF
```
We would duplicate the above (with appropriate `OP_TOALTSTACK` and `OP_FROM=
ALTSTACK`) for input `J` and output `K`, similar to Fig.2 in the paper.
The verifier then provides adaptor signatures, so that for `MuSig(P[I=3D1],=
V[I=3D1])` the prover can only complete the signature by revealing the `b =
+ p` for `I`.
Similar for `MuSig(P[I=3D0], V[I=3D0])`, the verifier provides adaptor sign=
atures so that the prover can only complete the signature by revealing the =
`b` for `I`.
And so on.
Thus, the prover can only execute the SCRIPT by revealing the correct commi=
tments for `I`, `J`, and `K`, and any equivocation would reveal `p` and let=
the verifier slash the fund of `P`.
Providing the adaptor signatures replaces the "unlock" of the challenge-res=
ponse phase, instead of requiring a preimage from the verifier.
The internal public key that hides the Taproot tree containing the above lo=
gic gate commitments could be `MuSig(P, V)` so that the verifier can stop a=
nd just take the funds by a single signature once it has learned `p` due to=
the prover equivocating.
Not really sure if this is super helpful or not.
Hashes are definitely less CPU to compute.
For example, would it be possible to have the Tapleaves be *just* the wires=
between NAND gates instead of NAND gates themselves?
So to prove a NAND gate operation with inputs `I` and `J` and output `K`, t=
he prover would provide bit commitments `B` for `B[I]`, `B[J]`, and `B[K]`,=
and each tapleaf would be just the bit commitment SCRIPT for `I`, `J`, and=
`K`.
The prover would have to provide `I` and `J`, and commit to those, and then=
verifier would compute `K =3D ~(I & J)` and provide *only* the adaptor sig=
nature for `MuSig(P[K=3D<result>], V[K=3D<result>])`, but not the other sid=
e.
In that case, it may be possible to just collapse it down to `MuSig(P, V)` =
and have the verifier provide individual adaptor signatures.
For example, the verifier can first challenge the prover to commit to the v=
alue of `I` by providing two adaptor signatures for `MuSig(P, V)`, one for =
the scalar behind `B[I]` and the other for the scalar behind `B[I] + P`.
The prover completes one or the other, then the verifier moves on to `B[J]`=
and `B[J] + P`.
The prover completes one or the other, then the verifier now knows `I` and =
`J` and can compute the supposed output `K`, and provides only the adaptor =
signature for `MuSig(P, V)` for the scalar behind `B[K]` or `B[K] + P`, dep=
ending on whether `K` is 0 or 1.
That way, you only really actually need Schnorr signatures without having t=
o use Tapleaves at all.
This would make BitVM completely invisible on the blockchain, even in a uni=
lateral case where one of the prover or verifier stop responding.
Regards,
ZmnSCPxj
|
