Delivery-date: Sat, 26 Apr 2025 09:14:44 -0700
Sender: bitcoindev@googlegroups.com
Date: Sat, 26 Apr 2025 08:30:52 -0700 (PDT)
From: waxwing/ AdamISZ <ekaggata@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <039cb943-5c94-44ba-929b-abec281082a8n@googlegroups.com>
In-Reply-To: <be3813bf-467d-4880-9383-2a0b0223e7e5@gmail.com>
References: <be3813bf-467d-4880-9383-2a0b0223e7e5@gmail.com>
Subject: [bitcoindev] Re: DahLIAS: Discrete Logarithm-Based Interactive
 Aggregate Signatures
MIME-Version: 1.0
Content-Type: multipart/mixed; 
	boundary="----=_Part_63930_85546993.1745681452380"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

------=_Part_63930_85546993.1745681452380
Content-Type: multipart/alternative; 
	boundary="----=_Part_63931_1260739144.1745681452380"

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

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 the=
=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 the=
=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 individual=
=20
component's R-values, and the same for s.

However it doesn't quite force us to add literally everything. The pubkeys=
=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 own=
=20
challenge hash: sum( challenge_hash_i * X_i). This may worry you that there=
=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 batch=
=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 treated=
=20
individually so we don't have to worry about that, but what about adding=20
the R values?" ("worry" here means: trivial key subtraction attacks or=20
sophisticated Wagner/ROS grinding). And here what is done is basically the=
=20
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 calculation=
=20
being done in the coordination before anything goes on-chain, and allowing=
=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 appropriate=
=20
to include a proof of the zero knowledgeness property of the scheme, and=20
not only the soundness? I can kind of accept the answer "it's trivial"=20
based on the structure of the partial sig components (s_k =3D r_k1 + br_k2 =
+=20
c_k x_k) being "identical" to baseline Schnorr?

The side note also raises this point: would it be a good idea to explicitly=
=20
write down ways in which the usage of the scheme/structure can, and cannot,=
=20
be optimised for the single-party case? Intuitively it's "obvious" that you=
=20
may be able to streamline it for the case where all operations happen on=20
the same device, with a single owner of all the private keys. I realize=20
that this is a thorny point, because we explicitly want to account for the=
=20
corruption of parties that are "supposed" to be the same as the honest=20
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 rounds,=
=20
and I'm assuming (though not sure exactly) that it makes the security proof=
=20
significantly simpler, but my guess is you mostly dismiss such approaches=
=20
as being too expensive for, say, constrained devices? (I imagine something=
=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 get=
=20
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,
>
> Cross-Input Signature Aggregation (CISA) has been a recurring topic here,=
=20
> aiming
> to reduce transaction sizes and verification cost [0]. Tim Ruffing, Yanni=
ck
> Seurin and I recently published DahLIAS, the first interactive aggregate
> signature scheme with constant-size signatures (64 bytes) compatible with
> secp256k1.
>
> https://eprint.iacr.org/2025/692.pdf
>
> Recall that in an aggregate signature scheme, each signer contributes=20
> their own
> message, which distinguishes it from multi- and threshold signatures,=20
> where all
> signers sign the same message. This makes aggregate signature schemes the
> natural cryptographic primitive for cross-input signature aggregation=20
> because
> each transaction input typically requires signing a different message.
>
> Previous candidates for constant-size aggregate signatures either:
> - Required cryptographic assumptions quite different from the discrete=20
> logarithm
> problem on secp256k1 currently used in Bitcoin signatures (e.g., groups=
=20
> with
> efficient pairings).
> - Were "folklore" constructions, lacking detailed descriptions and securi=
ty
> proofs.
>
> Besides presenting DahLIAS, the paper provides a proof that a class of=20
> these
> folklore constructions are indeed secure if the signer does _not_ use key
> tweaking (e.g., no Taproot commitments or BIP 32 derivation). Moreover, w=
e=20
> show
> that there exists a concrete attack against a folklore aggregate signatur=
e
> scheme derived from MuSig2 when key tweaking is used.
>
> In contrast, DahLIAS is proven to be compatible with key tweaking.=20
> Moreover, it
> requires two rounds of communication for signing, where the first round=
=20
> can be
> run before the messages to be signed are known. Verification of DahLIAS
> signatures is asymptotically twice as fast as half-aggregate Schnorr=20
> signatures
> and as batch verification of individual Schnorr signatures.
>
> We believe DahLIAS offers an attractive building block for a potential CI=
SA
> proposal and welcome any feedback or discussion.
>
> Jonas Nick, Tim Ruffing, Yannick Seurin
>
>
> [0] See, e.g., https://cisaresearch.org/ for a summary of various CISA
> discussions.
>

--=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/=
039cb943-5c94-44ba-929b-abec281082a8n%40googlegroups.com.

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

<div>Some comments/questions on the general structure of the scheme:</div><=
div><br /></div><div>When I started thinking about ways to change the algor=
ithm, I started to appreciate it more :) Although this algo is not specific=
 to Bitcoin I'm viewing it 100% through that lens here. Some thoughts:</div=
><div><br /></div><div>We want this CISA algorithm to have the property tha=
t it doesn't require the blockchain (and its verifiers) to incur linear cos=
t in the number of signers/signatures. For a 100 input transaction, we get =
big gains from the owner or owners of the inputs choosing to use this algo,=
 but that would mostly be lost if either the verifying was linear in the nu=
mber, or if the size of the signature was linear in the number. So to avoid=
 that we want a (R, s) structure to be actually published, not an (R1..Rn, =
s) or a (R, s1..sn). That pretty much forces us to make a sum R for all the=
 individual component's R-values, and the same for s.</div><div><br /></div=
><div>However it doesn't quite force us to add literally everything. The pu=
bkeys *can* be kept separate, because they are retrieved implicitly from th=
e existing blockchain record, they are not published with the signature (ta=
proot). (Technically the same comment applies to the message being signed).=
 This allows us to use the more "pedestrian", "safe" idea; we are not aggre=
gating keys (as in MuSig) so we can actually add each with its own challeng=
e hash: sum( challenge_hash_i * X_i). This may worry you that there is a pe=
rformance 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 veri=
fying the individual signatures (i.e. without CISA), this is twice as fast.=
</div><div><br /></div><div>So one could simplistically say "OK that's the =
pubkey side, they're treated individually so we don't have to worry about t=
hat, but what about adding the R values?" ("worry" here means: trivial key =
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 the =
nonce into two components and including an additional challenge hash, you p=
revent the counterparty/adversary from grinding R values successfully. Note=
 that the "b" coefficient used here is more explicit about hashing the full=
 context, than it was in MuSig2: it's hashing each individual pubkey and me=
ssage as well as the R2 subcomponents for each party. This is vaguely simil=
ar to "client side validation" ideas: it's not really "validation" as in st=
ate updates, but it's having the more complex/expensive part of the calcula=
tion being done in the coordination before anything goes on-chain, and allo=
wing us to just use a single "R" value onchain that we know is safe.</div><=
div><br /></div><div>(Side note: it's worth remembering that a lot (maybe a=
 huge majority?) of the usage of CISA will be a single signer of multiple i=
nputs; for these cases there is not the same security arguments required, o=
nly that the final signature is not leaking the private key!).</div><div><b=
r /></div><div>That side note reminds me of my first question: would it not=
 be appropriate to include a proof of the zero knowledgeness property of th=
e scheme, and not only the soundness? I can kind of accept the answer "it's=
 trivial" based on the structure of the partial sig components (s_k =3D r_k=
1 + br_k2 + c_k x_k) being "identical" to baseline Schnorr?</div><div><br /=
></div><div>The side note also raises this point: would it be a good idea t=
o explicitly write down ways in which the usage of the scheme/structure can=
, and cannot, be optimised for the single-party case? Intuitively it's "obv=
ious" that you may be able to streamline it for the case where all operatio=
ns 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 accoun=
t for the corruption of parties that are "supposed" to be the same as the h=
onest signer, but aren't.</div><div><br /></div><div>And my last question i=
s about this multi-component-nonce technique:</div><div><br /></div><div>Di=
d you consider the idea of e.g. sending proofs of knowledge of R along with=
 R in the coordination step? This would keep the same number of rounds, and=
 I'm assuming (though not sure exactly) that it makes the security proof si=
gnificantly simpler, but my guess is you mostly dismiss such approaches as =
being too expensive for, say, constrained devices? (I imagine something lik=
e: 2 parties say, X1 sends (R1, pi_R1) and same for X2, to coordinator, the=
n sum directly for overall R; here pi_R1 is ofc just a schnorr sig on r). I=
f we're talking about bandwidth the current "ctx" object is already pretty =
large, right, because it contains all the pubkeys and all the messages (tho=
ugh in bitcoin they could be implicit perhaps).</div><div><br /></div><div>=
(I won't mention the other idea, which is going back to MuSig1 style and ju=
st committing to R, because that's what both MuSig2 and FROST went away fro=
m, preferring fewer rounds.)</div><div><br /></div><div>By the way after wr=
iting this overly long post I realised I didn't even get in to the really t=
ricky part of the algorithm, the "check our key and message appears once" p=
art because of the multisig-to-aggregated-sig transformation and the hole p=
reviously identified in it, which to be fair is the most interesting bit. O=
h well, another time!</div><div><br /></div><div>Cheers,</div><div>AdamISZ/=
waxwing</div><div class=3D"gmail_quote"><div dir=3D"auto" class=3D"gmail_at=
tr">On Thursday, April 17, 2025 at 10:38:46=E2=80=AFAM UTC-6 Jonas Nick wro=
te:<br/></div><blockquote class=3D"gmail_quote" style=3D"margin: 0 0 0 0.8e=
x; 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" target=3D"_blank" rel=
=3D"nofollow" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&am=
p;q=3Dhttps://eprint.iacr.org/2025/692.pdf&amp;source=3Dgmail&amp;ust=3D174=
5763806761000&amp;usg=3DAOvVaw2EtjcO7fqg6JikIOowq85H">https://eprint.iacr.o=
rg/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/" target=3D"_blank" =
rel=3D"nofollow" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den=
&amp;q=3Dhttps://cisaresearch.org/&amp;source=3Dgmail&amp;ust=3D17457638067=
61000&amp;usg=3DAOvVaw2JSE03N5G02-3HEV2G6Yjm">https://cisaresearch.org/</a>=
 for a summary of various CISA
<br>     discussions.
<br></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/039cb943-5c94-44ba-929b-abec281082a8n%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/039cb943-5c94-44ba-929b-abec281082a8n%40googlegroups.com</a>.<br />

------=_Part_63931_1260739144.1745681452380--

------=_Part_63930_85546993.1745681452380--