From mboxrd@z Thu Jan 1 00:00:00 1970
Delivery-date: Fri, 25 Apr 2025 09:13:38 -0700
Received: from mail-yb1-f191.google.com ([209.85.219.191])
by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256
(Exim 4.94.2)
(envelope-from <bitcoindev+bncBDI23FE35EIBBJPJV3AAMGQE7KYKCLA@googlegroups.com>)
id 1u8LgH-0002Xd-TM
for bitcoindev@gnusha.org; Fri, 25 Apr 2025 09:13:38 -0700
Received: by mail-yb1-f191.google.com with SMTP id 3f1490d57ef6-e6de6e05450sf490768276.1
for <bitcoindev@gnusha.org>; Fri, 25 Apr 2025 09:13:38 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=googlegroups.com; s=20230601; t=1745597612; x=1746202412; 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=0BKcYlFwBkU6a4RvHvxEOuOJOvaMEMViOBbGHV/yR3A=;
b=vWoqE168s4w+gpWi/NQWgBUqduLnENd9fCSpUyAXTON8G2QIMG33DvTes450WbFvkP
rSQYR2u14O+o7mAzoK3T70cR2gQk4oMNXgsyarbR5s41g5UGXRtFYLPVMqxbkgxJfwhH
dWPYycketsg9pBuqf5L/ihQvZ/ytI6QxLfi/p6o2TFSOqbhpIQiFm76YsLLGZdi8qnmc
MTx2A4KaEWj9n3emfgmHv6p6ipELIBMgC5rsdHh9IVi7yZ49WX2uIzh5/o7WQ33UgGeO
rvrU2tLvKpLDxWgFX2LUgXfzh+v6pqEnBlo1YeDJlyPhS7pTjtYZZ8PXs8BPP7qaRzf7
eaOA==
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=gmail.com; s=20230601; t=1745597612; x=1746202412; 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=0BKcYlFwBkU6a4RvHvxEOuOJOvaMEMViOBbGHV/yR3A=;
b=kFrUkaU7pmAC2ipf56A57sP5aDeovWcfz/ByEReOBkHSSEwk8kePQ2Na0e0dlphDlD
MNAlHOYI3GYGglxq0jJf1fVhIaOiZ+6RmUn+VCrPxICrePV4mVGK1sjERZz/iTn6flRu
+vwf+vhwRao3HSKYivQaeE7yefONkv9SwQ1OsCO9QY9NKM+24yvUsbaDrZm6/c/9AaZh
pLwcn6qA5WUGH3NSnRXCdxnphShZVMgDTvvyA1TjryiMgEk3kustcUFCKb3yYtYD/geH
5eowB8LGMhvzonO1k8rBdMygkk6RvjGEl5YU7sK0y9ZJE6zi+/rsEDTYCxSKvCSFQB1N
cFaQ==
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
d=1e100.net; s=20230601; t=1745597612; x=1746202412;
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=0BKcYlFwBkU6a4RvHvxEOuOJOvaMEMViOBbGHV/yR3A=;
b=KUxrdVrKU6oIEMfEIRCtAHplt4fmFip9dOGI6MELkx4bWCFxoIKN1vW9KVvCJ9rHmh
yVW1J5gLcjUbPV96QUyYjhTqz8u6I/NtpH0b3IO+5L034+92ngMwgegS3ItNI8+hHUuH
I2vsuU76pq7gqydOBQfpBXjzMIF0AZWQ8IkUL/19kCzz7tjnNBNWReT0pF6iArAywoYn
pX9QFNm2SnHdcFLCoL1CWi/UbQylf3xA5txqRsPSoYLCj09boaNUkl0r77XGr9OC4yIq
POuKn43myiLCTOeuos/b5cAWgi61zVk9U6eCOcOMz7jwQfihId0Kj85G+fiTEKPC08zB
D2ug==
Sender: bitcoindev@googlegroups.com
X-Forwarded-Encrypted: i=1; AJvYcCXTBYSkaOZK+qcbHQS5elKr1PyPSu9zRQdqL4OzoPu3mHqMyn77JdrDsOIW0CD2LbEscWYniHlHBKIn@gnusha.org
X-Gm-Message-State: AOJu0Yx0XK6UgLVfDR3s84Gg0BO+bxz6TBWPbbh8nsN4Fs8Lf6UK6Pwq
DtkS8mhvlKN90k1fiXvAYG+p0WX3kuhI5hw4PCDBJUEHkLR4kXP8
X-Google-Smtp-Source: AGHT+IHIb429pjkYwcV+WAhPtDPpJOjcMMGUGIXLt9Zc1loTBmjiCkBXxXeC3n6gc29nirsbSCJ8Tg==
X-Received: by 2002:a05:6902:150c:b0:e73:1804:5b6 with SMTP id 3f1490d57ef6-e7318041c59mr1348207276.7.1745597611654;
Fri, 25 Apr 2025 09:13:31 -0700 (PDT)
X-BeenThere: bitcoindev@googlegroups.com; h=AVT/gBGkcCxhDury+evV00LhXhmT5vvoHBlzc5Q7Pu+BHzlM2Q==
Received: by 2002:a25:b128:0:b0:e72:89f3:c184 with SMTP id 3f1490d57ef6-e730820ac98ls70110276.0.-pod-prod-03-us;
Fri, 25 Apr 2025 09:13:25 -0700 (PDT)
X-Received: by 2002:a05:690c:b92:b0:6fe:b7ed:9715 with SMTP id 00721157ae682-708540ece89mr42982627b3.11.1745597605394;
Fri, 25 Apr 2025 09:13:25 -0700 (PDT)
Received: by 2002:a05:690c:6e93:b0:6ef:590d:3213 with SMTP id 00721157ae682-70854a7d3bams7b3;
Fri, 25 Apr 2025 09:08:28 -0700 (PDT)
X-Received: by 2002:a05:690c:ed6:b0:702:4eac:175f with SMTP id 00721157ae682-708541ff11dmr39187047b3.31.1745597307046;
Fri, 25 Apr 2025 09:08:27 -0700 (PDT)
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"
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_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&source=3Dgmail&ust=3D174=
5509675199000&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 "folklore" 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=
&q=3Dhttps://cisaresearch.org/&source=3Dgmail&ust=3D17455096751=
99000&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" 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--