path: root/e6/9364856bc6a4b63f3d9a683eaa7264105d5a04

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--