Oleg Andreev [ARCHIVE] on Nostr: š Original date posted:2019-01-31 š Original message:Hi, We've been working for ...
š
Original date posted:2019-01-31
š Original message: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/
š Original message: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/