Neighborhood trait

[mcalancea]

This PR introduces a new Neighborhood trait which describes "what we want from a HNSW candidate list data structure". It also introduces two impls for this trait: the slightly modified SortedNeighborhood and the new UnsortedNeighborhood. Additionally, many methods of HNSWSearcher are rewritten for a generic N: Neighborhood.

You can consult the trait docs for the contract and the unit test in neighborhood.rs for usage.

Notable changes:

• match_count is replaced by matches, which returns all the matches explicitly (vectors and distances).
• ~~(unfinished) mpc work is intended to be moved to retain_k_nearest, while insert_batch only appends to the container. retain_k_nearest must almost always be called after inserts to guarantee soundness~~.
• layer_search_std is rewritten to not require a pop_furthest API.
• get_nearest is renamed to get_next_candidate

Notable non-changes:

• insert_prepare is not yet written for unsorted neighborhoods.

[semgrep-code-worldcoin[bot]]

Semgrep found 6 tainted-path findings:

• iris-mpc-cpu/src/utils/serialization/mod.rs
  • L11 - Triage
  • L18 - Triage
  • L25 - Triage
  • L32 - Triage
• iris-mpc-bins/bin/iris-mpc-cpu/generate_ideal_graph.rs
  • L36 - Triage
  • L62 - Triage

The application builds a file path from potentially untrusted data, which can lead to a path traversal vulnerability. An attacker can manipulate the path which the application uses to access files. If the application does not validate user input and sanitize file paths, sensitive files such as configuration or user data can be accessed, potentially creating or overwriting files. To prevent this vulnerability, validate and sanitize any input that is used to create references to file paths. Also, enforce strict file access controls. For example, choose privileges allowing public-facing applications to access only the required files.

View Dataflow Graph

flowchart LR
    classDef invis fill:white, stroke: none
    classDef default fill:#e7f5ff, color:#1c7fd6, stroke: none

    subgraph File0["<b>iris-mpc-cpu/src/utils/serialization/mod.rs</b>"]
        direction LR
        %% Source

        subgraph Source
            direction LR

            v0["<a href=https://github.com/worldcoin/iris-mpc/blob/fc208dcecc3460568bd817effae67e8cd9fcf08e/iris-mpc-cpu/src/utils/serialization/mod.rs#L32 target=_blank style='text-decoration:none; color:#1c7fd6'>[Line: 32] filename</a>"]
        end
        %% Intermediate

        %% Sink

        subgraph Sink
            direction LR

            v1["<a href=https://github.com/worldcoin/iris-mpc/blob/fc208dcecc3460568bd817effae67e8cd9fcf08e/iris-mpc-cpu/src/utils/serialization/mod.rs#L32 target=_blank style='text-decoration:none; color:#1c7fd6'>[Line: 32] filename</a>"]
        end
    end
    %% Class Assignment
    Source:::invis
    Sink:::invis

    File0:::invis

    %% Connections

    Source --> Sink