Subject: [bitcoindev] DahLIAS: Discrete Logarithm-Based Interactive Aggregate Signatures

From: Jonas Nick <[email-masked]>
Date: Thu, 17 Apr 2025 16:27:04 +0000

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 [email-masked].
To view this discussion visit https://groups.google.com/d/msgid/bitcoindev/be3813bf-467d-4880-9383-2a0b0223e7e5%40gmail.com.