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