src/nse/gnunet-service-nse.c

   1 /*
   2   This file is part of GNUnet.
   3   (C) 2009, 2010, 2011 Christian Grothoff (and other contributing authors)
   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., 59 Temple Place - Suite 330,
  18   Boston, MA 02111-1307, USA.
  19  */
  20
  21 /**
  22  * @file nse/gnunet-service-nse.c
  23  * @brief network size estimation service
  24  * @author Nathan Evans
  25  * @author Christian Grothoff
  26  *
  27  * The purpose of this service is to estimate the size of the network.
  28  * Given a specified interval, each peer hashes the most recent
  29  * timestamp which is evenly divisible by that interval.  This hash is
  30  * compared in distance to the peer identity to choose an offset.  The
  31  * closer the peer identity to the hashed timestamp, the earlier the
  32  * peer sends out a "nearest peer" message.  The closest peer's
  33  * message should thus be received before any others, which stops
  34  * those peer from sending their messages at a later duration.  So
  35  * every peer should receive the same nearest peer message, and from
  36  * this can calculate the expected number of peers in the network.
  37  *
  38  * TODO:
  39  * - generate proof-of-work asynchronously, store it on disk & load it back
  40  * - handle messages for future round (one into the future, see FIXME)
  41  */
  42 #include "platform.h"
  43 #include "gnunet_client_lib.h"
  44 #include "gnunet_constants.h"
  45 #include "gnunet_container_lib.h"
  46 #include "gnunet_protocols.h"
  47 #include "gnunet_signatures.h"
  48 #include "gnunet_service_lib.h"
  49 #include "gnunet_server_lib.h"
  50 #include "gnunet_statistics_service.h"
  51 #include "gnunet_core_service.h"
  52 #include "gnunet_time_lib.h"
  53 #include "gnunet_nse_service.h"
  54 #include "nse.h"
  55
  56 /**
  57  * Over how many values do we calculate the weighted average?
  58  */
  59 #define HISTORY_SIZE 8
  60
  61 /**
  62  * Size of the queue to core.
  63  */
  64 #define CORE_QUEUE_SIZE 2
  65
  66 /**
  67  * Message priority to use.
  68  */
  69 #define NSE_PRIORITY 5
  70
  71 /**
  72  * Amount of work required (W-bit collisions) for NSE proofs, in collision-bits.
  73  */
  74 #define NSE_WORK_REQUIRED 0
  75
  76 /**
  77  * Interval for sending network size estimation flood requests.
  78  */
  79 #define GNUNET_NSE_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 60)
  80
  81
  82 /**
  83  * Per-peer information.
  84  */
  85 struct NSEPeerEntry
  86 {
  87
  88   /**
  89    * Pending message for this peer.
  90    */
  91   struct GNUNET_MessageHeader *pending_message;
  92
  93   /**
  94    * Core handle for sending messages to this peer.
  95    */
  96   struct GNUNET_CORE_TransmitHandle *th;
  97
  98   /**
  99    * What is the identity of the peer?
 100    */
 101   struct GNUNET_PeerIdentity id;
 102
 103   /**
 104    * Task scheduled to send message to this peer.
 105    */
 106   GNUNET_SCHEDULER_TaskIdentifier transmit_task;
 107
 108   /**
 109    * Did we receive or send a message about the previous round
 110    * to this peer yet?
 111    */
 112   int previous_round;
 113 };
 114
 115
 116 /**
 117  * Network size estimate reply; sent when "this"
 118  * peer's timer has run out before receiving a
 119  * valid reply from another peer.
 120  */
 121 struct GNUNET_NSE_FloodMessage
 122 {
 123   /**
 124    * Type: GNUNET_MESSAGE_TYPE_NSE_P2P_FLOOD
 125    */
 126   struct GNUNET_MessageHeader header;
 127
 128   /**
 129    * Number of hops this message has taken so far.
 130    */
 131   uint32_t hop_count;
 132
 133   /**
 134    * Purpose.
 135    */
 136   struct GNUNET_CRYPTO_RsaSignaturePurpose purpose;
 137
 138   /**
 139    * The current timestamp value (which all
 140    * peers should agree on).
 141    */
 142   struct GNUNET_TIME_AbsoluteNBO timestamp;
 143
 144   /**
 145    * Number of matching bits between the hash
 146    * of timestamp and the initiator's public
 147    * key.
 148    */
 149   uint32_t matching_bits;
 150
 151   /**
 152    * Public key of the originator.
 153    */
 154   struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded pkey;
 155
 156   /**
 157    * Proof of work, causing leading zeros when hashed with pkey.
 158    */
 159   uint64_t proof_of_work;
 160
 161   /**
 162    * Signature (over range specified in purpose).
 163    */
 164   struct GNUNET_CRYPTO_RsaSignature signature;
 165 };
 166
 167
 168 /**
 169  * Handle to our current configuration.
 170  */
 171 static const struct GNUNET_CONFIGURATION_Handle *cfg;
 172
 173 /**
 174  * Handle to the statistics service.
 175  */
 176 static struct GNUNET_STATISTICS_Handle *stats;
 177
 178 /**
 179  * Handle to the core service.
 180  */
 181 static struct GNUNET_CORE_Handle *coreAPI;
 182
 183 /**
 184  * Map of all connected peers.
 185  */
 186 static struct GNUNET_CONTAINER_MultiHashMap *peers;
 187
 188 /**
 189  * The current network size estimate.  Number of bits matching on
 190  * average thus far.
 191  */
 192 static double current_size_estimate;
 193
 194 /**
 195  * The standard deviation of the last HISTORY_SIZE network
 196  * size estimates.
 197  */
 198 static double current_std_dev = NAN;
 199
 200 /**
 201  * Current hop counter estimate (estimate for network diameter).
 202  */
 203 static uint32_t hop_count_max;
 204
 205 /**
 206  * Array of recent size estimate messages.
 207  */
 208 static struct GNUNET_NSE_FloodMessage size_estimate_messages[HISTORY_SIZE];
 209
 210 /**
 211  * Index of most recent estimate.
 212  */
 213 static unsigned int estimate_index;
 214
 215 /**
 216  * Task scheduled to update our flood message for the next round.
 217  */
 218 static GNUNET_SCHEDULER_TaskIdentifier flood_task;
 219
 220 /**
 221  * Notification context, simplifies client broadcasts.
 222  */
 223 static struct GNUNET_SERVER_NotificationContext *nc;
 224
 225 /**
 226  * The next major time.
 227  */
 228 static struct GNUNET_TIME_Absolute next_timestamp;
 229
 230 /**
 231  * The current major time.
 232  */
 233 static struct GNUNET_TIME_Absolute current_timestamp;
 234
 235 /**
 236  * The public key of this peer.
 237  */
 238 static struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded my_public_key;
 239
 240 /**
 241  * The private key of this peer.
 242  */
 243 static struct GNUNET_CRYPTO_RsaPrivateKey *my_private_key;
 244
 245 /**
 246  * The peer identity of this peer.
 247  */
 248 static struct GNUNET_PeerIdentity my_identity;
 249
 250 /**
 251  * Proof of work for this peer.
 252  */
 253 static uint64_t my_proof;
 254
 255
 256 /**
 257  * Initialize a message to clients with the current network
 258  * size estimate.
 259  *
 260  * @param em message to fill in
 261  */
 262 static void
 263 setup_estimate_message (struct GNUNET_NSE_ClientMessage *em)
 264 {
 265   unsigned int i;
 266   double mean;
 267   double sum;
 268   double std_dev;
 269   double variance;
 270   double val;
 271   double weight;
 272   double sumweight;
 273   double q;
 274   double r;
 275   double temp;
 276
 277   /* Weighted incremental algorithm for stddev according to West (1979) */
 278   mean = 0.0;
 279   sum = 0.0;
 280   sumweight = 0.0;
 281   for (i=0; i<HISTORY_SIZE; i++)
 282     {
 283       val = htonl (size_estimate_messages[i].matching_bits);
 284       weight = HISTORY_SIZE - ((estimate_index + HISTORY_SIZE - i) % HISTORY_SIZE);
 285
 286       temp = weight + sumweight;
 287       q = val - mean;
 288       r = q * weight / temp;
 289       sum += sumweight * q * r;
 290       mean += r;
 291       sumweight = temp;
 292     }
 293   variance = sum / (sumweight - 1.0);
 294   GNUNET_assert (variance >= 0);
 295   std_dev = sqrt (variance);
 296   current_std_dev = std_dev;
 297   current_size_estimate = mean;
 298
 299   em->header.size
 300     = htons (sizeof(struct GNUNET_NSE_ClientMessage));
 301   em->header.type
 302     = htons (GNUNET_MESSAGE_TYPE_NSE_ESTIMATE);
 303   em->reserved = htonl (0);
 304   em->size_estimate = mean - 0.5;
 305   em->std_deviation = std_dev;
 306   GNUNET_STATISTICS_set (stats,
 307                          "Current network size estimate",
 308                          (uint64_t) pow (2, mean - 0.5), GNUNET_NO);
 309 }
 310
 311
 312 /**
 313  * Handler for START message from client, triggers an
 314  * immediate current network estimate notification.
 315  * Also, we remember the client for updates upon future
 316  * estimate measurements.
 317  *
 318  * @param cls unused
 319  * @param client who sent the message
 320  * @param message the message received
 321  */
 322 static void
 323 handle_start_message(void *cls, struct GNUNET_SERVER_Client *client,
 324                      const struct GNUNET_MessageHeader *message)
 325 {
 326   struct GNUNET_NSE_ClientMessage em;
 327 #if DEBUG_NSE
 328   GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 329              "Received START message from client\n");
 330 #endif
 331   GNUNET_SERVER_notification_context_add (nc, client);
 332   setup_estimate_message (&em);
 333   GNUNET_SERVER_notification_context_unicast (nc, client, &em.header, GNUNET_YES);
 334   GNUNET_SERVER_receive_done (client, GNUNET_OK);
 335 }
 336
 337
 338 /**
 339  * How long should we delay a message to go the given number of
 340  * matching bits?
 341  *
 342  * @param matching_bits number of matching bits to consider
 343  */
 344 static double
 345 get_matching_bits_delay (uint32_t matching_bits)
 346 {
 347   /* Calculated as: S + f/2 - (f / pi) * (atan(x - p'))*/
 348   // S is next_timestamp
 349   // f is frequency (GNUNET_NSE_INTERVAL)
 350   // x is matching_bits
 351   // p' is current_size_estimate
 352   return ((double) GNUNET_NSE_INTERVAL.rel_value / (double) 2)
 353     - ((GNUNET_NSE_INTERVAL.rel_value / M_PI) * atan (matching_bits - current_size_estimate));
 354 }
 355
 356
 357 /**
 358  * What delay randomization should we apply for a given number of matching bits?
 359  *
 360  * @param matching_bits number of matching bits
 361  * @return random delay to apply
 362  */
 363 static struct GNUNET_TIME_Relative
 364 get_delay_randomization (uint32_t matching_bits)
 365 {
 366   struct GNUNET_TIME_Relative ret;
 367
 368   if (matching_bits == 0)
 369     return GNUNET_TIME_UNIT_ZERO;
 370   ret.rel_value = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
 371                                             (uint32_t) (get_matching_bits_delay (matching_bits - 1) / (double) (hop_count_max + 1)));
 372   return ret;
 373 }
 374
 375
 376 /**
 377  * Get the number of matching bits that the given timestamp has to the given peer ID.
 378  *
 379  * @param timestamp time to generate key
 380  * @param id peer identity to compare with
 381  * @return number of matching bits
 382  */
 383 static uint32_t
 384 get_matching_bits (struct GNUNET_TIME_Absolute timestamp,
 385                    const struct GNUNET_PeerIdentity *id)
 386 {
 387   GNUNET_HashCode timestamp_hash;
 388
 389   GNUNET_CRYPTO_hash (&timestamp.abs_value,
 390                       sizeof(timestamp.abs_value),
 391                       &timestamp_hash);
 392   return GNUNET_CRYPTO_hash_matching_bits (&timestamp_hash,
 393                                            &id->hashPubKey);
 394 }
 395
 396
 397 /**
 398  * Get the transmission delay that should be applied for a
 399  * particular round.
 400  *
 401  * @param round_offset -1 for the previous round (random delay between 0 and 50ms)
 402  *                      0 for the current round (based on our proximity to time key)
 403  * @return delay that should be applied
 404  */
 405 static struct GNUNET_TIME_Relative
 406 get_transmit_delay (int round_offset)
 407 {
 408   struct GNUNET_TIME_Relative ret;
 409   struct GNUNET_TIME_Absolute tgt;
 410   double dist_delay;
 411   uint32_t matching_bits;
 412
 413   switch (round_offset)
 414     {
 415     case -1:
 416       /* previous round is randomized between 0 and 50 ms */
 417       ret.rel_value = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
 418                                                 50);
 419       return ret;
 420     case 0:
 421       /* current round is based on best-known matching_bits */
 422       matching_bits = ntohl (size_estimate_messages[estimate_index].matching_bits);
 423       dist_delay = get_matching_bits_delay (matching_bits);
 424       dist_delay += get_delay_randomization (matching_bits).rel_value;
 425       ret.rel_value = (uint64_t) dist_delay;
 426       /* now consider round start time and add delay to it */
 427       tgt = GNUNET_TIME_absolute_add (current_timestamp, ret);
 428       return GNUNET_TIME_absolute_get_remaining (tgt);
 429     }
 430   GNUNET_break (0);
 431   return GNUNET_TIME_UNIT_FOREVER_REL;
 432 }
 433
 434
 435 /**
 436  * Task that triggers a NSE P2P transmission.
 437  *
 438  * @param cls the 'struct NSEPeerEntry'
 439  * @param tc scheduler context
 440  */
 441 static void
 442 transmit_task (void *cls,
 443                const struct GNUNET_SCHEDULER_TaskContext *tc);
 444
 445
 446 /**
 447  * Called when core is ready to send a message we asked for
 448  * out to the destination.
 449  *
 450  * @param cls closure (NULL)
 451  * @param size number of bytes available in buf
 452  * @param buf where the callee should write the message
 453  * @return number of bytes written to buf
 454  */
 455 static size_t
 456 transmit_ready (void *cls, size_t size, void *buf)
 457 {
 458   struct NSEPeerEntry *peer_entry = cls;
 459   unsigned int idx;
 460
 461   peer_entry->th = NULL;
 462   if (buf == NULL)
 463     {
 464       /* client disconnected */
 465       return 0;
 466     }
 467   GNUNET_assert (size >= sizeof (struct GNUNET_NSE_FloodMessage));
 468 #if DEBUG_NSE > 1
 469   GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
 470               "Sending size estimate to `%s'\n",
 471               GNUNET_i2s (&peer_entry->id));
 472 #endif
 473   idx = estimate_index;
 474   if (peer_entry->previous_round == GNUNET_YES)
 475     {
 476       idx = (idx + HISTORY_SIZE -1) % HISTORY_SIZE;
 477       peer_entry->previous_round = GNUNET_NO;
 478       peer_entry->transmit_task = GNUNET_SCHEDULER_add_delayed (get_transmit_delay (0),
 479                                                                 &transmit_task,
 480                                                                 peer_entry);
 481     }
 482   memcpy (buf,
 483           &size_estimate_messages[idx],
 484           sizeof (struct GNUNET_NSE_FloodMessage));
 485   GNUNET_STATISTICS_update (stats,
 486                             "# flood messages sent",
 487                             1,
 488                             GNUNET_NO);
 489   return sizeof (struct GNUNET_NSE_FloodMessage);
 490 }
 491
 492
 493 /**
 494  * Task that triggers a NSE P2P transmission.
 495  *
 496  * @param cls the 'struct NSEPeerEntry'
 497  * @param tc scheduler context
 498  */
 499 static void
 500 transmit_task (void *cls,
 501                const struct GNUNET_SCHEDULER_TaskContext *tc)
 502 {
 503   struct NSEPeerEntry *peer_entry = cls;
 504
 505   peer_entry->transmit_task = GNUNET_SCHEDULER_NO_TASK;
 506   peer_entry->th
 507     = GNUNET_CORE_notify_transmit_ready (coreAPI,
 508                                          GNUNET_NO,
 509                                          NSE_PRIORITY,
 510                                          GNUNET_TIME_UNIT_FOREVER_REL,
 511                                          &peer_entry->id,
 512                                          sizeof (struct GNUNET_NSE_FloodMessage),
 513                                          &transmit_ready, peer_entry);
 514 }
 515
 516
 517 /**
 518  * We've sent on our flood message or one that we received which was
 519  * validated and closer than ours.  Update the global list of recent
 520  * messages and the average.  Also re-broadcast the message to any
 521  * clients.
 522  */
 523 static void
 524 update_network_size_estimate ()
 525 {
 526   struct GNUNET_NSE_ClientMessage em;
 527
 528   setup_estimate_message (&em);
 529   GNUNET_SERVER_notification_context_broadcast (nc,
 530                                                 &em.header,
 531                                                 GNUNET_YES);
 532 }
 533
 534
 535 /**
 536  * Setup a flood message in our history array at the given
 537  * slot offset for the given timestamp.
 538  *
 539  * @param slot index to use
 540  * @param ts timestamp to use
 541  */
 542 static void
 543 setup_flood_message (unsigned int slot,
 544                      struct GNUNET_TIME_Absolute ts)
 545 {
 546   struct GNUNET_NSE_FloodMessage *fm;
 547   uint32_t matching_bits;
 548
 549   matching_bits = get_matching_bits (ts, &my_identity);
 550   fm = &size_estimate_messages[slot];
 551   fm->header.size = htons (sizeof(struct GNUNET_NSE_FloodMessage));
 552   fm->header.type = htons (GNUNET_MESSAGE_TYPE_NSE_P2P_FLOOD);
 553   fm->hop_count = htonl (0);
 554   fm->purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_NSE_SEND);
 555   fm->purpose.size = htonl (sizeof(struct GNUNET_NSE_FloodMessage)
 556                             - sizeof (struct GNUNET_MessageHeader)
 557                             - sizeof (uint32_t)
 558                             - sizeof (struct GNUNET_CRYPTO_RsaSignature));
 559   fm->matching_bits = htonl (matching_bits);
 560   fm->timestamp = GNUNET_TIME_absolute_hton (ts);
 561   fm->pkey = my_public_key;
 562   fm->proof_of_work = my_proof;
 563   GNUNET_CRYPTO_rsa_sign (my_private_key,
 564                           &fm->purpose,
 565                           &fm->signature);
 566 }
 567
 568
 569 /**
 570  * Schedule transmission for the given peer for the current round based
 571  * on what we know about the desired delay.
 572  *
 573  * @param cls unused
 574  * @param key hash of peer identity
 575  * @param value the 'struct NSEPeerEntry'
 576  * @return GNUNET_OK (continue to iterate)
 577  */
 578 static int
 579 schedule_current_round (void *cls,
 580                         const GNUNET_HashCode *key,
 581                         void *value)
 582 {
 583   struct NSEPeerEntry *peer_entry = value;
 584   struct GNUNET_TIME_Relative delay;
 585
 586   if (peer_entry->th != NULL)
 587     {
 588       peer_entry->previous_round = GNUNET_NO;
 589       return GNUNET_OK;
 590     }
 591   if (peer_entry->transmit_task != GNUNET_SCHEDULER_NO_TASK)
 592     {
 593       GNUNET_SCHEDULER_cancel (peer_entry->transmit_task);
 594       peer_entry->previous_round = GNUNET_NO;
 595     }
 596   delay = get_transmit_delay ((peer_entry->previous_round == GNUNET_NO) ? -1 : 0);
 597   peer_entry->transmit_task = GNUNET_SCHEDULER_add_delayed (delay,
 598                                                             &transmit_task,
 599                                                             peer_entry);
 600   return GNUNET_OK;
 601 }
 602
 603
 604 /**
 605  * Update our flood message to be sent (and our timestamps).
 606  *
 607  * @param cls unused
 608  * @param tc context for this message
 609  */
 610 static void
 611 update_flood_message(void *cls,
 612                      const struct GNUNET_SCHEDULER_TaskContext *tc)
 613 {
 614   struct GNUNET_TIME_Relative offset;
 615   unsigned int i;
 616
 617   flood_task = GNUNET_SCHEDULER_NO_TASK;
 618   offset = GNUNET_TIME_absolute_get_remaining (next_timestamp);
 619   if (0 != offset.rel_value)
 620     {
 621       /* somehow run early, delay more */
 622       flood_task
 623         = GNUNET_SCHEDULER_add_delayed (offset,
 624                                         &update_flood_message,
 625                                         NULL);
 626       return;
 627     }
 628   current_timestamp = next_timestamp;
 629   next_timestamp = GNUNET_TIME_absolute_add (current_timestamp,
 630                                              GNUNET_NSE_INTERVAL);
 631   estimate_index = (estimate_index + 1) % HISTORY_SIZE;
 632   setup_flood_message (estimate_index, current_timestamp);
 633   hop_count_max = 0;
 634   for (i=0;i<HISTORY_SIZE;i++)
 635     hop_count_max = GNUNET_MAX (ntohl (size_estimate_messages[i].hop_count),
 636                                 hop_count_max);
 637   GNUNET_CONTAINER_multihashmap_iterate (peers,
 638                                          &schedule_current_round,
 639                                          NULL);
 640   flood_task = GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_absolute_get_remaining (next_timestamp),
 641                                              &update_flood_message, NULL);
 642 }
 643
 644
 645 /**
 646  * Count the leading zeroes in hash.
 647  *
 648  * @param hash
 649  * @return the number of leading zero bits.
 650  */
 651 static unsigned int
 652 count_leading_zeroes(const GNUNET_HashCode *hash)
 653 {
 654   unsigned int hash_count;
 655
 656   hash_count = 0;
 657   while ((0 == GNUNET_CRYPTO_hash_get_bit(hash, hash_count)))
 658     hash_count++;
 659   return hash_count;
 660 }
 661
 662
 663 /**
 664  * Check whether the given public key
 665  * and integer are a valid proof of work.
 666  *
 667  * @param pkey the public key
 668  * @param val the integer
 669  *
 670  * @return GNUNET_YES if valid, GNUNET_NO if not
 671  */
 672 static int
 673 check_proof_of_work(const struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded *pkey,
 674                     uint64_t val)
 675 {
 676   char buf[sizeof(struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded) + sizeof(val)];
 677   GNUNET_HashCode result;
 678
 679   memcpy (buf,
 680           &val,
 681           sizeof (val));
 682   memcpy (&buf[sizeof(val)],
 683           pkey,
 684           sizeof(struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded));
 685   GNUNET_CRYPTO_hash (buf, sizeof (buf), &result);
 686   return (count_leading_zeroes (&result) >= NSE_WORK_REQUIRED) ? GNUNET_YES : GNUNET_NO;
 687 }
 688
 689
 690 /**
 691  * Given a public key, find an integer such that the hash of the key
 692  * concatenated with the integer has NSE_WORK_REQUIRED leading 0
 693  * bits.  FIXME: this is a synchronous function... bad
 694  *
 695  * @param pkey the public key
 696  * @return 64 bit number that satisfies the requirements
 697  */
 698 static uint64_t
 699 find_proof_of_work(const struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded *pkey)
 700 {
 701   uint64_t counter;
 702   char buf[sizeof(struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded) + sizeof(uint64_t)];
 703   GNUNET_HashCode result;
 704
 705   memcpy (&buf[sizeof(uint64_t)],
 706           pkey,
 707           sizeof(struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded));
 708   counter = 0;
 709   while (counter != UINT64_MAX)
 710     {
 711       memcpy (buf,
 712               &counter,
 713               sizeof(uint64_t));
 714       GNUNET_CRYPTO_hash (buf, sizeof (buf), &result);
 715       if (NSE_WORK_REQUIRED <= count_leading_zeroes(&result))
 716         break;
 717       counter++;
 718     }
 719   return counter;
 720 }
 721
 722
 723 /**
 724  * An incoming flood message has been received which claims
 725  * to have more bits matching than any we know in this time
 726  * period.  Verify the signature and/or proof of work.
 727  *
 728  * @param incoming_flood the message to verify
 729  *
 730  * @return GNUNET_YES if the message is verified
 731  *         GNUNET_NO if the key/signature don't verify
 732  */
 733 static int
 734 verify_message_crypto(const struct GNUNET_NSE_FloodMessage *incoming_flood)
 735 {
 736   if (GNUNET_YES !=
 737       check_proof_of_work (&incoming_flood->pkey,
 738                            incoming_flood->proof_of_work))
 739     {
 740       GNUNET_break_op (0);
 741       return GNUNET_NO;
 742     }
 743   if (GNUNET_OK !=
 744       GNUNET_CRYPTO_rsa_verify (GNUNET_SIGNATURE_PURPOSE_NSE_SEND,
 745                                 &incoming_flood->purpose,
 746                                 &incoming_flood->signature,
 747                                 &incoming_flood->pkey))
 748     {
 749       GNUNET_break_op (0);
 750       return GNUNET_NO;
 751     }
 752   return GNUNET_YES;
 753 }
 754
 755
 756 /**
 757  * Update transmissions for the given peer for the current round based
 758  * on updated proximity information.
 759  *
 760  * @param cls peer entry to exclude from updates
 761  * @param key hash of peer identity
 762  * @param value the 'struct NSEPeerEntry'
 763  * @return GNUNET_OK (continue to iterate)
 764  */
 765 static int
 766 update_flood_times (void *cls,
 767                     const GNUNET_HashCode *key,
 768                     void *value)
 769 {
 770   struct NSEPeerEntry *exclude = cls;
 771   struct NSEPeerEntry *peer_entry = value;
 772   struct GNUNET_TIME_Relative delay;
 773
 774   if (peer_entry->th != NULL)
 775     return GNUNET_OK; /* already active */
 776   if (peer_entry == exclude)
 777     return GNUNET_OK; /* trigger of the update */
 778   if (peer_entry->previous_round == GNUNET_YES)
 779     {
 780       /* still stuck in previous round, no point to update, check that
 781          we are active here though... */
 782       GNUNET_break (peer_entry->transmit_task != GNUNET_SCHEDULER_NO_TASK);
 783       return GNUNET_OK;
 784     }
 785   if (peer_entry->transmit_task != GNUNET_SCHEDULER_NO_TASK)
 786     {
 787       GNUNET_SCHEDULER_cancel (peer_entry->transmit_task);
 788       peer_entry->transmit_task = GNUNET_SCHEDULER_NO_TASK;
 789     }
 790   delay = get_transmit_delay (0);
 791   peer_entry->transmit_task = GNUNET_SCHEDULER_add_delayed (delay,
 792                                                             &transmit_task,
 793                                                             peer_entry);
 794   return GNUNET_OK;
 795 }
 796
 797
 798 /**
 799  * Core handler for size estimate flooding messages.
 800  *
 801  * @param cls closure unused
 802  * @param message message
 803  * @param peer peer identity this message is from (ignored)
 804  * @param atsi performance data (ignored)
 805  *
 806  */
 807 static int
 808 handle_p2p_size_estimate(void *cls,
 809                          const struct GNUNET_PeerIdentity *peer,
 810                          const struct GNUNET_MessageHeader *message,
 811                          const struct GNUNET_TRANSPORT_ATS_Information *atsi)
 812 {
 813   const struct GNUNET_NSE_FloodMessage *incoming_flood;
 814   struct GNUNET_TIME_Absolute ts;
 815   struct NSEPeerEntry *peer_entry;
 816   uint32_t matching_bits;
 817   unsigned int idx;
 818
 819   incoming_flood = (const struct GNUNET_NSE_FloodMessage *) message;
 820   GNUNET_STATISTICS_update (stats,
 821                             "# flood messages received",
 822                             1,
 823                             GNUNET_NO);
 824   matching_bits = ntohl (incoming_flood->matching_bits);
 825   peer_entry = GNUNET_CONTAINER_multihashmap_get (peers, &peer->hashPubKey);
 826   if (NULL == peer_entry)
 827     {
 828       GNUNET_break (0);
 829       return GNUNET_OK;
 830     }
 831   ts = GNUNET_TIME_absolute_ntoh (incoming_flood->timestamp);
 832   if (ts.abs_value == current_timestamp.abs_value)
 833     idx = estimate_index;
 834   else if (ts.abs_value == current_timestamp.abs_value - GNUNET_NSE_INTERVAL.rel_value)
 835     idx = (estimate_index + HISTORY_SIZE - 1) % HISTORY_SIZE;
 836   else if (ts.abs_value == next_timestamp.abs_value - GNUNET_NSE_INTERVAL.rel_value)
 837     {
 838       if (GNUNET_YES !=
 839           verify_message_crypto (incoming_flood))
 840         {
 841           GNUNET_break_op (0);
 842           return GNUNET_OK;
 843         }
 844       /* FIXME: keep in special 'future' buffer until next round starts for us! */
 845       GNUNET_break (0); /* not implemented */
 846       return GNUNET_OK;
 847     }
 848   else
 849     {
 850       GNUNET_STATISTICS_update (stats,
 851                                 "# flood messages discarded (clock skew too large)",
 852                                 1,
 853                                 GNUNET_NO);
 854       GNUNET_break_op (0);
 855       return GNUNET_OK;
 856     }
 857   if (0 == (memcmp (peer, &my_identity, sizeof(struct GNUNET_PeerIdentity))))
 858     {
 859       /* send to self, update our own estimate IF this also comes from us! */
 860       if (0 == memcmp (&incoming_flood->pkey,
 861                        &my_public_key,
 862                        sizeof (my_public_key)))
 863         update_network_size_estimate ();
 864       return GNUNET_OK;
 865     }
 866   if (matching_bits >= ntohl (size_estimate_messages[idx].matching_bits))
 867     {
 868       /* cancel transmission from us to this peer for this round */
 869       if (idx == estimate_index)
 870         {
 871           if (peer_entry->previous_round == GNUNET_NO)
 872             {
 873               /* cancel any activity for current round */
 874               if (peer_entry->transmit_task != GNUNET_SCHEDULER_NO_TASK)
 875                 {
 876                   GNUNET_SCHEDULER_cancel (peer_entry->transmit_task);
 877                   peer_entry->previous_round = GNUNET_NO;
 878                 }
 879               if (peer_entry->th != NULL)
 880                 {
 881                   GNUNET_CORE_notify_transmit_ready_cancel (peer_entry->th);
 882                   peer_entry->th = NULL;
 883                 }
 884             }
 885         }
 886       else
 887         {
 888           /* cancel previous round only */
 889           peer_entry->previous_round = GNUNET_NO;
 890         }
 891
 892     }
 893   if (matching_bits <= ntohl (size_estimate_messages[idx].matching_bits))
 894     {
 895       /* Not closer than our most recent message, no need to do work here */
 896       GNUNET_STATISTICS_update (stats,
 897                                 "# flood messages ignored (had closer already)",
 898                                 1,
 899                                 GNUNET_NO);
 900       return GNUNET_OK;
 901     }
 902   if (GNUNET_YES !=
 903       verify_message_crypto (incoming_flood))
 904     {
 905       GNUNET_break_op (0);
 906       return GNUNET_OK;
 907     }
 908   size_estimate_messages[idx] = *incoming_flood;
 909   size_estimate_messages[idx].hop_count = htonl (ntohl (incoming_flood->hop_count) + 1);
 910   hop_count_max = GNUNET_MAX (ntohl (incoming_flood->hop_count) + 1,
 911                               hop_count_max);
 912
 913   /* have a new, better size estimate, inform clients */
 914   update_network_size_estimate ();
 915
 916   /* flood to rest */
 917   GNUNET_CONTAINER_multihashmap_iterate (peers,
 918                                          &update_flood_times,
 919                                          peer_entry);
 920   return GNUNET_OK;
 921 }
 922
 923
 924
 925 /**
 926  * Method called whenever a peer connects.
 927  *
 928  * @param cls closure
 929  * @param peer peer identity this notification is about
 930  * @param atsi performance data
 931  */
 932 static void
 933 handle_core_connect(void *cls, const struct GNUNET_PeerIdentity *peer,
 934                     const struct GNUNET_TRANSPORT_ATS_Information *atsi)
 935 {
 936   struct NSEPeerEntry *peer_entry;
 937
 938   peer_entry = GNUNET_malloc(sizeof(struct NSEPeerEntry));
 939   peer_entry->id = *peer;
 940   GNUNET_CONTAINER_multihashmap_put (peers,
 941                                      &peer->hashPubKey,
 942                                      peer_entry,
 943                                      GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
 944   peer_entry->transmit_task = GNUNET_SCHEDULER_add_delayed (get_transmit_delay (-1),
 945                                                             &transmit_task,
 946                                                             peer_entry);
 947 }
 948
 949
 950 /**
 951  * Method called whenever a peer disconnects.
 952  *
 953  * @param cls closure
 954  * @param peer peer identity this notification is about
 955  */
 956 static void
 957 handle_core_disconnect(void *cls, const struct GNUNET_PeerIdentity *peer)
 958 {
 959   struct NSEPeerEntry *pos;
 960
 961   pos = GNUNET_CONTAINER_multihashmap_get (peers,
 962                                            &peer->hashPubKey);
 963   if (NULL == pos)
 964     {
 965       GNUNET_break (0);
 966       return;
 967     }
 968   GNUNET_assert (GNUNET_YES ==
 969                  GNUNET_CONTAINER_multihashmap_remove (peers,
 970                                                        &peer->hashPubKey,
 971                                                        pos));
 972   if (pos->transmit_task != GNUNET_SCHEDULER_NO_TASK)
 973     GNUNET_SCHEDULER_cancel (pos->transmit_task);
 974   if (pos->th != NULL)
 975     GNUNET_CORE_notify_transmit_ready_cancel (pos->th);
 976   GNUNET_free(pos);
 977 }
 978
 979
 980 /**
 981  * Task run during shutdown.
 982  *
 983  * @param cls unused
 984  * @param tc unused
 985  */
 986 static void
 987 shutdown_task(void *cls,
 988               const struct GNUNET_SCHEDULER_TaskContext *tc)
 989 {
 990   if (flood_task != GNUNET_SCHEDULER_NO_TASK)
 991     {
 992       GNUNET_SCHEDULER_cancel (flood_task);
 993       flood_task = GNUNET_SCHEDULER_NO_TASK;
 994     }
 995   GNUNET_SERVER_notification_context_destroy (nc);
 996   nc = NULL;
 997   if (coreAPI != NULL)
 998     {
 999       GNUNET_CORE_disconnect (coreAPI);
1000       coreAPI = NULL;
1001     }
1002   if (stats != NULL)
1003     {
1004       GNUNET_STATISTICS_destroy (stats, GNUNET_NO);
1005       stats = NULL;
1006     }
1007 }
1008
1009
1010 /**
1011  * Called on core init/fail.
1012  *
1013  * @param cls service closure
1014  * @param server handle to the server for this service
1015  * @param identity the public identity of this peer
1016  * @param publicKey the public key of this peer
1017  */
1018 void
1019 core_init(void *cls, struct GNUNET_CORE_Handle *server,
1020           const struct GNUNET_PeerIdentity *identity,
1021           const struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded *publicKey)
1022 {
1023   struct GNUNET_TIME_Absolute now;
1024   struct GNUNET_TIME_Absolute prev_time;
1025   unsigned int i;
1026
1027   if (server == NULL)
1028     {
1029 #if DEBUG_NSE
1030       GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1031                   "Connection to core FAILED!\n");
1032 #endif
1033       GNUNET_SCHEDULER_add_now (&shutdown_task, NULL);
1034       return;
1035     }
1036   my_identity = *identity;
1037   my_public_key = *publicKey;
1038
1039   now = GNUNET_TIME_absolute_get ();
1040   current_timestamp.abs_value = (now.abs_value / GNUNET_NSE_INTERVAL.rel_value) * GNUNET_NSE_INTERVAL.rel_value;
1041   next_timestamp.abs_value = current_timestamp.abs_value + GNUNET_NSE_INTERVAL.rel_value;
1042
1043   for (i=0;i<HISTORY_SIZE;i++)
1044     {
1045       prev_time.abs_value = next_timestamp.abs_value - (HISTORY_SIZE - i - 1) * GNUNET_NSE_INTERVAL.rel_value;
1046       setup_flood_message (i, prev_time);
1047     }
1048   estimate_index = HISTORY_SIZE - 1;
1049   flood_task
1050     = GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_absolute_get_remaining (next_timestamp),
1051                                     &update_flood_message, NULL);
1052   my_proof = find_proof_of_work (&my_public_key);
1053 }
1054
1055
1056 /**
1057  * Handle network size estimate clients.
1058  *
1059  * @param cls closure
1060  * @param server the initialized server
1061  * @param c configuration to use
1062  */
1063 static void
1064 run(void *cls, struct GNUNET_SERVER_Handle *server,
1065     const struct GNUNET_CONFIGURATION_Handle *c)
1066 {
1067   char *keyfile;
1068
1069   static const struct GNUNET_SERVER_MessageHandler handlers[] =
1070     {
1071       { &handle_start_message, NULL, GNUNET_MESSAGE_TYPE_NSE_START, sizeof (struct GNUNET_MessageHeader) },
1072       { NULL, NULL, 0, 0 }
1073     };
1074   static const struct GNUNET_CORE_MessageHandler core_handlers[] =
1075     {
1076       { &handle_p2p_size_estimate, GNUNET_MESSAGE_TYPE_NSE_P2P_FLOOD, sizeof (struct GNUNET_NSE_FloodMessage) },
1077       { NULL, 0, 0 }
1078     };
1079   cfg = c;
1080   if (GNUNET_OK !=
1081       GNUNET_CONFIGURATION_get_value_filename (cfg,
1082                                                "GNUNETD", "HOSTKEY",
1083                                                &keyfile))
1084     {
1085       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1086                   _ ("NSE service is lacking key configuration settings.  Exiting.\n"));
1087       GNUNET_SCHEDULER_shutdown ();
1088       return;
1089     }
1090   my_private_key = GNUNET_CRYPTO_rsa_key_create_from_file (keyfile);
1091   GNUNET_free (keyfile);
1092   if (my_private_key == NULL)
1093     {
1094       GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1095                   _("NSE service could not access hostkey.  Exiting.\n"));
1096       GNUNET_SCHEDULER_shutdown ();
1097       return;
1098     }
1099   GNUNET_SERVER_add_handlers (server, handlers);
1100   nc = GNUNET_SERVER_notification_context_create (server, 1);
1101   /* Connect to core service and register core handlers */
1102   coreAPI = GNUNET_CORE_connect (cfg, /* Main configuration */
1103                                  CORE_QUEUE_SIZE, /* queue size */
1104                                  NULL, /* Closure passed to functions */
1105                                  &core_init, /* Call core_init once connected */
1106                                  &handle_core_connect, /* Handle connects */
1107                                  &handle_core_disconnect, /* Handle disconnects */
1108                                  NULL, /* Do we care about "status" updates? */
1109                                  NULL, /* Don't want notified about all incoming messages */
1110                                  GNUNET_NO, /* For header only inbound notification */
1111                                  NULL, /* Don't want notified about all outbound messages */
1112                                  GNUNET_NO, /* For header only outbound notification */
1113                                  core_handlers); /* Register these handlers */
1114   if (coreAPI == NULL)
1115     {
1116       GNUNET_SCHEDULER_add_now (&shutdown_task, NULL);
1117       return;
1118     }
1119   stats = GNUNET_STATISTICS_create ("NSE", cfg);
1120 }
1121
1122
1123 /**
1124  * The main function for the statistics service.
1125  *
1126  * @param argc number of arguments from the command line
1127  * @param argv command line arguments
1128  * @return 0 ok, 1 on error
1129  */
1130 int
1131 main(int argc, char * const *argv)
1132 {
1133   return (GNUNET_OK == GNUNET_SERVICE_run (argc, argv,
1134                                            "nse",
1135                                            GNUNET_SERVICE_OPTION_NONE, &run,
1136                                            NULL)) ? 0 : 1;
1137 }
1138
1139 /* end of gnunet-service-nse.c */
1140