Date: Thu, 8 Jul 2021 21:17:16 +1000
From: Anthony Towns <aj@erisian.com.au>
To: Antoine Riard <antoine.riard@gmail.com>,
 Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Message-ID: <20210708111716.GC1339@erisian.com.au>
References: <CALZpt+FvLb=N5Qygs+dPmh1o9QCwXj8RoznF5n47opOq7CG_0g@mail.gmail.com>
MIME-Version: 1.0
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
In-Reply-To: <CALZpt+FvLb=N5Qygs+dPmh1o9QCwXj8RoznF5n47opOq7CG_0g@mail.gmail.com>
User-Agent: Mutt/1.10.1 (2018-07-13)
Subject: Re: [bitcoin-dev] A Stroll through Fee-Bumping Techniques :
 Input-Based vs Child-Pay-For-Parent
Precedence: list

On Thu, May 27, 2021 at 04:14:13PM -0400, Antoine Riard via bitcoin-dev wrote:
> This overhead could be smoothed even further in the future with more advanced
> sighash malleability flags like SIGHASH_IOMAP, allowing transaction signers to
> commit to a map of inputs/outputs [2]. In the context of input-based, the
> overflowed fee value could be redirected to an outgoing output.

> Input-based (SIGHASH_ANYPREVOUT+SIGHASH_IOMAP): Multiple chains of transactions
> might be aggregated together *non-interactively*. One bumping input and
> outgoing output can be attached to the aggregated root.

> [2] https://bitcointalk.org/index.php?topic=252960.0

I haven't seen any recent specs for "IOMAP", but there are a few things
that have bugged me about them in the past:

 (1) allowing partially overlapping sets of outputs could allow "theft",
     eg if I give you a signature "you can spend A+B as long as I get X"
     and "you can spend A+C as long as I get X", you could combine them
     to spend A+B+C instead but still only give me 1 X.

 (2) a range specification or a whole bitfield is a lot heavier than an
     extra bit to add to the sighash

 (3) this lets you specify lots of different ways of hashing the
     outputs, which then can't be cached, so you get kind-of quadratic
     behaviour -- O(n^2/8) where n/2 is the size of the inputs, which
     gives you the number of signatures, and n/2 is also the size of the
     outputs, so n/4 is a different half of the output selected for each
     signature in the input.

But under the "don't bring me problems, bring me solutions" banner,
here's an idea.

The easy way to avoid O(n^2) behaviour in (3) is to disallow partial
overlaps. So let's treat the tx as being distinct bundles of x-inputs
and y-outputs, and we'll use the annex for grouping, since that is
committed to by singatures. Call the annex field "sig_group_count".

When processing inputs, setup a new state pair, (start, end), initially
(0,0).

When evaluating an input, lookup sig_group_count. If it's not present,
then set start := end. If it's present and 0, leave start and end
unchanged. Otherwise, if it's present and greather than 0, set
start := end, and then set end := start + sig_group_count.

Introduce a new SIGHASH_GROUP flag, as an alternative to ALL/SINGLE/NONE,
that commits to each output i, start <= i < end. If start==end or end >
num_outputs, signature is invalid.

That means each output in a tx could be hashed three times instead of
twice (once for its particular group, as well as once for SIGHASH_ALL
and once for SIGHASH_SINGLE), and I think would let you combine x-input
and y-outputs fairly safely, by having the first input commit to "y"
in the annex, and the remaining x-1 commit to "0".

That does mean if you have two different sets of inputs (x1 and x2)
each spending to the exact same set of y outputs, you could claim all
but one of them while only paying a single set of y outputs. But you
could include an "OP_RETURN hash(x1)" tapleaf branch in one of the y
outputs to ensure the outputs aren't precisely the same to avoid that
problem, so maybe that's fine?

Okay, now that I've written and re-written that a couple of times,
it looks like I'm just reinventing Rusty's signature bundles from 2018:

https://lists.linuxfoundation.org/pipermail/bitcoin-dev/2018-April/015862.html

(though at least I think using the annex is probably an improvement on
having values that affect other inputs being buried deeper in an input's
witness data)


Without something like this, I think it will be very hard to incorporate
fees into eltoo with layered commitments [0]. As a new sighash mode it
would make sense to include it as part of ANYPREVOUT to avoid introducing
many new "unknown key types".

[0] https://lists.linuxfoundation.org/pipermail/lightning-dev/2020-January/002448.html
    also, https://www.erisian.com.au/lightning-dev/log-2021-07-08.html

Cheers,
aj