aboutsummaryrefslogtreecommitdiff
path: root/doc/handbook/chapters/developer.texi
diff options
context:
space:
mode:
Diffstat (limited to 'doc/handbook/chapters/developer.texi')
-rw-r--r--doc/handbook/chapters/developer.texi516
1 files changed, 514 insertions, 2 deletions
diff --git a/doc/handbook/chapters/developer.texi b/doc/handbook/chapters/developer.texi
index 6d8ddd3c2..369e5327c 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,513 @@ 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* Intersection Sets::
6934* Set Intersection Modifications::
6935* Set Intersection Operations::
6936* Intersection Result Elements::
6937* libgnunetseti::
6938* The SETI Client-Service Protocol::
6939* The SETI Intersection Peer-to-Peer Protocol::
6940@end menu
6941
6942@node Intersection Sets
6943@subsection Intersection 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 Intersection Modifications
6950@subsection Set Intersection 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 Intersection Operations
6961@subsection Set Intersection 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 Intersection Result Elements
6976@subsection Intersection 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* Intersection Set API::
6994* Intersection Listeners::
6995* Intersection Operations::
6996* Supplying a Set for Intersection::
6997* The Intersection Result Callback::
6998@end menu
6999
7000@node Intersection Set API
7001@subsubsection Intersection Set API
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 Intersection Listeners
7013@subsubsection Intersection 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 Intersection Operations
7024@subsubsection Intersection 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 for Intersection
7032@subsubsection Supplying a Set for Intersection
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 Intersection Result Callback
7044@subsubsection The Intersection 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 Intersection Sets::
7060* Listeners for Intersection::
7061* Initiating Intersection Operations::
7062* Modifying Intersection Sets::
7063* Intersection Results and Operation Status::
7064@end menu
7065
7066@node Creating Intersection Sets
7067@subsubsection Creating Intersection 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 Listeners for Intersection
7076@subsubsection Listeners for Intersection
7077
7078Each listener also requires a seperate client connection. By sending the
7079@code{GNUNET_SERVICE_SETI_LISTEN} message, the client notifies the service
7080of the application id and operation type it is interested in. A client
7081rejects an incoming request by sending @code{GNUNET_SERVICE_SETI_REJECT}
7082on the listener's client connection.
7083In contrast, when accepting an incoming request, a
7084@code{GNUNET_SERVICE_SETI_ACCEPT} message must be sent over the@ set that
7085is supplied for the set operation.
7086
7087@node Initiating Intersection Operations
7088@subsubsection Initiating Intersection Operations
7089
7090Operations with remote peers are initiated by sending a
7091@code{GNUNET_SERVICE_SETI_EVALUATE} message to the service. The@ client
7092connection that this message is sent by determines the set to use.
7093
7094@node Modifying Intersection Sets
7095@subsubsection Modifying Intersection Sets
7096
7097Sets are modified with the @code{GNUNET_SERVICE_SETI_ADD} message.
7098
7099
7100@c %@menu
7101@c %* Results and Operation Status::
7102@c %* Iterating Sets::
7103@c %@end menu
7104
7105@node Intersection Results and Operation Status
7106@subsubsection Intersection Results and Operation Status
7107
7108The service notifies the client of result elements and success/failure of
7109a set operation with the @code{GNUNET_SERVICE_SETI_RESULT} message.
7110
7111@node The SETI Intersection Peer-to-Peer Protocol
7112@subsection The SETI Intersection Peer-to-Peer Protocol
7113
7114The intersection protocol operates over CADET and starts with a
7115GNUNET_MESSAGE_TYPE_SETI_P2P_OPERATION_REQUEST being sent by the peer
7116initiating the operation to the peer listening for inbound requests.
7117It includes the number of elements of the initiating peer, which is used
7118to decide which side will send a Bloom filter first.
7119
7120The listening peer checks if the operation type and application
7121identifier are acceptable for its current state.
7122If not, it responds with a GNUNET_MESSAGE_TYPE_SETI_RESULT and a status of
7123GNUNET_SETI_STATUS_FAILURE (and terminates the CADET channel).
7124
7125If the application accepts the request, the listener sends back a
7126@code{GNUNET_MESSAGE_TYPE_SETI_P2P_ELEMENT_INFO} if it has
7127more elements in the set than the client.
7128Otherwise, it immediately starts with the Bloom filter exchange.
7129If the initiator receives a
7130@code{GNUNET_MESSAGE_TYPE_SETI_P2P_ELEMENT_INFO} response,
7131it beings the Bloom filter exchange, unless the set size is indicated to
7132be zero, in which case the intersection is considered finished after
7133just the initial handshake.
7134
7135
7136@menu
7137* The Bloom filter exchange in SETI::
7138* Intersection Salt::
7139@end menu
7140
7141@node The Bloom filter exchange in SETI
7142@subsubsection The Bloom filter exchange in SETI
7143
7144In this phase, each peer transmits a Bloom filter over the remaining
7145keys of the local set to the other peer using a
7146@code{GNUNET_MESSAGE_TYPE_SETI_P2P_BF} message. This
7147message additionally includes the number of elements left in the sender's
7148set, as well as the XOR over all of the keys in that set.
7149
7150The number of bits 'k' set per element in the Bloom filter is calculated
7151based on the relative size of the two sets.
7152Furthermore, the size of the Bloom filter is calculated based on 'k' and
7153the number of elements in the set to maximize the amount of data filtered
7154per byte transmitted on the wire (while avoiding an excessively high
7155number of iterations).
7156
7157The receiver of the message removes all elements from its local set that
7158do not pass the Bloom filter test.
7159It then checks if the set size of the sender and the XOR over the keys
7160match what is left of its own set. If they do, it sends a
7161@code{GNUNET_MESSAGE_TYPE_SETI_P2P_DONE} back to indicate
7162that the latest set is the final result.
7163Otherwise, the receiver starts another Bloom filter exchange, except
7164this time as the sender.
7165
7166@node Intersection Salt
7167@subsubsection Intersection Salt
7168
7169Bloom filter operations are probabilistic: With some non-zero probability
7170the test may incorrectly say an element is in the set, even though it is
7171not.
7172
7173To mitigate this problem, the intersection protocol iterates exchanging
7174Bloom filters using a different random 32-bit salt in each iteration (the
7175salt is also included in the message).
7176With different salts, set operations may fail for different elements.
7177Merging the results from the executions, the probability of failure drops
7178to zero.
7179
7180The iterations terminate once both peers have established that they have
7181sets of the same size, and where the XOR over all keys computes the same
7182512-bit value (leaving a failure probability of 2-511).
7183
7184
7185@cindex SETU Subsystem
7186@node SETU Subsystem
7187@section SETU Subsystem
7188
7189The SETU service implements efficient set union operations between two peers
7190over a CADET tunnel. Elements of a set consist of an @emph{element type} and
7191arbitrary binary @emph{data}. The size of an element's data is limited to
7192around 62 KB.
7193
7194@menu
7195* Union Sets::
7196* Set Union Modifications::
7197* Set Union Operations::
7198* Union Result Elements::
7199* libgnunetsetu::
7200* The SETU Client-Service Protocol::
7201* The SETU Union Peer-to-Peer Protocol::
7202@end menu
7203
7204@node Union Sets
7205@subsection Union Sets
7206
7207Sets created by a local client can be modified (by adding additional elements)
7208and reused for multiple operations. If elements are to be removed, a fresh
7209set must be created by the client.
7210
7211@node Set Union Modifications
7212@subsection Set Union Modifications
7213
7214Even when set operations are active, one can add elements
7215to a set.
7216However, these changes will only be visible to operations that have been
7217created after the changes have taken place. That is, every set operation
7218only sees a snapshot of the set from the time the operation was started.
7219This mechanism is @emph{not} implemented by copying the whole set, but by
7220attaching @emph{generation information} to each element and operation.
7221
7222@node Set Union Operations
7223@subsection Set Union Operations
7224
7225Set operations can be started in two ways: Either by accepting an
7226operation request from a remote peer, or by requesting a set operation
7227from a remote peer.
7228Set operations are uniquely identified by the involved @emph{peers}, an
7229@emph{application id} and the @emph{operation type}.
7230
7231The client is notified of incoming set operations by @emph{set listeners}.
7232A set listener listens for incoming operations of a specific operation
7233type and application id.
7234Once notified of an incoming set request, the client can accept the set
7235request (providing a local set for the operation) or reject it.
7236
7237@node Union Result Elements
7238@subsection Union Result Elements
7239
7240The SET service has three @emph{result modes} that determine how an
7241operation's result set is delivered to the client:
7242
7243@itemize @bullet
7244@item @strong{Locally added Elements.} Elements that are in the union
7245but not already in the local peer's set are returned.
7246@item @strong{Remote added Elements.} Additionally, notify the client
7247if the remote peer lacked some elements and thus also return to the
7248local client those elements that we are sending to the remote peer to
7249be added to its union. Obtaining these elements requires setting
7250the @code{GNUNET_SETU_OPTION_SYMMETRIC} option.
7251@end itemize
7252
7253@cindex libgnunetsetu
7254@node libgnunetsetu
7255@subsection libgnunetsetu
7256
7257@menu
7258* Union Set API::
7259* Union Listeners::
7260* Union Operations::
7261* Supplying a Set for Union::
7262* The Union Result Callback::
7263@end menu
7264
7265@node Union Set API
7266@subsubsection Union Set API
7267
7268New sets are created with @code{GNUNET_SETU_create}. Only the local peer's
7269configuration (as each set has its own client connection) must be provided.
7270The set exists until either the client calls @code{GNUNET_SETU_destroy} or
7271the client's connection to the service is disrupted.
7272In the latter case, the client is notified by the return value of
7273functions dealing with sets. This return value must always be checked.
7274
7275Elements are added with @code{GNUNET_SETU_add_element}.
7276
7277@node Union Listeners
7278@subsubsection Union Listeners
7279
7280Listeners are created with @code{GNUNET_SETU_listen}. Each time time a
7281remote peer suggests a set operation with an application id and operation
7282type matching a listener, the listener's callback is invoked.
7283The client then must synchronously call either @code{GNUNET_SETU_accept}
7284or @code{GNUNET_SETU_reject}. Note that the operation will not be started
7285until the client calls @code{GNUNET_SETU_commit}
7286(see Section "Supplying a Set").
7287
7288@node Union Operations
7289@subsubsection Union Operations
7290
7291Operations to be initiated by the local peer are created with
7292@code{GNUNET_SETU_prepare}. Note that the operation will not be started
7293until the client calls @code{GNUNET_SETU_commit}
7294(see Section "Supplying a Set").
7295
7296@node Supplying a Set for Union
7297@subsubsection Supplying a Set for Union
7298
7299To create symmetry between the two ways of starting a set operation
7300(accepting and initiating it), the operation handles returned by
7301@code{GNUNET_SETU_accept} and @code{GNUNET_SETU_prepare} do not yet have a
7302set to operate on, thus they can not do any work yet.
7303
7304The client must call @code{GNUNET_SETU_commit} to specify a set to use for
7305an operation. @code{GNUNET_SETU_commit} may only be called once per set
7306operation.
7307
7308@node The Union Result Callback
7309@subsubsection The Union Result Callback
7310
7311Clients must specify both a result mode and a result callback with
7312@code{GNUNET_SETU_accept} and @code{GNUNET_SETU_prepare}. The result
7313callback with a status indicating either that an element was received,
7314transmitted to the other peer (if this information was requested), or
7315if the operation failed or ultimately succeeded.
7316
7317@node The SETU Client-Service Protocol
7318@subsection The SETU Client-Service Protocol
7319
7320@menu
7321* Creating Union Sets::
7322* Listeners for Union::
7323* Initiating Union Operations::
7324* Modifying Union Sets::
7325* Union Results and Operation Status::
7326@end menu
7327
7328@node Creating Union Sets
7329@subsubsection Creating Union Sets
7330
7331For each set of a client, there exists a client connection to the service.
7332Sets are created by sending the @code{GNUNET_SERVICE_SETU_CREATE} message
7333over a new client connection. Multiple operations for one set are
7334multiplexed over one client connection, using a request id supplied by
7335the client.
7336
7337@node Listeners for Union
7338@subsubsection Listeners for Union
7339
7340Each listener also requires a seperate client connection. By sending the
7341@code{GNUNET_SERVICE_SETU_LISTEN} message, the client notifies the service
7342of the application id and operation type it is interested in. A client
7343rejects an incoming request by sending @code{GNUNET_SERVICE_SETU_REJECT}
7344on the listener's client connection.
7345In contrast, when accepting an incoming request, a
7346@code{GNUNET_SERVICE_SETU_ACCEPT} message must be sent over the@ set that
7347is supplied for the set operation.
7348
7349@node Initiating Union Operations
7350@subsubsection Initiating Union Operations
7351
7352
7353
7354Operations with remote peers are initiated by sending a
7355@code{GNUNET_SERVICE_SETU_EVALUATE} message to the service. The@ client
7356connection that this message is sent by determines the set to use.
7357
7358@node Modifying Union Sets
7359@subsubsection Modifying Union Sets
7360
7361Sets are modified with the @code{GNUNET_SERVICE_SETU_ADD} message.
7362
7363
7364@c %@menu
7365@c %* Results and Operation Status::
7366@c %* Iterating Sets::
7367@c %@end menu
7368
7369@node Union Results and Operation Status
7370@subsubsection Union Results and Operation Status
7371
7372The service notifies the client of result elements and success/failure of
7373a set operation with the @code{GNUNET_SERVICE_SETU_RESULT} message.
7374
7375
7376@node The SETU Union Peer-to-Peer Protocol
7377@subsection The SETU Union Peer-to-Peer Protocol
7378
7379
7380The SET union protocol is based on Eppstein's efficient set reconciliation
7381without prior context. You should read this paper first if you want to
7382understand the protocol.
7383
7384The union protocol operates over CADET and starts with a
7385GNUNET_MESSAGE_TYPE_SETU_P2P_OPERATION_REQUEST being sent by the peer
7386initiating the operation to the peer listening for inbound requests.
7387It includes the number of elements of the initiating peer, which is
7388currently not used.
7389
7390The listening peer checks if the operation type and application
7391identifier are acceptable for its current state. If not, it responds with
7392a @code{GNUNET_MESSAGE_TYPE_SETU_RESULT} and a status of
7393@code{GNUNET_SETU_STATUS_FAILURE} (and terminates the CADET channel).
7394
7395If the application accepts the request, it sends back a strata estimator
7396using a message of type GNUNET_MESSAGE_TYPE_SETU_P2P_SE. The
7397initiator evaluates the strata estimator and initiates the exchange of
7398invertible Bloom filters, sending a GNUNET_MESSAGE_TYPE_SETU_P2P_IBF.
7399
7400During the IBF exchange, if the receiver cannot invert the Bloom filter or
7401detects a cycle, it sends a larger IBF in response (up to a defined
7402maximum limit; if that limit is reached, the operation fails).
7403Elements decoded while processing the IBF are transmitted to the other
7404peer using GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENTS, or requested from the
7405other peer using GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENT_REQUESTS messages,
7406depending on the sign observed during decoding of the IBF.
7407Peers respond to a GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENT_REQUESTS message
7408with the respective element in a GNUNET_MESSAGE_TYPE_SETU_P2P_ELEMENTS
7409message. If the IBF fully decodes, the peer responds with a
7410GNUNET_MESSAGE_TYPE_SETU_P2P_DONE message instead of another
7411GNUNET_MESSAGE_TYPE_SETU_P2P_IBF.
7412
7413All Bloom filter operations use a salt to mingle keys before hashing them
7414into buckets, such that future iterations have a fresh chance of
7415succeeding if they failed due to collisions before.
7416
7417
7418
7419
7420
7421
6910@cindex STATISTICS Subsystem 7422@cindex STATISTICS Subsystem
6911@node STATISTICS Subsystem 7423@node STATISTICS Subsystem
6912@section STATISTICS Subsystem 7424@section STATISTICS Subsystem