Fundamentally this verification is based on your contact list, which is formed from people you already know and have added to your contacts, so there's not real

Fundamentally this verification is based on your contact list, which is formed from people you already know and have added to your contacts, so there's not really any need for a centralized trust. Presumably you trust the e-mail address of the contact you added, and the federation protocol could easily define how the authoritative hash/key for each user would be shared based on their e-mail. In most cases this could also be resolved at first contact in meatspace, directly between the devices when establishing contact via the typical ways users share contact information - QR code or some form of short range networking, or even with an SMS challenge.