The rapid advancement of the Internet of Vehicles (IoV) has led to a massive growth in data received from IoV networks. The cloud storage has been a timely service that provides a vast range of data storage for IoV networks. However, existing data storage and access models used to manage and protect data in IoV networks have proven to be insufficient. They are centralized and usually accompanied by a lack of trust, transparency, security, immutability, and provenance. In this paper, we propose VBlock, a blockchain-based system that addresses the issues of illegal modification of outsourced vehicular data for smart city management and improvement. We introduce a novel collusion-resistant model for outsourcing data to cloud storage that ensures the network remains tamper-proof, has good data provenance and auditing, and solves the centralized problems prone to the single point of failure. We introduced a key revocation mechanism to secure the network from malicious nodes. We formally define the system model of VBlock in the setting of a consortium blockchain. Our simulation results and security analysis show that the proposed model provides a strong security guarantee with high efficiency and is practicable in the IoV environment.