seti.rst (7498B)
1 .. index:: 2 double: subsystem; SETI 3 4 .. _SETI-Subsystem-Dev: 5 6 SETI 7 ==== 8 9 .. _Intersection-Set-API: 10 11 Intersection Set API 12 ^^^^^^^^^^^^^^^^^^^^ 13 14 New sets are created with ``GNUNET_SETI_create``. Only the local peer's 15 configuration (as each set has its own client connection) must be 16 provided. The set exists until either the client calls 17 ``GNUNET_SET_destroy`` or the client's connection to the service is 18 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 with ``GNUNET_SET_add_element``. 23 24 .. _Intersection-Listeners: 25 26 Intersection Listeners 27 ^^^^^^^^^^^^^^^^^^^^^^ 28 29 Listeners are created with ``GNUNET_SET_listen``. Each time time a 30 remote peer suggests a set operation with an application id and 31 operation type matching a listener, the listener's callback is invoked. 32 The client then must synchronously call either ``GNUNET_SET_accept`` or 33 ``GNUNET_SET_reject``. Note that the operation will not be started until 34 the client calls ``GNUNET_SET_commit`` (see Section \"Supplying a 35 Set\"). 36 37 .. _Intersection-Operations: 38 39 Intersection Operations 40 ^^^^^^^^^^^^^^^^^^^^^^^ 41 42 Operations to be initiated by the local peer are created with 43 ``GNUNET_SET_prepare``. Note that the operation will not be started 44 until the client calls ``GNUNET_SET_commit`` (see Section \"Supplying a 45 Set\"). 46 47 .. _Supplying-a-Set-for-Intersection: 48 49 Supplying a Set for Intersection 50 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 51 52 To create symmetry between the two ways of starting a set operation 53 (accepting and initiating it), the operation handles returned by 54 ``GNUNET_SET_accept`` and ``GNUNET_SET_prepare`` do not yet have a set 55 to operate on, thus they can not do any work yet. 56 57 The client must call ``GNUNET_SET_commit`` to specify a set to use for 58 an operation. ``GNUNET_SET_commit`` may only be called once per set 59 operation. 60 61 .. _The-Intersection-Result-Callback: 62 63 The Intersection Result Callback 64 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 65 66 Clients must specify both a result mode and a result callback with 67 ``GNUNET_SET_accept`` and ``GNUNET_SET_prepare``. The result callback 68 with a status indicating either that an element was received, or the 69 operation failed or succeeded. The interpretation of the received 70 element depends on the result mode. The callback needs to know which 71 result mode it is used in, as the arguments do not indicate if an 72 element is part of the full result set, or if it is in the difference 73 between the original set and the final set. 74 75 .. _The-SETI-Client_002dService-Protocol: 76 77 The SETI Client-Service Protocol 78 -------------------------------- 79 80 .. _Creating-Intersection-Sets: 81 82 Creating Intersection Sets 83 ^^^^^^^^^^^^^^^^^^^^^^^^^^ 84 85 For each set of a client, there exists a client connection to the 86 service. Sets are created by sending the ``GNUNET_SERVICE_SETI_CREATE`` 87 message over a new client connection. Multiple operations for one set 88 are multiplexed over one client connection, using a request id supplied 89 by the client. 90 91 .. _Listeners-for-Intersection: 92 93 Listeners for Intersection 94 ^^^^^^^^^^^^^^^^^^^^^^^^^^ 95 96 Each listener also requires a separate client connection. By sending the 97 ``GNUNET_SERVICE_SETI_LISTEN`` message, the client notifies the service 98 of the application id and operation type it is interested in. A client 99 rejects an incoming request by sending ``GNUNET_SERVICE_SETI_REJECT`` on 100 the listener's client connection. In contrast, when accepting an 101 incoming request, a ``GNUNET_SERVICE_SETI_ACCEPT`` message must be sent 102 over the set that is supplied for the set operation. 103 104 .. _Initiating-Intersection-Operations: 105 106 Initiating Intersection Operations 107 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 108 109 Operations with remote peers are initiated by sending a 110 ``GNUNET_SERVICE_SETI_EVALUATE`` message to the service. The client 111 connection that this message is sent by determines the set to use. 112 113 .. _Modifying-Intersection-Sets: 114 115 Modifying Intersection Sets 116 ^^^^^^^^^^^^^^^^^^^^^^^^^^^ 117 118 Sets are modified with the ``GNUNET_SERVICE_SETI_ADD`` message. 119 120 .. _Intersection-Results-and-Operation-Status: 121 122 Intersection Results and Operation Status 123 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 124 125 The service notifies the client of result elements and success/failure 126 of a set operation with the ``GNUNET_SERVICE_SETI_RESULT`` message. 127 128 .. _The-SETI-Intersection-Peer_002dto_002dPeer-Protocol: 129 130 The SETI Intersection Peer-to-Peer Protocol 131 ------------------------------------------- 132 133 The intersection protocol operates over CADET and starts with a 134 GNUNET_MESSAGE_TYPE_SETI_P2P_OPERATION_REQUEST being sent by the peer 135 initiating the operation to the peer listening for inbound requests. It 136 includes the number of elements of the initiating peer, which is used to 137 decide which side will send a Bloom filter first. 138 139 The listening peer checks if the operation type and application 140 identifier are acceptable for its current state. If not, it responds 141 with a GNUNET_MESSAGE_TYPE_SETI_RESULT and a status of 142 GNUNET_SETI_STATUS_FAILURE (and terminates the CADET channel). 143 144 If the application accepts the request, the listener sends back a 145 ``GNUNET_MESSAGE_TYPE_SETI_P2P_ELEMENT_INFO`` if it has more elements in 146 the set than the client. Otherwise, it immediately starts with the Bloom 147 filter exchange. If the initiator receives a 148 ``GNUNET_MESSAGE_TYPE_SETI_P2P_ELEMENT_INFO`` response, it beings the 149 Bloom filter exchange, unless the set size is indicated to be zero, in 150 which case the intersection is considered finished after just the 151 initial handshake. 152 153 .. _The-Bloom-filter-exchange-in-SETI: 154 155 The Bloom filter exchange in SETI 156 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ 157 158 In this phase, each peer transmits a Bloom filter over the remaining 159 keys of the local set to the other peer using a 160 ``GNUNET_MESSAGE_TYPE_SETI_P2P_BF`` message. This message additionally 161 includes the number of elements left in the sender's set, as well as the 162 XOR over all of the keys in that set. 163 164 The number of bits 'k' set per element in the Bloom filter is calculated 165 based on the relative size of the two sets. Furthermore, the size of the 166 Bloom filter is calculated based on 'k' and the number of elements in 167 the set to maximize the amount of data filtered per byte transmitted on 168 the wire (while avoiding an excessively high number of iterations). 169 170 The receiver of the message removes all elements from its local set that 171 do not pass the Bloom filter test. It then checks if the set size of the 172 sender and the XOR over the keys match what is left of its own set. If 173 they do, it sends a ``GNUNET_MESSAGE_TYPE_SETI_P2P_DONE`` back to 174 indicate that the latest set is the final result. Otherwise, the 175 receiver starts another Bloom filter exchange, except this time as the 176 sender. 177 178 .. _Intersection-Salt: 179 180 Intersection Salt 181 ^^^^^^^^^^^^^^^^^ 182 183 Bloom filter operations are probabilistic: With some non-zero 184 probability the test may incorrectly say an element is in the set, even 185 though it is not. 186 187 To mitigate this problem, the intersection protocol iterates exchanging 188 Bloom filters using a different random 32-bit salt in each iteration 189 (the salt is also included in the message). With different salts, set 190 operations may fail for different elements. Merging the results from the 191 executions, the probability of failure drops to zero. 192 193 The iterations terminate once both peers have established that they have 194 sets of the same size, and where the XOR over all keys computes the same 195 512-bit value (leaving a failure probability of 2-511). 196 197