[ZIP 217] Use aggregate multisignatures within a transaction

[daira]

The signatures used in a transaction can be combined into an aggregate multisignature, along the lines of https://eprint.iacr.org/2018/068 . This works for Sapling spend authorization and binding signatures.

[daira]

This doesn't necessarily require a circuit change.

[arielgabizon]

I'm working on it now as a fun friday/fun week thing :)

[daira]

This definitely doesn't require a circuit change. All of the RedJubjub signatures in a transaction are over the same message (the ZIP 243 sighash with no transparent input), and therefore only a "multisignature scheme with key aggregation" is needed, not a general aggregated signature scheme that would allow aggregation of signatures on distinct messages [*]. We know how to do such multisignatures without a circuit change, because MuSig can be straightforwardly adapted to RedDSA/RedJubjub.

Note that we still need the randomised public key rk in each Spend description, but this saves the bandwidth cost of the spend authorisation signatures (64 bytes each) and more importantly their verification cost. The aggregate signature effectively replaces the binding signature. A new transaction version is required, but this feature does not require disallowing the previous version, since it's only an optimisation. (On the other hand, using the previous version would reveal that the transaction was constructed using older software.)

This approach is compatible with using n-of-n multisignatures: MuSig composes such that each participating key can itself be a MuSig aggregate key. Furthermore it's compatible with a future extension (requiring a circuit change, perhaps in NU3) to allow k-of-n multisignatures.

We can't do this for ECDSA signatures; those would have to stay separate. That's not a long-term problem because we intend to remove t-addresses.

[*] Even if we did need aggregate signatures over distinct messages, there's a generic construction of Interactive Aggregate Signatures from multisignatures due to Bellare and Neven that would support that. The details of how to apply the Bellare–Neven construction to MuSig are discussed in Appendix A of the MuSig paper. But there's no need to incur this complexity given the design of Sapling.

[daira]

I think this is a pretty straightforward improvement that we should include in Blossom.

[arielgabizon]

I think this is a pretty straightforward improvement that we should include in Blossom.

If we do, I can work on it all week and not just Fun Friday ;)

[daira]

Assigned ZIP number 217.