Secure and efficient identity authentication is a fundamental requirement in vehicular ad-hoc networks (VANETs); however, it remains challenging due to the highly dynamic network topology, stringent latency constraints, and the need for conditional privacy preservation. Existing authentication schemes either rely on public key infrastructures (PKI) with complex certificate management or introduce partially decentralized designs that still depend on trusted authorities, leading to inefficiencies and single points of failure. In this paper, we propose EBDA, an Ethereum-based fully distributed authentication mechanism for VANETs. The core innovation of EBDA is to replace the traditional PKI certificate system with a blockchain-maintained Graph of Trust (GoT). Through three dedicated smart contracts, EBDA  fully decentralizes the management of vehicle identities and pseudonyms. Vehicles use pseudonyms to preserve privacy in Vehicle-to-Vehicle communications, while authentication is achieved certificate-free via transitive trust within the GoT. Importantly, latency-sensitive operations like message verification are executed off-chain through local checks, meeting VANETs’ strict real-time requirements. A prototype implementation and extensive evaluations demonstrate that EBDA significantly reduces authentication latency by at least 22.93% compared with representative blockchain-assisted and PKI-based baselines while maintaining low computational and storage overhead. These results confirm the feasibility of deploying GoT-based decentralized authentication in practical VANET environments.