What problem set is the Minisketch library designed for? What is it currently used for and what could it be used for in future?

Question

What problem set is the Minisketch library designed for? What is it currently used for and what could it be used for in future?

Answer 1

libminisketch is a library implementing the PinSketch set reconciliation algorithm and was covered in this Bitcoin Core PR review club. In theory it could be used for any problem where you have two sets of data and want to work out how those data sets differ (which specific elements are present in one but missing in another) as efficiently as possible.

The primary use case for Minisketch at the time of writing (February 2021) is Erlay on Bitcoin.

Erlay is a proposal for more bandwidth efficient transaction relay in Bitcoin and was covered in this Bitcoin Core PR review club. The Minisketch library is used in Erlay for set reconciliation between peers (peers generally have slightly different sets of transactions in their individual mempools).

There is also potentially a Lightning use case for Minisketch which was described by Rusty Russell in this lightning-dev mailing list post. Lightning nodes exchange gossip messages in an attempt to understand the topology of the network (nodes and channel sizes). They use this understanding to construct a route for a payment to a specific destination. This idea has not been implemented at the time of writing (February 2021). More centralized solutions such as LN-sync are currently used to address this problem.

There are also potential use cases unrelated to Bitcoin for Minisketch too. Pieter Wuille stated on IRC:

One of the most deployed uses of efficient set reconciliation algorithms is in the way PGP keyservers synchronize (or at least used to); that's using cpisync (an earlier algorithm before pinsketch was invented, which has far worse performance)

For additional possible applications of Minisketch see the Applications section of the README.