Proof of Backhaul: Trustfree Measurement of Broadband Bandwidth

Proof of Backhaul: Trustfree Measurement of Broadband Bandwidth

Speakers: Peiyao Sheng

Conference: NDSS Symposium

YouTube: https://www.youtube.com/watch?v=90eGCeQIakc

Overview

The talk "Proof of Backhaul: Trustfree Measurement of Broadband Bandwidth" by Peiyao Sheng introduces a groundbreaking protocol designed to securely and transparently measure the broadband backhaul link capacity of wireless access points in decentralized wireless networks. This innovation is critical for the burgeoning ecosystem of open networking initiatives, where individual participants and small enterprises host network nodes and require performance-based incentives for their contributions. The core challenge addressed is the need for a Byzantine fault-tolerant network telemetry system that can verify network performance without relying on a centralized, trusted authority.

The proposed protocol, dubbed Proof of Backhaul (PoB), offers a novel approach to bandwidth measurement that satisfies two crucial properties: Trustfree and Open. It ensures that bandwidth measurements are secure against sophisticated Byzantine attacks, even when challenge servers collude with the prover (the access point being measured). Furthermore, PoB significantly lowers the barrier to entry for challenge servers, eliminating the need for them to possess high-throughput or low-latency connections to the measured link. By aggregating challenge traffic from multiple distributed servers and employing robust cryptographic primitives, PoB guarantees the integrity of measurement results, making it an indispensable tool for the economic models underpinning decentralized network growth.

Background

▶ Watch: Introduction to Proof of Backhaul and problem (0:00)

The recent surge in decentralized network architectures, including Software Defined Networking (SDN), open software initiatives, and decentralized Internet Service Providers like Althea and Mobile Network Operators (MNOs) such as Helium, has underscored a fundamental requirement: secure and decentralized network telemetry. Unlike traditional centralized networks where telemetry primarily serves optimization purposes, in decentralized settings, it is paramount for incentive compatibility. This means ensuring that node operators are accurately and fairly compensated for the network services they provide, necessitating a trustfree and open measurement system.

Existing bandwidth estimation techniques, such as Speedtest and Fast, while state-of-the-art for consumer use, are fundamentally centralized. They rely on powerful servers to transmit large data volumes over extended durations, demanding that these servers maintain high-bandwidth, low-latency, and low-packet-loss links. This creates a significant barrier to entry for potential challengers and renders these methods unsuitable for trustfree environments, as measurements can be easily manipulated by an untrustworthy prover or a compromised central challenger. Even approaches that utilize traffic aggregation from multiple challengers, while potentially improving accuracy, still lack trustfree guarantees against a malicious prover.

Interactive measurement tools, like Traceroute and Pathchar, attempt to estimate link performance using timing information derived from ICMP packets. While capable of measuring capacity for any link within an end-to-end path, they are vulnerable to collusion between the prover and challengers. Moreover, the talk highlights empirical evidence demonstrating that the precise timing measurements (tens of microseconds) required for high bandwidths (500 Mbps and above) are difficult to achieve reliably over the internet due to inherent jitter, leading to measurement errors exceeding 20% for such capacities. Other proof systems in decentralized networks, such as Helium's Proof-of-Coverage for tokenized incentives, Althea's route meters, Route Bazaar's forwarding proofs, and Torpath's proposed system for remunerating relays based on data volume, address different aspects of network telemetry. PoB, however, uniquely focuses on measuring the backhaul bandwidth of end nodes without imposing high bandwidth requirements on the measuring nodes themselves, filling a critical gap in the decentralized networking landscape.

Key Findings

▶ Watch: Evaluation results: 1000 Mbps, less than 10% error (2:00)

The research behind Proof of Backhaul (PoB) delivers several pivotal findings and contributions essential for the advancement of decentralized wireless networks:

• First Trustfree and Open Protocol: PoB is presented as the first multichallenger protocol capable of enabling trustfree and open backhaul bandwidth measurement. This is a foundational step for decentralized networks where incentives are tied to performance and traditional trusted third parties are absent.
• High Accuracy and Efficiency: The protocol demonstrates remarkable accuracy, achieving, for instance, less than 10% error for backhaul bandwidths up to 1000 Mbps. Crucially, these measurements are obtained with short challenge durations, specifically 100 milliseconds, and involve reasonable data usage, making the system practical for real-world deployment.
• Robustness Against Byzantine Attacks: PoB is engineered to be robust against various sophisticated Byzantine attacks, including withholding attacks (where corrupted challengers delay or suppress packets) and rushing attacks (where corrupted challengers collude with the prover to inflate measured bandwidth). This resilience applies to malicious actions by both challengers and the prover itself.
• Leveraging Cryptographic Primitives and Robust Statistics: The security and accuracy of PoB are underpinned by a combination of traffic aggregation from multiple sources, digital signatures for unforgeable probes, Merkle trees for efficient proof of data receipt, and the use of median Round-Trip Time (RTT) measurements to mitigate individual misreports and network jitter.
• Practical Viability with Blockchain Integration: A full-stack implementation of PoB has been developed and successfully integrated with the Ethereum blockchain. This demonstrates the protocol's practical utility and its composability with existing decentralized ledger technologies, validating its real-world applicability through a live system with active global challengers.
• Adaptability for Available Bandwidth: The basic PoB protocol can be extended with minor modifications to measure available bandwidth, even in the presence of cross-traffic, further enhancing its versatility for dynamic network conditions.

Technical Deep Dive

▶ Watch: Limitations of existing bandwidth measurement techniques (3:00)

The Proof of Backhaul (PoB) protocol is a sophisticated system designed to measure a prover's backhaul bandwidth in a decentralized, trustfree manner. It operates within a system comprising n participants acting as challengers, where up to f = βn of them can be corrupted. The prover (P) is the node whose backhaul bandwidth (θp) is to be measured, and a trusted verifier, typically a blockchain, triggers the protocol and processes the measurement reports. The output of the protocol is an estimation θ of the prover's backhaul bandwidth.

PoB guarantees two critical security properties:

1. Approximate Completeness: If the prover is uncorrupted, the protocol output θ will be a significant fraction (α) of the true backhaul bandwidth θp, where α is a constant between 0 and 1.
2. Soundness: The protocol will never output a bandwidth θ higher than the actual θp, even if the prover is corrupted and attempts to inflate the measurement.

The core ideas underpinning the PoB protocol are:

• Traffic Aggregation: Multiple challengers simultaneously send challenge traffic to the prover. The challenge duration is carefully chosen to be long enough to ensure that traffic from all challengers queues at the prover's backhaul link, making it the bottleneck.
• Unforgeable Probe: Challengers are randomly selected from a larger pool. Each challenger sends digitally signed packets as traffic, preventing any party, including a colluding prover, from forging measurement probes. Traffic volume from each challenger is also limited to curtail individual influence.
• Short Witness: The prover must send a concise message to challengers to prove receipt of data. This is achieved efficiently using a partially verifiable hash, specifically a Merkle tree, which allows challengers to verify specific data without receiving all of it.
• Robust Timing Measurement: The overall Round-Trip Time (RTT) is estimated by taking the median of RTTs reported by various challengers. This statistical approach helps mitigate the impact of individual misreports and network jitter.

Formally, the protocol is built upon two conditions:

1. Aggregation Condition (Eq. 1): t0 + b/θ0 = ti1 + b/θi. This condition coordinates packet arrival times from different challengers, ensuring multiple traffic flows merge into a single stream at an appropriate rate at the prover's backhaul.
2. Bandwidth Condition (Eq. 2): (n-f)θ0 = θp. This ensures that the prover's backhaul link becomes the effective bottleneck for the aggregated traffic.

PoB extensively leverages cryptographic primitives such as collision-resistant cryptographic hash functions (specifically SHA256), Merkle trees for efficient verification of data integrity and receipt, and digital signatures (using Ed25519 via OpenSSL) for ensuring unforgeable probes and traceability of challenger actions. A blockchain serves as the trusted verifier, responsible for broadcasting protocol parameters, coordinating reports from challengers, and resolving any disputes that may arise.

The full PoB protocol operates in two main phases: Measurement and Verification.

The Measurement Phase (Algorithm 1):

1. The verifier (blockchain) initiates the protocol by broadcasting public parameters: t0 (start time), m0 (a random message), and θ0 (a global minimum bandwidth threshold).
2. Each challenger C_i first measures its own bandwidth θ_i and generates a public-private key pair (pk_i, sk_i), sending pk_i to the verifier.
3. For each sequence number q from 1 to k, challenger C_i sends a packet m_iq to the prover P at a specific time t_iq. This m_iq packet contains (i, q, σ_iq), where σ_iq is the digital signature of (q, m0) using sk_i. The t_iq is precisely calculated to ensure that packets from different challengers arrive at the prover's backhaul around the same time, facilitating the crucial traffic aggregation.
4. The prover P receives these packets. It separates the messages by challenger and stores (q, σ) in a local structure M_i for each challenger j.
5. Once the prover has received a total of (n-f)k packets (accounting for potential withholding by corrupted challengers), it generates a response. This response includes h_1j = Hash(M_j) for each challenger j, and h_2 = MerkleRoot(h_1j) for all challengers. The prover then signs (h_1j, h_2) as σ_j and broadcasts (h_1j, h_2, σ_j) to all challengers C_j.
6. Upon receiving this response, each challenger C_i verifies the prover's signature and records its round-trip time Δ_i = curTime_i - t_i1. This concludes the measurement phase.

The Verification Phase (Algorithm 2):

1. The prover constructs further proofs for the verifier. It sends (B_i, P_i) to each challenger C_i, where B_i is a bitmap indicating the packets received from C_i, and P_i is a Merkle proof for h_1i. The prover also outputs (REPORT, h_2) directly to the verifier.
2. Each challenger C_i receives (B_i, P_i) from the prover. It reconstructs h_1i from B_i and verifies it against the h_1i received earlier. It also reconstructs the Merkle root using P_i and h_1i and verifies it against h_2. If all checks pass, C_i outputs (REPORT, P, h_2, Δ_i, k_i) to the verifier, where k_i is the number of packets C_i sent.
3. The verifier collects these reports. It waits for at least n-f valid reports. It then calculates the median of the reported RTTs, Δ' = Median(M), and computes the final bandwidth θ = (cnt b (n-2f)) / (Δ' * (n-f)), where cnt is the total number of packets reported as received. This θ is the final estimated backhaul bandwidth.

Threat Model and Security Analysis

The formal security analysis of PoB operates under a static adversary threat model. This adversary can corrupt up to f challengers, where f is less than or equal to n/3, before the protocol begins. The prover itself can also be corrupted. The adversary is assumed to have access to external high-bandwidth communication channels. Several prominent attacks are considered:

• Withholding Attack: Corrupted challengers intentionally delay or withhold packets to deflate the measured bandwidth.
• Rushing Attack: Corrupted challengers collude with the prover to send packets through extra high-bandwidth links, thereby inflating the measured bandwidth.
• Information Sharing Attack: Corrupted challengers share their secret keys with the prover, allowing the prover to forge packets and manipulate measurements.
• DoS and Related Attacks: Challengers send invalid or duplicate packets, or attempt to flood the prover's backhaul to disrupt the measurement.

Under this threat model, PoB proves two fundamental theorems:

• Theorem 1 (Soundness): When f ≤ n/3, a corrupted prover cannot inflate the measured bandwidth. This guarantee stems from the unforgeable nature of packets sent by uncorrupted challengers and the robustness of the median RTT measurement against individual misreports.
• Theorem 2 (Approximate Completeness): When f ≤ n/3 and the prover is uncorrupted, the protocol will always output a bandwidth with an accuracy ratio α = (n-2f)/(n-f). This ensures that an honest prover can reliably establish a significant fraction of its true backhaul bandwidth.

It's noted that the f ≤ n/3 adversarial threshold applies to a "lazy" verifier. If the verifier has access to a timer with sufficient accuracy (e.g., 100ms), it can tolerate up to f ≤ n/2 Byzantine challengers.

Implementation Details and Practical Considerations

The PoB challengers and prover were implemented as UDP socket applications in C++. For digital signatures, an OpenSSL-based implementation of Ed25519 was chosen due to its low computational overhead. To address potential WiFi MAC aggregation issues with small packets, multiple signatures are bundled into larger 1514-byte UDP packets, with each carrying 23 distinct 64-byte signatures. SHA256 is used for hashing, and a C++ open-source library handles Merkle tree generation. To mitigate computational overhead during the challenge, challengers precompute all signatures after receiving the challenge request and while measuring initial ping latency.

Several practical factors, not fully captured in the theoretical model, were addressed:

• Challenger Bandwidth: Instead of precisely measuring θ_i, challengers ensure they have at least θ0 = θp/(n-f) bandwidth and send traffic at this rate.
• Latency: One-way latency l_i varies. The RTT calculation is modified to Δ_i = curTime_i - t_i1 - 2*l_i, where l_i is estimated as RTT/2 from 20 ICMP pings. A potential vulnerability if the prover delays ping responses is mitigated by geographically limiting challengers.
• Packet Drops: Simultaneous packet sending can cause buffer overflows. This is compensated by having challengers send 10% more data (1.1k packets) to ensure protocol termination.
• Time Synchronization: NTP is used, but residual errors of tens of milliseconds are acknowledged and accounted for.
• Computation Overhead: The delay introduced by hash and Merkle tree generation is factored into the evaluation.

Demo / Proof of Concept

▶ Watch: Core technical ideas: Aggregation, Unforgeable Probe, Witness (6:00)

The practical viability of the Proof of Backhaul protocol has been robustly demonstrated through a full-stack PoB system integrated with the Ethereum blockchain. This live implementation showcases the complete workflow and real-world performance of the protocol.

In this demonstration setup, a payer initiates a PoB challenge by depositing escrow tokens onto the Ethereum blockchain. A challenge coordinator then selects a diverse set of challengers, who proceed to execute the bandwidth measurement protocol as described. The results of these measurements are subsequently uploaded to the blockchain, and upon successful verification, the participating challengers are rewarded with tokens from the escrow.

The system is currently live and actively deployed, boasting approximately 25-30 active challengers globally. Real-world measurements conducted with this full-stack system provide compelling evidence of PoB's effectiveness. For a 500 Mbps backhaul, the system shows an average error of 4.2%. For 700 Mbps, the average error is 4.1%, and for 1000 Mbps, it is 9.9%. These real-world figures consistently align with the results obtained in controlled testbed environments, affirming the protocol's accuracy and robustness in a practical, decentralized setting.

Defensive Implications

▶ Watch: System design: Measurement and Verification phases (8:00)

The Proof of Backhaul protocol offers significant defensive implications for the integrity and operation of decentralized wireless networks. For decentralized network operators and platform providers (e.g., those managing Helium or Althea-like networks), PoB provides a foundational, trustfree mechanism for validating the quality of service offered by individual nodes. This is crucial for enabling performance-based incentives, ensuring that rewards (e.g., cryptocurrency tokens) are distributed fairly based on verifiable network contributions, thereby preventing fraud and ensuring the economic stability of the network.

For individual node operators or "provers" who host access points, PoB serves as a verifiable and indisputable method to prove their backhaul bandwidth. This empowers them to demonstrate their service quality transparently, ensuring they receive fair compensation and protecting them from accusations of underperformance or malicious activity. It helps to build trust within the network by providing an objective measure of a node's capabilities.

Furthermore, PoB actively helps to prevent Sybil attacks and other forms of manipulation where malicious actors might attempt to game reward systems by falsely claiming high bandwidth or service availability. By requiring cryptographic proofs and aggregating measurements from multiple, geographically diverse challengers, the protocol makes it significantly harder for a single entity or a colluding group to falsify performance metrics. This enhances the overall security and reliability of the decentralized infrastructure.

The transparency and auditability inherent in PoB's blockchain integration mean that network performance data is not only reliable but also publicly verifiable. This can inform critical resource allocation and routing decisions within decentralized networks, allowing the network to intelligently utilize nodes with proven high bandwidth and avoid those that are underperforming or malicious. In essence, PoB provides the cryptographic bedrock for ensuring accountability and integrity in the rapidly evolving landscape of open and decentralized networking.

Key Takeaways

• Trustfree and Open Measurement: Proof of Backhaul (PoB) is the first multichallenger protocol enabling trustfree and open measurement of broadband backhaul bandwidth in decentralized wireless networks, critical for performance-based incentives.
• Robust Security Guarantees: The protocol is demonstrably robust against Byzantine attacks, including withholding and rushing attacks by both challengers and the prover, with formal soundness (no inflation) and approximate completeness (accurate measurement for honest provers) guarantees.
• Innovative Technical Approach: PoB achieves its security and accuracy through a clever combination of traffic aggregation from multiple sources, cryptographic primitives like digital signatures (Ed25519) and Merkle trees (SHA256), and robust statistical methods like median RTT calculation.
• High Performance and Efficiency: The system delivers high accuracy (e.g., less than 10% error for 1000 Mbps) with short measurement durations (100ms) and reasonable data consumption, making it practical for real-world deployment.
• Blockchain Integration and Practical Viability: A full-stack implementation integrated with the Ethereum blockchain demonstrates PoB's practical utility, with a live system successfully operating with dozens of global challengers and consistent real-world performance.
• Foundational for Decentralized Networks: PoB addresses a central problem for decentralized network growth by providing a verifiable, auditable source of truth for network performance, essential for fair compensation, resource allocation, and preventing malicious manipulation.

About the Speaker(s)

Based on the provided metadata and transcript, the talk "Proof of Backhaul: Trustfree Measurement of Broadband Bandwidth" was presented by Peiyao Sheng. No further biographical details, such as title or company affiliation, were included in the provided input.