diff options
Diffstat (limited to 'c5')
| -rw-r--r-- | c5/47075fea42a5ab4036d7e9713f1f17ede3aab4 | 516 |
1 files changed, 516 insertions, 0 deletions
diff --git a/c5/47075fea42a5ab4036d7e9713f1f17ede3aab4 b/c5/47075fea42a5ab4036d7e9713f1f17ede3aab4 new file mode 100644 index 000000000..eb6ac8988 --- /dev/null +++ b/c5/47075fea42a5ab4036d7e9713f1f17ede3aab4 @@ -0,0 +1,516 @@ +Delivery-date: Sat, 26 Apr 2025 10:22:48 -0700 +Received: from mail-yw1-f183.google.com ([209.85.128.183]) + by mail.fairlystable.org with esmtps (TLS1.3) tls TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256 + (Exim 4.94.2) + (envelope-from <bitcoindev+bncBDI23FE35EIBBXFMWTAAMGQE6DZEMPQ@googlegroups.com>) + id 1u8jEk-00035n-JE + for bitcoindev@gnusha.org; Sat, 26 Apr 2025 10:22:48 -0700 +Received: by mail-yw1-f183.google.com with SMTP id 00721157ae682-7082e59b9a8sf48788147b3.2 + for <bitcoindev@gnusha.org>; Sat, 26 Apr 2025 10:22:46 -0700 (PDT) +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=googlegroups.com; s=20230601; t=1745688160; x=1746292960; 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=hotfxzwzdVtaVOWFnhE6u3hIfp/Zwfdn7J3urpMVpvE=; + b=SmkQ769sUF+vSAdDw10JD1qBp5VfFUmiO9EYgKFzmMaOpJ0aaL2NOGLmWC3VWoWV8Y + SRQFnG189qA7YbdP95uB+IVHDpz0zE8Tk0nro5yPOqKbfvdf/h1d5hHIL82i8bi9yCIj + n0Cp21+gvZYpDoLlLHZ/q7/NPRNxofDiWgat641PjCGQOw1U1RXonkEoPsDoIFn6i0Ee + Re8T/enaqMIFpZgs28U4RGYz28mznc3Va8yVpvICmSwKxP6olQMO8g7RlAatlpT1982m + ogy2SX7bS4xTyAEA/8omiBRWaNqc2+xNvkJSSaqcIfWTqKOx6fywt67wpkTaPCDp6ks/ + SODw== +DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=gmail.com; s=20230601; t=1745688160; x=1746292960; 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=hotfxzwzdVtaVOWFnhE6u3hIfp/Zwfdn7J3urpMVpvE=; + b=I5qA5I9DnJOu5yKft46uQ5mnY2fs+nRSD3BoakE7+cvae60M7fmZkdb2IEllF/bEoQ + VAj0yGYHAWYfnKpZsDk5zcYE4ZBfdhPquvBWuAPJm3rrJmq/Hb9YywjSZhikfqtp2aws + 92SzmOP0zoWXN2/XCKyhYxVnWFuBNUKY+QABL+CEhQbAlGTpwfcBPa/iBIPl0RWTFxLB + rBc0gWrkjBBtrRoR0Fpeq5UfZ3Hwf3Tmhfc/s3VqgJZt3qsrwCVEWZhIYuaiQ1T4Fy0u + grAscy20i9dF6RVovD93AYdhdPKmIGVeA3IpjqGXzIYpPIUpp6vItLmyIxAOCz8szbEg + lpag== +X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; + d=1e100.net; s=20230601; t=1745688160; x=1746292960; + 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=hotfxzwzdVtaVOWFnhE6u3hIfp/Zwfdn7J3urpMVpvE=; + b=HdirNN7WK0LpN8pIssuN3OG2Ix8bObuDWCk0NIoth2VsTs7hCHmZseDfKXXhdAlf5B + 1jPMzWznb8KYAzlPEg0ujFy6vWwWWTWuctL0eDn6lK0dYCeMWgEA2/ROXt6XC7cVURAb + MZQaEodaNUysYzKDFfu1PUqnzDzmCvHLt5LdfuQwOXu0n9ULHhmAPLo005udWCQeQpZ/ + aA8U+c/qt3WOdBZLItDYl+GYTXEKxN3B1RDJgV7FpnOMj88UfxOZSlhtyhrgop4arBxz + 8fRgyTKZfKIAyd9MhWxAdRxDKpA3zCTl1pA4pyg6bYq6kWo7YWeI+xjfJmIkcYTxfrUB + w0HQ== +Sender: bitcoindev@googlegroups.com +X-Forwarded-Encrypted: i=1; AJvYcCVDUa7VA8MPf5PblV1WsrRBGnTXP3FlZukCRC6Qk2FPz8HWGz4mSQQiYm5MOfsK7S8ESWL49SCfA0Rj@gnusha.org +X-Gm-Message-State: AOJu0YxdkrdTUtw2BEzBpuUpxbN41Eb+ALQ0TieheZq1m1iawWh2CIde + bbnsAIozOesOyjp/8D3gbMeEzogLdU5R9AmWYevidPSW9jdTH/GJ +X-Google-Smtp-Source: AGHT+IEkEv0wTBo0yPReGGsree3uysTldq4rGDrGGzLrezcaypZ5z1qIFTn2Kd6ftT1of8bOQjHIxQ== +X-Received: by 2002:a05:6902:907:b0:e61:1c56:d678 with SMTP id 3f1490d57ef6-e7316594582mr8771929276.5.1745688160231; + Sat, 26 Apr 2025 10:22:40 -0700 (PDT) +X-BeenThere: bitcoindev@googlegroups.com; h=AVT/gBFo0IBSem/6aWUdQDIPcMK8fnVqYtk6AzAcc4z1p+Vvlg== +Received: by 2002:a25:dccf:0:b0:e5b:1119:fc5b with SMTP id 3f1490d57ef6-e730820aaf7ls991606276.0.-pod-prod-06-us; + Sat, 26 Apr 2025 10:22:36 -0700 (PDT) +X-Received: by 2002:a05:690c:6c84:b0:703:ac44:d379 with SMTP id 00721157ae682-7085f1aa290mr50164247b3.22.1745688156563; + Sat, 26 Apr 2025 10:22:36 -0700 (PDT) +Received: by 2002:a05:690c:3693:b0:708:1ea1:3cd5 with SMTP id 00721157ae682-70854ddd573ms7b3; + Sat, 26 Apr 2025 10:05:17 -0700 (PDT) +X-Received: by 2002:a05:690c:6c84:b0:703:ac44:d379 with SMTP id 00721157ae682-7085f1aa290mr49464567b3.22.1745687116479; + Sat, 26 Apr 2025 10:05:16 -0700 (PDT) +Date: Sat, 26 Apr 2025 10:05:15 -0700 (PDT) +From: waxwing/ AdamISZ <ekaggata@gmail.com> +To: Bitcoin Development Mailing List <bitcoindev@googlegroups.com> +Message-Id: <604ca4d2-48c6-4fa0-baa6-329a78a02201n@googlegroups.com> +In-Reply-To: <039cb943-5c94-44ba-929b-abec281082a8n@googlegroups.com> +References: <be3813bf-467d-4880-9383-2a0b0223e7e5@gmail.com> + <039cb943-5c94-44ba-929b-abec281082a8n@googlegroups.com> +Subject: [bitcoindev] Re: DahLIAS: Discrete Logarithm-Based Interactive + Aggregate Signatures +MIME-Version: 1.0 +Content-Type: multipart/mixed; + boundary="----=_Part_32366_1712149344.1745687115956" +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_32366_1712149344.1745687115956 +Content-Type: multipart/alternative; + boundary="----=_Part_32367_1051542522.1745687115956" + +------=_Part_32367_1051542522.1745687115956 +Content-Type: text/plain; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +On that last point about "proof of knowledge of R", I suddenly realised=20 +it's not a viable suggestion: of course it defends against key subtraction= +=20 +attacks, but does not defend at all against the ability to grind nonces=20 +adversarially in a Wagner type attack, so that you could get a forgery on= +=20 +the victim's single key from a bunch of parallel signing sessions. So,=20 +question retracted, there. + +On Saturday, April 26, 2025 at 10:14:36=E2=80=AFAM UTC-6 waxwing/ AdamISZ w= +rote: + +> Some comments/questions on the general structure of the scheme: +> +> When I started thinking about ways to change the algorithm, I started to= +=20 +> appreciate it more :) Although this algo is not specific to Bitcoin I'm= +=20 +> viewing it 100% through that lens here. Some thoughts: +> +> We want this CISA algorithm to have the property that it doesn't require= +=20 +> the blockchain (and its verifiers) to incur linear cost in the number of= +=20 +> signers/signatures. For a 100 input transaction, we get big gains from th= +e=20 +> owner or owners of the inputs choosing to use this algo, but that would= +=20 +> mostly be lost if either the verifying was linear in the number, or if th= +e=20 +> size of the signature was linear in the number. So to avoid that we want = +a=20 +> (R, s) structure to be actually published, not an (R1..Rn, s) or a (R,=20 +> s1..sn). That pretty much forces us to make a sum R for all the individua= +l=20 +> component's R-values, and the same for s. +> +> However it doesn't quite force us to add literally everything. The pubkey= +s=20 +> *can* be kept separate, because they are retrieved implicitly from the=20 +> existing blockchain record, they are not published with the signature=20 +> (taproot). (Technically the same comment applies to the message being=20 +> signed). This allows us to use the more "pedestrian", "safe" idea; we are= +=20 +> not aggregating keys (as in MuSig) so we can actually add each with its o= +wn=20 +> challenge hash: sum( challenge_hash_i * X_i). This may worry you that the= +re=20 +> is a performance issue because the verifier has to iterate through that= +=20 +> whole list ( the verification equation being: sG =3D?=3D R + c_1 X_1 + c_= +2X_2 +=20 +> .. ), but the paper specifically claims that comparing this with just bat= +ch=20 +> verifying the individual signatures (i.e. without CISA), this is twice as= +=20 +> fast. +> +> So one could simplistically say "OK that's the pubkey side, they're=20 +> treated individually so we don't have to worry about that, but what about= +=20 +> adding the R values?" ("worry" here means: trivial key subtraction attack= +s=20 +> or sophisticated Wagner/ROS grinding). And here what is done is basically= +=20 +> the same as in MuSig2, which is to say, by breaking the nonce into two=20 +> components and including an additional challenge hash, you prevent the=20 +> counterparty/adversary from grinding R values successfully. Note that the= +=20 +> "b" coefficient used here is more explicit about hashing the full context= +,=20 +> than it was in MuSig2: it's hashing each individual pubkey and message as= +=20 +> well as the R2 subcomponents for each party. This is vaguely similar to= +=20 +> "client side validation" ideas: it's not really "validation" as in state= +=20 +> updates, but it's having the more complex/expensive part of the calculati= +on=20 +> being done in the coordination before anything goes on-chain, and allowin= +g=20 +> us to just use a single "R" value onchain that we know is safe. +> +> (Side note: it's worth remembering that a lot (maybe a huge majority?) of= +=20 +> the usage of CISA will be a single signer of multiple inputs; for these= +=20 +> cases there is not the same security arguments required, only that the=20 +> final signature is not leaking the private key!). +> +> That side note reminds me of my first question: would it not be=20 +> appropriate to include a proof of the zero knowledgeness property of the= +=20 +> scheme, and not only the soundness? I can kind of accept the answer "it's= +=20 +> trivial" based on the structure of the partial sig components (s_k =3D r_= +k1 +=20 +> br_k2 + c_k x_k) being "identical" to baseline Schnorr? +> +> The side note also raises this point: would it be a good idea to=20 +> explicitly write down ways in which the usage of the scheme/structure can= +,=20 +> and cannot, be optimised for the single-party case? Intuitively it's=20 +> "obvious" that you may be able to streamline it for the case where all=20 +> operations happen on the same device, with a single owner of all the=20 +> private keys. I realize that this is a thorny point, because we explicitl= +y=20 +> want to account for the corruption of parties that are "supposed" to be t= +he=20 +> same as the honest signer, but aren't. +> +> And my last question is about this multi-component-nonce technique: +> +> Did you consider the idea of e.g. sending proofs of knowledge of R along= +=20 +> with R in the coordination step? This would keep the same number of round= +s,=20 +> and I'm assuming (though not sure exactly) that it makes the security pro= +of=20 +> significantly simpler, but my guess is you mostly dismiss such approaches= +=20 +> as being too expensive for, say, constrained devices? (I imagine somethin= +g=20 +> like: 2 parties say, X1 sends (R1, pi_R1) and same for X2, to coordinator= +,=20 +> then sum directly for overall R; here pi_R1 is ofc just a schnorr sig on= +=20 +> r). If we're talking about bandwidth the current "ctx" object is already= +=20 +> pretty large, right, because it contains all the pubkeys and all the=20 +> messages (though in bitcoin they could be implicit perhaps). +> +> (I won't mention the other idea, which is going back to MuSig1 style and= +=20 +> just committing to R, because that's what both MuSig2 and FROST went away= +=20 +> from, preferring fewer rounds.) +> +> By the way after writing this overly long post I realised I didn't even= +=20 +> get in to the really tricky part of the algorithm, the "check our key and= +=20 +> message appears once" part because of the multisig-to-aggregated-sig=20 +> transformation and the hole previously identified in it, which to be fair= +=20 +> is the most interesting bit. Oh well, another time! +> +> Cheers, +> AdamISZ/waxwing +> On Thursday, April 17, 2025 at 10:38:46=E2=80=AFAM UTC-6 Jonas Nick wrote= +: +> +>> Hi list,=20 +>> +>> Cross-Input Signature Aggregation (CISA) has been a recurring topic here= +,=20 +>> aiming=20 +>> to reduce transaction sizes and verification cost [0]. Tim Ruffing,=20 +>> Yannick=20 +>> Seurin and I recently published DahLIAS, the first interactive aggregate= +=20 +>> signature scheme with constant-size signatures (64 bytes) compatible wit= +h=20 +>> secp256k1.=20 +>> +>> https://eprint.iacr.org/2025/692.pdf=20 +>> +>> Recall that in an aggregate signature scheme, each signer contributes=20 +>> their own=20 +>> message, which distinguishes it from multi- and threshold signatures,=20 +>> where all=20 +>> signers sign the same message. This makes aggregate signature schemes th= +e=20 +>> natural cryptographic primitive for cross-input signature aggregation=20 +>> because=20 +>> each transaction input typically requires signing a different message.= +=20 +>> +>> Previous candidates for constant-size aggregate signatures either:=20 +>> - Required cryptographic assumptions quite different from the discrete= +=20 +>> logarithm=20 +>> problem on secp256k1 currently used in Bitcoin signatures (e.g., groups= +=20 +>> with=20 +>> efficient pairings).=20 +>> - Were "folklore" constructions, lacking detailed descriptions and=20 +>> security=20 +>> proofs.=20 +>> +>> Besides presenting DahLIAS, the paper provides a proof that a class of= +=20 +>> these=20 +>> folklore constructions are indeed secure if the signer does _not_ use ke= +y=20 +>> tweaking (e.g., no Taproot commitments or BIP 32 derivation). Moreover,= +=20 +>> we show=20 +>> that there exists a concrete attack against a folklore aggregate=20 +>> signature=20 +>> scheme derived from MuSig2 when key tweaking is used.=20 +>> +>> In contrast, DahLIAS is proven to be compatible with key tweaking.=20 +>> Moreover, it=20 +>> requires two rounds of communication for signing, where the first round= +=20 +>> can be=20 +>> run before the messages to be signed are known. Verification of DahLIAS= +=20 +>> signatures is asymptotically twice as fast as half-aggregate Schnorr=20 +>> signatures=20 +>> and as batch verification of individual Schnorr signatures.=20 +>> +>> We believe DahLIAS offers an attractive building block for a potential= +=20 +>> CISA=20 +>> proposal and welcome any feedback or discussion.=20 +>> +>> Jonas Nick, Tim Ruffing, Yannick Seurin=20 +>> +>> +>> [0] See, e.g., https://cisaresearch.org/ for a summary of various CISA= +=20 +>> discussions.=20 +>> +> + +--=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/= +604ca4d2-48c6-4fa0-baa6-329a78a02201n%40googlegroups.com. + +------=_Part_32367_1051542522.1745687115956 +Content-Type: text/html; charset="UTF-8" +Content-Transfer-Encoding: quoted-printable + +On that last point about "proof of knowledge of R", I suddenly realised it'= +s not a viable suggestion: of course it defends against key subtraction att= +acks, but does not defend at all against the ability to grind nonces advers= +arially in a Wagner type attack,=C2=A0 so that you could get a forgery on t= +he victim's single key from a bunch of parallel signing sessions. So, quest= +ion retracted, there.<br /><br /><div class=3D"gmail_quote"><div dir=3D"aut= +o" class=3D"gmail_attr">On Saturday, April 26, 2025 at 10:14:36=E2=80=AFAM = +UTC-6 waxwing/ AdamISZ wrote:<br/></div><blockquote class=3D"gmail_quote" s= +tyle=3D"margin: 0 0 0 0.8ex; border-left: 1px solid rgb(204, 204, 204); pad= +ding-left: 1ex;"><div>Some comments/questions on the general structure of t= +he scheme:</div><div><br></div><div>When I started thinking about ways to c= +hange the algorithm, I started to appreciate it more :) Although this algo = +is not specific to Bitcoin I'm viewing it 100% through that lens here. = +Some thoughts:</div><div><br></div><div>We want this CISA algorithm to have= + the property that it doesn't require the blockchain (and its verifiers= +) to incur linear cost in the number of signers/signatures. For a 100 input= + transaction, we get big gains from the owner or owners of the inputs choos= +ing to use this algo, but that would mostly be lost if either the verifying= + was linear in the number, or if the size of the signature was linear in th= +e number. So to avoid that we want a (R, s) structure to be actually publis= +hed, not an (R1..Rn, s) or a (R, s1..sn). That pretty much forces us to mak= +e a sum R for all the individual component's R-values, and the same for= + s.</div><div><br></div><div>However it doesn't quite force us to add l= +iterally everything. The pubkeys *can* be kept separate, because they are r= +etrieved implicitly from the existing blockchain record, they are not publi= +shed with the signature (taproot). (Technically the same comment applies to= + the message being signed). This allows us to use the more "pedestrian= +", "safe" idea; we are not aggregating keys (as in MuSig) so= + we can actually add each with its own challenge hash: sum( challenge_hash_= +i * X_i). This may worry you that there is a performance issue because the = +verifier has to iterate through that whole list ( the verification equation= + being: sG =3D?=3D R + c_1 X_1 + c_2X_2 + .. ), but the paper specifically = +claims that comparing this with just batch verifying the individual signatu= +res (i.e. without CISA), this is twice as fast.</div><div><br></div><div>So= + one could simplistically say "OK that's the pubkey side, they'= +;re treated individually so we don't have to worry about that, but what= + about adding the R values?" ("worry" here means: trivial ke= +y subtraction attacks or sophisticated Wagner/ROS grinding). And here what = +is done is basically the same as in MuSig2, which is to say, by breaking th= +e nonce into two components and including an additional challenge hash, you= + prevent the counterparty/adversary from grinding R values successfully. No= +te that the "b" coefficient used here is more explicit about hash= +ing the full context, than it was in MuSig2: it's hashing each individu= +al pubkey and message as well as the R2 subcomponents for each party. This = +is vaguely similar to "client side validation" ideas: it's no= +t really "validation" as in state updates, but it's having th= +e more complex/expensive part of the calculation being done in the coordina= +tion before anything goes on-chain, and allowing us to just use a single &q= +uot;R" value onchain that we know is safe.</div><div><br></div><div>(S= +ide note: it's worth remembering that a lot (maybe a huge majority?) of= + the usage of CISA will be a single signer of multiple inputs; for these ca= +ses there is not the same security arguments required, only that the final = +signature is not leaking the private key!).</div><div><br></div><div>That s= +ide note reminds me of my first question: would it not be appropriate to in= +clude a proof of the zero knowledgeness property of the scheme, and not onl= +y the soundness? I can kind of accept the answer "it's trivial&quo= +t; based on the structure of the partial sig components (s_k =3D r_k1 + br_= +k2 + c_k x_k) being "identical" to baseline Schnorr?</div><div><b= +r></div><div>The side note also raises this point: would it be a good idea = +to explicitly write down ways in which the usage of the scheme/structure ca= +n, and cannot, be optimised for the single-party case? Intuitively it's= + "obvious" that you may be able to streamline it for the case whe= +re all operations happen on the same device, with a single owner of all the= + private keys. I realize that this is a thorny point, because we explicitly= + want to account for the corruption of parties that are "supposed"= +; to be the same as the honest signer, but aren't.</div><div><br></div>= +<div>And my last question is about this multi-component-nonce technique:</d= +iv><div><br></div><div>Did you consider the idea of e.g. sending proofs of = +knowledge of R along with R in the coordination step? This would keep the s= +ame number of rounds, and I'm assuming (though not sure exactly) that i= +t makes the security proof significantly simpler, but my guess is you mostl= +y dismiss such approaches as being too expensive for, say, constrained devi= +ces? (I imagine something like: 2 parties say, X1 sends (R1, pi_R1) and sam= +e for X2, to coordinator, then sum directly for overall R; here pi_R1 is of= +c just a schnorr sig on r). If we're talking about bandwidth the curren= +t "ctx" object is already pretty large, right, because it contain= +s all the pubkeys and all the messages (though in bitcoin they could be imp= +licit perhaps).</div><div><br></div><div>(I won't mention the other ide= +a, which is going back to MuSig1 style and just committing to R, because th= +at's what both MuSig2 and FROST went away from, preferring fewer rounds= +.)</div><div><br></div><div>By the way after writing this overly long post = +I realised I didn't even get in to the really tricky part of the algori= +thm, the "check our key and message appears once" part because of= + the multisig-to-aggregated-sig transformation and the hole previously iden= +tified in it, which to be fair is the most interesting bit. Oh well, anothe= +r time!</div><div><br></div><div>Cheers,</div><div>AdamISZ/waxwing</div><di= +v class=3D"gmail_quote"></div><div class=3D"gmail_quote"><div dir=3D"auto" = +class=3D"gmail_attr">On Thursday, April 17, 2025 at 10:38:46=E2=80=AFAM UTC= +-6 Jonas Nick wrote:<br></div></div><div class=3D"gmail_quote"><blockquote = +class=3D"gmail_quote" style=3D"margin:0 0 0 0.8ex;border-left:1px solid rgb= +(204,204,204);padding-left:1ex">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" rel=3D"nofollow" targe= +t=3D"_blank" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den&= +;q=3Dhttps://eprint.iacr.org/2025/692.pdf&source=3Dgmail&ust=3D1745= +772037681000&usg=3DAOvVaw1vd3zF_KLluWFbfpY5qm7j">https://eprint.iacr.or= +g/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/" rel=3D"nofollow" t= +arget=3D"_blank" data-saferedirecturl=3D"https://www.google.com/url?hl=3Den= +&q=3Dhttps://cisaresearch.org/&source=3Dgmail&ust=3D17457720376= +81000&usg=3DAOvVaw1j1lUH47B9z8Np_UgA32zE">https://cisaresearch.org/</a>= + for a summary of various CISA +<br> discussions. +<br></blockquote></div></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/604ca4d2-48c6-4fa0-baa6-329a78a02201n%40googlegroups.com?utm_med= +ium=3Demail&utm_source=3Dfooter">https://groups.google.com/d/msgid/bitcoind= +ev/604ca4d2-48c6-4fa0-baa6-329a78a02201n%40googlegroups.com</a>.<br /> + +------=_Part_32367_1051542522.1745687115956-- + +------=_Part_32366_1712149344.1745687115956-- + |