There’s a Blockchain of all the changes to everyone’s public key. They then introduced a new concept called index to quickly find Alice’s public key. And third party auditors who’ll verify the blockchain and the index and then sign it.

Bob can just use the index signed by auditors and get Alice’s key. Alice can also verify that the key published for her is correct.

when turned on, and only for contacts you know the phone number of (that’s a quirk, username-only contacts don’t work for this), it can verify that the last key you used is the current one. it asks the signal server for XYZ ID’s proof ID (which isn’t the phone number but a blinded account number) - and you use that on the tree working backwards until you find that yes, that anonymized user’s latest signal key is XYZ. Then you double check that both Cloudflare and Trail of Bits agree with Signal’s chain of events (that it didn’t present a different tree to you).