Peer-to-peer anonymous networks offer the resources to support today’s Internet applications. In today’s dynamic networks, the key challenge to these systems arises from node dynamics and failures that disrupt anonymous routing paths, forcing them to be frequently rebuilt. Not only do these path rebuilds interrupt application sessions, but they also leak information to logging attacks such as the predecessor attack, leading to significant degradation of anonymity over long sessions. In this paper, we propose Bluemoon, a new anonymous protocol that provides strong resilience against the predecessor attack through the use of reliable anonymous links built from persistent routing entries. When chained together, these links create robust anonymous paths that avoid path disruptions and rebuilds across node failures. Through detailed analysis, we show that relative to prior approaches, Bluemoon provides up to eight orders of magnitude stronger resistance against predecessor attacks. Finally, we implement and deploy a prototype on both local and Internet-scale network testbeds, and show that it provides high throughput even in high-load environments such as PlanetLab