The mechanisms to prevent against Sybil attacks are to utilize
identity certificates [11]. The basic idea is very simple. The setup
server, before deployment, assigns each sensor node some unique
information. The server then creates an identity certificate
binding this node‟s identity to the assigned unique information,
and downloads this information into the node. To securely
demonstrate its identity, a node first presents its identity
certificate, and then proves that it possesses or matches the associated unique information. This process requires the
exchange of several messages. Merkle hash tree can be used as
basic means of computing identity certificates [11]. The Merkle
hash tree is a vertex-labeled binary tree, where the label of each
non-leaf vertex is a hash of the concatenation of the labels of its
two child vertexes. The primary path of a leaf vertex is the set of
vertexes on the path from the leaf to the root of the tree. The
authentication path consists of the siblings of the vertexes on this
primary path. Given a vertex, its authentication path, and the
hash function, the primary path can then be computed, up to and
including the root of the tree. This computed value of the root
can then be compared with a stored value, to verify the
authenticity of the label of the leaf vertex.