From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Wed, 08 Jul 2026 12:11:04 -0700 Received: from mail-oa1-f55.google.com ([209.85.160.55]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1whXfk-0003zE-6H for bitcoindev@gnusha.org; Wed, 08 Jul 2026 12:11:04 -0700 Received: by mail-oa1-f55.google.com with SMTP id 586e51a60fabf-44a06794b48sf835614fac.0 for ; Wed, 08 Jul 2026 12:11:03 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20251104; t=1783537858; x=1784142658; 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=brlBenJYpgXZyfuIWTFcXm7XWUen69UtrNkwnt6SjIY=; b=Ibo41ZdIOm4SdWm24QdADw1quZtsEEB/PCsquR0LWVVIKRg9wI5a9pXclIuJlVWA8+ sv12YYc97CRxFOrXGAInRK/Xkx0EskK8WEU6KiZ5/smmLo2wbIlI3ApytaoCsBsRVXHw w73DhmbI+kofrtmfeh1ufhQ1GlewtF8EJX+cMReFI5vZospI5ACQKUozeruToa4r3dyO /f+TmB8Zs8hKxNTZOBbT7APV1RQVjHSeJ1IhsbT5YxRRBPwcP//0zTADza9mDwbKgFti BvsKKyAUNCQdaAgvRzM1Q9PiGOtZvki0prShP4y//B8VzmsS/LRkzIEsIrJ4vREmLUCL CpJg== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20251104; t=1783537858; x=1784142658; 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=brlBenJYpgXZyfuIWTFcXm7XWUen69UtrNkwnt6SjIY=; b=dcrIUPg1brmtnycGFQPY7jqIWc7SOqVGVoBc2eUZ+mBLTJfLLpr+pHjQuq+YBAR3eX e5HIraaorVl8JfUuiuAzNLx5g8/eoBDUngH9iaPT2HogFvtNfhEICDmUPfpLJunwHV1G KjpwXZrZAoW0RIYvTLG52wPv2nm6yA55teBdK4O2apU5iIiB0LfzF6v+nfA/IfPo6bsi IZkBzLgP7yfZ5Pkm+pxOV7MhARSe6PW+dgcIaM4gHxgFQS1mH6Z0WLtbA3NcSdX/rNDQ ji86OPhPHxgpwM0RApD+EGbwlwvDGmCPeOAEJcssKxWdgqrj+7Kxiti6tXQmUAyjTO+6 UXBg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20251104; t=1783537858; x=1784142658; 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=brlBenJYpgXZyfuIWTFcXm7XWUen69UtrNkwnt6SjIY=; b=l/IT46dK+oi/RoCpvK9BOGkEc2lHuyG6zAP+l4PhwcLWk822yDH//pgm3AwdgmvaEV iytO2UtCkDTtlmmuiCwVFyFyj+aj7wE9L2TISETIuaxk5FtCcRiBvPe1WcxjdGiHjFn1 kPZ6NxOXHg5EOVvTUwaozOuBzFU0baz5M9EFv5MeQMt1xcDmfZmaHKYN/DtGDzTRhIut +OtXNrKowdtM+qn9+XBNldxK/K8m05QjmO1d3sPWsnJmAQGeBh9kkmRi+KEIvvEDiojO ADFFM4Y2dc6Ktq/cz3MUFPIyluzv9RlR8ZjohhacR91BgsLsg86VybLjM8wj+wKeRcb9 ztVQ== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AFNElJ/jLkQdWU8XkmHbCHrawENSIBP9VbX/MQOO5uIpjWmRe+aq1zhvXGyApEFJQ/oxvajgOaaKbPqU5yrv@gnusha.org X-Gm-Message-State: AOJu0Yw9zvgN6HAJw5mNhKuaXLsE3foFtPsIReAfvJycY766nF+QFXfX 0D4C4DOKZNq/wauvZXpkP/fm2Sd6z7VJq1cCvakgeOhnv4MX5f5rtFPW X-Received: by 2002:a05:6870:2428:b0:448:c946:9ae1 with SMTP id 586e51a60fabf-4516381b989mr2051290fac.18.1783537857687; Wed, 08 Jul 2026 12:10:57 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h="AX0PUUeR+qZBfG0U0g2WF4/UkmahAH4qs86bhQgncSitmwxY3Q==" Received: by 2002:a05:6871:2edd:b0:448:8fc6:53a6 with SMTP id 586e51a60fabf-45148db8418ls841865fac.0.-pod-prod-08-us; Wed, 08 Jul 2026 12:10:51 -0700 (PDT) X-Received: by 2002:a05:6808:6909:b0:495:db98:cd70 with SMTP id 5614622812f47-4a2051009b8mr2691592b6e.35.1783537851765; Wed, 08 Jul 2026 12:10:51 -0700 (PDT) Received: by 2002:a05:690c:a617:b0:81b:edd5:5117 with SMTP id 00721157ae682-81d7134e63dms7b3; Wed, 8 Jul 2026 12:06:00 -0700 (PDT) X-Received: by 2002:a05:690c:62c7:b0:81e:68f6:f84d with SMTP id 00721157ae682-81e68f70306mr7048777b3.52.1783537559271; Wed, 08 Jul 2026 12:05:59 -0700 (PDT) Date: Wed, 8 Jul 2026 12:05:58 -0700 (PDT) From: waxwing/ AdamISZ To: Bitcoin Development Mailing List Message-Id: <76f2e760-37a7-42ca-b8c2-38659dc94c40n@googlegroups.com> In-Reply-To: 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> Subject: Re: [bitcoindev] Re: DahLIAS: Discrete Logarithm-Based Interactive Aggregate Signatures MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_589898_1083355994.1783537558838" 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_589898_1083355994.1783537558838 Content-Type: multipart/alternative; boundary="----=_Part_589899_1671857700.1783537558838" ------=_Part_589899_1671857700.1783537558838 Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable 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 with,= =20 since the design includes the untrusted coordinator role, so in that sense= =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 random= =20 oracle model for the hash_sig (AOMDL under ROM). Obviously there's only so= =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 what= =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 implication= =20 for implementation, it nicely shows why the technical problem to solve here= =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 you= =20 link=20 to https://medium.com/blockstream/musig-dn-schnorr-multisignatures-with-ver= ifiably-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? If= =20 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, but= =20 maybe it was not interesting there for some reason? Is it just because the= =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, > > Thanks again for your comments. > > > My initial reaction would be, since it's not worsening the scaling of t= he > > verifier, does it matter? > > I think saving time in signing does matter (3 group exponentiations=20 > requiring > O(1) group operations in total vs. O(n/log n) group operations); for=20 > 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 (s= ee > below) compared to "multi-b" which has lower signing cost. > > > The scheme is explicitly not limited to Bitcoin, nor blockchains, thoug= h, > > so there's that; is that relevant here? > > The scheme is not limited to Bitcoin, but the main application we designe= d=20 > for > is Bitcoin. I agree that verification performance is of primary=20 > importance. We > would choose a scheme with lower signing performance, if it gives us a=20 > better > verification performance in return (if the trade-off is reasonable). > > > Yes, those are some interesting points to consider. On one detail: "In= =20 > any > > case, identifying disruptive participants will work reliably only if th= e > > coordinator is honest, so let's assume this." -- this could also be=20 > addressed > > with proofs of knowledge, no? > > Maybe I misunderstand what you're getting at, but I don't understand how= =20 > proofs > of knowledge would get rid of the honest coordinator requirement for=20 > identifying > disruptive signers. Moreover, both R_{2,i} and R_{2,j} could have a valid= =20 > proof > of knowledge attached (for example, if parties i and j share the dlog of= =20 > R_{2,i} > =3D 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= =20 > to > > encode in circuits in zero knowledge (though things like equality check= s=20 > are > > entirely doable ofc!) and maybe easier to "encode" into modular schemes= =20 > 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= ?=20 > 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= =20 > product > of all R_{2,i}^{b_i}, which, even with a multiexp implementation, require= s=20 > 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. > --=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/= 76f2e760-37a7-42ca-b8c2-38659dc94c40n%40googlegroups.com. ------=_Part_589899_1671857700.1783537558838 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
A couple of other minor comments:

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

Security argument: the paper's securi= ty claim is a reduction to the algebraic variant of the one-more-discrete-l= og assumption under the random oracle model for the hash_sig (AOMDL under R= OM). 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 secur= ity claim somewhere, and what its kind of "ancestry" is. As there, pointing= out that AOMDL is a weaker (better) assumption is probably worth mentionin= g. 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-qua= ntum secure.

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

About nonce gen: this is obvious= ly a tricky but hugely important point, just as it was for BIP327. The firs= t comment I want to make is, why do you link to=C2=A0https://medium.com/blo= ckstream/musig-dn-schnorr-multisignatures-with-verifiably-deterministic-non= ces-27424b5df9d6#e3b6 in the section where you're saying "don't use determi= nistic 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. Bu= t 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 be= tter as it could be misleading perhaps).

Separat= ely you do point out the statelessness requirement can be dropped for one s= igner, which is a nice detail. ... I'm just wondering, why does this not ap= ply to BIP327 also? (I guess in some general sense it does, but maybe it wa= s not interesting there for some reason? Is it just because the 'special la= st 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,

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/76f2e760-37a7-42ca-b8c2-38659dc94c40n%40googlegroups.com.
------=_Part_589899_1671857700.1783537558838-- ------=_Part_589898_1083355994.1783537558838--