Forked version of Jami documentation, see wrycode.com/jami-docs-demo
git clone git://git.wrycode.com/wrycode/jami-docs.git
Log | Files | Refs

swarm.md (23162B)

      1 # Understanding Swarms
      3 ## Synospis
      5 The goal of this document is to describe how group chats
      6 (a.k.a. **swarm chat**) will be implemented in Jami.
      8 A *swarm* is a group able to discuss without any central authority in
      9 a resilient way. Indeed, if two person doesn't have any connectivity
     10 with the rest of the group (ie Internet outage) but they can contact
     11 each other (in a LAN for example or in a sub network), they will be
     12 able to send messages to each other and then, will be able to sync
     13 with the rest of the group when it's possible.
     15 So, the *swarm* is defined by:
     16 1. Ability to split and merge following the connectivity.
     17 2. Syncing of the history. Anyone must be able to send a message to the whole group.
     18 3. No central authority. Can't rely on any server.
     19 4. Non-repudiation. Devices must be able to verify old messages validity and to replay the whole history.
     20 5. PFS on the transport. Storage is managed by the device.
     22 Main idea is to get a synchronized merkle tree with the participants.
     24 We identified four modes for swarm chat that we want to implement:
     25 + **ONE_TO_ONE**, basically the case we have today, when you discuss to a friend
     26 + **ADMIN_INVITES_ONLY** generally a class where the teacher can invite people, but not students
     27 + **INVITES_ONLY** a private group of friends
     28 + **PUBLIC** basically an opened forum
     30 ## Scenarios
     32 ### Create a Swarm
     34 *Bob wants to create a new swarm*
     36 1. Bob create a local git repository.
     37 2. Then, he adds an initial signed commit and adds the following:
     38 	+ His public key in `/admins`
     39 	+ His device certificate in `/devices`
     40 	+ His CRL in `/crls`
     41 3. The hash of the first commit becomes the **ID** of the conversation
     42 4. Bob announce to his other devices that he creates a new conversation. This is done via an invite to join the swarm sent through the DHT to other devices linked to that account.
     44 ### Adding someone
     46 *Alice adds Bob*
     48 1. Alice adds Bob to the repo:
     49 	+ Adds the invited uri in `/invited`
     50 	+ Adds the CRL into `/crls`
     51 2. Alice sends a request on the DHT
     53 ### Receiving an invite
     55 *Alice gets the invite to join the previously create swarm*
     57 1. She accepts the invite (if decline, do nothing, it will just stay into invited and Alice will never receives any message)
     58 2. A peer to peer connection between Alice and Bob is done.
     59 3. Alice pull the git repo of Bob. **WARNING this means that messages needs a connection, not from the DHT like today**
     60 4. Alice validates commits from Bob
     61 5. To validate that Alice is a member, she removes the invite from `/invited` directory, then adds her certificate into the `/members` directory
     62 6. Once all commits validated and on her device, other members of the group are discovered by Alice. with these peers, she will construct the **DRT** (explained below) with Bob as a bootstrap.
     64 ### Sending a message
     66 *Alice sends a message*
     68 Sending a message is pretty simple. Alice write a commit-message with the following format:
     70 **TODO format unclear**
     72 and adds her device and CRL to the repository if missing (others must be able to verify the commit). Merge conflicts are avoided because we are mostly based on commit messages, not files (unless CRLS + certificates but they are located). then she announce the new commit via the **DRT** with a service message (explained later) and ping the DHT for mobile devices (they must receive a push notification).
     74 For pinging other devices, the sender sends to other members a SIP messages with mimetype = "application/im-gitmessage-id" containing a JSON with the "deviceId" which sends the message, the "id" of the conversation related and the "commit"
     76 ### Receiving a message
     78 *Bob receives the message from Alice*
     80 1. *Bob* do a git pull on *Alice*
     81 2. Commits MUST be verified via a hook
     82 3. If all commits are valid, commits are stored and displayed. Then *Bob* announce the message via the DRT for other devices.
     83 4. If all commits are not valid, pull is cancelled. *Alice* must restablish her state to a correct state. **TODO process*
     85 ### Validating a commit
     87 To avoid users to push some unwanted commits (with conflicts, false messages, etc), this is how each commits (from the oldest to the newest one) MUST be validated before merging a remote branch:
     89 Note: if the validation fails, the fetch is ignored and we do not merge the branch (and remove the datas), and the user should be notified
     90 Note2: If a fetch is too big, it's not done (**TODO**)
     92 + For each commits, check that the device who try to send the commit is authorized at this moment, and that the certificates are present (in /devices for the device, and in /members or /admins for the issuer).
     93 + 3 cases. The commit has 2 parents, so it's a merge, nothing more to validate here
     94 + The commit has 0 parent, it's the initial commit:
     95 	+ Check that admin cert is added
     96 	+ Check that device cert is added
     97 	+ Check CRLs added
     98 	+ Check that no other file is added
     99 + The commit has 1 parent, commit msg is a JSON with a type:
    100 	+ If text (or other mimetype that doesn't change files)
    101 		+ Check signature from certif in repo
    102 		+ Check that no weird file is added outside device cert nor removed
    103 	+ If vote
    104 		+ Check that vote is for user that signs the commit
    105 		+ Check that vote is from an admin and device present & not banned
    106 		+ Check that no weird file is added nor removed
    107 	+ If member
    108 		+ If adds
    109 			+ Check that commit is correctly signed
    110 			+ Check that certificate is added in /invited
    111 			+ Check that no weird file is added nor removed
    112 			+ If ONE_TO_ONE, check that we only have one admin, one member
    113 			+ If ADMIN_INVITES_ONLY, check that invite is from an admin
    114 		+ If joins
    115 			+ Check that commit is correctly signed
    116 			+ Check that device is added
    117 			+ Check that invitation is moved to members
    118 			+ Check that no weird file is added nor removed
    119 		+ If kickban
    120 			+ Check that vote is valid
    121 			+ Check that the user is ban via an admin
    122 			+ Check that member or device certificate is moved to banned/
    123 			+ Check that only files related to the vote is removed
    124 			+ Check that no weird file is added nor removed
    125 	+ else fail. Notify the user that they may be with an old version or that peer tried to submit unwanted commits
    128 ### Ban a device
    130 *Alice, Bob, Carla, Denys are in a swarm. Alice bans Denys*
    132 This is one of the most difficult scenario in our context. Without central authority we can't trust:
    134 1. Timestamps of generated commits
    135 2. Conflicts with banned devices. If multiple admin devices are present and if Alice can speak with Bob but not Denys and Carla ; Carla can speak with Denys ; Denys bans Alice, Alice bans Denys, what will be the state when the 4 members will merge the conversations.
    136 3. A device can be compromised, stolen or its certificate can expire. We should be able to ban a device and avoid that it lies about its expiration or send messages in the past (by changing its certificate or the timestamp of its commit).
    138 Similar systems (with distributed group systems) are not so much, but this is some examples:
    140 + [mpOTR doesn't define how to ban someone](https://www.cypherpunks.ca/~iang/pubs/mpotr.pdf)
    141 + Signal, without any central server for group chat (EDIT: they recently change that point) doesn't give the ability to ban someone of a group.
    143 This voting system need a human action to ban someone or must be based on the CRLs infos from the repository (because we can't trust external CRLs)
    145 ### Remove a device from a conversation
    147 This is the only part that MUST have a consensus to avoid conversation's split, like if two members kick each others from the conversation, what will see the third one?
    149 This is needed to detect revoked devices, or simply avoid to get unwanted people present in a public room. The process is pretty similar between a member and a device:
    151 *Alice removes Bob*
    153 Note: Alice MUST be admins to vote
    155 + First, she votes for ban Bob. To do that, she creates the file in /votes/members/uri_bob/uri_alice (members can be replaced by devices for a device) and commit
    156 + Then she checks if the vote is resolved. This means that >50% of the admins agree to ban Bob (if she is alone, it's sure it's more than 50%).
    157 + If the vote is resolved, files into /votes can be removed, all files for Bob in /members, /admins, /CRLs, /devices can be removed (or only in /devices if it's a device that is banned) and Bob's certificate can be placed into /banned/members/bob_uri.crt (or /banned/devices/uri.crt if a device is banned) and committed to the repo
    158 + Then, Alice informs other users (outside Bob)
    160 ### Remove a conversation
    162 1. Save in convInfos removed=time::now() (like removeContact saves in contacts) that the conversation is removed and sync with other user's devices
    163 2. Now, if a new commit is received for this conversation it's ignored
    164 3. Now, if Jami startup and the repo is still present, the conversation is not announced to clients
    165 4. Two cases:
    166 	a. If no other member in the conversation we can immediately removes the repository
    167 	b. If still other members, commit that we leave the conversation, and now wait that at least another device sync this message. This avoid the fact that other members will still detect the user as a valid member and still sends new messages notifications.
    168 5. When we are sure that someone is synched, remove erased=time::now() and sync with other user's devices
    169 6. All devices owned by the user can now erase the repository and related files
    171 ## How to specify a mode
    173 Modes can't be changed through the time. Or it's another conversation. So, this data is stored into the initial commit message.
    174 The commit message will be the following:
    177 ```json
    178 {
    179 	"type": "initial",
    180 	"mode": 0,
    181 }
    182 ```
    184 For now, "mode" accepts values 0 (ONE_TO_ONE), 1 (ADMIN_INVITES_ONLY), 2 (INVITES_ONLY), 3 (PUBLIC)
    186 ### Processus for 1:1 swarms
    188 The goal there is to keep the old API (addContact/removeContact, sendTrustRequest/acceptTrustRequest/discardTrustRequest) to generate swarm with a peer and its contact. This still imply some changes that we cannot ignore:
    190 The process is still the same, an account can add a contact via addContact, then send a TrustRequest via the DHT. But two changes are necessary:
    191 1. The TrustRequest embeds a "conversationId" to inform the peer what conversation to clone when accepting the request
    192 2. TrustRequest are retried when contact come backs online. It's not the case today (as we don't want to generate a new TrustRequest if the peer discard the first). So, if an account receives a trust request, it will be automatically ignored if the request with related conversation is declined (as convRequests are synched)
    194 Then, when a contact accepts the request, a period of sync is necessary, because the contact now needs to clone the conversation.
    196 removeContact() will remove the contact and related 1:1 conversations (with the same processus as "Remove a conversation"). The only note there is that if we ban a contact, we don't wait for sync, we just remove all related files.
    198 #### Tricky scenarios
    200 There is some cases were two conversations can be created. This is at least two of those scenarios:
    202 1. Alice adds Bob
    203 2. Bob accepts
    204 3. Alice removes Bob
    205 4. Alice adds Bob
    207 or
    209 1, Alice adds Bob & Bob adds Alice at the same time, but both are not connected together
    211 In this case, two conversations are generated. We don't want to removes messages from users or choose one conversation here. So, sometimes two 1:1 swarm between the same members will be shown. It will generate some bugs during the transition time (as we don't want to break API, the infered conversation will be one of the two shown conversation, but for now it's "ok-ish", will be fixed when clients will fully handle conversationId for all APIs (calls, file transfer, etc)).
    213 ### Conversations requests specification
    215 Conversations requests are represented by a **Map<String, String>** with the following keys:
    217 + id: the conversation id
    218 + from: uri of the sender
    219 + received: timestamp
    220 + title: (optional) name for the conversation
    221 + description: (optional)
    222 + avatar: (optional)
    224 ### Conversation's profile synchronization
    226 To be identifiable, a conversation generally needs some metadatas, like a title (eg: Jami), a description (eg: some links, what is the project, etc), and an image (the logo of the project). Those metadatas are optional, but shared across all members, so need to be synced and incorporated in the requests.
    228 #### Storage in the repository
    230 The profile of the conversation is stored in a classic vCard file at the root (`/profile.vcf`) like:
    232 ```
    234 VERSION:2.1
    235 FN:TITLE
    237 END:VCARD
    238 ```
    240 #### Synchronization
    242 To update the vCard, an user with enough permissions (by default: =ADMIN) needs to edit `/profile.vcf`. and will commit the file with the mimetype `application/update-profile`. The new message is sent via the same mechanism and all peers will receive the **MessageReceived** signal from the daemon. The branch is dropped if the commit contains other files or too big or if done by a non authorized member (by default: <ADMIN).
    244 #### Merge conflicts management
    246 Because two admins can change the description at the same time, a merge conflict can occurs on `profile.vcf`. In this case, the commit with the higher hash (eg ffffff > 000000) will be chosen.
    248 #### APIs
    250 The user got 2 methods to get and set conversation's metadatas:
    252 ```xml
    253 	   <method name="updateConversationInfos" tp:name-for-bindings="updateConversationInfos">
    254 		   <tp:added version="10.0.0"/>
    255 		   <tp:docstring>
    256 			   Update conversation's infos (supported keys: title, description, avatar)
    257 		   </tp:docstring>
    258 		   <arg type="s" name="accountId" direction="in"/>
    259 		   <arg type="s" name="conversationId" direction="in"/>
    260 		   <annotation name="org.qtproject.QtDBus.QtTypeName.In2" value="VectorMapStringString"/>
    261 		   <arg type="a{ss}" name="infos" direction="in"/>
    262 	   </method>
    264 	   <method name="conversationInfos" tp:name-for-bindings="conversationInfos">
    265 		   <tp:added version="10.0.0"/>
    266 		   <tp:docstring>
    267 			   Get conversation's infos (mode, title, description, avatar)
    268 		   </tp:docstring>
    269 		   <annotation name="org.qtproject.QtDBus.QtTypeName.Out0" value="VectorMapStringString"/>
    270 		   <arg type="a{ss}" name="infos" direction="out"/>
    271 		   <arg type="s" name="accountId" direction="in"/>
    272 		   <arg type="s" name="conversationId" direction="in"/>
    273 	   </method>
    274 ```
    276 where `infos` is a `map<str, str>` with the following keys:
    278 + mode: READ-ONLY
    279 + title
    280 + description
    281 + avatar
    283 #### Re-import an account (link/export)
    285 The archive MUST contains conversationId to be able to be able to retrieve conversations on new commits after a re-import (because there is no invite at this point). If a commit come for a conversation not present there is two possibilities:
    287 + The conversationId is there, in this case the daemon is able to re-clone this conversation
    288 + The conversationId is missing, so the daemon asks (via a message `{{"application/invite", conversationId}}`) a new invite that the user needs to (re)accepts
    290 Note, a conversation can only be retrieven if a contact or another device is there, else it will be lost. There is no magic.
    292 ### Other mime types
    294 + `application/call-history+json` with a JSON containing the `id` and the `duration` of the call
    295 + `application/data-transfer+json` with a JSON containing the `tid` of the file
    297 ## Used protocols
    299 ### Git
    301 #### Why this choice
    303 Each conversation will be a git repository. This choice is motivated by:
    305 1. We need to sync and ordering messages. The Merkle Tree is the perfect structure to do that and can be linearized by merging branches. Moreover, because it's massively used by Git, it's easy to sync between devices.
    306 2. Distributed by nature. Massively used. Lot of backends and plugguable.
    307 3. Can verify commits via hooks and massively used crypto
    308 4. Can be stored in a database if necessary
    309 5. Conflicts are avoided by using commit messages, not files.
    311 #### What we have to validate
    313 + Performance? `git.lock` can be low
    314 + Hooks in libgit2
    315 + Multiple pulls at the same time?
    317 #### Limits
    319 History can't be deleted. To delete a conversation, the device has to leave the conversation and create another one.
    321 However, non permanent messages (like messages readable only for some minutes) can be sent via a  special message via the DRT (like Typing or Read notifications).
    323 Moreover editing messages will be possible! (`commit --fixup`)
    325 #### Structure
    327 ```
    328 /
    329  - invited
    330  - admins (public keys)
    331  - members (public keys)
    332  - devices (certificates of authors to verify commits)
    333  - banned
    334    - devices
    335    - members
    336  - votes
    337 	- members
    338 		- uri
    339 	- devices
    340 		- uri
    341  - CRLs
    342 ```
    344 #### Attacks?
    346 + Avoid git bombs
    348 #### Notes
    350 Timestamp of a commit can be trusted because it's editable. Only the user's timestamp can be trusted.
    352 ### TLS
    354 Git operations, control messages, files and other things will use a p2p TLS v1.3 link with only cyphers which garanty PFS. So each key is renegotiated for each new connexion.
    356 ### DHT (udp)
    358 Used to send messages for mobiles (to trigger push notifications) and to initiate TCP connexions.
    360 ### DRT (name will change)
    362 The DRT is a new concept used in swarm to maintain p2p connections. Indeed, group members define a graph of nodes (identified by a hash) en must be connected.
    364 So we need a structure that:
    366 1. Maximize the connected nodes at every time
    367 2. Minimize the time for message transmission
    368 3. Minimize links between peers
    369 4. Needs low calculation
    371 Several solutions exists:
    373 1. Each node has a connection  to the next node. So we only need $N$ connections, but it's not effective to transmit a message, because the message will go though all peers, one by one.
    374 2. Each nodes is connected to all other nodes $N\timesN$ connections. Effective to transmit, but need more resources **WILL BE CHOSEN FOR THE FIRST VERSION**
    375 3. *Maximizing the Coverage of Roadmap Graph for Optimal Motion Planning*
    376 https://www.hindawi.com/journals/complexity/2018/9104720/. But need calculations
    377 4. Use the algorithm of the DHT for the routing table. The 4 points are basically solved and already used by Jami in UDP.
    379 Note: to optimize the socket numbers, a socket will be given by a **ConnectionManager** to get multiplexed sockets with a given hash. This means that if we need to transmit several files, and chat with someone, only one socket will be used.
    381 ### File transfer (libtorrent?)
    383 **TODO**
    385 ### Network activity
    387 #### Process to invite someone
    389 Alice wants to invite Bob:
    391 1. Alice adds bob to a conversation
    392 2. Alice generates an invite: { "application/invite+json" : {
    393 	"conversationId": "$id",
    394 	"members": [{...}]
    395 }}
    396 3. Two possibilites for sending the message
    397 	a. If not connected, via the DHT
    398 	b. Else, Alice sends on the SIP channel
    399 4. Two possibilities for Bob
    400 	a. Receives the invite, a signal is emitted for the client
    401 	b. Not connected, so will never receives the request cause Alice must not know if Bob just ignored or blocked alice. The only way is to regenerate a new invite via a new message (cf next scenario)
    403 #### Process to send a message to someone
    405 Alice wants to send a message to Bob:
    407 1. Alice adds a message in the repo, giving an ID
    408 2. Alice gets a message received (from herself) if successful
    409 3. Two possibilities, alice and bob are connected, or not. In both case a message is crafted: { "application/im-gitmessage-id" : "{"id":"$convId", "commit":"$commitId", "deviceId": "$alice_device_hash"}"}.
    410 	a. If not connected, via the DHT
    411 	b. Else, Alice sends on the SIP channel
    412 4. Four possibilities for Bob:
    413 	a. Bob is not connected to Alice, so if he trusts alice, ask for a new conection and go to b.
    414 	b. If connected, fetch from alice and announce new messages
    415 	c. Bob doesn't know that conversation. Ask through the DHT to get an invite first to be able to accept that conversation ({"application/invite", conversationId})
    416 	d. Bob is disconnected (no network, or just closed). He will not receive the new message, but will try to sync when the next connection will occurs
    419 ### Implementation
    421 **!! OLD DRAFT !!**
    423 Note: Following notes are not organized yet. Just some line of thoughts.
    425 ## Crypto improvements.
    427 For a serious group chat feature, we also need serious crypto. With the current design, if a certificate is stolen as the previous DHT values of a conversation, the conversation can be decrypted. Maybe we need to go to something like **Double ratchet**.
    429 Note: a lib might exists to implement group conversations. TODO, investigate.
    431 Needs ECC support in OpenDHT
    433 ## Usage
    435 ### Add Roles?
    437 There is two major use case for group chats:
    439 1. Something like a Mattermost in a company, with private channels, and some roles (admin/spectator/bot/etc) or for educations (where only a few are active).
    440 2. Horizontal conversations like a conversation between friends.
    442 Ring will be for which one?
    444 #### Implementation idea
    446 A certificate for a group which sign user with a flag for a role. Adding or revoking can also be done.
    448 ### Join a conversation
    450 + Only via a direct invite
    451 + Via a link/QR Code/whatever
    452 + Via a room name? (a **hash** on the DHT)
    454 ## What we need
    456 + Confidentiality: members outside of the group chat should not be able to read messages in the group
    457 + Forward secrecy: if any key from the group os compromised, previous messages should remain confidential (as much as possible)
    459 + Message ordering: There is a need to have messages in the right order
    460 + Synchronization: There is also a need to be sure to have all messages at soon as possible.
    461 + Persistence: Actually, a message on the DHT lives only 10 minutes. Because it's the best timing calculated for this kind of DHT. To persist datas, the node must re-put the value on the DHT every 10 minutes. Another way to do when the node is offline is to let nodes re-put the data. But, if after 10 minutes, 8 nodes are still here, they will do 64 requests (and it's exponential). The current way to avoid spamming for that is queries. This will still do 64 requests but limit the max redundency to 8 nodes.
    463 ## Other distributed ways
    465 + IPFS: Need some investigation
    466 + BitMessage: Need some investigation
    467 + Maidsafe: Need some investigation
    469 ### Based on current work we have
    471 Groups chat can be based on the same work we already have for multi devices (but here, with a group certificate). Problems to solve:
    473 1. History sync. This need to move the database from the client into the daemon.
    474 2. If nobody is connected, the synchronization can't be done, and the person will never see the conversation
    476 ### Another dedicated DHT
    478 Like a DHT with super user. (Not convinced)
    480 ## File transfer
    482 Currently the file transfer algorithm is based on a TURN connection (See https://git.ring.cx/savoirfairelinux/ring-project/wikis/tutorials/File-transfer). In case of a big group, this will be bad. We first need a p2p implem for the file transfer. Implement the RFC for p2p transfer.
    484 Other problem: currently there is no implementation for TCP support for ICE in PJSIP. This is mandatory for this point (in pjsip or home made)
    486 ## Resources
    488 + https://eprint.iacr.org/2017/666.pdf
    489 + Robust distributed synchronization of networked linear systems with intermittent information (Sean Phillips and Ricardo G.Sanfelice)