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" — 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 = x*B (x is a secret, B is a primary generator point)
Program commitment is a P2SH-like commitment:
P = 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 = 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/015614.html
[3]
https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-July/016249.html
[4] https://blockstream.com/2018/01/23/musig-key-aggregation-schnorr-signatures/
_______________________________________________
bitcoin-dev mailing list
bitcoin-dev@lists.linuxfoundation.org
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
