BIP459: Add FullAgg (DahLIAS) module #1754

This PR adds a FullAgg module implementing full aggregation of BIP 340 signatures using the interactive aggregate signature scheme (DahLIAS).

The implementation follows the BIP459.

Concept ACK

The last commit here now is implementing the code sharing between the musig and the fullagg model. That is one of the first questions I have when reviewers will take a closer look here: Do we want to do it this way? And do we event want to do this at all? I think it's pretty good but also the amount of LOC saving has been a bit underwhelming at the end.

A second thing that I changed and that I would be interested in high-level feedback on: I realized that the fullagg module really doesn't need any of the Schnorr module code, it just depends on extrakeys. I fixed this in the config where I still had the schnorr module as dependency of the fullagg module. However, in practical terms they will likely always be active together and it's also a bit awkward that I still have the module named schnorrsig_fullagg which I took over from the Halfagg PR where it's schnorrsig_halfagg. The most correct way would be to remove the schnorrsig part here but I am also unsatisfied with the asymmetry this would create 🙈 If anyone has opinions on this I am happy to hear them.

The latest push is a rebase but also does a bunch of renaming and rewording in response to the naming discussion in the BIP, e.g. dropping the "FullAgg of Schnorr signatures" framing.

Split out the first commit which is a pure refactor: https://github.com/bitcoin-core/secp256k1/pull/1915

Rebased after #1915 was merged

Pulled in additional test vectors added based on feedback on the BIP

Haven't had a deep look on the code yet (still catching up on BIP reading), but giving my two cents on the high-level questions:

The last commit here now is implementing the code sharing between the musig and the fullagg model. That is one of the first questions I have when reviewers will take a closer look here: Do we want to do it this way? And do we event want to do this at all? I think it's pretty good but also the amount of LOC saving has been a bit underwhelming at the end.

Good question, I think there could be made convincing arguments for both sharing and not sharing. One one hand deduplicating code is always nice (even if the overall LOC saving is not that large, the modules ideally become more readable overall), on the other hand this opens up a few questions regarding code organization, naming and scope (e.g. I wouldn't expect to find functions dealing with partial signatures in a module called "nonce_common"). Unless others strongly push back, I think a separate PR which creates the shared module (only moving from musig) could be already opened now for further discussion, in order to keep this PR focused on the new functionality.

A second thing that I changed and that I would be interested in high-level feedback on: I realized that the fullagg module really doesn't need any of the Schnorr module code, it just depends on extrakeys. I fixed this in the config where I still had the schnorr module as dependency of the fullagg module. However, in practical terms they will likely always be active together and it's also a bit awkward that I still have the module named schnorrsig_fullagg which I took over from the Halfagg PR where it's schnorrsig_halfagg. The most correct way would be to remove the schnorrsig part here but I am also unsatisfied with the asymmetry this would create 🙈 If anyone has opinions on this I am happy to hear them.

I'd slightly lean on keeping the schnorrsig_ prefix, to indicate the type of signature which is aggregated (even if the aggregation modules indeed don't depend on the regular schnorrsig module).

65e57481c4c5199c6beb1a0a6272ae739a22bf5a needs rebase

Unless others strongly push back, I think a separate PR which creates the shared module (only moving from musig) could be already opened now for further discussion, in order to keep this PR focused on the new functionality.

Sounds good to me, I have dropped the commit here and instead opened #1938. That would be a good place for people to push back strongly if they feel like it :)

I'd slightly lean on keeping the schnorrsig_ prefix, to indicate the type of signature which is aggregated (even if the aggregation modules indeed don't depend on the regular schnorrsig module).

Thanks, I actually already removed the prefix in some push earlier but my comment didn't make that clear enough since I hadn't really made up my mind when I wrote it. I will wait for 1-2 more opinions before I put them back. My feeling is that @real-or-random might lean the other way :)

needs rebase

Done