3d Range-Based Set Reconciliation

This page has been superseded by the page on region-based set reconciliation. The only links to this page should be from the Confidential Sync draft specification, whose development is put on hold and which uses a few obsoleted concepts.

In particular, that specification refers to 3d range-based set reconciliation, which is region-based set reconciliation using 3dRanges as regions. Our not-outdated specifications use AreaSlices instead of 3dRanges.

What follows are some definitions that are still referenced from the Confidential Sync spec draft. We keep them here for completeness, but you should consider them deprecated; when we return to Confidential Sync development it will use AreaSlices as regions as well.

Let Fingerprint denote the type of hashes of LengthyAuthorisedEntries that the peers exchange. Then the precise pieces of information that the peers need to exchange are the following:

1
The Fingerprint over all LengthyAuthorisedEntries a peer holds in some 3dRange.
2
struct 3dRangeFingerprint {
3
 
The 3dRange in question.
4
 
3d_range: 3dRange,
5
 
The Fingerprint over the LengthyAuthorisedEntries that the sender holds in the 3d_range.
6
 
fingerprint: Fingerprint,
7
}
8
9
The set of LengthyAuthorisedEntries a peer holds in some 3dRange.
10
struct 3dRangeEntrySet {
11
 
The 3dRange in question.
12
 
3d_range: 3dRange,
13
 
The LengthyAuthorisedEntries that the sender holds in the 3d_range.
14
 
entries: &[LengthyAuthorisedEntry],
15
 
A boolean flag to indicate whether the sender wishes to receive the other peer’s 3dRangeEntrySet for the same 3d_range in return.
16
 
want_response: Bool,
17
}

To initiate reconciliation of a 3dRange, a peer sends its 3dRangeFingerprint. Upon receiving a 3dRangeFingerprint, a peer computes the Fingerprint over its local LengthyAuthorisedEntries in the same range.

If it does not match, the peer either sends a number of 3dRangeFingerprints whose 3dRanges cover the 3dRange for which it received the mismatching Fingerprint. Or it replies with its 3dRangeEntrySet for that 3dRange, with the want_response flag set to true.

To any such 3dRangeEntrySet, a peer replies with its own 3dRangeEntrySet, setting the want_response flag to false, and omitting all LengthyAuthorisedEntries it had just received in the other peer’s 3dRangeEntrySet.

When a peer receives a 3dRangeFingerprint that matches the Fingerprint over its local LengthyAuthorisedEntries in the same 3dRange, the peer should reply with an empty 3dRangeEntrySet for that 3dRange, setting the want_response flag to false. This notifies the sender of the 3dRangeFingerprint that reconciliation has successfully concluded for the 3dRange.

The peers might be interested in when they have successfully completed reconciliation of a particular 3dRange. Unfortunately, tracking all the 3dRanges that you receive and determining whether their union covers the particular 3dRange you are interested in is a comparatively expensive (and annoying) algorithmic problem. To circumvent this problem, peers can attach small bits of metadata to their messages: whenever a peer splits a 3dRange into a set of covering 3dRanges, the peer can simply attach some metadata to the final such subrange that it sends that indicates which of the 3dRanges sent by the other peer has now been fully covered by subranges.

As long as both peers are accurate in supplying this metadata, they can maintain perfect information about the progress of reconciliation without the need for any sophisticated data structures. Peers should be cautious that a malicious peer could provide wildly inadequate metadata, but in general this is tolerable: a malicious peer can sabotage reconciliation in all sorts of interesting ways regardless.