Bob Poekert's Web-Log

Dec 12, 2018

Making Markets for Mesh Data

Introduction

There are a lot of places, even in developed countries like the United States, that don't have affordable broadband internet access. 35% of Americans don't have broadband at home, according to Pew.

Mesh technology can solve this problem by eliminating the requirement for big infrastructure providers to invest in an area before it can have affordable broadband. Mesh networks don't require any infrastructure to be built, and instead use connections between individual households to route traffic for others in addition to delivering data to the people in that household.

Added latency from mesh routing makes them only appropriate for last-mile connectivity. This means mesh networks need to be connected at at least one point to a traditional ISP. The main obstacle to adoption for existing systems like Freifunk is, in my opinion, the lack of any incentive for people to make these connections. Friefunk might be free but it is very slow for this reason.

The obvious thing to do, then, is to build a system to provide such an incentive. Here I propose a spot auction and payments system for people with connections to the wider internet to sell that bandwidth to other people within their local mesh network.

Such a system needs to allow:

  1. individual households within a community to connect to each other (mesh)
  2. people with internet bandwidth to advertise it for sale and for buyers to bid on it
  3. people who won bandwidth auctions to pay for the bandwidth they won
  4. the traffic that's routed through the mesh to look like normal internet traffic to websites, even if it exits the mesh at multiple points

1. Mesh connectivity

Gluon seems to have this part basically figured out. It uses BATMAN-adv for mesh routing and is based on OpenWRT which makes it easy to install on home routers. There are some moderately large (1000 nodes) Freifunk deployments using it.

2. Bidding

As bandwidth consumers users set a maximum per-gigabyte price and a monthly budget for bandwidth. If the user has another source of internet bandwidth (say, an LTE or satellite connection), that maximum price would probably be the price that other source charges.

As bandwidth providers users specify the amount of bandwidth they have for sale (eg: the monthly cap they have with their ISP) and the minimum price they're willing to accept per gigabyte to sell that bandwidth (eg: the per-GB cost their ISP charges plus some margin). The router also does a speed test to determine the amount of bandwidth available per second.

To make both sides of this market work, the users' routers act as brokers, automatically bidding and accepting bids on the users' behalf in accordance with these constraints.

The commodity being bought and sold in this auction is a unit of bandwidth (say, 1 Megabyte) to be used within a specified time after the auction is won (say, one minute). From here on we'll call one of these commodities a bandwidth block.

Bidding works as follows:

  1. A bandwidth provider announces to all the other nodes in the mesh that they have a bandwidth block to sell
  2. Bandwidth consumers send bids to the bandwidth provider specifying how much they're willing to pay
  3. After a specified time interval (say, one second), if there are any bids that clear the provider's reserve price the bandwidth provider accepts the highest bid.
  4. Accepting the bid involves announcing to all the other nodes in the mesh who won the auction and what the price was, and waiting for an acknowledgement from the winner that they won. The other nodes in the mesh can use this information to inform prices they set for bids in the future.
  5. The winning bidder sends payment to the provider

3. Payment and settlement

Once a buyer has won an auction the buyer must pay the seller the agreed price. This requires some sort of payments system. Blockchain systems have unacceptably high latencies for rapid payments like this (in addition to their many other well-known problems). If you're selling bandwidth to be used within the next minute you can't wait more than a minute for the payment to clear (or anywhere close to a minute).

We need a central payments clearinghouse in order to make transfers of money happen within the traditional financial system.

Having to send a request to the central clearinghouse after every auction might be viable but it would be difficult to keep the latency of getting a transfer to clear low enough. Then we're in the awkward position of either having payment processing be a bandwidth bottleneck or inviting fraud by not waiting for payments to clear before providing bandwidth.

Bandwidth consumers can easily avoid fraud by not buying any more bandwidth from nodes that don't supply the bandwidth they sold. The price of a bandwidth block is low enough that being out one block isn't an issue. But bandwidth providers may end up providing a large number of blocks to a consumer before they realize they can't pay.

Instead I propose a system based on what I'm calling coupons. A coupon is a signed message from the clearinghouse that says, effectively, "The clearinghouse will pay to the bearer of this coupon on demand the amount of $X if delivered by Y date". Coupons have one important feature, which is they can only change hands once after they've been issued by the clearinghouse. Party A receives a coupon from the clearinghouse, party A transfers it to party B, and party B takes it back to the clearinghouse to cash it in. Only allowing the coupons to change hands once means we can detect double-spending without keeping any kind of ledger, and in the majority of cases without having to send anything over network in each transaction.

The way we enforce that coupons only get spent once is:

  • Coupons are never valid for more than, say, one month
  • Each coupon has:
    • a unique identifier
    • a face value
    • an expiration time
  • Each node keeps a list of all the coupon unique ids they've seen in the last month
  • Each node keeps a bloom filter of that id list
  • Each node periodically broadcasts their bloom filter to all other nodes in the mesh, along with the expiration time of the youngest coupon in the list
  • Each node keeps all off the bloom filters that contain coupons that haven't expired
  • If a coupon isn't in any of the node's bloom filters, it hasn't been spent
  • If a coupon is in one of the bloom filters, ask the node whose bloom filter that is to check their full list in case it was a collision
  • If that node says it was not a collision, reject the coupon

Using these coupons we can process payments with very low latency while still preventing double-spending.

From a user's perspective this is just buying and receiving credit similarly to how people buy cellphone minutes.

4. Routing and VPN

For this I propose using a version of the OpenVPN protocol extended with an additional packet type that lets the client move the session to a new client IP address when it switches providers. The clearinghouse runs this VPN gateway and pays for it with the transaction fees it charges for issuing coupons.