... | ... | @@ -29,13 +29,13 @@ We considered three options for the structure of multi-block messages: |
|
|
|
|
|
### Binary tree
|
|
|
|
|
|
Block = group ID, block number, block count, tree hashes, body
|
|
|
Body of first block = timestamp, data
|
|
|
Body of subsequent blocks = data
|
|
|
* 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))
|
|
|
+ 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.
|
|
|
|
... | ... | @@ -87,10 +87,10 @@ We considered three variants of the b-tree option: |
|
|
|
|
|
### 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
|
|
|
* 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.
|
|
|
|
... | ... | @@ -157,23 +157,23 @@ There's also a minor drawback: |
|
|
|
|
|
### 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
|
|
|
* 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)
|
|
|
* 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 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)
|
|
|
* 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
|
|
|
|
... | ... | @@ -195,17 +195,17 @@ Leaving the root pointer outside the inner layer of encryption would expose the |
|
|
|
|
|
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 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 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 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)
|
|
|
+ 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
|
|
|
|
... | ... | @@ -278,10 +278,10 @@ We considered three variants of the chain option: |
|
|
|
|
|
### 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
|
|
|
* 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.
|
|
|
|
... | ... | @@ -338,23 +338,23 @@ This variant also has a minor drawback: in the worst case, all reassembly takes |
|
|
|
|
|
### 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
|
|
|
* 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)
|
|
|
* 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 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)
|
|
|
* 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
|
|
|
|
... | ... | @@ -376,17 +376,17 @@ Leaving the last block pointer outside the inner layer of encryption would expos |
|
|
|
|
|
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 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 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 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)
|
|
|
+ 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
|
|
|
|
... | ... | |