From: Anthony Towns <aj@erisian•com.au>
To: Antoine Riard <antoine.riard@gmail•com>,
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
Date: Thu, 8 Jul 2021 21:17:16 +1000 [thread overview]
Message-ID: <20210708111716.GC1339@erisian.com.au> (raw)
In-Reply-To: <CALZpt+FvLb=N5Qygs+dPmh1o9QCwXj8RoznF5n47opOq7CG_0g@mail.gmail.com>
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
next prev parent reply other threads:[~2021-07-08 11:17 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-05-27 20:14 Antoine Riard
2021-05-27 21:45 ` darosior
2021-05-28 4:13 ` Antoine Riard
2021-05-28 22:25 ` darosior
2021-06-10 21:16 ` Antoine Riard
2021-06-10 13:18 ` darosior
2021-06-07 2:27 ` Lloyd Fournier
2021-06-10 21:45 ` Antoine Riard
2021-06-10 22:47 ` darosior
2021-06-13 5:56 ` Lloyd Fournier
2021-06-13 14:16 ` Jeremy
2021-06-14 17:18 ` Antoine Riard
2021-06-14 16:46 ` Antoine Riard
2021-06-15 0:59 ` Lloyd Fournier
2021-06-15 3:08 ` Lloyd Fournier
2021-07-08 11:17 ` Anthony Towns [this message]
2021-07-09 13:19 ` Antoine Riard
2021-07-10 1:47 ` Anthony Towns
2021-07-12 0:02 ` Antoine Riard
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20210708111716.GC1339@erisian.com.au \
--to=aj@erisian$(echo .)com.au \
--cc=antoine.riard@gmail$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox