BIP459: DahLIAS fully aggregated signatures for secp256k1 #2210

This is a BIP draft for creating Schnorr-style Full Aggregate signatures, a standard for the DahLIAS scheme by Jonas Nick, Tim Ruffing, and Yannick Seurin. It complements BIP458 half-aggregation. Full-aggregation results in a constant 64-byte signature but requires an interactive signing protocol.

Compared to the version shared on the mailing list recently, this version incorporates waxwing's feedback from the thread, most notably:

1. More info on the uniqueness check in Sign and new test vectors covering this and other checks
2. A description of the deterministic nonce attack
3. Clarifications on the security model and other language improvements for clarity

The reference implementation is written in Python based on secp256k1lab, and the latest master of secp256k1lab is vendored with the BIP, same as it was done for BIP458.

I had asked BIP editors to reserve 459 for this so the CISA related BIPs can be in consecutive order, but I didn't want to cause confusion as it might have looked like self-assigment if had just pushed it with the number. So waiting for a confirmation for the number :)

Yes, 459 was reserved for Full-Aggregation of BIP340 Signatures.

One imprecision here that I am grappling with: While this says "Full-Aggregation of BIP340 Signatures" technically this doesn't aggregate BIP340 signatures like half-agg does because there is never an actual BIP340 signature created. Rather, there could have been a BIP 340 signature in its place instead, and this builds on Schnorr which is tied to BIP340 in the Bitcoin context. Expressing that more correctly felt like bending over backwards when I tried and might have caused more confusion that clarity. But I wanted to make clear that I am aware of this and happy to take suggestions for changes if people think this improves the BIP.

About the Nonce Generation warning on deterministic signatures:

related to my earlier comments on the list and elsewhere, about 'what if there is a folklore "acceptably secure" single-owner aggregation that doesn't follow the DahLIAS protocol', how about this one: suppose a user does use RFC6979-style deterministic nonce-generation, reasoning "well, the attack is only if I'm signing with someone else, but I'm not". You might reasonably retort: but it specifically says under "Nonce generation" that it 'MUST NOT BE USED' and references active attackers, but I'd counter that the explanatory footnote refers specifically to co-signers as the threat; so a person may read that and think "I have no co-signers, no risk".

There is at least one case where it could leak keys: if you sign with ACP, and you are convinced by external actions to, say, do RBF or "redo" the transaction elsewise, you could end up using the same nonce for different challenges.

Apologies if this is too much like pedantry; I am less looking at it from the angle of "is this protocol correct?" and more from the angle of "what stupid, but plausible, thing are people likely to do?". With MuSig2 I feel like it's less of an issue (though of course people certainly can shoot themselves in the foot!), I am thinking of smaller wallet developers looking for the "I can give my users cheaper transactions!" angle, but who don't understand the deeper/subtler parts of what's going on here.

While this says "Full-Aggregation of BIP340 Signatures" technically this doesn't aggregate BIP340 signatures like half-agg does

Yeah, I agree that this is confusing. Technically, it doesn't aggregate any signatures (at most partial signatures). This is a property that sets this apart from the half-agg BIP. So if these proposals are very different, it's okay (or even good) to have very different titles.

Some suggestions in decreasing order of preference

• "Full Aggregate Schnorr-style Signatures"
• "Full Aggregate BIP340-style Signatures" (not that wrong, but if you ask me, I'd still avoid BIP340).
• "Full Aggregate Signatures on secp256k1"
• "Interactive Aggregate Signatures on secp256k1" (again not wrong, but I think the half/full terms are well established in the community)
• "DahLIAS on secp256k1" (doesn't tell you anything)

(I'm trying to avoid if this should be "Full-Aggregate" or even "Fully Aggregate" instead... Let's leave that to a native speaker. Or an LLM.:D)

Pushed a few more changes:

• Renamed the BIP per @real-or-random 's suggestion and made further edits to avoid the "aggregate bip340 signatures" statement
• Changed the license per the comment here: #2205 (review)
• Added some extra details to the nonce gen part to address @AdamISZ 's comment: #2210 (comment)

Thanks a lot for the feedback!

On the title, yeah it's a tricky one. BIP340's title is similar to some of @real-or-random 's suggestions (and is the closest match, maybe) while BIP 327 has "MuSig2 for BIP340-compatible Multi-Signatures". As noted, "BIP340 compatible" can't be cross-applied here. While note that BIP327 does use the name of the scheme. Hence I'm not sure why @real-or-random dismisses "DahLIAS" as not conveying information; arguably that is the most specific, pertinent information (the actual scheme/protocol). Though I infer your meaning as: higher-level reader is not going to know what that term means. But the same could be said of "MuSig2". The thing that I think I would want the skim-reader to know is "this is a completely new (and therefore consensus changing in usage) type of bitcoin signing, using a new aggregation protocol". The niceties of it being Schnorr-like at the deeper conceptual, structural level I guess are not massively important. I'd be tempted by "DahLIAS aggregated signatures for bitcoin" or something like that (I was thinking that 'for bitcoin transactions' or 'for cross-input signature aggregation' are wrong because that's not this BIP, that's the other one).

Though I don't think @real-or-random 's "DahLIAS for secp256k1" is wrong either (as he seems to :) ), mirroring the BIP340 title. I suppose that might depend on whether there is a foreseen usage of this protocol outside of bitcoin consensus.

"DahLIAS aggregated signatures for bitcoin"

You are making good points @AdamISZ but I think the "for bitcoin" part is redundant given that we are in the BIPs repo here where everything should be specified for bitcoin to some degree. Otherwise I would be fine with adopting this name as well, but I do think there could be some minor confusion for casual readers since "full-agg" is kind of established as the casual, conversational name for what the BIP specifies.

Hence I'm not sure why @real-or-random dismisses "DahLIAS" as not conveying information; arguably that is the most specific, pertinent information (the actual scheme/protocol). Though I infer your meaning as: higher-level reader is not going to know what that term means.

Right! that's what I had in mind. If you don't know what DahLIAS is, then you have idea what this is about.

But the same could be said of "MuSig2".

Hm, in principle that's true, but if I remember correctly the term MuSig was floating in the community already for a while. Whereas (due to the lack of a concrete scheme), the most common term floating around for what this BIP proposes was "full aggregation", so I think it's nice to have this (or a variant of it) in the title.

The thing that I think I would want the skim-reader to know is "this is a completely new (and therefore consensus changing in usage) type of bitcoin signing, using a new aggregation protocol". The niceties of it being Schnorr-like at the deeper conceptual, structural level I guess are not massively important.

I tend to agree. The fact that this is not compatible to Schnorr is important (though the actual consensus change is proposed in the other BIP). Maybe my proposal of stressing the similarity to Schnorr comes from my cryptographer bias. But what should be made clear somehow is that this is EC-based (i.e., not post-quantum).

I'd be tempted by "DahLIAS aggregated signatures for bitcoin" or something like that (I was thinking that 'for bitcoin transactions' or 'for cross-input signature aggregation' are wrong because that's not this BIP, that's the other one).

Though I don't think @real-or-random 's "DahLIAS for secp256k1" is wrong either (as he seems to :) ), mirroring the BIP340 title. I suppose that might depend on whether there is a foreseen usage of this protocol outside of bitcoin consensus.

What about "DahLIAS fully aggregated signatures for secp256k1" (or "... on secp256k1")?

This ticks all the boxes for me:

• Mentions DahLIAS instead of Schnorr explicitly. (It mentions the new term DahLIAS and doesn't mention Schnorr which could be mistaken to imply compatibility to the existing Bitcoin network.)
• Mentions the known term "full aggregation".
• Mentions secp256k1, which stresses that it's EC-based.
• Doesn't mention that intended uses would change consensus (and that makes sense because it's in the other BIP).
• Still reasonably concise

What about "DahLIAS fully aggregated signatures for secp256k1" (or "... on secp256k1")?

Sounds good to me but I will wait for @AdamISZ 's feedback this time ;) Double-checked that this is under the 50-character limit, which it is at 49 :D

Great, I agree with "DahLIAS fully aggregated signatures for secp256k1" . Noted and agreed @fjahr about the 'fully' part, I wasn't considering that, but it's important here.

Renamed to "DahLIAS fully aggregated signatures for secp256k1". Thanks a lot for hashing this out @real-or-random and @AdamISZ !