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.