1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
Return-Path: <aj@erisian.com.au>
Received: from smtp3.osuosl.org (smtp3.osuosl.org [IPv6:2605:bc80:3010::136])
by lists.linuxfoundation.org (Postfix) with ESMTP id 97380C000E
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 8 Jul 2021 11:17:28 +0000 (UTC)
Received: from localhost (localhost [127.0.0.1])
by smtp3.osuosl.org (Postfix) with ESMTP id 935B460A93
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 8 Jul 2021 11:17:28 +0000 (UTC)
X-Virus-Scanned: amavisd-new at osuosl.org
X-Spam-Flag: NO
X-Spam-Score: -0.098
X-Spam-Level:
X-Spam-Status: No, score=-0.098 tagged_above=-999 required=5
tests=[BAYES_05=-0.5, KHOP_HELO_FCRDNS=0.399, SPF_HELO_NONE=0.001,
SPF_NONE=0.001, UNPARSEABLE_RELAY=0.001]
autolearn=no autolearn_force=no
Received: from smtp3.osuosl.org ([127.0.0.1])
by localhost (smtp3.osuosl.org [127.0.0.1]) (amavisd-new, port 10024)
with ESMTP id GznsdiQxSX-P
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 8 Jul 2021 11:17:27 +0000 (UTC)
X-Greylist: from auto-whitelisted by SQLgrey-1.8.0
Received: from azure.erisian.com.au (cerulean.erisian.com.au [139.162.42.226])
by smtp3.osuosl.org (Postfix) with ESMTPS id 92C4F606A7
for <bitcoin-dev@lists.linuxfoundation.org>;
Thu, 8 Jul 2021 11:17:27 +0000 (UTC)
Received: from aj@azure.erisian.com.au (helo=sapphire.erisian.com.au)
by azure.erisian.com.au with esmtpsa (Exim 4.92 #3 (Debian))
id 1m1S1x-00038j-UL; Thu, 08 Jul 2021 21:17:23 +1000
Received: by sapphire.erisian.com.au (sSMTP sendmail emulation);
Thu, 08 Jul 2021 21:17:16 +1000
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)
X-Spam-Score-int: -18
X-Spam-Bar: -
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: Thu, 08 Jul 2021 11:17:28 -0000
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
|
