Basically there are many options, none of them perfect:

1. Support phone number contact discovery, with persistence provided by the contacts provider. This is seamless and causes the least amount of complaints.

2. Support username discovery, with persistence provided by passphrase-encrypted online storage. This is painful and risks backlash from people losing access to data. Also, now the threat model must account for or ignore weak derived keys (which is probably most of them).

- 2a. Enforce strong passphrase requirements. Many users will abandon the product.

- 2b. Sync usernames between linked devices (using a generated key). Requires multiple devices, risks people losing data, more complaints.

- 2c. Sync usernames using custom contacts provider fields (e.g. email). Nobody is accustomed to doing this, but it might work. Automatic discovery rates would be low. Possibly requires an odd workflow for people adding Signal contacts by their email/username.

Signal (or, more accurately, one of its predecessors) used to use client-side private set intersection for contact discovery, but this scales poorly [1].

Now they use a solution based on Intel SGX and server-side trusted computing [2].

[1] https://signal.org/blog/contact-discovery/

[2] https://signal.org/blog/private-contact-discovery/

Because right now, Signal can use your contact list on the device to get your signal contacts. If you replace a phone number with a username, there will be no way to match signal's user to your contact without:

- Having a server to hold your contacts

- Or having signal app to maintain contact list and sync it across devices