DahLIAS: Discrete Logarithm-Based Interactive Aggregate Signatures

[Jonas Nick]

Hi list,

Cross-Input Signature Aggregation (CISA) has been a recurring topic here, aiming
to reduce transaction sizes and verification cost [0]. Tim Ruffing, Yannick
Seurin and I recently published DahLIAS, the first interactive aggregate
signature scheme with constant-size signatures (64 bytes) compatible with
secp256k1.

https://eprint.iacr.org/2025/692.pdf

Recall that in an aggregate signature scheme, each signer contributes their own
message, which distinguishes it from multi- and threshold signatures, where all
signers sign the same message. This makes aggregate signature schemes the
natural cryptographic primitive for cross-input signature aggregation because
each transaction input typically requires signing a different message.

Previous candidates for constant-size aggregate signatures either:
- Required cryptographic assumptions quite different from the discrete logarithm
problem on secp256k1 currently used in Bitcoin signatures (e.g., groups with
efficient pairings).
- Were "folklore" constructions, lacking detailed descriptions and security
proofs.

Besides presenting DahLIAS, the paper provides a proof that a class of these
folklore constructions are indeed secure if the signer does _not_ use key
tweaking (e.g., no Taproot commitments or BIP 32 derivation). Moreover, we show
that there exists a concrete attack against a folklore aggregate signature
scheme derived from MuSig2 when key tweaking is used.

In contrast, DahLIAS is proven to be compatible with key tweaking. Moreover, it
requires two rounds of communication for signing, where the first round can be
run before the messages to be signed are known. Verification of DahLIAS
signatures is asymptotically twice as fast as half-aggregate Schnorr signatures
and as batch verification of individual Schnorr signatures.

We believe DahLIAS offers an attractive building block for a potential CISA
proposal and welcome any feedback or discussion.

Jonas Nick, Tim Ruffing, Yannick Seurin


[0] See, e.g., https://cisaresearch.org/ for a summary of various CISA
discussions.

[waxwing/ AdamISZ]

Hi Jonas and list.

So I'm reading the paper and it's very interesting. I have other questions but this one seems more important so I'll just stick with this one:

Appendix A2 explains an attack on Musig2-IAS, in which you can forge a partial signature on a tweaked key of the honest signer. I don't understand why this same attack cannot be applied to MuSig2 itself?

the multisig-to-IAS "translation" makes sense, given the caveat of the weakness identified in the 2018 paper and explained here in detail, other than that it's basically about the message being a concat of the individual messages (and keys). But surely that doesn't change the structure of the attack? (i.e. multiply your R-vals by a2/a1, then take partial sig and multiply by a2/a1 and add the tweak). I note that 3 round musig is not vulnerable to it, nor would some PoK of R be.

Obviously I missed something.

Cheers,

AdamISZ/waxwing

[Jonas Nick]

Thanks for bringing this up. It's an interesting question and it made us realize
that we should clarify this section of the paper, as there are indeed some
subtleties here that are currently unmentioned.

> I don't understand why this same attack cannot be applied to MuSig2 itself?

There are nuances, but I think it's fair to say that the same attack cannot be
applied to MuSig2 itself. During the attack, the adversary requests a partial
signature for public key X and message m from the honest signer. Using this, the
adversary is able to create a partial signature for public key X' = TweakPK(X,
t), where t is some tweak chosen by the adversary, and message m'. When applying
the attack to MuSig2, we have that m' = m, and when applying it to MuSig2-IAS,
we may have m != m'.

So, using the attack, the adversary is able to produce a signature sigma_1 for
MuSig2 and sigma_2 for MuSig2-IAS such that

- MuSig2.Verify(KeyAgg(X, X'), m, sigma_1) = 1, and
- MuSig2-IAS.Verify((X, m), (X', m'), sigma_2) = 1.

sigma_2 is clearly a forgery under the EUF-CMA-TK security model defined in the
DahLIAS paper because it is a signature for a message m' that the honest signer
hasn't signed. In contrast, sigma_1 only covers the message that the honest
signer actually signed. Whether sigma_1 counts as a forgery depends on the
abstract security notion that you consider for multisignature tweaking. We
didn't provide such a model in the MuSig2 paper and I am not aware of a standard
one. It would be easy to design a security model where sigma_1 constitutes a
forgery and one where it doesn't.

More importantly, could this be a problem for MuSig2 in practice? I can only
come up with contrived scenarios, but it may still be worth mentioning in the
BIP, for example.

[waxwing/ AdamISZ]

I'm struggling to understand one detail in DahLIA's algorithm: the use of R2 as a check and not R1 (or both). Is it just that only one is needed? Is it just an optimization?

Thanks,

AdamISZ/waxwing

On Thursday, April 17, 2025 at 10:38:46 AM UTC-6 Jonas Nick wrote:

[Jonas Nick]

Yes, just one is needed and this is an optimization. The signer does not require
every individual R1 value as input, only the R2 values. This is different to
MuSig2, where both R1 and R2 can be aggregated by the coordinator.

[waxwing/ AdamISZ]

Some comments/questions on the general structure of the scheme:

When I started thinking about ways to change the algorithm, I started to appreciate it more :) Although this algo is not specific to Bitcoin I'm viewing it 100% through that lens here. Some thoughts:

We want this CISA algorithm to have the property that it doesn't require the blockchain (and its verifiers) to incur linear cost in the number of signers/signatures. For a 100 input transaction, we get big gains from the owner or owners of the inputs choosing to use this algo, but that would mostly be lost if either the verifying was linear in the number, or if the size of the signature was linear in the number. So to avoid that we want a (R, s) structure to be actually published, not an (R1..Rn, s) or a (R, s1..sn). That pretty much forces us to make a sum R for all the individual component's R-values, and the same for s.

However it doesn't quite force us to add literally everything. The pubkeys *can* be kept separate, because they are retrieved implicitly from the existing blockchain record, they are not published with the signature (taproot). (Technically the same comment applies to the message being signed). This allows us to use the more "pedestrian", "safe" idea; we are not aggregating keys (as in MuSig) so we can actually add each with its own challenge hash: sum( challenge_hash_i * X_i). This may worry you that there is a performance issue because the verifier has to iterate through that whole list ( the verification equation being: sG =?= R + c_1 X_1 + c_2X_2 + .. ), but the paper specifically claims that comparing this with just batch verifying the individual signatures (i.e. without CISA), this is twice as fast.

So one could simplistically say "OK that's the pubkey side, they're treated individually so we don't have to worry about that, but what about adding the R values?" ("worry" here means: trivial key subtraction attacks or sophisticated Wagner/ROS grinding). And here what is done is basically the same as in MuSig2, which is to say, by breaking the nonce into two components and including an additional challenge hash, you prevent the counterparty/adversary from grinding R values successfully. Note that the "b" coefficient used here is more explicit about hashing the full context, than it was in MuSig2: it's hashing each individual pubkey and message as well as the R2 subcomponents for each party. This is vaguely similar to "client side validation" ideas: it's not really "validation" as in state updates, but it's having the more complex/expensive part of the calculation being done in the coordination before anything goes on-chain, and allowing us to just use a single "R" value onchain that we know is safe.

(Side note: it's worth remembering that a lot (maybe a huge majority?) of the usage of CISA will be a single signer of multiple inputs; for these cases there is not the same security arguments required, only that the final signature is not leaking the private key!).

That side note reminds me of my first question: would it not be appropriate to include a proof of the zero knowledgeness property of the scheme, and not only the soundness? I can kind of accept the answer "it's trivial" based on the structure of the partial sig components (s_k = r_k1 + br_k2 + c_k x_k) being "identical" to baseline Schnorr?

The side note also raises this point: would it be a good idea to explicitly write down ways in which the usage of the scheme/structure can, and cannot, be optimised for the single-party case? Intuitively it's "obvious" that you may be able to streamline it for the case where all operations happen on the same device, with a single owner of all the private keys. I realize that this is a thorny point, because we explicitly want to account for the corruption of parties that are "supposed" to be the same as the honest signer, but aren't.

And my last question is about this multi-component-nonce technique:

Did you consider the idea of e.g. sending proofs of knowledge of R along with R in the coordination step? This would keep the same number of rounds, and I'm assuming (though not sure exactly) that it makes the security proof significantly simpler, but my guess is you mostly dismiss such approaches as being too expensive for, say, constrained devices? (I imagine something like: 2 parties say, X1 sends (R1, pi_R1) and same for X2, to coordinator, then sum directly for overall R; here pi_R1 is ofc just a schnorr sig on r). If we're talking about bandwidth the current "ctx" object is already pretty large, right, because it contains all the pubkeys and all the messages (though in bitcoin they could be implicit perhaps).

(I won't mention the other idea, which is going back to MuSig1 style and just committing to R, because that's what both MuSig2 and FROST went away from, preferring fewer rounds.)

By the way after writing this overly long post I realised I didn't even get in to the really tricky part of the algorithm, the "check our key and message appears once" part because of the multisig-to-aggregated-sig transformation and the hole previously identified in it, which to be fair is the most interesting bit. Oh well, another time!

Cheers,

AdamISZ/waxwing

On Thursday, April 17, 2025 at 10:38:46 AM UTC-6 Jonas Nick wrote:

[waxwing/ AdamISZ]

On that last point about "proof of knowledge of R", I suddenly realised it's not a viable suggestion: of course it defends against key subtraction attacks, but does not defend at all against the ability to grind nonces adversarially in a Wagner type attack,  so that you could get a forgery on the victim's single key from a bunch of parallel signing sessions. So, question retracted, there.

[Jonas Nick]

Thanks for your comments.

> That side note reminds me of my first question: would it not be appropriate
> to include a proof of the zero knowledgeness property of the scheme, and
> not only the soundness? I can kind of accept the answer "it's trivial"
> based on the structure of the partial sig components (s_k = r_k1 + br_k2 +
> c_k x_k) being "identical" to baseline Schnorr?

That partial signatures do not leak information about the secret key x_k is
implied by the security theorem for DahLIAS: If information would leak, the
adversary could use that to win the unforgeability game. However, the adversary
doesn't win the game unless the adversary solves the DL problem or finds a
collision in hash function Hnon.

> The side note also raises this point: would it be a good idea to explicitly
> write down ways in which the usage of the scheme/structure can, and cannot,
> be optimised for the single-party case?

This is a very interesting point, probably out of scope for the paper. A
single-party signer, given secret keys xi, ..., xn for public keys X1, ..., Xn
can draw r at random, compute R := r*G and then set s := r + c1*x1 + ... +
cn*xn. So this would only require a single group multiplication.

> On that last point about "proof of knowledge of R", I suddenly realised
> it's not a viable suggestion: of course it defends against key subtraction
> attacks, but does not defend at all against the ability to grind nonces
> adversarially in a Wagner type attack

We believe Appendix B provides a helpful characterization of "Wagner-style"
vulnerabilities. Roughly speaking, it shows that schemes where the adversary can
ask the signer to produce a partial signature s = r + c*x or s' = r + c'*x such
that c != c' then the scheme is vulnerable. In your "proof of knowledge of R
idea", the adversary can choose to provide either R2 or R2' in a signing
request, which would result in the same "effective nonce" r being used be the
signer but different challenges c and c'.

[waxwing/ AdamISZ]

> That partial signatures do not leak information about the secret key x_k is
implied by the security theorem for DahLIAS: If information would leak, the
adversary could use that to win the unforgeability game. However, the adversary
doesn't win the game unless the adversary solves the DL problem or finds a

collision in hash function Hnon.

OK, so that's maybe a theoretical confusion on my part, I'm thinking of the HVZK property of the Schnorr ID scheme, which "kinda" carries over into the FS transformed version with a simulator (maybe? kinda?). Anyway this is a sidetrack and not relevant to the paper, so I'll stop on that.

> This is a very interesting point, probably out of scope for the paper. A
single-party signer, given secret keys xi, ..., xn for public keys X1, ..., Xn
can draw r at random, compute R := r*G and then set s := r + c1*x1 + ... +
cn*xn. So this would only require a single group multiplication.

I feel bad for saying so, but I absolutely do believe it's in scope of the paper :) If there is a concrete, meaningful optimisation that's both possible and sensible (and as you say, there is such an ultra-simple optimisation ... I guess that's entirely correct!), then it should be included there and not elsewhere. Why? Because it's exactly the kind of thing an engineer might want to do, but it's definitely not their place to make a judgement as to whether it's safe or not, given that these protocols are such a minefield. I'd say even if there is *no* such optimisation possible it's worth saying so.

I guess the counterargument is that it's suitable for a BIP not the paper? But I'd disagree, this isn't purely a bitcoin thing.

On the third paragraph, yeah, as per earlier email, I realised that that just doesn't work.

[waxwing/ AdamISZ]

On the very important argument laid out in Appendix B:

(for readers, this part of the paper deals with this problem: if the scheme can allow a scenario where the output "effective nonce" of an honest signer is the same for two different contexts and thus have two difference signature hashes (in DahLIAS the sighash is H(L, R, X_i, m_i)), then with some deft mathematical footwork, we can extract a forgery on some other message by that signer, as long as we can do a bunch of parallel signing sessions; you can think of this as a sophisticated extension of the fundamental idea of "nonce reuse is insecure").

... I find myself stepping back through the arguments for this structure R1 + bR2 in MuSig2. In that case, it is vital that we end with a verification that looks like : sG =?= R + H(R,P,m)P, precisely, because we need MuSig2 verification to be indistinguishable from single-key Schnorr verification.

In DahLIAS we have (obviously, reasonably) relaxed that restriction. The verification now allows for multiple pubkeys and messages to be inputs; that's the whole point, we're publically verifying authorization of a bunch of (pubkey, message) pairs, so it would be incoherent or at least unnecessary to *require* some kind of aggregate pubkey as input. (though as the paper discussed, you can *try* to build the IAS from an IMS, which would mean actually doing that, but as demonstrated, it doesn't really seem to work, anyway).

So when we look at the R component, which, distinct from the pubkeys, *must actually be published*, we do need to have an aggregated R value (to get a short signature), so at the end, we publish (R, s) and can do a verification with the implied pubkey message pairs ((P1, m1), (P2, m2),..) like: sG =?= R + sigma (sighash(Pn,mn) * Pn).

So here's my question: why does the signing context, represented by "b", in the aggregate R-value, need to be a fixed value across signing indices? Clearly if we have one b-value, H-non(ctx), where ctx is ((P1, m1), (P2, m2),..) [1], then it is easy to sum all the R1,i = R1 and then sum all the R2,i values = R2 and then R = R1 + bR2, exploiting the linearity. But why do we have to? If coefficient b were different per participant, i.e. b_i = H(ctx, m_i, P_i) then it makes that sum "harder" but still trivial for all participants to create/calculate. All participants can still agree on the correct aggregate "R" before making their second stage output s_i.

If I am right that that is possible, then the gain is clear (I claim!): the attacks previously described, involving "attacker uses same key with different message" fail. The first thing I'd note is that the basic thwarting of ROS/Wagner style attacks still exists, because the b_i values still include the whole context, meaning grinding your nonce doesn't allow you to control the victim's effective nonce. But because in this case, you cannot create scenarios like in Appendix B, i.e. in the notation there:

F(X1, m1(0), out1, ctx) = F(X1, m1(1), out1, ctx) is no longer true because b no longer only depends on global ctx, but also on m1 (b_1 = Hnon(ctx, m1, P1) is my proposal),

then the "Property 3" does not apply and so (maybe? I haven't thought it through properly) the duplication checks as currently described, would not be needed.

I feel like this alternate version is more intuitive: I see it as analogous to (though not the same) as Fiat-Shamir hashing, where the main idea is to fix the actual context of the proof; but the context of *my* partial signature for this aggregate, is not only ((P1, m1), (P2, m2),..) but also my particular entry in that list.

[1] Here I am ignoring that actual DahLIAS uses ctx including R2 values because I understand that that is part of the checking procedure that I am (somewhat vaguely) here trying to argue might be omitted.

Cheers,
AdamISZ/waxwing

[Tim Ruffing]

First of all, again great to see that you look so carefully at the
paper.

Your observation is right: If each participant has a distinct b_i as
you've sketched, then the duplicate checks can be omitted. And I tend
to agree that this is more natural scheme. In fact, this is where we
started, and we had a security proof of this (though without tweaking
worked out) in an earlier unpublished draft of the paper, and only
afterwards we found a scheme with a single b.

The reason we why prefer the scheme with a single b is simply
efficiency. The current signing protocol needs 3 group exponentiations
(i.e., scalar-point multiplications). With separate b values, one of
those becomes a multi-exponentiation of size n-1, which is much slower
and needs O(n/log n) time instead of O(1).

Another, very minor and optional efficiency benefit is that the
coordinator can take care of the computation of the final R2 and send
it to the participants. (But that's really minor, because the
coordinator needs to send the individual R_{2,i} values anyway.)

Intuitively, we manage to get away with a single b by (ab)using the R_i
values as ephemeral identifiers for the participants, which makes it
possible to distinguish them even if they happen to have the same
public key (or, in other words, if it's the same participant that joins
the session more than once). This is why we need the uniqueness check,
to make sure that the identifiers are unique.

And yes, the uniqueness check looks a bit strange at first glance, but
(as the proof shows) there should be nothing wrong with it. One could
argue that the uniqueness check is a potential footgun in practice
because an implementation could omit it by accident, and would still
"work" and produce signatures. But we find this not really convincing
because it's possible to create a failing test vector for this case.

We didn't talk about identifying disruptive participants in the paper
at all, but one could also argue that the uniqueness check creates a
problem if the honest participants want to figure out who disrupted a
session: if malicious participant i copies from honest participant j,
then how the others tell who of them to exclude?

But if you think about it, that's not a real issue. In any case,
identifying disruptive participants will work reliably only if the
coordinator is honest, so let's assume this. And then, if additionally
the participants have secure channels to the coordinator, then no
malicious can steal the R_{2,j} of an honest participant j. So, if the
coordinator sees that R_{2,i} = R_{2,j}, the right conclusion is that
they are colluding and both malicious.

[waxwing/ AdamISZ]

Hi Tim, answers inline:

> Your observation is right: If each participant has a distinct b_i as
you've sketched, then the duplicate checks can be omitted. And I tend
to agree that this is more natural scheme. In fact, this is where we
started, and we had a security proof of this (though without tweaking
worked out) in an earlier unpublished draft of the paper, and only
afterwards we found a scheme with a single b.

I see. Funnily enough, the day after I posted "my idea" I saw that ~ the same thing exists in the original FROST paper!

> The reason we why prefer the scheme with a single b is simply
efficiency. The current signing protocol needs 3 group exponentiations
(i.e., scalar-point multiplications). With separate b values, one of
those becomes a multi-exponentiation of size n-1, which is much slower
and needs O(n/log n) time instead of O(1).

OK. I can see where the count of 3 comes from and, indeed, we would need a multiexponentiation in signing, here. But, we already need one in verifying.

So we'd be going from from O(1) sign, O(n/logn) verify to O(n/logn) sign, O(n/logn) verify. As per table 1, the only one that's better than that while being unrestricted is BN06, but that isn't a 2 round scheme.

My initial reaction would be, since it's not worsening the scaling of the verifier, does it matter? And *if* this were only for Bitcoin, then also because n is limited in that context with some upper bound (in the hundreds I think). A multiexp in signing for 100 inputs with n/logn scaling seems like it wouldn't be an issue since, after all, we are assuming we can do it in transaction verification. Signers being more constrained than verifiers doesn't seem realistic; am I missing something there? (hardware signing devices perhaps? is that an actual concern, given signers have so much more time than verifiers? perhaps Lightning-like protocols (though not LN itself I think)?)

The scheme is explicitly not limited to Bitcoin, nor blockchains, though, so there's that; is that relevant here?

> And yes, the uniqueness check looks a bit strange at first glance, but
(as the proof shows) there should be nothing wrong with it. One could
argue that the uniqueness check is a potential footgun in practice
because an implementation could omit it by accident, and would still
"work" and produce signatures. But we find this not really convincing
because it's possible to create a failing test vector for this case.

Yes, the footgun you point to in Section 4.2 is the very plausible one, but indeed, a test vector could alleviate that.

Yes, I have no concrete suggestion for now as to how this style of algorithm with comparative checking instead of being algebraic may cause a problem; I just find it suspicious ... but, to continue on that thought;

> We didn't talk about identifying disruptive participants in the paper
at all, but one could also argue that the uniqueness check creates a
problem if the honest participants want to figure out who disrupted a
session: if malicious participant i copies from honest participant j,
then how the others tell who of them to exclude? 

> But if you think about it, that's not a real issue. In any case,
identifying disruptive participants will work reliably only if the
coordinator is honest, so let's assume this. And then, if additionally
the participants have secure channels to the coordinator, then no
malicious can steal the R_{2,j} of an honest participant j. So, if the
coordinator sees that R_{2,i} = R_{2,j}, the right conclusion is that
they are colluding and both malicious.

Yes, those are some interesting points to consider. On one detail: "In any case, identifying disruptive participants will work reliably only if the
coordinator is honest, so let's assume this." -- this could also be addressed with proofs of knowledge, no?

Anyway, for me it was more a sort of preference for purely algebraic algorithms. It's a little fanciful, but algebraic algorithms are easier to encode in circuits in zero knowledge (though things like equality checks are entirely doable ofc!) and maybe easier to "encode" into modular schemes that use them as a building block. Maybe. Less conditional branches / loops to traverse in the code? And/or you could wave your hands and just say they "feel cleaner", or are easier to reason about.

As for finding a concrete problem with the equality checks, I have not. At least not yet.

Cheers,

AdamISZ/waxwing

[Jonas Nick]

Hi waxwing,

Thanks again for your comments.

> My initial reaction would be, since it's not worsening the scaling of the
> verifier, does it matter?

I think saving time in signing does matter (3 group exponentiations requiring
O(1) group operations in total vs. O(n/log n) group operations); for example, in
constrained signing devices as you mention. In particular, the "single-b"
variant with the larger signing cost doesn't appear to have advantages (see
below) compared to "multi-b" which has lower signing cost.

> The scheme is explicitly not limited to Bitcoin, nor blockchains, though,
> so there's that; is that relevant here?

The scheme is not limited to Bitcoin, but the main application we designed for
is Bitcoin. I agree that verification performance is of primary importance. We
would choose a scheme with lower signing performance, if it gives us a better
verification performance in return (if the trade-off is reasonable).

> Yes, those are some interesting points to consider. On one detail: "In any
> case, identifying disruptive participants will work reliably only if the
> coordinator is honest, so let's assume this." -- this could also be addressed
> with proofs of knowledge, no?

Maybe I misunderstand what you're getting at, but I don't understand how proofs
of knowledge would get rid of the honest coordinator requirement for identifying
disruptive signers. Moreover, both R_{2,i} and R_{2,j} could have a valid proof
of knowledge attached (for example, if parties i and j share the dlog of R_{2,i}
= R_{2,j}).

> Anyway, for me it was more a sort of preference for purely algebraic
> algorithms. It's a little fanciful, but algebraic algorithms are easier to
> encode in circuits in zero knowledge (though things like equality checks are
> entirely doable ofc!) and maybe easier to "encode" into modular schemes that
> use them as a building block. Maybe. Less conditional branches / loops to
> traverse in the code?

Why exactly would it be easier to encode the multi-b variant in a circuit? The
single-b variant requires checking whether there exists i such that R_{2,i}
matches a fixed R_{2,j}. In the multi-b variant we'd need to compute the product
of all R_{2,i}^{b_i}, which, even with a multiexp implementation, requires at
least visiting all elements plus the actual multiexponentiation involving
O(n/log n) group operations. So encoding the single-b variant appears to be
strictly easier.