From mboxrd@z Thu Jan 1 00:00:00 1970 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 ) 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 ; 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 To: Bitcoin Development Mailing List Message-Id: <604ca4d2-48c6-4fa0-baa6-329a78a02201n@googlegroups.com> In-Reply-To: <039cb943-5c94-44ba-929b-abec281082a8n@googlegroups.com> References: <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: X-Google-Group-Id: 786775582512 List-Post: , List-Help: , List-Archive: , List-Unsubscribe: , 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.

On Saturday, April 26, 2025 at 10:14:36=E2=80=AFAM = UTC-6 waxwing/ AdamISZ wrote:
Some comments/questions on the general structure of t= he scheme:

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:

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.

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.

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.

(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!).

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

=
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 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).

(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= .)

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!

Cheers,
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 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.or= g/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/604ca4d2-48c6-4fa0-baa6-329a78a02201n%40googlegroups.com.
------=_Part_32367_1051542522.1745687115956-- ------=_Part_32366_1712149344.1745687115956--