From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.osuosl.org (smtp1.osuosl.org [140.211.166.138]) by lists.linuxfoundation.org (Postfix) with ESMTP id F39A3C000D for ; Fri, 10 Sep 2021 07:42:29 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp1.osuosl.org (Postfix) with ESMTP id E268D83E60 for ; Fri, 10 Sep 2021 07:42:29 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -1.499 X-Spam-Level: X-Spam-Status: No, score=-1.499 tagged_above=-999 required=5 tests=[BAYES_00=-1.9, KHOP_HELO_FCRDNS=0.398, SPF_HELO_NONE=0.001, SPF_NONE=0.001, UNPARSEABLE_RELAY=0.001] autolearn=no autolearn_force=no Received: from smtp1.osuosl.org ([127.0.0.1]) by localhost (smtp1.osuosl.org [127.0.0.1]) (amavisd-new, port 10024) with ESMTP id lHt-NPyUaasd for ; Fri, 10 Sep 2021 07:42:29 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.8.0 Received: from azure.erisian.com.au (cerulean.erisian.com.au [139.162.42.226]) by smtp1.osuosl.org (Postfix) with ESMTPS id 1938683E59 for ; Fri, 10 Sep 2021 07:42:28 +0000 (UTC) Received: from aj@azure.erisian.com.au (helo=sapphire.erisian.com.au) by azure.erisian.com.au with esmtpsa (Exim 4.92 #3 (Debian)) id 1mObB2-00070Z-32; Fri, 10 Sep 2021 17:42:25 +1000 Received: by sapphire.erisian.com.au (sSMTP sendmail emulation); Fri, 10 Sep 2021 17:42:19 +1000 Date: Fri, 10 Sep 2021 17:42:19 +1000 From: Anthony Towns To: Jeremy Message-ID: <20210910074219.GA23578@erisian.com.au> References: <20210909064138.GA22496@erisian.com.au> <20210909065330.GB22496@erisian.com.au> MIME-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1 Content-Disposition: inline Content-Transfer-Encoding: 8bit In-Reply-To: User-Agent: Mutt/1.10.1 (2018-07-13) X-Spam-Score-int: -18 X-Spam-Bar: - Cc: Bitcoin Protocol Discussion 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: Fri, 10 Sep 2021 07:42:30 -0000 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