This work proposes authentication based on identity as a way to increase the efficiency and security of communications in vehicular ad-hoc networks. When using identity-based cryptography to achieve certificateless authentication, membership revocation is not a trivial problem. Thus, in order to improve the performance of revocation in such networks, the use of a dynamic authenticated data structure based on perfect k-ary hash trees combined with a duplex version of the new standard SHA-3 is here presented. Efficient algorithms in the used revocation trees allow reaching a refresh rate of at most simple updates per inserted node. Consequently, the proposal is especially useful for situations with frequent revocations, which are foreseeable when vehicular ad- hoc networks are widely deployed.