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--