path: root/c5/47075fea42a5ab4036d7e9713f1f17ede3aab4

Delivery-date: Sat, 26 Apr 2025 10:22:48 -0700
Received: from mail-yw1-f183.google.com ([209.85.128.183])
	by mail.fairlystable.org with esmtps  (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
	(Exim 4.94.2)
	(envelope-from <bitcoindev+bncBDI23FE35EIBBXFMWTAAMGQE6DZEMPQ@googlegroups.com>)
	id 1u8jEk-00035n-JE
	for bitcoindev@gnusha.org; Sat, 26 Apr 2025 10:22:48 -0700
Received: by mail-yw1-f183.google.com with SMTP id 00721157ae682-7082e59b9a8sf48788147b3.2
        for <bitcoindev@gnusha.org>; Sat, 26 Apr 2025 10:22:46 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=googlegroups.com; s=20230601; t=1745688160; x=1746292960; 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=hotfxzwzdVtaVOWFnhE6u3hIfp/Zwfdn7J3urpMVpvE=;
        b=SmkQ769sUF+vSAdDw10JD1qBp5VfFUmiO9EYgKFzmMaOpJ0aaL2NOGLmWC3VWoWV8Y
         SRQFnG189qA7YbdP95uB+IVHDpz0zE8Tk0nro5yPOqKbfvdf/h1d5hHIL82i8bi9yCIj
         n0Cp21+gvZYpDoLlLHZ/q7/NPRNxofDiWgat641PjCGQOw1U1RXonkEoPsDoIFn6i0Ee
         Re8T/enaqMIFpZgs28U4RGYz28mznc3Va8yVpvICmSwKxP6olQMO8g7RlAatlpT1982m
         ogy2SX7bS4xTyAEA/8omiBRWaNqc2+xNvkJSSaqcIfWTqKOx6fywt67wpkTaPCDp6ks/
         SODw==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=gmail.com; s=20230601; t=1745688160; x=1746292960; 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=hotfxzwzdVtaVOWFnhE6u3hIfp/Zwfdn7J3urpMVpvE=;
        b=I5qA5I9DnJOu5yKft46uQ5mnY2fs+nRSD3BoakE7+cvae60M7fmZkdb2IEllF/bEoQ
         VAj0yGYHAWYfnKpZsDk5zcYE4ZBfdhPquvBWuAPJm3rrJmq/Hb9YywjSZhikfqtp2aws
         92SzmOP0zoWXN2/XCKyhYxVnWFuBNUKY+QABL+CEhQbAlGTpwfcBPa/iBIPl0RWTFxLB
         rBc0gWrkjBBtrRoR0Fpeq5UfZ3Hwf3Tmhfc/s3VqgJZt3qsrwCVEWZhIYuaiQ1T4Fy0u
         grAscy20i9dF6RVovD93AYdhdPKmIGVeA3IpjqGXzIYpPIUpp6vItLmyIxAOCz8szbEg
         lpag==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
        d=1e100.net; s=20230601; t=1745688160; x=1746292960;
        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=hotfxzwzdVtaVOWFnhE6u3hIfp/Zwfdn7J3urpMVpvE=;
        b=HdirNN7WK0LpN8pIssuN3OG2Ix8bObuDWCk0NIoth2VsTs7hCHmZseDfKXXhdAlf5B
         1jPMzWznb8KYAzlPEg0ujFy6vWwWWTWuctL0eDn6lK0dYCeMWgEA2/ROXt6XC7cVURAb
         MZQaEodaNUysYzKDFfu1PUqnzDzmCvHLt5LdfuQwOXu0n9ULHhmAPLo005udWCQeQpZ/
         aA8U+c/qt3WOdBZLItDYl+GYTXEKxN3B1RDJgV7FpnOMj88UfxOZSlhtyhrgop4arBxz
         8fRgyTKZfKIAyd9MhWxAdRxDKpA3zCTl1pA4pyg6bYq6kWo7YWeI+xjfJmIkcYTxfrUB
         w0HQ==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCVDUa7VA8MPf5PblV1WsrRBGnTXP3FlZukCRC6Qk2FPz8HWGz4mSQQiYm5MOfsK7S8ESWL49SCfA0Rj@gnusha.org
X-Gm-Message-State: AOJu0YxdkrdTUtw2BEzBpuUpxbN41Eb+ALQ0TieheZq1m1iawWh2CIde
	bbnsAIozOesOyjp/8D3gbMeEzogLdU5R9AmWYevidPSW9jdTH/GJ
X-Google-Smtp-Source: AGHT+IEkEv0wTBo0yPReGGsree3uysTldq4rGDrGGzLrezcaypZ5z1qIFTn2Kd6ftT1of8bOQjHIxQ==
X-Received: by 2002:a05:6902:907:b0:e61:1c56:d678 with SMTP id 3f1490d57ef6-e7316594582mr8771929276.5.1745688160231;
        Sat, 26 Apr 2025 10:22:40 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=AVT/gBFo0IBSem/6aWUdQDIPcMK8fnVqYtk6AzAcc4z1p+Vvlg==
Received: by 2002:a25:dccf:0:b0:e5b:1119:fc5b with SMTP id 3f1490d57ef6-e730820aaf7ls991606276.0.-pod-prod-06-us;
 Sat, 26 Apr 2025 10:22:36 -0700 (PDT)
X-Received: by 2002:a05:690c:6c84:b0:703:ac44:d379 with SMTP id 00721157ae682-7085f1aa290mr50164247b3.22.1745688156563;
        Sat, 26 Apr 2025 10:22:36 -0700 (PDT)
Received: by 2002:a05:690c:3693:b0:708:1ea1:3cd5 with SMTP id 00721157ae682-70854ddd573ms7b3;
        Sat, 26 Apr 2025 10:05:17 -0700 (PDT)
X-Received: by 2002:a05:690c:6c84:b0:703:ac44:d379 with SMTP id 00721157ae682-7085f1aa290mr49464567b3.22.1745687116479;
        Sat, 26 Apr 2025 10:05:16 -0700 (PDT)
Date: Sat, 26 Apr 2025 10:05:15 -0700 (PDT)
From: waxwing/ AdamISZ <ekaggata@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <604ca4d2-48c6-4fa0-baa6-329a78a02201n@googlegroups.com>
In-Reply-To: <039cb943-5c94-44ba-929b-abec281082a8n@googlegroups.com>
References: <be3813bf-467d-4880-9383-2a0b0223e7e5@gmail.com>
 <039cb943-5c94-44ba-929b-abec281082a8n@googlegroups.com>
Subject: [bitcoindev] Re: DahLIAS: Discrete Logarithm-Based Interactive
 Aggregate Signatures
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_32366_1712149344.1745687115956"
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_32366_1712149344.1745687115956
Content-Type: multipart/alternative; 
	boundary="----=_Part_32367_1051542522.1745687115956"

------=_Part_32367_1051542522.1745687115956
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On that last point about "proof of knowledge of R", I suddenly realised=20
it's not a viable suggestion: of course it defends against key subtraction=
=20
attacks, but does not defend at all against the ability to grind nonces=20
adversarially in a Wagner type attack,  so that you could get a forgery on=
=20
the victim's single key from a bunch of parallel signing sessions. So,=20
question retracted, there.

On Saturday, April 26, 2025 at 10:14:36=E2=80=AFAM UTC-6 waxwing/ AdamISZ w=
rote:

> Some comments/questions on the general structure of the scheme:
>
> When I started thinking about ways to change the algorithm, I started to=
=20
> appreciate it more :) Although this algo is not specific to Bitcoin I'm=
=20
> viewing it 100% through that lens here. Some thoughts:
>
> We want this CISA algorithm to have the property that it doesn't require=
=20
> the blockchain (and its verifiers) to incur linear cost in the number of=
=20
> signers/signatures. For a 100 input transaction, we get big gains from th=
e=20
> owner or owners of the inputs choosing to use this algo, but that would=
=20
> mostly be lost if either the verifying was linear in the number, or if th=
e=20
> size of the signature was linear in the number. So to avoid that we want =
a=20
> (R, s) structure to be actually published, not an (R1..Rn, s) or a (R,=20
> s1..sn). That pretty much forces us to make a sum R for all the individua=
l=20
> component's R-values, and the same for s.
>
> However it doesn't quite force us to add literally everything. The pubkey=
s=20
> *can* be kept separate, because they are retrieved implicitly from the=20
> existing blockchain record, they are not published with the signature=20
> (taproot). (Technically the same comment applies to the message being=20
> signed). This allows us to use the more "pedestrian", "safe" idea; we are=
=20
> not aggregating keys (as in MuSig) so we can actually add each with its o=
wn=20
> challenge hash: sum( challenge_hash_i * X_i). This may worry you that the=
re=20
> is a performance issue because the verifier has to iterate through that=
=20
> whole list ( the verification equation being: sG =3D?=3D R + c_1 X_1 + c_=
2X_2 +=20
> .. ), but the paper specifically claims that comparing this with just bat=
ch=20
> verifying the individual signatures (i.e. without CISA), this is twice as=
=20
> fast.
>
> So one could simplistically say "OK that's the pubkey side, they're=20
> treated individually so we don't have to worry about that, but what about=
=20
> adding the R values?" ("worry" here means: trivial key subtraction attack=
s=20
> or sophisticated Wagner/ROS grinding). And here what is done is basically=
=20
> the same as in MuSig2, which is to say, by breaking the nonce into two=20
> components and including an additional challenge hash, you prevent the=20
> counterparty/adversary from grinding R values successfully. Note that the=
=20
> "b" coefficient used here is more explicit about hashing the full context=
,=20
> than it was in MuSig2: it's hashing each individual pubkey and message as=
=20
> well as the R2 subcomponents for each party. This is vaguely similar to=
=20
> "client side validation" ideas: it's not really "validation" as in state=
=20
> updates, but it's having the more complex/expensive part of the calculati=
on=20
> being done in the coordination before anything goes on-chain, and allowin=
g=20
> us to just use a single "R" value onchain that we know is safe.
>
> (Side note: it's worth remembering that a lot (maybe a huge majority?) of=
=20
> the usage of CISA will be a single signer of multiple inputs; for these=
=20
> cases there is not the same security arguments required, only that the=20
> final signature is not leaking the private key!).
>
> That side note reminds me of my first question: would it not be=20
> appropriate to include a proof of the zero knowledgeness property of the=
=20
> scheme, and not only the soundness? I can kind of accept the answer "it's=
=20
> trivial" based on the structure of the partial sig components (s_k =3D r_=
k1 +=20
> br_k2 + c_k x_k) being "identical" to baseline Schnorr?
>
> The side note also raises this point: would it be a good idea to=20
> explicitly write down ways in which the usage of the scheme/structure can=
,=20
> and cannot, be optimised for the single-party case? Intuitively it's=20
> "obvious" that you may be able to streamline it for the case where all=20
> operations happen on the same device, with a single owner of all the=20
> private keys. I realize that this is a thorny point, because we explicitl=
y=20
> want to account for the corruption of parties that are "supposed" to be t=
he=20
> same as the honest signer, but aren't.
>
> And my last question is about this multi-component-nonce technique:
>
> Did you consider the idea of e.g. sending proofs of knowledge of R along=
=20
> with R in the coordination step? This would keep the same number of round=
s,=20
> and I'm assuming (though not sure exactly) that it makes the security pro=
of=20
> significantly simpler, but my guess is you mostly dismiss such approaches=
=20
> as being too expensive for, say, constrained devices? (I imagine somethin=
g=20
> like: 2 parties say, X1 sends (R1, pi_R1) and same for X2, to coordinator=
,=20
> then sum directly for overall R; here pi_R1 is ofc just a schnorr sig on=
=20
> r). If we're talking about bandwidth the current "ctx" object is already=
=20
> pretty large, right, because it contains all the pubkeys and all the=20
> messages (though in bitcoin they could be implicit perhaps).
>
> (I won't mention the other idea, which is going back to MuSig1 style and=
=20
> just committing to R, because that's what both MuSig2 and FROST went away=
=20
> from, preferring fewer rounds.)
>
> By the way after writing this overly long post I realised I didn't even=
=20
> get in to the really tricky part of the algorithm, the "check our key and=
=20
> message appears once" part because of the multisig-to-aggregated-sig=20
> transformation and the hole previously identified in it, which to be fair=
=20
> is the most interesting bit. Oh well, another time!
>
> Cheers,
> AdamISZ/waxwing
> On Thursday, April 17, 2025 at 10:38:46=E2=80=AFAM UTC-6 Jonas Nick wrote=
:
>
>> Hi list,=20
>>
>> Cross-Input Signature Aggregation (CISA) has been a recurring topic here=
,=20
>> aiming=20
>> to reduce transaction sizes and verification cost [0]. Tim Ruffing,=20
>> Yannick=20
>> Seurin and I recently published DahLIAS, the first interactive aggregate=
=20
>> signature scheme with constant-size signatures (64 bytes) compatible wit=
h=20
>> secp256k1.=20
>>
>> https://eprint.iacr.org/2025/692.pdf=20
>>
>> Recall that in an aggregate signature scheme, each signer contributes=20
>> their own=20
>> message, which distinguishes it from multi- and threshold signatures,=20
>> where all=20
>> signers sign the same message. This makes aggregate signature schemes th=
e=20
>> natural cryptographic primitive for cross-input signature aggregation=20
>> because=20
>> each transaction input typically requires signing a different message.=
=20
>>
>> Previous candidates for constant-size aggregate signatures either:=20
>> - Required cryptographic assumptions quite different from the discrete=
=20
>> logarithm=20
>> problem on secp256k1 currently used in Bitcoin signatures (e.g., groups=
=20
>> with=20
>> efficient pairings).=20
>> - Were "folklore" constructions, lacking detailed descriptions and=20
>> security=20
>> proofs.=20
>>
>> Besides presenting DahLIAS, the paper provides a proof that a class of=
=20
>> these=20
>> folklore constructions are indeed secure if the signer does _not_ use ke=
y=20
>> tweaking (e.g., no Taproot commitments or BIP 32 derivation). Moreover,=
=20
>> we show=20
>> that there exists a concrete attack against a folklore aggregate=20
>> signature=20
>> scheme derived from MuSig2 when key tweaking is used.=20
>>
>> In contrast, DahLIAS is proven to be compatible with key tweaking.=20
>> Moreover, it=20
>> requires two rounds of communication for signing, where the first round=
=20
>> can be=20
>> run before the messages to be signed are known. Verification of DahLIAS=
=20
>> signatures is asymptotically twice as fast as half-aggregate Schnorr=20
>> signatures=20
>> and as batch verification of individual Schnorr signatures.=20
>>
>> We believe DahLIAS offers an attractive building block for a potential=
=20
>> CISA=20
>> proposal and welcome any feedback or discussion.=20
>>
>> Jonas Nick, Tim Ruffing, Yannick Seurin=20
>>
>>
>> [0] See, e.g., https://cisaresearch.org/ for a summary of various CISA=
=20
>> discussions.=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/=
604ca4d2-48c6-4fa0-baa6-329a78a02201n%40googlegroups.com.

------=_Part_32367_1051542522.1745687115956
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

On that last point about "proof of knowledge of R", I suddenly realised it'=
s not a viable suggestion: of course it defends against key subtraction att=
acks, but does not defend at all against the ability to grind nonces advers=
arially in a Wagner type attack,=C2=A0 so that you could get a forgery on t=
he victim's single key from a bunch of parallel signing sessions. So, quest=
ion retracted, there.<br /><br /><div class=3D"gmail_quote"><div dir=3D"aut=
o" class=3D"gmail_attr">On Saturday, April 26, 2025 at 10:14:36=E2=80=AFAM =
UTC-6 waxwing/ AdamISZ wrote:<br/></div><blockquote class=3D"gmail_quote" s=
tyle=3D"margin: 0 0 0 0.8ex; border-left: 1px solid rgb(204, 204, 204); pad=
ding-left: 1ex;"><div>Some comments/questions on the general structure of t=
he scheme:</div><div><br></div><div>When I started thinking about ways to c=
hange the algorithm, I started to appreciate it more :) Although this algo =
is not specific to Bitcoin I&#39;m viewing it 100% through that lens here. =
Some thoughts:</div><div><br></div><div>We want this CISA algorithm to have=
 the property that it doesn&#39;t require the blockchain (and its verifiers=
) to incur linear cost in the number of signers/signatures. For a 100 input=
 transaction, we get big gains from the owner or owners of the inputs choos=
ing to use this algo, but that would mostly be lost if either the verifying=
 was linear in the number, or if the size of the signature was linear in th=
e number. So to avoid that we want a (R, s) structure to be actually publis=
hed, not an (R1..Rn, s) or a (R, s1..sn). That pretty much forces us to mak=
e a sum R for all the individual component&#39;s R-values, and the same for=
 s.</div><div><br></div><div>However it doesn&#39;t quite force us to add l=
iterally everything. The pubkeys *can* be kept separate, because they are r=
etrieved implicitly from the existing blockchain record, they are not publi=
shed with the signature (taproot). (Technically the same comment applies to=
 the message being signed). This allows us to use the more &quot;pedestrian=
&quot;, &quot;safe&quot; idea; we are not aggregating keys (as in MuSig) so=
 we can actually add each with its own challenge hash: sum( challenge_hash_=
i * X_i). This may worry you that there is a performance issue because the =
verifier has to iterate through that whole list ( the verification equation=
 being: sG =3D?=3D R + c_1 X_1 + c_2X_2 + .. ), but the paper specifically =
claims that comparing this with just batch verifying the individual signatu=
res (i.e. without CISA), this is twice as fast.</div><div><br></div><div>So=
 one could simplistically say &quot;OK that&#39;s the pubkey side, they&#39=
;re treated individually so we don&#39;t have to worry about that, but what=
 about adding the R values?&quot; (&quot;worry&quot; here means: trivial ke=
y subtraction attacks or sophisticated Wagner/ROS grinding). And here what =
is done is basically the same as in MuSig2, which is to say, by breaking th=
e nonce into two components and including an additional challenge hash, you=
 prevent the counterparty/adversary from grinding R values successfully. No=
te that the &quot;b&quot; coefficient used here is more explicit about hash=
ing the full context, than it was in MuSig2: it&#39;s hashing each individu=
al pubkey and message as well as the R2 subcomponents for each party. This =
is vaguely similar to &quot;client side validation&quot; ideas: it&#39;s no=
t really &quot;validation&quot; as in state updates, but it&#39;s having th=
e more complex/expensive part of the calculation being done in the coordina=
tion before anything goes on-chain, and allowing us to just use a single &q=
uot;R&quot; value onchain that we know is safe.</div><div><br></div><div>(S=
ide note: it&#39;s worth remembering that a lot (maybe a huge majority?) of=
 the usage of CISA will be a single signer of multiple inputs; for these ca=
ses there is not the same security arguments required, only that the final =
signature is not leaking the private key!).</div><div><br></div><div>That s=
ide note reminds me of my first question: would it not be appropriate to in=
clude a proof of the zero knowledgeness property of the scheme, and not onl=
y the soundness? I can kind of accept the answer &quot;it&#39;s trivial&quo=
t; based on the structure of the partial sig components (s_k =3D r_k1 + br_=
k2 + c_k x_k) being &quot;identical&quot; to baseline Schnorr?</div><div><b=
r></div><div>The side note also raises this point: would it be a good idea =
to explicitly write down ways in which the usage of the scheme/structure ca=
n, and cannot, be optimised for the single-party case? Intuitively it&#39;s=
 &quot;obvious&quot; that you may be able to streamline it for the case whe=
re all operations happen on the same device, with a single owner of all the=
 private keys. I realize that this is a thorny point, because we explicitly=
 want to account for the corruption of parties that are &quot;supposed&quot=
; to be the same as the honest signer, but aren&#39;t.</div><div><br></div>=
<div>And my last question is about this multi-component-nonce technique:</d=
iv><div><br></div><div>Did you consider the idea of e.g. sending proofs of =
knowledge of R along with R in the coordination step? This would keep the s=
ame number of rounds, and I&#39;m assuming (though not sure exactly) that i=
t makes the security proof significantly simpler, but my guess is you mostl=
y dismiss such approaches as being too expensive for, say, constrained devi=
ces? (I imagine something like: 2 parties say, X1 sends (R1, pi_R1) and sam=
e for X2, to coordinator, then sum directly for overall R; here pi_R1 is of=
c just a schnorr sig on r). If we&#39;re talking about bandwidth the curren=
t &quot;ctx&quot; object is already pretty large, right, because it contain=
s all the pubkeys and all the messages (though in bitcoin they could be imp=
licit perhaps).</div><div><br></div><div>(I won&#39;t mention the other ide=
a, which is going back to MuSig1 style and just committing to R, because th=
at&#39;s what both MuSig2 and FROST went away from, preferring fewer rounds=
.)</div><div><br></div><div>By the way after writing this overly long post =
I realised I didn&#39;t even get in to the really tricky part of the algori=
thm, the &quot;check our key and message appears once&quot; part because of=
 the multisig-to-aggregated-sig transformation and the hole previously iden=
tified in it, which to be fair is the most interesting bit. Oh well, anothe=
r time!</div><div><br></div><div>Cheers,</div><div>AdamISZ/waxwing</div><di=
v class=3D"gmail_quote"></div><div class=3D"gmail_quote"><div dir=3D"auto" =
class=3D"gmail_attr">On Thursday, April 17, 2025 at 10:38:46=E2=80=AFAM UTC=
-6 Jonas Nick wrote:<br></div></div><div class=3D"gmail_quote"><blockquote =
class=3D"gmail_quote" style=3D"margin:0 0 0 0.8ex;border-left:1px solid rgb=
(204,204,204);padding-left:1ex">Hi list,
<br>
<br>Cross-Input Signature Aggregation (CISA) has been a recurring topic her=
e, aiming
<br>to reduce transaction sizes and verification cost [0]. Tim Ruffing, Yan=
nick
<br>Seurin and I recently published DahLIAS, the first interactive aggregat=
e
<br>signature scheme with constant-size signatures (64 bytes) compatible wi=
th
<br>secp256k1.
<br>
<br><a href=3D"https://eprint.iacr.org/2025/692.pdf" rel=3D"nofollow" targe=
t=3D"_blank" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&amp=
;q=3Dhttps://eprint.iacr.org/2025/692.pdf&amp;source=3Dgmail&amp;ust=3D1745=
772037681000&amp;usg=3DAOvVaw1vd3zF_KLluWFbfpY5qm7j">https://eprint.iacr.or=
g/2025/692.pdf</a>
<br>
<br>Recall that in an aggregate signature scheme, each signer contributes t=
heir own
<br>message, which distinguishes it from multi- and threshold signatures, w=
here all
<br>signers sign the same message. This makes aggregate signature schemes t=
he
<br>natural cryptographic primitive for cross-input signature aggregation b=
ecause
<br>each transaction input typically requires signing a different message.
<br>
<br>Previous candidates for constant-size aggregate signatures either:
<br>- Required cryptographic assumptions quite different from the discrete =
logarithm
<br>   problem on secp256k1 currently used in Bitcoin signatures (e.g., gro=
ups with
<br>   efficient pairings).
<br>- Were &quot;folklore&quot; constructions, lacking detailed description=
s and security
<br>   proofs.
<br>
<br>Besides presenting DahLIAS, the paper provides a proof that a class of =
these
<br>folklore constructions are indeed secure if the signer does _not_ use k=
ey
<br>tweaking (e.g., no Taproot commitments or BIP 32 derivation). Moreover,=
 we show
<br>that there exists a concrete attack against a folklore aggregate signat=
ure
<br>scheme derived from MuSig2 when key tweaking is used.
<br>
<br>In contrast, DahLIAS is proven to be compatible with key tweaking. More=
over, it
<br>requires two rounds of communication for signing, where the first round=
 can be
<br>run before the messages to be signed are known. Verification of DahLIAS
<br>signatures is asymptotically twice as fast as half-aggregate Schnorr si=
gnatures
<br>and as batch verification of individual Schnorr signatures.
<br>
<br>We believe DahLIAS offers an attractive building block for a potential =
CISA
<br>proposal and welcome any feedback or discussion.
<br>
<br>Jonas Nick, Tim Ruffing, Yannick Seurin
<br>
<br>
<br>[0] See, e.g., <a href=3D"https://cisaresearch.org/" rel=3D"nofollow" t=
arget=3D"_blank" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den=
&amp;q=3Dhttps://cisaresearch.org/&amp;source=3Dgmail&amp;ust=3D17457720376=
81000&amp;usg=3DAOvVaw1j1lUH47B9z8Np_UgA32zE">https://cisaresearch.org/</a>=
 for a summary of various CISA
<br>     discussions.
<br></blockquote></div></blockquote></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/604ca4d2-48c6-4fa0-baa6-329a78a02201n%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/604ca4d2-48c6-4fa0-baa6-329a78a02201n%40googlegroups.com</a>.<br />

------=_Part_32367_1051542522.1745687115956--

------=_Part_32366_1712149344.1745687115956--