Mobile Ad-hoc networks have various implementation constraints such as infrastructure-free, no trusted authority, node mobility, and the limited power and small memory of mobile device. And just like wired networks, various security issues such as authentication, confidentiality, integrity, non-repudiation, access control, availability and so on have been arisen in mobile Ad-hoc networks. But we focus on authentication of these security issues because it is quitely affected by the characteristics of networks. In this paper, we propose the authentication protocol that can limit the size of certificate repository as $log_2N$ and assures to make a trusted certificate path from one node to another, adopting the concept of Hamming distance. Particularly, our protocol can construct a trusted certificate path in spite of decreasing or increasing the number of nodes in mobile Ad-hoc network.