BIP draft: CISA for Taproot Key Path Spends

[Fabian]

Hi list,

I would like to share a BIP draft for transaction-wide cross-input

signature aggregation (CISA). It introduces a new witness version,

which enables Taproot-style key path spending where inputs can

aggregate their signatures.

Each input chooses between half-aggregation, full-aggregation, or an

explicit opt-out via a marker byte in its witness.

The aggregation schemes themselves are specified in the previously

shared BIP 458 (half-aggregation) and BIP 459 (full-aggregation)

drafts. Script path spending follows BIP 341/342 unchanged.

The BIP draft text can be found here:

https://github.com/fjahr/bips/blob/cf0d4f2142cd0504b16e86739167b1f7ab9a3a06/bip-XXXX.mediawiki

For inline comments, I have opened a mock pull request on my BIPs

repo fork:

https://github.com/fjahr/bips/pull/6

Feedback of any kind is much appreciated.

Best,

Fabian

[conduition]

Sending this again because I think the first time didn't work.

Thanks Fabian, this is very cool. I haven't read the entire BIP in detail yet, but first thing I notice on a quick skim is that reserving segwit version 2 conflicts with BIP-360 which proposes to use the same.

I'm particularly interested in how to dovetail this proposal with PQ migration efforts. I have two questions:

1. Can the framework you use for verifying aggregated sigs be generalized to support future aggregated PQ signatures in the future? (assuming we someday have a PQ sig algorithm that admits aggregation) 
   

2. How do you see this proposal mixing with BIP360? The major hurdle I see is that your proposed output type puts a bare EC pubkey on-chain in the script-pubkey. Unfortunately Boris' EC recovery trick does not seem to work in this context: Because signatures are aggregated we can't recover pubkeys, so we can't hide them behind a hash. We either have to put them in the SPK, or the witness. So at face value, it seems there are two options:

1. Couple CISA tightly with P2TRv2. On one hand this would be good because it would provide a concrete incentive for users to migrate to a wallet that supports PQC. This also seems like the easier option from an engineering perspective. However it comes with all the baggage of P2TRv2 (not actually quantum-safe by default, need to solve the Q-day timing problem).
2. Hide the EC pubkeys behind a hash in the SPK (e.g. P2MR or P2TRH), and attach the EC pubkey in the witness of every aggregated TX input, so that the verifier can run the aggregated sig-verify algorithms. This would be more secure and relaxes the Q-day timing constraints, but we don't get as much relative savings. 

Napkin math of the witness weight of an aggregated input, assuming full-aggregation is used:

• with P2TRv2:
• 1 byte for the marker
• total: 1 byte
• with P2TRH:
• 1 byte for the marker
• 32 bytes for the EC pubkey
• total: 33 weight units
• with P2MR:
• 1 byte for the marker (witness)
• 32 bytes for the merkle sibling node (witness)
• 32 bytes for the EC pubkey (witness)
• total: 65 weight units

regards,

conduition

--
You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+...@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/Qc_VmkfXgE8KHBfUnUB-hdWF1QOYv6zshzI7WEv_hvqJ6O_4zssJ4X2T2Di79I3TqHQvRDXsFtD8os5M44wrbB61M1LD_-GDRGYEagoHsV4%3D%40protonmail.com.

[Fabian]

Hi conduition,

Thanks a lot for checking out the proposal and raising those

questions!

One caveat up front: I have not spent much time on the PQ side of

things yet, so I can not give you a very serious answer on those parts

and I do not want to make strong claims here. But I am interested to

invest more time there now that the proposal is published and explore

how it can be adapted for different PQ scenarios.

> reserving segwit version 2 conflicts with BIP-360 which proposes to
> use the same.

Right, this was pointed out in an inline comment as well, please see my

answer there:

https://github.com/fjahr/bips/pull/6#discussion_r3609171527

> 1. Can the framework you use for verifying aggregated sigs be

> generalized to support future aggregated PQ signatures in the future?

I would expect that the transaction-level structure should generalize:

the markers, the mode commitment in the signature message, the group

formation, and the final input carrying the aggregate should not care

which scheme is used (again, take it with a grain of salt since I have not

studied any PQ schemes in real depth). We would still need a new witness

version but there would be need for a new output type anyway in this

scenario, I guess. I certainly hope in any scenario that the framework

and related learnings will be useful in a PQ world as well.

> 2. How do you see this proposal mixing with BIP360?

I do not have a concrete good answer here yet. The trade-off you describe

is certainly real: aggregation needs all public keys as input to verification,

so hiding them costs 32 bytes per input which halves full-agg savings

and makes half-agg ~useless. This proposal deliberately picks the

taproot security model, bare keys give us maximum savings. If

P2TRv2 materializes as the migration output type, I could see CISA

certainly being defined on top of it. The witness rules here should carry

over and since script path spending follows BIP 341/342 unchanged,

committing PQ fallback leaves would work the same way as proposed

there. That definitely seems worth exploring.

A hash-hidden variant like your option b should be possible within the

same framework. This could be specified as its own output type if the

ecosystem likes this trade-off and I think that is a very interesting idea to

explore. Both outputs types could coexist and users could pick based on

their quantum fear index while the implementation would share most of

the logic/code. Even shared aggregation groups seem possible cleanly

if we add them to this proposal, but this likely wouldn't be great for

CoinJoin privacy guarantees. 

But I think even the proposal as-is can provide a lot of value in many

conceivable scenarios of CRQC arrival and I think you were hinting at this

with the migration argument as well. If the network, for example, comes

to consensus that CRQCs will arrive in 1-2 years and a PQ scheme is about

to be deployed, which will be bigger and more expensive than BIP340, we

should see a lot of demand for consolidation and CoinJoins and having

CISA availability would provide a nice (though temporary) effect. But of course

this is also limited to the coins that have moved already by that time.

Best,

Fabian

To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/IrJGniZYNo7x0fr4wABg7SsdqJoJWs5yozmiFLGzJkxOwtHU01_O8swpJMKVi_uEkdqAfFUTELpOTja53HCrgmBgQBFYup1NQ4LCZHMRcFQ%3D%40proton.me.

[waxwing/ AdamISZ]

Hi Fabian,

Thanks again for the draft.

"A more flexible alternative with multiple aggregation groups per scheme, similar to the bucket concept from early aggregation discussions, was rejected because no concrete use case justified the additional validation complexity."

Say  a bunch of people want maximally weight-minimising transaction (for their consolidation), but don't want to run a collaborative scheme between each other because it's technically hard to do safely (constrained hardware/software, nonce state handling, etc.). Each of them just want to full agg their 10 inputs, each.

Not saying it's some super-common-in-practice scenario, but it seems suboptimal that you can't do it. So ... I guess it depends on whether "the additional validation complexity" is really bad compared with the utility of that specific use case.

More specifically, though, why couldn't a 'group ID' be folded into the marker byte. In your draft you say  "The chosen values fall into the range 0xbb to 0xfe, which is unassigned in legacy script and corresponds to OP_SUCCESS opcodes in tapscript, so they do not collide with opcodes commonly seen in scripts." - but there are a lot of values between 0xbd and 0xfe. I guess this is not a case for bitflags, but just different markers  where you add a groupID to 0xbd (and with the understanding - this clearly is only relevant for fullagg, not halfagg). Is this just out of consideration for some other reason that (hardly surprising) I'm not aware of?

(I don't believe this suggestion changes anything functionally as described in the 'Common Signature Message' section; I mean it literally changes the byte, but, functionally).

A negative (for privacy specifically) would be that you tag the different groups in the input list.

While that as a proposal may or may not be a good one, I feel like: this is worth mentioning at this time because (IIUC) it cannot be retrofitted in after.

Cheers,

AdamISZ/waxwing

[Fabian]

Hi waxwing,

Thanks again for sharing your feedback! The idea of

incrementing the marker byte with a group ID is clever

and I agree that it works technically. This triggered

me to spend some more time to think about what that

might look like which is fun but I am still not

fully convinced this is worth adding.

> Say a bunch of people want maximally weight-minimising

> transaction (for their consolidation), but don't want to

> run a collaborative scheme between each other because

> it's technically hard to do safely (constrained

> hardware/software, nonce state handling, etc.). Each of

> them just want to full agg their 10 inputs, each.

You may have already had this in mind but to make sure

we are on the same page: In this scenario the parties do

not become fully independent of each other. With sighash

default (or all) every signature commits to all outputs,

so all parties have to agree on the complete output list

of the transaction before anyone can sign. Only the

signing session itself is avoided. It is hard for me to

imagine a scenario where that kind of up-front

coordination is fine but the signing session isn't. It

would require some kind of communication and holding of

state as well. Please let me know if you think

differently here. I am not sure what your assumptions

are around up-front coordination capabilities.

I also looked into decoupling the parties further but

it does not really work in my opinion. SINGLE with

ANYONECANPAY only fits parties with one input and one

output each, the consolidation example has no outputs that

the other 9 inputs could safely commit to. When this does

fit, it reveals which input pays which output, and since

nothing commits to the other groups, anyone can split the

merged transaction apart. The explicit sighash bytes

also cost one extra weight unit per input, while

separate transactions can omit the byte by using the

default.

> Not saying it's some super-common-in-practice scenario,

> but it seems suboptimal that you can't do it. So ... I

> guess it depends on whether "the additional validation

> complexity" is really bad compared with the utility of

> that specific use case.

The utility seems limited because of the minor additional

savings they gain from this. They can use half-aggregation

within the shared transaction, but probably better for a

scenario as you outline, each party just broadcasts its

own transaction with its own full-aggregation group. The

latter has about 10 vbytes of transaction overhead and

both alternatives lose all the coordination requirements.

However, we could take the multi-full-agg-group concept

to the next level and half-agg the full-agg signatures

of the different groups for another round of savings (as

well as additional complexity of course).

So, back of the envelope multi-full-agg-group steelman

calculation for your scenario: 10 participants each

consolidating 10 inputs into 1 output.

Each in their own tx:

  10 x input skeleton                        1640 WU

  9 placeholders + 1 final (27 + 67)           94 WU

  1 output                                    172 WU

  tx skeleton                                  42 WU

  total                             1948 WU (487 vb)

All in one shared tx with half-agg on top:

  10 x input skeleton                        1640 WU

  9 placeholders + 1 R-only final (27 + 35)    62 WU

  1 output                                    172 WU

  share of combined s (32 / 10)               3.2 WU

  share of tx skeleton (42 / 10)              4.2 WU

  total                             1881 WU (470 vb)

So this takes it up to 17 vbytes, or 3.4% savings per

participant/group. I didn't fully sketch this out but

I think it should be possible without introducing

additional overhead.

I start to warm up to it because it's clever but I am

not sure if that is a good thing ;)

> More specifically, though, why couldn't a 'group ID' be

> folded into the marker byte.

[...]

> Is this just out of consideration for some other reason

> that (hardly surprising) I'm not aware of?

Yepp, this works just like you describe. The reason is

only that I do not see a real use case justifying it and

I even feel like the sighash constraints make reasonable

use-cases hard to imagine.

> A negative (for privacy specifically) would be that you

> tag the different groups in the input list.

Right, the group numbers would reveal which inputs

belong together. But for your consolidation scenario this

seems like a minor issue and it's not that different from

potential finger printing issues resulting from unique

mixing of different aggregation types in a transaction.

I already have some fingerprinting warnings in the BIP to

make people aware of this.

> While that as a proposal may or may not be a good one, I

> feel like: this is worth mentioning at this time because

> (IIUC) it cannot be retrofitted in after.

Yes, undefined marker values cannot become valid through

a soft fork, I thought about something like this early on

trying to find potential upgrade paths. But this doesn't

seem possible and it's good to have this conversation now.

Thank you again for raising this. I have expanded the

rationale section in the BIP with my reasoning so

that the decision is better documented. I am also

still open to think about other potentially interesting

use-cases for the multi-group-full-agg feature or to

reconsider if you or other reviewers think we should rather

be maximimally flexible in this regard even without a clear

use-case. But unless there is interest being signalled
I will err on the side of simplicity.

Best,

Fabian

--

You received this message because you are subscribed to the Google Groups "Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+...@googlegroups.com.

To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/74cecbeb-94d1-4181-9caa-3f60c54d6b08n%40googlegroups.com.