public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Jeremy <jlrubin@mit.edu>
To: Anthony Towns <aj@erisian.com.au>,
	Bitcoin Protocol Discussion
	<bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode
Date: Thu, 9 Sep 2021 12:26:37 -0700	[thread overview]
Message-ID: <CAD5xwhgFZPkQ2GbtphQ1DdzMDyeUEt0fKbA5g3jVoGRDVW4kKQ@mail.gmail.com> (raw)
In-Reply-To: <20210909065330.GB22496@erisian.com.au>

[-- Attachment #1: Type: text/plain, Size: 3867 bytes --]

I'm a bit skeptical of the safety of the control byte. Have you considered
the following issues?



> The low bit of C indicates the parity of X; if it's 0, X has even y,
> if it's 1, X has odd y.
>
> The next bit of C indicates whether the current script is dropped from
> the merkle path, if it's 0, the current script is kept, if it's 1 the
> current script is dropped.
>
> The remaining bits of C (ie C >> 2) are the number of steps in the merkle
> path that are dropped. (If C is negative, behaviour is to be determined
> -- either always fail, or always succeed and left for definition via
> future soft-fork)
>
> For example, suppose we have a taproot utxo that had 5 scripts
> (A,B,C,D,E), calculated as per the example in BIP 341 as:
>
>     AB = H_TapBranch(A, B)
>     CD = H_TapBranch(C, D)
>     CDE = H_TapBranch(CD, E)
>     ABCDE = H_TapBranch(AB, CDE)
>
> And we're spending using script E, in that case the control block includes
> the script E, and the merkle path to it, namely (AB, CD).
>
> So here's some examples of what you could do with TLUV to control how
> the spending scripts can change, between the input sPK and the output sPK.
>
> At it's simplest, if we used the script "0 0 0 TLUV", then that says we
> keep the current script, keep all steps in the merkle path, don't add
> any new ones, and don't change the internal public key -- that is that
> we want to resulting sPK to be exactly the same as the one we're spending.
>
> 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 used the script "0 F 2 TLUV" (H=F, C=2) then we drop the current
> script, but keep all the other steps, and add a new step (effectively
> replacing the current script with a new one):
>
>     CDF = H_TapBranch(CD, F)
>     ABCDF = H_TapBranch(AB, CDF)
>

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?

Suppose we protect against this by checking that after adding F the depth
is not more than 128 for E.

The E path that adds F could also be burned for future use once the depth
is hit, and if adding F is necessary for correctness, then we're burned
anyways.

I don't see a way to protect against this generically.

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




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


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?

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?

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

Identifying nodes by Hash is also not acceptable because of hash cycles,
unless you want to restrict the tree structure accordingly (maybe OK
tradeoff?).

[-- Attachment #2: Type: text/html, Size: 7181 bytes --]

  parent reply	other threads:[~2021-09-09 19:26 UTC|newest]

Thread overview: 17+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2021-09-09  6:41 [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode Anthony Towns
2021-09-09  6:53 ` Anthony Towns
2021-09-09 12:56   ` darosior
2021-09-09 15:54   ` Jeremy
2021-09-09 19:26   ` Jeremy [this message]
2021-09-10  7:42     ` Anthony Towns
2022-07-08 19:52   ` Tim Ruffing
2021-09-09  9:16 ` Matt Corallo
2021-09-10  4:12 ` Antoine Riard
2021-09-11  3:26   ` Anthony Towns
2021-09-12 23:37     ` Antoine Riard
2021-09-15  6:50       ` Anthony Towns
2021-09-18 14:11         ` Antoine Riard
2021-09-20 14:52           ` Anthony Towns
2021-09-22  1:40             ` Antoine Riard
2021-09-23  0:29 ` Olaoluwa Osuntokun
2021-10-29 15:47   ` Billy Tetrud

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=CAD5xwhgFZPkQ2GbtphQ1DdzMDyeUEt0fKbA5g3jVoGRDVW4kKQ@mail.gmail.com \
    --to=jlrubin@mit.edu \
    --cc=aj@erisian.com.au \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox