From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Thu, 03 Jul 2025 07:30:57 -0700 Received: from mail-yb1-f185.google.com ([209.85.219.185]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1uXKxk-0005KK-C8 for bitcoindev@gnusha.org; Thu, 03 Jul 2025 07:30:57 -0700 Received: by mail-yb1-f185.google.com with SMTP id 3f1490d57ef6-e897d331804sf2644690276.0 for ; Thu, 03 Jul 2025 07:30:55 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=googlegroups.com; s=20230601; t=1751553050; x=1752157850; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:sender:from :to:cc:subject:date:message-id:reply-to; bh=8NCELQ7mGqNAxNzdf2V+VOQ0zt5AkK+iMz1buj181eM=; b=E79EbfRalkrKkXgee9dYF+ZZbXdBT12MnkzFm+7oDAWxx+TLT7ETNuzER8f50eEb5L s+fuzqyxiF+DEb8tEVN0p2gUrMXHlFFdz+j3P0srYUjySThyKo3X1W/w1ZTRVxPoNSMY c8RWvm13dPcCikP0MPTDzHSMgY5b1usjrz/wr1+DS9s41qIaNzLkorKwm1AeHKjqfWng S/DWQtbilTgQvf47JcNebYSmffASTaFGtCkHavmU7KU9B3nCN1Sd+NM+2xmZu8EkkXke aJTFPTyZ9FfgMMrfeIuEveMvRGqT4s6aiblAPFlCTCCGDaDil73AKWy7gYO3T2oxbWPR syQQ== DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1751553050; x=1752157850; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender:mime-version :subject:references:in-reply-to:message-id:to:from:date:from:to:cc :subject:date:message-id:reply-to; bh=8NCELQ7mGqNAxNzdf2V+VOQ0zt5AkK+iMz1buj181eM=; b=cUzO/GFB8NqvEiHeFtjvNe5aweqFZW5tXHBlmoU5e1bTRh4e1mIK8DVvoJSESlhriy ZjuH/BBnFxYMKtKozgextb95dWrUaxJL02lFo2eZKmQ0YFanBYIQeuU9FsNbL1BjgSYM MFCvGSoScCAy9oVR7lpYjriTeaC7Pluv27iHW2S+sbnwIKiSxpRwaFkm48xWbSK3Cghp NlVmqpWrWAr+s27Qd+IWGiO1InCbFY2zYINInRgIyQvVhT1f+gFG6pmkUhs4/NRF2+IA Of7n2X49gjmagGHrMZvATMq+GZoC0zu3o8X32JKs3wtU467U1X7hI8pExwlxHIq7UY4K njGQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1751553050; x=1752157850; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-sender: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; bh=8NCELQ7mGqNAxNzdf2V+VOQ0zt5AkK+iMz1buj181eM=; b=iPh4pXEPLLoTE/YFUJUSg3h0uh+6VVMVqcRzCIY1uW3OECCB3AcA8y7L2riozx+cNi j49tghZoxAQy6O8ONW4X4OomMAizai6KBuJEMnck3ZFnWcGXjZY5MniilFGrcexyDB3+ ru5KQTWvfPRWosXtT8aaLZyCIl6lsllC4I7IoMbc/gyr1jKRqc9Lnn91YoJ+9FN96KYA hz8LCclhJ37nE0m7DTLq55+Y/va8QtJnObcNoKboE6xMw4wFznmglEIEzVj8nN0ee0p4 KdNlodcFkRO0Dx/jCG3+Na50fNSDW9WmbuFFxRaTwb46nFD0q+I/xSSPtckMfRHg8O4/ y70Q== Sender: bitcoindev@googlegroups.com X-Forwarded-Encrypted: i=1; AJvYcCX0N5QDh3kLlzn98WA8c03HMdiF/avnpq2+kX/2biZnnKhAoVv4/hUV5i62YK4tGKWZGWT1nJTdLqxD@gnusha.org X-Gm-Message-State: AOJu0YyVIAM39ikM3aN5VjZ1LIbOZ4/zgoL98vA3rO5HQp4NLdvEqNA0 cIJbKSyME3urhMak0YT18Ze8UlQ58TUsXucWDf82KLqo48v6+uuNPDFy X-Google-Smtp-Source: AGHT+IHU1DgnRuJk15vGzizEZi8o/KCFO/OJRcEeEQjXgKmFz6y4F3E+jMPNS//xxPL1fi78JEddYw== X-Received: by 2002:a05:6902:298a:b0:e89:8529:13af with SMTP id 3f1490d57ef6-e8985291842mr5675363276.16.1751553049553; Thu, 03 Jul 2025 07:30:49 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=AZMbMZcCYCoc+v01I0Z2TXR/jpwGOAMCTJdMtcDeyHx/D/BnBg== Received: by 2002:a25:df42:0:b0:e82:21c7:67f7 with SMTP id 3f1490d57ef6-e897c33e68dls2230643276.0.-pod-prod-07-us; Thu, 03 Jul 2025 07:30:44 -0700 (PDT) X-Received: by 2002:a05:690c:d91:b0:713:ff2a:c4f2 with SMTP id 00721157ae682-7164d3f1b55mr96985877b3.21.1751553044134; Thu, 03 Jul 2025 07:30:44 -0700 (PDT) Received: by 2002:a05:690c:2f88:b0:711:63b1:720 with SMTP id 00721157ae682-7151675d3dcms7b3; Thu, 3 Jul 2025 07:08:00 -0700 (PDT) X-Received: by 2002:a05:690c:6513:b0:70d:f47a:7e40 with SMTP id 00721157ae682-7164d2ca150mr107783217b3.16.1751551678597; Thu, 03 Jul 2025 07:07:58 -0700 (PDT) Date: Thu, 3 Jul 2025 07:07:58 -0700 (PDT) From: waxwing/ AdamISZ To: Bitcoin Development Mailing List Message-Id: <182e01b0-30f0-4dec-b4bb-5057bd4ef89fn@googlegroups.com> In-Reply-To: <437237c5f0debe352aafd0a184d6266c14d6e142.camel@timruffing.de> 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> Subject: Re: [bitcoindev] Re: DahLIAS: Discrete Logarithm-Based Interactive Aggregate Signatures MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_209708_1087604550.1751551678188" 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_209708_1087604550.1751551678188 Content-Type: multipart/alternative; boundary="----=_Part_209709_1349205113.1751551678188" ------=_Part_209709_1349205113.1751551678188 Content-Type: text/plain; charset="UTF-8" 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 -- 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/182e01b0-30f0-4dec-b4bb-5057bd4ef89fn%40googlegroups.com. ------=_Part_209709_1349205113.1751551678188 Content-Type: text/html; charset="UTF-8" Content-Transfer-Encoding: quoted-printable
Hi Tim, answers inline:

>=C2=A0Your obse= rvation 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.

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

>=C2=A0The reason we why prefer the scheme with a single b is simply
efficiency. The current signing protocol needs 3 group exponentiation= s
(i.e., scalar-point multiplications). With separate b values, one of
those becomes a multi-exponentiation of size n-1, which is much slowe= r
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 verifyin= g.
So we'd be going from=C2=A0from 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 bett= er than that while being unrestricted is BN06, but that isn't a 2 round sch= eme.

My initial reaction would be, since it's no= t 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 input= s 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 mor= e 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 prot= ocols (though not LN itself I think)?)

The schem= e 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.<= /div>

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

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

> We didn't talk about identifying disruptive part= icipants 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?=C2=A0
> 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 additionall= y
the participants have secure channels to the coordinator, then no
malicious can steal the R_{2,j} of an honest participant j. So, if th= e
coordinator sees that R_{2,i} =3D R_{2,j}, the right conclusion is th= at
they are colluding and both malicious.

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

Anyway, f= or 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 circu= its in zero knowledge (though things like equality checks are entirely doab= le 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.<= /div>

Cheers,
AdamISZ/waxwing


--
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/182e01b0-30f0-4dec-b4bb-5057bd4ef89fn%40googlegroups.com.
------=_Part_209709_1349205113.1751551678188-- ------=_Part_209708_1087604550.1751551678188--