2 This file is part of GNUnet.
3 (C) 2009, 2010, 2011 Christian Grothoff (and other contributing authors)
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.
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.
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.
22 * @file nse/gnunet-service-nse.c
23 * @brief network size estimation service
24 * @author Nathan Evans
25 * @author Christian Grothoff
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.
40 #include "gnunet_util_lib.h"
41 #include "gnunet_constants.h"
42 #include "gnunet_protocols.h"
43 #include "gnunet_signatures.h"
44 #include "gnunet_statistics_service.h"
45 #include "gnunet_core_service.h"
46 #include "gnunet_nse_service.h"
50 * Should messages be delayed randomly? This option should be set to
51 * GNUNET_NO only for experiments, not in production. It should also
52 * be removed once the initial experiments have been completed.
54 #define USE_RANDOM_DELAYS GNUNET_YES
57 * Should we generate a histogram with the time stamps of when we received
58 * NSE messages to disk? (for performance evaluation only, not useful in
59 * production). The associated code should also probably be removed
60 * once we're done with experiments.
62 #define ENABLE_HISTOGRAM GNUNET_YES
65 * Over how many values do we calculate the weighted average?
67 #define HISTORY_SIZE 64
70 * Message priority to use.
72 #define NSE_PRIORITY 5
75 #define log2(a) (log(a)/log(2))
79 * Amount of work required (W-bit collisions) for NSE proofs, in collision-bits.
81 static unsigned long long nse_work_required;
84 * Interval for sending network size estimation flood requests.
86 static struct GNUNET_TIME_Relative gnunet_nse_interval;
89 * Interval between proof find runs.
91 static struct GNUNET_TIME_Relative proof_find_delay;
95 * Handle for writing when we received messages to disk.
97 static struct GNUNET_BIO_WriteHandle *wh;
102 * Per-peer information.
108 * Core handle for sending messages to this peer.
110 struct GNUNET_CORE_TransmitHandle *th;
113 * What is the identity of the peer?
115 struct GNUNET_PeerIdentity id;
118 * Task scheduled to send message to this peer.
120 GNUNET_SCHEDULER_TaskIdentifier transmit_task;
123 * Did we receive or send a message about the previous round
124 * to this peer yet? GNUNET_YES if the previous round has
125 * been taken care of.
130 * Where a variable has been modified to cause a bug.
131 * FIXME DELETE AFTER DEBUG
140 * Amount of messages received from this peer on this round.
142 unsigned int received_messages;
145 * Amount of messages transmitted to this peer on this round.
147 unsigned int transmitted_messages;
150 * Which size did we tell the peer the network is?
152 unsigned int last_transmitted_size;
159 GNUNET_NETWORK_STRUCT_BEGIN
162 * Network size estimate reply; sent when "this"
163 * peer's timer has run out before receiving a
164 * valid reply from another peer.
166 struct GNUNET_NSE_FloodMessage
169 * Type: GNUNET_MESSAGE_TYPE_NSE_P2P_FLOOD
171 struct GNUNET_MessageHeader header;
174 * Number of hops this message has taken so far.
176 uint32_t hop_count GNUNET_PACKED;
181 struct GNUNET_CRYPTO_RsaSignaturePurpose purpose;
184 * The current timestamp value (which all
185 * peers should agree on).
187 struct GNUNET_TIME_AbsoluteNBO timestamp;
190 * Number of matching bits between the hash
191 * of timestamp and the initiator's public
194 uint32_t matching_bits GNUNET_PACKED;
197 * Public key of the originator.
199 struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded pkey;
202 * Proof of work, causing leading zeros when hashed with pkey.
204 uint64_t proof_of_work GNUNET_PACKED;
207 * Signature (over range specified in purpose).
209 struct GNUNET_CRYPTO_RsaSignature signature;
211 GNUNET_NETWORK_STRUCT_END
214 * Handle to our current configuration.
216 static const struct GNUNET_CONFIGURATION_Handle *cfg;
219 * Handle to the statistics service.
221 static struct GNUNET_STATISTICS_Handle *stats;
224 * Handle to the core service.
226 static struct GNUNET_CORE_Handle *coreAPI;
229 * Map of all connected peers.
231 static struct GNUNET_CONTAINER_MultiHashMap *peers;
234 * The current network size estimate. Number of bits matching on
237 static double current_size_estimate;
240 * The standard deviation of the last HISTORY_SIZE network
243 static double current_std_dev = NAN;
246 * Current hop counter estimate (estimate for network diameter).
248 static uint32_t hop_count_max;
251 * Message for the next round, if we got any.
253 static struct GNUNET_NSE_FloodMessage next_message;
256 * Array of recent size estimate messages.
258 static struct GNUNET_NSE_FloodMessage size_estimate_messages[HISTORY_SIZE];
261 * Index of most recent estimate.
263 static unsigned int estimate_index;
266 * Number of valid entries in the history.
268 static unsigned int estimate_count;
271 * Task scheduled to update our flood message for the next round.
273 static GNUNET_SCHEDULER_TaskIdentifier flood_task;
276 * Task scheduled to compute our proof.
278 static GNUNET_SCHEDULER_TaskIdentifier proof_task;
281 * Notification context, simplifies client broadcasts.
283 static struct GNUNET_SERVER_NotificationContext *nc;
286 * The next major time.
288 static struct GNUNET_TIME_Absolute next_timestamp;
291 * The current major time.
293 static struct GNUNET_TIME_Absolute current_timestamp;
296 * The public key of this peer.
298 static struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded my_public_key;
301 * The private key of this peer.
303 static struct GNUNET_CRYPTO_RsaPrivateKey *my_private_key;
306 * The peer identity of this peer.
308 static struct GNUNET_PeerIdentity my_identity;
311 * Proof of work for this peer.
313 static uint64_t my_proof;
317 * Initialize a message to clients with the current network
320 * @param em message to fill in
323 setup_estimate_message (struct GNUNET_NSE_ClientMessage *em)
335 /* Weighted incremental algorithm for stddev according to West (1979) */
347 for (i = 0; i < estimate_count; i++)
349 j = (estimate_index - i + HISTORY_SIZE) % HISTORY_SIZE;
350 val = htonl (size_estimate_messages[j].matching_bits);
351 weight = estimate_count + 1 - i;
353 temp = weight + sumweight;
355 r = q * weight / temp;
357 sum += sumweight * q * r;
360 if (estimate_count > 0)
361 variance = (sum / sumweight) * estimate_count / (estimate_count - 1.0);
363 /* trivial version for debugging */
366 /* non-weighted trivial version */
372 for (i = 0; i < estimate_count; i++)
374 j = (estimate_index - i + HISTORY_SIZE) % HISTORY_SIZE;
375 val = htonl (size_estimate_messages[j].matching_bits);
379 if (0 != estimate_count)
381 mean = sum / estimate_count;
382 variance = (vsq - mean * sum) / (estimate_count - 1.0); // terrible for numerical stability...
386 std_dev = sqrt (variance);
388 std_dev = variance; /* must be infinity due to estimate_count == 0 */
389 current_std_dev = std_dev;
390 current_size_estimate = mean;
392 em->header.size = htons (sizeof (struct GNUNET_NSE_ClientMessage));
393 em->header.type = htons (GNUNET_MESSAGE_TYPE_NSE_ESTIMATE);
394 em->reserved = htonl (0);
395 em->timestamp = GNUNET_TIME_absolute_hton (GNUNET_TIME_absolute_get ());
396 double se = mean - 0.332747;
397 nsize = log2 (GNUNET_CONTAINER_multihashmap_size (peers) + 1);
398 em->size_estimate = GNUNET_hton_double (GNUNET_MAX (se, nsize));
399 em->std_deviation = GNUNET_hton_double (std_dev);
400 GNUNET_STATISTICS_set (stats, "# nodes in the network (estimate)",
401 (uint64_t) pow (2, mean - 1.0 / 3.0), GNUNET_NO);
406 * Handler for START message from client, triggers an
407 * immediate current network estimate notification.
408 * Also, we remember the client for updates upon future
409 * estimate measurements.
412 * @param client who sent the message
413 * @param message the message received
416 handle_start_message (void *cls, struct GNUNET_SERVER_Client *client,
417 const struct GNUNET_MessageHeader *message)
419 struct GNUNET_NSE_ClientMessage em;
422 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Received START message from client\n");
424 GNUNET_SERVER_notification_context_add (nc, client);
425 setup_estimate_message (&em);
426 GNUNET_SERVER_notification_context_unicast (nc, client, &em.header,
428 GNUNET_SERVER_receive_done (client, GNUNET_OK);
433 * How long should we delay a message to go the given number of
436 * @param matching_bits number of matching bits to consider
439 get_matching_bits_delay (uint32_t matching_bits)
441 /* Calculated as: S + f/2 - (f / pi) * (atan(x - p')) */
442 // S is next_timestamp (ignored in return value)
443 // f is frequency (gnunet_nse_interval)
444 // x is matching_bits
445 // p' is current_size_estimate
446 return ((double) gnunet_nse_interval.rel_value / (double) 2.0) -
447 ((gnunet_nse_interval.rel_value / M_PI) *
448 atan (matching_bits - current_size_estimate));
453 * What delay randomization should we apply for a given number of matching bits?
455 * @param matching_bits number of matching bits
456 * @return random delay to apply
458 static struct GNUNET_TIME_Relative
459 get_delay_randomization (uint32_t matching_bits)
461 #if USE_RANDOM_DELAYS
462 struct GNUNET_TIME_Relative ret;
466 d = get_matching_bits_delay (matching_bits);
467 i = (uint32_t) (d / (double) (hop_count_max + 1));
469 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
470 "Randomizing flood using latencies up to %u ms\n",
473 ret.rel_value = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, i + 1);
476 return GNUNET_TIME_UNIT_ZERO;
482 * Get the number of matching bits that the given timestamp has to the given peer ID.
484 * @param timestamp time to generate key
485 * @param id peer identity to compare with
486 * @return number of matching bits
489 get_matching_bits (struct GNUNET_TIME_Absolute timestamp,
490 const struct GNUNET_PeerIdentity *id)
492 GNUNET_HashCode timestamp_hash;
494 GNUNET_CRYPTO_hash (×tamp.abs_value, sizeof (timestamp.abs_value),
496 return GNUNET_CRYPTO_hash_matching_bits (×tamp_hash, &id->hashPubKey);
501 * Get the transmission delay that should be applied for a
504 * @param round_offset -1 for the previous round (random delay between 0 and 50ms)
505 * 0 for the current round (based on our proximity to time key)
506 * @return delay that should be applied
508 static struct GNUNET_TIME_Relative
509 get_transmit_delay (int round_offset)
511 struct GNUNET_TIME_Relative ret;
512 struct GNUNET_TIME_Absolute tgt;
514 uint32_t matching_bits;
516 switch (round_offset)
519 /* previous round is randomized between 0 and 50 ms */
520 #if USE_RANDOM_DELAYS
521 ret.rel_value = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, 50);
523 ret = GNUNET_TIME_UNIT_ZERO;
526 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
527 "Transmitting previous round behind schedule in %llu ms\n",
528 (unsigned long long) ret.rel_value);
532 /* current round is based on best-known matching_bits */
534 ntohl (size_estimate_messages[estimate_index].matching_bits);
535 dist_delay = get_matching_bits_delay (matching_bits);
536 dist_delay += get_delay_randomization (matching_bits).rel_value;
537 ret.rel_value = (uint64_t) dist_delay;
539 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
540 "For round %llu, delay for %u matching bits is %llu ms\n",
541 (unsigned long long) current_timestamp.abs_value,
542 (unsigned int) matching_bits,
543 (unsigned long long) ret.rel_value);
545 /* now consider round start time and add delay to it */
546 tgt = GNUNET_TIME_absolute_add (current_timestamp, ret);
547 return GNUNET_TIME_absolute_get_remaining (tgt);
550 return GNUNET_TIME_UNIT_FOREVER_REL;
555 * Task that triggers a NSE P2P transmission.
557 * @param cls the 'struct NSEPeerEntry'
558 * @param tc scheduler context
561 transmit_task_cb (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc);
565 * Called when core is ready to send a message we asked for
566 * out to the destination.
568 * @param cls closure (NULL)
569 * @param size number of bytes available in buf
570 * @param buf where the callee should write the message
571 * @return number of bytes written to buf
574 transmit_ready (void *cls, size_t size, void *buf)
576 struct NSEPeerEntry *peer_entry = cls;
579 peer_entry->th = NULL;
580 peer_entry->where_th = __LINE__;
583 /* client disconnected */
586 GNUNET_assert (size >= sizeof (struct GNUNET_NSE_FloodMessage));
587 idx = estimate_index;
588 if (GNUNET_NO == peer_entry->previous_round)
590 idx = (idx + HISTORY_SIZE - 1) % HISTORY_SIZE;
591 peer_entry->previous_round = GNUNET_YES;
592 peer_entry->transmit_task =
593 GNUNET_SCHEDULER_add_delayed (get_transmit_delay (0), &transmit_task_cb,
596 if ((ntohl (size_estimate_messages[idx].hop_count) == 0) &&
597 (GNUNET_SCHEDULER_NO_TASK != proof_task))
599 GNUNET_STATISTICS_update (stats,
600 "# flood messages not generated (no proof yet)",
604 if (ntohs (size_estimate_messages[idx].header.size) == 0)
606 GNUNET_STATISTICS_update (stats,
607 "# flood messages not generated (lack of history)",
609 return 0; // FIXME necessary?
612 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
613 "In round %llu, sending to `%s' estimate with %u bits\n",
615 GNUNET_TIME_absolute_ntoh (size_estimate_messages[idx].
616 timestamp).abs_value,
617 GNUNET_i2s (&peer_entry->id),
618 (unsigned int) ntohl (size_estimate_messages[idx].matching_bits));
620 if (ntohl (size_estimate_messages[idx].hop_count) == 0)
621 GNUNET_STATISTICS_update (stats, "# flood messages started", 1, GNUNET_NO);
622 GNUNET_STATISTICS_update (stats, "# flood messages transmitted", 1,
625 peer_entry->transmitted_messages++;
626 peer_entry->last_transmitted_size =
627 ntohl(size_estimate_messages[idx].matching_bits);
629 memcpy (buf, &size_estimate_messages[idx],
630 sizeof (struct GNUNET_NSE_FloodMessage));
631 return sizeof (struct GNUNET_NSE_FloodMessage);
636 * Task that triggers a NSE P2P transmission.
638 * @param cls the 'struct NSEPeerEntry'
639 * @param tc scheduler context
642 transmit_task_cb (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
644 struct NSEPeerEntry *peer_entry = cls;
646 peer_entry->transmit_task = GNUNET_SCHEDULER_NO_TASK;
647 peer_entry->where_task = __LINE__;
649 GNUNET_assert (NULL == peer_entry->th);
651 GNUNET_CORE_notify_transmit_ready (coreAPI, GNUNET_NO, NSE_PRIORITY,
652 GNUNET_TIME_UNIT_FOREVER_REL,
655 GNUNET_NSE_FloodMessage),
656 &transmit_ready, peer_entry);
657 peer_entry->where_th = __LINE__;
662 * We've sent on our flood message or one that we received which was
663 * validated and closer than ours. Update the global list of recent
664 * messages and the average. Also re-broadcast the message to any
668 update_network_size_estimate ()
670 struct GNUNET_NSE_ClientMessage em;
672 setup_estimate_message (&em);
673 GNUNET_SERVER_notification_context_broadcast (nc, &em.header, GNUNET_YES);
678 * Setup a flood message in our history array at the given
679 * slot offset for the given timestamp.
681 * @param slot index to use
682 * @param ts timestamp to use
685 setup_flood_message (unsigned int slot, struct GNUNET_TIME_Absolute ts)
687 struct GNUNET_NSE_FloodMessage *fm;
688 uint32_t matching_bits;
690 matching_bits = get_matching_bits (ts, &my_identity);
691 fm = &size_estimate_messages[slot];
692 fm->header.size = htons (sizeof (struct GNUNET_NSE_FloodMessage));
693 fm->header.type = htons (GNUNET_MESSAGE_TYPE_NSE_P2P_FLOOD);
694 fm->hop_count = htonl (0);
695 fm->purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_NSE_SEND);
697 htonl (sizeof (struct GNUNET_NSE_FloodMessage) -
698 sizeof (struct GNUNET_MessageHeader) - sizeof (uint32_t) -
699 sizeof (struct GNUNET_CRYPTO_RsaSignature));
700 fm->matching_bits = htonl (matching_bits);
701 fm->timestamp = GNUNET_TIME_absolute_hton (ts);
702 fm->pkey = my_public_key;
703 fm->proof_of_work = my_proof;
704 if (nse_work_required > 0)
705 GNUNET_assert (GNUNET_OK ==
706 GNUNET_CRYPTO_rsa_sign (my_private_key, &fm->purpose,
709 memset (&fm->signature, 0, sizeof (fm->signature));
714 * Schedule transmission for the given peer for the current round based
715 * on what we know about the desired delay.
718 * @param key hash of peer identity
719 * @param value the 'struct NSEPeerEntry'
720 * @return GNUNET_OK (continue to iterate)
723 schedule_current_round (void *cls, const GNUNET_HashCode * key, void *value)
725 struct NSEPeerEntry *peer_entry = value;
726 struct GNUNET_TIME_Relative delay;
728 if (NULL != peer_entry->th)
730 peer_entry->previous_round = GNUNET_NO;
731 peer_entry->where_round = __LINE__;
734 if (GNUNET_SCHEDULER_NO_TASK != peer_entry->transmit_task)
736 GNUNET_SCHEDULER_cancel (peer_entry->transmit_task);
737 peer_entry->previous_round = GNUNET_NO;
738 peer_entry->where_round = __LINE__;
741 if (peer_entry->received_messages > 1)
742 GNUNET_STATISTICS_update(stats, "# extra messages",
743 peer_entry->received_messages - 1, GNUNET_NO);
744 peer_entry->transmitted_messages = 0;
745 peer_entry->last_transmitted_size = 0;
746 peer_entry->received_messages = 0;
749 get_transmit_delay ((peer_entry->previous_round == GNUNET_NO) ? -1 : 0);
750 peer_entry->transmit_task =
751 GNUNET_SCHEDULER_add_delayed (delay, &transmit_task_cb, peer_entry);
757 * Update our flood message to be sent (and our timestamps).
760 * @param tc context for this message
763 update_flood_message (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
765 struct GNUNET_TIME_Relative offset;
768 flood_task = GNUNET_SCHEDULER_NO_TASK;
769 if (0 != (tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN))
771 offset = GNUNET_TIME_absolute_get_remaining (next_timestamp);
772 if (0 != offset.rel_value)
774 /* somehow run early, delay more */
776 GNUNET_SCHEDULER_add_delayed (offset, &update_flood_message, NULL);
779 estimate_index = (estimate_index + 1) % HISTORY_SIZE;
780 if (estimate_count < HISTORY_SIZE)
782 current_timestamp = next_timestamp;
784 GNUNET_TIME_absolute_add (current_timestamp, gnunet_nse_interval);
785 if ((current_timestamp.abs_value ==
786 GNUNET_TIME_absolute_ntoh (next_message.timestamp).abs_value) &&
787 (get_matching_bits (current_timestamp, &my_identity) <
788 ntohl(next_message.matching_bits)))
790 /* we received a message for this round way early, use it! */
791 size_estimate_messages[estimate_index] = next_message;
792 size_estimate_messages[estimate_index].hop_count =
793 htonl (1 + ntohl (next_message.hop_count));
796 setup_flood_message (estimate_index, current_timestamp);
797 next_message.matching_bits = htonl (0); /* reset for 'next' round */
799 for (i = 0; i < HISTORY_SIZE; i++)
801 GNUNET_MAX (ntohl (size_estimate_messages[i].hop_count), hop_count_max);
802 GNUNET_CONTAINER_multihashmap_iterate (peers, &schedule_current_round, NULL);
804 GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_absolute_get_remaining
805 (next_timestamp), &update_flood_message,
811 * Count the leading zeroes in hash.
814 * @return the number of leading zero bits.
817 count_leading_zeroes (const GNUNET_HashCode * hash)
819 unsigned int hash_count;
822 while ((0 == GNUNET_CRYPTO_hash_get_bit (hash, hash_count)))
829 * Check whether the given public key
830 * and integer are a valid proof of work.
832 * @param pkey the public key
833 * @param val the integer
835 * @return GNUNET_YES if valid, GNUNET_NO if not
838 check_proof_of_work (const struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded *pkey,
841 char buf[sizeof (struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded) +
843 GNUNET_HashCode result;
845 memcpy (buf, &val, sizeof (val));
846 memcpy (&buf[sizeof (val)], pkey,
847 sizeof (struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded));
848 GNUNET_CRYPTO_hash (buf, sizeof (buf), &result);
849 return (count_leading_zeroes (&result) >=
850 nse_work_required) ? GNUNET_YES : GNUNET_NO;
855 * Write our current proof to disk.
863 GNUNET_CONFIGURATION_get_value_filename (cfg, "NSE", "PROOFFILE", &proof))
865 if (sizeof (my_proof) !=
866 GNUNET_DISK_fn_write (proof, &my_proof, sizeof (my_proof),
867 GNUNET_DISK_PERM_USER_READ |
868 GNUNET_DISK_PERM_USER_WRITE))
869 GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_WARNING, "write", proof);
876 * Find our proof of work.
878 * @param cls closure (unused)
879 * @param tc task context
882 find_proof (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
884 #define ROUND_SIZE 10
886 char buf[sizeof (struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded) +
888 GNUNET_HashCode result;
891 proof_task = GNUNET_SCHEDULER_NO_TASK;
892 memcpy (&buf[sizeof (uint64_t)], &my_public_key,
893 sizeof (struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded));
896 while ((counter != UINT64_MAX) && (i < ROUND_SIZE))
898 memcpy (buf, &counter, sizeof (uint64_t));
899 GNUNET_CRYPTO_hash (buf, sizeof (buf), &result);
900 if (nse_work_required <= count_leading_zeroes (&result))
904 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Proof of work found: %llu!\n",
905 (unsigned long long) GNUNET_ntohll (counter));
908 setup_flood_message (estimate_index, current_timestamp);
914 if (my_proof / (100 * ROUND_SIZE) < counter / (100 * ROUND_SIZE))
917 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Testing proofs currently at %llu\n",
918 (unsigned long long) counter);
920 /* remember progress every 100 rounds */
929 GNUNET_SCHEDULER_add_delayed_with_priority (proof_find_delay,
930 GNUNET_SCHEDULER_PRIORITY_IDLE,
936 * An incoming flood message has been received which claims
937 * to have more bits matching than any we know in this time
938 * period. Verify the signature and/or proof of work.
940 * @param incoming_flood the message to verify
942 * @return GNUNET_YES if the message is verified
943 * GNUNET_NO if the key/signature don't verify
946 verify_message_crypto (const struct GNUNET_NSE_FloodMessage *incoming_flood)
949 check_proof_of_work (&incoming_flood->pkey,
950 incoming_flood->proof_of_work))
952 GNUNET_log (GNUNET_ERROR_TYPE_INFO, _("Proof of work invalid: %llu!\n"),
954 GNUNET_ntohll (incoming_flood->proof_of_work));
958 if ((nse_work_required > 0) &&
960 GNUNET_CRYPTO_rsa_verify (GNUNET_SIGNATURE_PURPOSE_NSE_SEND,
961 &incoming_flood->purpose,
962 &incoming_flood->signature,
963 &incoming_flood->pkey)))
973 * Update transmissions for the given peer for the current round based
974 * on updated proximity information.
976 * @param cls peer entry to exclude from updates
977 * @param key hash of peer identity
978 * @param value the 'struct NSEPeerEntry'
979 * @return GNUNET_OK (continue to iterate)
982 update_flood_times (void *cls, const GNUNET_HashCode * key, void *value)
984 struct NSEPeerEntry *exclude = cls;
985 struct NSEPeerEntry *peer_entry = value;
986 struct GNUNET_TIME_Relative delay;
988 if (peer_entry->th != NULL)
989 return GNUNET_OK; /* already active */
990 if (peer_entry == exclude)
991 return GNUNET_OK; /* trigger of the update */
992 if (peer_entry->previous_round == GNUNET_NO)
994 /* still stuck in previous round, no point to update, check that
995 * we are active here though... */
996 if (GNUNET_SCHEDULER_NO_TASK == peer_entry->transmit_task &&
997 NULL == peer_entry->th)
1000 GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "ROUND%d TASK%d TH%d\n",
1001 peer_entry->where_round,
1002 peer_entry->where_task,
1003 peer_entry->where_th);
1007 if (peer_entry->transmit_task != GNUNET_SCHEDULER_NO_TASK)
1009 GNUNET_SCHEDULER_cancel (peer_entry->transmit_task);
1010 peer_entry->transmit_task = GNUNET_SCHEDULER_NO_TASK;
1011 peer_entry->where_task = __LINE__;
1013 delay = get_transmit_delay (0);
1014 peer_entry->transmit_task =
1015 GNUNET_SCHEDULER_add_delayed (delay, &transmit_task_cb, peer_entry);
1021 * Core handler for size estimate flooding messages.
1023 * @param cls closure unused
1024 * @param message message
1025 * @param peer peer identity this message is from (ignored)
1026 * @param atsi performance data (ignored)
1027 * @param atsi_count number of records in 'atsi'
1030 handle_p2p_size_estimate (void *cls, const struct GNUNET_PeerIdentity *peer,
1031 const struct GNUNET_MessageHeader *message,
1032 const struct GNUNET_ATS_Information *atsi,
1033 unsigned int atsi_count)
1035 const struct GNUNET_NSE_FloodMessage *incoming_flood;
1036 struct GNUNET_TIME_Absolute ts;
1037 struct NSEPeerEntry *peer_entry;
1038 uint32_t matching_bits;
1041 #if ENABLE_HISTOGRAM
1043 GNUNET_BIO_write_int64 (wh, GNUNET_TIME_absolute_get ().abs_value);
1045 incoming_flood = (const struct GNUNET_NSE_FloodMessage *) message;
1046 GNUNET_STATISTICS_update (stats, "# flood messages received", 1, GNUNET_NO);
1047 matching_bits = ntohl (incoming_flood->matching_bits);
1052 struct GNUNET_PeerIdentity os;
1054 GNUNET_CRYPTO_hash (&incoming_flood->pkey,
1055 sizeof (struct GNUNET_CRYPTO_RsaPublicKeyBinaryEncoded),
1057 GNUNET_snprintf (origin, sizeof (origin), "%s", GNUNET_i2s (&os));
1058 GNUNET_snprintf (pred, sizeof (pred), "%s", GNUNET_i2s (peer));
1059 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1060 "Flood at %llu from `%s' via `%s' at `%s' with bits %u\n",
1061 (unsigned long long)
1062 GNUNET_TIME_absolute_ntoh (incoming_flood->timestamp).abs_value,
1063 origin, pred, GNUNET_i2s (&my_identity),
1064 (unsigned int) matching_bits);
1068 peer_entry = GNUNET_CONTAINER_multihashmap_get (peers, &peer->hashPubKey);
1069 if (NULL == peer_entry)
1074 #if ENABLE_HISTOGRAM
1075 peer_entry->received_messages++;
1076 if (peer_entry->transmitted_messages > 0 &&
1077 peer_entry->last_transmitted_size >= matching_bits)
1078 GNUNET_STATISTICS_update(stats, "# cross messages", 1, GNUNET_NO);
1081 ts = GNUNET_TIME_absolute_ntoh (incoming_flood->timestamp);
1082 if (ts.abs_value == current_timestamp.abs_value)
1083 idx = estimate_index;
1084 else if (ts.abs_value ==
1085 current_timestamp.abs_value - gnunet_nse_interval.rel_value)
1086 idx = (estimate_index + HISTORY_SIZE - 1) % HISTORY_SIZE;
1087 else if (ts.abs_value == next_timestamp.abs_value)
1089 if (matching_bits <= ntohl (next_message.matching_bits))
1090 return GNUNET_OK; /* ignore, simply too early/late */
1091 if (GNUNET_YES != verify_message_crypto (incoming_flood))
1093 GNUNET_break_op (0);
1096 next_message = *incoming_flood;
1101 GNUNET_STATISTICS_update (stats,
1102 "# flood messages discarded (clock skew too large)",
1106 if (0 == (memcmp (peer, &my_identity, sizeof (struct GNUNET_PeerIdentity))))
1108 /* send to self, update our own estimate IF this also comes from us! */
1110 memcmp (&incoming_flood->pkey, &my_public_key, sizeof (my_public_key)))
1111 update_network_size_estimate ();
1114 if (matching_bits == ntohl (size_estimate_messages[idx].matching_bits))
1116 /* Cancel transmission in the other direction, as this peer clearly has
1117 up-to-date information already. Even if we didn't talk to this peer in
1118 the previous round, we should no longer send it stale information as it
1119 told us about the current round! */
1120 peer_entry->previous_round = GNUNET_YES;
1121 if (idx != estimate_index)
1123 /* do not transmit information for the previous round to this peer
1124 anymore (but allow current round) */
1127 /* got up-to-date information for current round, cancel transmission to
1128 * this peer altogether */
1129 if (GNUNET_SCHEDULER_NO_TASK != peer_entry->transmit_task)
1131 GNUNET_SCHEDULER_cancel (peer_entry->transmit_task);
1132 peer_entry->transmit_task = GNUNET_SCHEDULER_NO_TASK;
1133 peer_entry->where_task = __LINE__;
1135 if (peer_entry->th != NULL)
1137 GNUNET_CORE_notify_transmit_ready_cancel (peer_entry->th);
1138 peer_entry->th = NULL;
1139 peer_entry->where_th = __LINE__;
1143 if (matching_bits < ntohl (size_estimate_messages[idx].matching_bits))
1145 if ((idx < estimate_index) && (peer_entry->previous_round == GNUNET_YES)) {
1146 peer_entry->previous_round = GNUNET_NO;
1147 peer_entry->where_round = __LINE__;
1149 /* push back our result now, that peer is spreading bad information... */
1150 if (NULL == peer_entry->th)
1152 if (peer_entry->transmit_task != GNUNET_SCHEDULER_NO_TASK)
1153 GNUNET_SCHEDULER_cancel (peer_entry->transmit_task);
1154 peer_entry->transmit_task =
1155 GNUNET_SCHEDULER_add_now (&transmit_task_cb, peer_entry);
1157 /* Not closer than our most recent message, no need to do work here */
1158 GNUNET_STATISTICS_update (stats,
1159 "# flood messages ignored (had closer already)",
1163 if (GNUNET_YES != verify_message_crypto (incoming_flood))
1165 GNUNET_break_op (0);
1168 GNUNET_assert (matching_bits >
1169 ntohl (size_estimate_messages[idx].matching_bits));
1170 /* cancel transmission from us to this peer for this round */
1171 if (idx == estimate_index)
1173 /* cancel any activity for current round */
1174 // FIXME what if previous round was pending? (lost message?)
1175 if (peer_entry->transmit_task != GNUNET_SCHEDULER_NO_TASK)
1177 GNUNET_SCHEDULER_cancel (peer_entry->transmit_task);
1178 peer_entry->transmit_task = GNUNET_SCHEDULER_NO_TASK;
1179 peer_entry->where_task = __LINE__;
1181 if (peer_entry->th != NULL)
1183 GNUNET_CORE_notify_transmit_ready_cancel (peer_entry->th);
1184 peer_entry->th = NULL;
1185 peer_entry->where_th = __LINE__;
1190 /* cancel previous round only */
1191 peer_entry->previous_round = GNUNET_YES;
1193 size_estimate_messages[idx] = *incoming_flood;
1194 size_estimate_messages[idx].hop_count =
1195 htonl (ntohl (incoming_flood->hop_count) + 1);
1197 GNUNET_MAX (ntohl (incoming_flood->hop_count) + 1, hop_count_max);
1198 GNUNET_STATISTICS_set (stats,
1199 "# estimated network diameter",
1200 hop_count_max, GNUNET_NO);
1202 /* have a new, better size estimate, inform clients */
1203 update_network_size_estimate ();
1206 GNUNET_CONTAINER_multihashmap_iterate (peers, &update_flood_times,
1214 * Method called whenever a peer connects. Sets up the PeerEntry and
1215 * schedules the initial size info transmission to this peer.
1217 * @param cls closure
1218 * @param peer peer identity this notification is about
1219 * @param atsi performance data
1220 * @param atsi_count number of records in 'atsi'
1223 handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer,
1224 const struct GNUNET_ATS_Information *atsi,
1225 unsigned int atsi_count)
1227 struct NSEPeerEntry *peer_entry;
1230 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s' connected to us\n",
1233 peer_entry = GNUNET_malloc (sizeof (struct NSEPeerEntry));
1234 peer_entry->id = *peer;
1235 GNUNET_assert (GNUNET_OK ==
1236 GNUNET_CONTAINER_multihashmap_put (peers, &peer->hashPubKey,
1238 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
1239 peer_entry->transmit_task =
1240 GNUNET_SCHEDULER_add_delayed (get_transmit_delay (-1), &transmit_task_cb,
1242 GNUNET_STATISTICS_update (stats, "# peers", 1, GNUNET_NO);
1243 peer_entry->where_task = 0;
1244 peer_entry->where_round = __LINE__;
1245 peer_entry->where_th = __LINE__;
1250 * Method called whenever a peer disconnects. Deletes the PeerEntry and cancels
1251 * any pending transmission requests to that peer.
1253 * @param cls closure
1254 * @param peer peer identity this notification is about
1257 handle_core_disconnect (void *cls, const struct GNUNET_PeerIdentity *peer)
1259 struct NSEPeerEntry *pos;
1262 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Peer `%s' disconnected from us\n",
1265 pos = GNUNET_CONTAINER_multihashmap_get (peers, &peer->hashPubKey);
1271 GNUNET_assert (GNUNET_YES ==
1272 GNUNET_CONTAINER_multihashmap_remove (peers, &peer->hashPubKey,
1274 if (pos->transmit_task != GNUNET_SCHEDULER_NO_TASK) {
1275 GNUNET_SCHEDULER_cancel (pos->transmit_task);
1276 pos->transmit_task = GNUNET_SCHEDULER_NO_TASK;
1277 pos->where_task = __LINE__;
1279 if (pos->th != NULL)
1281 GNUNET_CORE_notify_transmit_ready_cancel (pos->th);
1283 pos->where_th = __LINE__;
1286 GNUNET_STATISTICS_update (stats, "# peers", -1, GNUNET_NO);
1291 * Task run during shutdown.
1297 shutdown_task (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
1299 if (flood_task != GNUNET_SCHEDULER_NO_TASK)
1301 GNUNET_SCHEDULER_cancel (flood_task);
1302 flood_task = GNUNET_SCHEDULER_NO_TASK;
1304 if (proof_task != GNUNET_SCHEDULER_NO_TASK)
1306 GNUNET_SCHEDULER_cancel (proof_task);
1307 proof_task = GNUNET_SCHEDULER_NO_TASK;
1308 write_proof (); /* remember progress */
1312 GNUNET_SERVER_notification_context_destroy (nc);
1315 if (coreAPI != NULL)
1317 GNUNET_CORE_disconnect (coreAPI);
1322 GNUNET_STATISTICS_destroy (stats, GNUNET_NO);
1327 GNUNET_CONTAINER_multihashmap_destroy (peers);
1330 if (my_private_key != NULL)
1332 GNUNET_CRYPTO_rsa_key_free (my_private_key);
1333 my_private_key = NULL;
1335 #if ENABLE_HISTOGRAM
1338 GNUNET_BIO_write_close (wh);
1346 * Called on core init/fail.
1348 * @param cls service closure
1349 * @param server handle to the server for this service
1350 * @param identity the public identity of this peer
1353 core_init (void *cls, struct GNUNET_CORE_Handle *server,
1354 const struct GNUNET_PeerIdentity *identity)
1356 struct GNUNET_TIME_Absolute now;
1357 struct GNUNET_TIME_Absolute prev_time;
1361 GNUNET_log (GNUNET_ERROR_TYPE_ERROR, "Connection to core FAILED!\n");
1362 GNUNET_SCHEDULER_shutdown ();
1366 memcmp (&my_identity, identity,
1367 sizeof (struct GNUNET_PeerIdentity)));
1368 now = GNUNET_TIME_absolute_get ();
1369 current_timestamp.abs_value =
1370 (now.abs_value / gnunet_nse_interval.rel_value) *
1371 gnunet_nse_interval.rel_value;
1373 GNUNET_TIME_absolute_add (current_timestamp, gnunet_nse_interval);
1374 estimate_index = HISTORY_SIZE - 1;
1376 if (GNUNET_YES == check_proof_of_work (&my_public_key, my_proof))
1378 int idx = (estimate_index + HISTORY_SIZE - 1) % HISTORY_SIZE;
1379 prev_time.abs_value =
1380 current_timestamp.abs_value - gnunet_nse_interval.rel_value;
1381 setup_flood_message (idx, prev_time);
1382 setup_flood_message (estimate_index, current_timestamp);
1386 GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_absolute_get_remaining
1387 (next_timestamp), &update_flood_message,
1393 * Handle network size estimate clients.
1395 * @param cls closure
1396 * @param server the initialized server
1397 * @param c configuration to use
1400 run (void *cls, struct GNUNET_SERVER_Handle *server,
1401 const struct GNUNET_CONFIGURATION_Handle *c)
1406 static const struct GNUNET_SERVER_MessageHandler handlers[] = {
1407 {&handle_start_message, NULL, GNUNET_MESSAGE_TYPE_NSE_START,
1408 sizeof (struct GNUNET_MessageHeader)},
1411 static const struct GNUNET_CORE_MessageHandler core_handlers[] = {
1412 {&handle_p2p_size_estimate, GNUNET_MESSAGE_TYPE_NSE_P2P_FLOOD,
1413 sizeof (struct GNUNET_NSE_FloodMessage)},
1419 GNUNET_CONFIGURATION_get_value_time (cfg, "NSE", "INTERVAL",
1420 &gnunet_nse_interval)) ||
1422 GNUNET_CONFIGURATION_get_value_time (cfg, "NSE", "WORKDELAY",
1423 &proof_find_delay)) ||
1425 GNUNET_CONFIGURATION_get_value_number (cfg, "NSE", "WORKBITS",
1426 &nse_work_required)))
1428 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1430 ("NSE service is lacking key configuration settings. Exiting.\n"));
1431 GNUNET_SCHEDULER_shutdown ();
1434 if (nse_work_required >= sizeof (GNUNET_HashCode) * 8)
1436 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1437 _("Invalid work requirement for NSE service. Exiting.\n"));
1438 GNUNET_SCHEDULER_shutdown ();
1444 GNUNET_CONFIGURATION_get_value_filename (cfg, "GNUNETD", "HOSTKEY",
1447 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1449 ("NSE service is lacking key configuration settings. Exiting.\n"));
1450 GNUNET_SCHEDULER_shutdown ();
1453 my_private_key = GNUNET_CRYPTO_rsa_key_create_from_file (keyfile);
1454 GNUNET_free (keyfile);
1455 if (my_private_key == NULL)
1457 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1458 _("NSE service could not access hostkey. Exiting.\n"));
1459 GNUNET_SCHEDULER_shutdown ();
1462 GNUNET_CRYPTO_rsa_key_get_public (my_private_key, &my_public_key);
1463 GNUNET_CRYPTO_hash (&my_public_key, sizeof (my_public_key),
1464 &my_identity.hashPubKey);
1466 GNUNET_CONFIGURATION_get_value_filename (cfg, "NSE", "PROOFFILE", &proof))
1468 GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
1470 ("NSE service is lacking key configuration settings. Exiting.\n"));
1471 if (my_private_key != NULL)
1473 GNUNET_CRYPTO_rsa_key_free (my_private_key);
1474 my_private_key = NULL;
1476 GNUNET_SCHEDULER_shutdown ();
1479 if ((GNUNET_YES != GNUNET_DISK_file_test (proof)) ||
1480 (sizeof (my_proof) !=
1481 GNUNET_DISK_fn_read (proof, &my_proof, sizeof (my_proof))))
1483 GNUNET_free (proof);
1485 GNUNET_SCHEDULER_add_with_priority (GNUNET_SCHEDULER_PRIORITY_IDLE,
1488 peers = GNUNET_CONTAINER_multihashmap_create (128);
1489 GNUNET_SERVER_add_handlers (server, handlers);
1490 nc = GNUNET_SERVER_notification_context_create (server, 1);
1491 /* Connect to core service and register core handlers */
1492 coreAPI = GNUNET_CORE_connect (cfg, /* Main configuration */
1493 1, NULL, /* Closure passed to functions */
1494 &core_init, /* Call core_init once connected */
1495 &handle_core_connect, /* Handle connects */
1496 &handle_core_disconnect, /* Handle disconnects */
1497 NULL, /* Don't want notified about all incoming messages */
1498 GNUNET_NO, /* For header only inbound notification */
1499 NULL, /* Don't want notified about all outbound messages */
1500 GNUNET_NO, /* For header only outbound notification */
1501 core_handlers); /* Register these handlers */
1502 GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_FOREVER_REL, &shutdown_task,
1504 #if ENABLE_HISTOGRAM
1506 GNUNET_CONFIGURATION_get_value_filename (cfg, "NSE", "HISTOGRAM", &proof))
1508 wh = GNUNET_BIO_write_open (proof);
1509 GNUNET_free (proof);
1512 if (coreAPI == NULL)
1514 GNUNET_SCHEDULER_shutdown ();
1517 stats = GNUNET_STATISTICS_create ("nse", cfg);
1522 * The main function for the statistics service.
1524 * @param argc number of arguments from the command line
1525 * @param argv command line arguments
1526 * @return 0 ok, 1 on error
1529 main (int argc, char *const *argv)
1531 return (GNUNET_OK ==
1532 GNUNET_SERVICE_run (argc, argv, "nse", GNUNET_SERVICE_OPTION_NONE,
1533 &run, NULL)) ? 0 : 1;
1536 /* end of gnunet-service-nse.c */