Skip to content

Instantly share code, notes, and snippets.

# sipa/mail-entroot.txt Secret

Last active May 12, 2022 22:30
Show Gist options
• Save sipa/ca1502f8465d0d5032d9dd2465f32603 to your computer and use it in GitHub Desktop.
Entroot mail
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
 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 *2k* 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

### jonasnick commented Sep 21, 2021

Typos:

• `P1+H(Q1 || M1)` -> `P1+H(Q1 || M1)*G`
• `P5+H(Q5 || H(Q6))` -> `P5+H(Q5 || H(Q6))*G`
• `P=Qiter-Hc(i)` -> `P=Qiter-Hc(s)`

### RubenSomsen commented Oct 5, 2021

While I don't think there's a reason for anyone to ever do this, it may be worth noting that if you were to sign over the right to spend to the same key (e.g. P == Qgraft) and then proceed to spend, the resulting witness could be malleated by any third party by recursively repeating the graft.

### sipa commented Nov 8, 2021

@RubenSomsen Interesting observation. Perhaps the depth, or even the contents of the chain up to every point should be included in the hashes being signed.

### reardencode commented Jan 7, 2022

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 a `Pns` that doesn't require a signature, and verifying that `Qiter-Hc(s)=Pns` in the absence of a signature. This would mean that script-only nodes would not be able to graft.

### reardencode commented Jan 7, 2022

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.

### sipa commented Jan 7, 2022 • edited Loading

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.

to join this conversation on GitHub. Already have an account? Sign in to comment