Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 7A4B2C000D for ; Thu, 9 Sep 2021 19:26:53 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id 5CCB960B32 for ; Thu, 9 Sep 2021 19:26:53 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -4.199 X-Spam-Level: X-Spam-Status: No, score=-4.199 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, HTML_MESSAGE=0.001, RCVD_IN_DNSWL_MED=-2.3, SPF_HELO_NONE=0.001, SPF_PASS=-0.001] autolearn=ham autolearn_force=no Received: from smtp3.osuosl.org ([127.0.0.1]) by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id nM0QYNj7mpZG for ; Thu, 9 Sep 2021 19:26:52 +0000 (UTC) X-Greylist: domain auto-whitelisted by SQLgrey-1.8.0 Received: from outgoing.mit.edu (outgoing-auth-1.mit.edu [18.9.28.11]) by smtp3.osuosl.org (Postfix) with ESMTPS id 38AA460B30 for ; Thu, 9 Sep 2021 19:26:51 +0000 (UTC) Received: from mail-lj1-f181.google.com (mail-lj1-f181.google.com [209.85.208.181]) (authenticated bits=0) (User authenticated as jlrubin@ATHENA.MIT.EDU) by outgoing.mit.edu (8.14.7/8.12.4) with ESMTP id 189JQneo024923 (version=TLSv1/SSLv3 cipher=AES128-GCM-SHA256 bits=128 verify=NOT) for ; Thu, 9 Sep 2021 15:26:50 -0400 Received: by mail-lj1-f181.google.com with SMTP id f2so4721918ljn.1 for ; Thu, 09 Sep 2021 12:26:50 -0700 (PDT) X-Gm-Message-State: AOAM532H+BD75BhMeZssjFI1We0K4d8i4sSZpOfucFysO8wcf5VtbNpw CFiqPYQwpNWbJqGAA67b/BUD7c0w9RZ4EJvj+iY= X-Google-Smtp-Source: ABdhPJyoFuwtIPFl0sSWAtxpwJCnIEFKYuBlozlwtKeYiUpOJlh0fQh8szGA+rJkU+5HwNbzvoqR1/cZwzirMrKx9hA= X-Received: by 2002:a05:651c:1683:: with SMTP id bd3mr1146197ljb.323.1631215608958; Thu, 09 Sep 2021 12:26:48 -0700 (PDT) MIME-Version: 1.0 References: <20210909064138.GA22496@erisian.com.au> <20210909065330.GB22496@erisian.com.au> In-Reply-To: <20210909065330.GB22496@erisian.com.au> From: Jeremy Date: Thu, 9 Sep 2021 12:26:37 -0700 X-Gmail-Original-Message-ID: Message-ID: To: Anthony Towns , Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary="000000000000ec94e205cb94fad8" Subject: Re: [bitcoin-dev] TAPLEAF_UPDATE_VERIFY covenant opcode X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 09 Sep 2021 19:26:53 -0000 --000000000000ec94e205cb94fad8 Content-Type: text/plain; charset="UTF-8" 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?). --000000000000ec94e205cb94fad8 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
I'm a bit skeptical of the safety of the control byte. Have y= ou considered the following issues?

=C2=A0
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 t= he
current script is dropped.

The remaining bits of C (ie C >> 2) are the number of steps in the me= rkle
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:

=C2=A0 =C2=A0 AB =3D H_TapBranch(A, B)
=C2=A0 =C2=A0 CD =3D H_TapBranch(C, D)
=C2=A0 =C2=A0 CDE =3D H_TapBranch(CD, E)
=C2=A0 =C2=A0 ABCDE =3D H_TapBranch(AB, CDE)

And we're spending using script E, in that case the control block inclu= des
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.<= br>
At it's simplest, if we used the script "0 0 0 TLUV", then th= at 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<= br> we want to resulting sPK to be exactly the same as the one we're spendi= ng.

If we used the script "0 F 0 TLUV" (H=3DF, C=3D0) then we keep th= e 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:

=C2=A0 =C2=A0 EF =3D H_TapBranch(E, F)
=C2=A0 =C2=A0 CDEF =3DH_TapBranch(CD, EF)
=C2=A0 =C2=A0 ABCDEF =3D H_TapBranch(AB, CDEF)

If we used the script "0 F 2 TLUV" (H=3DF, C=3D2) then we drop th= e current
script, but keep all the other steps, and add a new step (effectively
replacing the current script with a new one):

=C2=A0 =C2=A0 CDF =3D H_TapBranch(CD, F)
=C2=A0 =C2=A0 ABCDF =3D H_TapBranch(AB, CDF)

If we recursively apply this rule= , would it not be possible to repeatedly apply it and end up burning out pa= th E beyond the 128 Taproot depth limit?

Suppose we protect aga= inst this by checking that after adding F the depth is not more than 128 fo= r 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 agai= nst this generically.

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


=C2=A0

If we used the script "0 F 4 TLUV" (H=3DF, C=3D4) then we keep th= e current
script, but drop the last step in the merkle path, and add a new step
(effectively replacing the *sibling* of the current script):

=C2=A0 =C2=A0 EF =3D H_TapBranch(E, F)
=C2=A0 =C2=A0 ABEF =3D H_TapBranch(AB, EF)=C2=A0

If we used the script "0 0 4 TLUV" (H=3Dempty, C=3D4) then we kee= p the current
script, drop the last step in the merkle path, and don't add anything n= ew
(effectively dropping the sibling), giving just:

=C2=A0 =C2=A0 ABE =3D H_TapBranch(AB, E)



Is= C =3D 4 stable across all state transitions? I may be missing something, b= ut it seems that the location of C would not be stable across transitions.<= /div>


E.g., What happen= s when, C and E are similar scripts and C adds some clauses F1, F2, F3, the= n what does this sibling replacement do? Should a sibling not be able to sp= ecify (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 F= 2 F3, is C still in the same position as when E was created?

Es= pecially 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 trad= eoff?).


--000000000000ec94e205cb94fad8--