The invention discloses a vehicle networking structure based on a block chain and a working method thereof. The vehicle networking structure comprises an interconnected vehicle entity, a vehicle-mounted unit OBU, a roadside unit RSU, a core network and a block chain network. It has the typical characteristics of decentralization, distribution, collective maintenance and incapability of tampering.It can effectively solve the problem of centralization of traditional vehicle networking architecture and mutual distrust between entities. At that same time, the invention provides an undirected graph generation method, an identity privacy protection method and a location privacy protection method when the beacon information is uploaded by a vehicle, thereby solving the problem of identity and location privacy disclosure of a vehicle networking architecture based on a block chain.