Structured peer-to-peer (P2P) overlays rely on consis- tent and robust key-based routing to support large-scale network applications such as multicast and global-scale storage. We identify the main attack in these networks as a form of P2Pidentity theft, where a malicious node in the path of a message claims it is the desired destination node. Attackers can hijack route and lookup requests to forge and destroy data to disrupt applications. We propose a solu- tion where nodes sign proof-of-life certificates for partial nodeidsanddistribute themto randomlychosenproofman- agers in the network. Source nodes can evade attackers by requesting proofs from multiple proof managers. Analysis and simulation show the approach is effective and imposes storage and communication costs that grow logarithmically with network size.