From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Wed, 08 Jul 2026 12:29:36 -0700 Received: from mail-oo1-f62.google.com ([209.85.161.62]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1whXxf-0004Ak-Vq for bitcoindev@gnusha.org; Wed, 08 Jul 2026 12:29:36 -0700 Received: by mail-oo1-f62.google.com with SMTP id 006d021491bc7-6a141f64074sf1254230eaf.1 for ; Wed, 08 Jul 2026 12:29:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20251104; t=1783538969; x=1784143769; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:content-type :mime-version:subject:references:in-reply-to:message-id:to:from:date :sender:from:to:cc:subject:date:message-id:reply-to:content-type; bh=wyWLKczONELHU6zC3ATe05NTQAH0tAtXKJGaxByTHXs=; b=smeCF7MOLzp+rpDkaZYRBOHO/Bi60eerLW8Hpu9iKYDF9gguX/J6MHuLaSLkv5S1Ck neQFQdZEXKbYyA/vU24P6nYnJWf81rdrv2qbPtp4fvJJJB3fJwJ86sj05rgLII5QFOUA SZaDpD/ejTe69qUTPrbo6o3skSFkQg1frOrJBUYBCMfnhUDGK0VtLFG7VVO8BnZVI3og zWix3ZD5qmL2u6XkltoXCLYwJWv924E9Hhxss4fOvOq9IcqI+YVdtWzVbkatxyenl8vJ ejz+Pq8yAHn76GP7C2LfEe2d118rSBLy2vdLOQHwcnja1VrcFj6zjBvOH83DVcbfX0IR B7qw== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1783538969; x=1784143769; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:content-type :mime-version:subject:references:in-reply-to:message-id:to:from:date :from:to:cc:subject:date:message-id:reply-to:content-type; bh=wyWLKczONELHU6zC3ATe05NTQAH0tAtXKJGaxByTHXs=; b=JUhngxwx39+6nNKF38s85/Q0zz7Xt6EsZ0bLXh9DPpZj59uvi9tCzcc24tngEX3k5q 5pJ4jJF+Ozq0kb8tP/meTUC7Bt4SkWXls2Bw4zTdP1L7c5i8ethrrSvKFKP20vw1+/pa /qEgVbff4+BYRzHwgtSYbbFIIK63HwZn9K5VD9b8/WNAEUoXrZmx1FxnltKtMBoAykqe +MqwouRVRNmj6KkG78iqAQZsA5MsebMEDKNm+n/6nUl5Y7Zy5aC6+e9P64CVp43qbXt2 jTMa9kqkyxtUlD76d7rCz9G8aiH0rTjU3FaIiwUqOITWP7r4mLN5/pQDiv4Jp5G+Efyd ml9g== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1783538969; x=1784143769; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:content-type :mime-version:subject:references:in-reply-to:message-id:to:from:date :x-beenthere:x-gm-message-state:sender:from:to:cc:subject:date :message-id:reply-to:content-type; bh=wyWLKczONELHU6zC3ATe05NTQAH0tAtXKJGaxByTHXs=; b=Pk9LcQyesu9PgPlAv69FoTaIqVTtElTzR86HKHvmIHg/Wm2dIz9evjH65vZrzWRYhr GDm13cP+oyTlukhtNbOSvF2+goZmkqQ+ZWcldAB/8haL4vwR5fF2p4+8Pwqd+k64EWEl a236rPvFH48RCbZAf9KEAhOF8LFKFoRx1cK84PXWIuJJ1hxBrREIo74GNeRvtxvzYLyf W1YDMMHZ0tL1y3aPxGcPB9FReCY/l9T156i2qzO2XepU3yguR026V3T6Z5q/NLRelth4 qcYoiFI+zDGHwl+r8zU46EzVSnKrIBUTLgetJ0SFQiB0JdHAHzlyVF5YmbYvEyLB8LRl VIwQ== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AFNElJ+qWfaUPkd3QhmRDyrQXC+pa+dYo3Z+tO9+073ZBu74PfZ2FrF6tWd0zOasGLOFwD/pvFj4FVXzQljE@gnusha.org X-Gm-Message-State: AOJu0YwFoFF8LfjcicGoSl1cIHzCE5CjXlShjeglmOXwowuY6edQIpFs QDDKFUITio0XGDPMorx6u5nOF0PQKj7fAGCOes4oOf+NxHpVfLr9QDtb X-Received: by 2002:a05:6820:c3c8:b0:6a3:731c:8ac7 with SMTP id 006d021491bc7-6a3731c9d9amr1301873eaf.67.1783538969035; Wed, 08 Jul 2026 12:29:29 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="AX0PUUdYQNJ9sBl97Sx6TXGdwDcXJc8jDin6dBN1k3izNkdbgg==" Received: by 2002:a05:6871:8899:10b0:447:4a70:4987 with SMTP id 586e51a60fabf-4514ae02466ls576310fac.2.-pod-prod-03-us; Wed, 08 Jul 2026 12:29:23 -0700 (PDT) X-Received: by 2002:a05:6808:17a9:b0:486:8a11:6e8b with SMTP id 5614622812f47-4a2018ccdcemr3141469b6e.2.1783538963705; Wed, 08 Jul 2026 12:29:23 -0700 (PDT) Received: by 2002:a05:690c:a74a:b0:81c:b14:1c48 with SMTP id 00721157ae682-81d76d8014fms7b3; Wed, 8 Jul 2026 12:12:42 -0700 (PDT) X-Received: by 2002:a05:690c:7406:b0:80c:85b6:75bf with SMTP id 00721157ae682-81dbf588f4fmr32621177b3.72.1783537962156; Wed, 08 Jul 2026 12:12:42 -0700 (PDT) Date: Wed, 8 Jul 2026 12:12:41 -0700 (PDT) From: waxwing/ AdamISZ To: Bitcoin Development Mailing List Message-Id: <23f2c418-d652-4f92-81c2-0e9fc608d8bbn@googlegroups.com> In-Reply-To: <76f2e760-37a7-42ca-b8c2-38659dc94c40n@googlegroups.com> References: <039cb943-5c94-44ba-929b-abec281082a8n@googlegroups.com> <604ca4d2-48c6-4fa0-baa6-329a78a02201n@googlegroups.com> <3f23ebaa-02c7-45d1-bf57-9baf48c133a3n@googlegroups.com> <437237c5f0debe352aafd0a184d6266c14d6e142.camel@timruffing.de> <182e01b0-30f0-4dec-b4bb-5057bd4ef89fn@googlegroups.com> <76f2e760-37a7-42ca-b8c2-38659dc94c40n@googlegroups.com> Subject: Re: [bitcoindev] Re: DahLIAS: Discrete Logarithm-Based Interactive Aggregate Signatures MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_422972_1361458637.1783537961757" X-Original-Sender: ekaggata@gmail.com Precedence: list Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com List-ID: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , X-Spam-Score: -0.5 (/) ------=_Part_422972_1361458637.1783537961757 Content-Type: multipart/alternative; boundary="----=_Part_422973_615064177.1783537961757" ------=_Part_422973_615064177.1783537961757 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Apologies I sent this in the wrong thread! Please ignore :) On Wednesday, July 8, 2026 at 4:10:57=E2=80=AFPM UTC-3 waxwing/ AdamISZ wro= te: > A couple of other minor comments: > > On list ordering, I was tempted to write "why not include a default=20 > ordering algorithm", but ... I can see why that's not worth bothering wit= h,=20 > since the design includes the untrusted coordinator role, so in that sens= e=20 > it really doesn't matter. > > Security argument: the paper's security claim is a reduction to the=20 > algebraic variant of the one-more-discrete-log assumption under the rando= m=20 > oracle model for the hash_sig (AOMDL under ROM). Obviously there's only s= o=20 > much to be written there, but following on from BIP340 and BIP327 I think= =20 > it's reasonable to briefly describe the security claim somewhere, and wha= t=20 > its kind of "ancestry" is. As there, pointing out that AOMDL is a weaker= =20 > (better) assumption is probably worth mentioning. You could also add a=20 > note, though it's unlikely any BIP reader would be confused about this=20 > 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=20 > footnote? While it's both in the weeds, and also has no direct implicatio= n=20 > for implementation, it nicely shows why the technical problem to solve he= re=20 > is different from what the paper calls "IMS" vs "IAS".) > > About nonce gen: this is obviously a tricky but hugely important point,= =20 > just as it was for BIP327. The first comment I want to make is, why do yo= u=20 > link to=20 > https://medium.com/blockstream/musig-dn-schnorr-multisignatures-with-veri= fiably-deterministic-nonces-27424b5df9d6#e3b6=20 > in the section where you're saying "don't use deterministic nonce=20 > generation"? The main point of that blog post is to show a way that that= =20 > *can* done in MuSig2, even though, by default, it's insecure. But aren't= =20 > you mainly trying to point out that, as in BIP327, in this BIP, we don't= =20 > have security with deterministic nonces? (rather than making a Musig-DN= =20 > recommendation)? > > (Hmm, I guess you used that link because it nicely describes the attack?= =20 > If so maybe another link's better as it could be misleading perhaps). > > Separately you do point out the statelessness requirement can be dropped= =20 > for one signer, which is a nice detail. ... I'm just wondering, why does= =20 > this not apply to BIP327 also? (I guess in some general sense it does, bu= t=20 > maybe it was not interesting there for some reason? Is it just because th= e=20 > 'special last signer deterministic' subcase subsumes it?) > > Cheers, > AdamISZ/waxwing > > On Thursday, July 17, 2025 at 10:34:49=E2=80=AFAM UTC-3 Jonas Nick wrote: > >> Hi waxwing,=20 >> >> Thanks again for your comments.=20 >> >> > My initial reaction would be, since it's not worsening the scaling of= =20 >> the=20 >> > verifier, does it matter?=20 >> >> I think saving time in signing does matter (3 group exponentiations=20 >> requiring=20 >> O(1) group operations in total vs. O(n/log n) group operations); for=20 >> example, in=20 >> constrained signing devices as you mention. In particular, the "single-b= "=20 >> variant with the larger signing cost doesn't appear to have advantages= =20 >> (see=20 >> below) compared to "multi-b" which has lower signing cost.=20 >> >> > The scheme is explicitly not limited to Bitcoin, nor blockchains,=20 >> though,=20 >> > so there's that; is that relevant here?=20 >> >> The scheme is not limited to Bitcoin, but the main application we=20 >> designed for=20 >> is Bitcoin. I agree that verification performance is of primary=20 >> importance. We=20 >> would choose a scheme with lower signing performance, if it gives us a= =20 >> better=20 >> verification performance in return (if the trade-off is reasonable).=20 >> >> > Yes, those are some interesting points to consider. On one detail: "In= =20 >> any=20 >> > case, identifying disruptive participants will work reliably only if= =20 >> the=20 >> > coordinator is honest, so let's assume this." -- this could also be=20 >> addressed=20 >> > with proofs of knowledge, no?=20 >> >> Maybe I misunderstand what you're getting at, but I don't understand how= =20 >> proofs=20 >> of knowledge would get rid of the honest coordinator requirement for=20 >> identifying=20 >> disruptive signers. Moreover, both R_{2,i} and R_{2,j} could have a vali= d=20 >> proof=20 >> of knowledge attached (for example, if parties i and j share the dlog of= =20 >> R_{2,i}=20 >> =3D R_{2,j}).=20 >> >> > Anyway, for me it was more a sort of preference for purely algebraic= =20 >> > algorithms. It's a little fanciful, but algebraic algorithms are easie= r=20 >> to=20 >> > encode in circuits in zero knowledge (though things like equality=20 >> checks are=20 >> > entirely doable ofc!) and maybe easier to "encode" into modular scheme= s=20 >> that=20 >> > use them as a building block. Maybe. Less conditional branches / loops= =20 >> to=20 >> > traverse in the code?=20 >> >> Why exactly would it be easier to encode the multi-b variant in a=20 >> circuit? The=20 >> single-b variant requires checking whether there exists i such that=20 >> R_{2,i}=20 >> matches a fixed R_{2,j}. In the multi-b variant we'd need to compute the= =20 >> product=20 >> of all R_{2,i}^{b_i}, which, even with a multiexp implementation,=20 >> requires at=20 >> least visiting all elements plus the actual multiexponentiation involvin= g=20 >> O(n/log n) group operations. So encoding the single-b variant appears to= =20 >> be=20 >> strictly easier.=20 >> > --=20 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 e= mail to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/= 23f2c418-d652-4f92-81c2-0e9fc608d8bbn%40googlegroups.com. ------=_Part_422973_615064177.1783537961757 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable Apologies I sent this in the wrong thread! Please ignore :)

On Wednesday,= July 8, 2026 at 4:10:57=E2=80=AFPM UTC-3 waxwing/ AdamISZ wrote:
A couple of other= minor comments:

On list ordering, I was tempted t= o 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 mat= ter.

Security argument: the paper's security c= laim is a reduction to the algebraic variant of the one-more-discrete-log a= ssumption 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 f= rom BIP340 and BIP327 I think it's reasonable to briefly describe the s= ecurity claim somewhere, and what its kind of "ancestry" is. As t= here, pointing out that AOMDL is a weaker (better) assumption is probably w= orth mentioning. You could also add a note, though it's unlikely any BI= P reader would be confused about this point, that the scheme is *not* inten= ded to be post-quantum secure.

(Is it worth mentio= ning 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, i= t nicely shows why the technical problem to solve here is different from wh= at the paper calls "IMS" vs "IAS".)

About nonce gen: this is obviously a tricky but hugely important poin= t, just as it was for BIP327. The first comment I want to make is, why do y= ou link to=C2=A0https://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 main= ly trying to point out that, as in BIP327, in this BIP, we don't have s= ecurity with deterministic nonces? (rather than making a Musig-DN recommend= ation)?

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

Separately you do po= int 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 BI= P327 also? (I guess in some general sense it does, but maybe it was not int= eresting there for some reason? Is it just because the 'special last si= gner deterministic' subcase subsumes it?)

Cheers,
AdamISZ/waxwing

On Thursday, July 17, 2025 at 10:34:49=E2=80= =AFAM UTC-3 Jonas Nick wrote:
Hi waxwing,

Thanks again for your comments.

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

I think saving time in signing does matter (3 group exponentiations req= uiring
O(1) group operations in total vs. O(n/log n) group operations); for ex= ample, in
constrained signing devices as you mention. In particular, the "si= ngle-b"
variant with the larger signing cost doesn't appear to have advanta= ges (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 desig= ned for
is Bitcoin. I agree that verification performance is of primary importa= nce. 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 co= uld also be addressed
> with proofs of knowledge, no?

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

> Anyway, for me it was more a sort of preference for purely algebr= aic
> 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 circu= it? 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 comput= e the product
of all R_{2,i}^{b_i}, which, even with a multiexp implementation, requi= res at
least visiting all elements plus the actual multiexponentiation involvi= ng
O(n/log n) group operations. So encoding the single-b variant appears t= o be
strictly easier.

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoind= ev/23f2c418-d652-4f92-81c2-0e9fc608d8bbn%40googlegroups.com.
------=_Part_422973_615064177.1783537961757-- ------=_Part_422972_1361458637.1783537961757--