Systems and techniques are provided for a decentralized database associating public keys and communications addresses. A signed secret message may be sent by a validator computing device of a peer-to-peer network for a decentralized database to a communications address from a request for verification entry in a verification queue of the decentralized database. A second request for verification including the communications address and a user-signed secret message may be received. The user-signed secret message may be verified using a public key from the request for verification entry in the verification queue. The communications address and public key may be written to a verified database of the decentralized database when verifying the user-signed secret message causes a number of user-signed secret messages received in requests for verification with the communications address and successfully verified to meet a threshold number.