PBCert: Privacy-Preserving Blockchain-Based Certificate Status Validation Toward Mass Storage Management

Shixiong Yao, Jing Chen, Kun He, Ruiying Du, Tianqing Zhu, Xin Chen

Abstract

Modern Public Key Infrastructure (PKI) faces significant challenges, notably the single-point-of-failure inherent in Certificate Authorities (CAs) and the leakage of user privacy during certificate status validation. While blockchain-based solutions offer public auditability, they often struggle with storage scalability and privacy preservation. This paper introduces PBCert, a novel scheme that decouples the control and storage planes of certificate revocation. By storing only minimal control information on-chain and utilizing an "obscure response" mechanism for queries, PBCert achieves both high scalability and robust user privacy.

Introduction

The security of the internet relies heavily on PKI, yet traditional models are increasingly vulnerable. Attacks on CAs can compromise the entire trust chain, leading to the proposal of decentralized or publicly auditable systems like Certificate Transparency (CT) and various blockchain-based PKIs. However, these advancements introduce new problems: "blockchain bloat" from massive revocation data and privacy risks where validation servers can track user browsing habits.

Taxonomy of PKI security challenges and existing solutions

As shown in the taxonomy above, security efforts in PKI generally target certificate revocation efficiency, privacy protection, and mitigating CA failures. PBCert specifically addresses the intersection of these domains by leveraging blockchain for auditability while optimizing for mass storage and privacy.

The PBCert Architecture

PBCert addresses the scalability bottleneck by separating the management of revoked certificates into two distinct planes:

  1. Control Plane (On-chain): The blockchain acts as a ledger for minimal control metadata. Instead of full certificate details, it stores only certificate hashes, operation types (e.g., revocation), and the root of a Merkle hash tree. This ensures that the blockchain remains lean and efficient, regardless of the volume of revoked certificates.
  2. Storage Plane (Off-chain): Detailed revocation information, encapsulated in CertRevo structures, is stored in external data stores (OCSP servers). These servers maintain a Merkle tree of all revoked certificates, the root of which is anchored to the blockchain to prevent tampering.

Privacy-Preserving Validation via Obscure Response

A critical contribution of PBCert is its "obscure response" mechanism, designed to prevent validation servers from learning which specific website a client is visiting.

In traditional OCSP, a client sends the full hash of a certificate to check its status. In PBCert, the client sends only a prefix—the first $n$ bits—of the certificate hash. The server then returns a Bloom Filter containing all revoked certificates that match this prefix. The client performs the final check locally. This approach provides a form of k-anonymity, hiding the user's specific target within a set of certificates sharing the same prefix.

Performance and Evaluation

The authors evaluated PBCert using a prototype built with Node.js, OpenSSL, and Ethereum. Key findings include:

  • Storage Scalability: Unlike previous blockchain PKIs where block size grows linearly with the number of revocations, PBCert maintains a stable block size.
  • Efficiency: The system was tested with up to 10 million certificates. For a revocation list of 500,000 items, the obscure response requires downloading only a few kilobytes, making it highly efficient for mobile and low-bandwidth clients.
  • Latency: Total validation time is approximately 459ms. While slightly higher than non-private legacy methods, it is competitive with other secure, blockchain-based alternatives.

Conclusion

PBCert demonstrates that blockchain-based PKI can be both scalable and private. By offloading bulk data to a storage plane and using prefix-based queries with Bloom Filters, the system mitigates the primary drawbacks of decentralized certificate management. Future work will focus on optimizing the prefix length $n$ to balance the trade-off between user privacy and communication overhead.

Summary updated

Abstract

In the recent years, the vulnerabilities of conventional public key infrastructure are exposed by the real-world attacks, such as the certificate authority’s single-point-of-failure or clients’ private information leakage. Aimed at the first issue, one type of approach is that multiple entities are introduced to assist the certificate operations, including registration, update, and revocation. However, it is inefficient in computation. Another type is to make the certificate information publicly visible by bringing in the log servers. Nevertheless, the data synchronization among log servers may lead to network latency. Based on the second approach, the blockchain-based public key infrastructure schemes are proposed. Through these type of schemes, all the certificate operations are stored in the blockchain for public audit. However, the issue of revoked certificates’ status storage is worth paying attention, especially in the setting with massive certificates. In addition, the target web server that a client wants to access is exposed in the process of certificate status validation. In this paper, we propose a privacy-preserving blockchain-based certificate status validation scheme called PBCert to solve these two issues. First, we separate the revoked certificates control and storage plane. Only the minimal control information (namely, certificate hashes and related operation block height) is stored in the blockchain and it uses external data stores for the detailed information about all revoked certificates. Second, we design an obscure response to the clients’ certificate status query for the purpose of privacy preserving. Through the security analysis and experiment evaluation, our scheme is significant in practice.
BibTeX
@inproceedings{yao2018pbcert,
  author = {Shixiong Yao and Jing Chen and Kun He and Ruiying Du and Tianqing Zhu and Xin Chen},
  title = {{PBCert: Privacy-Preserving Blockchain-Based Certificate Status Validation Toward Mass Storage Management}},
  booktitle = {IEEE Access},
  year = {2018},
  doi = {10.1109/access.2018.2889898},
}
Figure