An on-ledger certificate authority operates a node of a distributed ledger that controls a certificate issuance store and a certificate revocation store. When the certificate authority issues a certificate, the node issues a ledger transaction with an instruction to store a validation hash of the certificate in the issuance store, and when a certificate is revoked, a ledger transaction with an instruction to store the serial number of the certificate in the revocation store. As such transactions propagate throughout the ledger, the instructions are executed by on-ledger verifiers in their local replicas of the stores. An on-ledger verifier validates a certificate by verifying that its serial number is not in the revocation store while its validation hash is in the verifier's replica of the issuance store.