Sucks that it requires iCloud Keychain enabled, and also removing your appleid from any legacy macs and iphones. Wish they explained the reasons for this, because I'm having a hard time seeing one.
It’s described in more detail here:
https://security.apple.com/blog/imessage-contact-key-verific...
(This is end-to-end encrypted, by the way; Apple can’t get at people’s private keys.)
And this is a new protocol, so no surprise it doesn’t work with older operating systems. (It doesn’t say you have to remove your Apple ID completely, just log out of iMessage.)
And I could totally see Apple making non-verified contacts' bubbles a different color sooner rather than later...