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>
Subject: [bitcoin-dev] Predicate Tree in ZkVM: a variant of Taproot/G'root
Precedence: list

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/