reduce loop counters to more practical levels
[oweals/gnunet.git] / src / scalarproduct / gnunet-service-scalarproduct_alice.c
1 /*
2      This file is part of GNUnet.
3      Copyright (C) 2013, 2014, 2017 GNUnet e.V.
4
5      GNUnet is free software; you can redistribute it and/or modify
6      it under the terms of the GNU General Public License as published
7      by the Free Software Foundation; either version 3, or (at your
8      option) any later version.
9
10      GNUnet is distributed in the hope that it will be useful, but
11      WITHOUT ANY WARRANTY; without even the implied warranty of
12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
13      General Public License for more details.
14
15      You should have received a copy of the GNU General Public License
16      along with GNUnet; see the file COPYING.  If not, write to the
17      Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18      Boston, MA 02110-1301, USA.
19  */
20 /**
21  * @file scalarproduct/gnunet-service-scalarproduct_alice.c
22  * @brief scalarproduct service implementation
23  * @author Christian M. Fuchs
24  * @author Christian Grothoff
25  */
26 #include "platform.h"
27 #include <limits.h>
28 #include <gcrypt.h>
29 #include "gnunet_util_lib.h"
30 #include "gnunet_core_service.h"
31 #include "gnunet_cadet_service.h"
32 #include "gnunet_applications.h"
33 #include "gnunet_protocols.h"
34 #include "gnunet_scalarproduct_service.h"
35 #include "gnunet_set_service.h"
36 #include "scalarproduct.h"
37 #include "gnunet-service-scalarproduct.h"
38
39 #define LOG(kind,...) GNUNET_log_from (kind, "scalarproduct-alice", __VA_ARGS__)
40
41 /**
42  * An encrypted element key-value pair.
43  */
44 struct MpiElement
45 {
46   /**
47    * Key used to identify matching pairs of values to multiply.
48    * Points into an existing data structure, to avoid copying
49    * and doubling memory use.
50    */
51   const struct GNUNET_HashCode *key;
52
53   /**
54    * Value represented (a).
55    */
56   gcry_mpi_t value;
57 };
58
59
60 /**
61  * A scalarproduct session which tracks
62  * a request form the client to our final response.
63  */
64 struct AliceServiceSession
65 {
66
67   /**
68    * (hopefully) unique transaction ID
69    */
70   struct GNUNET_HashCode session_id;
71
72   /**
73    * Alice or Bob's peerID
74    */
75   struct GNUNET_PeerIdentity peer;
76
77   /**
78    * The client this request is related to.
79    */
80   struct GNUNET_SERVICE_Client *client;
81
82   /**
83    * The message queue for the client.
84    */
85   struct GNUNET_MQ_Handle *client_mq;
86
87   /**
88    * The message queue for CADET.
89    */
90   struct GNUNET_MQ_Handle *cadet_mq;
91
92   /**
93    * all non-0-value'd elements transmitted to us.
94    * Values are of type `struct GNUNET_SCALARPRODUCT_Element *`
95    */
96   struct GNUNET_CONTAINER_MultiHashMap *intersected_elements;
97
98   /**
99    * Set of elements for which will conduction an intersection.
100    * the resulting elements are then used for computing the scalar product.
101    */
102   struct GNUNET_SET_Handle *intersection_set;
103
104   /**
105    * Set of elements for which will conduction an intersection.
106    * the resulting elements are then used for computing the scalar product.
107    */
108   struct GNUNET_SET_OperationHandle *intersection_op;
109
110   /**
111    * Handle to Alice's Intersection operation listening for Bob
112    */
113   struct GNUNET_SET_ListenHandle *intersection_listen;
114
115   /**
116    * channel-handle associated with our cadet handle
117    */
118   struct GNUNET_CADET_Channel *channel;
119
120   /**
121    * a(Alice), sorted array by key of length @e used_element_count.
122    */
123   struct MpiElement *sorted_elements;
124
125   /**
126    * Bob's permutation p of R
127    */
128   struct GNUNET_CRYPTO_PaillierCiphertext *r;
129
130   /**
131    * Bob's permutation q of R
132    */
133   struct GNUNET_CRYPTO_PaillierCiphertext *r_prime;
134
135   /**
136    * Bob's "s"
137    */
138   struct GNUNET_CRYPTO_PaillierCiphertext s;
139
140   /**
141    * Bob's "s'"
142    */
143   struct GNUNET_CRYPTO_PaillierCiphertext s_prime;
144
145   /**
146    * The computed scalar
147    */
148   gcry_mpi_t product;
149
150   /**
151    * How many elements we were supplied with from the client (total
152    * count before intersection).
153    */
154   uint32_t total;
155
156   /**
157    * How many elements actually are used for the scalar product.
158    * Size of the arrays in @e r and @e r_prime.  Sometimes also
159    * reset to 0 and used as a counter!
160    */
161   uint32_t used_element_count;
162
163   /**
164    * Already transferred elements from client to us.
165    * Less or equal than @e total.
166    */
167   uint32_t client_received_element_count;
168
169   /**
170    * Already transferred elements from Bob to us.
171    * Less or equal than @e total.
172    */
173   uint32_t cadet_received_element_count;
174
175   /**
176    * State of this session.   In
177    * #GNUNET_SCALARPRODUCT_STATUS_ACTIVE while operation is
178    * ongoing, afterwards in #GNUNET_SCALARPRODUCT_STATUS_SUCCESS or
179    * #GNUNET_SCALARPRODUCT_STATUS_FAILURE.
180    */
181   enum GNUNET_SCALARPRODUCT_ResponseStatus status;
182
183   /**
184    * Flag to prevent recursive calls to #destroy_service_session() from
185    * doing harm.
186    */
187   int in_destroy;
188
189 };
190
191
192 /**
193  * GNUnet configuration handle
194  */
195 static const struct GNUNET_CONFIGURATION_Handle *cfg;
196
197 /**
198  * Service's own public key
199  */
200 static struct GNUNET_CRYPTO_PaillierPublicKey my_pubkey;
201
202 /**
203  * Service's own private key
204  */
205 static struct GNUNET_CRYPTO_PaillierPrivateKey my_privkey;
206
207 /**
208  * Service's offset for values that could possibly be negative but are plaintext for encryption.
209  */
210 static gcry_mpi_t my_offset;
211
212 /**
213  * Handle to the CADET service.
214  */
215 static struct GNUNET_CADET_Handle *my_cadet;
216
217
218 /**
219  * Iterator called to free elements.
220  *
221  * @param cls the `struct AliceServiceSession *` (unused)
222  * @param key the key (unused)
223  * @param value value to free
224  * @return #GNUNET_OK (continue to iterate)
225  */
226 static int
227 free_element_cb (void *cls,
228                  const struct GNUNET_HashCode *key,
229                  void *value)
230 {
231   struct GNUNET_SCALARPRODUCT_Element *e = value;
232
233   GNUNET_free (e);
234   return GNUNET_OK;
235 }
236
237
238 /**
239  * Destroy session state, we are done with it.
240  *
241  * @param s the session to free elements from
242  */
243 static void
244 destroy_service_session (struct AliceServiceSession *s)
245 {
246   if (GNUNET_YES == s->in_destroy)
247     return;
248   s->in_destroy = GNUNET_YES;
249   if (NULL != s->client)
250   {
251     struct GNUNET_SERVICE_Client *c = s->client;
252
253     s->client = NULL;
254     GNUNET_SERVICE_client_drop (c);
255   }
256   if (NULL != s->channel)
257   {
258     GNUNET_CADET_channel_destroy (s->channel);
259     s->channel = NULL;
260   }
261   if (NULL != s->intersected_elements)
262   {
263     GNUNET_CONTAINER_multihashmap_iterate (s->intersected_elements,
264                                            &free_element_cb,
265                                            s);
266     GNUNET_CONTAINER_multihashmap_destroy (s->intersected_elements);
267     s->intersected_elements = NULL;
268   }
269   if (NULL != s->intersection_listen)
270   {
271     GNUNET_SET_listen_cancel (s->intersection_listen);
272     s->intersection_listen = NULL;
273   }
274   if (NULL != s->intersection_op)
275   {
276     GNUNET_SET_operation_cancel (s->intersection_op);
277     s->intersection_op = NULL;
278   }
279   if (NULL != s->intersection_set)
280   {
281     GNUNET_SET_destroy (s->intersection_set);
282     s->intersection_set = NULL;
283   }
284   if (NULL != s->sorted_elements)
285   {
286     for (unsigned int i=0;i<s->used_element_count;i++)
287       gcry_mpi_release (s->sorted_elements[i].value);
288     GNUNET_free (s->sorted_elements);
289     s->sorted_elements = NULL;
290   }
291   if (NULL != s->r)
292   {
293     GNUNET_free (s->r);
294     s->r = NULL;
295   }
296   if (NULL != s->r_prime)
297   {
298     GNUNET_free (s->r_prime);
299     s->r_prime = NULL;
300   }
301   if (NULL != s->product)
302   {
303     gcry_mpi_release (s->product);
304     s->product = NULL;
305   }
306   GNUNET_free (s);
307 }
308
309
310 /**
311  * Notify the client that the session has failed.  A message gets sent
312  * to Alice's client if we encountered any error.
313  *
314  * @param session the associated client session to fail or succeed
315  */
316 static void
317 prepare_client_end_notification (struct AliceServiceSession *session)
318 {
319   struct ClientResponseMessage *msg;
320   struct GNUNET_MQ_Envelope *e;
321
322   if (NULL == session->client_mq)
323     return; /* no client left to be notified */
324   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
325               "Sending session-end notification with status %d to client for session %s\n",
326               session->status,
327               GNUNET_h2s (&session->session_id));
328   e = GNUNET_MQ_msg (msg,
329                      GNUNET_MESSAGE_TYPE_SCALARPRODUCT_RESULT);
330   msg->product_length = htonl (0);
331   msg->status = htonl (session->status);
332   GNUNET_MQ_send (session->client_mq,
333                   e);
334 }
335
336
337 /**
338  * Prepare the final (positive) response we will send to Alice's
339  * client.
340  *
341  * @param s the session associated with our client.
342  */
343 static void
344 transmit_client_response (struct AliceServiceSession *s)
345 {
346   struct ClientResponseMessage *msg;
347   struct GNUNET_MQ_Envelope *e;
348   unsigned char *product_exported = NULL;
349   size_t product_length = 0;
350   int32_t range;
351   gcry_error_t rc;
352   int sign;
353   gcry_mpi_t value;
354
355   if (NULL == s->product)
356   {
357     GNUNET_break (0);
358     prepare_client_end_notification (s);
359     return;
360   }
361   value = gcry_mpi_new (0);
362   sign = gcry_mpi_cmp_ui (s->product, 0);
363   if (0 > sign)
364   {
365     range = -1;
366     gcry_mpi_sub (value,
367                   value,
368                   s->product);
369   }
370   else if (0 < sign)
371   {
372     range = 1;
373     gcry_mpi_add (value, value, s->product);
374   }
375   else
376   {
377     /* result is exactly zero */
378     range = 0;
379   }
380   gcry_mpi_release (s->product);
381   s->product = NULL;
382
383   if ( (0 != range) &&
384        (0 != (rc = gcry_mpi_aprint (GCRYMPI_FMT_STD,
385                                     &product_exported,
386                                     &product_length,
387                                     value))))
388   {
389     LOG_GCRY (GNUNET_ERROR_TYPE_ERROR,
390               "gcry_mpi_scan",
391               rc);
392     prepare_client_end_notification (s);
393     return;
394   }
395   gcry_mpi_release (value);
396   e = GNUNET_MQ_msg_extra (msg,
397                            product_length,
398                            GNUNET_MESSAGE_TYPE_SCALARPRODUCT_RESULT);
399   msg->status = htonl (GNUNET_SCALARPRODUCT_STATUS_SUCCESS);
400   msg->range = htonl (range);
401   msg->product_length = htonl (product_length);
402   if (NULL != product_exported)
403   {
404     GNUNET_memcpy (&msg[1],
405             product_exported,
406             product_length);
407     GNUNET_free (product_exported);
408   }
409   GNUNET_MQ_send (s->client_mq,
410                   e);
411   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
412               "Sent result to client, session %s has ended!\n",
413               GNUNET_h2s (&s->session_id));
414 }
415
416
417
418 /**
419  * Function called whenever a channel is destroyed.  Should clean up
420  * any associated state.
421  *
422  * It must NOT call #GNUNET_CADET_channel_destroy() on the channel.
423  *
424  * @param cls our `struct AliceServiceSession`
425  * @param channel connection to the other end (henceforth invalid)
426  */
427 static void
428 cb_channel_destruction (void *cls,
429                         const struct GNUNET_CADET_Channel *channel)
430 {
431   struct AliceServiceSession *s = cls;
432
433   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
434               "Peer disconnected, terminating session %s with peer %s\n",
435               GNUNET_h2s (&s->session_id),
436               GNUNET_i2s (&s->peer));
437   if (GNUNET_SCALARPRODUCT_STATUS_ACTIVE == s->status)
438   {
439     /* We didn't get an answer yet, fail with error */
440     s->status = GNUNET_SCALARPRODUCT_STATUS_FAILURE;
441     prepare_client_end_notification (s);
442   }
443   s->channel = NULL;
444 }
445
446
447 /**
448  * Computes the square sum over a vector of a given length.
449  *
450  * @param vector the vector to compute over
451  * @param length the length of the vector
452  * @return an MPI value containing the calculated sum, never NULL
453  */
454 static gcry_mpi_t
455 compute_square_sum_mpi_elements (const struct MpiElement *vector,
456                                  uint32_t length)
457 {
458   gcry_mpi_t elem;
459   gcry_mpi_t sum;
460   uint32_t i;
461
462   GNUNET_assert (NULL != (sum = gcry_mpi_new (0)));
463   GNUNET_assert (NULL != (elem = gcry_mpi_new (0)));
464   for (i = 0; i < length; i++)
465   {
466     gcry_mpi_mul (elem, vector[i].value, vector[i].value);
467     gcry_mpi_add (sum, sum, elem);
468   }
469   gcry_mpi_release (elem);
470   return sum;
471 }
472
473
474 /**
475  * Computes the square sum over a vector of a given length.
476  *
477  * @param vector the vector to compute over
478  * @param length the length of the vector
479  * @return an MPI value containing the calculated sum, never NULL
480  */
481 static gcry_mpi_t
482 compute_square_sum (const gcry_mpi_t *vector,
483                     uint32_t length)
484 {
485   gcry_mpi_t elem;
486   gcry_mpi_t sum;
487   uint32_t i;
488
489   GNUNET_assert (NULL != (sum = gcry_mpi_new (0)));
490   GNUNET_assert (NULL != (elem = gcry_mpi_new (0)));
491   for (i = 0; i < length; i++)
492   {
493     gcry_mpi_mul (elem, vector[i], vector[i]);
494     gcry_mpi_add (sum, sum, elem);
495   }
496   gcry_mpi_release (elem);
497   return sum;
498 }
499
500
501 /**
502  * Compute our scalar product, done by Alice
503  *
504  * @param session the session associated with this computation
505  * @return product as MPI, never NULL
506  */
507 static gcry_mpi_t
508 compute_scalar_product (struct AliceServiceSession *session)
509 {
510   uint32_t count;
511   gcry_mpi_t t;
512   gcry_mpi_t u;
513   gcry_mpi_t u_prime;
514   gcry_mpi_t p;
515   gcry_mpi_t p_prime;
516   gcry_mpi_t tmp;
517   gcry_mpi_t r[session->used_element_count];
518   gcry_mpi_t r_prime[session->used_element_count];
519   gcry_mpi_t s;
520   gcry_mpi_t s_prime;
521   unsigned int i;
522
523   count = session->used_element_count;
524   // due to the introduced static offset S, we now also have to remove this
525   // from the E(a_pi)(+)E(-b_pi-r_pi) and E(a_qi)(+)E(-r_qi) twice each,
526   // the result is E((S + a_pi) + (S -b_pi-r_pi)) and E(S + a_qi + S - r_qi)
527   for (i = 0; i < count; i++)
528   {
529     r[i] = gcry_mpi_new (0);
530     GNUNET_CRYPTO_paillier_decrypt (&my_privkey,
531                                     &my_pubkey,
532                                     &session->r[i],
533                                     r[i]);
534     gcry_mpi_sub (r[i],
535                   r[i],
536                   my_offset);
537     gcry_mpi_sub (r[i],
538                   r[i],
539                   my_offset);
540     r_prime[i] = gcry_mpi_new (0);
541     GNUNET_CRYPTO_paillier_decrypt (&my_privkey,
542                                     &my_pubkey,
543                                     &session->r_prime[i],
544                                     r_prime[i]);
545     gcry_mpi_sub (r_prime[i],
546                   r_prime[i],
547                   my_offset);
548     gcry_mpi_sub (r_prime[i],
549                   r_prime[i],
550                   my_offset);
551   }
552
553   // calculate t = sum(ai)
554   t = compute_square_sum_mpi_elements (session->sorted_elements,
555                                        count);
556   // calculate U
557   u = gcry_mpi_new (0);
558   tmp = compute_square_sum (r, count);
559   gcry_mpi_sub (u, u, tmp);
560   gcry_mpi_release (tmp);
561
562   //calculate U'
563   u_prime = gcry_mpi_new (0);
564   tmp = compute_square_sum (r_prime, count);
565   gcry_mpi_sub (u_prime, u_prime, tmp);
566
567   GNUNET_assert (p = gcry_mpi_new (0));
568   GNUNET_assert (p_prime = gcry_mpi_new (0));
569   GNUNET_assert (s = gcry_mpi_new (0));
570   GNUNET_assert (s_prime = gcry_mpi_new (0));
571
572   // compute P
573   GNUNET_CRYPTO_paillier_decrypt (&my_privkey,
574                                   &my_pubkey,
575                                   &session->s,
576                                   s);
577   GNUNET_CRYPTO_paillier_decrypt (&my_privkey,
578                                   &my_pubkey,
579                                   &session->s_prime,
580                                   s_prime);
581
582   // compute P
583   gcry_mpi_add (p, s, t);
584   gcry_mpi_add (p, p, u);
585
586   // compute P'
587   gcry_mpi_add (p_prime, s_prime, t);
588   gcry_mpi_add (p_prime, p_prime, u_prime);
589
590   gcry_mpi_release (t);
591   gcry_mpi_release (u);
592   gcry_mpi_release (u_prime);
593   gcry_mpi_release (s);
594   gcry_mpi_release (s_prime);
595
596   // compute product
597   gcry_mpi_sub (p, p, p_prime);
598   gcry_mpi_release (p_prime);
599   tmp = gcry_mpi_set_ui (tmp, 2);
600   gcry_mpi_div (p, NULL, p, tmp, 0);
601
602   gcry_mpi_release (tmp);
603   for (i = 0; i < count; i++)
604   {
605     gcry_mpi_release (session->sorted_elements[i].value);
606     gcry_mpi_release (r[i]);
607     gcry_mpi_release (r_prime[i]);
608   }
609   GNUNET_free (session->sorted_elements);
610   session->sorted_elements = NULL;
611   GNUNET_free (session->r);
612   session->r = NULL;
613   GNUNET_free (session->r_prime);
614   session->r_prime = NULL;
615
616   return p;
617 }
618
619
620 /**
621  * Check a multipart chunk of a response we got from another service
622  * we wanted to calculate a scalarproduct with.
623  *
624  * @param cls the `struct AliceServiceSession`
625  * @param msg the actual message
626  * @return #GNUNET_OK to keep the connection open,
627  *         #GNUNET_SYSERR to close it (signal serious error)
628  */
629 static int
630 check_bobs_cryptodata_multipart (void *cls,
631                                  const struct BobCryptodataMultipartMessage *msg)
632 {
633   struct AliceServiceSession *s = cls;
634   uint32_t contained;
635   size_t msg_size;
636   size_t required_size;
637
638   msg_size = ntohs (msg->header.size);
639   contained = ntohl (msg->contained_element_count);
640   required_size = sizeof (struct BobCryptodataMultipartMessage)
641     + 2 * contained * sizeof (struct GNUNET_CRYPTO_PaillierCiphertext);
642   if ( (required_size != msg_size) ||
643        (s->cadet_received_element_count + contained > s->used_element_count) )
644   {
645     GNUNET_break (0);
646     return GNUNET_SYSERR;
647   }
648   return GNUNET_OK;
649 }
650
651 /**
652  * Handle a multipart chunk of a response we got from another service
653  * we wanted to calculate a scalarproduct with.
654  *
655  * @param cls the `struct AliceServiceSession`
656  * @param msg the actual message
657  */
658 static void
659 handle_bobs_cryptodata_multipart (void *cls,
660                                   const struct BobCryptodataMultipartMessage *msg)
661 {
662   struct AliceServiceSession *s = cls;
663   const struct GNUNET_CRYPTO_PaillierCiphertext *payload;
664   size_t i;
665   uint32_t contained;
666
667   contained = ntohl (msg->contained_element_count);
668   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
669               "Received %u additional crypto values from Bob\n",
670               (unsigned int) contained);
671
672   payload = (const struct GNUNET_CRYPTO_PaillierCiphertext *) &msg[1];
673   /* Convert each k[][perm] to its MPI_value */
674   for (i = 0; i < contained; i++)
675   {
676     GNUNET_memcpy (&s->r[s->cadet_received_element_count + i],
677                    &payload[2 * i],
678                    sizeof (struct GNUNET_CRYPTO_PaillierCiphertext));
679     GNUNET_memcpy (&s->r_prime[s->cadet_received_element_count + i],
680                    &payload[2 * i],
681                    sizeof (struct GNUNET_CRYPTO_PaillierCiphertext));
682   }
683   s->cadet_received_element_count += contained;
684   GNUNET_CADET_receive_done (s->channel);
685   if (s->cadet_received_element_count != s->used_element_count)
686     return; /* more to come */
687
688   s->product = compute_scalar_product (s);
689   transmit_client_response (s);
690 }
691
692
693 /**
694  * Check a response we got from another service we wanted to
695  * calculate a scalarproduct with.
696  *
697  * @param cls our `struct AliceServiceSession`
698  * @param message the actual message
699  * @return #GNUNET_OK to keep the connection open,
700  *         #GNUNET_SYSERR to close it (we are done)
701  */
702 static int
703 check_bobs_cryptodata_message (void *cls,
704                                const struct BobCryptodataMessage *msg)
705 {
706   struct AliceServiceSession *s = cls;
707   uint32_t contained;
708   uint16_t msg_size;
709   size_t required_size;
710
711   msg_size = ntohs (msg->header.size);
712   contained = ntohl (msg->contained_element_count);
713   required_size = sizeof (struct BobCryptodataMessage)
714     + 2 * contained * sizeof (struct GNUNET_CRYPTO_PaillierCiphertext)
715     + 2 * sizeof (struct GNUNET_CRYPTO_PaillierCiphertext);
716   if ( (msg_size != required_size) ||
717        (contained > UINT16_MAX) ||
718        (s->used_element_count < contained) )
719   {
720     GNUNET_break_op (0);
721     return GNUNET_SYSERR;
722   }
723   if (NULL == s->sorted_elements)
724   {
725     /* we're not ready yet, how can Bob be? */
726     GNUNET_break_op (0);
727     return GNUNET_SYSERR;
728   }
729   if (s->total != s->client_received_element_count)
730   {
731     /* we're not ready yet, how can Bob be? */
732     GNUNET_break_op (0);
733     return GNUNET_SYSERR;
734   }
735   return GNUNET_OK;
736 }
737
738
739 /**
740  * Handle a response we got from another service we wanted to
741  * calculate a scalarproduct with.
742  *
743  * @param cls our `struct AliceServiceSession`
744  * @param msg the actual message
745  */
746 static void
747 handle_bobs_cryptodata_message (void *cls,
748                                 const struct BobCryptodataMessage *msg)
749 {
750   struct AliceServiceSession *s = cls;
751   const struct GNUNET_CRYPTO_PaillierCiphertext *payload;
752   uint32_t i;
753   uint32_t contained;
754
755   contained = ntohl (msg->contained_element_count);
756   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
757               "Received %u crypto values from Bob\n",
758               (unsigned int) contained);
759   payload = (const struct GNUNET_CRYPTO_PaillierCiphertext *) &msg[1];
760   GNUNET_memcpy (&s->s,
761                  &payload[0],
762                  sizeof (struct GNUNET_CRYPTO_PaillierCiphertext));
763   GNUNET_memcpy (&s->s_prime,
764                  &payload[1],
765                  sizeof (struct GNUNET_CRYPTO_PaillierCiphertext));
766   payload = &payload[2];
767
768   s->r = GNUNET_new_array (s->used_element_count,
769                            struct GNUNET_CRYPTO_PaillierCiphertext);
770   s->r_prime = GNUNET_new_array (s->used_element_count,
771                                  struct GNUNET_CRYPTO_PaillierCiphertext);
772   for (i = 0; i < contained; i++)
773   {
774     GNUNET_memcpy (&s->r[i],
775                    &payload[2 * i],
776                    sizeof (struct GNUNET_CRYPTO_PaillierCiphertext));
777     GNUNET_memcpy (&s->r_prime[i],
778                    &payload[2 * i + 1],
779                    sizeof (struct GNUNET_CRYPTO_PaillierCiphertext));
780   }
781   s->cadet_received_element_count = contained;
782   GNUNET_CADET_receive_done (s->channel);
783
784   if (s->cadet_received_element_count != s->used_element_count)
785   {
786     /* More to come */
787     return;
788   }
789   s->product = compute_scalar_product (s);
790   transmit_client_response (s);
791 }
792
793
794 /**
795  * Iterator to copy over messages from the hash map
796  * into an array for sorting.
797  *
798  * @param cls the `struct AliceServiceSession *`
799  * @param key the key (unused)
800  * @param value the `struct GNUNET_SCALARPRODUCT_Element *`
801  */
802 static int
803 copy_element_cb (void *cls,
804                  const struct GNUNET_HashCode *key,
805                  void *value)
806 {
807   struct AliceServiceSession *s = cls;
808   struct GNUNET_SCALARPRODUCT_Element *e = value;
809   gcry_mpi_t mval;
810   int64_t val;
811
812   mval = gcry_mpi_new (0);
813   val = (int64_t) GNUNET_ntohll (e->value);
814   if (0 > val)
815     gcry_mpi_sub_ui (mval, mval, -val);
816   else
817     gcry_mpi_add_ui (mval, mval, val);
818   s->sorted_elements [s->used_element_count].value = mval;
819   s->sorted_elements [s->used_element_count].key = &e->key;
820   s->used_element_count++;
821   return GNUNET_OK;
822 }
823
824
825 /**
826  * Compare two `struct MpiValue`s by key for sorting.
827  *
828  * @param a pointer to first `struct MpiValue *`
829  * @param b pointer to first `struct MpiValue *`
830  * @return -1 for a < b, 0 for a=b, 1 for a > b.
831  */
832 static int
833 element_cmp (const void *a,
834              const void *b)
835 {
836   const struct MpiElement *ma = a;
837   const struct MpiElement *mb = b;
838
839   return GNUNET_CRYPTO_hash_cmp (ma->key,
840                                  mb->key);
841 }
842
843
844 /**
845  * Maximum number of elements we can put into a single cryptodata
846  * message
847  */
848 #define ELEMENT_CAPACITY ((GNUNET_CONSTANTS_MAX_CADET_MESSAGE_SIZE - 1 - sizeof (struct AliceCryptodataMessage)) / sizeof (struct GNUNET_CRYPTO_PaillierCiphertext))
849
850
851 /**
852  * Send the cryptographic data from Alice to Bob.
853  * Does nothing if we already transferred all elements.
854  *
855  * @param s the associated service session
856  */
857 static void
858 send_alices_cryptodata_message (struct AliceServiceSession *s)
859 {
860   struct AliceCryptodataMessage *msg;
861   struct GNUNET_MQ_Envelope *e;
862   struct GNUNET_CRYPTO_PaillierCiphertext *payload;
863   unsigned int i;
864   uint32_t todo_count;
865   gcry_mpi_t a;
866   uint32_t off;
867
868   s->sorted_elements
869     = GNUNET_malloc (GNUNET_CONTAINER_multihashmap_size (s->intersected_elements) *
870                      sizeof (struct MpiElement));
871   s->used_element_count = 0;
872   GNUNET_CONTAINER_multihashmap_iterate (s->intersected_elements,
873                                          &copy_element_cb,
874                                          s);
875   LOG (GNUNET_ERROR_TYPE_DEBUG,
876        "Finished intersection, %d items remain\n",
877        s->used_element_count);
878   qsort (s->sorted_elements,
879          s->used_element_count,
880          sizeof (struct MpiElement),
881          &element_cmp);
882   off = 0;
883   while (off < s->used_element_count)
884   {
885     todo_count = s->used_element_count - off;
886     if (todo_count > ELEMENT_CAPACITY)
887       todo_count = ELEMENT_CAPACITY;
888     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
889                 "Sending %u/%u crypto values to Bob\n",
890                 (unsigned int) todo_count,
891                 (unsigned int) s->used_element_count);
892
893     e = GNUNET_MQ_msg_extra (msg,
894                              todo_count * sizeof (struct GNUNET_CRYPTO_PaillierCiphertext),
895                              GNUNET_MESSAGE_TYPE_SCALARPRODUCT_ALICE_CRYPTODATA);
896     msg->contained_element_count = htonl (todo_count);
897     payload = (struct GNUNET_CRYPTO_PaillierCiphertext *) &msg[1];
898     a = gcry_mpi_new (0);
899     for (i = off; i < off + todo_count; i++)
900     {
901       gcry_mpi_add (a,
902                     s->sorted_elements[i].value,
903                     my_offset);
904       GNUNET_assert (3 ==
905                      GNUNET_CRYPTO_paillier_encrypt (&my_pubkey,
906                                                      a,
907                                                      3,
908                                                      &payload[i - off]));
909     }
910     gcry_mpi_release (a);
911     off += todo_count;
912     GNUNET_MQ_send (s->cadet_mq,
913                     e);
914   }
915 }
916
917
918 /**
919  * Callback for set operation results. Called for each element
920  * that should be removed from the result set, and then once
921  * to indicate that the set intersection operation is done.
922  *
923  * @param cls closure with the `struct AliceServiceSession`
924  * @param element a result element, only valid if status is #GNUNET_SET_STATUS_OK
925  * @param current_size current set size
926  * @param status what has happened with the set intersection?
927  */
928 static void
929 cb_intersection_element_removed (void *cls,
930                                  const struct GNUNET_SET_Element *element,
931                                  uint64_t current_size,
932                                  enum GNUNET_SET_Status status)
933 {
934   struct AliceServiceSession *s = cls;
935   struct GNUNET_SCALARPRODUCT_Element *se;
936
937   switch (status)
938   {
939   case GNUNET_SET_STATUS_OK:
940     /* this element has been removed from the set */
941     se = GNUNET_CONTAINER_multihashmap_get (s->intersected_elements,
942                                             element->data);
943     GNUNET_assert (NULL != se);
944     LOG (GNUNET_ERROR_TYPE_DEBUG,
945          "Intersection removed element with key %s and value %lld\n",
946          GNUNET_h2s (&se->key),
947          (long long) GNUNET_ntohll (se->value));
948     GNUNET_assert (GNUNET_YES ==
949                    GNUNET_CONTAINER_multihashmap_remove (s->intersected_elements,
950                                                          element->data,
951                                                          se));
952     GNUNET_free (se);
953     return;
954   case GNUNET_SET_STATUS_DONE:
955     s->intersection_op = NULL;
956     if (NULL != s->intersection_set)
957     {
958       GNUNET_SET_destroy (s->intersection_set);
959       s->intersection_set = NULL;
960     }
961     send_alices_cryptodata_message (s);
962     return;
963   case GNUNET_SET_STATUS_HALF_DONE:
964     /* unexpected for intersection */
965     GNUNET_break (0);
966     return;
967   case GNUNET_SET_STATUS_FAILURE:
968     /* unhandled status code */
969     LOG (GNUNET_ERROR_TYPE_DEBUG,
970          "Set intersection failed!\n");
971     if (NULL != s->intersection_listen)
972     {
973       GNUNET_SET_listen_cancel (s->intersection_listen);
974       s->intersection_listen = NULL;
975     }
976     s->intersection_op = NULL;
977     if (NULL != s->intersection_set)
978     {
979       GNUNET_SET_destroy (s->intersection_set);
980       s->intersection_set = NULL;
981     }
982     s->status = GNUNET_SCALARPRODUCT_STATUS_FAILURE;
983     prepare_client_end_notification (s);
984     return;
985   default:
986     GNUNET_break (0);
987     return;
988   }
989 }
990
991
992 /**
993  * Called when another peer wants to do a set operation with the
994  * local peer. If a listen error occurs, the @a request is NULL.
995  *
996  * @param cls closure with the `struct AliceServiceSession *`
997  * @param other_peer the other peer
998  * @param context_msg message with application specific information from
999  *        the other peer
1000  * @param request request from the other peer (never NULL), use GNUNET_SET_accept()
1001  *        to accept it, otherwise the request will be refused
1002  *        Note that we can't just return value from the listen callback,
1003  *        as it is also necessary to specify the set we want to do the
1004  *        operation with, whith sometimes can be derived from the context
1005  *        message. It's necessary to specify the timeout.
1006  */
1007 static void
1008 cb_intersection_request_alice (void *cls,
1009                                const struct GNUNET_PeerIdentity *other_peer,
1010                                const struct GNUNET_MessageHeader *context_msg,
1011                                struct GNUNET_SET_Request *request)
1012 {
1013   struct AliceServiceSession *s = cls;
1014
1015   if (0 != memcmp (other_peer,
1016                    &s->peer,
1017                    sizeof (struct GNUNET_PeerIdentity)))
1018   {
1019     GNUNET_break_op (0);
1020     return;
1021   }
1022   s->intersection_op
1023     = GNUNET_SET_accept (request,
1024                          GNUNET_SET_RESULT_REMOVED,
1025                          (struct GNUNET_SET_Option[]) {{ 0 }},
1026                          &cb_intersection_element_removed,
1027                          s);
1028   if (NULL == s->intersection_op)
1029   {
1030     GNUNET_break (0);
1031     s->status = GNUNET_SCALARPRODUCT_STATUS_FAILURE;
1032     prepare_client_end_notification (s);
1033     return;
1034   }
1035   if (GNUNET_OK !=
1036       GNUNET_SET_commit (s->intersection_op,
1037                          s->intersection_set))
1038   {
1039     GNUNET_break (0);
1040     s->status = GNUNET_SCALARPRODUCT_STATUS_FAILURE;
1041     prepare_client_end_notification (s);
1042     return;
1043   }
1044 }
1045
1046
1047 /**
1048  * Our client has finished sending us its multipart message.
1049  *
1050  * @param session the service session context
1051  */
1052 static void
1053 client_request_complete_alice (struct AliceServiceSession *s)
1054 {
1055   struct GNUNET_MQ_MessageHandler cadet_handlers[] = {
1056     GNUNET_MQ_hd_var_size (bobs_cryptodata_message,
1057                            GNUNET_MESSAGE_TYPE_SCALARPRODUCT_BOB_CRYPTODATA,
1058                            struct BobCryptodataMessage,
1059                            s),
1060     GNUNET_MQ_hd_var_size (bobs_cryptodata_multipart,
1061                            GNUNET_MESSAGE_TYPE_SCALARPRODUCT_BOB_CRYPTODATA_MULTIPART,
1062                            struct BobCryptodataMultipartMessage,
1063                            s),
1064     GNUNET_MQ_handler_end ()
1065   };
1066   struct ServiceRequestMessage *msg;
1067   struct GNUNET_MQ_Envelope *e;
1068
1069   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1070               "Creating new channel for session with key %s.\n",
1071               GNUNET_h2s (&s->session_id));
1072   s->channel
1073     = GNUNET_CADET_channel_create (my_cadet,
1074                                    s,
1075                                    &s->peer,
1076                                    &s->session_id,
1077                                    GNUNET_CADET_OPTION_RELIABLE,
1078                                    NULL,
1079                                    &cb_channel_destruction,
1080                                    cadet_handlers);
1081   if (NULL == s->channel)
1082   {
1083     s->status = GNUNET_SCALARPRODUCT_STATUS_FAILURE;
1084     prepare_client_end_notification (s);
1085     return;
1086   }
1087   s->cadet_mq = GNUNET_CADET_get_mq (s->channel);
1088   s->intersection_listen
1089     = GNUNET_SET_listen (cfg,
1090                          GNUNET_SET_OPERATION_INTERSECTION,
1091                          &s->session_id,
1092                          &cb_intersection_request_alice,
1093                          s);
1094   if (NULL == s->intersection_listen)
1095   {
1096     s->status = GNUNET_SCALARPRODUCT_STATUS_FAILURE;
1097     GNUNET_CADET_channel_destroy (s->channel);
1098     s->channel = NULL;
1099     prepare_client_end_notification (s);
1100     return;
1101   }
1102
1103   e = GNUNET_MQ_msg (msg,
1104                      GNUNET_MESSAGE_TYPE_SCALARPRODUCT_SESSION_INITIALIZATION);
1105   msg->session_id = s->session_id;
1106   msg->public_key = my_pubkey;
1107   GNUNET_MQ_send (s->cadet_mq,
1108                   e);
1109 }
1110
1111
1112 /**
1113  * We're receiving additional set data. Check if
1114  * @a msg is well-formed.
1115  *
1116  * @param cls client identification of the client
1117  * @param msg the actual message
1118  * @return #GNUNET_OK if @a msg is well-formed
1119  */
1120 static int
1121 check_alice_client_message_multipart (void *cls,
1122                                       const struct ComputationBobCryptodataMultipartMessage *msg)
1123 {
1124   struct AliceServiceSession *s = cls;
1125   uint32_t contained_count;
1126   uint16_t msize;
1127
1128   msize = ntohs (msg->header.size);
1129   contained_count = ntohl (msg->element_count_contained);
1130   if ( (msize != (sizeof (struct ComputationBobCryptodataMultipartMessage) +
1131                   contained_count * sizeof (struct GNUNET_SCALARPRODUCT_Element))) ||
1132        (0 == contained_count) ||
1133        (s->total == s->client_received_element_count) ||
1134        (s->total < s->client_received_element_count + contained_count) )
1135   {
1136     GNUNET_break_op (0);
1137     return GNUNET_SYSERR;
1138   }
1139   return GNUNET_OK;
1140 }
1141
1142
1143 /**
1144  * We're receiving additional set data. Add it to our
1145  * set and if we are done, initiate the transaction.
1146  *
1147  * @param cls client identification of the client
1148  * @param msg the actual message
1149  */
1150 static void
1151 handle_alice_client_message_multipart (void *cls,
1152                                        const struct ComputationBobCryptodataMultipartMessage *msg)
1153 {
1154   struct AliceServiceSession *s = cls;
1155   uint32_t contained_count;
1156   const struct GNUNET_SCALARPRODUCT_Element *elements;
1157   struct GNUNET_SET_Element set_elem;
1158   struct GNUNET_SCALARPRODUCT_Element *elem;
1159
1160   contained_count = ntohl (msg->element_count_contained);
1161   s->client_received_element_count += contained_count;
1162   elements = (const struct GNUNET_SCALARPRODUCT_Element *) &msg[1];
1163   for (uint32_t i = 0; i < contained_count; i++)
1164   {
1165     elem = GNUNET_new (struct GNUNET_SCALARPRODUCT_Element);
1166     GNUNET_memcpy (elem,
1167                    &elements[i],
1168                    sizeof (struct GNUNET_SCALARPRODUCT_Element));
1169     if (GNUNET_SYSERR ==
1170         GNUNET_CONTAINER_multihashmap_put (s->intersected_elements,
1171                                            &elem->key,
1172                                            elem,
1173                                            GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
1174     {
1175       GNUNET_break (0);
1176       GNUNET_free (elem);
1177       continue;
1178     }
1179     set_elem.data = &elem->key;
1180     set_elem.size = sizeof (elem->key);
1181     set_elem.element_type = 0;
1182     GNUNET_SET_add_element (s->intersection_set,
1183                             &set_elem,
1184                             NULL, NULL);
1185     s->used_element_count++;
1186   }
1187   GNUNET_SERVICE_client_continue (s->client);
1188   if (s->total != s->client_received_element_count)
1189   {
1190     /* more to come */
1191     return;
1192   }
1193   client_request_complete_alice (s);
1194 }
1195
1196
1197 /**
1198  * Handler for Alice's client request message.
1199  * Check that @a msg is well-formed.
1200  *
1201  * @param cls identification of the client
1202  * @param msg the actual message
1203  * @return #GNUNET_OK if @a msg is well-formed
1204  */
1205 static int
1206 check_alice_client_message (void *cls,
1207                             const struct AliceComputationMessage *msg)
1208 {
1209   struct AliceServiceSession *s = cls;
1210   uint16_t msize;
1211   uint32_t total_count;
1212   uint32_t contained_count;
1213
1214   if (NULL != s->intersected_elements)
1215   {
1216     /* only one concurrent session per client connection allowed,
1217        simplifies logic a lot... */
1218     GNUNET_break (0);
1219     return GNUNET_SYSERR;
1220   }
1221   msize = ntohs (msg->header.size);
1222   total_count = ntohl (msg->element_count_total);
1223   contained_count = ntohl (msg->element_count_contained);
1224   if ( (0 == total_count) ||
1225        (0 == contained_count) ||
1226        (msize != (sizeof (struct AliceComputationMessage) +
1227                   contained_count * sizeof (struct GNUNET_SCALARPRODUCT_Element))) )
1228   {
1229     GNUNET_break_op (0);
1230     return GNUNET_SYSERR;
1231   }
1232   return GNUNET_OK;
1233 }
1234
1235
1236 /**
1237  * Handler for Alice's client request message.
1238  * We are doing request-initiation to compute a scalar product with a peer.
1239  *
1240  * @param cls identification of the client
1241  * @param msg the actual message
1242  */
1243 static void
1244 handle_alice_client_message (void *cls,
1245                              const struct AliceComputationMessage *msg)
1246 {
1247   struct AliceServiceSession *s = cls;
1248   uint32_t contained_count;
1249   uint32_t total_count;
1250   const struct GNUNET_SCALARPRODUCT_Element *elements;
1251   struct GNUNET_SET_Element set_elem;
1252   struct GNUNET_SCALARPRODUCT_Element *elem;
1253
1254   total_count = ntohl (msg->element_count_total);
1255   contained_count = ntohl (msg->element_count_contained);
1256   s->peer = msg->peer;
1257   s->status = GNUNET_SCALARPRODUCT_STATUS_ACTIVE;
1258   s->total = total_count;
1259   s->client_received_element_count = contained_count;
1260   s->session_id = msg->session_key;
1261   elements = (const struct GNUNET_SCALARPRODUCT_Element *) &msg[1];
1262   s->intersected_elements = GNUNET_CONTAINER_multihashmap_create (s->total,
1263                                                                   GNUNET_YES);
1264   s->intersection_set = GNUNET_SET_create (cfg,
1265                                            GNUNET_SET_OPERATION_INTERSECTION);
1266
1267   for (uint32_t i = 0; i < contained_count; i++)
1268   {
1269     if (0 == GNUNET_ntohll (elements[i].value))
1270       continue;
1271     elem = GNUNET_new (struct GNUNET_SCALARPRODUCT_Element);
1272     GNUNET_memcpy (elem,
1273             &elements[i],
1274             sizeof (struct GNUNET_SCALARPRODUCT_Element));
1275     if (GNUNET_SYSERR ==
1276         GNUNET_CONTAINER_multihashmap_put (s->intersected_elements,
1277                                            &elem->key,
1278                                            elem,
1279                                            GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
1280     {
1281       /* element with same key encountered twice! */
1282       GNUNET_break (0);
1283       GNUNET_free (elem);
1284       continue;
1285     }
1286     set_elem.data = &elem->key;
1287     set_elem.size = sizeof (elem->key);
1288     set_elem.element_type = 0;
1289     GNUNET_SET_add_element (s->intersection_set,
1290                             &set_elem,
1291                             NULL, NULL);
1292     s->used_element_count++;
1293   }
1294   GNUNET_SERVICE_client_continue (s->client);
1295   if (s->total != s->client_received_element_count)
1296   {
1297     /* wait for multipart msg */
1298     return;
1299   }
1300   client_request_complete_alice (s);
1301 }
1302
1303
1304 /**
1305  * Task run during shutdown.
1306  *
1307  * @param cls unused
1308  */
1309 static void
1310 shutdown_task (void *cls)
1311 {
1312   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1313               "Shutting down, initiating cleanup.\n");
1314   // FIXME: we have to cut our connections to CADET first!
1315   if (NULL != my_cadet)
1316   {
1317     GNUNET_CADET_disconnect (my_cadet);
1318     my_cadet = NULL;
1319   }
1320 }
1321
1322
1323 /**
1324  * A client connected.
1325  *
1326  * Setup the associated data structure.
1327  *
1328  * @param cls closure, NULL
1329  * @param client identification of the client
1330  * @param mq message queue to communicate with @a client
1331  * @return our `struct AliceServiceSession`
1332  */
1333 static void *
1334 client_connect_cb (void *cls,
1335                    struct GNUNET_SERVICE_Client *client,
1336                    struct GNUNET_MQ_Handle *mq)
1337 {
1338   struct AliceServiceSession *s;
1339
1340   s = GNUNET_new (struct AliceServiceSession);
1341   s->client = client;
1342   s->client_mq = mq;
1343   return s;
1344 }
1345
1346
1347 /**
1348  * A client disconnected.
1349  *
1350  * Remove the associated session(s), release data structures
1351  * and cancel pending outgoing transmissions to the client.
1352  *
1353  * @param cls closure, NULL
1354  * @param client identification of the client
1355  * @param app_cls our `struct AliceServiceSession`
1356  */
1357 static void
1358 client_disconnect_cb (void *cls,
1359                       struct GNUNET_SERVICE_Client *client,
1360                       void *app_cls)
1361 {
1362   struct AliceServiceSession *s = app_cls;
1363
1364   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1365               "Client %p disconnected from us.\n",
1366               client);
1367   s->client = NULL;
1368   s->client_mq = NULL;
1369   destroy_service_session (s);
1370 }
1371
1372
1373 /**
1374  * Initialization of the program and message handlers
1375  *
1376  * @param cls closure
1377  * @param c configuration to use
1378  * @param service the initialized service
1379  */
1380 static void
1381 run (void *cls,
1382      const struct GNUNET_CONFIGURATION_Handle *c,
1383      struct GNUNET_SERVICE_Handle *service)
1384 {
1385   cfg = c;
1386   /*
1387     offset has to be sufficiently small to allow computation of:
1388     m1+m2 mod n == (S + a) + (S + b) mod n,
1389     if we have more complex operations, this factor needs to be lowered */
1390   my_offset = gcry_mpi_new (GNUNET_CRYPTO_PAILLIER_BITS / 3);
1391   gcry_mpi_set_bit (my_offset,
1392                     GNUNET_CRYPTO_PAILLIER_BITS / 3);
1393   GNUNET_CRYPTO_paillier_create (&my_pubkey,
1394                                  &my_privkey);
1395   my_cadet = GNUNET_CADET_connect (cfg);
1396   GNUNET_SCHEDULER_add_shutdown (&shutdown_task,
1397                                  NULL);
1398   if (NULL == my_cadet)
1399   {
1400     GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1401                 _("Connect to CADET failed\n"));
1402     GNUNET_SCHEDULER_shutdown ();
1403     return;
1404   }
1405 }
1406
1407
1408 /**
1409  * Define "main" method using service macro.
1410  */
1411 GNUNET_SERVICE_MAIN
1412 ("scalarproduct-alice",
1413  GNUNET_SERVICE_OPTION_NONE,
1414  &run,
1415  &client_connect_cb,
1416  &client_disconnect_cb,
1417  NULL,
1418  GNUNET_MQ_hd_var_size (alice_client_message,
1419                         GNUNET_MESSAGE_TYPE_SCALARPRODUCT_CLIENT_TO_ALICE,
1420                         struct AliceComputationMessage,
1421                         NULL),
1422  GNUNET_MQ_hd_var_size (alice_client_message_multipart,
1423                         GNUNET_MESSAGE_TYPE_SCALARPRODUCT_CLIENT_MULTIPART_ALICE,
1424                         struct ComputationBobCryptodataMultipartMessage,
1425                         NULL),
1426  GNUNET_MQ_handler_end ());
1427
1428
1429 /* end of gnunet-service-scalarproduct_alice.c */