aboutsummaryrefslogtreecommitdiff
path: root/doc/handbook
diff options
context:
space:
mode:
authorChristian Grothoff <christian@grothoff.org>2020-08-19 13:17:01 +0200
committerChristian Grothoff <christian@grothoff.org>2020-08-19 13:17:01 +0200
commit6531e03875f8b3dba0eface2ac8ea195e9a80d86 (patch)
tree40cb1bc17372f67679d8cc767f8557f6748b4db8 /doc/handbook
parent6c1e93877194aa2c0cbd50a3636a1532dd521e3b (diff)
downloadgnunet-6531e03875f8b3dba0eface2ac8ea195e9a80d86.tar.gz
gnunet-6531e03875f8b3dba0eface2ac8ea195e9a80d86.zip
break out chapters on SETI and SETUI from SET chapter
Diffstat (limited to 'doc/handbook')
-rw-r--r--doc/handbook/chapters/developer.texi522
1 files 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.
71* PEERINFO Subsystem:: 71* PEERINFO Subsystem::
72* PEERSTORE Subsystem:: 72* PEERSTORE Subsystem::
73* SET Subsystem:: 73* SET Subsystem::
74* SETI Subsystem::
75* SETU Subsystem::
74* STATISTICS Subsystem:: 76* STATISTICS Subsystem::
75* Distributed Hash Table (DHT):: 77* Distributed Hash Table (DHT)::
76* GNU Name System (GNS):: 78* GNU Name System (GNS)::
@@ -6535,10 +6537,13 @@ destroyed as well.
6535@node SET Subsystem 6537@node SET Subsystem
6536@section SET Subsystem 6538@section SET Subsystem
6537 6539
6538 6540The SET subsystem is in process of being replaced by the SETU and
6541SETI subsystems, which provide basically the same functionality,
6542just using two different subsystems. SETI and SETU should be used
6543for new code.
6539 6544
6540The SET service implements efficient set operations between two peers 6545The SET service implements efficient set operations between two peers
6541over a mesh tunnel. 6546over a CADET tunnel.
6542Currently, set union and set intersection are the only supported 6547Currently, set union and set intersection are the only supported
6543operations. Elements of a set consist of an @emph{element type} and 6548operations. Elements of a set consist of an @emph{element type} and
6544arbitrary binary @emph{data}. 6549arbitrary binary @emph{data}.
@@ -6907,6 +6912,519 @@ All Bloom filter operations use a salt to mingle keys before hashing them
6907into buckets, such that future iterations have a fresh chance of 6912into buckets, such that future iterations have a fresh chance of
6908succeeding if they failed due to collisions before. 6913succeeding if they failed due to collisions before.
6909 6914
6915
6916
6917
6918
6919
6920
6921
6922@cindex SETI Subsystem
6923@node SETI Subsystem
6924@section SETI Subsystem
6925
6926The SET service implements efficient set intersection between two peers
6927over a CADET tunnel.
6928Elements of a set consist of an @emph{element type} and
6929arbitrary binary @emph{data}.
6930The size of an element's data is limited to around 62 KB.
6931
6932@menu
6933* Local Sets::
6934* Set Modifications::
6935* Set Operations::
6936* Result Elements::
6937* libgnunetseti::
6938* The SET Client-Service Protocol::
6939* The SET Intersection Peer-to-Peer Protocol::
6940@end menu
6941
6942@node Local Sets
6943@subsection Local Sets
6944
6945Sets created by a local client can be modified (by adding additional elements)
6946and reused for multiple operations. If elements are to be removed, a fresh
6947set must be created by the client.
6948
6949@node Set Modifications
6950@subsection Set Modifications
6951
6952Even when set operations are active, one can add elements
6953to a set.
6954However, these changes will only be visible to operations that have been
6955created after the changes have taken place. That is, every set operation
6956only sees a snapshot of the set from the time the operation was started.
6957This mechanism is @emph{not} implemented by copying the whole set, but by
6958attaching @emph{generation information} to each element and operation.
6959
6960@node Set Operations
6961@subsection Set Operations
6962
6963Set operations can be started in two ways: Either by accepting an
6964operation request from a remote peer, or by requesting a set operation
6965from a remote peer.
6966Set operations are uniquely identified by the involved @emph{peers}, an
6967@emph{application id} and the @emph{operation type}.
6968
6969The client is notified of incoming set operations by @emph{set listeners}.
6970A set listener listens for incoming operations of a specific operation
6971type and application id.
6972Once notified of an incoming set request, the client can accept the set
6973request (providing a local set for the operation) or reject it.
6974
6975@node Result Elements
6976@subsection Result Elements
6977
6978The SET service has two @emph{result modes} that determine how an
6979operation's result set is delivered to the client:
6980
6981@itemize @bullet
6982@item @strong{Return intersection.} All elements of set resulting from the set
6983intersection are returned to the client.
6984@item @strong{Removed Elements.} Only elements that are in the local
6985peer's initial set but not in the intersection are returned.
6986@end itemize
6987
6988@cindex libgnunetseti
6989@node libgnunetseti
6990@subsection libgnunetseti
6991
6992@menu
6993* Sets::
6994* Listeners::
6995* Operations::
6996* Supplying a Set::
6997* The Result Callback::
6998@end menu
6999
7000@node Sets
7001@subsubsection Sets
7002
7003New sets are created with @code{GNUNET_SETI_create}. Only the local peer's
7004configuration (as each set has its own client connection) must be provided.
7005The set exists until either the client calls @code{GNUNET_SET_destroy} or
7006the client's connection to the service is disrupted.
7007In the latter case, the client is notified by the return value of
7008functions dealing with sets. This return value must always be checked.
7009
7010Elements are added with @code{GNUNET_SET_add_element}.
7011
7012@node Listeners
7013@subsubsection Listeners
7014
7015Listeners are created with @code{GNUNET_SET_listen}. Each time time a
7016remote peer suggests a set operation with an application id and operation
7017type matching a listener, the listener's callback is invoked.
7018The client then must synchronously call either @code{GNUNET_SET_accept}
7019or @code{GNUNET_SET_reject}. Note that the operation will not be started
7020until the client calls @code{GNUNET_SET_commit}
7021(see Section "Supplying a Set").
7022
7023@node Operations
7024@subsubsection Operations
7025
7026Operations to be initiated by the local peer are created with
7027@code{GNUNET_SET_prepare}. Note that the operation will not be started
7028until the client calls @code{GNUNET_SET_commit}
7029(see Section "Supplying a Set").
7030
7031@node Supplying a Set
7032@subsubsection Supplying a Set
7033
7034To create symmetry between the two ways of starting a set operation
7035(accepting and initiating it), the operation handles returned by
7036@code{GNUNET_SET_accept} and @code{GNUNET_SET_prepare} do not yet have a
7037set to operate on, thus they can not do any work yet.
7038
7039The client must call @code{GNUNET_SET_commit} to specify a set to use for
7040an operation. @code{GNUNET_SET_commit} may only be called once per set
7041operation.
7042
7043@node The Result Callback
7044@subsubsection The Result Callback
7045
7046Clients must specify both a result mode and a result callback with
7047@code{GNUNET_SET_accept} and @code{GNUNET_SET_prepare}. The result
7048callback with a status indicating either that an element was received, or
7049the operation failed or succeeded.
7050The interpretation of the received element depends on the result mode.
7051The callback needs to know which result mode it is used in, as the
7052arguments do not indicate if an element is part of the full result set,
7053or if it is in the difference between the original set and the final set.
7054
7055@node The SETI Client-Service Protocol
7056@subsection The SETI Client-Service Protocol
7057
7058@menu
7059* Creating Sets::
7060* Listeners2::
7061* Initiating Operations::
7062* Modifying Sets::
7063* Results and Operation Status::
7064@end menu
7065
7066@node Creating Sets
7067@subsubsection Creating Sets
7068
7069For each set of a client, there exists a client connection to the service.
7070Sets are created by sending the @code{GNUNET_SERVICE_SETI_CREATE} message
7071over a new client connection. Multiple operations for one set are
7072multiplexed over one client connection, using a request id supplied by
7073the client.
7074
7075@node Listeners2
7076@subsubsection Listeners2
7077
7078
7079
7080Each listener also requires a seperate client connection. By sending the
7081@code{GNUNET_SERVICE_SETI_LISTEN} message, the client notifies the service
7082of the application id and operation type it is interested in. A client
7083rejects an incoming request by sending @code{GNUNET_SERVICE_SETI_REJECT}
7084on the listener's client connection.
7085In contrast, when accepting an incoming request, a
7086@code{GNUNET_SERVICE_SETI_ACCEPT} message must be sent over the@ set that
7087is supplied for the set operation.
7088
7089@node Initiating Operations
7090@subsubsection Initiating Operations
7091
7092Operations with remote peers are initiated by sending a
7093@code{GNUNET_SERVICE_SETI_EVALUATE} message to the service. The@ client
7094connection that this message is sent by determines the set to use.
7095
7096@node Modifying Sets
7097@subsubsection Modifying Sets
7098
7099Sets are modified with the @code{GNUNET_SERVICE_SETI_ADD} message.
7100
7101
7102@c %@menu
7103@c %* Results and Operation Status::
7104@c %* Iterating Sets::
7105@c %@end menu
7106
7107@node Results and Operation Status
7108@subsubsection Results and Operation Status
7109
7110The service notifies the client of result elements and success/failure of
7111a set operation with the @code{GNUNET_SERVICE_SETI_RESULT} message.
7112
7113@node The SET Intersection Peer-to-Peer Protocol
7114@subsection The SET Intersection Peer-to-Peer Protocol
7115
7116The intersection protocol operates over CADET and starts with a
7117GNUNET_MESSAGE_TYPE_SETI_P2P_OPERATION_REQUEST being sent by the peer
7118initiating the operation to the peer listening for inbound requests.
7119It includes the number of elements of the initiating peer, which is used
7120to decide which side will send a Bloom filter first.
7121
7122The listening peer checks if the operation type and application
7123identifier are acceptable for its current state.
7124If not, it responds with a GNUNET_MESSAGE_TYPE_SETI_RESULT and a status of
7125GNUNET_SETI_STATUS_FAILURE (and terminates the CADET channel).
7126
7127If the application accepts the request, the listener sends back a
7128@code{GNUNET_MESSAGE_TYPE_SETI_P2P_ELEMENT_INFO} if it has
7129more elements in the set than the client.
7130Otherwise, it immediately starts with the Bloom filter exchange.
7131If the initiator receives a
7132@code{GNUNET_MESSAGE_TYPE_SETI_P2P_ELEMENT_INFO} response,
7133it beings the Bloom filter exchange, unless the set size is indicated to
7134be zero, in which case the intersection is considered finished after
7135just the initial handshake.
7136
7137
7138@menu
7139* The Bloom filter exchange::
7140* Salt::
7141@end menu
7142
7143@node The Bloom filter exchange
7144@subsubsection The Bloom filter exchange
7145
7146In this phase, each peer transmits a Bloom filter over the remaining
7147keys of the local set to the other peer using a
7148@code{GNUNET_MESSAGE_TYPE_SETI_P2P_BF} message. This
7149message additionally includes the number of elements left in the sender's
7150set, as well as the XOR over all of the keys in that set.
7151
7152The number of bits 'k' set per element in the Bloom filter is calculated
7153based on the relative size of the two sets.
7154Furthermore, the size of the Bloom filter is calculated based on 'k' and
7155the number of elements in the set to maximize the amount of data filtered
7156per byte transmitted on the wire (while avoiding an excessively high
7157number of iterations).
7158
7159The receiver of the message removes all elements from its local set that
7160do not pass the Bloom filter test.
7161It then checks if the set size of the sender and the XOR over the keys
7162match what is left of its own set. If they do, it sends a
7163@code{GNUNET_MESSAGE_TYPE_SETI_P2P_DONE} back to indicate
7164that the latest set is the final result.
7165Otherwise, the receiver starts another Bloom filter exchange, except
7166this time as the sender.
7167
7168@node Salt
7169@subsubsection Salt
7170
7171Bloomfilter operations are probabilistic: With some non-zero probability
7172the test may incorrectly say an element is in the set, even though it is
7173not.
7174
7175To mitigate this problem, the intersection protocol iterates exchanging
7176Bloom filters using a different random 32-bit salt in each iteration (the
7177salt is also included in the message).
7178With different salts, set operations may fail for different elements.
7179Merging the results from the executions, the probability of failure drops
7180to zero.
7181
7182The iterations terminate once both peers have established that they have
7183sets of the same size, and where the XOR over all keys computes the same
7184512-bit value (leaving a failure probability of 2-511).
7185
7186
7187@cindex SETU Subsystem
7188@node SETU Subsystem
7189@section SETU Subsystem
7190
7191The SETU service implements efficient set union operations between two peers
7192over a CADET tunnel. Elements of a set consist of an @emph{element type} and
7193arbitrary binary @emph{data}. The size of an element's data is limited to
7194around 62 KB.
7195
7196@menu
7197* Local Sets::
7198* Set Modifications::
7199* Set Operations::
7200* Result Elements::
7201* libgnunetset::
7202* The SET Client-Service Protocol::
7203* The SET Intersection Peer-to-Peer Protocol::
7204* The SET Union Peer-to-Peer Protocol::
7205@end menu
7206
7207@node Local Sets
7208@subsection Local Sets
7209
7210Sets created by a local client can be modified (by adding additional elements)
7211and reused for multiple operations. If elements are to be removed, a fresh
7212set must be created by the client.
7213
7214@node Set Modifications
7215@subsection Set Modifications
7216
7217Even when set operations are active, one can add elements
7218to a set.
7219However, these changes will only be visible to operations that have been
7220created after the changes have taken place. That is, every set operation
7221only sees a snapshot of the set from the time the operation was started.
7222This mechanism is @emph{not} implemented by copying the whole set, but by
7223attaching @emph{generation information} to each element and operation.
7224
7225@node Set Operations
7226@subsection Set Operations
7227
7228Set operations can be started in two ways: Either by accepting an
7229operation request from a remote peer, or by requesting a set operation
7230from a remote peer.
7231Set operations are uniquely identified by the involved @emph{peers}, an
7232@emph{application id} and the @emph{operation type}.
7233
7234The client is notified of incoming set operations by @emph{set listeners}.
7235A set listener listens for incoming operations of a specific operation
7236type and application id.
7237Once notified of an incoming set request, the client can accept the set
7238request (providing a local set for the operation) or reject it.
7239
7240@node Result Elements
7241@subsection Result Elements
7242
7243The SET service has three @emph{result modes} that determine how an
7244operation's result set is delivered to the client:
7245
7246@itemize @bullet
7247@item @strong{Locally added Elements.} Elements that are in the union
7248but not already in the local peer's set are returned.
7249@item @strong{Remote added Elements.} Additionally, notify the client
7250if the remote peer lacked some elements and thus also return to the
7251local client those elements that we are sending to the remote peer to
7252be added to its union. Obtaining these elements requires setting
7253the @code{GNUNET_SETU_OPTION_SYMMETRIC} option.
7254@end itemize
7255
7256@cindex libgnunetsetu
7257@node libgnunetsetu
7258@subsection libgnunetsetu
7259
7260@menu
7261* Sets::
7262* Listeners::
7263* Operations::
7264* Supplying a Set::
7265* The Result Callback::
7266@end menu
7267
7268@node Sets
7269@subsubsection Sets
7270
7271New sets are created with @code{GNUNET_SETU_create}. Only the local peer's
7272configuration (as each set has its own client connection) must be provided.
7273The set exists until either the client calls @code{GNUNET_SETU_destroy} or
7274the client's connection to the service is disrupted.
7275In the latter case, the client is notified by the return value of
7276functions dealing with sets. This return value must always be checked.
7277
7278Elements are added with @code{GNUNET_SETU_add_element}.
7279
7280@node Listeners
7281@subsubsection Listeners
7282
7283Listeners are created with @code{GNUNET_SETU_listen}. Each time time a
7284remote peer suggests a set operation with an application id and operation
7285type matching a listener, the listener's callback is invoked.
7286The client then must synchronously call either @code{GNUNET_SETU_accept}
7287or @code{GNUNET_SETU_reject}. Note that the operation will not be started
7288until the client calls @code{GNUNET_SETU_commit}
7289(see Section "Supplying a Set").
7290
7291@node Operations
7292@subsubsection Operations
7293
7294Operations to be initiated by the local peer are created with
7295@code{GNUNET_SETU_prepare}. Note that the operation will not be started
7296until the client calls @code{GNUNET_SETU_commit}
7297(see Section "Supplying a Set").
7298
7299@node Supplying a Set
7300@subsubsection Supplying a Set
7301
7302To create symmetry between the two ways of starting a set operation
7303(accepting and initiating it), the operation handles returned by
7304@code{GNUNET_SETU_accept} and @code{GNUNET_SETU_prepare} do not yet have a
7305set to operate on, thus they can not do any work yet.
7306
7307The client must call @code{GNUNET_SETU_commit} to specify a set to use for
7308an operation. @code{GNUNET_SETU_commit} may only be called once per set
7309operation.
7310
7311@node The Result Callback
7312@subsubsection The Result Callback
7313
7314Clients must specify both a result mode and a result callback with
7315@code{GNUNET_SETU_accept} and @code{GNUNET_SETU_prepare}. The result
7316callback with a status indicating either that an element was received,
7317transmitted to the other peer (if this information was requested), or
7318if the operation failed or ultimately succeeded.
7319
7320@node The SETU Client-Service Protocol
7321@subsection The SETU Client-Service Protocol
7322
7323@menu
7324* Creating Sets::
7325* Listeners2::
7326* Initiating Operations::
7327* Modifying Sets::
7328* Results and Operation Status::
7329* Iterating Sets::
7330@end menu
7331
7332@node Creating Sets
7333@subsubsection Creating Sets
7334
7335For each set of a client, there exists a client connection to the service.
7336Sets are created by sending the @code{GNUNET_SERVICE_SETU_CREATE} message
7337over a new client connection. Multiple operations for one set are
7338multiplexed over one client connection, using a request id supplied by
7339the client.
7340
7341@node Listeners2
7342@subsubsection Listeners2
7343
7344Each listener also requires a seperate client connection. By sending the
7345@code{GNUNET_SERVICE_SETU_LISTEN} message, the client notifies the service
7346of the application id and operation type it is interested in. A client
7347rejects an incoming request by sending @code{GNUNET_SERVICE_SETU_REJECT}
7348on the listener's client connection.
7349In contrast, when accepting an incoming request, a
7350@code{GNUNET_SERVICE_SETU_ACCEPT} message must be sent over the@ set that
7351is supplied for the set operation.
7352
7353@node Initiating Operations
7354@subsubsection Initiating Operations
7355
7356
7357
7358Operations with remote peers are initiated by sending a
7359@code{GNUNET_SERVICE_SETU_EVALUATE} message to the service. The@ client
7360connection that this message is sent by determines the set to use.
7361
7362@node Modifying Sets
7363@subsubsection Modifying Sets
7364
7365
7366
7367Sets are modified with the @code{GNUNET_SERVICE_SETU_ADD} message.
7368
7369
7370@c %@menu
7371@c %* Results and Operation Status::
7372@c %* Iterating Sets::
7373@c %@end menu
7374
7375@node Results and Operation Status
7376@subsubsection Results and Operation Status
7377
7378The service notifies the client of result elements and success/failure of
7379a set operation with the @code{GNUNET_SERVICE_SETU_RESULT} message.
7380
7381
7382@node The SET Union Peer-to-Peer Protocol
7383@subsection The SET Union Peer-to-Peer Protocol
7384
7385
7386The SET union protocol is based on Eppstein's efficient set reconciliation
7387without prior context. You should read this paper first if you want to
7388understand the protocol.
7389
7390The union protocol operates over CADET and starts with a
7391GNUNET_MESSAGE_TYPE_SETU_P2P_OPERATION_REQUEST being sent by the peer
7392initiating the operation to the peer listening for inbound requests.
7393It includes the number of elements of the initiating peer, which is
7394currently not used.
7395
7396The listening peer checks if the operation type and application
7397identifier are acceptable for its current state. If not, it responds with
7398a @code{GNUNET_MESSAGE_TYPE_SETU_RESULT} and a status of
7399@code{GNUNET_SETU_STATUS_FAILURE} (and terminates the CADET channel).
7400
7401If the application accepts the request, it sends back a strata estimator
7402using a message of type GNUNET_MESSAGE_TYPE_SETU_P2P_SE. The
7403initiator evaluates the strata estimator and initiates the exchange of
7404invertible Bloom filters, sending a GNUNET_MESSAGE_TYPE_SETU_P2P_IBF.
7405
7406During the IBF exchange, if the receiver cannot invert the Bloom filter or
7407detects a cycle, it sends a larger IBF in response (up to a defined
7408maximum limit; if that limit is reached, the operation fails).
7409Elements decoded while processing the IBF are transmitted to the other
7410peer using GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENTS, or requested from the
7411other peer using GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENT_REQUESTS messages,
7412depending on the sign observed during decoding of the IBF.
7413Peers respond to a GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENT_REQUESTS message
7414with the respective element in a GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENTS
7415message. If the IBF fully decodes, the peer responds with a
7416GNUNET_MESSAGE_TYPE_SETU_P2P_DONE message instead of another
7417GNUNET_MESSAGE_TYPE_SETU_P2P_IBF.
7418
7419All Bloom filter operations use a salt to mingle keys before hashing them
7420into buckets, such that future iterations have a fresh chance of
7421succeeding if they failed due to collisions before.
7422
7423
7424
7425
7426
7427
6910@cindex STATISTICS Subsystem 7428@cindex STATISTICS Subsystem
6911@node STATISTICS Subsystem 7429@node STATISTICS Subsystem
6912@section STATISTICS Subsystem 7430@section STATISTICS Subsystem