Scalability through Prefix Filtering

This page is a proposal or recommendation. Its content is most likely not representing an actual situation.

Introduction

This page describes a proposal for a way to make Bitmessage scalable.

NOTE: This proposal is not yet complete, as some aspects of proposed system are not yet resolved (see https://bitmessage.org/wiki/Scalability_through_Prefix_Filtering#Unresolved_Questions).

Suggestions and contributions are welcome.

Summary of the proposal

Each Bitmessage address has a 'prefix' and a 'prefix length'. These values determine the balance between anonymity and efficiency that the owner of the address will have when retrieving messages from the network.
Each node in the Bitmessage network also has a 'prefix' and a 'prefix length'. These values determine what part and what proportion of the total network traffic the node will handle.
Groups of nodes form overlapping 'streams' based on their prefix values.
As the network grows or shrinks, addresses move to a higher or lower stream in order to maintain the balance between anonymity and efficiency desired by the address's owner.
As the network grows or shrinks, nodes also move to a higher or lower stream in order to handle a greater or smaller proportion of the network object traffic.
Nodes maintain long-lived connections to nodes in their own stream and streams that are 'nearby' in the stream hierarchy, but also temporarily connect directly to nodes in any stream when necessary.
Each Bitmessage object has a prefix nonce. This value determines which streams the object will propagate in.
Nodes process objects in their own stream and all lower streams of the same branch.
Objects propagate in the stream that matches their prefix nonce and all higher streams of the same branch.

Background

There are three basic possible approaches to making Bitmessage scalable (credit to Dokument for this summary):

Nothing (or everyone gets everything)

Everyone user gets every message.
Massive bandwidth and disk space and processing usage, eventually becomes completely unsustainable.
Most private.

Streams

Take the above and split it into pieces.
Still potential for lots of bandwidth/disk space/processing usage.
There are problems with binding addresses to one stream, and there are problems with not binding addresses to streams. Both sets affect privacy.

Scaling without streams

The same as the first method except only some messages are saved (once the network grows beyond a certain point).
Requires two part messages.
Requires a lot of thought and processes to effectively hide receiving a message.

This proposal outlines a method for implementing streams that avoids or reduces many of the difficulties with previous stream proposals. In general the problems shared by most stream systems are simplified. For example, instead the network having to create or abandon streams as the total network traffic level changes, nodes simply adjust their position in a pre-determined hierarchy of streams, moving either 'up' or 'down' the hierarchy.

Proposed changes

Prefixes

The purpose of the prefix filtering system is to provide a mechanism for determining how Bitmessage objects should be routed.

Rather than having one stream to start with and gradually increasing or decreasing the number of streams as the network grows or shrinks, this system makes 18 quintillion possible 'streams' (prefix values) available immediately.

Each node in the network handles a certain proportion of the total network traffic, with the size of that proportion determined according to the node's capability. For example, if a node is capable of processing up to 100,000 objects per day and the total network object traffic is 10,000,000 objects per day then the node would select a prefix length value of 7, which would result in it having to process roughly 78,000 objects per day. Over time, the node can change its stream number in order to keep processing as much object traffic as it can.

When a Bitmessage address is created, the client creating the address selects a prefix length value that will result in a balance between anonymity and efficiency that best suits the end user who owns that address. For example, if the total network object traffic is 10,000,000 objects per day and the the owner of the new address wants a balance between anonymity and efficiency that equates to an anonymity set of roughly 10,000 objects per day then the client will select a prefix length value of 10 for the address. This will result in the client needing to download roughly 9,700 objects per day in order to be sure of receiving all objects destined for it.

Address

The prefix value of each Bitmessage address is the first 64 bits of the ripe hash encoded within the address. The prefix of an address never changes.

The prefix length value of each address is contained within the address's pubkey, as below. The prefix length value of an address determines how many bits of the address's prefix should be used. Increasing the prefix length of an address moves that address to a lower stream. Increasing the prefix length of an address moves it to a higher stream. This can be accomplished by publishing a new pubkey which contains the updated prefix length value.

If non-hashed addresses are added to the Bitmessage protocol, their prefix length value will have to be encoded within the address string itself, as non-hashed addresses do not have pubkeys. This would prevent non-hashed addresses from moving between streams. Users of non-hashed addresses would have create new addresses instead. This would undoubtedly be less convenient, but is consistent with the overall profile of non-hashed addresses - gaining security and anonymity at the expense of convenience and efficiency.

Object

Under this proposal, Bitmessage objects would be composed as follows. This can be compared to the current specification found at https://bitmessage.org/wiki/Protocol_specification#object.

Field Size	Description	Data type	Comments
8	nonce	uint64_t	Random nonce used for the Proof Of Work
8	expiresTime	uint64_t	The "end of life" time of this object (be aware, in version 2 of the protocol this was the generation time). Objects shall be shared with peers until its end-of-life time has been reached. The node should store the inventory vector of that object for some extra period of time to avoid reloading it from another node with a small time delay. The time may be no further than 28 days + 3 hours in the future.
4	objectType	uint32_t	Four values are currently defined: 0-"getpubkey", 1-"pubkey", 2-"msg", 3-"broadcast". All other values are reserved. Nodes should relay objects even if they use an undefined object type.
1+	version	var_int	The object's version. Note that msg objects won't contain a version until Sun, 16 Nov 2014 22:00:00 GMT.
8	prefixNonce	uint64_t	The object's prefix nonce. This determines which streams the object will propagate in.
?	objectPayload	uchar[]	This field varies depending on the object type; see below.

Pubkey

Under this proposal, the encrypted part of a pubkey would be composed as follows. This can be compared to the current specification found at https://bitmessage.org/wiki/Protocol_specification#pubkey.

Field Size	Description	Data type	Comments
4	behavior bitfield	uint32_t	A bitfield of optional behaviors and features that can be expected from the node receiving the message.
1	prefix_length	uint8_t	The number of bits from the address's prefix value that should be used. Must be in the range 0-64.
64	public signing key	uchar[]	The ECC public key used for signing (uncompressed format; normally prepended with \x04 )
64	public encryption key	uchar[]	The ECC public key used for encryption (uncompressed format; normally prepended with \x04 )
1+	nonce_trials_per_byte	var_int	Used to calculate the difficulty target of messages accepted by this node. The higher this value, the more difficult the Proof of Work must be before this individual will accept the message. This number is the average number of nonce trials a node will have to perform to meet the Proof of Work requirement. 1000 is the network minimum so any lower values will be automatically raised to 1000.
1+	extra_bytes	var_int	Used to calculate the difficulty target of messages accepted by this node. The higher this value, the more difficult the Proof of Work must be before this individual will accept the message. This number is added to the data length to make sending small messages more difficult. 1000 is the network minimum so any lower values will be automatically raised to 1000.
1+	sig_length	var_int	Length of the signature
sig_length	signature	uchar[]	The ECDSA signature which covers everything from the object header starting with the time, then appended with the decrypted data down to the extra_bytes. This was changed in protocol v3.

Proposed Stream Structure

The diagram below shows the structure of streams under the proposed system. The small, light blue circles represent groups of nodes. The large coloured circles represent streams. Note that this diagram only shows 4 complete levels (5 levels of nodes and 4 levels of streams). The proposed stream hierarchy would have 64 such levels.

Node Connections

The diagram below illustrates the connections between nodes and clients under the proposed system. Both nodes and clients are labelled with a stream number, which correspond to the stream numbers in the stream structure diagram above. Note that this diagram only shows nodes and clients in the first 4 levels of streams. In practice there would be 64 levels of streams.

How do objects travel through the network / How do nodes connect to each other?

Node addresses are shared very widely (e.g. up to 100 node addresses per stream).

If a node needs to send an object to another stream, it connects to one or more nodes in that stream or a higher stream and sends the object to them.

Nodes maintain many constant connections to nodes in their own stream and nearby streams (both higher and lower).

Nodes of higher capacity should generally maintain more constant connections.

Client Procedures

Creating a Bitmessage address and pubkey

When a new Bitmessage address is generated by a Bitmessage client, the following occurs:

The client makes a request to one or more nodes in the network for information on the current object traffic levels in the network.
The client uses this information to determine a prefix length value that will result in a balance between anonymity and efficiency that matches the requirements of the owner of the address.
The client creates a pubkey object for the address. This includes the prefix length value.
The client takes the first n bits of the address's prefix value, where n is the prefix length value. The resulting value is the address's current stream number.
The client sets the first n bits of pubkey prefix nonce to match the address's stream number.
The client sets the remaining bits of the pubkey prefix nonce randomly.
The client sends the pubkey to nodes in the address's stream or a higher stream of the same branch.
The pubkey propagates through its address's stream and all higher streams of the same branch.

Retrieving an address's pubkey

When a client needs to retrieve the pubkey of an address, it does the following:

The client extracts the address's prefix value from the address string.
The client, or a node acting on behalf of the client, connects to one or more nodes with a stream number that matches any number of bits of the address's prefix value.
The client then creates a getpubkey object with a prefix nonce that exactly matches the address's prefix value and sends it to those nodes.
The client, or a node acting on its behalf, then repeatedly queries nodes in that stream for the pubkey in question until it is retrieved.

Sending a message

When a client sends a message to an address, it does the following:

Sets the first n bits of msg prefix nonce to match the identifying prefix bits from the destination address's prefix.
Sets the remaining bits of the msg prefix nonce randomly.
Sends the msg to one or more nodes with a stream number matching the destination address’s identifying prefix bits or a higher steam.

Retrieving messages from the network

When a client wishes to retrieve objects from the network, it does the following:

For each address owned by the client, the client connects to one or more nodes in the address's stream or a higher stream of the same branch.
The client then requests any objects with a prefix nonce where the first n bits match the destination address's stream number, where n is the prefix length value of the address.
The client then processes these objects.

Broadcasts

Broadcasts are sent to every node in their destination address's stream (like msgs). When a client wants to subscribe to broadcasts from an address, it does the following:

Extracts the address's prefix value from the address.
Retrieves the address's pubkey (see above).
Extracts the prefix length value from the address's pubkey and uses it to calculate the address's current stream number.
Periodically make a request to one or more nodes in the address's stream for any broadcast objects which are tagged as being from the address that the client is subscribed to.

Notes

Upper Stream Desertion

If the object traffic in the Bitmessage network continues to grow, eventually a point will be reached where no single node can process all of it. At this point, any nodes that started in stream 1 (shown as "stream _" in the stream hierarchy diagram) will have to move to stream 2 or 3, or an even lower stream. This will mean that there will be no nodes in stream 1. This process of 'stream desertion' will continue as long as the object traffic continues to grow. However since both nodes and addresses can move to different streams, this should not present a problem for the functioning of the system.

Node prefix length examples

A prefix length value of 0 would mean that the node will deal with 100% of the total network object traffic.
A prefix length value of 4 would mean that the node will deal with 6.25% of the total network object traffic.
A prefix length value of 8 would mean that the node will deal with 0.39% of the total network object traffic.
A prefix length value of 14 would mean that the node will deal with 0.006% of the total network object traffic.
A prefix length value of 64 would mean that the node will only deal with objects with a prefix nonce that exactly matches the node's stream number (which will be the same as its prefix value, since all 64 bits are used).

Sharing of node addresses

Under the proposed system, each node would keep a large list of the addresses of other nodes, listing the IP address and stream number of each one. This list would cover a very large range of different stream numbers. The IP addresses and stream numbers of new nodes would be spread widely through the network, regardless of the stream system.

Nodes would maintain long-lived connections to nodes in their own stream and 'nearby' streams in the tree hierarchy, but when necessary they could temporarily connect directly to nodes in any stream, for example when sending a message to an address in that stream.

Nodes in higher streams would not have any special 'master' role. They would just handle a higher proportion of the object traffic than nodes in lower streams.

Unresolved Questions

Rules for nodes moving between streams

As the overall size of the network changes, nodes will need to adjust the proportion of the network traffic that they handle. This will require moving between streams. How can this be done in a way that does not undermine the security of the network and its users?

The basic idea is that nodes can measure the level of object traffic in their stream. All objects must have POW done for them, so the object traffic is valuable because it is costly to spoof. Nodes would move to lower streams when the level of object traffic in their stream is too great for them to handle and move to higher streams when the level of object traffic is below 50% of what they are capable of processing.

In order to prevent attackers 'pushing' nodes into lower streams by creating short bursts of very high volume object traffic, nodes could implement a time delay mechanism that ensures that they will only move up or down based on the object traffic levels of a relatively long period of time (e.g. 1 week).

Rules for addresses moving between streams

As the overall size of the network changes, addresses will need to move between streams in order to preserve the balance between anonymity and efficiency that their owner has selected. How can this be done in a way that does not undermine the security of the network and its users?

Similarly to nodes, addresses must move to higher or lower streams in order to preserve the balance between anonymity and efficiency that the address's owner desires. Again, it would make sense to use the level of object traffic to decide when to do this. As clients must download all objects in their address's stream(s), they should also be able to use the levels of object traffic to determine when each address needs to move up or down in the stream hierarchy.

Clients that control addresses could also implement a time delay mechanism, similar to the one described above for nodes.