# 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?
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)
Sign in with Wallet
Connect another wallet