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 !

I think there might be more to the List Ordering aspect than I had in mind originally. Maybe?

Is it worth specifying that in doing the Sign' step, one actually sanity checks the full list of (Xj,mj) values extracted from ctx? Because with a coordinator that's untrusted, they could simply provide a different list and therefore different L that happens to pass the unique-entry check.

It's a weird thing to talk about, I realize; one doesn't write 'check that the m-value you're signing is your actual message', either in single sig or multisig. It's part of the setup that you choose a message. In this aggregation scenario, we have the co-EUF-CMA game which expands 'chosen message attack' to 'chosen keys and messages list attack'. So now the 'list of keys and messages' is taking the place of what previously was just a single message, so you could reasonably slot that in and say 'well obviously I'm not signing if that list is wrong', but there is a nuance if you now use a coordinator, read that list from him, as opposed to reading it yourself from some setup state, and the spec specifically says 'check your entry in that list' - it might be inferred that you don't care what else is in the list (and perhaps in some circumstances, you don't, but in others you do).

As you noted:

In many applications, the signers already know the list of public keys and messages before the signing session starts and only the aggnonce and individual public nonces need to be communicated.

... in these cases my comment doesn't apply, clearly. One case where it could apply might be a spontaneously coordinated big coinjoin or batching. But then, since 459 is the sig scheme not the bitcoin specific part, we should be looking in general, not only at these applications.

Also in the paper they do write:

Yet another option would be to change the syntax so that Coord only takes the list of signers’ first-round outputs (R1,i,R2,i), but not the public keys and messages. The coordinator would simply compute R1 and R2 and output ctx = (R1,R2,(R2,i)i∈[n]). Then, we would also need to change Sign′ so that it takes public keys and messages of cosigners, but the question then is how each signer can link the values R2,j in the session context ctx and the cosigners’ pk/message pairs. It seems like it would require a unique id per signer, something that would be inconvenient and that our scheme avoids: packing Xi, mi, and R2,i in a single triple is the task of the coordinator.

So I guess there are several, reasonable, slight variants. My only concern is that, coming from the Spec section of the paper, there's a hole that someone might miss and just accept any list that passes the uniqueness check, and go ahead and merrily sign.

(if there is something to edit here, might want to look at 'Signer verification checks' under Security, too).

Another detail worthy of consideration, I think, is that such checks are not EC operations, so not a concern even on constrained devices, right.

Yes, co-EUF-CMA gives you the guarantee that if you don't agree with what else is list, you can securely refuse to sign.

and the spec specifically says 'check your entry in that list' - it might be inferred that you don't care what else is in the list (and perhaps in some circumstances, you don't, but in others you do).

Yeah, the fact that you may care in some circumstances but not in all makes it particularly subtle to explain.

As you point out, Sign in the spec gets m explicitly and can perform the check. But it doesn't get any other entry explicitly.

I currently don't see a better way than explaining this in detail. The caller needs to check any condition in the list they would like to hold true (e.g., if they want some other pk_i to sign m_i, they need to check this).

The only check that the scheme does for them is that their own pubkey signs m. We could even push this check to the user, but I don't think that's a great idea. Doing so would make the thing conceptually simpler, but it would introduce a footgun even for those callers who don't care about the rest of the list.

Thanks @AdamISZ and @real-or-random, makes sense to spell this out. In this push I have added notes to both the Sign section and in Security, clarifying that Sign only checks the signer's own entry and that any requirement on the rest of the list must be checked by the caller before signing.