Group 11 Created with Sketch.
noun_63692_ffffff Created with Sketch.

Lot49: Adding Payments to Mesh Networks

By | 11/8/19, 3:54pm EST

goTenna Mesh devices can automatically form mesh networks when multiple devices are within range of one another allowing data like text messages to be sent over longer distances than one device could reach on its own. If a node in the mesh has an Internet connection, they can act as a gateway, allowing other nodes in the mesh to send data through them to the broader Internet.

One problem that can arise in any mesh network is the tragedy of the commons – one user sends a lot of traffic and leaves little bandwidth for everyone else. This can cause other users to leave the mesh if they had only joined altruistically, or to conserve their device’s battery life. As a result, total capacity on the mesh drops and it becomes less useful for all participants.

A potential solution would be to have users pay for the messages they broadcast, and allow others to be rewarded for relaying them through the mesh network. Each node involved in passing along the message earns a fraction of the total payment, and the sender gets a proof that the message was delivered. A recent proposal, Lot49, aims to add this payment layer to mesh networks. Using Bitcoin as a currency, and payment channels based on the eltoo design, mesh users could pay each other offline and collect their balance in Bitcoin when needed through a gateway node connected to the internet.

Lot49

Adding payments to the mesh requires adding additional data to each message. Nodes must set up payment channels, update the payment balance between nodes when messages are sent, and ensure that either party can always claim their Bitcoin without cheating the other party. The main component of this extra data is cryptographic signatures, which allow the sender of the message to pay other nodes that relay their message. There are many signature schemes to choose from, but whatever is chosen must be compatible with the Bitcoin network.

The Lot49 protocol classifies different messages in terms of how they update the channel between nodes; setup messages involve negotiating the terms of the payment channel, such as how much Bitcoin to open the payment channel with. Witness messages are used to set up the channel on the Bitcoin blockchain, and must be passed to a witness node which acts as a gateway to the Internet. Update messages carry the signatures that allow senders to pay receivers, and the payload is the actual data being paid for.

Figure 1: An example of how channels are established. At timestep 0, each node negotiates setting up a new channel with it’s channel partner. At timestep 1, two of the nodes negotiate setting up a new channel with witness nodes that are gateways to the internet. At timestep 2, the nodes send a onchain commitment to establish their channels; Relay Node 1 needs to send its commitment via Relay node 2. At timestep 3, the witness node sends back proofs that the commitments are confirmed.

Lot49 originally used BLS signatures, which allow multiple people to combine signatures using a technique called signature aggregation. However, this signature scheme is unlikely to be added to Bitcoin in the near future. As a result, we decided to make some changes to the Lot49 protocol:

  1. Migrate to the primary signature scheme used in Bitcoin, secp256k1.
  2. Develop new optimizations that would reduce the overhead of larger signatures.

Step 1 – Migrating to secp256k1

The migration to secp256k1 only affects the size of the update messages. Signatures are sent in Lot49 whenever a user needs to pay for a message to be sent. In secp256k1, each signature is 64 bytes; to update a payment channel two signatures must be sent. For each hop in the path of the message, another pair of signatures must be sent. By the time the message reaches its destination, each node can claim the payment for the message (as long as the proof of delivery is returned back to the original sender).

Figure 2: An example of how a message propagates through the mesh using Lot49. At timestep 0, the message and matching signatures are sent to relay node 1. At timestep 1, relay node 1 saves the received signatures and forwards the message to relay node 2 along with new signatures to update their channel. At timestep 2, the process repeats between relay node 2 and the destination node. At timestep 3, the destination node decrypts the delivery receipt and returns it to relay node 2, allowing their payment channel to update. At timesteps 4 and 5, the process repeats between the relay nodes and the sending node; all payment channels are updated and the sender has a proof that the message was delivered.

Using secp256k1 increased the total amount of data used for signatures per message hop from 96 bytes using BLS to 128 bytes. Since each data packet is small, saving space is a priority for making Lot49 more efficient. While this change may not seem like progress towards that goal, it does bring Lot49 much closer to being deployable when using Bitcoin as the currency for payments.

Step 2 – Protocol Optimizations

Both simulations were run with the same parameters – 30 nodes in a square of 9 km^2 moving at 1.4 m/s, with a radio range of 1.6 km. 20% of the nodes were gateways, and message hops were limited to 6. Both simulations were run for 480 time steps. Note that the difference in average bandwidth used for payloads, setup headers, and witness headers between the two signature schemes is due to expected variation between simulation runs. The primary difference is that transmitting Update headers requires approximately 30% more network bandwidth per message due to the use of larger signatures.

After successfully migrating Lot49 to secp256k1, the next step was to try and reduce total overhead back to the levels seen with BLS signatures, and ideally even lower. Some optimizations appear naturally as part of moving away from BLS; for example, each update message also included data on the path a message followed to help in verifying the aggregate signature. This data was also needed to relay the proofs of delivery back on the correct path. With secp256k1, this data can be stored at each node instead of sent with the message, saving a few bytes and keeping update message sizes constant.

Another optimization is focused on reducing the overhead for a set of messages. Currently there is a payment and a receipt associated with each message. If the sender’s data doesn’t fit in one message, they may want to only pay for message relay if all messages in a set are received successfully. By using Merkle trees that include the message hash and decrypted receipts, we can construct proofs that some set of messages from the set were delivered. Payments tied to nodes in this tree would only become valid after multiple messages were received. Senders could also customize how they split the payment over the set of messages, as long as the receiver is also aware of the split the sender chooses. Using this construction would reduce the total amount of payment updates needed by at least half, reducing the total number of signatures transmitted. However, one drawback of this technique is that all relay nodes involved in message transmission take on the risk of potential failures caused by the other relay nodes.

Figure 3: An example Merkle tree for aggregating 4 proofs of delivery. Message hashes and delivery receipts form the leaves of the tree. Currently channel updates are tied directly to delivery receipts (red boxes). Using the nodes in the second level of the tree (green nodes) would require 2 channel updates instead of 4. Using the root of the Merkle tree (blue node) would require only 1 payment update.

We are also considering signature schemes that would allow us to partially aggregate the two signatures sent for each payment update. This could give us update messages with signatures comparable in size to BLS but which are also fully compatible with the Bitcoin blockchain. 

Conclusion

Looking forward, the Bitcoin community has provided valuable feedback on Lot49 and other possible optimizations.  Other projects have demonstrated using ham radio for transmitting Bitcoin transactions across oceans and continents. As the fragility of the Internet becomes more apparent, the development of alternative networks is encouraging in providing not just a backup but also its own utility for communication in unique situations. Note that Lot49 is hardware agnostic; ham radio operators could bridge meshes operating in cities and provide long-distance links that smaller and more portable devices like the goTenna Mesh aren’t capable of. I’m excited to see how these alternative networks develop, and Lot49 shows significant potential in solving the problem of growing and maintaining these networks.

Links

The updated Lot49 simulation is available at https://github.com/jharveyb/lot49/tree/musig.

readme.md (not README.md) contains instructions on how to build the simulation on your own machine.

If you have questions about the project or issues using it, feel free to leave an issue in the GitHub repository, or contact me at jonathan@gotenna.com

Jonathan Harvey-Buschel

Jonathan Harvey-Buschel was a protocol developer contracted to Global Mesh Labs to further develop the Lot49 protocol. Jonathan studied Computer Science at MIT and is interested in how mesh networking and Bitcoin can be combined to enable new resilient and decentralized networks.

Comments