Re: [bitcoindev] Re: DahLIAS: Discrete Logarithm-Based Interactive Aggregate Signatures

[waxwing/ AdamISZ <ekaggata@gmail.com>]

[-- Attachment #1.1: Type: text/plain, Size: 5542 bytes --]

A couple of other minor comments:

On list ordering, I was tempted to write "why not include a default 
ordering algorithm", but ... I can see why that's not worth bothering with, 
since the design includes the untrusted coordinator role, so in that sense 
it really doesn't matter.

Security argument: the paper's security claim is a reduction to the 
algebraic variant of the one-more-discrete-log assumption under the random 
oracle model for the hash_sig (AOMDL under ROM). Obviously there's only so 
much to be written there, but following on from BIP340 and BIP327 I think 
it's reasonable to briefly describe the security claim somewhere, and what 
its kind of "ancestry" is. As there, pointing out that AOMDL is a weaker 
(better) assumption is probably worth mentioning. You could also add a 
note, though it's unlikely any BIP reader would be confused about this 
point, that the scheme is *not* intended to be post-quantum secure.

(Is it worth mentioning the co-EUF-CMA definition here? Perhaps in a 
footnote? While it's both in the weeds, and also has no direct implication 
for implementation, it nicely shows why the technical problem to solve here 
is different from what the paper calls "IMS" vs "IAS".)

About nonce gen: this is obviously a tricky but hugely important point, 
just as it was for BIP327. The first comment I want to make is, why do you 
link 
to https://medium.com/blockstream/musig-dn-schnorr-multisignatures-with-verifiably-deterministic-nonces-27424b5df9d6#e3b6 
in the section where you're saying "don't use deterministic nonce 
generation"? The main point of that blog post is to show a way that that 
*can* done in MuSig2, even though, by default, it's insecure. But aren't 
you mainly trying to point out that, as in BIP327, in this BIP, we don't 
have security with deterministic nonces? (rather than making a Musig-DN 
recommendation)?

(Hmm, I guess you used that link because it nicely describes the attack? If 
so maybe another link's better as it could be misleading perhaps).

Separately you do point out the statelessness requirement can be dropped 
for one signer, which is a nice detail. ... I'm just wondering, why does 
this not apply to BIP327 also? (I guess in some general sense it does, but 
maybe it was not interesting there for some reason? Is it just because the 
'special last signer deterministic' subcase subsumes it?)

Cheers,
AdamISZ/waxwing

On Thursday, July 17, 2025 at 10:34:49 AM UTC-3 Jonas Nick wrote:

> 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.
>

-- 
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+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/76f2e760-37a7-42ca-b8c2-38659dc94c40n%40googlegroups.com.

[-- Attachment #1.2: Type: text/html, Size: 6303 bytes --]