Although there have been various proposals to build large-scale PKIs, there appears to be no research publicly available on the underlying certificate store which will be required to support such a PKI. This paper analyses the requirements for, and presents the design of a general-purpose certificate store which places few constraints on the underlying computer hardware or operating system used, provides a high degree of scalability (from single end users up to the corporate/CA level), and provides the level of reliability, availability and error recovery required of such an application and stipulated in a number of standards which cover CA operation.