Decentralised MLS

1. Proposals and Commits
2. Implementation and tests
3. Test file

WARNING: This document is very much in a draft state, and may not make any sense.

Basic ideas:

create a DAG of MLS trees
when multiple senders try to update the MLS tree, we will get a fork
use a Lamport clock to order updates
try to merge the fork by automatically applying changes when possible: tree nodes are tagged with the Lamport timestamp and user ID, and when changes conflict, the operation with the later timestamp (or larger user ID if the timestamps are the same) takes precedence. Some operations may require users to re-do some conflicting operations; this can be done by the next person who sends a message.

TODO: show an example of the DAG and how the Lamport clock works

For simplicity, we assume that each user owns only one leaf in the MLS tree. But in practice, we would s/user/device/.

The explanation includes an implementation in Julia. The LBBTree (a left-balanced tree) and TreeKEM modules are not currently included in this file, but may be later on. We will be working with a simplified model for the tree for demonstration purposes.

1 Proposals and Commits

In MLS, users make proposals to the tree, and proposals are grouped together and committed to the tree. In a decentralised environment, this is difficult to do, since the person committing to the tree may not see all the proposals that have been made. To avoid this issue, we will assume that proposals are committed immediately. Thus we only need to merge committed changes together.

2 Implementation and tests

In addition to the normal information required for TreeKEM, the tree nodes must contain the timestamp at which the node was last updated and the user who updated it. The user will be represented by the index of the leaf that they occupy.

ClockedTreeKEM.jl =

module ClockedTreeKEM

using ..LBBTree # left-balanced binary tree implementation
using ..TreeKEM # basic TreeKEM implementation

<<clocked_tree_kem>>

end

<<clocked_tree_kem>> =

struct Data
    key::TreeKEM.Data
    time::UInt
    user_id::Int
end

"create data with no key"
Data(time::UInt, user_id::Int) =
    Data(TreeKEM.Data(nothing, nothing), time, user_id)
"create data with only a public key"
Data(pubKey::TreeKEM.Key, time::UInt, user_id::Int) =
    Data(TreeKEM.Data(nothing, pubKey), time, user_id)
"create data with a public and private key"
Data(privKey::TreeKEM.Key, pubKey::TreeKEM.Key, time::UInt, user_id::Int) =
    Data(TreeKEM.Data(privKey, pubKey), time, user_id)

# when printing, print the key data, followed by the time and user ID
Base.show(io::IO, data::Data) =
    print(io, data.key, " (", data.time, ",", data.user_id, ")")

Our tree will also contain the current timestamp, so that when we apply operations, it will know what timestamp to use.

<<clocked_tree_kem>> =

struct Tree
    tree::LBBTree.Tree{Data}
    time::UInt
end

# when we print a tree, only print the tree and not the current clock
Base.show(io::IO, tree::Tree) = Base.show(io, tree.tree)

When we create a tree, we will assume that the user in leaf 0 created the tree.

<<clocked_tree_kem>> =

"""
create a tree from a vector of leaf data
"""
function initTree(data::Vector{TreeKEM.Data})
    # the LBBTree constructor expects a vector of data for all nodes, which the
    # leaf node data with an internal node stuck in between.
    allNodes = Vector{Data}(undef, 2*length(data) - 1)
    allNodes[1] = Data(data[1], UInt(0), 0)
    for i = 2:length(data)
        allNodes[2i-2] = Data(UInt(0), 0)
        allNodes[2i-1] = Data(data[i], UInt(0), 0)
    end
    Tree(LBBTree.Tree(allNodes), UInt(0))
end

2.1 `Update` operations

For applying an Update operation, we define two functions. The first function is used normally by a user updating the tree, and overwrites the node data in a path of the tree. This version just uses the next Lamport timestamp from the tree.

<<clocked_tree_kem>> =

"""
perform an `Update` on the tree, given a vector of new data for the path from
the tree root to the leaf
"""
function update(
    t::Tree, index::Integer, keys::Vector{TreeKEM.Data}
)
    newtime = t.time + 1
    Tree(_update(t.tree, index, keys, newtime), newtime)
end

function _update(
    t::LBBTree.Tree{Data}, index::Integer, keys::Vector{TreeKEM.Data},
    newtime::UInt
)
    path = LBBTree.pathToLeaf(t, index)

    # convert the vector of keys to the data stored in the key by adding the
    # timestamp and the user
    #data = Data[Data(key, newtime, index) for key in keys]
    data = Data.(keys, newtime, index)

    LBBTree.replacePath(t, path, data)
end

The second function is used for applying an update coming from a different branch in the DAG. This requires you to specify the timestamp associated with the operation. It also needs to ensure that it does not overwrite any changes coming from operations that came "later" than it, according to the Lamport clock. We do this by using a _newer function, which given the current node data and the proposed replacement data, will return the data that is considered newer.

When we apply an update, we will use the special missing value to indicate that a specific node should be left alone. This will be used when merging Add operations.

<<clocked_tree_kem>> =

"""
Return the `Data` that is newer, based on the Lamport timestamp and user ID
"""
_newer(x::Data, y::Union{Data, Missing}) =
    ismissing(y) || x.time > y.time || (x.time == y.time && x.user_id > y.user_id) ? x : y

"""
apply an `Update` operation from a different branch of the DAG
"""
function applyUpdate(
    t::Tree, index::Integer, keys,
    time::UInt
)
    Tree(_applyUpdate(t.tree, index, keys, time), max(t.time, time))
end

function _applyUpdate(
    t::LBBTree.Tree{Data}, index::Integer, keys,
    time::UInt
)
    path = LBBTree.pathToLeaf(t, index)

    # convert the vector of keys to the data stored in the key by adding the
    # timestamp and the user
    data = map(key -> ismissing(key) ? missing : Data(key, time, index), keys)

    # apply the new data to the path, keeping the newer data
    LBBTree.replacePath(t, path, _newer, data)
end

Using this, a set of Update operations can be applied in any order, and end up with the same tree.

TODO: ensure that everyone gets sent all the private keys that they need.

In this example, we start with a tree with five leaf nodes and blank internal nodes. In one branch of the DAG, users 1 and 4 perform updates, and in another branch, user 3 performs an update. At this point, the changes from the two branches are communicated to the other side, so user 3's update is applied to the tree from the first branch, and user 1 and 4's updates are applied to the tree from the second branch.

(The ~ function in the example is a helper function that allows Julia's pipe operator (|>) to work with multi-argument functions.)

Example:

data = Data.(["0", "1", "2", "3", "4"])
tree = ClockedTreeKEM.initTree(data)
# clock = 0

# Users 1 and 4 update keys.  Then user 3's update from the other branch of the
# DAG is applied.
t1 = tree |>
    (~ClockedTreeKEM.update)(
        1, Data.(["new1'''", "new1''", "new1'", "new1"])
    ) |>
    # clock = 1
    (~ClockedTreeKEM.update)(
        4, Data.(["new4''", "new4'", "new4"])
    ) |>
    # clock = 2
    (~ClockedTreeKEM.applyUpdate)(
        3, Data.(["new3'''", "new3''", "new3'", "new3"]), UInt(1)
    )
    # clock = 2

# User 3 updates their key.  Then the updates from users 1 and 4 are applied.
t2 = tree |>
    (~ClockedTreeKEM.update)(
        3, Data.(["new3'''", "new3''", "new3'", "new3"])
    ) |>
    # clock = 1
    (~ClockedTreeKEM.applyUpdate)(
        1, Data.(["new1'''", "new1''", "new1'", "new1"]), UInt(1)
    ) |>
    # clock = 1
    (~ClockedTreeKEM.applyUpdate)(
        4, Data.(["new4''", "new4'", "new4"]), UInt(2)
    )
    # clock = 2

println(t1)

@test t1 == t2

Tree{Main.ClockedTreeKEM.Data}:
         ,- pubKey: 0 (0,0)
     ,- pubKey: new1' (1,1)
    |    `- pubKey: new1 (1,1)
 ,- pubKey: new3'' (1,3)
|   |    ,- pubKey: 2 (0,0)
|    `- pubKey: new3' (1,3)
|        `- pubKey: new3 (1,3)
pubKey: new4'' (2,4)
 `- pubKey: new4' (2,4)

2.2 `Delete` operations

Delete operations are similar to Update operations in that they just change the keys on paths in the tree. Again, we have two functions to apply Delete operations.

<<clocked_tree_kem>> =

"""
Delete the node at `index` from `t`.  The delete is performed by `deleter_index`,
who updates the nodes on the path from root to their leaf with the given `keys`
"""
function delete(
    t::Tree, index::Integer,
    deleter_index::Integer, keys::Vector{TreeKEM.Data}
)
    newtime = t.time + 1

    # blank the path from the deleted index to the root
    path = LBBTree.pathToLeaf(t.tree, index)
    len = length(path)
    data = fill(Data(newtime, deleter_index), len)
    deleted_tree = LBBTree.replacePath(t.tree, path, data)

    # the deleter does an update
    Tree(_update(deleted_tree, deleter_index, keys, newtime), newtime)
end

"""
Apply a `Delete` operation from another branch of the DAG.
"""
function applyDelete(
    t::Tree, index::Integer,
    deleter_index::Integer, keys::Vector{TreeKEM.Data},
    time::UInt
)
    path = LBBTree.pathToLeaf(t.tree, index)
    len = length(path)
    data = fill(Data(time, deleter_index), len)
    deleted_tree = LBBTree.replacePath(t.tree, path, _newer, data)
    Tree(_applyUpdate(deleted_tree, deleter_index, keys, time), max(t.time, time))
end

Delete operations can be mixed in with Update operations, and applying operations from different branches of the DAG gives the expected results.

TODO: explain example

Example:

data = Data.(["0", "1", "2", "3", "4"])
tree = ClockedTreeKEM.initTree(data)
# clock = 0

t1 = tree |>
    (~ClockedTreeKEM.update)(
        1, Data.(["new1'''", "new1''", "new1'", "new1"])
    ) |>
    # clock = 1
    (~ClockedTreeKEM.delete)(
        0, 4, Data.(["new4''", "new4'", "new4"])
    ) |>
    # clock = 2
    (~ClockedTreeKEM.applyDelete)(
        2, 3, Data.(["new3'''", "new3''", "new3'", "new3"]), UInt(1)
    )
    # clock = 2

t2 = tree |>
    (~ClockedTreeKEM.delete)(
        2, 3, Data.(["new3''''", "new3''", "new3'", "new3"])
    ) |>
    # clock = 1
    (~ClockedTreeKEM.applyUpdate)(
        1, Data.(["new1'''", "new1''", "new1'", "new1"]), UInt(1)
    ) |>
    # clock = 1
    (~ClockedTreeKEM.applyDelete)(
        0, 4, Data.(["new4''", "new4'", "new4"]), UInt(2)
    )
    # clock = 2

println(t1)

@test t1 == t2

Tree{Main.ClockedTreeKEM.Data}:
         ,- blank (2,4)
     ,- blank (2,4)
    |    `- pubKey: new1 (1,1)
 ,- blank (2,4)
|   |    ,- blank (1,3)
|    `- pubKey: new3' (1,3)
|        `- pubKey: new3 (1,3)
pubKey: new4'' (2,4)
 `- pubKey: new4' (2,4)

However, with deletes, we must ensure that the deleted user does not have access to any of the keys used by the tree. This can be performed by ensuring that the next user who sends a message re-deletes the user. This can be done by marking the user as a "dirty delete", which can be done outside of the TreeKEM structure.

TODO: how does this interact with state resolution? e.g. if Alice kicks Bob, and Bob kicks Carol, but state resolution decides that Bob's kick of Carol should be rolled back, then how does Carol get added back to the TreeKEM tree?

2.3 `Add` operations

Add operations are also mostly similar if the added user uses an existing node rather than increasing the size of the tree.

<<clocked_tree_kem>> =

"""
Add a new user with `pubKey` at `index`.  The `Add` is performed by `user_id`.
"""
function add(t::Tree, pubKey::TreeKEM.Key, index::Integer, user_id::Int)
    newtime = t.time + 1
    tree = t.tree

    if index == tree.size
        # adding a new node to the tree
        Tree(
            LBBTree.addNode(
                tree,
                # leaf node is the user's public key
                Data(pubKey, newtime, user_id),
                # all other nodes from root to leaf are blank
                (x, y) -> Data(newtime, user_id)
            ),
            newtime
        )
    else
        # replacing a blank node
        path = LBBTree.pathToLeaf(tree, index)
        len = length(path)

        # all the nodes other than the leaf node will be blank
        data = fill(Data(newtime, user_id), len)
        # the leaf node contains the user's public key
        data[len] = Data(pubKey, newtime, user_id)

        Tree(LBBTree.replacePath(tree, path, data), newtime)
    end
end

"""
Apply an `Add` operation from a different branch in the DAG.
"""
function applyAdd(
    t::Tree, pubKey::TreeKEM.Key, index::Integer, user_id::Int, time::UInt
)
    tree = t.tree

    if index == tree.size
        # adding a new node to the tree
        Tree(
            LBBTree.addNode(
                tree,
                # leaf node is the user's public key
                Data(pubKey, time, user_id),
                # all other nodes from root to leaf are blank
                (x, y) -> Data(time, user_id)
            ),
            max(t.time, time)
        )
    else
        path = LBBTree.pathToLeaf(tree, index)
        len = length(path)

        # all the nodes other than the leaf node will be blank
        data = fill(Data(time, user_id), len)
        # the leaf node contains the user's public key
        data[len] = Data(pubKey, time, user_id)

        Tree(LBBTree.replacePath(tree, path, _newer, data), max(t.time, time))
    end
end

If the added user is placed in a blank node, then an Add operation can be mixed with Update and Delete operations.

TODO: explain example

Example:

data = Data.(["0", nothing, "2", "3", "4"])
tree = ClockedTreeKEM.initTree(data) |>
    # clock = 0
    (~ClockedTreeKEM.update)(
        0, Data.(["0''''", "0''", "0'", "0"])
    ) |>
    # clock = 1
    (~ClockedTreeKEM.update)(
        2, Data.(["2'''", "2''", "2'", "2"])
    )
    # clock = 2

t1 = tree |>
    (~ClockedTreeKEM.add)(
        "1", 1, 0
    ) |>
    # clock = 3
    (~ClockedTreeKEM.update)(
        4, Data.(["new4''", "new4'", "new4"])
    ) |>
    # clock = 4
    (~ClockedTreeKEM.applyDelete)(
        2, 3, Data.(["new3'''", "new3''", "new3'", "new3"]), UInt(3)
    )
    # clock = 4

t2 = tree |>
    (~ClockedTreeKEM.delete)(
        2, 3, Data.(["new3'''", "new3''", "new3'", "new3"])
    ) |>
    # clock = 3
    (~ClockedTreeKEM.applyAdd)(
        "1", 1, 0, UInt(3)
    ) |>
    # clock = 3
    (~ClockedTreeKEM.applyUpdate)(
        4, Data.(["new4''", "new4'", "new4"]), UInt(4)
    )
    # clock = 4

println(t1)

@test t1 == t2

Tree{Main.ClockedTreeKEM.Data}:
         ,- pubKey: 0 (1,0)
     ,- blank (3,0)
    |    `- pubKey: 1 (3,0)
 ,- pubKey: new3'' (3,3)
|   |    ,- blank (3,3)
|    `- pubKey: new3' (3,3)
|        `- pubKey: new3 (3,3)
pubKey: new4'' (4,4)
 `- pubKey: new4' (4,4)

Two cases for Add do not work. The first case is where two or more different users are added to the same slot. In this case, we keep the user with the smallest user ID in the slot, and overwrite any updates from the other user(s) with the latest update from the selected user. The next user who sends a message to the group then re-adds the other user(s) to empty slots. If more than one user needs to be re-added, then they should be re-added in order of their user IDs. By re-adding them in a predictable order, if multiple users perform the re-add operation with the same users, then they will not conflict.

TODO: example

The second case where simply using a Lamport clock does not work is where an Add increases the size of the tree such that the path length changes for an update/delete from a different branch of the DAG. For example:

data = Data.(["0", "1", "2", "3", "4"])
tree = ClockedTreeKEM.initTree(data)
# clock = 0

t1 = ClockedTreeKEM.add(tree, "5", 5, 0)
# clock = 1

println("t1:")
println(t1)

t2 = ClockedTreeKEM.update(tree, 4, Data.(["new4'", "new4"]))
# clock = 1

println("t2:")
println(t2)

t1:
Tree{Main.ClockedTreeKEM.Data}:
         ,- pubKey: 0 (0,0)
     ,- blank (0,0)
    |    `- pubKey: 1 (0,0)
 ,- blank (0,0)
|   |    ,- pubKey: 2 (0,0)
|    `- blank (0,0)
|        `- pubKey: 3 (0,0)
blank (1,0)
|    ,- pubKey: 4 (0,0)
 `- blank (1,0)
     `- pubKey: 5 (1,0)
t2:
Tree{Main.ClockedTreeKEM.Data}:
         ,- pubKey: 0 (0,0)
     ,- blank (0,0)
    |    `- pubKey: 1 (0,0)
 ,- blank (0,0)
|   |    ,- pubKey: 2 (0,0)
|    `- blank (0,0)
|        `- pubKey: 3 (0,0)
pubKey: new4' (1,4)
 `- pubKey: new4 (1,4)

If we simply try to apply the update operation to t1, it will fail since we do not have enough keys; the path from the root to leaf 4 now has length 3 rather than length 2. One possible solution to this is to try to extend the array of values that we set on the path to leaf 4. We can try to extend it with blanks:

data = Data.(["0", "1", "2", "3", "4"])
tree = ClockedTreeKEM.initTree(data)
# clock = 0

t1 = ClockedTreeKEM.add(tree, "5", 5, 0)
# clock = 1

t1_1 = ClockedTreeKEM.applyUpdate(t1, 4, Data.([nothing, "new4'", "new4"]), UInt(1))

println(t1_1)

Tree{Main.ClockedTreeKEM.Data}:
         ,- pubKey: 0 (0,0)
     ,- blank (0,0)
    |    `- pubKey: 1 (0,0)
 ,- blank (0,0)
|   |    ,- pubKey: 2 (0,0)
|    `- blank (0,0)
|        `- pubKey: 3 (0,0)
blank (1,4)
|    ,- pubKey: new4 (1,4)
 `- pubKey: new4' (1,4)
     `- pubKey: 5 (1,0)

However, if we compare this with t2 above, we note that the public key new4' has moved from the root node to the right child of the root node. This is undesirable, since users 0 through 3 are already able to decrypt data encrypted with new4', which means that if, say user 0 is deleted by user 1, the new private key for the root node will be encrypted using new4' (since new4' is on the copath from the root to leaf 1), but user 0 will be able to decrypt it and obtain the new private key.

This can be addressed by remembering which nodes the keys were intended for, by using the node index. For example, new4 is intended for node 9 and new4' is intended for node 8. Then we filter out the keys that, when applied to the new tree, will not be applied to the intended nodes.

<<clocked_tree_kem>> =

function extendPath(t1::Tree, t2::Tree, index::Integer, keys::Vector{TreeKEM.Data})
    # compare the paths from the root to the given leaf in both trees
    path1 = LBBTree.nodeIndexPathToLeaf(t1.tree, index)
    path2 = LBBTree.nodeIndexPathToLeaf(t2.tree, index)
    if (length(path1) == length(path2))
        # if they're the same length, then we're fine
        return keys
    end

    # "keys" was created for t1, so we'll extend it by prepending with nothings
    # until it's the right length for t2, and extend the path in t1 in the same
    # way.  Then check if the node indices are the same in the two paths, and
    # only take the keys where the node indices are the same.
    filler = Iterators.repeated(undef, length(path2) - length(path1))
    map(
        (i2, i1, key) -> i2 == i1 ? key : missing,
        path2,
        Iterators.flatten((filler, path1)),
        Iterators.flatten((filler, keys))
    )
end

Example:

data = Data.(["0", "1", "2", "3", "4"])
tree = ClockedTreeKEM.initTree(data)
# clock = 0

t1 = ClockedTreeKEM.add(tree, "5", 5, 0)
# clock = 1

new_keys = ClockedTreeKEM.extendPath(tree, t1, 4, Data.(["new4'", "new4"]))

t1_1 = ClockedTreeKEM.applyUpdate(t1, 4, new_keys, UInt(1))

println(t1_1)

t2_1 = tree |>
  (~ClockedTreeKEM.update)(
    4, Data.(["new4'", "new4"])
  ) |>
  (~ClockedTreeKEM.applyAdd)(
    "5", 5, 0, UInt(1)
  )

println(t2_1)

@test t1_1 == t2_1

Tree{Main.ClockedTreeKEM.Data}:
         ,- pubKey: 0 (0,0)
     ,- blank (0,0)
    |    `- pubKey: 1 (0,0)
 ,- blank (0,0)
|   |    ,- pubKey: 2 (0,0)
|    `- blank (0,0)
|        `- pubKey: 3 (0,0)
blank (1,0)
|    ,- pubKey: new4 (1,4)
 `- blank (1,0)
     `- pubKey: 5 (1,0)

TODO: how does this interact with state resolution? e.g. if Alice kicks Bob, and Bob adds Carol, but state resolution decides that Bob's add of Carol should be rolled back, then how does Carol get removed from the TreeKEM tree?

TODO: does this work to resolve multiple conflicts?

TODO: turn this into an actual algorithm

3 Test file

include("LBBTree.jl")
include("TreeKEM.jl")
include("ClockedTreeKEM.jl")

using Test

Data = TreeKEM.Data
Key = TreeKEM.Key

"""
Helper for piping to a function that takes multiple arguments, allowing for
Elixir-like notation.  If f() takes multiple arguments, then `x |> (~f)(y1, y2, ...)`
will evaluate to `f(x, y1, y2, ...)`.

"""
~(f::Function) = (args...; kwargs...) -> ((x) -> f(x, args...; kwargs...))

<<tests>>

Decentralised MLS

Table of Contents

1 Proposals and Commits

2 Implementation and tests

2.1 Update operations

2.2 Delete operations

2.3 Add operations

3 Test file

2.1 `Update` operations

2.2 `Delete` operations

2.3 `Add` operations