Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 8C8BF7BCD for ; 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 ; Fri, 1 Feb 2019 17:56:52 +0000 (UTC) Received: by mail-pf1-f169.google.com with SMTP id q1so3574476pfi.5 for ; 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 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Fri, 01 Feb 2019 09:56:50 -0800 (PST) From: Oleg Andreev 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: To: bitcoin-dev In-Reply-To: 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 List-Unsubscribe: , List-Archive: List-Post: List-Help: List-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 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 = ` 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 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? 

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:

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#sig= ntx

`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-Ja= nuary/015614.html
[3] https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-Ju= ly/016249.html
[4] https://blockstream.com/2018/01/23/musig-key-aggregation-schnor= r-signatures/




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