Revisiting Falcon signature aggregation for PQ mempools

Very interesting breakdown and thanks @b-wagn for drawing my attention to it!

My question from Lattice-based signatures aggregation post had the consensus setting in mind, where we don’t need to keep the public key around (as the validator’s public key can be looked up by its index). In that case, assuming the proof size stays more or less constant at about ~70 KB, the break even point should be around 100 signatures.


For reference, I am adding below a similar comparison you did but with the consensus setting in mind. I forked your code here for the estimation, adapted the formulas and considered the same three cases.

Case 1: Key Recovery, No Aggregation

This case only seems interesting on the EL (where public keys are not stored) as on the CL public keys are already known. Included for comparison:

\text{Total} = N \cdot (\tilde{S} + R)

Case 2: Standard Falcon, No Aggregation

Similar to your case 2, but includes the validator indexes instead of the public key p:

\text{Total} = N \cdot (S + R + \text{idx})

Case 3: Standard Falcon, With Aggregation

Similar to your case 3, but includes the validator indexes instead of the public key p:

\text{Total} = a_N + N \cdot (R + \text{idx})

As expected, the break even shifts to the left now and it is indeed around 100 signatures (instead of 200 as in EL).

6 Likes