Entroot mail

mail-entroot.txt

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

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)

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.

@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.

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.

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.