Optimize duplicate signer detection in _verifySignaturesThreshold

[cernicc]

The _verifySignaturesThreshold function in AttestationLightClient.sol currently uses a nested loop to check for duplicate signers.

[linear]

IBCSOL-279

[Ninjatosba]

hello @cernicc noobie here who wants to help

I found the function you mentioned

One idea is to first collect the recovered signer addresses sort them in memory and then detect duplicates with a single linear lookup

Sorting alone does not reduce the overall complexity unless we use quick sort which would work but adds recursion and more code to audit

So the options look like this

Insertion sort + linear lookup = O(n^2)

Quick sort + linear lookup = n log n

Another idea is to define a mapping and change the function from view to a state changing one then use a hashmap to check duplicates but this would introduce storage writes and higher gas cost

Given these tradeoffs the nested loop approach is still reasonable for readability and simplicity and insertion sort could also be used

If the signature length might grow significantly in the future then we drink the Kool Aid now and switch to quick sort

Happy to go with whatever direction you suggest and let me know if I am missing something