Blockchain holds a big promise for Public Key Infrastructure (PKI) designs. Prominent systems, such as Keybase and CONIKS, tend to be centralized, something that eases the update of keys and provides good availability. Centralized designs, however, require users to trust that the source of authority acts honestly at all times, and does not perform surveillance.
ClaimChain is a decentralized PKI design, where users maintain repositories of claims implemented as hash chains: data structures that allow for efficient verification of the integrity and authenticity of their content. Claims relate to the key material of the owners, or their beliefs about public keys of others. In the latter case, cross-referencing serves as a way of efficient and verifiable vouching about states of other users. In practice, such information would reveal the social graph of the chain owners and even their communication patterns. To solve this privacy issue, we use cryptographic verifiable random functions to derive private identifiers that are re-randomized on each chain update, encrypted to a given set of authorized readers. In that way, chain owners can not present different views to authorized readers of the same contact. ClaimChain allows to detect chain compromises, manifested as forks of hash chains, and to implement various social policies for deriving decisions about the latest state of users in the system.
Evaluation of a prototype implementation indicates that ClaimChain can scale to accommodate the needs of large groups at an acceptable computational and bandwidth overhead cost. Interoperability with PGP makes it possible for users to gradually deploy ClaimChain locally. Email providers that wish to adopt ClaimChain will participate as an additional factor in the social authentication process. Arguably, ClaimChain constitutes an example that decentralization in combination with modern cryptography allow for increased robustness to adversarial central authorities, and offer comparable availability, as well as more options for supporting privacy.