From medical support to education and remote work, our everyday lives increasingly depend on Internet performance. When users experience poor performance, however, the decentralization of the Internet allows limited visibility into which network is responsible. As a result, users are promised Service Level Agreements (SLAs) they cannot verify, regulators make rules they cannot enforce, and networks with competitive performance cannot reliably showcase it to attract new customers. To change this, researchers have proposed transparency protocols, which rely on networks reporting on their own performance. However, these proposals would be hard to adopt because i) they require substantial network resources for extracting and publishing the performance information, or ii) they require cooperative networks that honestly report their performance against their self-interests, or iii) they threaten the anonymizing capability of Tor-like networks by violating their limited visibility assumptions and introducing a new attack vector against them.

This dissertation enables network users to estimate the loss and delay of individual networks in an efficient and accurate manner, despite networks generating and controlling the performance data and potentially wanting to exaggerate their performance. It also proposes the first transparency protocol that tries to preserve the capabilities of anonymity networks.

The key to efficient and accurate performance monitoring is i) creating incentives for networks to be honest by causing dishonest networks to get into conflict with their neighbors, and ii) combining these incentives with mathematical tools that "tie together" different aspects of network performance.

The key to anonymity-preserving monitoring is the insight that users can benefit from transparency even when networks expose coarser-than-per-packet performance information, which at the same time hides sensitive communication patterns and improves anonymity.

Our thesis is that efficient and accurate Internet performance transparency is possible and that we can ease the tussle between transparency and user anonymity.