With the breakthroughs in sensor technology and internet of things, Vehicular Ad Hoc Network (VANET) is developing into a new generation. The technical challenges of current VANET are decentralized architecture deployment and privacy protection. Since the blockchain owns the characteristics of being decentralized, distributed, collective maintenance and non-tampering, this paper designs a novel decentralized architecture using blockchain technology, which is called blockchain-based VANET. The blockchain-based VANET involves four major stages: blockchain set-up, registration of vehicles, SBMs upload, and blockchain record. It can effectively address the problems of centralization and mutual distrust between entities in current VANET. For protecting identity and location privacy, we propose UGG, IPP and LPP algorithms with the way of dynamic threshold encryption and k-anonymity unity in the stage of SBMs upload of blockchain-based VANET. To quantify the availability of k-anonymity unity, we propose two indicators: connectivity and average distance. Extensive simulations have been conducted to validate the effectiveness of blockchain-based VANET. We analyze the simulation results from four aspects: system time, average distance, connectivity, and privacy leakage. The simulation results show that our proposed architecture performs better in terms of processing time than current architectures. Furthermore, our proposed architecture shows its superior in the aspect of protecting identity and location privacy.