Minisketch

Minisketch uses finite field arithmetic over $GF(2^b)$ to map data entries to field elements. The process follows these mathematical steps:

1. Mapping Data to Field Elements

Every integer in the range $[1...2^b-1]$ is mapped to a nonzero field element of $GF(2^b)$. Addition in this field corresponds to bitwise XOR.

2. Representing Sets as Power Series

Sets are treated as formal power series $S(M)$. For a set $M = {m_1, m_2, \dots}$, the series is the sum of individual element series: $S(M) = \sum S(m_i)$. Because field addition is XOR, $S(a) + S(a) = 0$, which enables the symmetric difference property.

3. Sketch Construction

A sketch is constructed using the first $2n$ coefficients of the power series $S(M)$. Specifically, the sketch is the list of sums of powers: $[m_1 + m_2 + \dots, m_1^2 + m_2^2 + \dots, \dots, m_1^{2n} + m_2^{2n} + \dots]$.

4. Element Recovery (Decoding)

To recover elements from a sketch of size $n$:

1. Solve for Polynomial $L$: Use the coefficients of the sketch to set up $n$ linear equations. These equations are solved (typically via Gaussian elimination or the Berlekamp-Massey algorithm) to find the coefficients $l_i$ of a polynomial $L$.
2. Find Roots: Find the roots of $L$.
3. Invert Roots: The set elements $m_i$ are the inverses of the roots of $L$. To avoid expensive inversion operations, one can instead factor the polynomial $L$ with its coefficients in reverse order.

5. Handling Unknown Set Sizes

If the exact number of elements $n$ is unknown but an upper bound (capacity $c$) is provided, the Peterson-Gorenstein-Zierler algorithm is used. This involves attempting to solve the equations by counting down from $c$ until a valid solution is found.

Set reconciliation is performed by merging two sketches.

1. Create two sketches representing two different sets (e.g., sketch_a and sketch_b).
2. Serialize sketch_a and send it to the holder of sketch_b.
3. The receiver deserializes sketch_a and calls minisketch_merge(sketch_b, sketch_a).
4. The resulting sketch_b now contains the symmetric difference: elements that appeared in exactly one of the two original sets.
5. Use minisketch_decode to extract the actual differing elements from the merged sketch.

// 1. Merge Alice's sketch into Bob's sketch
minisketch_merge(sketch_b, sketch_a);

// 2. Decode the differences
uint64_t differences[4];
ssize_t num_differences = minisketch_decode(sketch_b, 4, differences);

if (num_differences < 0) {
  // Error: more differences than the capacity 'c' allowed
  printf("More than 4 differences!\n");
} else {
  for (ssize_t i = 0; i < num_differences; ++i) {
    printf("%lu is in only one of the two sets\n", differences[i]);
  }
}

Minisketch employs several mathematical optimizations to improve performance and reduce data size:

• Sketch Size Reduction (Halving): By utilizing the Frobenius endomorphism ($(x + y)^2 = x^2 + y^2$ in fields where $x + x = 0$), only the odd terms of the power series ($s_1, s_3, s_5, \dots, s_{2n-1}$) need to be transmitted. The even terms can be reconstructed locally, reducing the sketch size to $c$ field elements.
• Quadratic Complexity: Instead of using $O(n^3)$ Gaussian elimination, the Berlekamp-Massey (BM) algorithm can solve the coefficient equations in $O(n^2)$ time.
• Root-finding vs. Factorization: Rather than performing full polynomial factorization, the implementation uses efficient root-finding algorithms. Since the set elements are the inverses of the roots of the polynomial $L$, finding roots is more direct.
• Avoiding Inversions: To bypass expensive field inversion operations, the implementation can factor the polynomial $L$ with its coefficients in reverse order, which directly yields the set elements as roots.

Since the exact number of differences is often unknown, consider these strategies for managing sketch size and communication:

• Overestimation: Always overestimate the required sketch size to amortize communication overheads like packet headers and round-trip delays.
• Incremental Sending: Send elements for a sketch one at a time. This is most easily implemented by computing the largest possible sketch size and sending it incrementally as needed.
• Adaptive Subdivision (Recursive Decoding): If a sketch is overfull, you can adaptively subdivide the set. The sender uses a hash function to select approximately half the set members and sends a sketch of them. The receiver does the same. This allows the receiver to combine the results into two smaller sketches. This process can be repeated recursively on failure, making decode time essentially linear at the cost of communication efficiency.
• Fallback to Full Set: If the total data sent exceeds the cost of sending the whole set, you can send the full set in response to a failure. To save bandwidth, omit as many elements as the size of the previously sent sketch; the receiver can then decode the partial set and use existing data to complete it.

To reconcile two sets (Alice and Bob) using libminisketch, follow this protocol:

1. Compute Sketches: Alice and Bob both compute a sketch of their respective set elements.
2. Exchange: Alice sends her sketch to Bob.
3. Combine: Bob XORs the two sketches to obtain a sketch of the symmetric difference.
4. Recover: Bob attempts to recover the elements from the difference sketch.
5. Sync: Bob sends every element found in the difference that he does not possess to Alice.

Success Condition: This protocol succeeds if the size of the symmetric difference (elements unique to Alice + elements unique to Bob) does not exceed the capacity of the sketch Alice sent.

Note on Large Elements: If elements are large, it is more efficient to compute sketches over hashes of the elements. In this case, Bob sends the hashes of the missing elements to Alice, and Alice responds with the actual requested elements.