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 ) 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 ; 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 To: Bitcoin Development Mailing List Message-Id: In-Reply-To: References: 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: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , 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
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?

Thanks,
A= damISZ/waxwing

On Thursday, April 17, 2025 at 10:38:46=E2=80=AFAM UTC-6 J= onas Nick wrote:
Hi list,

Cross-Input Signature Aggregation (CISA) has been a recurring topic her= e, aiming
to reduce transaction sizes and verification cost [0]. Tim Ruffing, Yan= nick
Seurin and I recently published DahLIAS, the first interactive aggregat= e
signature scheme with constant-size signatures (64 bytes) compatible wi= th
secp256k1.

https://eprint.iacr.o= rg/2025/692.pdf

Recall that in an aggregate signature scheme, each signer contributes t= heir own
message, which distinguishes it from multi- and threshold signatures, w= here all
signers sign the same message. This makes aggregate signature schemes t= he
natural cryptographic primitive for cross-input signature aggregation b= ecause
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 = logarithm
problem on secp256k1 currently used in Bitcoin signatures (e.g., gro= ups with
efficient pairings).
- Were "folklore" constructions, lacking detailed description= s and security
proofs.

Besides presenting DahLIAS, the paper provides a proof that a class of = these
folklore constructions are indeed secure if the signer does _not_ use k= ey
tweaking (e.g., no Taproot commitments or BIP 32 derivation). Moreover,= we show
that there exists a concrete attack against a folklore aggregate signat= ure
scheme derived from MuSig2 when key tweaking is used.

In contrast, DahLIAS is proven to be compatible with key tweaking. More= over, it
requires two rounds of communication for signing, where the first round= can be
run before the messages to be signed are known. Verification of DahLIAS
signatures is asymptotically twice as fast as half-aggregate Schnorr si= gnatures
and as batch verification of individual Schnorr signatures.

We believe DahLIAS offers an attractive building block for a potential = CISA
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.

--
You received this message because you are subscribed to the Google Groups &= quot;Bitcoin Development Mailing List" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to bitcoind= ev+unsubscribe@googlegroups.com.
To view this discussion visit https://groups.google.com/d/msgid/bitcoind= ev/ffbf7fe1-8250-4db7-9ae6-21f0b1984b3an%40googlegroups.com.
------=_Part_96825_1224832642.1745597306536-- ------=_Part_96824_1472148329.1745597306536--