[bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode

[Anthony Towns]

On Thu, Sep 09, 2021 at 12:26:37PM -0700, Jeremy wrote:
> I'm a bit skeptical of the safety of the control byte. Have you considered the
> following issues?

>     If we used the script "0 F 0 TLUV" (H=F, C=0) then we keep the current
>     script, keep all the steps in the merkle path (AB and CD), and add
>     a new step to the merkle path (F), giving us:
>         EF = H_TapBranch(E, F)
>         CDEF =H_TapBranch(CD, EF)
>         ABCDEF = H_TapBranch(AB, CDEF)
> 
> If we recursively apply this rule, would it not be possible to repeatedly apply
> it and end up burning out path E beyond the 128 Taproot depth limit?

Sure. Suppose you had a script X which allows adding a new script A[0..n]
as its sibling. You'd start with X and then go to (A0, X), then (A0,
(A1, X)), then (A0, (A1, (A2, X))) and by the time you added A127 TLUV
would fail because it'd be trying to add a path longer than 128 elements.

But this would be bad anyway -- you'd already have a maximally unbalanced
tree. So the fix for both these things would be to do a key path spend
and rebalance the tree. With taproot, you always want to do key path
spends if possible.

Another approach would be to have X replace itself not with (X, A) but
with (X, (X, A)) -- that way you go from:

   /\
  A  X

to 
     /\
    A /\
     X /\
      B  X
  
to 
      /\
     /  \
    A   /\
       /  \
      /    \
     /\    /\
    C  X  B  X

and can keep the tree height at O(log(n)) of the number of members.

This means the script X would need a way to reference its own hash, but
you could do that by invoking TLUV twice, once to check that your new
sPK is adding a sibling (X', B) to the current script X, and a second
time to check that you're replacing the current script with (X', (X',
B)). Executing it twice ensures that you've verified X' = X, so you can
provide X' on the stack, rather than trying to include the script's on
hash in itself.

> Perhaps it's OK: E can always approve burning E?

As long as you've got the key path, then I think that's the thing to do.

>     If we used the script "0 F 4 TLUV" (H=F, C=4) then we keep the current
>     script, but drop the last step in the merkle path, and add a new step
>     (effectively replacing the *sibling* of the current script):
>         EF = H_TapBranch(E, F)
>         ABEF = H_TapBranch(AB, EF) 
>     If we used the script "0 0 4 TLUV" (H=empty, C=4) then we keep the current
>     script, drop the last step in the merkle path, and don't add anything new
>     (effectively dropping the sibling), giving just:
>         ABE = H_TapBranch(AB, E)
> 
> Is C = 4 stable across all state transitions? I may be missing something, but
> it seems that the location of C would not be stable across transitions.

Dropping a sibling without replacing it or dropping the current script
would mean you could re-execute the same script on the new utxo, and
repeat that enough times and the only remaining ways of spending would
be that script and the key path.

> E.g., What happens when, C and E are similar scripts and C adds some clauses
> F1, F2, F3, then what does this sibling replacement do? Should a sibling not be
> able to specify (e.g., by leaf version?) a NOREPLACE flag that prevents
> siblings from modifying it?

If you want a utxo where some script paths are constant, don't construct
the utxo with script paths that can modify them.

> What happens when E adds a bunch of F's F1 F2 F3, is C still in the same
> position as when E was created?

That depends how you define "position". If you have:

    
   /\
  R  S

and

   /\
  R /\
   S  T

then I'd say that "R" has stayed in the same position, while "S" has
been lowered to allow for a new sibling "T". But the merkle path to
R will have changed (from "H(S)" to "H(H(S),H(T))"). 

> Especially since nodes are lexicographically sorted, it seems hard to create
> stable path descriptors even if you index from the root downwards.

The merkle path will always change unless you have the exact same set
of scripts, so that doesn't seem like a very interesting way to define
"position" when you're adding/removing/replacing scripts.

The "lexical ordering" is just a modification to how the hash is
calculated that makes it commutative, so that H(A,B) = H(B,A), with
the result being that the merkle path for any script in the the R,(S,T)
tree above is the same for the corresponding script in the tree:

   /\
  /\ R
 T  S

Cheers,
aj