---
# System prepended metadata

title: Blind Find v1.5 Design

---

# Blind Find v1.5 Design

[TOC]

## To-Do
- [ ] Detect seen hubs to avoid loops
    - Now we limit the recursion depth to 6.

## Why v1.5?

![](https://github.com/mhchia/blind-find/blob/main/specs/assets/blind_find_v1.5.png?raw=true)

As described in v1 [spec](https://github.com/mhchia/blind-find/blob/main/specs/blind_find_v1.md#blind-find-v15), Blind Find v1.5 keeps the admin-hub-user hierarchy but adds **hub-to-hub connections**. This allow users to search for users on different hubs while preserving the [advantages](https://github.com/mhchia/blind-find/blob/main/specs/blind_find_v1.md#future-works) we get in v1:
- Spam prevention: search messages always go through the hubs. Hubs can stop spamming by messages rate limit.
- Cache: users can go offline and still able to be searched by others as long as hubs are online.


## V1.5 Changes

### Hub Connections

For a hub to connect another hub, both of them need to sign on a message `hash("HUB_CONNECTION" ++ pubkeyHub1 ++ pubkeyHub2)` and be authorized by the admin. By authorization, admin hashes the signatures and public keys altogether and puts the result as a leaf of [hub connection merkle tree](#Hub-Connection-Merkle-Tree). The new merkle root should be updated on chain to make the hub connection valid. This allows them to create [Proof of Salted Connection](#Proof-of-Salted-Connection) later.

> [name=kevin] Question: Should hub connection information be commited on chain? Now I make it stored privately.
> [name=barryWhiteHat] Yes. You can blind it and put on chain + ZKP that each climed connection exists. 
> [name=kevin] For commiting hub connections on chain, is it because we want admin to authorize every hub connection?
> [name=kevin] Confirmed with Barry: Yes.

### Hub Connections Merkle Tree
Each entry of Hub Connection Merkle Tree is composed of
- HubPubkey1
- HubSignature1
- HubPubkey2
- HubSignature2

Whenever a hub connection is established, admin needs to update the tree's new merkle root on Blind Find Contract. Because of this new structure, the followings need to be changed:
- Admin client
- Hub client
- Blind Find Contract


### Search protocol

To support cross-hubs search, hubs must be able to [proxy search messages](https://hackmd.io/aMWuPDDYTHiFHQKg4ryJzQ#Proxied-communications).

#### Pseudo Code: Search Receiver
```python=
class Hub:
    ...

    def handle_search(self, initiator_socket):
        # Run SMP with the search initiator against our users.
        for user in self.users:
            params = smp(initiator_socket, user)
            send_proof_of_smp(initiator_socket, params)

        # Tell the search initiator that we don't have more user.
        send_no_more_users(initiator_socket)
        
        # Try other hubs that have connection with us instead.
        for hub in self.connected_hubs:
            # Send the Proof of Connection with `salted(hub)` to the search initiator.
            proof_connection_with_salted_hub = gen_proof_hub_connection(hub)
            initiator_socket.send(proof_connection_with_salted_hub)
            hub_conn = open(hub)
            # Proxy messages between initiator and hub back and forth.
            proxy(initiator_socket, hub_conn)
            # Wait until NO_MORE_HUBS are sent.
            wait_for_no_more_hubs(hub_conn)

        # Indicate we have no more hubs, and the search on our side is done.
        send_no_more_hubs(initiator)
```

#### Pseudo Code: Search Initiator

```python=
class User:
    ...
    
    def search(
        self, 
        ip: string,
        port: number,
        target: PubKey,
    ) -> List[ProofIndirectConnection]:
        hub_socket = open(ip, port)
        return self._search(hub_socket, target, [])

    def _search(
        self, 
        hub_socket: Socket,
        target: PubKey,
        proof_connections: List[ProofConnection],
    ) -> List[ProofIndirectConnection]:
        hub_socket = open(ip, port)
        cur_res = []
        
        # Run SMP with all users of the hub.
        while not hub_conn.is_closed:
            control_msg = hub.conn.read()
            if control_msg.type == 'USER':
                smp_detail, proof_smp = run_smp(hub_socket, target)
                if smp_detail.res:
                    proof_successful_smp = self.create_proof_smp(proof_smp)
                    proof_indirect_connection = {
                        'proof_connections': proof_connections,
                        'proof_smp': proof_smp,
                        'proof_successful_smp': proof_successful_smp,
                    }
                    cur_res.append(proof_indirect_connection)
            elif control_msg.type == 'NO_MORE_USERS':
                break
            else:
                raise InvalidControlMsg

        # Keep searching through the connected hubs of the hub with messages proxied.
        while not hub_conn.is_closed:
            control_msg = hub.conn.read()
            if control_msg.type == 'HUB':
                # Verify if Proof of Connection is correct or not
                if not self.verify_proof_connection(control_msg.hub.proof_connection):
                    raise InvalidProof("Proof Connection is invalid")
                # Now messages should already be proxied.
                proofs = self._search(
                    hub_socket,
                    target,
                    proof_connections + control_msg.hub.proof_connection,
                )
                # Concat the search results got from the hub to `cur_res`.
                cur_res.extends(proofs)
            elif control_msg.type == 'NO_MORE_HUBS':
                break
            else:
                raise InvalidControlMsg
        return cur_res
```

#### Example
User A is searching for user C.

```graphviz
digraph G {
    "A" -> "Hub 0" [dir=none];
    "Hub 0" -> "Hub 1" [dir=none];
    "Hub 1" -> "C" [dir=none];
    "Hub 0" -> "B" [dir=none];
    { rank=same; "A" "Hub 0" "Hub 1" "C" }
}
```

### Proof Statements

#### Proof of Salted Connection
```=
Private Inputs
    hubPubkey0: PubKey
    hubPubkey1: PubKey

    sig0: Signature
    merkleProof0: merkle proof of hub0's hub registry

    hubConnectionSig0: hub0's signature on hubConnectionMsg
    hubConnectionSig1: hub1's signature on hubConnectionMsg
    hubConnectionMerkleProof: merkle proof of the entry of the connection between hub0 and hub1.
    
Public Inputs
    hubConnectionMsg: string = "HubConnection"
    saltedHubPubkey0: hub0's public key (salted)
    saltedHubPubkey1: hub1's public key (salted)
    merkleRoot: merkle root of the hub registry tree 
    hubConnectionMerkleRoot: merkle root of the hub connection merkle tree
    
Constraints
    # Salted identities
    saltedHubPubkey0 === hash(hubPubkey0)
    saltedHubPubkey1 === hash(hubPubkey1)
    
    # Hub registry
    verifySignature(hubPubkey1, sig1, registerNewHubMsg)
    verifySignature(hubPubkey2, sig2, registerNewHubMsg)
    verifyMerkleProof(merkleProof1, merkleRoot)
    verifyMerkleProof(merkleProof2, merkleRoot)
    
    # Hub Connection
    hubConnectionSigningMsg = hubConnectionMsg ++ hubPubkey1 ++ hubPubkey2
    verifySignature(hubPubkey1, hubConnectionSig1, hubConnectionSigningMsg)
    verifySignature(hubPubkey2, hubConnectionSig2, hubConnectionSigningMsg)
    verifyMerkleProof(hubConnectionMerkleProof, hubConnectionMerkleRoot)
```

#### Proof of Indirect Connection

Continue with the [example](#Example) above. Assume user A has run SMP with Hub 1 and SMP result is true.

Proof of Indirect Connection is composed of the following proofs:
1. [Proof of SMP](https://github.com/mhchia/blind-find/blob/main/specs/blind_find_v1.md#proof-of-smp) is created by Hub 1.
2. All intermediate [Proof of Salted Connection](#Proof-of-Salted-Connection)s.
    - A Proof of Salted Connection is created by Hub 0 to prove
        - 1. it is connected with salted(Hub 1)
        - 2. it’s salted(Hub 0).
3. [Proof of Successful SMP](https://github.com/mhchia/blind-find/blob/main/specs/blind_find_v1.md#proof-of-successful-smp) is created by user A.

> [name=Kevin] Question: Should `salted(pubkey)` be a plain hash function or we should also salt pubkeys with some random numbers?


### Browser Support
To migrate user onto the browser, we need to change the followings:
1. Shell calls: should be changed to pure javascript calls. We can
    - at least replace `zkutil` with `snarkjs`, or
    - compile `zkutil` to wasm and import it from javascript.
2. Storage: user's data should be stored in browser's storage (e.g. cookie) instead of LevelDB

> [name=Kevin] I'm not sure if method 2 works. Need to verify it.
> [name=barryWhiteHat] you can ask Chance about this he knows browser stuff well. 
> [name=Kevin] Thanks for the direction! Confirmed with Chance: [localStorage](https://developer.mozilla.org/en-US/docs/Web/API/Storage) sounds promising.

### UI

#### Introduction
Blind Find v1.5 is a hierarchical peer-to-peer network allowing users to search for others while preserving privacy. When a user is searching for others, it does not reveal its own identity and also the identity of the user it's searching for.

In the network, there are three roles: Admin, Hub, and User.
- Admin: in charge of authorizing people to be hubs. There is only one admin in the network.
- Hub: hubs listen to users' requests. Users can join a hub and be searchable by other users. Also, they can search for others through a hub.
- User: users can be searchable in the network by joining a hub, and search for others through asking a hub.

We only need a page for User because it's not trivial for Hub and Admin to work in browsers.

#### User UI
##### Identity
- `TextIdentity`: A column showing the user's identity. A user identity is a plain ascii string.
- `ButtonCreateIdentity`: A button to create a new identity. When an identity is created, `ColumnIdentity` should be replaced by it.

##### Hub Interaction

Join Hub
- `InputsJoinHub`: A set of inputs including a hub's contact information which is used to join the hub.
    - `InputTextHubAddress`: A string, the hub's IPv4 address
    - `InputTextHubIdentity`: A string, the hub's public key
    - `ButtonJoinHub`: A button triggering join-hub operation
- `TableJoinedHubs`: A table showing the hubs the user has joined before. Each column contains
    - `TextHubAddress`: A string, the hub's IPv4 address
    - `TextHubIdentity`: the hub's identity

Search
- `InputsSearch`: A set of inputs including a hub's contact information which is used to search for another user.
    - `InputTextHubAddress`: A string, the hub's IPv4 address
    - `InputTextTargetUserIdentity`: A string, target user's identity
    - `ButtonSearch`: A button triggering search operation
- `TableSearchHistory`: A table showing the search results. Each column contains
    - `TextHubAddress`: A string, the hub's IPv4 address
    - `TextTargetUserIdentity`: A string, target user's identity
    - `TextResult`: A string, whether the search is successful or not
    - `ButtonShowProof`: A button, showing the zk-proof when it's clicked


## V1 Profiling
### Machine
Measured on MacBook Pro (16-inch, 2019) with
- Processor: 2.6 GHz 6-Core Intel Core i7
- Memory: 32 GB 2667 MHz DDR4

### SMP
|  | Time (seconds) | Creator| Sent through the network |
| -------- | ------------- | ------------- | -------------|
| SMP Message 1 | 0.157    | Hub | Yes |
| SMP Message 2 | 0.593    | User | Yes |
| SMP Message 3 | 0.788    | Hub | Yes |
| SMP Message 4 | 0.515    | User | No |

Total: 2.053 seconds

### Proof geneneration and verification

| | Constraints | Compilation (circom) | Calculate witness (snarkjs) | Generate proof (zkutil) | Verify proof (zkutil) |
| -------- | -------- | -------- | -------- | -------- | -------- | -------- | -------- |
| Proof of SMP | 86042 | 18.139s | 0.724s | 2.093s | 0.444s |
| Proof of Successful SMP | 7073 | 2.620s | 0.198s | 0.234s | 0.090s |

## Other Improvements

### Parallelizing SMPs in a search
Now when a user searches through a hub, it sequentially runs SMP through all of the hub's users. To fully utilize CPU and network bandwidth, it may be reasonable for a search to run SMP with all users simultaneously if we assume CPU and network bandwidth are not bottlenecks.

### Asynchronous calls
Some of the synchronous calls can be changed to asynchronous, e.g. `writeFileSync`.

## Reference
- [Blind Find v1 spec](https://github.com/mhchia/blind-find/blob/main/specs/blind_find_v1.md)
