set.rst (9740B)
1 .. index:: 2 double: subsystem; SET 3 4 .. _SET-Subsystem-Dev: 5 6 SET 7 === 8 9 .. _Sets: 10 11 Sets 12 ^^^^ 13 14 New sets are created with ``GNUNET_SET_create``. Both the local peer's 15 configuration (as each set has its own client connection) and the 16 operation type must be specified. The set exists until either the client 17 calls ``GNUNET_SET_destroy`` or the client's connection to the service 18 is disrupted. In the latter case, the client is notified by the return 19 value of functions dealing with sets. This return value must always be 20 checked. 21 22 Elements are added and removed with ``GNUNET_SET_add_element`` and 23 ``GNUNET_SET_remove_element``. 24 25 .. _Listeners: 26 27 Listeners 28 ^^^^^^^^^ 29 30 Listeners are created with ``GNUNET_SET_listen``. Each time time a 31 remote peer suggests a set operation with an application id and 32 operation type matching a listener, the listener's callback is invoked. 33 The client then must synchronously call either ``GNUNET_SET_accept`` or 34 ``GNUNET_SET_reject``. Note that the operation will not be started until 35 the client calls ``GNUNET_SET_commit`` (see Section \"Supplying a 36 Set\"). 37 38 .. _Operations: 39 40 Operations 41 ^^^^^^^^^^ 42 43 Operations to be initiated by the local peer are created with 44 ``GNUNET_SET_prepare``. Note that the operation will not be started 45 until the client calls ``GNUNET_SET_commit`` (see Section \"Supplying a 46 Set\"). 47 48 .. _Supplying-a-Set: 49 50 Supplying a Set 51 ^^^^^^^^^^^^^^^ 52 53 To create symmetry between the two ways of starting a set operation 54 (accepting and initiating it), the operation handles returned by 55 ``GNUNET_SET_accept`` and ``GNUNET_SET_prepare`` do not yet have a set 56 to operate on, thus they can not do any work yet. 57 58 The client must call ``GNUNET_SET_commit`` to specify a set to use for 59 an operation. ``GNUNET_SET_commit`` may only be called once per set 60 operation. 61 62 .. _The-Result-Callback: 63 64 The Result Callback 65 ^^^^^^^^^^^^^^^^^^^ 66 67 Clients must specify both a result mode and a result callback with 68 ``GNUNET_SET_accept`` and ``GNUNET_SET_prepare``. The result callback 69 with a status indicating either that an element was received, or the 70 operation failed or succeeded. The interpretation of the received 71 element depends on the result mode. The callback needs to know which 72 result mode it is used in, as the arguments do not indicate if an 73 element is part of the full result set, or if it is in the difference 74 between the original set and the final set. 75 76 .. _The-SET-Client_002dService-Protocol: 77 78 The SET Client-Service Protocol 79 ------------------------------- 80 81 .. _Creating-Sets: 82 83 Creating Sets 84 ^^^^^^^^^^^^^ 85 86 For each set of a client, there exists a client connection to the 87 service. Sets are created by sending the ``GNUNET_SERVICE_SET_CREATE`` 88 message over a new client connection. Multiple operations for one set 89 are multiplexed over one client connection, using a request id supplied 90 by the client. 91 92 .. _Listeners2: 93 94 Listeners 95 ^^^^^^^^^ 96 97 Each listener also requires a separate client connection. By sending the 98 ``GNUNET_SERVICE_SET_LISTEN`` message, the client notifies the service 99 of the application id and operation type it is interested in. A client 100 rejects an incoming request by sending ``GNUNET_SERVICE_SET_REJECT`` on 101 the listener's client connection. In contrast, when accepting an 102 incoming request, a ``GNUNET_SERVICE_SET_ACCEPT`` message must be sent 103 over the set that is supplied for the set operation. 104 105 .. _Initiating-Operations: 106 107 Initiating Operations 108 ^^^^^^^^^^^^^^^^^^^^^ 109 110 Operations with remote peers are initiated by sending a 111 ``GNUNET_SERVICE_SET_EVALUATE`` message to the service. The client 112 connection that this message is sent by determines the set to use. 113 114 .. _Modifying-Sets: 115 116 Modifying Sets 117 ^^^^^^^^^^^^^^ 118 119 Sets are modified with the ``GNUNET_SERVICE_SET_ADD`` and 120 ``GNUNET_SERVICE_SET_REMOVE`` messages. 121 122 .. _Results-and-Operation-Status: 123 124 Results and Operation Status 125 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 126 127 The service notifies the client of result elements and success/failure 128 of a set operation with the ``GNUNET_SERVICE_SET_RESULT`` message. 129 130 .. _Iterating-Sets: 131 132 Iterating Sets 133 ^^^^^^^^^^^^^^ 134 135 All elements of a set can be requested by sending 136 ``GNUNET_SERVICE_SET_ITER_REQUEST``. The server responds with 137 ``GNUNET_SERVICE_SET_ITER_ELEMENT`` and eventually terminates the 138 iteration with ``GNUNET_SERVICE_SET_ITER_DONE``. After each received 139 element, the client must send ``GNUNET_SERVICE_SET_ITER_ACK``. Note that 140 only one set iteration may be active for a set at any given time. 141 142 .. _The-SET-Intersection-Peer_002dto_002dPeer-Protocol: 143 144 The SET Intersection Peer-to-Peer Protocol 145 ------------------------------------------ 146 147 The intersection protocol operates over CADET and starts with a 148 GNUNET_MESSAGE_TYPE_SET_P2P_OPERATION_REQUEST being sent by the peer 149 initiating the operation to the peer listening for inbound requests. It 150 includes the number of elements of the initiating peer, which is used to 151 decide which side will send a Bloom filter first. 152 153 The listening peer checks if the operation type and application 154 identifier are acceptable for its current state. If not, it responds 155 with a GNUNET_MESSAGE_TYPE_SET_RESULT and a status of 156 GNUNET_SET_STATUS_FAILURE (and terminates the CADET channel). 157 158 If the application accepts the request, the listener sends back a 159 ``GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_ELEMENT_INFO`` if it has more 160 elements in the set than the client. Otherwise, it immediately starts 161 with the Bloom filter exchange. If the initiator receives a 162 ``GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_ELEMENT_INFO`` response, it 163 beings the Bloom filter exchange, unless the set size is indicated to be 164 zero, in which case the intersection is considered finished after just 165 the initial handshake. 166 167 .. _The-Bloom-filter-exchange: 168 169 The Bloom filter exchange 170 ^^^^^^^^^^^^^^^^^^^^^^^^^ 171 172 In this phase, each peer transmits a Bloom filter over the remaining 173 keys of the local set to the other peer using a 174 ``GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF`` message. This message 175 additionally includes the number of elements left in the sender's set, 176 as well as the XOR over all of the keys in that set. 177 178 The number of bits 'k' set per element in the Bloom filter is calculated 179 based on the relative size of the two sets. Furthermore, the size of the 180 Bloom filter is calculated based on 'k' and the number of elements in 181 the set to maximize the amount of data filtered per byte transmitted on 182 the wire (while avoiding an excessively high number of iterations). 183 184 The receiver of the message removes all elements from its local set that 185 do not pass the Bloom filter test. It then checks if the set size of the 186 sender and the XOR over the keys match what is left of its own set. If 187 they do, it sends a ``GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_DONE`` 188 back to indicate that the latest set is the final result. Otherwise, the 189 receiver starts another Bloom filter exchange, except this time as the 190 sender. 191 192 .. _Salt: 193 194 Salt 195 ^^^^ 196 197 Bloomfilter operations are probabilistic: With some non-zero probability 198 the test may incorrectly say an element is in the set, even though it is 199 not. 200 201 To mitigate this problem, the intersection protocol iterates exchanging 202 Bloom filters using a different random 32-bit salt in each iteration 203 (the salt is also included in the message). With different salts, set 204 operations may fail for different elements. Merging the results from the 205 executions, the probability of failure drops to zero. 206 207 The iterations terminate once both peers have established that they have 208 sets of the same size, and where the XOR over all keys computes the same 209 512-bit value (leaving a failure probability of 2\ :superscript:`-511`\ ). 210 211 .. _The-SET-Union-Peer_002dto_002dPeer-Protocol: 212 213 The SET Union Peer-to-Peer Protocol 214 ----------------------------------- 215 216 The SET union protocol is based on Eppstein's efficient set 217 reconciliation without prior context. You should read this paper first 218 if you want to understand the protocol. 219 220 .. todo:: Link to Eppstein's paper! 221 222 The union protocol operates over CADET and starts with a 223 GNUNET_MESSAGE_TYPE_SET_P2P_OPERATION_REQUEST being sent by the peer 224 initiating the operation to the peer listening for inbound requests. It 225 includes the number of elements of the initiating peer, which is 226 currently not used. 227 228 The listening peer checks if the operation type and application 229 identifier are acceptable for its current state. If not, it responds 230 with a ``GNUNET_MESSAGE_TYPE_SET_RESULT`` and a status of 231 ``GNUNET_SET_STATUS_FAILURE`` (and terminates the CADET channel). 232 233 If the application accepts the request, it sends back a strata estimator 234 using a message of type GNUNET_MESSAGE_TYPE_SET_UNION_P2P_SE. The 235 initiator evaluates the strata estimator and initiates the exchange of 236 invertible Bloom filters, sending a 237 GNUNET_MESSAGE_TYPE_SET_UNION_P2P_IBF. 238 239 During the IBF exchange, if the receiver cannot invert the Bloom filter 240 or detects a cycle, it sends a larger IBF in response (up to a defined 241 maximum limit; if that limit is reached, the operation fails). Elements 242 decoded while processing the IBF are transmitted to the other peer using 243 GNUNET_MESSAGE_TYPE_SET_P2P_ELEMENTS, or requested from the other peer 244 using GNUNET_MESSAGE_TYPE_SET_P2P_ELEMENT_REQUESTS messages, depending 245 on the sign observed during decoding of the IBF. Peers respond to a 246 GNUNET_MESSAGE_TYPE_SET_P2P_ELEMENT_REQUESTS message with the respective 247 element in a GNUNET_MESSAGE_TYPE_SET_P2P_ELEMENTS message. If the IBF 248 fully decodes, the peer responds with a 249 GNUNET_MESSAGE_TYPE_SET_UNION_P2P_DONE message instead of another 250 GNUNET_MESSAGE_TYPE_SET_UNION_P2P_IBF. 251 252 All Bloom filter operations use a salt to mingle keys before hashing 253 them into buckets, such that future iterations have a fresh chance of 254 succeeding if they failed due to collisions before. 255