The `reconciliation` protocol finds the differences between two sets of [`14/WAKU2-MESSAGE`](https://rfc.vac.dev/waku/standards/core/14/message) on different nodes.
It assumes that each [`14/WAKU2-MESSAGE`](https://rfc.vac.dev/waku/standards/core/14/message) maps to a uniquely identifying `SyncID`,
which is maintained in an ordered set within each node.
An ordered set of `SyncID`s is termed a `Range`.
This implies that any contiguous subset of a `Range` is also a `Range`.
In other words, the `reconciliation` protocol allows two nodes to find differences between `Range`s of `SyncID`s,
which would map to an equivalent difference in cached [`14/WAKU2-MESSAGE`](https://rfc.vac.dev/waku/standards/core/14/message)s.
These terms, the wire protocol and message flows are explained below.
### Wire protocol
#### Reconcilation payload
Nodes participating in the `reconciliation` protocol exchange encoded `RangesData` messages.
The `RangesData` structure represents a complete `reconciliation` payload:
| shards | seq[varint] | Shards supported by the sender |
| ranges | seq[Range] | Sequence of ranges |
The `cluster` and `shards` fields
represent the sharding elements as defined in [RELAY-SHARDING](https://github.com/waku-org/specs/blob/master/standards/core/relay-sharding.md#static-sharding).
The `ranges` field contain a sequence of ranges for reconciliation.
We identify the following subtypes:
##### Range
A `Range` represents a representation of the bounds, type and, optionally, an encoded representation of the content of a range.
| bounds | RangeBounds | The bounds of the range |
| type | RangeType | The type of the range |
| Option(content)| Fingerprint OR ItemSet | Optional field depending on `type`. If set, possible values are a `Fingerprint` of the range, or the complete `ItemSet` in the range |
##### RangeBounds
`RangeBounds` defines a `Range` by two bounding `SyncID` values, forming a time-hash interval:
| timestamp | varint | Timestamp of the message (nanoseconds) |
| hash | seq[Byte] | 32-byte message hash |
The timestamp MUST be the time of message creation and
the hash MUST follow the [deterministic message hashing specification](https://rfc.vac.dev/waku/standards/core/14/message#deterministic-message-hashing).
SyncIDs MUST be totally ordered by timestamp first, then by hash to disambiguate messages with identical timestamps.
##### RangeType
A `RangeType` indicates the type of `content` encoding for the `Range`:
1. From the first `SyncID`, encode the timestamp in full
2. From the first `SyncID`, encode the hash in full
3. For each subsequent `SyncID`:
- Delta encode the timestamp, i.e., encode only the difference from the previous `SyncID`'s timestamp
- Append the encoded hash in full
4. Encode a single byte for the `reconciled` boolean (0 or 1)
### Reconciliation Message Flow
The `reconciliation` message flow is triggered by an `initiator` with an initial `RangesData` payload.
The selection of sync peers
and triggers for initiating a `reconciliation` is out of scope of this document.
The response to a `RangesData` payload is another `RangesData` payload, according to the heuristic below.
The syncing peers SHOULD continue exchanging `RangesData` payloads until all ranges have been processed.
The output of a `reconciliation` flow is a set of differences in `SyncID`s.
These could either be `SyncID`s present in the remote peer and missing locally,
or `SyncID`s present locally but missing in the remote peer.
Each sync peer MAY use the `transfer` protocol to exchange the full messages corresponding to these computed differences,
proactively transferring messages missing in the remote peer.
#### Initial Message
The initiator
1. Selects a time range to sync
2. Computes a fingerprint for the entire range
3. Constructs an initial `RangesData` payload with:
- The initiator's cluster ID
- The initiator's supported shards
- A single range of type `Fingerprint` covering the entire sync period
- The fingerprint for this range
4. [Delta encodes](#payload-encoding) the payload
5. Sends the payload using libp2p length-prefixed encoding
#### Responding to a `RangesData` payload
Each syncing peer performs the following in response to a `RangesData` payload:
The responder:
1. Receives and decodes the payload
2. If shards and cluster match, processes each range:
- If the received range is of type `Skip`, ignores it.
- If the received range is of type `Fingerprint`, computes the fingerprint over the local matching range
- If the local fingerprint matches the received fingerprint, includes this range in the response as type `Skip`
- If the local fingerprint does _not_ match the received fingerprint:
- If the corresponding range is small enough, includes this range in the response as type `ItemSet` with all `SyncID`s
- If the corresponding range is too large, divide it into subranges.
For each subrange, if the range is small enough, includes it in the response as type `ItemSet` with all `SyncID`s.
If the subrange is too large, includes it in the response as type `Fingerprint`.
- If the received range is of type `ItemSet`, compares it to the local items in the corresponding range
- If there are any differences between the local and remote items, adds these as part of the output of the `reconciliation` procedure.
At this point, the syncing peers MAY start to exchange the full messages corresponding to differences using the `transfer` protocol.
- If the received `ItemSet` is _not_ marked as `reconciled` by the remote peer, includes the corresponding local range in the response as type `ItemSet`.
- If the received `ItemSet` is marked as `reconciled` by the remote peer, includes the corresponding local range in the response as type `Skip`.
3. If shards or cluster don't match:
- Responds with an empty payload
4. Delta encodes the response
5. Sends the response using libp2p length-prefixed encoding
This process continues until the syncing peer crafts an empty response,
i.e., when all ranges have been processed and reconciled by both syncing peers and there are no differences left.
