Large cloud providers such as AWS and IBM now provide managed blockchain platforms, showcasing an active interest in blockchains. Unfortunately, blockchains provide poor performance and scalability. This is true even for the Execute-Order-Validate (EOV) style of blockchains which improves over the traditional Order-Execute architecture. We experimentally show that EOV platforms scale poorly using both vertical and horizontal scaling approaches. We find that the throughput is bottlenecked by the Validation and Commit phases, which poorly utilize the resources, limiting performance and scalability. We introduce three ideas to improve the performance, scalability, and cost-efficiency of EOV platforms. We first propose a provably correct way to pipeline the Validation and Commit phases. We then introduce a new type of node called sparse peer that validates and commits only a subset of transactions. Finally, we propose a technique that makes it possible for these systems to elastically scale as per the load. Our implementation provides 3.7x and 2.1x higher throughput than Hyperledger Fabric and FastFabric for the same infrastructure cost while providing their peak throughputs at 87% and 50% lower cost. It also makes dynamic horizontal scaling practical by providing 12-26X faster scale-up times.