[darkhorn]

The problem could be solved like this; you generate an UUID and your friend generates UUID. Then you both exchange the UUID. You should do it within an hour. When both UUIDs are entered into the opposite parties you become friends. Now your friend knows you as G435-… and your wife knows you as B64J-…. No one can add you as friend with these used UUIDs. This will solve the privacy problem, mostly.

[couchand]

At the expense of being practically unusable for most people. It's a trade off.

EDIT: This proposal also suffers from a bootstrapping problem. You have to already have a secure channel to communicate the ids.

[codedokode]

Signal could allow both options: register with a phone number or with completely anonymous logins. I think they just don't want anonymous users, visits from FBI etc. Also, it is not very profitable to sell ads to anonymous users.

[ubercow13]

You have to have a secure channel to exchange phone numbers too. The code could be communicated simply using a QR code. Other messengers already work this way and it works well.

[couchand]

Yes, the difference being that a phone number is an established identity mechanism and you likely already know it.

[ubercow13]

Yes but it's a kind of bad one. There are many ways you can lose or change your phone number. Email address is a better identifier.