From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136]) by lists.linuxfoundation.org (Postfix) with ESMTP id 97380C000E for ; Thu, 8 Jul 2021 11:17:28 +0000 (UTC) Received: from localhost (localhost [127.0.0.1]) by smtp3.osuosl.org (Postfix) with ESMTP id 935B460A93 for ; Thu, 8 Jul 2021 11:17:28 +0000 (UTC) X-Virus-Scanned: amavisd-new at osuosl.org X-Spam-Flag: NO X-Spam-Score: -0.098 X-Spam-Level: X-Spam-Status: No, score=-0.098 tagged_above=-999 required=5 tests=[BAYES_05=-0.5, KHOP_HELO_FCRDNS=0.399, SPF_HELO_NONE=0.001, SPF_NONE=0.001, UNPARSEABLE_RELAY=0.001] autolearn=no 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 GznsdiQxSX-P for ; Thu, 8 Jul 2021 11:17:27 +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 smtp3.osuosl.org (Postfix) with ESMTPS id 92C4F606A7 for ; Thu, 8 Jul 2021 11:17:27 +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 1m1S1x-00038j-UL; Thu, 08 Jul 2021 21:17:23 +1000 Received: by sapphire.erisian.com.au (sSMTP sendmail emulation); Thu, 08 Jul 2021 21:17:16 +1000 Date: Thu, 8 Jul 2021 21:17:16 +1000 From: Anthony Towns To: Antoine Riard , Bitcoin Protocol Discussion Message-ID: <20210708111716.GC1339@erisian.com.au> References: MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.10.1 (2018-07-13) X-Spam-Score-int: -18 X-Spam-Bar: - Subject: Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent 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, 08 Jul 2021 11:17:28 -0000 On Thu, May 27, 2021 at 04:14:13PM -0400, Antoine Riard via bitcoin-dev wrote: > This overhead could be smoothed even further in the future with more advanced > sighash malleability flags like SIGHASH_IOMAP, allowing transaction signers to > commit to a map of inputs/outputs [2]. In the context of input-based, the > overflowed fee value could be redirected to an outgoing output. > Input-based (SIGHASH_ANYPREVOUT+SIGHASH_IOMAP): Multiple chains of transactions > might be aggregated together *non-interactively*. One bumping input and > outgoing output can be attached to the aggregated root. > [2] https://bitcointalk.org/index.php?topic=252960.0 I haven't seen any recent specs for "IOMAP", but there are a few things that have bugged me about them in the past: (1) allowing partially overlapping sets of outputs could allow "theft", eg if I give you a signature "you can spend A+B as long as I get X" and "you can spend A+C as long as I get X", you could combine them to spend A+B+C instead but still only give me 1 X. (2) a range specification or a whole bitfield is a lot heavier than an extra bit to add to the sighash (3) this lets you specify lots of different ways of hashing the outputs, which then can't be cached, so you get kind-of quadratic behaviour -- O(n^2/8) where n/2 is the size of the inputs, which gives you the number of signatures, and n/2 is also the size of the outputs, so n/4 is a different half of the output selected for each signature in the input. But under the "don't bring me problems, bring me solutions" banner, here's an idea. The easy way to avoid O(n^2) behaviour in (3) is to disallow partial overlaps. So let's treat the tx as being distinct bundles of x-inputs and y-outputs, and we'll use the annex for grouping, since that is committed to by singatures. Call the annex field "sig_group_count". When processing inputs, setup a new state pair, (start, end), initially (0,0). When evaluating an input, lookup sig_group_count. If it's not present, then set start := end. If it's present and 0, leave start and end unchanged. Otherwise, if it's present and greather than 0, set start := end, and then set end := start + sig_group_count. Introduce a new SIGHASH_GROUP flag, as an alternative to ALL/SINGLE/NONE, that commits to each output i, start <= i < end. If start==end or end > num_outputs, signature is invalid. That means each output in a tx could be hashed three times instead of twice (once for its particular group, as well as once for SIGHASH_ALL and once for SIGHASH_SINGLE), and I think would let you combine x-input and y-outputs fairly safely, by having the first input commit to "y" in the annex, and the remaining x-1 commit to "0". That does mean if you have two different sets of inputs (x1 and x2) each spending to the exact same set of y outputs, you could claim all but one of them while only paying a single set of y outputs. But you could include an "OP_RETURN hash(x1)" tapleaf branch in one of the y outputs to ensure the outputs aren't precisely the same to avoid that problem, so maybe that's fine? Okay, now that I've written and re-written that a couple of times, it looks like I'm just reinventing Rusty's signature bundles from 2018: https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-April/015862.html (though at least I think using the annex is probably an improvement on having values that affect other inputs being buried deeper in an input's witness data) Without something like this, I think it will be very hard to incorporate fees into eltoo with layered commitments [0]. As a new sighash mode it would make sense to include it as part of ANYPREVOUT to avoid introducing many new "unknown key types". [0] https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-January/002448.html also, https://www.erisian.com.au/lightning-dev/log-2021-07-08.html Cheers, aj