In general for Vehicle-to-Vehicle (V2V) communication, message authentication is performed on every received wireless message by conducting verification for a valid signature, and only messages that have been successfully verified are processed further. In V2V safety communication, there are a large number of vehicles and each vehicle transmits safety messages frequently; therefore the number of received messages per second would be large. Thus authentication of each and every received message, for example based on the IEEE 1609.2 standard, is computationally very expensive and can only be carried out with expensive dedicated cryptographic hardware. An interesting observation is that most of these routine safety messages do not result in driver warnings or control actions since we expect that the safety system would be designed to provide warnings or control actions only when the threat of collision is high. If the V2V system is designed to provide too frequent warnings or control actions, then the system would be a nuisance to the driver. Therefore it is reasonable to define an approach where messages are first processed and then authenticated using verification on-demand. In this paper we describe such an approach and discuss its implementation for V2V safety system. It is shown that Verify-on-Demand (VoD) is a practical and scalable approach for broadcast authentication in V2V safety communication while conforming to the IEEE 1609.2 standard.