Blockchains are known to provide verifiable tamper-resistant trails of accepted transactions. This guarantee comes at the considerable cost of storage and computational power, thereby restricting its application. Current research has focused on alternatives such as proof of reputation, proof of stake, and proof of elapsed-time to reduce the computational burden on the blockchain participants. Orthogonal to this effort, we focus on a specific set of applications that cannot commit much storage space and computational resources, but require only reasonable guarantees on the validity of transactions. To this end, we introduce blockchain design alternatives, collectively called ApproxBC, that can provide proof of transactions with provable confidence bounds. Consequently, ApproxBC can considerably reduce the computation and storage resources required, making them suitable for resource-constrained Internet of Things environments. We also showcase two approximation-tolerant applications that can leverage the quicker computation and smaller storage requirements. © 2017 IEEE.