Super batch verify same-subnet attestations

[dapplion]

Description

Lighthouse batch verifies attestations and other messages into collections of signature sets, by combining different messages into a linear combination.

$$ S⋆ = r_1 S_1 + ⋯ r_n S_n $$

This saves at the limit 50% of pairings. The optimization is explained in detailed here https://ethresear.ch/t/security-of-bls-batch-verification/10748

However, we can do better. When a node is an aggregator, it receives ~439 individual attestations that sign over the same message. Since its the same message, there's no need to multiply each signature / message tuple by a random integer just perform your classic 'old FastAggregateVerify and pay a single pairing for those 439 messages.

Epic savings

How to

Some layer of the stack must group to-verify messages by signing root.

1. The network processor queues or groups attestations by AttestationData, then sends collections of the same data to the super batch verify function
2. Some intermediary layer in the BLS verifier that buffers messages and groups then by signing root, independent of the message represents. It's a more generic approach, but only subnet attestations are worth grouping this way. Buffering also adds latency.

[pawanjay176]

Neat trick!
How would the timing of this look like? I would assume this would require holding off on gossip verification of the received attestations until some cutoff time into the slot.
So assuming we wait for X seconds into the slot for all attestations in our subnet, then batch verify and forward everything.
Wouldn't this hurt attestation propagation if instead of immediately verifying and forwarding (takes ~5ms), we wait for some X seconds before verifying and forwarding?

[dapplion]

Right, we need to measure but I would guess (hope?) that a node with --subscribe-all-subnets is experiencing some natural buffering due to the burst-y nature of attestations.

Otherwise, introducing some very small buffering of 1-10ms may acceptable and sufficient? Efficiency gains quickly trend down, buffering 10 messages ~90% savings, buffering 100 messages ~99% savings.

[michaelsproul]

In offline discussion we concluded that this optimisation was unsafe due to the ability of the attacker to add junk to the signatures that cancels out when aggregated. However the linked ethresear.ch post addresses this and implies that it can be mitigated by doing subgroup checks.

Maybe we need to summon @kirk-baird to a planning session to iron out the kinks and come up with a working design?

[kirk-baird]

However the linked ethresear.ch post addresses this and implies that it can be mitigated by doing subgroup checks.

These sub group checks are required for a different junk that you can add which cancels out during linear combination. It adds junk outside our subgroup which is cleared when we do linear multiplication. e.g. we can find a junk e outside the subgroup where 2 * e = 0. Now adding that to a valid signature SA = S1 + e.

So during the linear combination if r1 is even r1 = 2m for some m. So then the following would happen when multiplying by r1

r1 * SA = r1 * (S1 + e)
= r1 * S1 + r1 * e
= r1 * S1 + 2m * e
= r1 * S1 + m * 2e  // note we selected e such that 2e = 0
= r1 * S1 + m * 0
= r1 * S1

So the lack of subgroup check here would be bad as we could add junk that disappears when multiplied.

For FastAggregateVerification we can still add junk within our sub-group which won't be caught by sub group checks. e.g. pick a value in the subgroup such as the generator G. Then take our valid signature S1 and make an invalid signautre SA = S1 + G and again except minus the junk, SB = S2 - G. When we add the two of these together in fast aggregate verify they'll cancel out e.g.

SB + SA = S1 + G + S2 - G
= S1 + S2

So here we've sent SA and SB over the wire which are invalid but when added together it matches the valid S1 and S2.

[dapplion]

Closing issue as this approach can result in a malicious peer forcing you to propagate invalid data and getting banned. It becomes quite easy to execute an eclipse attack under these conditions.

[matthewkeil]

A security fix was applied and the mathematical proof is in peer review. There is a further optimization that can be applied to this technique with MSM and overall efficiency gain is substantial. Figured was worth another look by you guys.

Here is the ethresearch post with the security proof:
https://ethresear.ch/t/attestation-verification-optimization/20516

pinging @dapplion

[kirk-baird]

This is a good suggestion from @matthewkeil. If we instead multiply the public key and signature (as opposed to message and signature) by a random oracle, then we can perform aggregation safely and do a single pairing.

[michaelsproul]

Reopening this as a potentially interesting avenue for optimisation.