From mboxrd@z Thu Jan 1 00:00:00 1970 Delivery-date: Thu, 17 Apr 2025 09:38:52 -0700 Received: from mail-oa1-f57.google.com ([209.85.160.57]) by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 (Exim 4.94.2) (envelope-from ) id 1u5SGJ-0008Ef-Tn for bitcoindev@gnusha.org; Thu, 17 Apr 2025 09:38:52 -0700 Received: by mail-oa1-f57.google.com with SMTP id 586e51a60fabf-2cc00fc06fdsf797667fac.2 for ; Thu, 17 Apr 2025 09:38:52 -0700 (PDT) ARC-Seal: i=2; a=rsa-sha256; t=1744907926; cv=pass; d=google.com; s=arc-20240605; b=VRYHxCGQW1fsmELDOiv7e46z0XvFHgbfUe/oNkkdvxindTtWbJt68tjcoywuz0dR3d MIezYPXb3oPFzl6qp4GhjGgjAn4dhvJU4uMxnfyZgW9clkW/145NLNba6fhYaEOl/Cg1 vUQ/abOEwSQaXx9Cgyp7878kOoQlbMkTuzvC2fCKgfbeGRpCC9C7YGbdBg+Or5IL1F8p A6CiALofulfwbTcctKoZKoN+5/lG47If6BJ5Pn3Csl9OE/TLw95VI7lkpzmf5j0a80z0 Ktc3zcjTUEHHKbT/8je9lV8TCBT8OmlrPH1Riwu4mXOsZ5pyMgJrZgL/9RmKgaCTWjHm wshQ== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:subject:from:to:content-language :user-agent:mime-version:date:message-id:sender:dkim-signature; bh=fsDJ3KAcXXlfeX6t1jEjjOqZCcvZJhsYqJntwheszIU=; fh=mQeUe5VpuU1BuKbKf6hvxik0kCQJIiYk0g5TM3k+7PY=; b=XB7Z3/PhD0bpVjJeCkffwaQC5hVG/i+KXWJt4HvtnQu4Epn5Qbg3aQpgBnoDKevm8A RjXkcXBK0Y5iRgNUrhKmcNoP5tg71fCcpAY3/OwzJV870E0j8ftYzYYc+5QY9wIP+HSZ P+YHfYpvfpqBS64/5t0ZGun/S/MdOvJRG2iUcUs3UO8KfN3kR2mXAzuhvc1QQwknjDPG wMr79VQumffn4sWX+uQdNIl4PbGC2av4+v6v6RlMLhUX0JX5NoIfmUGcgLreCVBlnPKX kUr4Q1Zmmdpw5FRbiuIk1MaHay042zjaQibABL1YdVaT6gRamv9xE5/gDv9UHWhfBNNf FJeQ==; darn=gnusha.org ARC-Authentication-Results: i=2; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=ZYUsD9Gu; spf=pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::329 as permitted sender) smtp.mailfrom=jonasd.nick@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1744907926; x=1745512726; darn=gnusha.org; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:subject:from:to:content-language:user-agent :mime-version:date:message-id:sender:from:to:cc:subject:date :message-id:reply-to; bh=fsDJ3KAcXXlfeX6t1jEjjOqZCcvZJhsYqJntwheszIU=; b=TLxctsEQUhdNW++qYVI/KO0csopYOdFv1XYJv7EnGsQj5b9Dfv6nBFEu0XelbTffat aDpjbgGY6qALhGKtr6z/Pw2NJ+RmxictlW+SxisXuHEeo90PjOPoV5VykX4inZDX7Cxh SjmqaaaSqDTC2QwTdSC3ObltG1k4tlsS7jbP1uqmOCa2N6fTyI/5JcE/qtXTncW5ZBso 5lc1AQyAGtgBaA6zZlQ3NMVLr4Bz4H08+d6ijJHOXBZU32JSFAxtSl4FJomEmKr+thoc ZsOg4yJE5lcC7Fm5T7EFX8wt1XhcRKTbZp+9yGLydMK90AfSNMXV9vA9UDXozTIcU4rN 2abQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1744907926; x=1745512726; h=list-unsubscribe:list-subscribe:list-archive:list-help:list-post :list-id:mailing-list:precedence:x-original-authentication-results :x-original-sender:subject:from:to:content-language:user-agent :mime-version:date:message-id:sender:x-beenthere:x-gm-message-state :from:to:cc:subject:date:message-id:reply-to; bh=fsDJ3KAcXXlfeX6t1jEjjOqZCcvZJhsYqJntwheszIU=; b=fg7mHtxkML9j0zLYvaTK5Fk9Qvw2OXcPvmkcx8nMlY1fR1NtVV8Ig6S5E7gRmUY41u 8p2FDxqWyO/R1qT/FLZEshG8FsKP8JAldtpDAppY9BkhiuCIVBV7c+BjxvY0xQUSps5j 8i8od8iBBWXPla/yDM2uBH+Y522LnX6zGvD6psuB5LkaPpni9KDUIRnwRrn3hCzRrnlh 5oGT1UHRv6GYeSiOFvzqQa36DYjBiLGAQVPqHcw3ziCHsGQTYDzIH5hDaqyUADo/yzto CUXm4LbTwt0AA4QUGmkMF8eF8KLG31EJFic1PJ7iA/WLP+WOrYY/kCaCIkTDrx4YcBNR ceyA== X-Forwarded-Encrypted: i=2; AJvYcCVNKRzA3ItQScxBJJvVbZccNYi/MoNVd0nEai/ISUHhLLXc8xoRam7+Rh/pA1otiHw+vksYfMulaNT6@gnusha.org X-Gm-Message-State: AOJu0YwjgjWaYXaa0W33kbfrIXWJmSYr9B7qfJNIPMwDFBYW8vX/2Nyb nclrFBj7ePAlTq8V63E41g8QCgWbizAsf59/wW3eDbbdiH6xM3+j X-Google-Smtp-Source: AGHT+IHoJljZMQCRzmpCP3Bp0EiZAaxCMyQ8MQoH60O6RmkIpM+yAFDIcpEkQbizsEv6B4uL/1Hx2w== X-Received: by 2002:a05:6871:848a:b0:2a3:8331:717c with SMTP id 586e51a60fabf-2d4d2a920e3mr4035679fac.10.1744907926076; Thu, 17 Apr 2025 09:38:46 -0700 (PDT) X-BeenThere: bitcoindev@googlegroups.com; h=ARLLPAJ/pHV3A4d7xzcsXUi9oMBT4x0HHutq71gL8bRXXkB4wQ== Received: by 2002:a05:6871:6502:b0:2c2:35f3:8a19 with SMTP id 586e51a60fabf-2d4eb9eb6c8ls947737fac.0.-pod-prod-03-us; Thu, 17 Apr 2025 09:38:41 -0700 (PDT) X-Received: by 2002:a05:6808:250a:b0:3f8:498c:9ef4 with SMTP id 5614622812f47-400b021ac4emr3492732b6e.24.1744907921083; Thu, 17 Apr 2025 09:38:41 -0700 (PDT) Received: by 2002:ab3:1084:0:b0:293:3256:5107 with SMTP id a1c4a302cd1d6-29f11a50a26msc7a; Thu, 17 Apr 2025 09:27:08 -0700 (PDT) X-Received: by 2002:ac2:4e16:0:b0:54a:c4af:15 with SMTP id 2adb3069b0e04-54d6dc9f0e2mr159292e87.19.1744907226423; Thu, 17 Apr 2025 09:27:06 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1744907226; cv=none; d=google.com; s=arc-20240605; b=VpXAIcvWgisJZIg2AWfcHPH5DVtBEnKIH1jL3GCJZvDPitB2ZMMDBgjCKiKOAgm482 W74cq+HwzhLS8p89g/Ht4otdtvKvezP4FFtcavLBkJuUt9Y+l0I5iDOy41Rftl43qpCh tgCKT7W+sXTxEj5gJglmL8MnY/ZtMcHK7VzlwLx6r4JRWJM9D9oyG6+VGipQ3qSuimBV yc7siUSZStUlkzWmYMOBe77+30Oj8Z+h1vZaoMdc12FCqSr66nMG5RF2pMFiDJdEOlvI eaF5XQVuQmTE9EbNdXTBcse3JtrKk1cEuMDJA9lr9HBddZBDygPlFphm5fovPxt9z4+s cEsQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20240605; h=content-transfer-encoding:subject:from:to:content-language :user-agent:mime-version:date:message-id:sender:dkim-signature; bh=3X0PXU7CSA+1bgKzW2aHa7X13zQpBzs8wxPLfwHmw30=; fh=VcGcg+Zjs9gw1uDcHbxsAILhBAcecnbJzZRdxgKVDIc=; b=gS4gNpeMInLu9ZAxHRp4JjGhpWmBezknd0OD8z4ZhfWWJr272zIJQSCM7ovWWGkBI3 htyT0iaDMmhiWQ7zbX04+NzDOdSwbbChsqnByxvrfj1jxUb0iWEhVntfHwUvpn+kH7S8 goLUYOU0mXId2nKw3jH1dJg9GWx1R/ifJRCMwXwoDAiwa5+xhL0RlX38cqGiVWbC/Meg Dg+AnpPYnmbZ36fWSG01742zBLSJfLGBBr3dVWZhXVKpglx9/estv9Tv3T3WW9bHwVYD oohn0ygjBYU43Z8xO5Jozd/hktObMgRKE/OEYt2bC+wKKCfFbI6kSqQ7FP6VRIDJzzXW 1zBA==; dara=google.com ARC-Authentication-Results: i=1; gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=ZYUsD9Gu; spf=pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::329 as permitted sender) smtp.mailfrom=jonasd.nick@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.com Received: from mail-wm1-x329.google.com (mail-wm1-x329.google.com. [2a00:1450:4864:20::329]) by gmr-mx.google.com with ESMTPS id 2adb3069b0e04-54d6dfd5e69si749e87.8.2025.04.17.09.27.06 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 17 Apr 2025 09:27:06 -0700 (PDT) Received-SPF: pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::329 as permitted sender) client-ip=2a00:1450:4864:20::329; Received: by mail-wm1-x329.google.com with SMTP id 5b1f17b1804b1-43cf628cb14so16500185e9.1 for ; Thu, 17 Apr 2025 09:27:06 -0700 (PDT) X-Gm-Gg: ASbGnctKO7UKkgnlH4SHkzVAQ51TL2wkJuy28xjNg95HQWfE/Efg8hEecuhM17+y7Yi 8dLb8cErTl7yNRXusp161x5Fa5N2OLVrOUisxB+7xyg3Q85f0d2Ip9DMl9M6tx2maaDq04HmH+q O12KbUReeYJ5XYFAqs9nq+t09WYUAOysiR1R+RrvNnwCWqt0bN4KOHatVMJMtgIlz87wCbIQtZk QssW7lTIWDS2vvWFOkTs19ihxohZSwr68yxasIbQrEB47JMhwwCj/5F2Ym35eF+xR53/eAM4MBm TctyitM0fHHPKUKtNIOnoCTBIwVHhWeENBT9xEvnfCW1Gq2k/3ioqC/9AmgbLZAAwPVJ6aM85nU = X-Received: by 2002:a7b:cd85:0:b0:440:69f5:f179 with SMTP id 5b1f17b1804b1-44069f5f20emr1050575e9.7.1744907225661; Thu, 17 Apr 2025 09:27:05 -0700 (PDT) Received: from [10.11.10.42] (p57b13477.dip0.t-ipconnect.de. [87.177.52.119]) by smtp.googlemail.com with ESMTPSA id ffacd0b85a97d-39efa4206ecsm78162f8f.17.2025.04.17.09.27.04 for (version=TLS1_3 cipher=TLS_AES_128_GCM_SHA256 bits=128/128); Thu, 17 Apr 2025 09:27:05 -0700 (PDT) Sender: Jonas Nick Message-ID: Date: Thu, 17 Apr 2025 16:27:04 +0000 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Content-Language: en-US To: bitcoindev@googlegroups.com From: Jonas Nick Subject: [bitcoindev] DahLIAS: Discrete Logarithm-Based Interactive Aggregate Signatures Content-Type: text/plain; charset="UTF-8"; format=flowed X-Original-Sender: jonasdnick@gmail.com X-Original-Authentication-Results: gmr-mx.google.com; dkim=pass header.i=@gmail.com header.s=20230601 header.b=ZYUsD9Gu; spf=pass (google.com: domain of jonasd.nick@gmail.com designates 2a00:1450:4864:20::329 as permitted sender) smtp.mailfrom=jonasd.nick@gmail.com; dmarc=pass (p=NONE sp=QUARANTINE dis=NONE) header.from=gmail.com; dara=pass header.i=@googlegroups.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 (/) Hi list, Cross-Input Signature Aggregation (CISA) has been a recurring topic here, aiming to reduce transaction sizes and verification cost [0]. Tim Ruffing, Yannick 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 their own message, which distinguishes it from multi- and threshold signatures, where all signers sign the same message. This makes aggregate signature schemes the natural cryptographic primitive for cross-input signature aggregation 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 logarithm problem on secp256k1 currently used in Bitcoin signatures (e.g., groups with efficient pairings). - Were "folklore" constructions, lacking detailed descriptions 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 key tweaking (e.g., no Taproot commitments or BIP 32 derivation). Moreover, we show that there exists a concrete attack against a folklore aggregate signature scheme derived from MuSig2 when key tweaking is used. In contrast, DahLIAS is proven to be compatible with key tweaking. Moreover, 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 signatures 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 "Bitcoin Development Mailing List" group. To unsubscribe from this group and stop receiving emails from it, send an email to bitcoindev+unsubscribe@googlegroups.com. To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/be3813bf-467d-4880-9383-2a0b0223e7e5%40gmail.com.