CertLedger: A New PKI Model with Certificate Transparency Based on Blockchain

1. INTRODUCTION

• CAs bear absolute responsibility for issuing correct certificates, but compromise or noncompliance can result in fake but valid certificates.CAs are expected to follow rules set out in Certificate Policy and Certificate Practice Statement documents.Source: §1 · p. 1
• Examples include Stuxnet signed with compromised Taiwanese CA keys, nine fraudulent Comodo certificates, and 531 fraudulent DigiNotar certificates.The DigiNotar certificates targeted valuable domains, and at least 300,000 unique IPs were detected using Google services through them.Source: §1 · p. 1
• Other cases involved Trustwave and Turktrust subCA certificates used for traffic introspection, and fraudulent CNNIC subCA certificates.The passage also describes Lenovo Superfish’s local CA, unauthorized Symantec certificates, and Blue Coat’s becoming a Symantec SubCA.Source: §1 · p. 2
• Key pinning, crowdsourcing, and pushing revocation information to browsers were initial solutions, but failed due to scalability problems.The passage says these solutions were partly implemented.Source: §1 · p. 2

1.1.1. Sovereign Key (SK) Cryptography

• The chronological survey describes SK, where domains publish service keys to append-only TimeLine Servers, but the servers provide no inclusion proof and clients must trust their Mirrors.Domains use sovereign key pairs and add a self-signed certificate to the TLS chain; clients reject connections if the signature cannot be verified.Source: §1.1.1 · p. 2, §1.1 · p. 2

1.1.2. Certificate Transparency (CT)

• CT uses append-only Merkle logs, SCTs, tree heads, and proofs; monitors inspect certificates while clients audit log consistency.Clients may refuse connections when SCTs are absent or cannot be verified.Source: §1.1.2 · p. 2
• A log controlling multiple tree views can enable split-world impersonation in CT [25], while monitors and auditors may see only genuine or internally consistent fraudulent proofs.An adversary can present a fake but valid certificate and bogus SCT to targeted clients; monitors and other auditors may not detect the attack because they receive only one view.Source: §1.1.2 · pp. 2–3

1.1.3. Certificate Issuance and Revocation Transparency (CIRT)

• CIRT adds proofs for revoked, current, and never-issued certificates using two public Merkle logs, but remains vulnerable to split-world attacks [25].Source: §1.1.3 · p. 3

1.1.4. Accountable Key Infrastructure (AKI)

• AKI distributes PKI accountability among CAs, log operators, and validators; domains select trusted entities and management rules, while clients verify certificates using preinstalled CA certificates and log keys.Integrity Log Server Operators store certificates and registration, update, and revocation information; Validators monitor their operations.Source: §1.1.4 · p. 3
• AKI assumes trusted CAs, logs, and validators do not collude; a compromised CA and log can enable an undetectable split-world attack.The paper characterizes the no-collusion assumption as unrealistic against a strong adversary.Source: §1.1.4 · p. 3
• AKI revocation is weak because a domain owner can request it without confirmation, allowing an attacker with the domain private key to revoke its certificate.Source: §1.1.4 · p. 3
• AKI clients must trust CAs, ILSs, and Validators, burdening them with management of multiple trusted entity types.Source: §1.1.4 · p. 3

1.1.5. Attack Resilient PKI (ARPKI)

• ARPKI requires two CAs and an ILS, with signed proofs verified by clients, but colluding certificate entities can mount split-world attacks and ILS synchronization creates a single point of failure.The domain selects the trusted entities; one CA validates another CA and the ILS, while the ILS coordinates certificate synchronization among ILSs.Source: §1.1.5 · p. 3

1.1.6. NameCoin and CertCoin

• NameCoin supports self-signed TLS certificates for .bit domains, while Certcoin adds decentralized registration, lookup, verification, and revocation but lacks identity verification.First-claim ownership can deceive identities; compromised online and offline keys can make identities unrecoverable, and blockchain lookups are inefficient, while added accumulators and distributed hash tables add complexity.Source: §1.1.6 · p. 4

1.1.7. Distributed Transparent Key Infrastructure (DTKI)

• DTKI uses certificate and mapping log maintainers plus mirrors, with browsers verifying mapping and certificate proofs; domains use master certificates to request TLS certificates.CAs issue certificates but are not the sole source of trust.Source: §1.1.7 · p. 4
• DTKI’s assumption that master certificates are genuine leaves it vulnerable to undetectable split-world attacks if a CA and CLM are compromised.The paper argues that CAs may issue fake certificates because of inadequate security controls or processes.Source: §1.1.7 · p. 4

1.1.8. Blockchain-based Certificate and Revocation Transparency

• Wang et al.’s blockchain scheme periodically records certificates and revocation status; servers send clients a certificate transaction and Merkle path for verification against synchronized block headers.Separate publishing keys sign transactions and are initially certified by web servers already on the blockchain; transactions have validity periods.Source: §1.1.8 · p. 4
• The blockchain proposal’s publishing-key trust can be undermined by bogus domains, and its revocation transparency still depends on CAs publishing revocation data.Its proposed remedy of relying on more publicly trusted CAs leaves the trust level unclear; compromised or malfunctioning CAs may also fail to provide CRLs or OCSP responses on time.Source: §1.1.8 · pp. 4–5
• Clients can accept an unexpired transaction for a revoked or updated certificate because they check transaction inclusion, not the certificate’s final state.An adversary can send the transaction and its Merkle proofs during a TLS handshake.Source: §1.1.8 · p. 5
• The blockchain proposal incurs high storage costs by periodically adding certificates and publishing keys, recording CRLs per revoked certificate, and using large headers.The headers include DNS names found in block transactions.Source: §1.1.8 · p. 5

1.2. Ongoing Security Issues

• Adversaries controlling CAs or log operators can show victims different log views; gossip detects this only under specific conditions [25] [35].Detection requires enough gossiping clients and servers, with at least some seeing the genuine log and requesting a consistency proof.Source: §1.2 · p. 5
• Revocation depends on CAs, so compromised or malfunctioning CAs may leave browsers accepting revoked certificates, while incompatible validation and revocation implementations are error prone.Browsers rarely check whether certificates have been revoked.Source: §1.2 · p. 5
• TLS clients rely on trusted CA certificates or other public keys; removing compromised roots burdens clients, and injected fake CA certificates enable undetected MITM attacks.Removal can leave outdated operating systems or applications vulnerable.Source: §1.2 · p. 5

Our Contributions

• CertLedger aims to resist split-world attacks, make revocation more transparent, and provide unique, efficient, and trustworthy certificate validation.It uses a blockchain-based public log to validate, store, and revoke TLS certificates.Source: §1.3 · p. 5
• The contributions also include eliminating clients’ trusted key stores, preserving TLS client privacy, and removing external auditing requirements through the inherent public-log architecture.Source: §1.3 · p. 5
• CertLedger aims to enable efficient, prompt monitoring to minimize attack duration and provide transparency in trusted CA management.Source: §1.3 · p. 5
• The paper provides detailed security and performance analysis of CertLedger and compares it with recent works.Source: §1.3 · p. 5

• Section 2 describes how public blockchain addresses the previously mentioned PKI problems.Source: §1.4 · p. 5
• Section 3 presents CertLedger, a blockchain-based PKI model with certificate transparency.Source: §1.4 · p. 5
• Sections 4 and 5 analyze CertLedger’s security and performance, respectively.Source: §1.4 · p. 5
• Section 6 compares CertLedger with existing schemes, and Section 7 concludes with future work.Source: §1.4 · p. 5

2. HOW PUBLIC BLOCKCHAIN SOLVES PKI PROBLEMS?

• A decentralized, consensus-updated public log that cannot be reverted is presented as preventing a single operator from creating split views.The paper links this design to CT’s client-gossip requirement for consistent views.Source: §2 · pp. 5–6
• On-chain certificates enable one-time trusted-path construction and unified revocation checks, including owner-initiated revocation, eliminating CRL and OCSP checking.The paper says this also makes the complete revocation process more transparent and avoids error-prone differences in browser revocation implementations.Source: §2 · p. 6
• Storing trusted CA certificates on-chain lets TLS clients avoid storing them because the blockchain admits certificates issued only by trusted CAs.Source: §2 · p. 6

2.1. Blockchain Characteristics for PKI

• Certificate logs require persistent state, distributed writers to reduce manipulation, no vulnerable always-online TTP, and public verifiability; writer trust and identity also matter.Known writers should be dispersed globally, while even trusted writers may be controlled by a strong adversary.Source: §2.1 · pp. 6–7
• CertLedger requires smart contracts, consensus without temporary forks, timely block confirmation, and efficient final-state verification and Merkle proofs.The paper identifies Ethereum, Neo, and Ontology as suitable architectures, with PBFT or DBFT as consensus options that avoid temporary forks.Source: §2.1 · p. 7

3. CERTLEDGER

• CertLedger uses blockchain state objects to manage TLS certificates and revocation, trusted CA certificates, accounts and tokens, and fraud reports.Each state object is a digital document containing data and immutable smart contract code; transactions trigger and track state changes.Source: §3 · p. 7

3.1. Entities

• CAs issue certificates and may record or revoke them without CRL or OCSP; the threshold-key CertLedger Board manages trusted CAs, and light clients verify certificates through CertLedger.The Board’s account private key is shared among members in a threshold fashion.Source: §3.1 · p. 8

3.2.1. Adversary Capabilities

• CAs, CertLedger clients, and miners may behave maliciously, while at most t of n CertLedger Board members are assumed corrupted.The model includes CAs issuing fake but valid certificates.Source: §3.2.1 · p. 8

3.2.2. Assumptions

• The model assumes an insecure network, some clients honest under the blockchain consensus model, and secure underlying cryptographic primitives and blockchain architecture.Source: §3.2.2 · p. 8

3.3. PKI Functionalities of CertLedger

• The Board audits CA applicants and adds compliant certificates through threshold-signed transactions; it can mark a CA untrusted after further audit failure or proven misbehavior, revoking that CA’s TLS certificates.Smart contracts check transaction signatures and CA certificate validity; the trusted-CA object triggers the change to issued certificate statuses.Source: §3.3 · pp. 8–9
• Domain owners or CAs add TLS certificates through signed transactions and can revoke valid, unexpired certificates using a request signed by the certificate or its issuing CA.The Domain State Object validates requests and changes certificate status to revoked.Source: §3.3 · p. 9
• A domain owner can report a fake but valid certificate with proof of domain ownership; the accused CA can plead, and the Board may mark it untrusted if unconvinced.The Fraud Report State Object checks certificate presence, subject alternative names, and the genuineness of the certificate used to sign the report.Source: §3.3 · pp. 9–10
• Clients obtain certificate state proofs from full nodes and verify them against a block header; after checking the proof and certificate validity, they need no further certificate validation.During a TLS handshake, the domain sends the certificate and its proof for an agreed latest block.Source: §3.3 · pp. 10–11

Property 1

• With at most t of n board members corrupted and secure blockchain consensus, CertLedger’s single consensus-updated log prevents clients from receiving split views.If more than t board members are corrupted, a fraudulent CA may be added, but the paper says this cannot target only selected victims; detection can prompt replacement of board members or a fork.Source: §4 · p. 11

Property 2

• Domain Owners can trigger revocation of compromised certificates without CA consent when they can use the private key, and on-chain status changes are transparent and trackable.CAs can create revocation transactions when a key is unusable; if a compromised certificate’s key is unavailable to the owner, the owner requests revocation from the CA.Source: §4 · pp. 11–12

Property 3

• Clients receive the certificate’s final state and proofs during the TLS handshake and verify revocation using the block-header state-tree hash, without CA CRL or OCSP services.Source: §4 · p. 12

Property 4

• Clients can verify certificate authenticity and revocation status during the TLS handshake without another network connection, preserving their privacy.Source: §4 · p. 12

Property 5

• Trusted-CA requirements are defined in open standards, with threshold board inspections conducted periodically and fraud reports and CA justifications recorded for review.After inspecting the evidence, board members can change a Trusted CA’s status to Untrusted through a threshold decision.Source: §4 · p. 12

Property 6

• CertLedger Clients do not need Certificate/Key Stores for trusted-CA certificates or log public keys because the blockchain architecture assures their trustworthiness and integrity.Source: §4 · p. 12

Property 7

• CertLedger eliminates the requirement for external log auditors.Source: §4 · p. 12

CertLedger

• New blocks require client consensus, removing the need for external auditing of the log’s cryptographic consistency and behaviour.Source: CertLedger · p. 12
• CertLedger validates TLS certificates against international standards before ledger entry, so clients check only certificate existence and revocation status, avoiding vendor validation differences.The paper notes that inconsistent vendor implementations can cause different crawlers to have different connection outcomes for the same TLS-protected domain.Source: CertLedger · p. 12
• CertLedger does not prevent fake-valid TLS certificate issuance, but event watchers can promptly alert domain owners to certificate changes and fraudulent revocations, minimizing attack duration.Watchers can notify owners through channels such as e-mail or SMS.Source: CertLedger · p. 13

5.1. Storage

• All TLS certificates require roughly 84 GB of storage; Full Nodes need about 84 GB per year, while light-node CertLedger Clients need approximately 50 MB for two years.The Full Node estimate assumes an average one-year certificate lifetime; storing the transactions costs about $3.4 for a non-mining full node.Source: §5.1 · p. 13

5.2. Communication

• Full node clients exchange transactions and blocks with P2P peers, while light nodes download only block headers and receive domain state and Merkle proofs during TLS connections.The state and proofs are carried in TLS extensions, adding communication overhead between the client and domain.Source: §5.2 · pp. 13–14

5.3. Computation

• Modified Patricia trees can support certificate lookup, insertion, and update operations in O(log(n)), where n is the number of TLS certificates.The data structures are intended to let CertLedger Clients verify final certificate state efficiently.Source: §5.3 · p. 14

• CertLedger provides existence and revocation proofs for all TLS certificates, unlike CT, AKI, and ARPKI; may lack revocation proofs when CAs provide incorrect CRLs or no OCSP service.DTKI also provides both existence and revocation proofs.Source: §6 · p. 14
• Full-node CertLedger clients check certificate existence and revocation locally without external proofs during a successful TLS handshake.Light-node clients instead receive and verify the certificate’s final state and related Merkle Audit Proof from the domain; prior approaches may require proof requests or conventional revocation checks.Source: §6 · p. 14
• CertLedger places all TLS certificates in one log with multiple copies, avoiding the changing set of independent logs that burdens CAs and domain owners.Only the single log needs monitoring, and clients need no trusted key to verify its proofs.Source: §6 · p. 14
• CertLedger’s P2P consensus log is held by full-node clients, while light-node clients verify domain-provided certificate state and Merkle proofs locally using block headers.This avoids the permanent log availability dependency described for prior proposals.Source: §6 · p. 14
• CertLedger requires no external auditing and can be monitored easily and promptly.Prior approaches assign auditing to external auditors, validators, or TLS clients, and some do not provide efficient monitoring.Source: §6 · p. 14
• CertLedger stores and manages trusted CA certificates centrally, so clients need no trusted keys or certificates for TLS certificate validation.Certificates are checked against trusted CAs when added; during handshakes, clients only check revocation status.Source: §6 · p. 15
• CertLedger fully preserves TLS clients’ privacy.The comparison contrasts this with approaches involving client log queries or OCSP revocation checks that can expose browsing history.Source: §6 · p. 15

CONCLUSION AND FUTURE WORK

• Existing public-log proposals, including CT, AKI, ARPKI, and DTKI, remain vulnerable to split-world attacks.The paper motivates these proposals by serious security incidents involving corrupted CAs that issued fake but valid TLS certificates.Source: §7 · p. 15
• CertLedger lets all TLS clients verify the log’s final state, making split-world attacks impossible, and provides transparency for certificate revocation and trusted CA management.The model places all TLS certificates, revocation status, and trusted CA management processes in CertLedger.Source: §7 · p. 15
• Future work includes implementing CertLedger on an existing blockchain framework and conducting detailed performance and usability analyses.The paper also proposes an automated mechanism without human intervention to eliminate CertLedger Board Members and increase transparency in trusted CA management.Source: §7 · p. 15