As the distributed ledger technology underlying cryptocurrencies such as Bitcoin and Ethereum, blockchain has empowered various industries, such as supply chain management, healthcare, government services, e-voting, etc. However, the ever-growing ledger on each node has been the main bottleneck for blockchain scalability as the network scale expands, which worsens in blockchain-enabled IoT scenarios with resource-limited devices. With the support of the Reed–Solomon (RS) code, the Cuckoo-Store (CS), a ledger storage optimization engine, is proposed in this paper to dramatically decrease the storage burden on each node by encoding the ledger as data segments with redundancy and distributing them to multiple nodes. These distributed data segments can be collected and decoded using RS code to recover the original ledger. Furthermore, the Cuckoo filter (CF) is used to guarantee the integrity of the encoded segments, which helps detect the forged segments and facilitates the process of ledger recovery. Theoretical analysis and simulation results show that the CS engine can decrease the storage in each node by more than 94%, and the original ledger can be recovered efficiently with acceptable communication overheads.