diff options
author | Antoine Riard <antoine.riard@gmail.com> | 2021-07-09 09:19:45 -0400 |
---|---|---|
committer | bitcoindev <bitcoindev@gnusha.org> | 2021-07-09 13:20:01 +0000 |
commit | ccf6e06c9240d624c2c233402d877e7189e96c8f (patch) | |
tree | d4761d5de83a0dcc242961d9291b6fc66ca9bd82 | |
parent | 872458a6c09656f87cef8e4f95c8430df5aeee2d (diff) | |
download | pi-bitcoindev-ccf6e06c9240d624c2c233402d877e7189e96c8f.tar.gz pi-bitcoindev-ccf6e06c9240d624c2c233402d877e7189e96c8f.zip |
Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques : Input-Based vs Child-Pay-For-Parent
-rw-r--r-- | e6/9364856bc6a4b63f3d9a683eaa7264105d5a04 | 657 |
1 files changed, 657 insertions, 0 deletions
diff --git a/e6/9364856bc6a4b63f3d9a683eaa7264105d5a04 b/e6/9364856bc6a4b63f3d9a683eaa7264105d5a04 new file mode 100644 index 000000000..0529ee8d4 --- /dev/null +++ b/e6/9364856bc6a4b63f3d9a683eaa7264105d5a04 @@ -0,0 +1,657 @@ +Return-Path: <antoine.riard@gmail.com> +Received: from smtp1.osuosl.org (smtp1.osuosl.org [IPv6:2605:bc80:3010::138]) + by lists.linuxfoundation.org (Postfix) with ESMTP id 5D16AC001A + for <bitcoin-dev@lists.linuxfoundation.org>; + Fri, 9 Jul 2021 13:20:01 +0000 (UTC) +Received: from localhost (localhost [127.0.0.1]) + by smtp1.osuosl.org (Postfix) with ESMTP id 3FAED83D1C + for <bitcoin-dev@lists.linuxfoundation.org>; + Fri, 9 Jul 2021 13:20:01 +0000 (UTC) +X-Virus-Scanned: amavisd-new at osuosl.org +X-Spam-Flag: NO +X-Spam-Score: -2.098 +X-Spam-Level: +X-Spam-Status: No, score=-2.098 tagged_above=-999 required=5 + tests=[BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, + DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, FREEMAIL_FROM=0.001, + HTML_MESSAGE=0.001, RCVD_IN_DNSWL_NONE=-0.0001, SPF_HELO_NONE=0.001, + SPF_PASS=-0.001] autolearn=ham autolearn_force=no +Authentication-Results: smtp1.osuosl.org (amavisd-new); + dkim=pass (2048-bit key) header.d=gmail.com +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 vm6vQy3101kt + for <bitcoin-dev@lists.linuxfoundation.org>; + Fri, 9 Jul 2021 13:19:59 +0000 (UTC) +X-Greylist: whitelisted by SQLgrey-1.8.0 +Received: from mail-wm1-x32a.google.com (mail-wm1-x32a.google.com + [IPv6:2a00:1450:4864:20::32a]) + by smtp1.osuosl.org (Postfix) with ESMTPS id 0A37883D11 + for <bitcoin-dev@lists.linuxfoundation.org>; + Fri, 9 Jul 2021 13:19:58 +0000 (UTC) +Received: by mail-wm1-x32a.google.com with SMTP id + t14-20020a05600c198eb029020c8aac53d4so25471493wmq.1 + for <bitcoin-dev@lists.linuxfoundation.org>; + Fri, 09 Jul 2021 06:19:58 -0700 (PDT) +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; + h=mime-version:references:in-reply-to:from:date:message-id:subject:to + :cc; bh=VgSgzR6n68sxQlyu+h6+WdWuE6hx30wT8syGTobvAwo=; + b=CVqz3N6SIeDf8EUl6ea69OoxU03lbDb1jcJOucea9U/w7pU8J+HvCSoKnEVLVw6CPh + jF2M+JRtZlOFWyzVmsAMh/SCIFm8IhsKxjwoP05euOBv3NaZbju0paC8tvS69OTsrgSS + /kColFPAOOe6VPfaWXSyKujv4YcKIl1kRrYiAiQGCYIdZN+7UEzZJ/07JVG6WxoybjP8 + os6gJ+LZKVRDbVsTkaIhUh4EhNrCbVNJp6hZ4a2WWx6PJgAdu/98hxsAikMW0oCXorbM + ZsD0sARVWrqfvFw6LSybl3E5nx/T00E5BNemX2IFIAlyaxUiW8WJWpKMnHc4zgIsyNvh + pOkQ== +X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=1e100.net; s=20161025; + h=x-gm-message-state:mime-version:references:in-reply-to:from:date + :message-id:subject:to:cc; + bh=VgSgzR6n68sxQlyu+h6+WdWuE6hx30wT8syGTobvAwo=; + b=KkvHf+wOnAEHBEI1lPX30Tsx/GpKqiYz7oDmsDGGkmvdf7+napjS9PdESjMCZUdQrT + fNOOSP2/oDWUViQa9fAllGGRKkl87qT29adkA3yVVpuSfvwZKR+DTFcjamCZs/HeMhAV + AL90q4RUkN7uFUb2DkKGCTSfma25A+feej1tEYsZukuuoR5sHSWEPL9d5QvUjYH25zFL + HmhtRxbMoyJTGhpNrxacUc9qdhP/Fes18r57ZxUSn3Zu/MNgEPIquYcSFYIQ5dXyLrZ8 + efN7TFzV3fw+CxXSQj+1c3strq50oVSJb5Eivh2/yN3ClWwaTbvjuUwAi+We3vuhzcdu + K8Cw== +X-Gm-Message-State: AOAM533/mLAuChX+//ngbMRNt4BFFgD52JvObMGBJ+efAQcax6V4vqYh + yjfPOOAJ1BCahs9JY9F16hxltj5k+QsyxG5zMoI9obZPV2tOWw== +X-Google-Smtp-Source: ABdhPJzBtFKOfD4RET5ra/rkQrEaxbuAmj8ttMAsFiHEpwhBFkTabMpIU5NXStg9nMiCd7O5XlBi6R6l/ugMP1+qhZA= +X-Received: by 2002:a05:600c:1c85:: with SMTP id + k5mr12065064wms.47.1625836796985; + Fri, 09 Jul 2021 06:19:56 -0700 (PDT) +MIME-Version: 1.0 +References: <CALZpt+FvLb=N5Qygs+dPmh1o9QCwXj8RoznF5n47opOq7CG_0g@mail.gmail.com> + <20210708111716.GC1339@erisian.com.au> +In-Reply-To: <20210708111716.GC1339@erisian.com.au> +From: Antoine Riard <antoine.riard@gmail.com> +Date: Fri, 9 Jul 2021 09:19:45 -0400 +Message-ID: <CALZpt+FCCgSiRh2qAL+RM0S9Vm8s-xS3VdTAZhS9VwLcFi_1QQ@mail.gmail.com> +To: Anthony Towns <aj@erisian.com.au> +Content-Type: multipart/alternative; boundary="000000000000bf452805c6b0a0d9" +X-Mailman-Approved-At: Fri, 09 Jul 2021 13:24:21 +0000 +Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org> +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 <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: Fri, 09 Jul 2021 13:20:01 -0000 + +--000000000000bf452805c6b0a0d9 +Content-Type: text/plain; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +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=3D252960.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: + +TBH, I don't think we have been further with Darosior than comparing the +compression schemes relevant for the bitfield :) + +Thanks to start the hard grinding work! + +> (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. + +Yes I think there is an even more unsafe case than described. A transaction +third-party knowledgeable about the partial sets could combine them, then +attach an additional siphoning output Y. E.g, if {A=3D50, B=3D50, C=3D50} a= +nd +X=3D100 the third-party could attach output Y=3D50 ? + +Though I believe the validity of those thefts are a function of further +specification of the transaction digest coverage, as you might have a +malleability scheme where B or C's signatures hash are implicitly +committing to subset inputs order. If you have `H_prevouts(A || B)` and +`H_prevouts(A || C)`, an attacker wouldn't be able to satisfy both B and C +scripts in the same transaction ? + +One mitigation which was mentioned in previous pinning discussion was to +add a per-participant finalizing key to A's script and thus lockdown +transaction template at broadcast. I don't think it works here as you can't +assume that your counterparties, from different protocol sessions, won't +collude together to combine their finalizing signatures and achieve a spend +replay across sessions ? + +That said, I'm not even sure we should disallow partially overlapping sets +of outputs at the consensus-level, one could imagine a crowdfunding +application where you delegate A+B and A+C to different parties, and you +implicitly allow them to cooperate as long as they fulfill X's output value +? + +> (2) a range specification or a whole bitfield is a lot heavier than an +> extra bit to add to the sighash + +Yes, one quick optimization in case of far-depth output committed in the +bitfield could be to have a few initial bits serving as vectors to blank +out unused bitfield spaces. Though I concede a new sighash bits arithmetic +might be too fancy for consensus-code. + + +> (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. + +If you assume n size of transaction data, and that each signature hash is +committing to inputs + half of outputs, yes I think it's even worst kind-of +quadratic, like O(3n^2/4) ? And you might even worsen the hashing in +function of flexibility allowed, like still committing to the whole +transaction size but a different combination order of outputs selected for +each signature. + +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 :=3D end. If it's present and 0, leave start and end +> unchanged. Otherwise, if it's present and greather than 0, set +> start :=3D end, and then set end :=3D start + sig_group_count. + +IIUC the design rationale, the "sig_group_count" lockdowns the hashing of +outputs for a given input, thus allowing midstate reuse across signatures +input. + +> Introduce a new SIGHASH_GROUP flag, as an alternative to ALL/SINGLE/NONE, +> that commits to each output i, start <=3D i < end. If start=3D=3Dend or e= +nd > +> 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? + +If the index i is absolute w.r.t to the transaction output index, I think +this design might have a shortcoming. + +Let's say you want to combine {x_1, y_1} and {x_2, y_2} where {x, y} +denotes bundles of Lightning commitment transactions. + +x_1 is dual-signed by Alice and Bob under the SIGHASH_GROUP flag with +`sig_group_count`=3D3. +x_2 is dual-signed by Alice and Caroll under the SIGHASH_GROUP flag, with +`sig_group_count`=3D2. +y_1 and y_2 are disjunctive. + +At broadcast, Alice is not able to combine {x_1,y_1} and {x_2, y_2} for the +reason that x_1, x_2 are colliding on the absolute output position. + +One fix could be to skim the "end > num_ouputs" semantic, and thus have +Alice negotiate (start,end) encompassing all her channels outputs index and +then strictly ordering her i indexes on all her counterparties. But I don't +think you can assume index order to be transitive across Lightning nodes, +at least without bundle combination gaps in your local set of channels. + +I think this SIGHASH_GROUP proposal might solve other use-cases, but if I +understand the semantics correctly, it doesn't seem to achieve the batch +fee-bumping of multiple Lightning commitment with O(1) onchain footprint I +was thinking of for IOMAP... + +One counter-proposal to solve this "pre-signed y-outputs ordinate" could be +instead to envision the SIGHASH_GROUP as vector coordinates and the annex +field as the projection. + +Let's say annex field :=3D (hashOutputsGroups) and SIGHASH_GROUP(i,j) where= + j +is a non-null integer. +Call i the starting index of the output group committed by this input. +Call j the output group size committed by this input. + +At validation, compute `hashOutputsGroup` =3D H(outputs[i...i+j-1]). +If the computed `hashOutputGroup` isn't equal to the input annex field +`hashOutputsGroup`, fails validation. +Otherwise, substitute `hashOutputGroup` to bip-143 `hashOutputs` while +conserving , and proceed to signature verification. + +As (i,j) are not included in the annex and are only part of witness data, +they can be selected by the bundles combiner at broadcast to construct a +valid transaction. + +If the combiner is malicious and (i,j) points to another outputs group, the +computed hash is going to be invalid, as it doesn't satisfy the annex +`output_group` field. + +If you want to disallow partial overlaps for your bundle, we could even +have a bit k. If k=3D1, verify that all transaction `output_group` fields a= +re +not colliding. + +Hmmmm, sounds more flexible but you might still have a bit of hashing +complexity to deal with ? + +> 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.h= +tml +> +> (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". + +Well, I agree on the overall direction though maybe we should detail +primitive requirements a bit more, otherwise it might not fit the +second-layer use-case we're interested with. + +Cheers, +Antoine + +Le jeu. 8 juil. 2021 =C3=A0 07:17, Anthony Towns <aj@erisian.com.au> a =C3= +=A9crit : + +> 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, t= +he +> > 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=3D252960.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 :=3D end. If it's present and 0, leave start and end +> unchanged. Otherwise, if it's present and greather than 0, set +> start :=3D end, and then set end :=3D start + sig_group_count. +> +> Introduce a new SIGHASH_GROUP flag, as an alternative to ALL/SINGLE/NONE, +> that commits to each output i, start <=3D i < end. If start=3D=3Dend or e= +nd > +> 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/00= +2448.html +> also, https://www.erisian.com.au/lightning-dev/log-2021-07-08.html +> +> Cheers, +> aj +> +> + +--000000000000bf452805c6b0a0d9 +Content-Type: text/html; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +<div dir=3D"ltr">On Thu, May 27, 2021 at 04:14:13PM -0400, Antoine Riard vi= +a bitcoin-dev wrote:<br>> This overhead could be smoothed even further i= +n the future with more advanced<br>> sighash malleability flags like SIG= +HASH_IOMAP, allowing transaction signers to<br>> commit to a map of inpu= +ts/outputs [2]. In the context of input-based, the<br>> overflowed fee v= +alue could be redirected to an outgoing output.<br><br>> Input-based (SI= +GHASH_ANYPREVOUT+SIGHASH_IOMAP): Multiple chains of transactions<br>> mi= +ght be aggregated together *non-interactively*. One bumping input and<br>&g= +t; outgoing output can be attached to the aggregated root.<br><br>> [2] = +<a href=3D"https://bitcointalk.org/index.php?topic=3D252960.0">https://bitc= +ointalk.org/index.php?topic=3D252960.0</a><br><br>> I haven't seen a= +ny recent specs for "IOMAP", but there are a few things<br>> t= +hat have bugged me about them in the past:<br><br>TBH, I don't think we= + have been further with Darosior than comparing the compression schemes rel= +evant for the bitfield :)<br><br>Thanks to start the hard grinding work!<br= +><br>> =C2=A0(1) allowing partially overlapping sets of outputs could al= +low "theft",<br>> =C2=A0 =C2=A0 =C2=A0eg if I give you a signa= +ture "you can spend A+B as long as I get X"<br>> =C2=A0 =C2=A0= + =C2=A0and "you can spend A+C as long as I get X", you could comb= +ine them<br>> =C2=A0 =C2=A0 =C2=A0to spend A+B+C instead but still only = +give me 1 X.<br><br>Yes I think there is an even more unsafe case than desc= +ribed. A transaction third-party knowledgeable about the partial sets could= + combine them, then attach an additional siphoning output Y. E.g, if {A=3D5= +0, B=3D50, C=3D50} and X=3D100 the third-party could attach output Y=3D50 ?= +<br><br>Though I believe the validity of those thefts are a function of fur= +ther specification of the transaction digest coverage, as you might have a = +malleability scheme where B or C's signatures hash are implicitly commi= +tting to subset inputs order. If you have `H_prevouts(A || B)` and `H_prevo= +uts(A || C)`, an attacker wouldn't be able to satisfy both B and C scri= +pts in the same transaction ?<br><br>One mitigation which was mentioned in = +previous pinning discussion was to add a per-participant finalizing key to = +A's script and thus lockdown transaction template at broadcast. I don&#= +39;t think it works here as you can't assume that your counterparties, = +from different protocol sessions, won't collude together to combine the= +ir finalizing signatures and achieve a spend replay across sessions ?<br><b= +r>That said, I'm not even sure we should disallow partially overlapping= + sets of outputs at the consensus-level, one could imagine a crowdfunding a= +pplication where you delegate A+B and A+C to different parties, and you imp= +licitly allow them to cooperate as long as they fulfill X's output valu= +e ?<br><br>> =C2=A0(2) a range specification or a whole bitfield is a lo= +t heavier than an<br>> =C2=A0 =C2=A0 =C2=A0extra bit to add to the sigha= +sh<br><br>Yes, one quick optimization in case of far-depth output committed= + in the bitfield could be to have a few initial bits serving as vectors to = +blank out unused bitfield spaces. Though I concede a new sighash bits arith= +metic might be too fancy for consensus-code.<br><br><br>> =C2=A0(3) this= + lets you specify lots of different ways of hashing the<br>> =C2=A0 =C2= +=A0 =C2=A0outputs, which then can't be cached, so you get kind-of quadr= +atic<br>> =C2=A0 =C2=A0 =C2=A0behaviour -- O(n^2/8) where n/2 is the siz= +e of the inputs, which<br>> =C2=A0 =C2=A0 =C2=A0gives you the number of = +signatures, and n/2 is also the size of the<br>> =C2=A0 =C2=A0 =C2=A0out= +puts, so n/4 is a different half of the output selected for each<br>> = +=C2=A0 =C2=A0 =C2=A0signature in the input.<br><br>If you assume n size of = +transaction data, and that each signature hash is committing to inputs + ha= +lf of outputs, yes I think it's even worst kind-of quadratic, like O(3n= +^2/4) ? And you might even worsen the hashing in function of flexibility al= +lowed, like still committing to the whole transaction size but a different = +combination order of outputs selected for each signature.<br><br>But under = +the "don't bring me problems, bring me solutions" banner, her= +e's an idea.<br><br>> The easy way to avoid O(n^2) behaviour in (3) = +is to disallow partial<br>> overlaps. So let's treat the tx as being= + distinct bundles of x-inputs<br>> and y-outputs, and we'll use the = +annex for grouping, since that is<br>> committed to by singatures. Call = +the annex field "sig_group_count".<br><br>> When processing in= +puts, setup a new state pair, (start, end), initially<br>> (0,0).<br>>= +; <br>> When evaluating an input, lookup sig_group_count. If it's no= +t present,<br>> then set start :=3D end. If it's present and 0, leav= +e start and end<br>> unchanged. Otherwise, if it's present and great= +her than 0, set<br>> start :=3D end, and then set end :=3D start + sig_g= +roup_count.<br><br>IIUC the design rationale, the "sig_group_count&quo= +t; lockdowns the hashing of outputs for a given input, thus allowing midsta= +te reuse across signatures input.<br><br>> Introduce a new SIGHASH_GROUP= + flag, as an alternative to ALL/SINGLE/NONE,<br>> that commits to each o= +utput i, start <=3D i < end. If start=3D=3Dend or end ><br>> nu= +m_outputs, signature is invalid.<br>> <br>> That means each output in= + a tx could be hashed three times instead of<br>> twice (once for its pa= +rticular group, as well as once for SIGHASH_ALL<br>> and once for SIGHAS= +H_SINGLE), and I think would let you combine x-input<br>> and y-outputs = +fairly safely, by having the first input commit to "y"<br>> in= + the annex, and the remaining x-1 commit to "0".<br>> <br>>= + That does mean if you have two different sets of inputs (x1 and x2)<br>>= +; each spending to the exact same set of y outputs, you could claim all<br>= +> but one of them while only paying a single set of y outputs. But you<b= +r>> could include an "OP_RETURN hash(x1)" tapleaf branch in on= +e of the y<br>> outputs to ensure the outputs aren't precisely the s= +ame to avoid that<br>> problem, so maybe that's fine?<br><br>If the = +index i is absolute w.r.t to the transaction output index, I think this des= +ign might have a shortcoming.<br><br>Let's say you want to combine {x_1= +, y_1} and {x_2, y_2} where {x, y} denotes bundles of Lightning commitment = +transactions.<br><br>x_1 is dual-signed by Alice and Bob under the SIGHASH_= +GROUP flag with `sig_group_count`=3D3.<br>x_2 is dual-signed by Alice and C= +aroll under the SIGHASH_GROUP flag, with `sig_group_count`=3D2.<br>y_1 and = +y_2 are disjunctive.<br><br>At broadcast, Alice is not able to combine {x_1= +,y_1} and {x_2, y_2} for the reason that x_1, x_2 are colliding on the abso= +lute output position.<br><br>One fix could be to skim the "end > nu= +m_ouputs" semantic, and thus have Alice negotiate (start,end) encompas= +sing all her channels outputs index and then strictly ordering her i indexe= +s on all her counterparties. But I don't think you can assume index ord= +er to be transitive across Lightning nodes, at least without bundle combina= +tion gaps in your local set of channels.<br><br>I think this SIGHASH_GROUP = +proposal might solve other use-cases, but if I understand the semantics cor= +rectly, it doesn't seem to achieve the batch fee-bumping of multiple Li= +ghtning commitment with O(1) onchain footprint I was thinking of for IOMAP.= +..<br><br>One counter-proposal to solve this "pre-signed y-outputs ord= +inate" could be instead to envision the SIGHASH_GROUP as vector coordi= +nates and the annex field as the projection.<br><br>Let's say annex fie= +ld :=3D (hashOutputsGroups) and SIGHASH_GROUP(i,j) where j is a non-null in= +teger.<br>Call i the starting index of the output group committed by this i= +nput.<br>Call j the output group size committed by this input.<br><br>At va= +lidation, compute `hashOutputsGroup` =3D H(outputs[i...i+j-1]).<br>If the c= +omputed `hashOutputGroup` isn't equal to the input annex field `hashOut= +putsGroup`, fails validation.<br>Otherwise, substitute `hashOutputGroup` to= + bip-143 `hashOutputs` while conserving , and proceed to signature verifica= +tion.<br><br>As (i,j) are not included in the annex and are only part of wi= +tness data, they can be selected by the bundles combiner at broadcast to co= +nstruct a valid transaction.<br><br>If the combiner is malicious and (i,j) = +points to another outputs group, the computed hash is going to be invalid, = +as it doesn't satisfy the annex `output_group` field.<br><br>If you wan= +t to disallow partial overlaps for your bundle, we could even have a bit k.= + If k=3D1, verify that all transaction `output_group` fields are not collid= +ing.<br><br>Hmmmm, sounds more flexible but you might still have a bit of h= +ashing complexity to deal with ?<br><br>> Okay, now that I've writte= +n and re-written that a couple of times,<br>> it looks like I'm just= + reinventing Rusty's signature bundles from 2018:<br>> <br>> <a h= +ref=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-April/0= +15862.html">https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-Ap= +ril/015862.html</a><br>> <br>> (though at least I think using the ann= +ex is probably an improvement on<br>> having values that affect other in= +puts being buried deeper in an input's<br>> witness data)<br>> <b= +r>> Without something like this, I think it will be very hard to incorpo= +rate<br>> fees into eltoo with layered commitments [0]. As a new sighash= + mode it<br>> would make sense to include it as part of ANYPREVOUT to av= +oid introducing<br>> many new "unknown key types".<br><br>Well= +, I agree on the overall direction though maybe we should detail primitive = +requirements a bit more, otherwise it might not fit the second-layer use-ca= +se we're interested with.<br><br>Cheers,<br>Antoine<br></div><br><div c= +lass=3D"gmail_quote"><div dir=3D"ltr" class=3D"gmail_attr">Le=C2=A0jeu. 8 j= +uil. 2021 =C3=A0=C2=A007:17, Anthony Towns <<a href=3D"mailto:aj@erisian= +.com.au">aj@erisian.com.au</a>> a =C3=A9crit=C2=A0:<br></div><blockquote= + class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left:1px so= +lid rgb(204,204,204);padding-left:1ex">On Thu, May 27, 2021 at 04:14:13PM -= +0400, Antoine Riard via bitcoin-dev wrote:<br> +> This overhead could be smoothed even further in the future with more a= +dvanced<br> +> sighash malleability flags like SIGHASH_IOMAP, allowing transaction si= +gners to<br> +> commit to a map of inputs/outputs [2]. In the context of input-based, = +the<br> +> overflowed fee value could be redirected to an outgoing output.<br> +<br> +> Input-based (SIGHASH_ANYPREVOUT+SIGHASH_IOMAP): Multiple chains of tra= +nsactions<br> +> might be aggregated together *non-interactively*. One bumping input an= +d<br> +> outgoing output can be attached to the aggregated root.<br> +<br> +> [2] <a href=3D"https://bitcointalk.org/index.php?topic=3D252960.0" rel= +=3D"noreferrer" target=3D"_blank">https://bitcointalk.org/index.php?topic= +=3D252960.0</a><br> +<br> +I haven't seen any recent specs for "IOMAP", but there are a = +few things<br> +that have bugged me about them in the past:<br> +<br> +=C2=A0(1) allowing partially overlapping sets of outputs could allow "= +theft",<br> +=C2=A0 =C2=A0 =C2=A0eg if I give you a signature "you can spend A+B as= + long as I get X"<br> +=C2=A0 =C2=A0 =C2=A0and "you can spend A+C as long as I get X", y= +ou could combine them<br> +=C2=A0 =C2=A0 =C2=A0to spend A+B+C instead but still only give me 1 X.<br> +<br> +=C2=A0(2) a range specification or a whole bitfield is a lot heavier than a= +n<br> +=C2=A0 =C2=A0 =C2=A0extra bit to add to the sighash<br> +<br> +=C2=A0(3) this lets you specify lots of different ways of hashing the<br> +=C2=A0 =C2=A0 =C2=A0outputs, which then can't be cached, so you get kin= +d-of quadratic<br> +=C2=A0 =C2=A0 =C2=A0behaviour -- O(n^2/8) where n/2 is the size of the inpu= +ts, which<br> +=C2=A0 =C2=A0 =C2=A0gives you the number of signatures, and n/2 is also the= + size of the<br> +=C2=A0 =C2=A0 =C2=A0outputs, so n/4 is a different half of the output selec= +ted for each<br> +=C2=A0 =C2=A0 =C2=A0signature in the input.<br> +<br> +But under the "don't bring me problems, bring me solutions" b= +anner,<br> +here's an idea.<br> +<br> +The easy way to avoid O(n^2) behaviour in (3) is to disallow partial<br> +overlaps. So let's treat the tx as being distinct bundles of x-inputs<b= +r> +and y-outputs, and we'll use the annex for grouping, since that is<br> +committed to by singatures. Call the annex field "sig_group_count"= +;.<br> +<br> +When processing inputs, setup a new state pair, (start, end), initially<br> +(0,0).<br> +<br> +When evaluating an input, lookup sig_group_count. If it's not present,<= +br> +then set start :=3D end. If it's present and 0, leave start and end<br> +unchanged. Otherwise, if it's present and greather than 0, set<br> +start :=3D end, and then set end :=3D start + sig_group_count.<br> +<br> +Introduce a new SIGHASH_GROUP flag, as an alternative to ALL/SINGLE/NONE,<b= +r> +that commits to each output i, start <=3D i < end. If start=3D=3Dend = +or end ><br> +num_outputs, signature is invalid.<br> +<br> +That means each output in a tx could be hashed three times instead of<br> +twice (once for its particular group, as well as once for SIGHASH_ALL<br> +and once for SIGHASH_SINGLE), and I think would let you combine x-input<br> +and y-outputs fairly safely, by having the first input commit to "y&qu= +ot;<br> +in the annex, and the remaining x-1 commit to "0".<br> +<br> +That does mean if you have two different sets of inputs (x1 and x2)<br> +each spending to the exact same set of y outputs, you could claim all<br> +but one of them while only paying a single set of y outputs. But you<br> +could include an "OP_RETURN hash(x1)" tapleaf branch in one of th= +e y<br> +outputs to ensure the outputs aren't precisely the same to avoid that<b= +r> +problem, so maybe that's fine?<br> +<br> +Okay, now that I've written and re-written that a couple of times,<br> +it looks like I'm just reinventing Rusty's signature bundles from 2= +018:<br> +<br> +<a href=3D"https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-Apr= +il/015862.html" rel=3D"noreferrer" target=3D"_blank">https://lists.linuxfou= +ndation.org/pipermail/bitcoin-dev/2018-April/015862.html</a><br> +<br> +(though at least I think using the annex is probably an improvement on<br> +having values that affect other inputs being buried deeper in an input'= +s<br> +witness data)<br> +<br> +<br> +<br> +Without something like this, I think it will be very hard to incorporate<br= +> +fees into eltoo with layered commitments [0]. As a new sighash mode it<br> +would make sense to include it as part of ANYPREVOUT to avoid introducing<b= +r> +many new "unknown key types".<br> +<br> +[0] <a href=3D"https://lists.linuxfoundation.org/pipermail/lightning-dev/20= +20-January/002448.html" rel=3D"noreferrer" target=3D"_blank">https://lists.= +linuxfoundation.org/pipermail/lightning-dev/2020-January/002448.html</a><br= +> +=C2=A0 =C2=A0 also, <a href=3D"https://www.erisian.com.au/lightning-dev/log= +-2021-07-08.html" rel=3D"noreferrer" target=3D"_blank">https://www.erisian.= +com.au/lightning-dev/log-2021-07-08.html</a><br> +<br> +Cheers,<br> +aj<br> +<br> +</blockquote></div> + +--000000000000bf452805c6b0a0d9-- + |