A new solution scheme called certificate revocation threaded binary sorted Hash trees (CRTBSHT) for certificate revocation problem in public key infrastructure (PKI) is proposed in this paper. Previous solution schemes including traditional X.509 certificates system's certificate revocation lists (CRL), Micali's Certificate Revocation System (CRS), Kocher's Certificate Revocation Trees (CRT), and Naro-Nossim's 2-3 certificate revocation trees (2-3CRT), but no one is perfect. The new scheme keeps the good properties of CRT that it is easy to check or prove whether a certificate is revoked which only needs the related path values but does not need the whole CRT values and overcomes the disadvantage of CRT that any update will cause the whole CRT to be conmputed completely. The new scheme has referential value to the PKI engineering practice.