Abstract For numerous applications, it is essential to reliably link a public key with its owner. The current solution is to employ the well-known Public Key Infrastructure (PKI), represented by a trusted certificate authority (CA), to fulfill this assignment by signing the certificate for the public key after validating its owner. However, due to the centralized architecture, it raises the single-point failure problem with unpredictable threats. In this paper, we present a distributed certificate scheme, referred to as Cecoin which is inspired by the well-known Bitcoin by employing its irreversible unforgeability and public verifiability. In Cecoin, the certificates can be treated as currencies and recorded on block chain, which removes the single point failure problem. The miners can verify the validity of certificates following a set of rules to ensure ownership consistency, and allow an identity to bind multiple public-key certificates. For efficient retrieval and verification of certificates, and quick operations, we incorporate the modified Merkle Patricia tree and employ it to implement a distributed Certificate Library. To allow the owner to transfer the possession of identity, we design an online fair exchange protocol without a trusted third party. Security and efficiency analyses show that our Cecoin provides strong security with desirable efficiency.