path: root/6f/65e1d2cc15ce33bd6a3915c74db08934bb3196

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 <bitcoindev+bncBDI23FE35EIBBFFITLBQMGQEQDVGPWI@googlegroups.com>)
	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 <bitcoindev@gnusha.org>; 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 <ekaggata@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <182e01b0-30f0-4dec-b4bb-5057bd4ef89fn@googlegroups.com>
In-Reply-To: <437237c5f0debe352aafd0a184d6266c14d6e142.camel@timruffing.de>
References: <be3813bf-467d-4880-9383-2a0b0223e7e5@gmail.com>
 <039cb943-5c94-44ba-929b-abec281082a8n@googlegroups.com>
 <604ca4d2-48c6-4fa0-baa6-329a78a02201n@googlegroups.com>
 <f9e082e3-4079-40b6-aa49-5d1b9b3b1e29@gmail.com>
 <a9f133ff-1d8e-45a3-8186-79fb52bbd467n@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: <bitcoindev.googlegroups.com>
X-Google-Group-Id: 786775582512
List-Post: <https://groups.google.com/group/bitcoindev/post>, <mailto:bitcoindev@googlegroups.com>
List-Help: <https://groups.google.com/support/>, <mailto:bitcoindev+help@googlegroups.com>
List-Archive: <https://groups.google.com/group/bitcoindev
List-Subscribe: <https://groups.google.com/group/bitcoindev/subscribe>, <mailto:bitcoindev+subscribe@googlegroups.com>
List-Unsubscribe: <mailto:googlegroups-manage+786775582512+unsubscribe@googlegroups.com>,
 <https://groups.google.com/group/bitcoindev/subscribe>
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

<div>Hi Tim, answers inline:</div><div><br /></div><div>&gt;=C2=A0Your obse=
rvation is right: If each participant has a distinct b_i as
<br />you've sketched, then the duplicate checks can be omitted. And I tend
<br />to agree that this is more natural scheme. In fact, this is where we
<br />started, and we had a security proof of this (though without tweaking
<br />worked out) in an earlier unpublished draft of the paper, and only
<br />afterwards we found a scheme with a single b.</div><div><br /></div><=
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!</div><div><br /></div><div=
>&gt;=C2=A0The reason we why prefer the scheme with a single b is simply
<br />efficiency. The current signing protocol needs 3 group exponentiation=
s
<br />(i.e., scalar-point multiplications). With separate b values, one of
<br />those becomes a multi-exponentiation of size n-1, which is much slowe=
r
<br />and needs O(n/log n) time instead of O(1).</div><div><br /></div><div=
>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.</div><div>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.</div><div><br /></div><div>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)?)</div><div><br /></div><div>The schem=
e is explicitly not limited to Bitcoin, nor blockchains, though, so there's=
 that; is that relevant here?</div><div><br /></div><div>&gt; And yes, the =
uniqueness check looks a bit strange at first glance, but
<br />(as the proof shows) there should be nothing wrong with it. One could
<br />argue that the uniqueness check is a potential footgun in practice
<br />because an implementation could omit it by accident, and would still
<br />"work" and produce signatures. But we find this not really convincing
<br />because it's possible to create a failing test vector for this case.<=
/div><div><br /></div><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.</div><div><br /></div>=
<div>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;</div>=
<div><br /></div><div>&gt; We didn't talk about identifying disruptive part=
icipants in the paper
<br />at all, but one could also argue that the uniqueness check creates a
<br />problem if the honest participants want to figure out who disrupted a
<br />session: if malicious participant i copies from honest participant j,
<br />then how the others tell who of them to exclude?=C2=A0<br /></div><di=
v>&gt; But if you think about it, that's not a real issue. In any case,
<br />identifying disruptive participants will work reliably only if the
<br />coordinator is honest, so let's assume this. And then, if additionall=
y
<br />the participants have secure channels to the coordinator, then no
<br />malicious can steal the R_{2,j} of an honest participant j. So, if th=
e
<br />coordinator sees that R_{2,i} =3D R_{2,j}, the right conclusion is th=
at
<br />they are colluding and both malicious.</div><div><br /></div><div>Yes=
, those are some interesting points to consider. On one detail: "In any cas=
e, identifying disruptive participants will work reliably only if the
<br />coordinator is honest, so let's assume this." -- this could also be a=
ddressed with proofs of knowledge, no?</div><div><br /></div><div>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.</div><div><br /></div><div>As for finding =
a concrete problem with the equality checks, I have not. At least not yet.<=
/div><div><br /></div><div>Cheers,</div><div>AdamISZ/waxwing</div><div><br =
/></div><div><br /></div>

<p></p>

-- <br />
You received this message because you are subscribed to the Google Groups &=
quot;Bitcoin Development Mailing List&quot; group.<br />
To unsubscribe from this group and stop receiving emails from it, send an e=
mail to <a href=3D"mailto:bitcoindev+unsubscribe@googlegroups.com">bitcoind=
ev+unsubscribe@googlegroups.com</a>.<br />
To view this discussion visit <a href=3D"https://groups.google.com/d/msgid/=
bitcoindev/182e01b0-30f0-4dec-b4bb-5057bd4ef89fn%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/182e01b0-30f0-4dec-b4bb-5057bd4ef89fn%40googlegroups.com</a>.<br />

------=_Part_209709_1349205113.1751551678188--

------=_Part_209708_1087604550.1751551678188--