Newer
Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
# Bramble Synchronisation Protocol, version 1
## 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. Peers that are members of a group do not necessarily share it with each other. Membership and sharing are dynamic.
Each member of a group keeps a partial copy of the message graph. Each message in the member's copy of the graph may be **shared**, **unshared** 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 unshared, the device will retain its local copy but will not synchronise the message to its peers. If a message is deleted, the device no longer has a copy of the message's content.
Each group belongs to a **client application**, which is responsible for deciding which peers the group should be shared with, what constitutes a valid message, and whether each message should be shared, unshared or deleted. BSP implements these policies on behalf of the client.
A message graph is a directed acyclic graph where each message points to its **dependencies**. BSP provides **causal consistency**, meaning that a message is not delivered to the client until its dependencies have been delivered. If the client shares a message then its dependencies are also shared.
BSP requires a **transport layer security protocol** that can deliver data from a sender to a recipient 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.
### 1.2 Cryptographic Primitives
**Notation:** || denotes concatenation, double quotes denote an ASCII string, and len(x) denotes the length of x in bytes, represented as a 32-bit integer. All integers in BSP are big-endian.
BSP uses two cryptographic primitives:
1. **A cryptographic hash function**, H(m)
2. **A random number generator**, R(n), with a output length of n bytes
All hashes are HASH\_LEN bytes. (*Note:* The current version of the protocol uses BLAKE2s as the hash function, giving HASH\_LEN = 32.)
We use H(m) to define a multi-argument hash function:
- HASH(x\_1, ..., x\_n) = H(len(x\_1) || x\_1 || ... || len(x\_n) || x\_n)
R(n) must be either a true random number generator or a cryptographically secure pseudo-random number generator.
## 2 Data Formats
### 2.1 Client Identifiers
Each client has a unique random identifier HASH\_LEN bytes long:
- client\_id = R(HASH\_LEN)
The client identifier is generated by the client developer and serves to prevent collisions between groups and messages belonging to different clients.
### 2.2 Group Identifiers
Each group has a unique identifier HASH\_LEN bytes long. The identifier is calculated by hashing the client identifier and a byte string called the **group descriptor**:
- group\_id = HASH("GROUP\_ID", client\_id, group\_descriptor)
The group descriptor is supplied by the client and is not interpreted by BSP. The maximum length of a group descriptor is 2<sup>15</sup> bytes (32 KiB).
### 2.3 Messages
A message consists of a byte string called the **message body** and a timestamp indicating the time at which the message was created. The timestamp is a 64-bit integer representing milliseconds since the Unix epoch.
The message body is supplied by the client and is not interpreted by BSP. The maximum length of a message body is 2<sup>15</sup> bytes (32 KiB).
### 2.4 Message Identifiers
Each message has a unique identifier HASH\_LEN bytes long. The identifier is calculated by hashing the group identifier, timestamp and message body:
- message\_id = HASH("MESSAGE\_ID", group\_id, timestamp, message\_body)
## 3 Wire Protocol
Peers synchronise data by exchanging **records** via the transport layer security protocol. Each record starts with a four-byte header with the following format:
- Bits 0-7: Protocol version
- Bits 8-15: Record type
- Bits 16-31: Length of the payload in bytes as a 16-bit integer
The current version of the protocol is 1, which has four record types:
**0: ACK** - The payload consists of one or more message identifiers. This record informs the recipient that the sender holds the listed messages.
**1: MESSAGE** - The payload consists of a message (group identifier, timestamp and message body).
**2: OFFER** - The payload consists of one or more message identifiers. This record informs the recipient that the sender holds the listed messages, is sharing them with the recipient, and does not know whether the recipient holds them.
**3: REQUEST** - The payload consists of one or more message identifiers. This record asks the recipient to send the listed messages to the sender.
## 4 Synchronisation
### 4.1 Synchronisation State
A device stores the following synchronisation state for each message it is sharing with each of its peers:
- **Hold flag** - Set to one if the peer is known to hold the message, otherwise zero
- **Ack flag** - Set to one if the device needs to acknowledge receipt of the message from the peer, otherwise zero
- **Request flag** - Set to one if the peer has requested the message since the device last offered or sent it, otherwise zero
- **Send count** - The number of times the message has been offered or sent to the peer
- **Send time** - The time at which the message can next be offered or sent to the peer
The device also stores a list of message identifiers that have been offered by the peer and not yet acknowledged or requested by the device. The length of this list should be bounded, and the device should replace the oldest entry in the list if the maximum length is reached. The maximum length of the list is an implementation parameter.
### 4.2 Synchronisation Modes
Each time a device has an opportunity to send records to a peer, it decides whether to use ***interactive mode*** or ***batch mode***.
Interactive mode uses less bandwidth than batch mode, but needs two round-trips for synchronisation, whereas batch mode needs one.
A 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. BSP does not specify how to decide which mode to use - devices may use different methods, and may change their methods at any time. It is not necessary for peers to choose the same mode.
##### Interactive Mode
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 holds, and has not yet acknowledged
- **Request** any messages **offered** by the peer that the device does not hold, 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 have reached their send times
- **Offer** any messages that the device is **sharing** with the peer, and does not know whether the peer holds, and that have reached their send times
##### Batch Mode
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 holds, and has not yet acknowledged
- **Request** any messages **offered** by the peer that the device does not hold, 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 have reached their send times
- **Send** any messages that the device is **sharing** with the peer, and does not know whether the peer holds, and that have reached their send times
### 4.3 Retransmission
Whenever a device offers or sends a message to a peer, it increases the message's **send count** and **send 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. BSP does not specify how the send time should be increased, except that the amount by which it is increased should increase exponentially with the send count. Devices may use different methods, and may change their methods at any time. It is not necessary for peers to use the same method.