path: root/14/2a32df86a74b6eb1b63d79412aa2dbfb803721

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 8C8BF7BCD
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri,  1 Feb 2019 17:56:53 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-pf1-f169.google.com (mail-pf1-f169.google.com
	[209.85.210.169])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 59A5E829
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri,  1 Feb 2019 17:56:52 +0000 (UTC)
Received: by mail-pf1-f169.google.com with SMTP id q1so3574476pfi.5
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Fri, 01 Feb 2019 09:56:52 -0800 (PST)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025;
	h=from:mime-version:subject:date:references:to:in-reply-to:message-id; 
	bh=KKe03/c1PYo4zUXcoYgq+qbqe00D/5DM+BOCO4LgH9Q=;
	b=LiYHiwXDmlhQuGVa8zF5u9skUnNxQa3Xo2WSAmlLjRkPiSRvdOsKLWSzmsgH0naFaP
	XRfeAvLLDFrk23vSdrEwg+2/AaUdiLpWsdHP6QJzm4nUUdWdYqRPI1qL97/lN2vHSqjr
	5FTvcCsr1bsTnmaAgYVtuzerDJxmzpmZYZniq9oU2buCYyjNOX4WXdJNiaaCTJBuPRl4
	nSOnRO6a2ALy8asEuMEuvIiiYmwYUv89pGz4ZkQI2vMeRbv302fMvWDb0Rz2JS0KHeO4
	URoSMth5o72Hb1G+SAjbrdGyRDPigH1JwHUqjVW67U7zSeL8stCPi1ZN8w7prPaWWkyS
	QNNw==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20161025;
	h=x-gm-message-state:from:mime-version:subject:date:references:to
	:in-reply-to:message-id;
	bh=KKe03/c1PYo4zUXcoYgq+qbqe00D/5DM+BOCO4LgH9Q=;
	b=lzR406UDmTTudyLYXkvlVULHh8rIzWRDDOfNls0UdgnYt8NHI3/posBOdn2EAT7b0z
	8f6wt01PlhxNWjG4nNnXxjutnywAdX8w4Xj89yAfEXaXtnPa7T+1FP+cdBOBz4s6okNv
	RfnI+jGyLQlwXf4praPrYgmXCid7RDknjKZLGsgWOhP84xIw/UC5XZG1E+WM9QkaB6Vk
	kW1m90gZAD0OCg/1CJrTCFJey23ObR3jhnyD3eooRRh0Sal/WbZ5qXS1hIEUJGtujW04
	mSKcIVYK59SavuVm3c66sKL5bsk+9uyMUMXg9M4VjKx6dbikSd1le+cOm5QlerNF0cQ2
	Kwcw==
X-Gm-Message-State: AHQUAuanzDK1ynRDd3Y7HBxDeE5/i2XNBqm2rycW/r0cq1oBP35rgb/v
	1N4OGL0e2Ea3Ew9DAWpSVA4ifgp/
X-Google-Smtp-Source: AHgI3IYEossMO1Zn6LiEbUmGrq+5d/FydSN3oItfgG5H1cNYLcoZV0XbA15k7OOM3EihSvuMcA9oBg==
X-Received: by 2002:a63:9e19:: with SMTP id s25mr3180109pgd.203.1549043811084; 
	Fri, 01 Feb 2019 09:56:51 -0800 (PST)
Received: from [10.21.171.74] ([68.65.169.20])
	by smtp.gmail.com with ESMTPSA id
	r1sm12040490pgo.17.2019.02.01.09.56.49
	for <bitcoin-dev@lists.linuxfoundation.org>
	(version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128);
	Fri, 01 Feb 2019 09:56:50 -0800 (PST)
From: Oleg Andreev <oleganza@gmail.com>
Content-Type: multipart/alternative;
	boundary="Apple-Mail=_00F43F46-BAE0-457E-8EC3-14D735800805"
Mime-Version: 1.0 (Mac OS X Mail 12.2 \(3445.102.3\))
Date: Fri, 1 Feb 2019 09:56:49 -0800
References: <B88B34DB-8FBE-4B45-9E24-6676384C54F2@gmail.com>
To: bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
In-Reply-To: <B88B34DB-8FBE-4B45-9E24-6676384C54F2@gmail.com>
Message-Id: <902846E6-80CC-4713-8467-932274182B75@gmail.com>
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, HTML_MESSAGE,
	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: Sat, 02 Feb 2019 02:37:05 +0000
Subject: Re: [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: Fri, 01 Feb 2019 17:56:53 -0000


--Apple-Mail=_00F43F46-BAE0-457E-8EC3-14D735800805
Content-Transfer-Encoding: quoted-printable
Content-Type: text/plain;
	charset=utf-8

A follow-up comment: I've have sent this email right before Pieter's =
talk on miniscript at Stanford yesterday. I want to express my =
appreciation to the thinking about scripts/contracts that Pieter, Andy, =
Greg have been promoting for long time. These ideas influenced a lot the =
design decisions in ZkVM: "blockchain as a court", very limited =
functionality and clarity of scripts, and, as Pieter laid out yesterday, =
composition of policies. These are all the same values that I'm trying =
to reflect in ZkVM, that's why i think it might be interesting to this =
mailing list.

Also, Neha Narula asked a question this morning:

> Isn't this a DoS vector, in that an attacker could generate a lot of =
expensive code to execute in the VM which would then be rejected once =
the checks get executed?  If so, how critical is this deferred execution =
of point operations to your design?=20

The answer: hopefully it's not a DoS vector, we are working on this =
right now. Programs for `call` and `delegate` have to be statically =
built into the transaction bytecode string, and cannot be constructed =
within the VM (so it's very similar to P2SH). ZkVM is similar to Bitcoin =
Script in that the execution cost is proportional to the program length: =
one cannot make a short program that would use loops or recursion into =
dynamically constructed programs to exhibit arbitrary validation cost. =
For those familiar with TxVM released last year, we are removing loops =
and dynamic program construction, and gas-like "runlimit" with them from =
ZkVM.

Another feature is inspired by old proposal by Pieter (IIRC) to treat =
checksig as all-or-nothing. ZkVM does not do dynamic branching based on =
outcomes of expensive operations. Signature checks, predicate tree =
traversal - all have to unconditionally succeed.

1. This makes the program execution (w/o ECC ops) very fast and =
proportional to the length of the program.
2. Then, all the collected ECC ops give precise metric of how expensive =
the rest of the validation would be.
3. Plus, the constraint system proof blob (that comes with the =
transaction) by itself gives an exact measurement of the bulletproofs =
validation cost.

The upstream protocol ("blockchain rules") can have soft- or hard- caps =
on both program length and amount of ECC operations (similar to the =
limit on sig checks per block in Bitcoin). That said, we haven't drilled =
into specifics what these caps should be and how they should be =
enforced, that's still in the works.


> On Jan 31, 2019, at 15:44 , Oleg Andreev <oleganza@gmail.com> wrote:
>=20
> Hi,
>=20
> 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.
>=20
> 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.
>=20
> ## Background
>=20
> 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.
>=20
> ## Predicate Tree
>=20
> Predicate is a point that represents one of three things, which allows =
composing conditions in an arbitrary tree:
>=20
> 1. Public key
> 2. Program
> 3. Disjunction of two other predicates
>=20
> 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):
>=20
>   P =3D x*B  (x is a secret, B is a primary generator point)
>=20
> Program commitment is a P2SH-like commitment:
>=20
>   P =3D hash2scalar(program)*B2   (B2 is orthogonal to B, so one =
cannot sign for P, but must reveal the program)
>=20
> Disjunction (asymmetric to allow happy-path signing with the left =
predicate):
>=20
>   P =3D L + hash2scalar(L,R)*B
>=20
>=20
> ## VM instructions
>=20
> To use the predicate trees, ZkVM provides 4 instructions:
>=20
> 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).
>=20
> More details are in the ZkVM spec: =
https://github.com/interstellar/zkvm/blob/main/spec/ZkVM.md#signtx
>=20
> `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.
>=20
>=20
> ## Performance
>=20
> For performance, the following rules are built into ZkVM:
>=20
> 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.
>=20
>=20
> ## What is different from Taproot/G'root
>=20
> (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.
>=20
> (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.
>=20
>=20
> ## References
>=20
> [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/
>=20
>=20
>=20


--Apple-Mail=_00F43F46-BAE0-457E-8EC3-14D735800805
Content-Transfer-Encoding: quoted-printable
Content-Type: text/html;
	charset=utf-8

<html><head><meta http-equiv=3D"Content-Type" content=3D"text/html; =
charset=3Dutf-8"></head><body style=3D"word-wrap: break-word; =
-webkit-nbsp-mode: space; line-break: after-white-space;" class=3D"">A =
follow-up comment: I've have sent this email right before Pieter's talk =
on miniscript at Stanford yesterday. I want to express my appreciation =
to the thinking about scripts/contracts that Pieter, Andy, Greg have =
been promoting for long time. These ideas influenced a lot the design =
decisions in ZkVM: "blockchain as a court", very limited functionality =
and clarity of scripts, and, as Pieter laid out yesterday, composition =
of policies. These are all the same values that I'm trying to reflect in =
ZkVM, that's why i think it might be interesting to this mailing =
list.<div class=3D""><br class=3D""></div><div class=3D"">Also, Neha =
Narula asked a question this morning:</div><div class=3D""><br =
class=3D""></div><div class=3D""><blockquote type=3D"cite" =
style=3D"font-family: monospace; font-size: 12px;" class=3D"">Isn't this =
a DoS vector, in that an attacker could generate a lot of expensive code =
to execute in the VM which would then be rejected once the checks get =
executed?&nbsp;&nbsp;If so, how critical is this deferred execution of =
point operations to your design?&nbsp;</blockquote><div><br =
class=3D""></div><div>The answer: hopefully it's not a DoS vector, we =
are working on this right now. Programs for `call` and `delegate` have =
to be statically built into the transaction bytecode string, and cannot =
be constructed within the VM (so it's very similar to P2SH). ZkVM is =
similar to Bitcoin Script in that the execution cost is proportional to =
the program length: one cannot make a short program that would use loops =
or recursion into dynamically constructed programs to exhibit arbitrary =
validation cost. For those familiar with TxVM released last year, we are =
removing loops and dynamic program construction, and gas-like "runlimit" =
with them from ZkVM.</div><div><br class=3D""></div><div>Another feature =
is inspired by old proposal by Pieter (IIRC) to treat checksig as =
all-or-nothing. ZkVM does not do dynamic branching based on outcomes of =
expensive operations. Signature checks, predicate tree traversal - all =
have to unconditionally succeed.</div><div><br class=3D""></div><div>1. =
This makes the program execution (w/o ECC ops) very fast and =
proportional to the length of the program.</div><div>2. Then, all the =
collected ECC ops give precise metric of how expensive the rest of the =
validation would be.</div><div>3. Plus, the constraint system proof blob =
(that comes with the transaction) by itself gives an exact measurement =
of the bulletproofs validation cost.</div><div><br =
class=3D""></div><div>The upstream protocol ("blockchain rules") can =
have soft- or hard- caps on both program length and amount of ECC =
operations (similar to the limit on sig checks per block in Bitcoin). =
That said, we haven't drilled into specifics what these caps should be =
and how they should be enforced, that's still in the =
works.</div><div><br class=3D""></div><div><br =
class=3D""></div><div><blockquote type=3D"cite" class=3D""><div =
class=3D"">On Jan 31, 2019, at 15:44 , Oleg Andreev &lt;<a =
href=3D"mailto:oleganza@gmail.com" class=3D"">oleganza@gmail.com</a>&gt; =
wrote:</div><br class=3D"Apple-interchange-newline"><div class=3D""><div =
class=3D"">Hi,<br class=3D""><br class=3D"">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.<br class=3D""><br =
class=3D"">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.<br class=3D""><br =
class=3D"">## Background<br class=3D""><br class=3D"">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.<br class=3D""><br class=3D"">## Predicate Tree<br =
class=3D""><br class=3D"">Predicate is a point that represents one of =
three things, which allows composing conditions in an arbitrary tree:<br =
class=3D""><br class=3D"">1. Public key<br class=3D"">2. Program<br =
class=3D"">3. Disjunction of two other predicates<br class=3D""><br =
class=3D"">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):<br class=3D""><br class=3D""> &nbsp;&nbsp;P =3D =
x*B &nbsp;(x is a secret, B is a primary generator point)<br =
class=3D""><br class=3D"">Program commitment is a P2SH-like =
commitment:<br class=3D""><br class=3D""> &nbsp;&nbsp;P =3D =
hash2scalar(program)*B2 &nbsp;&nbsp;(B2 is orthogonal to B, so one =
cannot sign for P, but must reveal the program)<br class=3D""><br =
class=3D"">Disjunction (asymmetric to allow happy-path signing with the =
left predicate):<br class=3D""><br class=3D""> &nbsp;&nbsp;P =3D L + =
hash2scalar(L,R)*B<br class=3D""><br class=3D""><br class=3D"">## VM =
instructions<br class=3D""><br class=3D"">To use the predicate trees, =
ZkVM provides 4 instructions:<br class=3D""><br class=3D"">1. `signtx` =
to verify the signature over the transaction ID treating the predicate =
as a pubkey.<br class=3D"">2. `call` to reveal the committed program and =
execute it.<br class=3D"">3. `left`/`right` to replace the contract's =
predicate with one of the sub-predicates in a disjunction.<br =
class=3D"">4. `delegate` to check a signature over a program and execute =
that program (pay-to-signed-program pattern).<br class=3D""><br =
class=3D"">More details are in the ZkVM spec: <a =
href=3D"https://github.com/interstellar/zkvm/blob/main/spec/ZkVM.md#signtx=
" =
class=3D"">https://github.com/interstellar/zkvm/blob/main/spec/ZkVM.md#sig=
ntx</a><br class=3D""><br class=3D"">`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.<br class=3D""><br class=3D""><br class=3D"">## =
Performance<br class=3D""><br class=3D"">For performance, the following =
rules are built into ZkVM:<br class=3D""><br class=3D"">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.<br class=3D"">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.<br class=3D""><br class=3D""><br =
class=3D"">## What is different from Taproot/G'root<br class=3D""><br =
class=3D"">(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.<br class=3D""><br class=3D"">(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:<br class=3D"">1. The =
happy-path one-time-key normally acts as a sufficient blinding factor =
for the program.<br class=3D"">2. If the program needs a blinding =
factor, it can be embedded as a `&lt;garbage&gt; drop`.<br class=3D"">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.<br =
class=3D""><br class=3D""><br class=3D"">## References<br class=3D""><br =
class=3D"">[1] <a href=3D"https://github.com/interstellar/zkvm" =
class=3D"">https://github.com/interstellar/zkvm</a><br class=3D"">[2] <a =
href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-Janua=
ry/015614.html" =
class=3D"">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-Ja=
nuary/015614.html</a><br class=3D"">[3] <a =
href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/=
016249.html" =
class=3D"">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-Ju=
ly/016249.html</a><br class=3D"">[4] <a =
href=3D"https://blockstream.com/2018/01/23/musig-key-aggregation-schnorr-s=
ignatures/" =
class=3D"">https://blockstream.com/2018/01/23/musig-key-aggregation-schnor=
r-signatures/</a><br class=3D""><br class=3D""><br class=3D""><br =
class=3D""></div></div></blockquote></div><br =
class=3D""></div></body></html>=

--Apple-Mail=_00F43F46-BAE0-457E-8EC3-14D735800805--