path: root/76/a96dae244859f829dda4870a586977d458cae2

Return-Path: <jlrubin@mit.edu>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136])
 by lists.linuxfoundation.org (Postfix) with ESMTP id 7A4B2C000D
 for <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>;
 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 <bitcoin-dev@lists.linuxfoundation.org>; Thu, 9 Sep 2021 15:26:50 -0400
Received: by mail-lj1-f181.google.com with SMTP id f2so4721918ljn.1
 for <bitcoin-dev@lists.linuxfoundation.org>;
 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 <jlrubin@mit.edu>
Date: Thu, 9 Sep 2021 12:26:37 -0700
X-Gmail-Original-Message-ID: <CAD5xwhgFZPkQ2GbtphQ1DdzMDyeUEt0fKbA5g3jVoGRDVW4kKQ@mail.gmail.com>
Message-ID: <CAD5xwhgFZPkQ2GbtphQ1DdzMDyeUEt0fKbA5g3jVoGRDVW4kKQ@mail.gmail.com>
To: Anthony Towns <aj@erisian.com.au>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>, 
 <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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

<div dir=3D"ltr"><div class=3D"gmail_quote"><div><div class=3D"gmail_defaul=
t" style=3D"font-family:arial,helvetica,sans-serif;font-size:small;color:rg=
b(0,0,0)">I&#39;m a bit skeptical of the safety of the control byte. Have y=
ou considered the following issues?</div><br></div><div>=C2=A0</div><blockq=
uote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-wi=
dth:1px;border-left-style:solid;border-left-color:rgb(204,204,204);padding-=
left:1ex">The low bit of C indicates the parity of X; if it&#39;s 0, X has =
even y,<br>
if it&#39;s 1, X has odd y.<br>
<br>
The next bit of C indicates whether the current script is dropped from<br>
the merkle path, if it&#39;s 0, the current script is kept, if it&#39;s 1 t=
he<br>
current script is dropped.<br>
<br>
The remaining bits of C (ie C &gt;&gt; 2) are the number of steps in the me=
rkle<br>
path that are dropped. (If C is negative, behaviour is to be determined<br>
-- either always fail, or always succeed and left for definition via<br>
future soft-fork)<br>
<br>
For example, suppose we have a taproot utxo that had 5 scripts<br>
(A,B,C,D,E), calculated as per the example in BIP 341 as:<br>
<br>
=C2=A0 =C2=A0 AB =3D H_TapBranch(A, B)<br>
=C2=A0 =C2=A0 CD =3D H_TapBranch(C, D)<br>
=C2=A0 =C2=A0 CDE =3D H_TapBranch(CD, E)<br>
=C2=A0 =C2=A0 ABCDE =3D H_TapBranch(AB, CDE)<br>
<br>
And we&#39;re spending using script E, in that case the control block inclu=
des<br>
the script E, and the merkle path to it, namely (AB, CD).<br>
<br>
So here&#39;s some examples of what you could do with TLUV to control how<b=
r>
the spending scripts can change, between the input sPK and the output sPK.<=
br>
<br>
At it&#39;s simplest, if we used the script &quot;0 0 0 TLUV&quot;, then th=
at says we<br>
keep the current script, keep all steps in the merkle path, don&#39;t add<b=
r>
any new ones, and don&#39;t change the internal public key -- that is that<=
br>
we want to resulting sPK to be exactly the same as the one we&#39;re spendi=
ng.<br>
<br>
If we used the script &quot;0 F 0 TLUV&quot; (H=3DF, C=3D0) then we keep th=
e current<br>
script, keep all the steps in the merkle path (AB and CD), and add<br>
a new step to the merkle path (F), giving us:<br>
<br>
=C2=A0 =C2=A0 EF =3D H_TapBranch(E, F)<br>
=C2=A0 =C2=A0 CDEF =3DH_TapBranch(CD, EF)<br>
=C2=A0 =C2=A0 ABCDEF =3D H_TapBranch(AB, CDEF)<br>
<br>
If we used the script &quot;0 F 2 TLUV&quot; (H=3DF, C=3D2) then we drop th=
e current<br>
script, but keep all the other steps, and add a new step (effectively<br>
replacing the current script with a new one):<br>
<br>
=C2=A0 =C2=A0 CDF =3D H_TapBranch(CD, F)<br>
=C2=A0 =C2=A0 ABCDF =3D H_TapBranch(AB, CDF)<br></blockquote><div><br></div=
><div><div class=3D"gmail_default" style=3D"font-family:arial,helvetica,san=
s-serif;font-size:small;color:rgb(0,0,0)">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?</div><div class=3D"gmail_default" =
style=3D"font-family:arial,helvetica,sans-serif;font-size:small;color:rgb(0=
,0,0)"><br></div><div class=3D"gmail_default" style=3D"font-family:arial,he=
lvetica,sans-serif;font-size:small;color:rgb(0,0,0)">Suppose we protect aga=
inst this by checking that after adding F the depth is not more than 128 fo=
r E.</div><div class=3D"gmail_default" style=3D"font-family:arial,helvetica=
,sans-serif;font-size:small;color:rgb(0,0,0)"><br></div><div class=3D"gmail=
_default" style=3D"font-family:arial,helvetica,sans-serif;font-size:small;c=
olor:rgb(0,0,0)">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&#39;re burned anyways.</div><div class=3D"gmail_default" style=3D"font-f=
amily:arial,helvetica,sans-serif;font-size:small;color:rgb(0,0,0)"><br></di=
v><div class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-se=
rif;font-size:small;color:rgb(0,0,0)">I don&#39;t see a way to protect agai=
nst this generically.</div><div class=3D"gmail_default" style=3D"font-famil=
y:arial,helvetica,sans-serif;font-size:small;color:rgb(0,0,0)"><br></div><d=
iv class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif;=
font-size:small;color:rgb(0,0,0)">Perhaps it&#39;s OK: E can always approve=
 burning E?</div><br></div><div><br></div><div>=C2=A0</div><blockquote clas=
s=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;b=
order-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex"=
>
<br>
If we used the script &quot;0 F 4 TLUV&quot; (H=3DF, C=3D4) then we keep th=
e current<br>
script, but drop the last step in the merkle path, and add a new step<br>
(effectively replacing the *sibling* of the current script):<br>
<br>
=C2=A0 =C2=A0 EF =3D H_TapBranch(E, F)<br>
=C2=A0 =C2=A0 ABEF =3D H_TapBranch(AB, EF)=C2=A0</blockquote><blockquote cl=
ass=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px=
;border-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1e=
x">
<br>
If we used the script &quot;0 0 4 TLUV&quot; (H=3Dempty, C=3D4) then we kee=
p the current<br>
script, drop the last step in the merkle path, and don&#39;t add anything n=
ew<br>
(effectively dropping the sibling), giving just:<br>
<br>
=C2=A0 =C2=A0 ABE =3D H_TapBranch(AB, E)<br>
<br>
<br></blockquote><div><br></div><div><div class=3D"gmail_default" style=3D"=
font-family:arial,helvetica,sans-serif;font-size:small;color:rgb(0,0,0)">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><div class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans=
-serif;font-size:small;color:rgb(0,0,0)"><br></div><div class=3D"gmail_defa=
ult" style=3D"font-family:arial,helvetica,sans-serif;font-size:small;color:=
rgb(0,0,0)"><br></div><div class=3D"gmail_default" style=3D"font-family:ari=
al,helvetica,sans-serif;font-size:small;color:rgb(0,0,0)">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?</div><div class=3D"gmail_default" style=3D"font-family:arial=
,helvetica,sans-serif;font-size:small;color:rgb(0,0,0)"><br></div><div clas=
s=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif;font-si=
ze:small;color:rgb(0,0,0)">What happens when E adds a bunch of F&#39;s F1 F=
2 F3, is C still in the same position as when E was created?</div><div clas=
s=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif;font-si=
ze:small;color:rgb(0,0,0)"><br></div><div class=3D"gmail_default" style=3D"=
font-family:arial,helvetica,sans-serif;font-size:small;color:rgb(0,0,0)">Es=
pecially since nodes are lexicographically sorted, it seems hard to create =
stable path descriptors even if you index from the root downwards.</div><di=
v class=3D"gmail_default" style=3D"font-family:arial,helvetica,sans-serif;f=
ont-size:small;color:rgb(0,0,0)"><br></div><div class=3D"gmail_default" sty=
le=3D"font-family:arial,helvetica,sans-serif;font-size:small;color:rgb(0,0,=
0)">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?).</div><br></div><div><br></div></div></div>

--000000000000ec94e205cb94fad8--