# Oblivious Address Discovery

Scenario / goals:

- User $A$ wants to enable cryptocurrency account discovery for a list of its
contacts in an asynchronous way, i.e., $A$ does not want to interact with any of
its contacts directly to enable discoverability.

Assumptions:

- There exists a (distributed) salting service that allows a client and a set
of servers to jointly evaluate a (distributed) verifiable oblivious
pseudorandom function (VOPRF) to derive a salt. We denote this by $y =
VOPRF(x)$.

- There exists a cache that manages discovery tuples of the form
$(id_{joint}, id_{target}, proof)$.

- There exists a smart contract that manages on-chain user accounts of the form
$(id, pk, addr)$ where id is a unique VOPRF-based identifier, $pk$ is a public
key, and $addr$ is the cryptocurrency address.

Protocol:

- For the setup, user $A$ executes the following steps:

+ S01: Compute a key pair $(sk_A, pk_A) = (a, g^a)$ and a cryptocurrency address $addr_A = H(pk_A)$.
+ S02: Register phone number $n_A$ on the platform and obtain a proof from the validators that it was successful.
+ S03: Create a zk-proof $p_A$ showing that $A$ is the legitimate owner of phone number $n_A$ as approved during registration (see subroutine below)
+ S04: Interact with the salting service to get $salt_A = VOPRF(n_A)$ legitimizing the request with $p_A$.
+ S05: Compute $id_A = H(n_A || salt_A)$.
+ S06: Store the account information $(id_A, pk_A, addr_A)$ on the blockchain.

- To enable account discovery for a contact $B$, user $A$ executes the following steps:

+ S07: Create a zk-proof $p_{AB}$ showing that $A$ is the legitimate owner of $n_A$ or $n_B$ (see subroutine below).
+ S08: Interact with the salting service to get $salt_{AB} = VOPRF(n_A || n_B)$ legitimizing the request with $p_{AB}$.
+ S09: Compute $id_{AB} = H(n_A || n_B || salt_{AB})$.
+ S10: Create a zk-proof $p_{ABA}$ showing that $id_{AB}$ and $id_A$ share a connection. (TODO)
+ S11: Store in a (distributed) cache the discovery tuple $(id_{AB}, id_A, p_{ABA})$.

- If a user $B$ wants to discover the address of one of its contacts $A$, it executes the following steps:

+ S12: Create a zk-proof $p_{BA}$ showing that $B$ is the legitimate owner of $n_B$ or $n_A$ (see subroutine below).
+ S13: Interact with the salting service to get $salt_{AB} = VOPRF(n_A || n_B)$ legitimizing the request with $p_{BA}$.
+ S14: Compute $id_{AB} = H(n_A || n_B || salt_{AB})$.
+ S15: Retrieve the tuple $(id_{AB}, id_A, p_{ABA})$ from the (distributed) cache and verify $p_{ABA}$.
+ S16: If $p_{ABA}$ is invalid, abort. Otherwise retrieve the account information $(id_A, pk_A, addr_A)$ from the blockchain.

Subroutines:

For S03:

- We denote $g_1$ and $g_2$ as the base points for pairing curves $G_1$ and $G_2$.
- Assume user $A$ has a validator BLS signature $s = H(n_A)^v$ where $v$ is the
(aggregate) secret key and $pk = (g_1)^v$ is the aggregate public key that he
got during registration. We denote the key pair of the VOPRF service by $(k, g^k)$
- A picks a random value $r$, and sends to the salting service $s^r$ and $H(n_A)^r$
(note: the latter will be the actual input to the VOPRF).
- The salting service verifies those values via $e(g_1, s^r) = e(pk, H(n_A)^r)$
and if correct replies with $s_k = (H(n_A)^r)^k$.
- After receiving $s_k$, the user BLS-verifies it against $g^k$, if correct
removes $r$ from $s_k$, and computes $salt_A = H( n_A || H(n_A)^k )$.

For S07 / S12:

- Phone numbers $n_A$ and $n_B$.
- Validator BLS sig $s_v = H(n_A)^v$.
- Pick random $r$ and compute $(s_v)^r$, $H(n_A)^r$, $H(n_B)^r$.
- Authenticate as in S03.
- Salting service sends back $( H(n_A)^r \cdot H(n_B)^r )^k$.
- User verifies that value using $g^k$, if correct removes $r$, and then outputs
$salt_{AB} = H( H(n_A) \cdot H(n_B) || (H(n_A) \cdot H(n_B))^k )$.
- The symmetric approach works for $B$ (S12).

Notes:

- We use the (distributed) cache (e.g., could be something like IPFS) as an
intermediary to save on-chain space, to enable updateability of the
connections between contacts, and to give users the choice for which of their
contacts they would like to enable phone-number-based discoverability and
whether they want to point all of their contacts to one account, have a
separate account for each of their contacts or anything in between.

- The cache learns for how many of its contacts a user has enabled
discoverability.

- The cache does not learn the connection between phone numbers and addresses
as it does not own any of the phone numbers and thus cannot query the VOPRF
service.

- The cache also does not learn whether users share a connection as it only
stores discovery tuples containing oblivious indices and a zk-proof.

- A cache can delete its entries or deny discovery requests. Since caches do not
know the phone numbers that correspond to certain entries, denying requests
selectively seems difficult. Caches can still identify users through other
means such as their IP addresses. Users can counter this by connecting to the
cache through an anonymity network. Another mitigation could be that there are
several caches and users decide where they store their discovery tuples either
randomly or with those caches providing the best service.