Subspace

A messaging layer for Bitcoin


The Bitcoin protocol has proven itself to be a versatile platform for innovation, yet there are still limits to what we can do with it. As an example, we cannot send arbitrary messages across the network. This is by design ― we want it to send value from person A to person B as efficiently as possible and not be bogged down storing information that is not needed for consensus.

However, the lack of a viable messaging layer means that a number of bitcoin related extensions remain on the shelf. For example, I've had a few conversations with Tim Ruffing, author of the CoinShuffle paper, and despite the enthusiasm for the protocol, it remains largely unimplemented due to a lack of viable communication channel.

In my own projects I have a number of use cases where I need to send data from one client to another ― payment requests, 2FA (multisig) signing requests, direct-to-recipient payments, ECDH transactions, etc ― but I have yet to find a messaging protocol that has all the properties I need to make these work.

Adam Back (inventor of Hashcash and sidechains) had this to say about the issue recently on the development mailing list:

Relatedly I think bitcoin could do with a store-and-forward message
bus with privacy and strong reliability via redundancy (but less
redundancy maybe than consensus all-nodes must receiving and agree and
store forever). That provides an efficient store-and-forward SPV
receivable stealth-address solution that doesnt suck: send the
recipient their payment, if they like it they broadcast it themselves.
As a bonus store-and-forward message mixes are better able to provide
meaningful network privacy than interactive privacy networks.

Remarkably, that was posted on the same day I released a prototype of a messaging protocol designed to do just that ― Subspace.

Subspace, I hope, can be the messaging layer we need to make these things happen. In this article I’ll talk about the properties I’m looking for in a messaging protocol, the design challenges we face and how subspace attempts to overcome them.

Why a new protocol?

That’s a good question! There are plenty messaging protocol to choose from and it would be much easier to use an existing one, preferably one with a high degree of reliability. But once we run through our requirements, the contenders start dropping off rather quickly.

Peer-to-peer

Life would be so much simpler if there were no threats to server based systems. Unfortunately, in today’s world if the wrong person doesn't like what you’re doing, they can shut you down pretty easily. So we need a protocol, not unlike Bitcoin, that resists censorship.

End-to-end encryption

Because of the public nature of the blockchain we are literally broadcasting our wealth to the world and holding up a “come rob me” sign when we use Bitcoin. To reclaim our financial privacy we need tools that allow us to ensure our private data remains private without trusting third parties to keep it safe.

Store-and-forward

In most conceivable applications it’s unlikely that the sender and recipient will be online at the same time. Hence, we need a network to which a sender can upload a message, have it stored for some amount of time, with the recipient retrieving it later. There are very few P2P protocols doing this type of asynchronous messaging as it tends to be difficult to prevent spammers from abusing network.

No metadata

To the extent we want to remain private we likely need to go further than just encrypting the content of our messages ―we should try to hide the non-content data (sender, recipient, etc) as well. Again, the public nature of the blockchain means that network observers could likely link messages to transactions in the blockchain if they know the sender, recipient and timing of a message.

Scalability

There’s a bit of a trend that we see repeated in network design. The network works reasonably well when the number of users is small, but it runs into problems as the number of grows. If this protocol is to grow to handle all bitcoin users and their use cases (which itself is growing) it should be designed to scale well from the start.

Low-latency

Both from a functional and user experience perspective we need the network to be as fast as possible. Bitcoin user’s have grown accustomed to transactions which reach their destinations in under a second. We can’t expect them to adopt anything with built-in 2 or 3 minute delays. Additionally, protocols like CoinShuffle need low-latency communication otherwise transactions will take forever to complete.

So now that we've laid out the requirements we can see that there are almost no messaging protocols left standing. The one that comes the closest is Bitmessage. It’s P2P, end-to-end encrypted, asynchronous, and leaves no metadata trail. Unfortunately, it has some scalability issues (which could possibly be overcome with clever engineering) and it uses proof-of-work as an anti-spam mechanism meaning it doesn’t satisfy our requirement for low-latency communication.

If we are to design a protocol that meets these requirements, we’re going to have to figure out a way to deal with the spam problem without using proof-of-work.

File sharing as a model

A possible solution can be found in the design of most peer-to-peer file sharing networks. File sharing networks, like BitTorrent, have proven their ability to scale to enormous sizes, store and transfer petabytes of data, and remain standing despite large, well-funded interests seeking to shut them down.

So how do they do it? Unlike Bitmessage, say, these networks don’t require all nodes to store files. In fact, that couldn't possibly work given the overall amount of data we’re talking about. Instead nodes only store a mapping of a unique file ID and the IP address(s) of the node(s) storing the file. When you want to download an episode of Family Guy, you query the network for the IP addresses of the nodes storing the file, then make a direct connection to one (or more) of them and ask to download the file.

While this setup reduces the overhead of each node, the total number of mappings can still be quite large. Instead of each node storing the entire set, some networks use an architecture called a distributed hash table (DHT) to distribute the load. Each node in the DHT only stores a tiny subset of the database with the assumption being at any given time there will be multiple nodes storing any given file ID/IP address pair. Your client can use a fairly clever iterative routing technique to find the node storing the IP address you’re interested in.

Messages instead of files

If we consider this network architecture in the context of secure messaging we can see that this model would solve both our problems with scalability and spam.

Instead of ‘seeding’ an episode of Family Guy, you can seed your outgoing messages. We can swap out the ‘file ID’ parameter in the DHT for the public key of the recipient. Now when the recipient queries the network for his messages (using his public key) he is given the IP address of your computer from which he can download the message.

Because we are not forcing other nodes to store our messages, we don’t have to worry about spam and can remove the proof-of-work requirement that slows down our communications.

Lightweight Clients

Above I described how a ‘full node’ in the network would work. However, like Bitcoin, there are some inconveniences to running full node that would make it unsuitable for most users ― namely, you have remain online at all times so recipients can retrieve their messages and putting your own IP address in the DHT makes it tricky (though not impossible) to remain private.

To solve these problems we can outsource the ‘seeding’ of our messages to a third party service provider. Doing so eliminates the need remain online, dramatically simplifies the client-side code, and replaces our IP address in the DHT with that of the service provider.

What we end up with looks very similar to lightweight Bitcoin wallets like Electrum, Mycelium, Blockchain.info, etc. Each of these wallets connect to a service provider (a server) which connects to the larger Bitcoin network. The reason you can send a transaction from Electrum and receive it in Mycelium is because the servers are using the same network protocol. Subspace would work the same way.

Eliminating Metadata

Up to this point we've been tagging messages using the public key of the recipient so he can retrieve it, which enables network observers to collect piles of metadata. The way Bitmessage eliminates the metadata is to have all clients download all messages and attempt to decrypt them. By mixing your messages with others, it becomes impossible to tell who is sending and receiving messages.

Unfortunately, downloading all messages scales very poorly. In Subspace, we use a filtering technique that allows us to mix our messages with a user-defined subset of the total message space, reducing your bandwidth consumption while preserving your privacy.

When you create a subspace address you can define a ‘prefix length’ parameter. If you set your prefix length to zero, people sending you messages will tag the message with a random number (instead of your public key) and you would download and attempt to decrypt all messages (like Bitmessage). If you set your prefix length to one, senders will set the first bit in the message tag to the first bit in your public key and randomly set the remaining bits. This will reduce the number of messages you need to download by 50% while reducing your anonymity set by 50%. Each additional bit of length reduces your bandwidth consumption and anonymity set by another 50%. For example, a prefix length of five would create an anonymity set of about 3.125% of the messages in the network.

We only need to make a small change to the basic DHT architecture to allow querying by prefix.

Moving Forward

One of the primary benefits of the network model I've described above is that it has already gone through a trial by fire. File sharing networks make up between 43% and 70% of all internet traffic despite remaining under constant assault. Using this model we should be able to satisfy all our requirements for a Bitcoin messaging network.

There is already a subspace server running at https://bitcoinauthenticator.org:8335 and you can download a prototype messaging client using the protocol here. If you have a use case for a protocol like this and would like to help out with development, please do contact me at ctpacia@gmail.com