Halve commit size and improve verification speed with partial Ed25519 signature aggregation

[tony-iqlusion]

Protocol Change Proposal

Summary

CometBFT uses Ed25519 signatures created by validators for consensus.

If a normal Ed25519 signature is (R, s) where each component is a 32-byte serialized field element (i.e. base/scalar field respectively), it's possible to aggregate the s components of the signature as a linear combination, which can be verified by an efficient batch verification algorithm.

This effectively cuts the size of consensus signatures stored in blocks in half, in a way that can be deterministically computed from the original set of Ed25519 signatures, and requires no changes to signers (i.e. HSM-friendly).

Problem Definition / Proposal

This was originally proposed by @ValarDragon as tendermint/tendermint#7892 which contains a detailed description, but was auto-closed as stale.

I mainly opened this issue because it seems like a highly impactful "drop-in" optimization for how CometBFT stores consensus signatures which can significantly reduce both block size and verification time, and I didn't want to see it lost in the shuffle.

If it's helpful I can copy the relevant text into this issue.

Edit: I should note there's a paper describing the scheme here, complete with security proof: https://eprint.iacr.org/2021/350.pdf

[cason]

Thank you for porting this issue to our new repository.

I don't have the cryptographic background in order to fully understand and validate this approach for signature aggregation. But, when considering the approach itself, the main points I think we should consider are:

1. Can users keep using the validator keys they are currently using? Do we impose any restriction on the type/size/whatever characteristic of the keys that can currently be used by CometBFT?
2. Is the proposed change backwards compatible? Or how complex are the changes required in the verification of a block so that we are still able to verify old blocks, not adopting this approach?
3. Can you provide a more detailed reasoning or empirical results to support that commits could be halved in size? While it seems clear that we are removing half of the signature bytes size, a commit actually (and unfortunately) contains much more data.
4. What is the cost of the aggregation procedure? This should be considered in overall, namely the trade-off reasoning should also include possible changes in the cost of producing or verifying a regular (single, not aggregated) signature.

The questions above were crucial, for instance, to define that at the current state of the art we should not adopt BLS aggregated signatures. Not only for requiring new keys and not being backwards-compatible, but also because producing ordinary (single, non aggregated) signatures with this kind of keys is at least 10 times slower than when adopting Ed25519.

[tony-iqlusion]

1. Can users keep using the validator keys they are currently using? Do we impose any restriction on the type/size/whatever characteristic of the keys that can currently be used by CometBFT?

Yes, this involves no changes to validators, their signing keys, or how signatures are produced (i.e. HSM-friendly)

2. Is the proposed change backwards compatible? Or how complex are the changes required in the verification of a block so that we are still able to verify old blocks, not adopting this approach?

It would be most easily implemented as an optimization technique applied to new blocks, leaving old blocks as-is.

There is perhaps some possibility of applying it to old blocks to reduce the size of archival nodes, but I would expect that to be much harder to implement and I'm not sure it's even possible offhand (e.g. would it change block IDs?)

3. Can you provide a more detailed reasoning or empirical results to support that commits could be halved in size? While it seems clear that we are removing half of the signature bytes size, a commit actually (and unfortunately) contains much more data.

That text was carried over from tendermint/tendermint#7892. To be clear it reduces the size of the consensus signatures in half. Offhand I don't have statistics as to how much of the overall block size signatures make up on average.

4. What is the cost of the aggregation procedure? This should be considered in overall, namely the trade-off reasoning should also include possible changes in the cost of producing or verifying a regular (single, not aggregated) signature.

For the linear combination part of it, on my M1 Max a scalar addition takes 18ns. Multiply that times, say 125 signatures and that's 2.25 microseconds. And there are more efficient algorithms for computing linear combinations.

That's not the complete story, but suffice it to say the aggregation is significantly faster than Ed25519 signing/verifying.

It's also a small one-time cost on the part of the proposer which makes signature verification faster overall, where the verification win impacts every block verified by every full node (though the performance win there would come largely from batch verification, which could be implemented without this technique).