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
|
Return-Path: <oleganza@gmail.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id DAAE14679
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 31 Jan 2019 23:44:46 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-pl1-f170.google.com (mail-pl1-f170.google.com
[209.85.214.170])
by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 5035B852
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 31 Jan 2019 23:44:46 +0000 (UTC)
Received: by mail-pl1-f170.google.com with SMTP id e11so2202785plt.11
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 31 Jan 2019 15:44:46 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
h=from:content-transfer-encoding:mime-version:subject:message-id:date
:to; bh=PveF5o9qRjC8OHwLi/WnVtFUUX1Bj2Yz2m2MFAcm0gE=;
b=k5nqQhs97+DxB9krEgKMf+LED17vw9F3XW1qQuobzpExEetbxEHP/PYwqykO8pKY9Z
b2pFp/WCy9DxeBlSBmf+++hrjDBH813Bis+IQP7jmTSqpJhFfgP/ErP5laVFt5AsmDh7
lHV0kKY47Nx4z4XeOKTZ4sLmxjgI2QSCeR0HEyqwhR1VvY6++BZBBk+kL63JswcIKFS3
Jh3Jn/eqzOUcjcEstlcWp/lQyW0Mo7PdA6Lx0Fz//ZFq8TrrM8Q+p2j9z6QwURk9WTQu
SDi/0mYHZU0hPcJnkseUR0G8ri8dMmjsqnEFiGvTGqYtahzzrQCe5p8ruxx8+WxoYuIh
NdiQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20161025;
h=x-gm-message-state:from:content-transfer-encoding:mime-version
:subject:message-id:date:to;
bh=PveF5o9qRjC8OHwLi/WnVtFUUX1Bj2Yz2m2MFAcm0gE=;
b=i22742Px8CAuhpCz5Bq39eJ4RqoMAhPq/p/dMi2xpqxaTeRgxVcGa4c+cdhLpumG/D
lmJ+My2IAdEbMSup5oHdDTlrIpgGk7kBMC3B2HfIlAi4W9bu5yPW2ernKRR1Aby6YKex
axLqw3OWer951pGEo0Tb/zgQUCOu6/HZ/4hrZ7a7bzgR4catY6a2RtvwDAPD/u+XIY/w
u3ioKqhz7U2Dw1WDBn5FnNk/VM9aV0J3lSuW7Cfi0FuRI+GbGPWGRwhCWyINVqH2xX/x
G+tlg/pyi6rk/6tn2ykSSsmUPcHNz5fj3Ks3xXZpu3MofOxDsjc1el5MhZp9sDgzHJMD
y3hA==
X-Gm-Message-State: AJcUukfHZDWBCbpl8EPn60SFZBP11jFntVDJB6F0m95ZtHTTXcARGrDi
7zj/yQ+B97M5Y0H7jiZ2coh9HfSd
X-Google-Smtp-Source: ALg8bN4e9Vc1GjapcjDIzVQ7B/rPnFlJUt1/15dF/16yFSVjSxNc3g0mI7HUFKgQ5Lcwx7hJzJXQzA==
X-Received: by 2002:a17:902:9f93:: with SMTP id
g19mr36353816plq.195.1548978285486;
Thu, 31 Jan 2019 15:44:45 -0800 (PST)
Received: from [10.21.168.80] ([68.65.169.20])
by smtp.gmail.com with ESMTPSA id
r76sm8445832pfb.69.2019.01.31.15.44.44
for <bitcoin-dev@lists.linuxfoundation.org>
(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
Thu, 31 Jan 2019 15:44:45 -0800 (PST)
From: Oleg Andreev <oleganza@gmail.com>
Content-Type: text/plain;
charset=utf-8
Content-Transfer-Encoding: quoted-printable
Mime-Version: 1.0 (Mac OS X Mail 12.2 \(3445.102.3\))
Message-Id: <B88B34DB-8FBE-4B45-9E24-6676384C54F2@gmail.com>
Date: Thu, 31 Jan 2019 15:44:43 -0800
To: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
X-Mailer: Apple Mail (2.3445.102.3)
X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED,
DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM,
RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
smtp1.linux-foundation.org
X-Mailman-Approved-At: Fri, 01 Feb 2019 14:56:03 +0000
Subject: [bitcoin-dev] Predicate Tree in ZkVM: a variant of Taproot/G'root
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: Thu, 31 Jan 2019 23:44:47 -0000
Hi,
We've been working for a thing called ZkVM [1] for the last few weeks. =
It is a "blockchain virtual machine" in the spirit of Bitcoin, with =
multi-asset transfers and zero-knowledge programmable constraints.
As a part of its design, there is a "Predicate Tree" =E2=80=94 a variant =
of Taproot by Greg Maxwell [2] and G'root by Anthony Towns [3] that I =
would like to present here. Hopefully it is useful to the discussion, =
and I would appreciate any feedback.
## Background
In ZkVM there are linear types Contract and Value (in addition to plain =
data types), where Contract also implements "object capabilities" =
pattern: Contract "locks" a collection of data and Values under a =
"predicate" which is represented by a single group element ("point" in =
ECC terms). The predicate can be "satisfied" in a number of allowed ways =
which makes the contract unlock its contents, e.g. release the stored =
Value which can then be locked in a new unspent output.
## Predicate Tree
Predicate is a point that represents one of three things, which allows =
composing conditions in an arbitrary tree:
1. Public key
2. Program
3. Disjunction of two other predicates
Public key allows representing N-of-N signing conditions (and M-of-N =
with proper threshold key setup, although small combinations like 2-of-3 =
can be non-interactively represented as a tree of 3 combinations of =
2-of-2 conditions):
P =3D x*B (x is a secret, B is a primary generator point)
Program commitment is a P2SH-like commitment:
P =3D hash2scalar(program)*B2 (B2 is orthogonal to B, so one cannot =
sign for P, but must reveal the program)
Disjunction (asymmetric to allow happy-path signing with the left =
predicate):
P =3D L + hash2scalar(L,R)*B
## VM instructions
To use the predicate trees, ZkVM provides 4 instructions:
1. `signtx` to verify the signature over the transaction ID treating the =
predicate as a pubkey.
2. `call` to reveal the committed program and execute it.
3. `left`/`right` to replace the contract's predicate with one of the =
sub-predicates in a disjunction.
4. `delegate` to check a signature over a program and execute that =
program (pay-to-signed-program pattern).
More details are in the ZkVM spec: =
https://github.com/interstellar/zkvm/blob/main/spec/ZkVM.md#signtx
`call` and `delegate` differ in that `call` reveals and runs a =
pre-arranged program (like in P2SH), while `delegate` allows choosing =
the program later which can be signed with a pre-arranged public key. =
`delegate` also enables use cases for SIGHASH: if a specific output or =
outputs or constraints must be signed, they can be represented by such =
program snippet. Likewise, a "revocation token" for the payment channel =
(LN) can be implemented with `delegate` instruction.
## Performance
For performance, the following rules are built into ZkVM:
1. All point operations are deferred. Signature checks, disjunction =
proofs, program commitment proofs - are not executed right away, but =
deferred and verified in a batch after the VM execution is complete. =
This enables significant savings, especially since half or third of the =
terms reuse static points B and B2.
2. `signtx` does not accept individual signatures, but uses a single =
aggregated signature for the whole transaction. All the pubkeys are =
remembered in a separate set and combined via MuSig-style [4] protocol =
to check the single 64-byte signature over txid in the end of the VM =
execution. In other words, signature aggregation is not optional for =
`signtx` (signatures over txid). Note: the `delegate` instruction =
permits arbitrary programs, so it uses one signature per program.
## What is different from Taproot/G'root
(1) No pure hash-based MAST: each time one peels off a layer of a tree, =
there's an ECC check which is more expensive than pure-hash merkle path =
check, but makes the design simpler and all ECC ops are batched =
alongside bulletproofs R1CS verification statement, making the =
performance difference unimportant.
(2) There is no designated blinding factor or a pubkey with the program =
commitment like in G'root. This is not something i'm particularly sure =
about, but will lay out the current rationale:
1. The happy-path one-time-key normally acts as a sufficient blinding =
factor for the program.
2. If the program needs a blinding factor, it can be embedded as a =
`<garbage> drop`.
3. The combo of "sign + programmatic constraints" is done by having =
instructions inside the program that wrap the value(s) in a transient =
contract with the required pubkey and leaving it on the stack.
## References
[1] https://github.com/interstellar/zkvm
[2] =
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-January/01561=
4.html
[3] =
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016249.h=
tml
[4] =
https://blockstream.com/2018/01/23/musig-key-aggregation-schnorr-signature=
s/
|
