Various designs exist for a Public Key Infrastructure (PKI), each with its own inherent security and optimization issues. Certain properties of the Bitcoin blockchain and its derivatives - mainly the safeguards against the manipulation of data once it is stored - solved many of the PKI issues, and various designs for a blockchain-based PKI were proposed. Such blockchain-based PKIs required enormous amounts of storage space as the number of blocks and the number of users increased and thus became less efficient in performing operations such as inclusion, key retrieval, key verification, etc. In this article, we propose a new approach to the blockchain-based PKI, which while being as tamper-proof as the current blockchain-based PKIs, is very efficient in its space requirements and the time taken for key verification.