I'm seeing lots of mentions of cross-input signature aggregation (CISA) lately. It appears to be something that one can do with Schnorr signatures. What is the main idea of CISA? What would a transaction look like that makes use of CISA?
The idea behind CISA is to only provide a single signature per Bitcoin transaction even when there are multiple inputs.
A key advantage of the Schnorr signature algorithm over ECDSA is its linearity. As Sachin's answer described already, this permits multiple signers to construct a single signature which proves a message's authorization by several keys.
In Bitcoin, traditionally each input requires a signature committing to a digest of the complete transaction, the
sighash. For non-segwit inputs, each input's
sighash was distinct (which was also causing the quadratic hashing problem), but the
sighash is uniform for all segwit inputs in one transaction. Since all segwit inputs in one transaction commit to the same digest, a single signature can be used to satisfy multiple inputs.
The current sketch for CISA proposes to replace all but one of the corresponding witnesses with a one-byte placeholder and then to provide only a single signature for all the encompassed inputs in the last input's witness. For a transaction with
n inputs, this would reduce the transaction data by
n-1 signatures adding
n-1 one-byte placeholders in their stead.
The MuSig paper says this also requires a change to outputs: “Doing so requires a fundamental change in validation semantics, as the validity of separate inputs is no longer independent. As a result, the outputs can no longer be modeled as predicates. Instead, we model them as functions that return a boolean plus a set of zero or more public keys. Overall validity requires all returned booleans to be True and a multi-signature of the transaction with L the union of all returned keys.”. Can you expand on this?– runeksNov 28, 2021 at 8:49
Schnorr Signatures and public keys can be aggregated (added together) such that
S1 + S2 = S3 and P1 + P2 = P3 where (S3, P3) is a valid signature-pubkey pair IFF (S1, P1) and (S2,P2) were valid signature-pubkey pairs.
Because of this, if a transaction has n inputs, the signatures of those inputs can be aggregated, so the transaction only needs one signature and public key even with any number of inputs, whereas a regular transaction would need n signatures and public keys.
The main benefit being block space (fee) savings.
1The last second half of this post covers it in greater detail: reddit.com/r/Bitcoin/comments/ibcnsv/… May 19, 2021 at 23:48
3Note that this is an oversimplification, and actually doing this would be completely insecure. But the principle applies indeed: keys can be combined in such a way that signing for the combination is easy. May 20, 2021 at 1:41