unsolved problems for fully decentralized P2P instant messaging

1. How do you assign persistent usernames to potentially rapidly changing IPs? You can't use a centralized server or any side channels (like an email address).

2. How do you do push notifications in Android or iOS? Push notifications are sent by Apple or Google servers via your signed, trusted (centralized) server(s).

Tox (the chat protocol) solves #1 by using centralized servers and #2 by simply not doing push notifications (which is unacceptable).

I dream of a chat client that has all the features of Messenger or iMessage without having to trust anyone. No central server in the middle. Just my message to your device and back and forth.

#1 is basically the same question as, How do you do torrents without trackers?

How do you locate a peer in a P2P network without an authoritative list of peers?

The only way I can think of is something like the way DNS or ``the blockchain'' works. Basically every user (or maybe a subset of them--volunteers like Tor relays) has to store a constantly updating a hash table of usernames to IP addresses.