In recent years, vaccine safety incidents have occurred frequently. To protect vaccine safety, researchers have proposed to use blockchain to secure the vaccine circulation process. Technically, blockchain has some limitations in solving vaccine and other supply chain problems, such as large on-chain storage consumption and low throughput. To better alleviate these restrictions, we propose an improved, blockchain-based, storage-efficient vaccine safety protection scheme in this work. Specifically, we first model the vaccine circulation process. We then design a system to protect vaccine circulation using blockchain, cloud, and cryptographic mechanisms. The proposed system leverages the cloud to implement the vaccine circulation model. Correspondingly, it uses the blockchain to store circulating data certificates and signatures. We evaluated the proposed conceptual model using a consortium blockchain. The experimental results show that the proposed system is efficient.