From 6531e03875f8b3dba0eface2ac8ea195e9a80d86 Mon Sep 17 00:00:00 2001 From: Christian Grothoff Date: Wed, 19 Aug 2020 13:17:01 +0200 Subject: break out chapters on SETI and SETUI from SET chapter --- doc/handbook/chapters/developer.texi | 522 ++++++++++++++++++++++++++++++++++- 1 file changed, 520 insertions(+), 2 deletions(-) diff --git a/doc/handbook/chapters/developer.texi b/doc/handbook/chapters/developer.texi index 6d8ddd3c2..0ff222f25 100644 --- a/doc/handbook/chapters/developer.texi +++ b/doc/handbook/chapters/developer.texi @@ -71,6 +71,8 @@ new chapters, sections or insightful comments. * PEERINFO Subsystem:: * PEERSTORE Subsystem:: * SET Subsystem:: +* SETI Subsystem:: +* SETU Subsystem:: * STATISTICS Subsystem:: * Distributed Hash Table (DHT):: * GNU Name System (GNS):: @@ -6535,10 +6537,13 @@ destroyed as well. @node SET Subsystem @section SET Subsystem - +The SET subsystem is in process of being replaced by the SETU and +SETI subsystems, which provide basically the same functionality, +just using two different subsystems. SETI and SETU should be used +for new code. The SET service implements efficient set operations between two peers -over a mesh tunnel. +over a CADET tunnel. Currently, set union and set intersection are the only supported operations. Elements of a set consist of an @emph{element type} and arbitrary binary @emph{data}. @@ -6907,6 +6912,519 @@ 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. + + + + + + + +@cindex SETI Subsystem +@node SETI Subsystem +@section SETI Subsystem + +The SET service implements efficient set intersection between two peers +over a CADET tunnel. +Elements of a set consist of an @emph{element type} and +arbitrary binary @emph{data}. +The size of an element's data is limited to around 62 KB. + +@menu +* Local Sets:: +* Set Modifications:: +* Set Operations:: +* Result Elements:: +* libgnunetseti:: +* The SET Client-Service Protocol:: +* The SET Intersection Peer-to-Peer Protocol:: +@end menu + +@node Local Sets +@subsection Local 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. + +@node Set Modifications +@subsection Set 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 @emph{not} implemented by copying the whole set, but by +attaching @emph{generation information} to each element and operation. + +@node Set Operations +@subsection Set 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 @emph{peers}, an +@emph{application id} and the @emph{operation type}. + +The client is notified of incoming set operations by @emph{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. + +@node Result Elements +@subsection Result Elements + +The SET service has two @emph{result modes} that determine how an +operation's result set is delivered to the client: + +@itemize @bullet +@item @strong{Return intersection.} All elements of set resulting from the set +intersection are returned to the client. +@item @strong{Removed Elements.} Only elements that are in the local +peer's initial set but not in the intersection are returned. +@end itemize + +@cindex libgnunetseti +@node libgnunetseti +@subsection libgnunetseti + +@menu +* Sets:: +* Listeners:: +* Operations:: +* Supplying a Set:: +* The Result Callback:: +@end menu + +@node Sets +@subsubsection Sets + +New sets are created with @code{GNUNET_SETI_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 @code{GNUNET_SET_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 @code{GNUNET_SET_add_element}. + +@node Listeners +@subsubsection Listeners + +Listeners are created with @code{GNUNET_SET_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 @code{GNUNET_SET_accept} +or @code{GNUNET_SET_reject}. Note that the operation will not be started +until the client calls @code{GNUNET_SET_commit} +(see Section "Supplying a Set"). + +@node Operations +@subsubsection Operations + +Operations to be initiated by the local peer are created with +@code{GNUNET_SET_prepare}. Note that the operation will not be started +until the client calls @code{GNUNET_SET_commit} +(see Section "Supplying a Set"). + +@node Supplying a Set +@subsubsection Supplying a Set + +To create symmetry between the two ways of starting a set operation +(accepting and initiating it), the operation handles returned by +@code{GNUNET_SET_accept} and @code{GNUNET_SET_prepare} do not yet have a +set to operate on, thus they can not do any work yet. + +The client must call @code{GNUNET_SET_commit} to specify a set to use for +an operation. @code{GNUNET_SET_commit} may only be called once per set +operation. + +@node The Result Callback +@subsubsection The Result Callback + +Clients must specify both a result mode and a result callback with +@code{GNUNET_SET_accept} and @code{GNUNET_SET_prepare}. The result +callback with a status indicating either that an element was received, or +the operation failed or succeeded. +The interpretation of the received element depends on the result mode. +The callback needs to know which result mode it is used in, as the +arguments do not indicate if an element is part of the full result set, +or if it is in the difference between the original set and the final set. + +@node The SETI Client-Service Protocol +@subsection The SETI Client-Service Protocol + +@menu +* Creating Sets:: +* Listeners2:: +* Initiating Operations:: +* Modifying Sets:: +* Results and Operation Status:: +@end menu + +@node Creating Sets +@subsubsection Creating Sets + +For each set of a client, there exists a client connection to the service. +Sets are created by sending the @code{GNUNET_SERVICE_SETI_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. + +@node Listeners2 +@subsubsection Listeners2 + + + +Each listener also requires a seperate client connection. By sending the +@code{GNUNET_SERVICE_SETI_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 @code{GNUNET_SERVICE_SETI_REJECT} +on the listener's client connection. +In contrast, when accepting an incoming request, a +@code{GNUNET_SERVICE_SETI_ACCEPT} message must be sent over the@ set that +is supplied for the set operation. + +@node Initiating Operations +@subsubsection Initiating Operations + +Operations with remote peers are initiated by sending a +@code{GNUNET_SERVICE_SETI_EVALUATE} message to the service. The@ client +connection that this message is sent by determines the set to use. + +@node Modifying Sets +@subsubsection Modifying Sets + +Sets are modified with the @code{GNUNET_SERVICE_SETI_ADD} message. + + +@c %@menu +@c %* Results and Operation Status:: +@c %* Iterating Sets:: +@c %@end menu + +@node Results and Operation Status +@subsubsection Results and Operation Status + +The service notifies the client of result elements and success/failure of +a set operation with the @code{GNUNET_SERVICE_SETI_RESULT} message. + +@node The SET Intersection Peer-to-Peer Protocol +@subsection The SET Intersection Peer-to-Peer Protocol + +The intersection protocol operates over CADET and starts with a +GNUNET_MESSAGE_TYPE_SETI_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 used +to decide which side will send a Bloom filter first. + +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_SETI_RESULT and a status of +GNUNET_SETI_STATUS_FAILURE (and terminates the CADET channel). + +If the application accepts the request, the listener sends back a +@code{GNUNET_MESSAGE_TYPE_SETI_P2P_ELEMENT_INFO} if it has +more elements in the set than the client. +Otherwise, it immediately starts with the Bloom filter exchange. +If the initiator receives a +@code{GNUNET_MESSAGE_TYPE_SETI_P2P_ELEMENT_INFO} response, +it beings the Bloom filter exchange, unless the set size is indicated to +be zero, in which case the intersection is considered finished after +just the initial handshake. + + +@menu +* The Bloom filter exchange:: +* Salt:: +@end menu + +@node The Bloom filter exchange +@subsubsection The Bloom filter exchange + +In this phase, each peer transmits a Bloom filter over the remaining +keys of the local set to the other peer using a +@code{GNUNET_MESSAGE_TYPE_SETI_P2P_BF} message. This +message additionally includes the number of elements left in the sender's +set, as well as the XOR over all of the keys in that set. + +The number of bits 'k' set per element in the Bloom filter is calculated +based on the relative size of the two sets. +Furthermore, the size of the Bloom filter is calculated based on 'k' and +the number of elements in the set to maximize the amount of data filtered +per byte transmitted on the wire (while avoiding an excessively high +number of iterations). + +The receiver of the message removes all elements from its local set that +do not pass the Bloom filter test. +It then checks if the set size of the sender and the XOR over the keys +match what is left of its own set. If they do, it sends a +@code{GNUNET_MESSAGE_TYPE_SETI_P2P_DONE} back to indicate +that the latest set is the final result. +Otherwise, the receiver starts another Bloom filter exchange, except +this time as the sender. + +@node Salt +@subsubsection Salt + +Bloomfilter operations are probabilistic: With some non-zero probability +the test may incorrectly say an element is in the set, even though it is +not. + +To mitigate this problem, the intersection protocol iterates exchanging +Bloom filters using a different random 32-bit salt in each iteration (the +salt is also included in the message). +With different salts, set operations may fail for different elements. +Merging the results from the executions, the probability of failure drops +to zero. + +The iterations terminate once both peers have established that they have +sets of the same size, and where the XOR over all keys computes the same +512-bit value (leaving a failure probability of 2-511). + + +@cindex SETU Subsystem +@node SETU Subsystem +@section SETU Subsystem + +The SETU service implements efficient set union operations between two peers +over a CADET tunnel. Elements of a set consist of an @emph{element type} and +arbitrary binary @emph{data}. The size of an element's data is limited to +around 62 KB. + +@menu +* Local Sets:: +* Set Modifications:: +* Set Operations:: +* Result Elements:: +* libgnunetset:: +* The SET Client-Service Protocol:: +* The SET Intersection Peer-to-Peer Protocol:: +* The SET Union Peer-to-Peer Protocol:: +@end menu + +@node Local Sets +@subsection Local 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. + +@node Set Modifications +@subsection Set 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 @emph{not} implemented by copying the whole set, but by +attaching @emph{generation information} to each element and operation. + +@node Set Operations +@subsection Set 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 @emph{peers}, an +@emph{application id} and the @emph{operation type}. + +The client is notified of incoming set operations by @emph{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. + +@node Result Elements +@subsection Result Elements + +The SET service has three @emph{result modes} that determine how an +operation's result set is delivered to the client: + +@itemize @bullet +@item @strong{Locally added Elements.} Elements that are in the union +but not already in the local peer's set are returned. +@item @strong{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 @code{GNUNET_SETU_OPTION_SYMMETRIC} option. +@end itemize + +@cindex libgnunetsetu +@node libgnunetsetu +@subsection libgnunetsetu + +@menu +* Sets:: +* Listeners:: +* Operations:: +* Supplying a Set:: +* The Result Callback:: +@end menu + +@node Sets +@subsubsection Sets + +New sets are created with @code{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 @code{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 @code{GNUNET_SETU_add_element}. + +@node Listeners +@subsubsection Listeners + +Listeners are created with @code{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 @code{GNUNET_SETU_accept} +or @code{GNUNET_SETU_reject}. Note that the operation will not be started +until the client calls @code{GNUNET_SETU_commit} +(see Section "Supplying a Set"). + +@node Operations +@subsubsection Operations + +Operations to be initiated by the local peer are created with +@code{GNUNET_SETU_prepare}. Note that the operation will not be started +until the client calls @code{GNUNET_SETU_commit} +(see Section "Supplying a Set"). + +@node Supplying a Set +@subsubsection Supplying a Set + +To create symmetry between the two ways of starting a set operation +(accepting and initiating it), the operation handles returned by +@code{GNUNET_SETU_accept} and @code{GNUNET_SETU_prepare} do not yet have a +set to operate on, thus they can not do any work yet. + +The client must call @code{GNUNET_SETU_commit} to specify a set to use for +an operation. @code{GNUNET_SETU_commit} may only be called once per set +operation. + +@node The Result Callback +@subsubsection The Result Callback + +Clients must specify both a result mode and a result callback with +@code{GNUNET_SETU_accept} and @code{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. + +@node The SETU Client-Service Protocol +@subsection The SETU Client-Service Protocol + +@menu +* Creating Sets:: +* Listeners2:: +* Initiating Operations:: +* Modifying Sets:: +* Results and Operation Status:: +* Iterating Sets:: +@end menu + +@node Creating Sets +@subsubsection Creating Sets + +For each set of a client, there exists a client connection to the service. +Sets are created by sending the @code{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. + +@node Listeners2 +@subsubsection Listeners2 + +Each listener also requires a seperate client connection. By sending the +@code{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 @code{GNUNET_SERVICE_SETU_REJECT} +on the listener's client connection. +In contrast, when accepting an incoming request, a +@code{GNUNET_SERVICE_SETU_ACCEPT} message must be sent over the@ set that +is supplied for the set operation. + +@node Initiating Operations +@subsubsection Initiating Operations + + + +Operations with remote peers are initiated by sending a +@code{GNUNET_SERVICE_SETU_EVALUATE} message to the service. The@ client +connection that this message is sent by determines the set to use. + +@node Modifying Sets +@subsubsection Modifying Sets + + + +Sets are modified with the @code{GNUNET_SERVICE_SETU_ADD} message. + + +@c %@menu +@c %* Results and Operation Status:: +@c %* Iterating Sets:: +@c %@end menu + +@node Results and Operation Status +@subsubsection Results and Operation Status + +The service notifies the client of result elements and success/failure of +a set operation with the @code{GNUNET_SERVICE_SETU_RESULT} message. + + +@node The SET Union Peer-to-Peer Protocol +@subsection The SET 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. + +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 @code{GNUNET_MESSAGE_TYPE_SETU_RESULT} and a status of +@code{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. + + + + + + @cindex STATISTICS Subsystem @node STATISTICS Subsystem @section STATISTICS Subsystem -- cgit v1.2.3