Virtual block devices are heavily used to fulfill the block storage needs of hypervisor-based virtual machine (VM) instances through either local or remote storage spaces. However, a high degree of VM co-location makes it increasingly difficult to physically provision all the necessary block devices using only local storage space. Also, the local storage performance degrades rapidly as workloads interleave. On the other hand, when block devices are acquired through remote storage services, the aggregated network traffic may consume too much cluster-wide network bandwidth in a cloud data center. In order to solve these challenges, we propose a caching scheme for virtual block devices within the hypervisor. The scheme utilizes the physical node's finite local storage space as a block-level cache for the remote storage blocks to reduce the network traffic bound to the storage servers. This allows hypervisor-based compute nodes to serve the hosted VMs' I/O (Input/Output) requests from its local storage as much as possible while enabling VMs to exercise large storage space beyond the capacity of local disks for new virtual disks. Caching virtual disks at block-level in a cloud data center poses several challenges in maintaining high performance while adhering to the virtual disk semantics. We have realized the proposed scheme, called vStore, on Xen hypervisor nodes with factual assessment on its design effectiveness and implementation efficiency. Our comprehensive experimental evaluations show that the proposed scheme substantially reduces the network traffic (49% on average), and incurs less than 12% overheads on the storage I/O performance.