Difference between revisions of "Scalability through Prefix Filtering"

From Bitmessage Wiki
Jump to navigation Jump to search
(Added some more content)
(Added some more content)
Line 71: Line 71:
<b>Proposed Stream Structure</b>
===Proposed Stream Structure===
Line 77: Line 77:
<b>Node Connections</b>
===Node Connections===

Revision as of 15:13, 2 February 2015


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. 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 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, nodes move to a higher or lower stream in order to handle a greater or smaller proportion of the network object traffic.
  • 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.
  • Nodes maintain long-lived connections to nodes in their own stream and 'nearby' 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 the object's destination stream.
  • Objects propagate in their destination stream and lower streams of the same branch.
  • Nodes process objects in their own stream and lower streams of the same branch.

Reasoning behind the proposal

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.

Proposed changes


Under this proposal, a msg object 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.
4 prefixNonce uint32_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.


Proposed Stream Structure

Prefix Filter Streams Hierarchy.png


Node Connections

Node Connections Diagram.png


Example 1


Example 2


Example 3









Idea: POW variable by prefix specificity


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 should this be done?

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 should this be done?