summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAntoine Riard <antoine.riard@gmail.com>2021-07-09 09:19:45 -0400
committerbitcoindev <bitcoindev@gnusha.org>2021-07-09 13:20:01 +0000
commitccf6e06c9240d624c2c233402d877e7189e96c8f (patch)
treed4761d5de83a0dcc242961d9291b6fc66ca9bd82
parent872458a6c09656f87cef8e4f95c8430df5aeee2d (diff)
downloadpi-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/9364856bc6a4b63f3d9a683eaa7264105d5a04657
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>&gt; This overhead could be smoothed even further i=
+n the future with more advanced<br>&gt; sighash malleability flags like SIG=
+HASH_IOMAP, allowing transaction signers to<br>&gt; commit to a map of inpu=
+ts/outputs [2]. In the context of input-based, the<br>&gt; overflowed fee v=
+alue could be redirected to an outgoing output.<br><br>&gt; Input-based (SI=
+GHASH_ANYPREVOUT+SIGHASH_IOMAP): Multiple chains of transactions<br>&gt; 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>&gt; [2] =
+<a href=3D"https://bitcointalk.org/index.php?topic=3D252960.0">https://bitc=
+ointalk.org/index.php?topic=3D252960.0</a><br><br>&gt; I haven&#39;t seen a=
+ny recent specs for &quot;IOMAP&quot;, but there are a few things<br>&gt; t=
+hat have bugged me about them in the past:<br><br>TBH, I don&#39;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>&gt; =C2=A0(1) allowing partially overlapping sets of outputs could al=
+low &quot;theft&quot;,<br>&gt; =C2=A0 =C2=A0 =C2=A0eg if I give you a signa=
+ture &quot;you can spend A+B as long as I get X&quot;<br>&gt; =C2=A0 =C2=A0=
+ =C2=A0and &quot;you can spend A+C as long as I get X&quot;, you could comb=
+ine them<br>&gt; =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&#39;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&#39;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&#39;s script and thus lockdown transaction template at broadcast. I don&#=
+39;t think it works here as you can&#39;t assume that your counterparties, =
+from different protocol sessions, won&#39;t collude together to combine the=
+ir finalizing signatures and achieve a spend replay across sessions ?<br><b=
+r>That said, I&#39;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&#39;s output valu=
+e ?<br><br>&gt; =C2=A0(2) a range specification or a whole bitfield is a lo=
+t heavier than an<br>&gt; =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>&gt; =C2=A0(3) this=
+ lets you specify lots of different ways of hashing the<br>&gt; =C2=A0 =C2=
+=A0 =C2=A0outputs, which then can&#39;t be cached, so you get kind-of quadr=
+atic<br>&gt; =C2=A0 =C2=A0 =C2=A0behaviour -- O(n^2/8) where n/2 is the siz=
+e of the inputs, which<br>&gt; =C2=A0 =C2=A0 =C2=A0gives you the number of =
+signatures, and n/2 is also the size of the<br>&gt; =C2=A0 =C2=A0 =C2=A0out=
+puts, so n/4 is a different half of the output selected for each<br>&gt; =
+=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&#39;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 &quot;don&#39;t bring me problems, bring me solutions&quot; banner, her=
+e&#39;s an idea.<br><br>&gt; The easy way to avoid O(n^2) behaviour in (3) =
+is to disallow partial<br>&gt; overlaps. So let&#39;s treat the tx as being=
+ distinct bundles of x-inputs<br>&gt; and y-outputs, and we&#39;ll use the =
+annex for grouping, since that is<br>&gt; committed to by singatures. Call =
+the annex field &quot;sig_group_count&quot;.<br><br>&gt; When processing in=
+puts, setup a new state pair, (start, end), initially<br>&gt; (0,0).<br>&gt=
+; <br>&gt; When evaluating an input, lookup sig_group_count. If it&#39;s no=
+t present,<br>&gt; then set start :=3D end. If it&#39;s present and 0, leav=
+e start and end<br>&gt; unchanged. Otherwise, if it&#39;s present and great=
+her than 0, set<br>&gt; start :=3D end, and then set end :=3D start + sig_g=
+roup_count.<br><br>IIUC the design rationale, the &quot;sig_group_count&quo=
+t; lockdowns the hashing of outputs for a given input, thus allowing midsta=
+te reuse across signatures input.<br><br>&gt; Introduce a new SIGHASH_GROUP=
+ flag, as an alternative to ALL/SINGLE/NONE,<br>&gt; that commits to each o=
+utput i, start &lt;=3D i &lt; end. If start=3D=3Dend or end &gt;<br>&gt; nu=
+m_outputs, signature is invalid.<br>&gt; <br>&gt; That means each output in=
+ a tx could be hashed three times instead of<br>&gt; twice (once for its pa=
+rticular group, as well as once for SIGHASH_ALL<br>&gt; and once for SIGHAS=
+H_SINGLE), and I think would let you combine x-input<br>&gt; and y-outputs =
+fairly safely, by having the first input commit to &quot;y&quot;<br>&gt; in=
+ the annex, and the remaining x-1 commit to &quot;0&quot;.<br>&gt; <br>&gt;=
+ That does mean if you have two different sets of inputs (x1 and x2)<br>&gt=
+; each spending to the exact same set of y outputs, you could claim all<br>=
+&gt; but one of them while only paying a single set of y outputs. But you<b=
+r>&gt; could include an &quot;OP_RETURN hash(x1)&quot; tapleaf branch in on=
+e of the y<br>&gt; outputs to ensure the outputs aren&#39;t precisely the s=
+ame to avoid that<br>&gt; problem, so maybe that&#39;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&#39;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 &quot;end &gt; nu=
+m_ouputs&quot; 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&#39;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&#39;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 &quot;pre-signed y-outputs ord=
+inate&quot; could be instead to envision the SIGHASH_GROUP as vector coordi=
+nates and the annex field as the projection.<br><br>Let&#39;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&#39;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&#39;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>&gt; Okay, now that I&#39;ve writte=
+n and re-written that a couple of times,<br>&gt; it looks like I&#39;m just=
+ reinventing Rusty&#39;s signature bundles from 2018:<br>&gt; <br>&gt; <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>&gt; <br>&gt; (though at least I think using the ann=
+ex is probably an improvement on<br>&gt; having values that affect other in=
+puts being buried deeper in an input&#39;s<br>&gt; witness data)<br>&gt; <b=
+r>&gt; Without something like this, I think it will be very hard to incorpo=
+rate<br>&gt; fees into eltoo with layered commitments [0]. As a new sighash=
+ mode it<br>&gt; would make sense to include it as part of ANYPREVOUT to av=
+oid introducing<br>&gt; many new &quot;unknown key types&quot;.<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&#39;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 &lt;<a href=3D"mailto:aj@erisian=
+.com.au">aj@erisian.com.au</a>&gt; 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>
+&gt; This overhead could be smoothed even further in the future with more a=
+dvanced<br>
+&gt; sighash malleability flags like SIGHASH_IOMAP, allowing transaction si=
+gners to<br>
+&gt; commit to a map of inputs/outputs [2]. In the context of input-based, =
+the<br>
+&gt; overflowed fee value could be redirected to an outgoing output.<br>
+<br>
+&gt; Input-based (SIGHASH_ANYPREVOUT+SIGHASH_IOMAP): Multiple chains of tra=
+nsactions<br>
+&gt; might be aggregated together *non-interactively*. One bumping input an=
+d<br>
+&gt; outgoing output can be attached to the aggregated root.<br>
+<br>
+&gt; [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&#39;t seen any recent specs for &quot;IOMAP&quot;, 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 &quot;=
+theft&quot;,<br>
+=C2=A0 =C2=A0 =C2=A0eg if I give you a signature &quot;you can spend A+B as=
+ long as I get X&quot;<br>
+=C2=A0 =C2=A0 =C2=A0and &quot;you can spend A+C as long as I get X&quot;, 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&#39;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 &quot;don&#39;t bring me problems, bring me solutions&quot; b=
+anner,<br>
+here&#39;s an idea.<br>
+<br>
+The easy way to avoid O(n^2) behaviour in (3) is to disallow partial<br>
+overlaps. So let&#39;s treat the tx as being distinct bundles of x-inputs<b=
+r>
+and y-outputs, and we&#39;ll use the annex for grouping, since that is<br>
+committed to by singatures. Call the annex field &quot;sig_group_count&quot=
+;.<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&#39;s not present,<=
+br>
+then set start :=3D end. If it&#39;s present and 0, leave start and end<br>
+unchanged. Otherwise, if it&#39;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 &lt;=3D i &lt; end. If start=3D=3Dend =
+or end &gt;<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 &quot;y&qu=
+ot;<br>
+in the annex, and the remaining x-1 commit to &quot;0&quot;.<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 &quot;OP_RETURN hash(x1)&quot; tapleaf branch in one of th=
+e y<br>
+outputs to ensure the outputs aren&#39;t precisely the same to avoid that<b=
+r>
+problem, so maybe that&#39;s fine?<br>
+<br>
+Okay, now that I&#39;ve written and re-written that a couple of times,<br>
+it looks like I&#39;m just reinventing Rusty&#39;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&#39;=
+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 &quot;unknown key types&quot;.<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--
+