They should only notify users if they both have each other's phone. Otherwise it is trivial to create several thousands of accounts and upload thousands of numbers from each to get a mapping between an id and a phone number. Here is a quote from a head of Russian company that claims to do this:
> A phone number used by [Telegram] account @silovikicat was discovered using a program titled "Insider-Telegram" developed by the "Center of research of legitimacy and political protest". The head of the "Center" Eugene Venediktov explains: "Currently the database contains over 10 million of numbers. We just go through all possible numbers and check whether they are registered in Telegram: for example, we take all numbers starting with a prefix +7911 and check them. You automatically see all contacts from you address book in your Telegram, don't you? We just have a very "fat" address book with phones of all users from our country."
> When a phone number provided by Eugene is added into an address book, Telegram automatically matches it with account @silovikicat («Siloviks' cat»).
Having a phone number means that the government can track its rough location and know owner's identity.
This also means that other messengers using similar contact discovery allow to de-anonymize its users the same way.
> A phone number used by [Telegram] account @silovikicat was discovered using a program titled "Insider-Telegram" developed by the "Center of research of legitimacy and political protest". The head of the "Center" Eugene Venediktov explains: "Currently the database contains over 10 million of numbers. We just go through all possible numbers and check whether they are registered in Telegram: for example, we take all numbers starting with a prefix +7911 and check them. You automatically see all contacts from you address book in your Telegram, don't you? We just have a very "fat" address book with phones of all users from our country."
> When a phone number provided by Eugene is added into an address book, Telegram automatically matches it with account @silovikicat («Siloviks' cat»).
Having a phone number means that the government can track its rough location and know owner's identity.
This also means that other messengers using similar contact discovery allow to de-anonymize its users the same way.
[1] (in Russian) https://meduza.io/feature/2019/08/10/kto-takoy-tovarisch-may...