1

Suppose a mapping of addresses and their respective balances. I would like to recover a list of the top "k" addresses by balance.

I understand that sorting inside the contract is prohibited especially when the number of addresses is arbitrary large. I have found that the proposed way is to observe for events emitted on state changes and then sort the data off-chain.

However I can't see how this sorting can be trusted. The data could be manipulated by a malicious node or by the the front-end. Ideally the contract should be able to confirm that the sorted data provided correspond to the top "k" balances before using them for any other operation.

How would you go about this? To me it seems you cannot alleviate this need for trust on the off-chain sorting without doing some on-chain sorting. Even confirming that the data are sorted doesn't mean they truly are the desired top "k".

Improve this question
1

1 Answer 1

Reset to default
1

Verifying the elements are sorted correctly on-chain should be O(N) on the number of elements.

Another option is to include rewards and punishments in the protocol when a wrong answer is submitted.

Improve this answer
1
  • Indeed checking if they are sorted should be relatively cheap. But knowing if the submitted list is the top "k" elements in the mapping should require that the contract knows the max. Unfortunately I can't see a way of doing that programmatically without sorting inside the contract.
    – wolf dun
    Jul 18, 2022 at 0:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.