Delivery-date: Fri, 25 Apr 2025 09:13:38 -0700
Sender: bitcoindev@googlegroups.com
Date: Fri, 25 Apr 2025 09:08:26 -0700 (PDT)
From: waxwing/ AdamISZ <ekaggata@gmail.com>
To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com>
Message-Id: <ffbf7fe1-8250-4db7-9ae6-21f0b1984b3an@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_96824_1472148329.1745597306536"
Precedence: list
Mailing-list: list bitcoindev@googlegroups.com; contact bitcoindev+owners@googlegroups.com

------=_Part_96824_1472148329.1745597306536
Content-Type: multipart/alternative; 
	boundary="----=_Part_96825_1224832642.1745597306536"

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

I'm struggling to understand one detail in DahLIA's algorithm: the use of=
=20
R2 as a check and not R1 (or both). Is it just that only one is needed? Is=
=20
it just an optimization?

Thanks,
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/=
ffbf7fe1-8250-4db7-9ae6-21f0b1984b3an%40googlegroups.com.

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

<div>I'm struggling to understand one detail in DahLIA's algorithm: the use=
 of R2 as a check and not R1 (or both). Is it just that only one is needed?=
 Is it just an optimization?</div><div><br /></div><div>Thanks,</div><div>A=
damISZ/waxwing</div><br /><div class=3D"gmail_quote"><div dir=3D"auto" clas=
s=3D"gmail_attr">On Thursday, April 17, 2025 at 10:38:46=E2=80=AFAM UTC-6 J=
onas Nick wrote:<br/></div><blockquote class=3D"gmail_quote" style=3D"margi=
n: 0 0 0 0.8ex; border-left: 1px solid rgb(204, 204, 204); padding-left: 1e=
x;">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=
5509675199000&amp;usg=3DAOvVaw1LOejxT_6ki8xcN9TejHKg">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=3D17455096751=
99000&amp;usg=3DAOvVaw1wuOWExWKuoWn_TQu4Z-PK">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/ffbf7fe1-8250-4db7-9ae6-21f0b1984b3an%40googlegroups.com?utm_med=
ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind=
ev/ffbf7fe1-8250-4db7-9ae6-21f0b1984b3an%40googlegroups.com</a>.<br />

------=_Part_96825_1224832642.1745597306536--

------=_Part_96824_1472148329.1745597306536--