Accurate and Provably Secure Latency Estimation with Treeple

A network latency estimation scheme associates a short “position string” to each peer in a distributed system so that the latency between any two peers can be estimated given only their positions. Proposed applications for these schemes have included efficient overlay construction, compact routing, anonymous route selection, and efficient byzantine agreement. This paper introduces Treeple, a new scheme for latency estimation, that differs from previous schemes in several respects. First, Treeple is provably secure in a strong sense, rather than being designed only to resist known attacks. Second, Treeple “positions” are not based on Euclidean coordinates, but reflect the underlying network topology. Third, Treeple positions are highly stable, allowing peers to retain the same position information for long periods with no maintenance. Finally, Treeple positions can be assigned to peers that do not participate directly in the scheme. We evaluate Treeple on a large internet dataset (with over 200,000 measurements) and find that on average, its latency estimates are within 26% of the true round-trip time. By comparison, Vivaldi, a popular but insecure scheme, has a median relative error of 25% on the same dataset.