Explore batch verification of mithril certificate chain

[iquerejeta]

Why

Certificate chain verification could be made more efficient

What

When verifying a chain of n certificates, we currently verify each individually. This means that we compute the final check for each n certificate, resulting in 2n pairing evaluations. We can improve this by batching this check, resulting in n + 1 pairing evaluations.

How

Suppose that you received n STM aggregate signatures, S_1,…, S_n, where each signature S_i is the aggregate of k multi-signatures. For each n STM signature, let PK_i be it's aggregate public key. For each STM signature, we need to check that the following equation holds, e(S_i, G_2) = e(M_i, PK_i), where G_2 is the generator of G2, and M_i is the message signed by signature i.

The trivial way to verify the batch would be to compute n equality checks, resulting in 2n pairing evaluations. However, we can do better by aggregating all checks into a single one as follows:

e(\sum_{i=1}^n S_i, G_2) = \prod_{i=1}^n e(M_i, PK_i)

reducing the number of pairing evaluations to n + 1, in exchange of n additions in G1 (a much cheaper operation).

NOTE: This batch verification (without multiplying each S_i and M_i by a random scalar) is only possible because in mithril, S_i and PK_i are already multiscalar multiplications of the underlying signatures and public keys respectively with (pseudo)random scalars. If this was not the case, we would need to multiply each S_i and PK_i with a random scalar.