SETU — Peer to peer set unions

The SETU service implements efficient set union operations between two peers over a CADET tunnel. Elements of a set consist of an element type and arbitrary binary data. The size of an element’s data is limited to around 62 KB.

Union Sets

Sets created by a local client can be modified (by adding additional elements) and reused for multiple operations. If elements are to be removed, a fresh set must be created by the client.

Set Union Modifications

Even when set operations are active, one can add elements to a set. However, these changes will only be visible to operations that have been created after the changes have taken place. That is, every set operation only sees a snapshot of the set from the time the operation was started. This mechanism is not implemented by copying the whole set, but by attaching generation information to each element and operation.

Set Union Operations

Set operations can be started in two ways: Either by accepting an operation request from a remote peer, or by requesting a set operation from a remote peer. Set operations are uniquely identified by the involved peers, an application id and the operation type.

The client is notified of incoming set operations by set listeners. A set listener listens for incoming operations of a specific operation type and application id. Once notified of an incoming set request, the client can accept the set request (providing a local set for the operation) or reject it.

Union Result Elements

The SET service has three result modes that determine how an operation’s result set is delivered to the client:

• Locally added Elements. Elements that are in the union but not already in the local peer’s set are returned.

• Remote added Elements. Additionally, notify the client if the remote peer lacked some elements and thus also return to the local client those elements that we are sending to the remote peer to be added to its union. Obtaining these elements requires setting the GNUNET_SETU_OPTION_SYMMETRIC option.

libgnunetsetu libgnunetsetu ————-

Union Set API

New sets are created with GNUNET_SETU_create. Only the local peer’s configuration (as each set has its own client connection) must be provided. The set exists until either the client calls GNUNET_SETU_destroy or the client’s connection to the service is disrupted. In the latter case, the client is notified by the return value of functions dealing with sets. This return value must always be checked.

Elements are added with GNUNET_SETU_add_element.

Union Listeners

Listeners are created with GNUNET_SETU_listen. Each time time a remote peer suggests a set operation with an application id and operation type matching a listener, the listener’s callback is invoked. The client then must synchronously call either GNUNET_SETU_accept or GNUNET_SETU_reject. Note that the operation will not be started until the client calls GNUNET_SETU_commit (see Section "Supplying a Set").

Union Operations

Operations to be initiated by the local peer are created with GNUNET_SETU_prepare. Note that the operation will not be started until the client calls GNUNET_SETU_commit (see Section "Supplying a Set").

Supplying a Set for Union

To create symmetry between the two ways of starting a set operation (accepting and initiating it), the operation handles returned by GNUNET_SETU_accept and GNUNET_SETU_prepare do not yet have a set to operate on, thus they can not do any work yet.

The client must call GNUNET_SETU_commit to specify a set to use for an operation. GNUNET_SETU_commit may only be called once per set operation.

The Union Result Callback

Clients must specify both a result mode and a result callback with GNUNET_SETU_accept and GNUNET_SETU_prepare. The result callback with a status indicating either that an element was received, transmitted to the other peer (if this information was requested), or if the operation failed or ultimately succeeded.

The SETU Client-Service Protocol

Creating Union Sets

For each set of a client, there exists a client connection to the service. Sets are created by sending the GNUNET_SERVICE_SETU_CREATE message over a new client connection. Multiple operations for one set are multiplexed over one client connection, using a request id supplied by the client.

Listeners for Union

Each listener also requires a separate client connection. By sending the GNUNET_SERVICE_SETU_LISTEN message, the client notifies the service of the application id and operation type it is interested in. A client rejects an incoming request by sending GNUNET_SERVICE_SETU_REJECT on the listener’s client connection. In contrast, when accepting an incoming request, a GNUNET_SERVICE_SETU_ACCEPT message must be sent over the set that is supplied for the set operation.

Initiating Union Operations

Operations with remote peers are initiated by sending a GNUNET_SERVICE_SETU_EVALUATE message to the service. The client connection that this message is sent by determines the set to use.

Modifying Union Sets

Sets are modified with the GNUNET_SERVICE_SETU_ADD message.

Union Results and Operation Status

The service notifies the client of result elements and success/failure of a set operation with the GNUNET_SERVICE_SETU_RESULT message.

The SETU Union Peer-to-Peer Protocol

The SET union protocol is based on Eppstein’s efficient set reconciliation without prior context. You should read this paper first if you want to understand the protocol.

Todo

Link to Eppstein’s paper!

The union protocol operates over CADET and starts with a GNUNET_MESSAGE_TYPE_SETU_P2P_OPERATION_REQUEST being sent by the peer initiating the operation to the peer listening for inbound requests. It includes the number of elements of the initiating peer, which is currently not used.

The listening peer checks if the operation type and application identifier are acceptable for its current state. If not, it responds with a GNUNET_MESSAGE_TYPE_SETU_RESULT and a status of GNUNET_SETU_STATUS_FAILURE (and terminates the CADET channel).

If the application accepts the request, it sends back a strata estimator using a message of type GNUNET_MESSAGE_TYPE_SETU_P2P_SE. The initiator evaluates the strata estimator and initiates the exchange of invertible Bloom filters, sending a GNUNET_MESSAGE_TYPE_SETU_P2P_IBF.

During the IBF exchange, if the receiver cannot invert the Bloom filter or detects a cycle, it sends a larger IBF in response (up to a defined maximum limit; if that limit is reached, the operation fails). Elements decoded while processing the IBF are transmitted to the other peer using GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENTS, or requested from the other peer using GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENT_REQUESTS messages, depending on the sign observed during decoding of the IBF. Peers respond to a GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENT_REQUESTS message with the respective element in a GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENTS message. If the IBF fully decodes, the peer responds with a GNUNET_MESSAGE_TYPE_SETU_P2P_DONE message instead of another GNUNET_MESSAGE_TYPE_SETU_P2P_IBF.

All Bloom filter operations use a salt to mingle keys before hashing them into buckets, such that future iterations have a fresh chance of succeeding if they failed due to collisions before.