-
-
Save sipa/ca1502f8465d0d5032d9dd2465f32603 to your computer and use it in GitHub Desktop.
Hello all, | |
This document describes "Entroot", a way of integrating Graftroot natively into (a slightly improved version of) G'root, | |
itself a generalization of Taproot. It is the result of a discussion with Anthony Towns. | |
This is a longer-term idea, and shouldn't interact with the current discussions around bip-taproot. | |
The goal is defining how script validation would work while permitting the use of various "script structure" improvements | |
(Merkle branches, Taproot/P2C, Graftroot/Delegation) recursively, and combined arbitrarily. While I don't think it is at | |
all surprising that this is possible, I think the resulting formulation is remarkably elegant. | |
1. Condition points | |
Just like in G'root, everything revolves around elliptic curve points which encode the requirement to sign with a | |
particular public key, as well as satisfying any additional criteria represented by a script. | |
In general, a point Q = P + Hc(s) is a condition point where P is its (companion) public key, and s is a script. Hc here | |
stands for a hash-to-curve operation: a function which maps every input to a deterministic but unpredictable point on the | |
curve, with no known discrete logarithm. As a special optimized case, we define Hc(OP_TRUE) as the point at infinity, | |
making every public key also a valid condition point directly. | |
This is a slight improvement over the earlier idea of using a Pedersen commitment (Q = P + H(s)G2, with G2 a distinct | |
generator from the G used for public keys). Hashing to a curve is much faster than an EC multiplication, removing the | |
need for using a modified signature scheme to be batch verifiable. Given a Q and H(s)G2 it is only possible to batch | |
verify the entire operation if the signature does not commit to P, which is incompatible with the key prefixing used in | |
bip-schnorr. Verifying the hash-to-curve based version can be implementated using key-prefixed Schnorr at virtually no | |
loss in efficiency. | |
There are a number of mechanisms for implementing a hash-to-curve operation: | |
* Use the successive outputs of a PRNG seeded by the input as candidate X coordinates, until one on the curve is found. | |
This is simple and efficient in the average case (2 iterations is enough on average), but is susceptible to a grinding | |
attack where an attacker constructs their scripts using *2<sup>k</sup>* work to make verification require *k* | |
iterations. | |
* Use a constant-time algebraic operation, like in [1]. This is complicated, and avoids the grinding attack, | |
but in non-attack scenarios is significantly slower than the previous option. | |
* A third option suggested by Tadge Dryja is to use a variant of the first option, but store the iteration count in the | |
script itself. This makes scripts one byte larger on-chain, avoids the grinding attack, but also permits constant-time, | |
simple, and efficient verification. | |
2. A reformulation of G'root | |
I'm going to build up Entroot in steps, starting from a slightly convoluted way of describing G'root, which will turn out | |
to be much easier to extend. | |
Let's define a spending policy as a tree with consisting of the following node types: | |
* (Q) A single condition (a conjunction of a key and optionally a script). | |
* (M) A disjunction between two arbitrary policies (the left and right branch) | |
* (T) A disjunction between a single condition (called the common condition) and an arbitrary policy. | |
No explicit conjunction policies are included. Conjunctions of multiple keys can be represented as a single key using | |
MuSig, and conjunctions of multiple scripts can be represented by a larger script that contains all combined checks. | |
Thus, as long as a policy can be described as a disjunction between conjunctions of at least one keys and zero or more | |
script-verifiable conditions (which may themselves involve disjunctions or thresholds), the above set of permitted | |
policies is sufficient. | |
Policy type (T) may seem redundant, as it is equivalent to a type (M) where one of the child policies is a (Q). However, | |
it turns out that it can be implemented with very different trade-offs: | |
* (Q) can be implemented using the condition point construction above. To satisfy it, a signature with its public key, | |
the script, and the inputs to the script are provided. | |
* (M) can be implemented using Merkle tree nodes. To satisfy one of these, a satisfaction for the chosen branch is | |
needed, plus a 32-byte hash of the other branch. | |
* (T) can be implemented using Taproot's pay-to-contract (P2C) construction. By tweaking the condition point | |
corresponding to the common condition using a hash of the other policy, the common condition can be spent directly | |
without revealing it was in fact constructed as a disjunction with another policy. The downside however is that in | |
order to spend the right branch, both the condition and policy need to be revealed. This means it is very similar to a | |
Merkle node, however instead of costing 32 bytes for both sides, one side costs 0, and the other costs 64. This makes | |
it more appropriate than (M) in cases where the left branch is far more likely than the right one. | |
Because of the distinct data types involved (hashes for M nodes, condition points for Q and T nodes), we impose some | |
restrictions: the top of the tree can only be Q or T, and the left child of a T must be a Q. As a result, an M can only | |
occur as the right child of a T, or as the child of another M. | |
An example policy tree for a disjunction between 5 conditions (Q1=P1+Hc(s1), ..., Q6=P6+Hc(s6)), where Q1 has 99% chance | |
of being used, Q2-Q4 all have 0.25% chance, Q5 has 0.2499%, and Q6 has 0.0001%. Q1 is far more likely than everything | |
else, so it's made the common branch of the top T. Below it is a Merkle tree for the rest, but since Q6 is much less | |
likely than Q5, that disjunction is turned into another T. | |
T1 | |
/ \ | |
Q1 M1 | |
/ \ | |
M2 M3 | |
/ \ / \ | |
Q2 Q3 Q4 T2 | |
/ \ | |
Q5 Q6 | |
Any such tree can be validated using the following logic: | |
* Start with Qiter = the top level condition point in the scriptPubKey | |
* While true: | |
* Read a mode m from the stack. | |
* If m = "Q": | |
* Read from stack: script s, script input i, signature sig | |
* Verify sig against public key P=Qiter-Hc(s) and the spending transaction as message. | |
* Verify (execute) the script s with input i. | |
* break and return success | |
* If m = "T": | |
* Read from stack: points Qcommon and Qleaf, Merkle branch b | |
* Compute r = MerkleRoot(leaf=H(Qleaf), branch=b) | |
* Verify Qiter == Qcommon + H(Qcommon || r)*G | |
* Set Qiter to Qleaf | |
Examples following the policy above: | |
* Satisfying with Q1: | |
* mode="Q", s=s1, sig with key P1+H(Q1 || M1). | |
* Satisfying with Q3: | |
* mode="T", Qcommon=Q1, Qleaf=Q3, b=[H(Q2),M3] | |
* mode="Q", s=s3, sig with key P3 | |
* Satisfying with Q5: | |
* mode="T", Qcommon=Q1, Qleaf=T2, b=[H(Q4),M2] | |
* mode="Q", s=s5, sig with key P5+H(Q5 || H(Q6)). | |
* Satisfying with Q6: | |
* mode="T", Qcommon=Q1, Qleaf=T2, b=[H(Q4),M2] | |
* mode="T", Qcommon=Q5, Qleaf=Q6, b=[] | |
* mode="Q", s=s6, sig with key P6. | |
This is a pure generalization of Taproot, lifting some of its limitations while only adding trivial computational and | |
bandwidth overhead. It is not restricted to having a pure public key as common case, not restricted to a pure script in | |
the uncommon cases, and not restricted to just a single P2C tweaking for dealing with branches that are much more likely | |
than others. To maintain Taproot's "all common case spends look identical", a rule could be added that if spending | |
consists of just a single mode="Q" step, it must be a pure pubkey and not have a script component. | |
3. Adding Graftroot | |
In Graftroot, an additional way to spend is added to Taproot: instead of committing up front to the potential spending | |
policies, the top key can sign over the right to spend to a script. This permits spending costs that scale O(1) with the | |
number of permitted policies, at the cost of needing an interactive setup. | |
Similar functionality can be added very simply to the above validation logic. Inside the "While Qiter != infinity" loop, | |
another mode is added that is very similar to "Q", except the message being signed is not the transaction itself, but | |
another condition point, which we then continue with: | |
* if m = "G": | |
* Read from stack: script s, script input i, signature sig, point Qgraft | |
* Verify sig against public key P=Qiter-Hc(i) and Qgraft as message. | |
* Verify (execute) the script s with input i. | |
* Set Qiter to Qgraft | |
This enables the same functionality as Graftroot, but grafts can be performed by anyone who can satisfy any of the | |
branches. In addition, grafts can sign over to other policies. | |
A. References | |
[1] https://www.di.ens.fr/~fouque/pub/latincrypt12.pdf |
Should this proposal be updated to use hash-to-curve as proposed by the IETF?
https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-10.html
Overall, the IETF proposal is Bitcoin compatible (using tagged sha256 as a source of random bits, which are mapped to field elements), but it does require instantiating a second curve in the field that has a non-zero A, mapping to a point on that curve, and then using an isogenic mapping function to move it onto secp256k1.
I think it is technically not true to call this a pure generalization on Taproot, because all leaves in Entroot are of type Q which require a signature.
This never really got incorporated into this document, but the idea would be that you can optimize away:
- If Q=Hc(script), you can spend with just the script satisfaction (plus a marker to indicate "no key present"); in a way, treating P=infinity as the "no signature needed" key.
- If Q=P, you can spend with just the signature (plus a marker to indicate "no script present"); this is implicitly accomplished by defining Hc(OP_TRUE) as the point at infinity.
- If Q=P+Hc(script), you'd spend with both script satisfaction and a signature (plus a marker that both are present).
Should this proposal be updated to use hash-to-curve as proposed by the IETF?
I wouldn't call it a proposal. More a half-finished email about an idea I stopped working on a few years ago, and then had its URL leaked :p
https://www.ietf.org/archive/id/draft-irtf-cfrg-hash-to-curve-10.html
Yeah, I'm familiar with that approach. It may be worth benchmarking various hash-to-curve approaches if someone wants to actually propose this.
I think it is technically not true to call this a pure generalization on Taproot, because all leaves in Entroot are of type
Q
which require a signature. I'm not sure if there are use cases that require it, but it could be made a generalization by specifying aPns
that doesn't require a signature, and verifying thatQiter-Hc(s)=Pns
in the absence of a signature. This would mean that script-only nodes would not be able to graft.