ChainPad and Listmap¶
In the database, collaborative documents (i.e. documents that are not static files uploaded by the user) are stored as a series of encrypted "patches" that allow the document to be reconstructed from a starting point. This patch management is handled by our ChainPad library.
Each user initializes a local ChainPad "object" and fills it with the patch history of the database from a given starting point. The patches contain a set of simple operations to perform on the document (e.g. "remove X characters and add 'abc' at the Y position") as well as a "parent". Storing a parent identifier in the patch allows for the document to be re-built with the patches in the correct order. Applying the full set of patches from a starting point (usually an empty string) produces the latest version of the document.
Once the document is restored, CryptPad detects each change made in the application in order to generate a new "local" version of the document and provides this version to ChainPad. ChainPad then analyzes it, finding all the differences between the new version and the previous version. These differences are used to create a new "patch" that is encrypted by CryptPad, sent to other users, and stored in the database.
When receiving a patch in real time from another user, ChainPad tries to integrate it into the current document. If unsaved changes (patch not yet created) are in progress by the current user, ChainPad first merges the local changes with the remote patch before inserting the updated content into the interface. This merge allows users to make many changes simultaneously without losing characters in the content.
ChainPad also includes tools to manage conflicts. While the order of the patches is known, thanks to the parent identifier, the delay for all users to receive patches can result in two users sending patches with the same parent at the same time. This creates a "fork" in the patch tree. As the patches are encrypted, the server cannot determine how to resolve these conflicts. ChainPad has to handle them in each user's browser. To ensure that the result of "merging" the branching patches is identical for all users, ChainPad checks the order of the messages received by the server. Two patches can have the same parent, but one of these patches still reaches the server before the other. WebSocket technology guarantees that messages sent by the server to the various clients arrive in the order in which the server sent them. The ChainPads of all users therefore know which patches have the same parent and the order in which to process them, which is enough to achieve the same result everywhere.
The interactions between CryptPad and ChainPad can be summarized as :
Provide remote patches to ChainPad
Indicate to ChainPad any changes made locally
Receive patches from ChainPad related to local changes
Retrieve the current state of the ChainPad document
State common to all users, called "authDoc"
Local state (not yet saved/sent), called "userDoc"
In order to avoid having to synchronize the complete history of the document since its creation each time a collaborative document is loaded, ChainPad uses a system of checkpoints. Every 50 patches stored in the database, the user creating the patch will in fact create a special patch called a checkpoint. Such a patch consists in a single operation that deletes the entire document and re-inserts it at the same time. Checkpoints have the particularity that they can be used as starting points for the system. Checkpoints also have a special marking added after encryption that allows the server to identify them as such.
When a user loads an existing document and asks for its history, the server will only send all patches starting from the penultimate checkpoint (in theory the last checkpoint is sufficient, but the penultimate one makes it easier to solve some problems). This system saves considerable loading time for documents that are heavily used over long periods of time. It also allows document owners to delete the old history, only keeping the messages from the last two checkpoints in the database.
As mentioned above, ChainPad only works with text documents. This means that the only operations it can perform are to add or remove characters at a given position relative to the beginning of the document. Therefore, ChainPad cannot work with objects or arrays directly, for example using an operation that requires the 3rd element of an array to be changed.
A basic solution would be for ChainPad to work with the string representation of the object (with
JSON.stringify) and to transform it back into an object once the work of ChainPad has been done (with
JSON.parse). The problem with this kind of solution is that conflict management may destroy the document!
To solve this problem, it is possible to initialize an instance of ChainPad with a specific algorithm to handle conflicts, as well as an algorithm to validate a patch. When you want to work with an object, for a patch to be valid,
JSON.parse() must not generate an error. If an error occurs, the patch is simply ignored.
Each instance of ChainPad works with only one document and it must be initialized with the correct algorithm:
ChainPad allows for the management of patches, either to integrate them into the local document or to generate patches from the local document. To form a real-time system, a missing element needs to encrypt these patches and communicate with the server to broadcast them to other users. The chainpad-netflux library addresses this need.
This section explains the Netflux protocol used by CryptPad to communicate with the server, though a WebSocket client and server implementation. The chainpad-netflux library connects a ChainPad instance with this client-side Netflux implementation.
Chainpad-netflux is initialized with a "channelId" corresponding to the desired collaborative document, a "crypto" module containing a function to encrypt and a function to decrypt using the keys corresponding to the desired document, and a WebSocket address to connect to the server.
Chainpad-netflux automatically initializes the Websocket connection to the server:
Join the channel corresponding to the desired document (with the provided channelId)
Create a ChainPad instance
Request history from the server
Decrypt messages from the history
Fill ChainPad with the decrypted history
Other configuration fields of chainpad-netflux are used to interact with the ChainPad instance and to listen to specific events. Chainpad-netflux sends events as soon as remote patches are received, when changes are made to the user list or when disconnecting from the network. It gives access to the ChainPad instance in order to retrieve the current state of the document and to indicate any changes made. As soon as ChainPad generates a patch, it is encrypted by Chainpad-netflux and sent to the server automatically.
The user account (containing the drive), the shared folders and the teams are all used and stored as a chainpad-listmap document.