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