[bitcoin-dev] Signature bundles

[bitcoin-dev] Signature bundles

[Rusty Russell]

Hi all!

        Since there's activity on new signature types, I think it's
worth considering a more flexible alternative to
SIGHASH_SINGLE|SIGHASH_ANYONECANPAY.  See Usefulness for why.

Proposal: Two bits: SIGHASH_BUNDLESTART/SIGHASH_INBUNDLE
--------

A signature needs to indicate that signs only part of a transaction's
inputs and outputs (a.k.a. a "bundle").  Bundles can be combined
together into larger transactions, and non-bundled signature inputs /
outputs appended.

Two per-tx counters are kept: bundle_inputs_used and
bundle_outputs_used, both starting at 0.

SIGHASH_BUNDLESTART indicates two var_int sit between the sighash flags
and the signature itself: the first is the number of inputs in this
bundle starting at bundle_inputs_used, the second is the number of
outputs starting at bundle_outputs_used.  bundle_inputs_used and
bundle_outputs_used have these values added, for next time.

SIGHASH_INBUNDLE indicates that this signature applies to the current
bundle.  The txCopy is reduced to cover only the inputs and
outputs in the current bundle, and the signature commits to the two
var_ints from SIGHASH_BUNDLESTART along with the sighash flags.

(A proper BIP would detail how any weird stuff makes the tx invalid:
take that as read).

Usage
-----
You can use this to sign a transaction just like now, with only two
extra bytes and these SIGHASH flags.  But this transaction can now be
aggregated by pasting on another bundle, or attaching other normal
inputs and/or outputs.  You can aggregate as many transactions as you
want this way.

Usefulness
----------

One of the issues we've struck with lightning is trying to guess future
fees for commitment transactions: we can't rely on getting another
signature from our counterparty to increase fees.  Nor can we use
parent-pays-for-child since the outputs we can spend are timelocked.

This "holding a valid tx but I want to add fees later without
re-signing" seems like a general problem.  The only current method would
be to engineer transactions as a single-input-single-output tx and use
SIGHASH_SINGLE|SIGHASH_ANYONECANPAY; this is very limiting.

The other obvious application would be to run public aggregators, which
would provide throughput promises ("if you send me a tx with feerate X,
I will make sure it goes onchain within a week").  This service would
sometimes profit, if it can do so cheaper than it quoted, and sometimes
have to add additional fees.  The existence of such services should
smooth the current fee cliff by allowing users and services to offer
"slow mode" payment options without requiring interaction.

Feedback welcome!
Rusty.

Re: [bitcoin-dev] Signature bundles

[Anthony Towns]

On Tue, Apr 03, 2018 at 09:16:45AM +0930, Rusty Russell via bitcoin-dev wrote:
> Proposal: Two bits: SIGHASH_BUNDLESTART/SIGHASH_INBUNDLE
> --------
> 
> A signature needs to indicate that signs only part of a transaction's
> inputs and outputs (a.k.a. a "bundle").  Bundles can be combined
> together into larger transactions, and non-bundled signature inputs /
> outputs appended.

> Two per-tx counters are kept: bundle_inputs_used and
> bundle_outputs_used, both starting at 0.
> 
> SIGHASH_BUNDLESTART indicates two var_int sit between the sighash flags
> and the signature itself: the first is the number of inputs in this
> bundle starting at bundle_inputs_used, the second is the number of
> outputs starting at bundle_outputs_used.  bundle_inputs_used and
> bundle_outputs_used have these values added, for next time.
> 
> SIGHASH_INBUNDLE indicates that this signature applies to the current
> bundle.  The txCopy is reduced to cover only the inputs and
> outputs in the current bundle, and the signature commits to the two
> var_ints from SIGHASH_BUNDLESTART along with the sighash flags.

So suppose you have two bundles you want to combine together, and they
didn't pay enough fees, so you have an extra input so you can bump up the
fees. Your tx looks like:

bundle 1:
  input 1:   500 bits, signed by key A [pre]
  input 2:   500 bits, signed by key B [pre]
  input 3:   500 bits, signed by key C
  output 1: 1450 bits
bundle 2:
  input 3:   600 bits, signed by key D [pre]
  output 2:  200 bits
  output 3:  380 bits
extra:
  input 4:  2000 bits, signed by key E
  output 4:  864 bits

Keys A, B and D have pre-signed their respective bundle, but you have
control over keys C and E at the time you're constructing the transaction.

So the things you'd have to do when signing would be:

  A,B,C decide on an order for the inputs and outputs (ideally just sort them)
  Because A turns out to be first, A signs with BUNDLESTART[3,1] INBUNDLE
  Because B is second, B just signs with INBUNDLE

  D just signs with BUNDLESTART[3,1] INBUNDLE

  And finally they get collected and C and E signs the entire transaction
  with SIGHASH_ALL

All bundles have to appear together, before any extra inputs; though they
can be reordered arbitrarily prior to adding the SIGHASH_ALL sigs.

If you've got one bundle that overpays fees and another that underpays,
you can safely combine the two only if you can put a SIGHASH_ALL sig in
the one that overpays (otherwise miners could just make their own tx of
just the overpaying bundle).

This could replace SINGLE|ANYONECANPAY at a cost of an extra couple of
witness bytes.

I think BUNDLESTART is arguably redundant -- you could just infer
BUNDLESTART if you see an INBUNDLE flag when you're not already in
a bundle. Probably better to have the flag to make parsing easier,
so just have the rule be BUNDLESTART is set for precisely the first
INBUNDLE signature since the last bundle finished.

Should be straightforward to establish BIP-69-style ordering rules too:
within a bundle, order inputs lexically, then order outputs lexically;
order bundles lexically by the first input; order remaining inputs
lexically, then order remaining outputs lexically.

I think the only reason to do bundling like this (rather than just post
separate transactions) is to deal with fees? It doesn't seem like you gain
any privacy -- the inputs/outputs in each bundle are tightly related, and
you're only saving about 10 bytes due to sharing a transaction structure.

Anyway, seems like it makes sense. 

> One of the issues we've struck with lightning is trying to guess future
> fees for commitment transactions: we can't rely on getting another
> signature from our counterparty to increase fees.  Nor can we use
> parent-pays-for-child since the outputs we can spend are timelocked.

That doesn't quite work with the HTLC-Success/HTLC-Timeout transactions
though, does it? They spend outputs from the commitment transaction
and need to be pre-signed by your channel partner in order to ensure
the output address is correct -- but if the commitment transaction gets
bundled, its txid will change, so it can't be pre-signed.

FWIW, a dumb idea I had for this problem was to add a zero-value
anyone-can-spend output to commitment transactions, that can then be
used with CPFP to bump the fees. Not very nice for UTXO bloat if fee
bumping isn't needed though, and I presume it would fail to pass the
dust threshold...

I wonder if it would be plausible to have after-the-fact fee-bumping
via special sighash flags at the block level anyway though. Concretely:
say you have two transactions, X and Y, that don't pay enough in fees,
you then provide a third transaction whose witness is [txid-for-X,
txid-for-Y, signature committing to (txid-for-X, txid-for-Y)], and can
only be included in a block if X and Y are also in the same block. You
could make that fairly concise if you allowed miners to replace txid-for-X
with X's offset within the block (or the delta between X's txnum and the
third transaction's txnum), though coding that probably isn't terribly
straightforward.

Cheers,
aj

Re: [bitcoin-dev] Signature bundles

[Rusty Russell]

Anthony Towns via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org> writes:
> If you've got one bundle that overpays fees and another that underpays,
> you can safely combine the two only if you can put a SIGHASH_ALL sig in
> the one that overpays (otherwise miners could just make their own tx of
> just the overpaying bundle).

This is a potential problem, yes :( And I'm not sure how to solve it,
unless you do some crazy thing like commit to a set of keys which are
allowed to bundle, which kind of defeats the generality of outsourcing.

> This could replace SINGLE|ANYONECANPAY at a cost of an extra couple of
> witness bytes.
>
> I think BUNDLESTART is arguably redundant -- you could just infer
> BUNDLESTART if you see an INBUNDLE flag when you're not already in
> a bundle. Probably better to have the flag to make parsing easier,
> so just have the rule be BUNDLESTART is set for precisely the first
> INBUNDLE signature since the last bundle finished.

Indeed.

>> One of the issues we've struck with lightning is trying to guess future
>> fees for commitment transactions: we can't rely on getting another
>> signature from our counterparty to increase fees.  Nor can we use
>> parent-pays-for-child since the outputs we can spend are timelocked.
>
> That doesn't quite work with the HTLC-Success/HTLC-Timeout transactions
> though, does it? They spend outputs from the commitment transaction
> and need to be pre-signed by your channel partner in order to ensure
> the output address is correct -- but if the commitment transaction gets
> bundled, its txid will change, so it can't be pre-signed.

Not without SIGHASH_NOINPUT, no.

> FWIW, a dumb idea I had for this problem was to add a zero-value
> anyone-can-spend output to commitment transactions, that can then be
> used with CPFP to bump the fees. Not very nice for UTXO bloat if fee
> bumping isn't needed though, and I presume it would fail to pass the
> dust threshold...

Yeah, let's not do that.

> I wonder if it would be plausible to have after-the-fact fee-bumping
> via special sighash flags at the block level anyway though. Concretely:
> say you have two transactions, X and Y, that don't pay enough in fees,
> you then provide a third transaction whose witness is [txid-for-X,
> txid-for-Y, signature committing to (txid-for-X, txid-for-Y)], and can
> only be included in a block if X and Y are also in the same block. You
> could make that fairly concise if you allowed miners to replace txid-for-X
> with X's offset within the block (or the delta between X's txnum and the
> third transaction's txnum), though coding that probably isn't terribly
> straightforward.

What would it spend though?  Can't use an existing output, so this
really needs to be stashed in an *output script*, say a zero-amount
output which is literally a push of txids, and is itself unspendable.

        <txid1>... <txidN>

That's pretty large though, and it's non-witness data (though
discardable).  How about 'OP_NOP4 <N> <ripemd160-of-last-N-txids>'?
Then the miner just bundles those tx all together?

Cheers,
Rusty.

Re: [bitcoin-dev] Signature bundles

[Jim Posen]

[-- Attachment #1: Type: text/plain, Size: 3617 bytes --]

I'll just mention that non-interactive one-way aggregation with BLS
signatures solves this problem rather nicely.

On Mon, Apr 2, 2018 at 10:31 PM, Rusty Russell via bitcoin-dev <
bitcoin-dev@lists.linuxfoundation.org> wrote:

> Anthony Towns via bitcoin-dev <bitcoin-dev@lists.linuxfoundation.org>
> writes:
> > If you've got one bundle that overpays fees and another that underpays,
> > you can safely combine the two only if you can put a SIGHASH_ALL sig in
> > the one that overpays (otherwise miners could just make their own tx of
> > just the overpaying bundle).
>
> This is a potential problem, yes :( And I'm not sure how to solve it,
> unless you do some crazy thing like commit to a set of keys which are
> allowed to bundle, which kind of defeats the generality of outsourcing.
>
> > This could replace SINGLE|ANYONECANPAY at a cost of an extra couple of
> > witness bytes.
> >
> > I think BUNDLESTART is arguably redundant -- you could just infer
> > BUNDLESTART if you see an INBUNDLE flag when you're not already in
> > a bundle. Probably better to have the flag to make parsing easier,
> > so just have the rule be BUNDLESTART is set for precisely the first
> > INBUNDLE signature since the last bundle finished.
>
> Indeed.
>
> >> One of the issues we've struck with lightning is trying to guess future
> >> fees for commitment transactions: we can't rely on getting another
> >> signature from our counterparty to increase fees.  Nor can we use
> >> parent-pays-for-child since the outputs we can spend are timelocked.
> >
> > That doesn't quite work with the HTLC-Success/HTLC-Timeout transactions
> > though, does it? They spend outputs from the commitment transaction
> > and need to be pre-signed by your channel partner in order to ensure
> > the output address is correct -- but if the commitment transaction gets
> > bundled, its txid will change, so it can't be pre-signed.
>
> Not without SIGHASH_NOINPUT, no.
>
> > FWIW, a dumb idea I had for this problem was to add a zero-value
> > anyone-can-spend output to commitment transactions, that can then be
> > used with CPFP to bump the fees. Not very nice for UTXO bloat if fee
> > bumping isn't needed though, and I presume it would fail to pass the
> > dust threshold...
>
> Yeah, let's not do that.
>
> > I wonder if it would be plausible to have after-the-fact fee-bumping
> > via special sighash flags at the block level anyway though. Concretely:
> > say you have two transactions, X and Y, that don't pay enough in fees,
> > you then provide a third transaction whose witness is [txid-for-X,
> > txid-for-Y, signature committing to (txid-for-X, txid-for-Y)], and can
> > only be included in a block if X and Y are also in the same block. You
> > could make that fairly concise if you allowed miners to replace
> txid-for-X
> > with X's offset within the block (or the delta between X's txnum and the
> > third transaction's txnum), though coding that probably isn't terribly
> > straightforward.
>
> What would it spend though?  Can't use an existing output, so this
> really needs to be stashed in an *output script*, say a zero-amount
> output which is literally a push of txids, and is itself unspendable.
>
>         <txid1>... <txidN>
>
> That's pretty large though, and it's non-witness data (though
> discardable).  How about 'OP_NOP4 <N> <ripemd160-of-last-N-txids>'?
> Then the miner just bundles those tx all together?
>
> Cheers,
> Rusty.
> _______________________________________________
> bitcoin-dev mailing list
> bitcoin-dev@lists.linuxfoundation.org
> https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
>

[-- Attachment #2: Type: text/html, Size: 4792 bytes --]