Newer
Older
## 1 Introduction
Bramble Synchronisation Protocol (BSP) is an application layer data synchronisation protocol suitable for delay-tolerant networks.
### 1.1 System Model
BSP synchronises data among dynamic sets of **devices**. Each device has a dynamic set of **peers** with which it communicates.
Data is organised into **groups**. Each group is an independent synchronisation scope containing a **message graph** made up of immutable **messages**.
If a device takes part in synchronising a group's messages, we say the device is a **member** of the group. If two peers synchronise a group's messages with each other, we say they **share** the group with each other. Group membership and sharing are dynamic. Devices that are members of a group are not necessarily each other's peers, and peers that are members of a group do not necessarily share it with each other.
Each member of a group stores a copy of the message graph, which may be incomplete. Each message in the member's copy of the graph may be **shared** or **deleted**. If a message is shared, the device will synchronise the message to any peers with which it shares the group. If a message is deleted, the device will delete its copy of the message but retain some information about the message's position in the graph.
Each group belongs to a **client**, which is an application component that uses BSP to synchronise data. The client is responsible for deciding which peers the group should be shared with, what constitutes a valid message, which messages should be shared, and which messages should be deleted. BSP carries out these decisions on behalf of the client.
BSP requires a **transport layer security protocol** that can deliver data from one device to another on a best-effort basis, meaning that data may be delayed, lost, reordered or duplicated. The transport layer security protocol is responsible for ensuring the confidentiality, integrity, authenticity and forward secrecy of the data it carries.
* || denotes concatenation
* Double quotes denote an ASCII string
* len(x) denotes the length of x in bytes
* int\_n(x) denotes x represented as an unsigned, big-endian, n-bit integer
### 1.4 Cryptographic Primitives
BSP uses a **cryptographic hash function**, H(m).
We use H(m) to define a multi-argument hash function:
- HASH(x\_1, ..., x\_n) = H(int\_32(len(x\_1)) || x\_1 || ... || int\_32(len(x\_n)) || x\_n)
All hashes are HASH\_LEN bytes.
(*Note:* The current version of the protocol uses BLAKE2b as the hash function, with an output length of 32 bytes, giving HASH\_LEN = 32.)
## 2 Data Formats
### 2.1 Client Identifiers
Each client is identified by a namespaced string. The namespace is based on domain names and is intended to prevent accidental collisions between clients created by different developers. For example, all clients developed by the Briar project have identifiers starting with `org.briarproject`.
### 2.2 Client Versioning
BSP uses a major/minor numbering scheme to distinguish between versions of each client.
The client identifier and major version are included when calculating group identifiers, so different major versions of a given client use distinct groups, whereas different minor versions use the same groups.
The major version is used to indicate backward-incompatible changes. A client may send a message that another client with the same identifier but a different major version would not be able to handle. The use of distinct groups for each major version makes this safe.
The minor version is used to indicate backward-compatible changes. A client may not send a message that another client with the same identifier and major version but a different minor version would not be able to handle.
Each group has a unique identifier HASH\_LEN bytes long. The identifier is calculated by hashing the client identifier and major version with a byte string called the **group descriptor**:
- group\_id = HASH("org.briarproject.bramble/GROUP\_ID", int\_8(group\_format\_version), client\_id, int\_32(client\_major\_version), group\_descriptor)
The group format version is 1 for the current version of BSP.
The group descriptor is supplied by the client. BSP treats it as an opaque byte string without interpreting its contents. The maximum length of a group descriptor is 16 KiB.
A message consists of a byte string called the **message body** and a timestamp indicating the time at which the message was created, represented in milliseconds since the Unix epoch.
The message body is supplied by the client. BSP treats it as an opaque byte string without interpreting its contents. The maximum length of a message body is 32 KiB.
Each message has a unique identifier HASH\_LEN bytes long. The identifier is calculated by hashing the group identifier, timestamp and message body:
- body\_hash = HASH("org.briarproject.bramble/MESSAGE\_BLOCK", int\_8(message\_format\_version), message\_body)
- message\_id = HASH("org.briarproject.bramble/MESSAGE\_ID", int\_8(message\_format\_version), group\_id, int\_64(timestamp), body\_hash)
The message format version is 1 for the current version of BSP.
Peers synchronise data by exchanging **records** via the transport layer security protocol. Each record has the following format:
- record\_header = int\_8(protocol\_version) || int\_8(record\_type) || int\_16(len(payload))
The maximum length of the payload is 48 KiB.
The current version of the protocol is 0, which has five record types:
**0: ACK** - The record's payload consists of one or more message identifiers. This record informs the recipient that the sender has seen the listed messages.
**1: MESSAGE** - The record's payload consists of a message (group identifier, timestamp and message body).
**2: OFFER** - The record's payload consists of one or more message identifiers. This record informs the recipient that the sender has seen the listed messages, is sharing them with the recipient, and does not know whether the recipient has seen them.
**3: REQUEST** - The record's payload consists of one or more message identifiers. This record asks the recipient to send the listed messages to the sender.
**4: VERSIONS** - The record's payload consists of up to ten 8-bit integers, each identifying a version of BSP supported by the sender. This record will be used for version negotiation by future versions of BSP.
A device should reject any record with an unsupported protocol version and ignore any record with a supported protocol version but an unrecognised record type. This allows new record types to be added without breaking compatibility.
## 4 Synchronisation
### 4.1 Synchronisation State
A device stores the following synchronisation state for each message it is sharing with a peer:
- **Seen flag** - Raised if the peer is known to have seen the message, otherwise lowered (column `seen` in `statuses` table, Bramble database)
- **Ack flag** - Raised if the peer has offered or sent the message since the device last acknowledged it, otherwise lowered (column `ack`)
- **Request flag** - Raised if the peer has requested the message since the device last offered or sent it, otherwise lowered (`requested`)
- **Send count** - The number of times the message has been offered or sent to the peer (`txCount`)
- **Send time** - The time at which the message can next be offered or sent to the peer, or zero if the message has never been offered or sent to the peer (`expiry`)
- **Expected arrival time** - The time at which the offer or message is expected to arrive at the peer, or zero if the message has never been offered or sent to the peer (`eta`)
The device may also store a list of message identifiers that have been offered by the peer and not yet requested by the device. This list allows requests to be sent asynchronously. The length of the list may be bounded and the peer may discard offered message identifiers when the list is full.
### 4.2 Synchronisation Modes
Each time a device has an opportunity to send records to a peer, it decides whether to use ***interactive mode***, ***batch mode*** or ***eager mode***.
Interactive mode uses less bandwidth than the other modes, but needs two round-trips for synchronisation, whereas the other modes need one round-trip. Interactive mode is generally suitable for transports with relatively short round-trip times, such as TCP.
Batch mode uses more bandwidth than interactive mode, but less than eager mode. It is generally suitable for transports with relatively long round-trip times and low risk of data loss, where it is better to wait for an acknowledgement than to resend a message at the next opportunity.
Eager mode uses more bandwidth than the other modes. It is generally suitable for transports with relatively long round-trip times and high risk of data loss, where it is better to resend a message at the next opportunity than to wait for an acknowledgement.
The device may choose a mode based on prior knowledge or measurements of the underlying transport, such as the round-trip time, or it may use any other method. Devices may use different methods of choosing modes than their peers.
In interactive mode, messages are offered before being sent. The device does the following, in any order:
- **Acknowledge** any messages **received** from the peer that the device has not yet acknowledged
- **Acknowledge** any messages **offered** by the peer that the device has seen and has not yet acknowledged
- **Request** any messages **offered** by the peer that the device has not seen and has not yet requested
- **Send** any messages that the device is **sharing** with the peer, that have been **requested** by the peer, and that are **ready to send** (see below)
- **Offer** any messages that the device is **sharing** with the peer, and does not know whether the peer has seen, and that are ready to send
In batch mode, messages are sent without being offered. The device does the following, in any order:
- **Acknowledge** any messages **sent** by the peer that the device has not yet acknowledged
- **Acknowledge** any messages **offered** by the peer that the device has seen and has not yet acknowledged
- **Send** any messages that the device is **sharing** with the peer, and does not know whether the peer has seen, and that are ready to send
In eager mode, messages are sent without being offered, and may be resent immediately. The device does the following, in any order:
- **Acknowledge** any messages **sent** by the peer that the device has not yet acknowledged
- **Acknowledge** any messages **offered** by the peer that the device has seen and has not yet acknowledged
- **Send** any messages that the device is **sharing** with the peer, and does not know whether the peer has seen, regardless of whether they are ready to send
### 4.3 Retransmission
Whenever a device offers or sends a message to a peer, it increases the message's **send count** and **send time** and updates the message's **expected arrival time**.
A device may increase the send time based on prior knowledge or measurements of the underlying transport, such as the round-trip time, or it may use any other method. Devices may use different methods from their peers. BSP only requires that the send time should increase exponentially with the send count. In other words, retransmission should use some form of exponential backoff.
Similarly, a device may update the expected arrival time based on prior knowledge or measurements of the underlying transport, or it may use any other method. Devices may use different methods from their peers.
A message is considered **ready to send** if either its send time has been reached, or the expected arrival time would be reduced if the message was sent now.
Each group belongs to a client that is responsible for deciding which peers the group should be shared with, what constitutes a valid message, which messages should be shared, and which messages should be deleted. The messages in the group form a message graph.
The message graph is a directed graph where each message points to its **dependencies**. The list of dependencies is encoded in the message body in a format determined by the client. Since messages are immutable, dependency relationships are also immutable and the graph is acyclic. The graph may have more than one component.
When a device receives a message for the first time, the client responsible for the corresponding group parses the message body and extracts a list of dependencies. BSP uses the list of dependencies to determine the message's position in the message graph. If the client cannot parse the message, BSP marks it as invalid and deletes it. Any messages that transitively depend on it are also marked as invalid and deleted.
A message is eligible to be **delivered** to the client when all its dependencies have been delivered. Thus on every device in the group, messages are delivered to the client in a consistent order, even if the messages arrive at different devices in different orders. This can be used to implement **causal consistency**. When a message is delivered, the client validates the message in the context of its dependencies. If the client decides the message is invalid, BSP marks it as invalid and deletes it. Any messages that transitively depend on it are also marked as invalid and deleted.
The client may share any message that has been delivered, in which case the message's transitive dependencies are also shared. The client may delete any message that it no longer needs to store. This does not affect the message's dependencies or dependents.