|
|
# Design options for multi-block messages
|
|
|
|
|
|
## Design goals
|
|
|
|
|
|
* Bandwidth efficiency. The sync protocol should use bandwidth efficiently, both in the case where the receiver has not yet received any part of the message, and in the case where the receiver has received part of the message in a previous or concurrent session. Bandwidth use should scale well with message size and number of messages.
|
|
|
|
|
|
* Database efficiency. Database operations should be small enough in the worst case that they don't cause issues for other parts of the app (e.g. UI responsiveness, network timeouts). The number and size of database operations should scale well with message size and number of messages.
|
|
|
|
|
|
* Compatibility with block encryption. (Note: In the future we may add support for encrypting blocks with a message-specific inner key and a group-specific outer key, allowing data to be synced with devices that don't have access to message content.) The message format should allow group subscribers to reassemble encrypted messages efficiently, while minimising the metadata that's exposed by removing the outer layer of encryption.
|
|
|
|
|
|
|
|
|
## Abandoned design goals
|
|
|
|
|
|
* Reusing blocks across groups. This would make it possible to save bandwidth and storage when using identical blocks of data in messages to different groups (e.g. forwarding an attachment). We couldn't find a way to save bandwidth without potentially leaking information about which groups the receiver subscribes to, so we abandoned this goal. It may still be possible to save storage by deduplicating data in the database.
|
|
|
|
|
|
* Reusing blocks within a group. This would make it possible to save bandwidth and storage when using identical blocks of data in messages to the same group (e.g. sending an updated version of an attachment, or syncing files). We couldn't find a way to reconcile this with the ability to delete messages immediately. If blocks are reusable then blocks of a message being deleted may be used by other messages not yet received, so we must either keep the blocks in case they're needed, which defeats immediate deletion, or inform contacts that we no longer have the blocks, which complicates the sync protocol. Another possibility would be to encrypt the data and store the key in a non-reusable block, which could be deleted immediately, but this would add decryption overhead every time the message was read from the database. On balance we decided that this goal wasn't worthwhile. It may still be possible to save storage by deduplicating data in the database.
|
|
|
|
|
|
|
|
|
## Design options
|
|
|
|
|
|
We considered three options for the structure of multi-block messages:
|
|
|
|
|
|
* Binary tree. Blocks of data form the leaves of a binary hash tree. The message ID is derived from the tree's root hash. When we send a block, we include the hashes needed to derive the root hash.
|
|
|
|
|
|
* B-tree. Blocks of data form the leaves of a b-tree. The hashes of the blocks at each level are packed into blocks at the level above. The message ID is derived from the hash of the root block. Blocks of hashes are sent in the same way as blocks of data.
|
|
|
|
|
|
* Chain. Blocks of data form a chain. Each block except the first includes the hash of the previous block. The message ID is derived from the hash of the last block.
|
|
|
|
|
|
|
|
|
### Binary tree
|
|
|
|
|
|
Block = group ID, block number, block count, tree hashes, body
|
|
|
Body of first block = timestamp, data
|
|
|
Body of subsequent blocks = data
|
|
|
|
|
|
Leaf node of hash tree = body
|
|
|
Parent node of hash tree = H(left child), H(right child)
|
|
|
Message ID = H(group ID, block count, H(root node))
|
|
|
|
|
|
Each block includes the hashes needed to derive the root hash. These are the hashes of the siblings of the block's ancestors in the hash tree.
|
|
|
|
|
|
#### Creating a message
|
|
|
|
|
|
A message is created from a stream of data by dividing the data into blocks, hashing them and storing them in the database. The hash tree is built in memory as the stream is read. At the end of the stream we add the tree hashes to each block, which requires one database operation per block, and associate the message ID with the blocks, which requires a single operation that updates all blocks.
|
|
|
|
|
|
#### Reassembly
|
|
|
|
|
|
When a block is received we can immediately add it to the message. When the message is complete, we already know which blocks belong to the message so we can share or delete the message with a single database operation that updates all blocks.
|
|
|
|
|
|
#### Estimating progress
|
|
|
|
|
|
At any point we know how many blocks have been received and how many are missing.
|
|
|
|
|
|
#### Encryption
|
|
|
|
|
|
When using block encryption, the body is encrypted with the inner key before hashing. The message size is exposed to a future adversary who learns the outer key. The receiver can reassemble the message before knowing the inner key.
|
|
|
|
|
|
#### Sync protocol
|
|
|
|
|
|
The sync protocol uses the existing offer, request and ack records, plus three new records: partial ack, partial offer and block. The existing message record can still be used for single-block messages in the old format.
|
|
|
|
|
|
The receiver sends a request in response to an offer of a message that the receiver has not received any part of.
|
|
|
|
|
|
The receiver sends an ack in response to a message record, or an offer of a message that the receiver has fully received.
|
|
|
|
|
|
The receiver sends a partial ack in response to a block record, or in response to an offer of a message that the receiver has partly received. A partial ack contains the message ID and one or more ranges of block numbers that the receiver acks or requests.
|
|
|
|
|
|
The sender sends a partial offer instead of an offer when the receiver has acked or requested some but not all blocks of a message. A partial offer contains the message ID and one or more ranges of block numbers that the sender wants the receiver to ack or request.
|
|
|
|
|
|
#### Pros and cons
|
|
|
|
|
|
The major drawback of this option is bandwidth inefficiency for large messages, as hashes from the higher layers of the hash tree are included in many blocks. We could omit hashes that have already been sent in the same session, or in blocks already acked by the receiver, but this would increase complexity and require extra database operations to keep track of received hashes.
|
|
|
|
|
|
|
|
|
### B-tree
|
|
|
|
|
|
The b-tree option uses four block types: single, root, middle and leaf. A single block contains an entire message. The other block types are used for multi-block messages.
|
|
|
|
|
|
Root and middle blocks are known as parent blocks. Middle and leaf blocks are known as child blocks.
|
|
|
|
|
|
We considered three variants of the b-tree option:
|
|
|
|
|
|
* Simple b-tree
|
|
|
* B-tree with root pointers
|
|
|
* B-tree with parent pointers
|
|
|
|
|
|
|
|
|
### Simple b-tree
|
|
|
|
|
|
Single block = group ID, block type, timestamp, data
|
|
|
Root block = group ID, block type, timestamp, hashes of children
|
|
|
Middle block = group ID, block type, hashes of children
|
|
|
Leaf block = group ID, block type, data
|
|
|
|
|
|
For sync purposes, each block is identified by its hash. The message is identified by the hash of the root block.
|
|
|
|
|
|
#### Creating a message
|
|
|
|
|
|
A message is created from a stream of data by dividing the data into blocks, hashing them and storing them in the database. Parent blocks are built up incrementally, with each block being hashed and stored when it's complete. At the end of the stream we associate the message ID with the blocks, which requires a single database operation that updates all blocks.
|
|
|
|
|
|
#### Reassembly
|
|
|
|
|
|
When a root block is received, we count the number of complete children. If all the children are complete, the message is complete.
|
|
|
|
|
|
When a middle block is received, we count the number of complete children. If all the children are complete, the middle block is complete. We look up any parent blocks that point to it as a child and increment their complete child counts.
|
|
|
|
|
|
When a leaf block is received, we look up any parent blocks that point to it as a child and increment their complete child counts.
|
|
|
|
|
|
When a root block's children are all complete, the message is complete.
|
|
|
|
|
|
When a middle block's children are all complete, the middle block is complete. We look up any parent blocks that point to it as a child and increment their complete child counts.
|
|
|
|
|
|
A block that points to a single or root block as a child is invalid. A block that points to an invalid block is invalid.
|
|
|
|
|
|
#### Estimating progress
|
|
|
|
|
|
We can estimate how complete a partial message is by dividing the root block's complete child count by its number of children. This may be an underestimate, as blocks of the message may have been received but not yet attached to the root.
|
|
|
|
|
|
#### Encryption
|
|
|
|
|
|
There are two options for block encryption:
|
|
|
|
|
|
1. Data encryption. Only the data and timestamp are encrypted with the inner key. The message size is exposed to a future adversary who learns the outer key.
|
|
|
|
|
|
2. Maximal encryption. Everything except the group ID is encrypted with the inner key. The receiver needs to know the inner key before starting to reassemble the message.
|
|
|
|
|
|
In both cases, blocks are hashed after encrypting with the inner key.
|
|
|
|
|
|
#### Sync protocol
|
|
|
|
|
|
The sync protocol uses the existing offer, request and ack records, plus four new records: block offer, block request, block ack and block. The existing message record can still be used for single-block messages in the old format.
|
|
|
|
|
|
The receiver sends a request in response to an offer of a message that the receiver has not fully received.
|
|
|
|
|
|
The receiver sends an ack in response to a message record, or an offer of a message that the receiver has fully received.
|
|
|
|
|
|
The sender sends a block offer for each block belonging to a message that the receiver has requested, unless the receiver has already acked the block.
|
|
|
|
|
|
The receiver sends a block request in response to a block offer of a block that the receiver has not received.
|
|
|
|
|
|
The receiver sends a block ack in response to a block record, or a block offer of a block that the receiver has received.
|
|
|
|
|
|
The sender sends a block record in response to a block request.
|
|
|
|
|
|
#### Pros and cons
|
|
|
|
|
|
This variant has two major drawbacks:
|
|
|
|
|
|
* Child blocks are reusable between messages. As mentioned above, this prevents us from supporting immediate message deletion without complicating the sync protocol or adding encryption overhead.
|
|
|
|
|
|
* When reassembling a message, we need to keep track of whether the subtree below a parent block is complete. Initialising this state when a parent block is received involves an expensive database query: we need to count the parent's complete children, and since child blocks are reusable the query must consider all child blocks in the group. The query can be made cheaper by keeping the index in memory, but this slows down application startup and uses more memory.
|
|
|
|
|
|
There's also a minor drawback:
|
|
|
|
|
|
* When a message is shared or deleted, we need to know which blocks belong to the message. This requires traversing the b-tree, either eagerly when the message is complete, or lazily when the message is shared or deleted. We can traverse the tree by fetching blocks asynchronously, so the individual database operations are cheap, but for a large message the total cost is significant.
|
|
|
|
|
|
|
|
|
### B-tree with root pointers
|
|
|
|
|
|
Single block = group ID, block type, timestamp, data
|
|
|
Root block = group ID, block type, timestamp, inner hashes of children
|
|
|
Middle block = group ID, block type, outer hash of root block, inner hashes of children
|
|
|
Leaf block = group ID, block type, outer hash of root block, data
|
|
|
|
|
|
In this variant a child block can be referred to by either of two hashes. The inner hash is used when building the tree. The outer hash identifies the block for sync purposes. A single or root block only has an outer hash, which identifies the block for sync purposes. The outer hash of the root block identifies the message.
|
|
|
|
|
|
The outer hash of a child block includes the outer hash of the root block, which is the message ID, so blocks are not reusable between messages.
|
|
|
|
|
|
Outer hash of single block = H(group ID, block type, timestamp, data)
|
|
|
Outer hash of root block = H(group ID, block type, timestamp, inner hashes of children)
|
|
|
|
|
|
Inner hash of middle block = H(group ID, block type, inner hashes of children)
|
|
|
Outer hash of middle block = H(outer hash of root block, inner hash of this block)
|
|
|
|
|
|
Inner hash of leaf block = H(group ID, block type, data)
|
|
|
Outer hash of leaf block = H(outer hash of root block, inner hash of this block)
|
|
|
|
|
|
#### Creating a message
|
|
|
|
|
|
Creating a message works in the same way as the simple variant, except that at the end of the stream we also calculate and store the outer hash of each child block, which requires one database operation per block. The same operation can be used to associate the message ID with the block.
|
|
|
|
|
|
#### Reassembly
|
|
|
|
|
|
Reassembly works in the same way as the simple variant, with an extra check: a block that points to a single, middle or leaf block as the root block is invalid.
|
|
|
|
|
|
#### Estimating progress
|
|
|
|
|
|
Estimating progress works in the same way as the simple variant.
|
|
|
|
|
|
#### Encryption
|
|
|
|
|
|
The block encryption options are similar to the simple variant. Maximal encryption is trickier to implement because we need to be able to calculate the inner hash of a middle or leaf block before decrypting it with the inner key, but the block includes a root pointer that's not included in the inner hash.
|
|
|
|
|
|
Leaving the root pointer outside the inner layer of encryption would expose the message size to a future adversary who learns the outer key. So for a middle or leaf block, we separately encrypt the root pointer with the inner key after calculating the inner hash. To avoid exposing the average message size via the number of blocks of each type, we use the same format for a single or root block, encrypting a magic value in place of the root pointer.
|
|
|
|
|
|
The encrypted root pointers must be unique to avoid exposing the message size.
|
|
|
|
|
|
Inner hash of single block = H(group ID, ENC(inner key, block type, timestamp, data))
|
|
|
Outer hash of single block = H(ENC(inner key, magic value), inner hash of this block)
|
|
|
|
|
|
Inner hash of root block = H(group ID, ENC(inner key, block type, timestamp, inner hashes of children))
|
|
|
Outer hash of root block = H(ENC(inner key, magic value), inner hash of this block)
|
|
|
|
|
|
Inner hash of middle block = H(group ID, ENC(inner key, block type, inner hashes of children))
|
|
|
Outer hash of middle block = H(ENC(inner key, outer hash of root block), inner hash of this block)
|
|
|
|
|
|
Inner hash of leaf block = H(group ID, ENC(inner key, block type, data))
|
|
|
Outer hash of leaf block = H(ENC(inner key, outer hash of root block), inner hash of this block)
|
|
|
|
|
|
#### Sync protocol
|
|
|
|
|
|
The sync protocol is similar to the simple variant, with a small optimisation. The protocol uses a new partial ack record, which contains a message ID. The receiver sends a partial ack in response to an offer if the receiver has received any block containing the message ID. A request is only used if the receiver hasn't received any such block.
|
|
|
|
|
|
The sender interprets a request as requesting every block of the message, so blocks can be sent without exchanging block offers and block requests. This optimisation isn't possible in the simple variant because the receiver may already have received some of the blocks, but may not know that they belong to the message.
|
|
|
|
|
|
The sender sends a block offer for each block belonging to a message that the receiver has partially acked, unless the receiver has already acked the block.
|
|
|
|
|
|
If we use maximal encryption then this optimisation is less effective because we don't know a block's message ID until it's attached to the root.
|
|
|
|
|
|
#### Pros and cons
|
|
|
|
|
|
This variant solves the two major drawbacks of the simple variant:
|
|
|
|
|
|
* Child blocks are no longer reusable between messages because they contain the message ID. Child blocks are still reusable within a message, however. If this is useful, we can allow it but we have to be careful about duplicates when counting a parent's complete children. If it's not useful, we can prevent it by numbering the blocks in each layer of the tree, including the height and block number in each block, and checking that a parent's children have the correct height and block numbers based on the parent's height and block number.
|
|
|
|
|
|
* When a parent block is received, the database query to count its complete children is cheaper than in the simple variant: the query only needs to consider child blocks with a given message ID, rather than all child blocks in the group. (If we use maximal encryption then the query is still expensive: we can't read the message ID until we've decrypted the block, and we can't decrypt the block until we've found its parent, so we have to consider all undecrypted blocks in the group.)
|
|
|
|
|
|
However, this variant doesn't solve the minor drawback of the simple variant: when a message is shared, we have to traverse the b-tree to find out which blocks belong to the message. Although each child block contains the message ID, we can't verify it until we've received the block's ancestors up to the root. So when the message is complete, there may be blocks left over that falsely claim to belong to the message. If we share the message then we shouldn't share these blocks, otherwise an attacker could use these blocks to propagate data across the group, bypassing any flooding protections at the client layer. So before we can share the message we have to traverse the b-tree to find the blocks that genuinely belong to the message.
|
|
|
|
|
|
Deleting a message in this variant doesn't require traversing the b-tree: all blocks that claim to belong to the message can be deleted.
|
|
|
|
|
|
Child blocks are slightly larger than in the simple variant.
|
|
|
|
|
|
|
|
|
### B-tree with parent pointers
|
|
|
|
|
|
This is similar to the previous variant, except that the outer hash of a child block includes the outer hash of its parent, rather than the outer hash of the root block.
|
|
|
|
|
|
#### Creating a message
|
|
|
|
|
|
Creating a message works in the same way as the simple variant, except that at the end of the stream we also calculate and store the outer hash of each child block, which requires one database operation per block.
|
|
|
|
|
|
#### Reassembly
|
|
|
|
|
|
Reassembly works in the same way as the simple variant, with two extra checks: a block that points to a single or leaf block as its parent is invalid, and a block that points to a parent block that does not point back to it as a child is invalid.
|
|
|
|
|
|
#### Estimating progress
|
|
|
|
|
|
Estimating progress works in the same way as the simple variant.
|
|
|
|
|
|
#### Encryption
|
|
|
|
|
|
Block encryption works in the same way as the previous variant, except that when using maximal encryption the parent pointer rather than the root pointer is encrypted separately.
|
|
|
|
|
|
#### Sync protocol
|
|
|
|
|
|
The sync protocol is the same as the simple variant.
|
|
|
|
|
|
#### Pros and cons
|
|
|
|
|
|
The database query to count the complete children of a parent block is even cheaper in this variant than in the previous one: the query only needs to consider child blocks that claim this block as their parent. (As with the previous variant, we lose this advantage if we use maximal encryption.)
|
|
|
|
|
|
This variant shares the minor drawback of the simple variant: when sharing or deleting a message, we have to traverse the b-tree to find out which blocks belong to the message.
|
|
|
|
|
|
Child blocks are slightly larger than in the simple variant.
|
|
|
|
|
|
|
|
|
### Chain
|
|
|
|
|
|
The chain option uses four block types: single, first, middle and last. A single block contains an entire message. The other block types are used for multi-block messages.
|
|
|
|
|
|
We considered three variants of the chain option:
|
|
|
|
|
|
* Simple chain
|
|
|
* Chain with last block pointers
|
|
|
* Chain with next block pointers
|
|
|
|
|
|
|
|
|
### Simple chain
|
|
|
|
|
|
Single block = group ID, block type, timestamp, data
|
|
|
First block = group ID, block type, data
|
|
|
Middle block = group ID, block type, hash of previous block, data
|
|
|
Last block = group ID, block type, block count, hash of previous block, timestamp, data
|
|
|
|
|
|
For sync purposes, each block is identified by its hash. The message is identified by the hash of the last block.
|
|
|
|
|
|
#### Creating a message
|
|
|
|
|
|
A message is created from a stream of data by dividing the data into blocks, hashing them and storing them in the database. At the end of the stream we associate the message ID with the blocks, which requires a single database operation that updates all blocks.
|
|
|
|
|
|
#### Reassembly
|
|
|
|
|
|
Messages are reassembled backwards, starting from the last block. When a last block is received, we start a new partial message. We may then be able to extend the partial message by adding previously received blocks.
|
|
|
|
|
|
When a middle block is received, we look for a partial message whose earliest block points to the newly received block. If found, we add the newly received block to the partial message. We may then be able to extend the partial message by adding previously received blocks.
|
|
|
|
|
|
When a first block is received, we look for a partial message whose earliest block points to the newly received block. If found, we add the newly received block to the partial message, which is now complete.
|
|
|
|
|
|
A block that points to a single or last block as the previous block is invalid. A block that points to an invalid block is invalid. When a message is complete, the block count in the last block must match the number of blocks in the message.
|
|
|
|
|
|
#### Estimating progress
|
|
|
|
|
|
We can estimate how complete a partial message is by dividing the number of blocks in the partial message by the block count in the last block. This may be an underestimate, as blocks of the message may have been received but not yet attached to the partial message.
|
|
|
|
|
|
#### Encryption
|
|
|
|
|
|
There are two options for block encryption:
|
|
|
|
|
|
1. Data encryption. Only the data and timestamp are encrypted with the inner key. The message size is exposed to a future adversary who learns the outer key.
|
|
|
|
|
|
2. Maximal encryption. Everything except the group ID is encrypted with the inner key. The receiver needs to know the inner key before starting to reassemble the message.
|
|
|
|
|
|
In both cases, blocks are hashed after encrypting with the inner key.
|
|
|
|
|
|
#### Sync protocol
|
|
|
|
|
|
The sync protocol uses the existing offer, request and ack records, plus five new records: partial ack, block offer, block request, block ack and block. The existing message record can still be used for single-block messages in the old format.
|
|
|
|
|
|
The receiver sends a request in response to an offer of a message that the receiver has not received the last block of.
|
|
|
|
|
|
The receiver sends an ack in response to a message record, or an offer of a message that the receiver has fully received.
|
|
|
|
|
|
The receiver sends a partial ack in response to an offer of a message that the receiver has received the last block of, but has not fully received. A partial ack contains the message ID and the number of consecutive blocks received, ending at the last block.
|
|
|
|
|
|
The sender sends a block offer for each block belonging to a message that the receiver has requested or partially acked, unless the receiver has already acked the block.
|
|
|
|
|
|
The receiver sends a block request in response to a block offer of a block that the receiver has not received.
|
|
|
|
|
|
The receiver sends a block ack in response to a block record, or a block offer of a block that the receiver has received.
|
|
|
|
|
|
#### Pros and cons
|
|
|
|
|
|
The major drawback of this variant is that first and middle blocks can be reused between messages. As mentioned above, this prevents us from supporting immediate message deletion without complicating the sync protocol or adding encryption overhead.
|
|
|
|
|
|
This variant also has a minor drawback: in the worst case, all reassembly takes place when the last block is received. We can do this asynchronously, with database operations that are individually cheap, but this complicates the implementation.
|
|
|
|
|
|
|
|
|
### Chain with last block pointers
|
|
|
|
|
|
Single block = group ID, block type, timestamp, data
|
|
|
First block = group ID, block type, outer hash of last block, data
|
|
|
Middle block = group ID, block type, outer hash of last block, inner hash of previous block, data
|
|
|
Last block = group ID, block type, block count, inner hash of previous block, timestamp, data
|
|
|
|
|
|
In this variant a first or middle block can be referred to by either of two hashes. The inner hash is used when building the chain. The outer hash identifies the block for sync purposes. A single or last block only has an outer hash, which identifies the block for sync purposes. The outer hash of the last block identifies the message.
|
|
|
|
|
|
The outer hash of a first or middle block includes the outer hash of the last block, which is the message ID, so blocks are not reusable between messages.
|
|
|
|
|
|
Outer hash of single block = H(group ID, block type, timestamp, data)
|
|
|
Outer hash of last block = H(group ID, block type, block count, inner hash of previous block, timestamp, data)
|
|
|
|
|
|
Inner hash of middle block = H(group ID, block type, inner hash of previous block, data)
|
|
|
Outer hash of middle block = H(outer hash of last block, inner hash of this block)
|
|
|
|
|
|
Inner hash of first block = H(group ID, block type, data)
|
|
|
Outer hash of first block = H(outer hash of last block, inner hash of this block)
|
|
|
|
|
|
#### Creating a message
|
|
|
|
|
|
Creating a message works in the same way as the simple variant, except that at the end of the stream we also calculate and store the outer hash of each block except the last, which requires one database operation per block. The same operation can be used to associate the message ID with the block.
|
|
|
|
|
|
#### Reassembly
|
|
|
|
|
|
Reassembly works in the same way as the simple variant, with an extra check: a block that points to a single, first or middle block as the last block is invalid.
|
|
|
|
|
|
#### Estimating progress
|
|
|
|
|
|
Estimating progress works in the same way as the simple variant.
|
|
|
|
|
|
#### Encryption
|
|
|
|
|
|
The block encryption options are similar to the simple variant. Maximal encryption is trickier to implement because we need to be able to calculate the inner hash of a first or middle block before decrypting it with the inner key, but the block includes a last block pointer that's not included in the inner hash.
|
|
|
|
|
|
Leaving the last block pointer outside the inner layer of encryption would expose the message size to a future adversary who learns the outer key. So for a first or middle block, we separately encrypt the last block pointer with the inner key after calculating the inner hash. To avoid exposing the average message size via the number of blocks of each type, we use the same format for a single or last block, encrypting a magic value in place of the last block pointer.
|
|
|
|
|
|
The encrypted last block pointers must be unique to avoid exposing the message size.
|
|
|
|
|
|
Inner hash of single block = H(group ID, ENC(inner key, block type, timestamp, data))
|
|
|
Outer hash of single block = H(ENC(inner key, magic value), inner hash of this block)
|
|
|
|
|
|
Inner hash of last block = H(group ID, ENC(inner key, block type, timestamp, inner hash of previous block, data))
|
|
|
Outer hash of last block = H(ENC(inner key, magic value), inner hash of this block)
|
|
|
|
|
|
Inner hash of middle block = H(group ID, ENC(inner key, block type, inner hash of previous block, data))
|
|
|
Outer hash of middle block = H(ENC(inner key, outer hash of last block), inner hash of this block)
|
|
|
|
|
|
Inner hash of first block = H(group ID, ENC(inner key, block type, data))
|
|
|
Outer hash of first block = H(ENC(inner key, outer hash of last block), inner hash of this block)
|
|
|
|
|
|
#### Sync protocol
|
|
|
|
|
|
The sync protocol is similar to the simple variant, with a small optimisation. The receiver responds to an offer with a partial ack if the receiver has received any block containing the message ID. A request is only used if the receiver hasn't received any such block. (If the receiver hasn't received the last block then the partial ack will say that the number of consecutive blocks received, ending at the last block, is zero.)
|
|
|
|
|
|
The sender interprets a request as requesting every block of the message, so blocks can be sent without exchanging block offers and block requests. This optimisation isn't possible in the simple variant because the receiver may already have received some of the blocks, but may not know that they belong to the message.
|
|
|
|
|
|
If we use maximal encryption then we can't use this optimisation, so the sync protocol is the same as the simple variant.
|
|
|
|
|
|
#### Pros and cons
|
|
|
|
|
|
This variant solves the major drawback of the simple variant: blocks are not reusable between messages.
|
|
|
|
|
|
This variant shares the minor drawback of the simple variant: in the worst case, all reassembly takes place when the last block is received.
|
|
|
|
|
|
First and middle blocks are slightly larger than in the simple variant.
|
|
|
|
|
|
|
|
|
### Chain with next block pointers
|
|
|
|
|
|
This is similar to the previous variant, except that the outer hash of a first or middle block includes the outer hash of the next block, rather than the outer hash of the last block.
|
|
|
|
|
|
#### Creating a message
|
|
|
|
|
|
Creating a message works in the same way as the simple variant, except that at the end of the stream we also calculate and store the outer hash of each block except the last, which requires one database operation per block.
|
|
|
|
|
|
#### Reassembly
|
|
|
|
|
|
This variant provides better support for incremental reassembly than the other two variants. Blocks can be reassembled into message fragments before being attached to the last block. A fragment that includes the last block is called a partial message.
|
|
|
|
|
|
When a last block is received, we start a new partial message. We then look for a fragment whose latest block points to, and is pointed to by, the newly received block. If found, we join the fragments.
|
|
|
|
|
|
When a middle block is received, we look for a fragment whose earliest block points to, and is pointed to by, the newly received block. If not found, we start a new fragment. If found, we add the newly received block to the fragment. We then look for a fragment whose latest block points to, and is pointed to by, the newly received block. If found, we join the fragments.
|
|
|
|
|
|
When a first block is received, we look for a fragment whose earliest block points, and is pointed to by, to the newly received block. If not found, we start a new fragment. If found, we add the newly received block to the fragment.
|
|
|
|
|
|
There are two ways to implement fragments, with different database costs:
|
|
|
|
|
|
1. Each block holds a reference to its fragment. When joining two fragments, we update the shorter fragment's blocks to refer to the longer fragment. In the worst case, each block's reference will be updated log n times as an n-block message is reassembled. When the message is complete, all blocks refer to the same fragment, so associating the message ID with the blocks requires a single operation that updates all blocks.
|
|
|
|
|
|
2. Blocks don't hold references to their fragments. Joining fragments is cheap, but when the message is complete we must traverse the chain to associate the message ID with the blocks, which requires one database operation per block.
|
|
|
|
|
|
If we use maximal encryption then we can't use fragments, so reassembly works in the same way as the simple variant.
|
|
|
|
|
|
A block that points to a single or last block as the previous block is invalid, and a block that points to a single or first block as the next block is invalid. A block that points to an invalid block is invalid. When a message is complete, the block count in the last block must match the number of blocks in the message.
|
|
|
|
|
|
#### Estimating progress
|
|
|
|
|
|
Estimating progress works in the same way as the simple variant.
|
|
|
|
|
|
#### Encryption
|
|
|
|
|
|
Block encryption works in the same way as the previous variant, except that when using maximal encryption the next block pointer rather than the last block pointer is encrypted separately.
|
|
|
|
|
|
#### Sync protocol
|
|
|
|
|
|
The sync protocol is the same as the simple variant.
|
|
|
|
|
|
#### Pros and cons
|
|
|
|
|
|
This variant solves the major drawback of the simple variant: blocks are not reusable between messages.
|
|
|
|
|
|
This variant also solves the minor drawback of the other two variants: in the worst case, reassembly when a block is received involves three database operations, regardless of the message size. This advantage is lost if we use maximal encryption.
|
|
|
|
|
|
First and middle blocks are slightly larger than in the simple variant. |