musig: multi-message API for mitigating Russell's attack

[oleganza]

Background

See appendices A.2/A.3 in the MuSig paper.

TL;DR

If you have two UTXOs using the same key, and you did not check ALL the utxos being using in the signed message, then your partial signature for one UTXO can be reused to also sign off inclusion of another UTXO.

Solution for aggregation-by-verifier

The MuSig paper's appendix A.3 describes a solution:

1. The total signed message is formed with ordered pairs (pubkey, item) where item is a specific message signed by the given pubkey (e.g. a unique utxo id or contract id - see also zkvm: make contracts unique #172).
2. Each party generates their own Fiat-Shamir challenge corresponding to their index.
3. The per-party F-S challenges effectively cover the "delinearization" factor applied to each pubkey, so there is no need to apply it to pubkeys in prior steps.
4. The verifier needs to see each individual pubkey and individual message for this to work.

Key aggregation by provers

In the cases when the verifier does not see individual keys, that is, when they were compressed under n-of-n rule offline into a single predicate, each signer is supposed to be fully aware of a message they are signing.

This works fine in case of delegate (provided the contract's anchor is unique and covered by signature: #172).

For signtx, the signer must be "aware of" not just txid, but the specific pair of (pubkey, item) which is normally a (predicate, utxo_id). They usually would ignore txid and only verify proofs of certain outputs to belong to the txid that they sign, since the txid itself and other signers' outputs are not relevant to the given signer.

API

The multi-message API is inherently different from single-message API, since each key's delinearization factor is effectively an individual fiat-shamir challenge bound to the specific (key-submessage) pair.

This should be composable over the regular musig protocol for nested Multikeys via API for cumulative multiplicative adjustment factor (#236).