Routing security has a great importance to the security of Mobile Ad Hoc Networks (MANETs). There are various kinds of attacks when establishing the routing path between the source and destination. The adversaries attempt to deceive the source node and get the privilege of data transmission. Then, they try to launch the malicious behaviors such as passive or active attacks. Due to the characteristics of the MANETs, e.g. dynamic topology, open medium, distributed cooperation, and constrained capability, it is difficult to verify the behaviors of nodes and detect malicious nodes without revealing any privacy. In this paper, we present PVad, an approach conducting privacy-preserving verification in the routing discovery phase of MANETs. PVad tries to find the existing communication rules via the association rules instead of making the rules. PVad consists of two phases, a reasoning phase deducing the expected log data of the peers, and a verification phase using a Merkle Hash Tree to verify the correctness of the derived information without revealing any privacy of nodes on the expected routing paths. Without deploying any special nodes to assist the verification, PVad can detect multiple malicious nodes by itself. To show that our approach can be used to guarantee the security of the MANETs, we conducted our experiments in NS3 as well as the real router environment, with the improvement of the detection accuracy by 4% on average compared to our former work.