  Recent years have seen the emergence of decentralized wireless networks
consisting of nodes hosted by many individuals and small enterprises,
reawakening the decades-old dream of open networking. These networks have been
deployed in an organic, distributed manner and are driven by new economic
models resting on tokenized incentives. A critical requirement for the
incentives to scale is the ability to prove network performance in a
decentralized trustfree manner, i.e., a Byzantine fault tolerant network
telemetry system. In this paper, we present a Proof of Backhaul (PoB) protocol
which measures the bandwidth of the (broadband) backhaul link of a wireless
access point, termed prover, in a decentralized and trustfree manner. In
particular, our proposed protocol is the first one to satisfy the following two
properties: (1) Trustfree. Bandwidth measurement is secure against Byzantine
attacks by collaborations of challenge servers and the prover. (2) Open. The
barrier-to-entry for being a challenge server is low; there is no requirement
of having a low latency and high throughput path to the measured link. At a
high-level, our protocol aggregates the challenge traffic from multiple
challenge servers and uses cryptographic primitives to ensure that a subset of
challengers or, even challengers and provers, cannot maliciously modify results
in their favor. A formal security model allows us to establish guarantees of
accurate bandwidth measurement as a function of the fraction of malicious
actors. Our evaluation shows that our PoB protocol can verify backhaul
bandwidth of up to 1000 Mbps with less than 8% error using measurements lasting
only 100 ms. The measurement accuracy is not affected in the presence of
corrupted challengers. Importantly, the basic verification protocol lends
itself to a minor modification that can measure available bandwidth even in the
presence of cross-traffic.
