8 files changed, 492 insertions, 195 deletions

diff --git a/src/revocation/gnunet-revocation.c b/src/revocation/gnunet-revocation.c
index 14e23b244..8b7cf33c6 100644
--- a/src/revocation/gnunet-revocation.c
+++ b/src/revocation/gnunet-revocation.c
@@ -28,6 +28,10 @@
 #include "gnunet_revocation_service.h"
 #include "gnunet_identity_service.h"
 
+/**
+ * Pow passes
+ */
+static unsigned int pow_passes = 1;
 
 /**
  * Final status code.
@@ -55,6 +59,11 @@ static char *revoke_ego;
 static char *test_ego;
 
 /**
+ * -e option.
+ */
+static unsigned int epochs = 1;
+
+/**
  * Handle for revocation query.
  */
 static struct GNUNET_REVOCATION_Query *q;
@@ -80,10 +89,19 @@ static const struct GNUNET_CONFIGURATION_Handle *cfg;
 static unsigned long long matching_bits;
 
 /**
+ * Epoch length
+ */
+static struct GNUNET_TIME_Relative epoch_duration;
+
+/**
  * Task used for proof-of-work calculation.
  */
 static struct GNUNET_SCHEDULER_Task *pow_task;
 
+/**
+ * Proof-of-work object
+ */
+static struct GNUNET_REVOCATION_Pow proof_of_work;
 
 /**
  * Function run if the user aborts with CTRL-C.
@@ -93,6 +111,7 @@ static struct GNUNET_SCHEDULER_Task *pow_task;
 static void
 do_shutdown (void *cls)
 {
+  fprintf (stderr, "%s", _ ("Shutting down...\n"));
   if (NULL != el)
   {
     GNUNET_IDENTITY_ego_lookup_cancel (el);
@@ -188,37 +207,13 @@ print_revocation_result (void *cls, int is_valid)
 
 
 /**
- * Data needed to perform a revocation.
- */
-struct RevocationData
-{
-  /**
-   * Public key.
-   */
-  struct GNUNET_CRYPTO_EcdsaPublicKey key;
-
-  /**
-   * Revocation signature data.
-   */
-  struct GNUNET_CRYPTO_EcdsaSignature sig;
-
-  /**
-   * Proof of work (in NBO).
-   */
-  uint64_t pow GNUNET_PACKED;
-};
-
-
-/**
  * Perform the revocation.
  */
 static void
-perform_revocation (const struct RevocationData *rd)
+perform_revocation ()
 {
   h = GNUNET_REVOCATION_revoke (cfg,
-                                &rd->key,
-                                &rd->sig,
-                                rd->pow,
+                                &proof_of_work,
                                 &print_revocation_result,
                                 NULL);
 }
@@ -231,13 +226,13 @@ perform_revocation (const struct RevocationData *rd)
  * @param rd data to sync
  */
 static void
-sync_rd (const struct RevocationData *rd)
+sync_pow ()
 {
   if ((NULL != filename) &&
-      (sizeof(struct RevocationData) ==
+      (sizeof(struct GNUNET_REVOCATION_Pow) !=
        GNUNET_DISK_fn_write (filename,
-                             &rd,
-                             sizeof(rd),
+                             &proof_of_work,
+                             sizeof(struct GNUNET_REVOCATION_Pow),
                              GNUNET_DISK_PERM_USER_READ
                              | GNUNET_DISK_PERM_USER_WRITE)))
     GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_ERROR, "write", filename);
@@ -252,15 +247,16 @@ sync_rd (const struct RevocationData *rd)
 static void
 calculate_pow_shutdown (void *cls)
 {
-  struct RevocationData *rd = cls;
-
+  struct GNUNET_REVOCATION_PowCalculationHandle *ph = cls;
+  fprintf (stderr, "%s", _ ("Cancelling calculation.\n"));
+  sync_pow ();
   if (NULL != pow_task)
   {
     GNUNET_SCHEDULER_cancel (pow_task);
     pow_task = NULL;
   }
-  sync_rd (rd);
-  GNUNET_free (rd);
+  if (NULL != ph)
+    GNUNET_REVOCATION_pow_stop (ph);
 }
 
 
@@ -272,38 +268,26 @@ calculate_pow_shutdown (void *cls)
 static void
 calculate_pow (void *cls)
 {
-  struct RevocationData *rd = cls;
+  struct GNUNET_REVOCATION_PowCalculationHandle *ph = cls;
 
   /* store temporary results */
   pow_task = NULL;
-  if (0 == (rd->pow % 128))
-    sync_rd (rd);
-  /* display progress estimate */
-  if ((0 == ((1 << matching_bits) / 100 / 50)) ||
-      (0 == (rd->pow % ((1 << matching_bits) / 100 / 50))))
-    fprintf (stderr, "%s", ".");
-  if ((0 != rd->pow) && ((0 == ((1 << matching_bits) / 100)) ||
-                         (0 == (rd->pow % ((1 << matching_bits) / 100)))))
-    fprintf (stderr,
-             " - @ %3u%% (estimate)\n",
-             (unsigned int) (rd->pow * 100) / (1 << matching_bits));
+  if (0 == (pow_passes % 128))
+    sync_pow ();
   /* actually do POW calculation */
-  rd->pow++;
-  if (GNUNET_OK == GNUNET_REVOCATION_check_pow (&rd->key,
-                                                rd->pow,
-                                                (unsigned int) matching_bits))
+  if (GNUNET_OK == GNUNET_REVOCATION_pow_round (ph))
   {
     if ((NULL != filename) &&
-        (sizeof(struct RevocationData) !=
+        (sizeof(struct GNUNET_REVOCATION_Pow) !=
          GNUNET_DISK_fn_write (filename,
-                               rd,
-                               sizeof(struct RevocationData),
+                               &proof_of_work,
+                               sizeof(struct GNUNET_REVOCATION_Pow),
                                GNUNET_DISK_PERM_USER_READ
                                | GNUNET_DISK_PERM_USER_WRITE)))
       GNUNET_log_strerror_file (GNUNET_ERROR_TYPE_ERROR, "write", filename);
     if (perform)
     {
-      perform_revocation (rd);
+      perform_revocation ();
     }
     else
     {
@@ -316,7 +300,19 @@ calculate_pow (void *cls)
     }
     return;
   }
-  pow_task = GNUNET_SCHEDULER_add_now (&calculate_pow, rd);
+  pow_passes++;
+  /**
+   * Otherwise CTRL-C does not work
+   */
+  if (0 == pow_passes % 128)
+    pow_task = GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_MILLISECONDS,
+                                             &calculate_pow,
+                                             ph);
+  else
+    pow_task = GNUNET_SCHEDULER_add_delayed (GNUNET_TIME_UNIT_MILLISECONDS,
+                                             &calculate_pow,
+                                             ph);
+
 }
 
 
@@ -329,8 +325,9 @@ calculate_pow (void *cls)
 static void
 ego_callback (void *cls, const struct GNUNET_IDENTITY_Ego *ego)
 {
-  struct RevocationData *rd;
   struct GNUNET_CRYPTO_EcdsaPublicKey key;
+  const struct GNUNET_CRYPTO_EcdsaPrivateKey *privkey;
+  struct GNUNET_REVOCATION_PowCalculationHandle *ph = NULL;
 
   el = NULL;
   if (NULL == ego)
@@ -340,44 +337,55 @@ ego_callback (void *cls, const struct GNUNET_IDENTITY_Ego *ego)
     return;
   }
   GNUNET_IDENTITY_ego_get_public_key (ego, &key);
-  rd = GNUNET_new (struct RevocationData);
+  privkey = GNUNET_IDENTITY_ego_get_private_key (ego);
+  memset (&proof_of_work, 0, sizeof (proof_of_work));
   if ((NULL != filename) && (GNUNET_YES == GNUNET_DISK_file_test (filename)) &&
-      (sizeof(struct RevocationData) ==
-       GNUNET_DISK_fn_read (filename, rd, sizeof(struct RevocationData))))
+      (sizeof(proof_of_work) ==
+       GNUNET_DISK_fn_read (filename, &proof_of_work, sizeof(proof_of_work))))
   {
-    if (0 != GNUNET_memcmp (&rd->key, &key))
+    if (0 != GNUNET_memcmp (&proof_of_work.key, &key))
     {
       fprintf (stderr,
                _ ("Error: revocation certificate in `%s' is not for `%s'\n"),
                filename,
                revoke_ego);
-      GNUNET_free (rd);
       return;
     }
-  }
-  else
-  {
-    GNUNET_REVOCATION_sign_revocation (GNUNET_IDENTITY_ego_get_private_key (
-                                         ego),
-                                       &rd->sig);
-    rd->key = key;
-  }
-  if (GNUNET_YES ==
-      GNUNET_REVOCATION_check_pow (&key, rd->pow, (unsigned int) matching_bits))
-  {
-    fprintf (stderr, "%s", _ ("Revocation certificate ready\n"));
-    if (perform)
-      perform_revocation (rd);
-    else
-      GNUNET_SCHEDULER_shutdown ();
-    GNUNET_free (rd);
-    return;
+    if (GNUNET_YES ==
+        GNUNET_REVOCATION_check_pow (&proof_of_work,
+                                     (unsigned int) matching_bits,
+                                     epoch_duration))
+    {
+      fprintf (stderr, "%s", _ ("Revocation certificate ready\n"));
+      if (perform)
+        perform_revocation ();
+      else
+        GNUNET_SCHEDULER_shutdown ();
+      return;
+    }
+    /**
+     * Certificate not yet ready
+     */
+    fprintf (stderr,
+             "%s",
+             _ ("Continuing calculation where left off...\n"));
+    ph = GNUNET_REVOCATION_pow_start (&proof_of_work,
+                                      epochs,
+                                      matching_bits);
   }
   fprintf (stderr,
            "%s",
            _ ("Revocation certificate not ready, calculating proof of work\n"));
-  pow_task = GNUNET_SCHEDULER_add_now (&calculate_pow, rd);
-  GNUNET_SCHEDULER_add_shutdown (&calculate_pow_shutdown, rd);
+  if (NULL == ph)
+  {
+    GNUNET_REVOCATION_pow_init (privkey,
+                                &proof_of_work);
+    ph = GNUNET_REVOCATION_pow_start (&proof_of_work,
+                                      epochs, /* Epochs */
+                                      matching_bits);
+  }
+  pow_task = GNUNET_SCHEDULER_add_now (&calculate_pow, ph);
+  GNUNET_SCHEDULER_add_shutdown (&calculate_pow_shutdown, ph);
 }
 
 
@@ -396,7 +404,6 @@ run (void *cls,
      const struct GNUNET_CONFIGURATION_Handle *c)
 {
   struct GNUNET_CRYPTO_EcdsaPublicKey pk;
-  struct RevocationData rd;
 
   cfg = c;
   if (NULL != test_ego)
@@ -429,6 +436,17 @@ run (void *cls,
                                "WORKBITS");
     return;
   }
+  if (GNUNET_OK != GNUNET_CONFIGURATION_get_value_time (cfg,
+                                                        "REVOCATION",
+                                                        "EPOCH_DURATION",
+                                                        &epoch_duration))
+  {
+    GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR,
+                               "REVOCATION",
+                               "EPOCH_DURATION");
+    return;
+  }
+
   if (NULL != revoke_ego)
   {
     if (! perform && (NULL == filename))
@@ -445,7 +463,9 @@ run (void *cls,
   }
   if ((NULL != filename) && (perform))
   {
-    if (sizeof(rd) != GNUNET_DISK_fn_read (filename, &rd, sizeof(rd)))
+    if (sizeof(proof_of_work) != GNUNET_DISK_fn_read (filename,
+                                                      &proof_of_work,
+                                                      sizeof(proof_of_work)))
     {
       fprintf (stderr,
                _ ("Failed to read revocation certificate from `%s'\n"),
@@ -454,18 +474,20 @@ run (void *cls,
     }
     GNUNET_SCHEDULER_add_shutdown (&do_shutdown, NULL);
     if (GNUNET_YES !=
-        GNUNET_REVOCATION_check_pow (&rd.key,
-                                     rd.pow,
-                                     (unsigned int) matching_bits))
+        GNUNET_REVOCATION_check_pow (&proof_of_work,
+                                     (unsigned int) matching_bits,
+                                     epoch_duration))
     {
-      struct RevocationData *cp = GNUNET_new (struct RevocationData);
+      struct GNUNET_REVOCATION_PowCalculationHandle *ph;
+      ph = GNUNET_REVOCATION_pow_start (&proof_of_work,
+                                        epochs, /* Epochs */
+                                        matching_bits);
 
-      *cp = rd;
-      pow_task = GNUNET_SCHEDULER_add_now (&calculate_pow, cp);
-      GNUNET_SCHEDULER_add_shutdown (&calculate_pow_shutdown, cp);
+      pow_task = GNUNET_SCHEDULER_add_now (&calculate_pow, ph);
+      GNUNET_SCHEDULER_add_shutdown (&calculate_pow_shutdown, ph);
       return;
     }
-    perform_revocation (&rd);
+    perform_revocation ();
     return;
   }
   fprintf (stderr, "%s", _ ("No action specified. Nothing to do.\n"));
@@ -511,6 +533,12 @@ main (int argc, char *const *argv)
                                  gettext_noop (
                                    "test if the public key KEY has been revoked"),
                                  &test_ego),
+    GNUNET_GETOPT_option_uint ('e',
+                               "epochs",
+                               "EPOCHS",
+                               gettext_noop (
+                                 "number of epochs to calculate for"),
+                               &epochs),
 
     GNUNET_GETOPT_OPTION_END
   };
diff --git a/src/revocation/gnunet-service-revocation.c b/src/revocation/gnunet-service-revocation.c
index 3e811cd9a..3c08e8452 100644
--- a/src/revocation/gnunet-service-revocation.c
+++ b/src/revocation/gnunet-service-revocation.c
@@ -129,6 +129,11 @@ static struct GNUNET_SET_ListenHandle *revocation_union_listen_handle;
 static unsigned long long revocation_work_required;
 
 /**
+ * Length of an expiration expoch
+ */
+static struct GNUNET_TIME_Relative epoch_duration;
+
+/**
  * Our application ID for set union operations.  Must be the
  * same for all (compatible) peers.
  */
@@ -167,25 +172,15 @@ new_peer_entry (const struct GNUNET_PeerIdentity *peer)
 static int
 verify_revoke_message (const struct RevokeMessage *rm)
 {
-  if (GNUNET_YES !=
-      GNUNET_REVOCATION_check_pow (&rm->public_key,
-                                   rm->proof_of_work,
-                                   (unsigned int) revocation_work_required))
+  if (GNUNET_YES != GNUNET_REVOCATION_check_pow (&rm->proof_of_work,
+                                   (unsigned int) revocation_work_required,
+                                   epoch_duration))
   {
     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
                 "Proof of work invalid!\n");
     GNUNET_break_op (0);
     return GNUNET_NO;
   }
-  if (GNUNET_OK !=
-      GNUNET_CRYPTO_ecdsa_verify_ (GNUNET_SIGNATURE_PURPOSE_REVOCATION,
-                                   &rm->purpose,
-                                   &rm->signature,
-                                   &rm->public_key))
-  {
-    GNUNET_break_op (0);
-    return GNUNET_NO;
-  }
   return GNUNET_YES;
 }
 
@@ -308,7 +303,7 @@ publicize_rm (const struct RevokeMessage *rm)
   struct GNUNET_HashCode hc;
   struct GNUNET_SET_Element e;
 
-  GNUNET_CRYPTO_hash (&rm->public_key,
+  GNUNET_CRYPTO_hash (&rm->proof_of_work.key,
                       sizeof(struct GNUNET_CRYPTO_EcdsaPublicKey),
                       &hc);
   if (GNUNET_YES ==
@@ -848,6 +843,20 @@ run (void *cls,
     GNUNET_free (fn);
     return;
   }
+  if (GNUNET_OK !=
+      GNUNET_CONFIGURATION_get_value_time (cfg,
+                                             "REVOCATION",
+                                             "EPOCH_DURATION",
+                                             &epoch_duration))
+  {
+    GNUNET_log_config_missing (GNUNET_ERROR_TYPE_ERROR,
+                               "REVOCATION",
+                               "EPOCH_DURATION");
+    GNUNET_SCHEDULER_shutdown ();
+    GNUNET_free (fn);
+    return;
+  }
+
   revocation_set = GNUNET_SET_create (cfg,
                                       GNUNET_SET_OPERATION_UNION);
   revocation_union_listen_handle
@@ -893,7 +902,7 @@ run (void *cls,
       return;
     }
     GNUNET_break (0 == ntohl (rm->reserved));
-    GNUNET_CRYPTO_hash (&rm->public_key,
+    GNUNET_CRYPTO_hash (&rm->proof_of_work.key,
                         sizeof(struct GNUNET_CRYPTO_EcdsaPublicKey),
                         &hc);
     GNUNET_break (GNUNET_OK ==
diff --git a/src/revocation/plugin_block_revocation.c b/src/revocation/plugin_block_revocation.c
index 8d16b8781..291c56f70 100644
--- a/src/revocation/plugin_block_revocation.c
+++ b/src/revocation/plugin_block_revocation.c
@@ -52,6 +52,7 @@
 struct InternalContext
 {
   unsigned int matching_bits;
+  struct GNUNET_TIME_Relative epoch_duration;
 };
 
 
@@ -142,24 +143,15 @@ block_plugin_revocation_evaluate (void *cls,
     GNUNET_break_op (0);
     return GNUNET_BLOCK_EVALUATION_RESULT_INVALID;
   }
-  if (GNUNET_YES !=
-      GNUNET_REVOCATION_check_pow (&rm->public_key,
-                                   rm->proof_of_work,
-                                   ic->matching_bits))
+  if (0 >=
+      GNUNET_REVOCATION_check_pow (&rm->proof_of_work,
+                                   ic->matching_bits,
+                                   ic->epoch_duration))
   {
     GNUNET_break_op (0);
     return GNUNET_BLOCK_EVALUATION_RESULT_INVALID;
   }
-  if (GNUNET_OK !=
-      GNUNET_CRYPTO_ecdsa_verify_ (GNUNET_SIGNATURE_PURPOSE_REVOCATION,
-                                   &rm->purpose,
-                                   &rm->signature,
-                                   &rm->public_key))
-  {
-    GNUNET_break_op (0);
-    return GNUNET_BLOCK_EVALUATION_RESULT_INVALID;
-  }
-  GNUNET_CRYPTO_hash (&rm->public_key,
+  GNUNET_CRYPTO_hash (&rm->proof_of_work.key,
                       sizeof(struct GNUNET_CRYPTO_EcdsaPublicKey),
                       &chash);
   if (GNUNET_YES ==
@@ -195,7 +187,7 @@ block_plugin_revocation_get_key (void *cls,
     GNUNET_break_op (0);
     return GNUNET_SYSERR;
   }
-  GNUNET_CRYPTO_hash (&rm->public_key,
+  GNUNET_CRYPTO_hash (&rm->proof_of_work.key,
                       sizeof(struct GNUNET_CRYPTO_EcdsaPublicKey),
                       key);
   return GNUNET_OK;
@@ -218,6 +210,7 @@ libgnunet_plugin_block_revocation_init (void *cls)
   struct GNUNET_BLOCK_PluginFunctions *api;
   struct InternalContext *ic;
   unsigned long long matching_bits;
+  struct GNUNET_TIME_Relative epoch_duration;
 
   if (GNUNET_OK !=
       GNUNET_CONFIGURATION_get_value_number (cfg,
@@ -225,6 +218,12 @@ libgnunet_plugin_block_revocation_init (void *cls)
                                              "WORKBITS",
                                              &matching_bits))
     return NULL;
+  if (GNUNET_OK !=
+      GNUNET_CONFIGURATION_get_value_time (cfg,
+                                           "REVOCATION",
+                                           "EPOCH_DURATION",
+                                           &epoch_duration))
+    return NULL;
 
   api = GNUNET_new (struct GNUNET_BLOCK_PluginFunctions);
   api->evaluate = &block_plugin_revocation_evaluate;
@@ -233,6 +232,7 @@ libgnunet_plugin_block_revocation_init (void *cls)
   api->types = types;
   ic = GNUNET_new (struct InternalContext);
   ic->matching_bits = (unsigned int) matching_bits;
+  ic->epoch_duration = epoch_duration;
   api->cls = ic;
   return api;
 }
diff --git a/src/revocation/revocation.conf.in b/src/revocation/revocation.conf.in
index 5ad41cd49..346168785 100644
--- a/src/revocation/revocation.conf.in
+++ b/src/revocation/revocation.conf.in
@@ -14,5 +14,6 @@ UNIX_MATCH_GID = YES
 # (using only a single-core) with SCRYPT.
 # DO NOT CHANGE THIS VALUE, doing so will break the protocol!
 WORKBITS = 25
+EPOCH_DURATION = 356 d
 
 DATABASE = $GNUNET_DATA_HOME/revocation.dat
diff --git a/src/revocation/revocation.h b/src/revocation/revocation.h
index b6e7a07ec..868c2b853 100644
--- a/src/revocation/revocation.h
+++ b/src/revocation/revocation.h
@@ -27,6 +27,7 @@
 #define REVOCATION_H
 
 #include "gnunet_util_lib.h"
+#include "gnunet_revocation_service.h"
 
 GNUNET_NETWORK_STRUCT_BEGIN
 
@@ -91,23 +92,7 @@ struct RevokeMessage
   /**
    * Number that causes a hash collision with the @e public_key.
    */
-  uint64_t proof_of_work GNUNET_PACKED;
-
-  /**
-   * Signature confirming revocation.
-   */
-  struct GNUNET_CRYPTO_EcdsaSignature signature;
-
-  /**
-   * Must have purpose #GNUNET_SIGNATURE_PURPOSE_REVOCATION,
-   * size expands over the public key. (@deprecated)
-   */
-  struct GNUNET_CRYPTO_EccSignaturePurpose purpose;
-
-  /**
-   * Key to revoke.
-   */
-  struct GNUNET_CRYPTO_EcdsaPublicKey public_key;
+  struct GNUNET_REVOCATION_Pow proof_of_work;
 };
 
 
diff --git a/src/revocation/revocation_api.c b/src/revocation/revocation_api.c
index 4755d4816..18a312ab8 100644
--- a/src/revocation/revocation_api.c
+++ b/src/revocation/revocation_api.c
@@ -27,8 +27,7 @@
 #include "gnunet_signatures.h"
 #include "gnunet_protocols.h"
 #include "revocation.h"
-#include <gcrypt.h>
-
+#include <inttypes.h>
 
 /**
  * Handle for the key revocation query.
@@ -53,6 +52,58 @@ struct GNUNET_REVOCATION_Query
 
 
 /**
+ * Helper struct that holds a found pow nonce
+ * and the corresponding number of leading zeroes.
+ */
+struct BestPow
+{
+  /**
+   * PoW nonce
+   */
+  uint64_t pow;
+
+  /**
+   * Corresponding zero bits in hash
+   */
+  unsigned int bits;
+};
+
+
+/**
+ * The handle to a PoW calculation.
+ * Used in iterative PoW rounds.
+ */
+struct GNUNET_REVOCATION_PowCalculationHandle
+{
+  /**
+   * Current set of found PoWs
+   */
+  struct BestPow best[POW_COUNT];
+
+  /**
+   * The final PoW result data structure.
+   */
+  struct GNUNET_REVOCATION_Pow *pow;
+
+  /**
+   * The current nonce to try
+   */
+  uint64_t current_pow;
+
+  /**
+   * Epochs how long the PoW should be valid.
+   * This is added on top of the difficulty in the PoW.
+   */
+  unsigned int epochs;
+
+  /**
+   * The difficulty (leading zeros) to achieve.
+   */
+  unsigned int difficulty;
+
+};
+
+/**
  * Generic error handler, called with the appropriate
  * error code and the same closure specified at the creation of
  * the message queue.
@@ -235,6 +286,7 @@ handle_revocation_response (void *cls,
  * @param key public key of the key to revoke
  * @param sig signature to use on the revocation (should have been
  *            created using #GNUNET_REVOCATION_sign_revocation).
+ * @param ts  revocation timestamp
  * @param pow proof of work to use (should have been created by
  *            iteratively calling #GNUNET_REVOCATION_check_pow)
  * @param func funtion to call with the result of the check
@@ -245,9 +297,7 @@ handle_revocation_response (void *cls,
  */
 struct GNUNET_REVOCATION_Handle *
 GNUNET_REVOCATION_revoke (const struct GNUNET_CONFIGURATION_Handle *cfg,
-                          const struct GNUNET_CRYPTO_EcdsaPublicKey *key,
-                          const struct GNUNET_CRYPTO_EcdsaSignature *sig,
-                          uint64_t pow,
+                          const struct GNUNET_REVOCATION_Pow *pow,
                           GNUNET_REVOCATION_Callback func,
                           void *func_cls)
 {
@@ -261,23 +311,39 @@ GNUNET_REVOCATION_revoke (const struct GNUNET_CONFIGURATION_Handle *cfg,
     GNUNET_MQ_handler_end ()
   };
   unsigned long long matching_bits;
+  struct GNUNET_TIME_Relative epoch_duration;
   struct RevokeMessage *rm;
   struct GNUNET_MQ_Envelope *env;
 
-  if ((GNUNET_OK ==
+  if ((GNUNET_OK !=
        GNUNET_CONFIGURATION_get_value_number (cfg,
                                               "REVOCATION",
                                               "WORKBITS",
-                                              &matching_bits)) &&
-      (GNUNET_YES !=
-       GNUNET_REVOCATION_check_pow (key,
-                                    pow,
-                                    (unsigned int) matching_bits)))
+                                              &matching_bits)))
+  {
+    GNUNET_break (0);
+    GNUNET_free (h);
+    return NULL;
+  }
+  if ((GNUNET_OK !=
+       GNUNET_CONFIGURATION_get_value_time (cfg,
+                                            "REVOCATION",
+                                            "EPOCH_DURATION",
+                                            &epoch_duration)))
   {
     GNUNET_break (0);
     GNUNET_free (h);
     return NULL;
   }
+  if (GNUNET_YES != GNUNET_REVOCATION_check_pow (pow,
+                                                 (unsigned int) matching_bits,
+                                                 epoch_duration))
+  {
+    GNUNET_break (0);
+    GNUNET_free (h);
+    return NULL;
+  }
+
 
   h->mq = GNUNET_CLIENT_connect (cfg,
                                  "revocation",
@@ -294,12 +360,7 @@ GNUNET_REVOCATION_revoke (const struct GNUNET_CONFIGURATION_Handle *cfg,
   env = GNUNET_MQ_msg (rm,
                        GNUNET_MESSAGE_TYPE_REVOCATION_REVOKE);
   rm->reserved = htonl (0);
-  rm->proof_of_work = pow;
-  rm->purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_REVOCATION);
-  rm->purpose.size = htonl (sizeof(struct GNUNET_CRYPTO_EccSignaturePurpose)
-                            + sizeof(struct GNUNET_CRYPTO_EcdsaPublicKey));
-  rm->public_key = *key;
-  rm->signature = *sig;
+  rm->proof_of_work = *pow;
   GNUNET_MQ_send (h->mq,
                   env);
   return h;
@@ -342,56 +403,263 @@ count_leading_zeroes (const struct GNUNET_HashCode *hash)
 
 
 /**
- * Check if the given proof-of-work value
- * would be acceptable for revoking the given key.
+ * Calculate the average zeros in the pows.
  *
- * @param key key to check for
- * @param pow proof of work value
+ * @param ph the PowHandle
+ * @return the average number of zeroes.
+ */
+static unsigned int
+calculate_score (const struct GNUNET_REVOCATION_PowCalculationHandle *ph)
+{
+  double sum = 0.0;
+  for (unsigned int j = 0; j<POW_COUNT; j++)
+    sum += ph->best[j].bits;
+  double avg = sum / POW_COUNT;
+  return avg;
+}
+
+
+/**
+ * Check if the given proof-of-work is valid.
+ *
+ * @param pow proof of work
  * @param matching_bits how many bits must match (configuration)
+ * @param epoch_duration length of single epoch in configuration
+ * @return #GNUNET_YES if the @a pow is acceptable, #GNUNET_NO if not
+ */
+enum GNUNET_GenericReturnValue
+GNUNET_REVOCATION_check_pow (const struct GNUNET_REVOCATION_Pow *pow,
+                             unsigned int difficulty,
+                             struct GNUNET_TIME_Relative epoch_duration)
+{
+  char buf[sizeof(struct GNUNET_CRYPTO_EcdsaPublicKey)
+           + sizeof (struct GNUNET_TIME_AbsoluteNBO)
+           + sizeof (uint64_t)] GNUNET_ALIGN;
+  struct GNUNET_REVOCATION_SignaturePurpose spurp;
+  struct GNUNET_HashCode result;
+  struct GNUNET_TIME_Absolute ts;
+  struct GNUNET_TIME_Absolute exp;
+  struct GNUNET_TIME_Relative ttl;
+  struct GNUNET_TIME_Relative buffer;
+  unsigned int score = 0;
+  unsigned int tmp_score = 0;
+  unsigned int epochs;
+  uint64_t pow_val;
+
+  /**
+   * Check if signature valid
+   */
+  spurp.key = pow->key;
+  spurp.timestamp = pow->timestamp;
+  spurp.purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_REVOCATION);
+  spurp.purpose.size = htonl (sizeof(struct GNUNET_CRYPTO_EccSignaturePurpose)
+                              + sizeof(struct GNUNET_CRYPTO_EcdsaPublicKey)
+                              + sizeof (struct GNUNET_TIME_AbsoluteNBO));
+  if (GNUNET_OK !=
+      GNUNET_CRYPTO_ecdsa_verify_ (GNUNET_SIGNATURE_PURPOSE_REVOCATION,
+                                   &spurp.purpose,
+                                   &pow->signature,
+                                   &pow->key))
+  {
+    GNUNET_log (GNUNET_ERROR_TYPE_ERROR,
+                "Proof of work signature invalid!\n");
+    return GNUNET_NO;
+  }
+
+  /**
+   * First, check if any duplicates are in the PoW set
+   */
+  for (unsigned int i = 0; i < POW_COUNT; i++)
+  {
+    for (unsigned int j = i + 1; j < POW_COUNT; j++)
+    {
+      if (pow->pow[i] == pow->pow[j])
+        return GNUNET_NO;
+    }
+  }
+  GNUNET_memcpy (&buf[sizeof(uint64_t)],
+                 &pow->timestamp,
+                 sizeof (uint64_t));
+  GNUNET_memcpy (&buf[sizeof(uint64_t) * 2],
+                 &pow->key,
+                 sizeof(struct GNUNET_CRYPTO_EcdsaPublicKey));
+  for (unsigned int i = 0; i < POW_COUNT; i++)
+  {
+    pow_val = GNUNET_ntohll (pow->pow[i]);
+    GNUNET_memcpy (buf, &pow_val, sizeof(uint64_t));
+    GNUNET_CRYPTO_pow_hash ("gnunet-revocation-proof-of-work",
+                            buf,
+                            sizeof(buf),
+                            &result);
+    tmp_score = count_leading_zeroes (&result);
+    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
+                "Score %u with %" PRIu64 " (#%u)\n",
+                tmp_score, pow_val, i);
+    score += tmp_score;
+
+  }
+  score = score / POW_COUNT;
+  if (score < difficulty)
+    return GNUNET_NO;
+  epochs = score - difficulty;
+
+  /**
+   * Check expiration
+   */
+  ts = GNUNET_TIME_absolute_ntoh (pow->timestamp);
+  ttl = GNUNET_TIME_relative_multiply (epoch_duration,
+                                       epochs);
+  /**
+   * Extend by 10% for unsynchronized clocks
+   */
+  buffer = GNUNET_TIME_relative_divide (epoch_duration,
+                                        10);
+  exp = GNUNET_TIME_absolute_add (ts, ttl);
+  exp = GNUNET_TIME_absolute_add (exp,
+                                  buffer);
+
+  if (0 != GNUNET_TIME_absolute_get_remaining (ts).rel_value_us)
+    return GNUNET_NO; /* Not yet valid. */
+  /* Revert to actual start time */
+  ts = GNUNET_TIME_absolute_add (ts,
+                                 buffer);
+
+  if (0 == GNUNET_TIME_absolute_get_remaining (exp).rel_value_us)
+    return GNUNET_NO; /* expired */
+  return GNUNET_YES;
+}
+
+
+/**
+ * Initializes a fresh PoW computation.
+ *
+ * @param key the key to calculate the PoW for.
+ * @param[out] pow starting point for PoW calculation (not yet valid)
+ */
+void
+GNUNET_REVOCATION_pow_init (const struct GNUNET_CRYPTO_EcdsaPrivateKey *key,
+                            struct GNUNET_REVOCATION_Pow *pow)
+{
+  struct GNUNET_TIME_Absolute ts = GNUNET_TIME_absolute_get ();
+  struct GNUNET_REVOCATION_SignaturePurpose rp;
+
+  /**
+   * Predate the validity period to prevent rejections due to
+   * unsynchronized clocks
+   */
+  ts = GNUNET_TIME_absolute_subtract (ts,
+                                      GNUNET_TIME_UNIT_WEEKS);
+
+  pow->timestamp = GNUNET_TIME_absolute_hton (ts);
+  rp.timestamp = pow->timestamp;
+  rp.purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_REVOCATION);
+  rp.purpose.size = htonl (sizeof(struct GNUNET_CRYPTO_EccSignaturePurpose)
+                           + sizeof(struct GNUNET_CRYPTO_EcdsaPublicKey)
+                           + sizeof (struct GNUNET_TIME_AbsoluteNBO));
+  GNUNET_CRYPTO_ecdsa_key_get_public (key, &pow->key);
+  rp.key = pow->key;
+  GNUNET_assert (GNUNET_OK ==
+                 GNUNET_CRYPTO_ecdsa_sign_ (key,
+                                            &rp.purpose,
+                                            &pow->signature));
+}
+
+
+/**
+ * Starts a proof-of-work calculation given the pow object as well as
+ * target epochs and difficulty.
+ *
+ * @param pow the PoW to based calculations on.
+ * @param epochs the number of epochs for which the PoW must be valid.
+ * @param difficulty the base difficulty of the PoW.
+ * @return a handle for use in PoW rounds
+ */
+struct GNUNET_REVOCATION_PowCalculationHandle*
+GNUNET_REVOCATION_pow_start (struct GNUNET_REVOCATION_Pow *pow,
+                             int epochs,
+                             unsigned int difficulty)
+{
+  struct GNUNET_REVOCATION_PowCalculationHandle *pc;
+
+  pc = GNUNET_new (struct GNUNET_REVOCATION_PowCalculationHandle);
+  pc->pow = pow;
+  pc->current_pow = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
+                                              UINT64_MAX);
+  pc->difficulty = difficulty;
+  pc->epochs = epochs;
+  return pc;
+}
+
+
+/**
+ * Calculate a key revocation valid for broadcasting for a number
+ * of epochs.
+ *
+ * @param pc handle to the PoW, initially called with NULL.
+ * @param epochs number of epochs for which the revocation must be valid.
+ * @param pow current pow value to try
+ * @param difficulty current base difficulty to achieve
  * @return #GNUNET_YES if the @a pow is acceptable, #GNUNET_NO if not
  */
-int
-GNUNET_REVOCATION_check_pow (const struct GNUNET_CRYPTO_EcdsaPublicKey *key,
-                             uint64_t pow,
-                             unsigned int matching_bits)
+enum GNUNET_GenericReturnValue
+GNUNET_REVOCATION_pow_round (struct GNUNET_REVOCATION_PowCalculationHandle *pc)
 {
   char buf[sizeof(struct GNUNET_CRYPTO_EcdsaPublicKey)
-           + sizeof(pow)] GNUNET_ALIGN;
+           + sizeof (uint64_t)
+           + sizeof (uint64_t)] GNUNET_ALIGN;
   struct GNUNET_HashCode result;
+  unsigned int zeros;
+
+  pc->current_pow++;
 
-  GNUNET_memcpy (buf, &pow, sizeof(pow));
-  GNUNET_memcpy (&buf[sizeof(pow)], key,
+  /**
+   * Do not try duplicates
+   */
+  for (unsigned int i = 0; i < POW_COUNT; i++)
+    if (pc->current_pow == pc->best[i].pow)
+      return GNUNET_NO;
+
+  GNUNET_memcpy (buf, &pc->current_pow, sizeof(uint64_t));
+  GNUNET_memcpy (&buf[sizeof(uint64_t)],
+                 &pc->pow->timestamp,
+                 sizeof (uint64_t));
+  GNUNET_memcpy (&buf[sizeof(uint64_t) * 2],
+                 &pc->pow->key,
                  sizeof(struct GNUNET_CRYPTO_EcdsaPublicKey));
   GNUNET_CRYPTO_pow_hash ("gnunet-revocation-proof-of-work",
                           buf,
                           sizeof(buf),
                           &result);
-  return (count_leading_zeroes (&result) >=
-          matching_bits) ? GNUNET_YES : GNUNET_NO;
+  zeros = count_leading_zeroes (&result);
+  for (unsigned int i = 0; i < POW_COUNT; i++)
+  {
+    if (pc->best[i].bits < zeros)
+    {
+      pc->best[i].bits = zeros;
+      pc->best[i].pow = pc->current_pow;
+      pc->pow->pow[i] = GNUNET_htonll (pc->current_pow);
+      GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
+                  "New best score %u with %" PRIu64 " (#%u)\n",
+                  zeros, pc->current_pow, i);
+      break;
+    }
+  }
+  return calculate_score (pc) >= pc->difficulty + pc->epochs ? GNUNET_YES :
+         GNUNET_NO;
 }
 
 
 /**
- * Create a revocation signature.
+ * Stop a PoW calculation
  *
- * @param key private key of the key to revoke
- * @param sig where to write the revocation signature
+ * @param pc the calculation to clean up
+ * @return #GNUNET_YES if pow valid, #GNUNET_NO if pow was set but is not
+ * valid
  */
 void
-GNUNET_REVOCATION_sign_revocation (const struct
-                                   GNUNET_CRYPTO_EcdsaPrivateKey *key,
-                                   struct GNUNET_CRYPTO_EcdsaSignature *sig)
+GNUNET_REVOCATION_pow_stop (struct GNUNET_REVOCATION_PowCalculationHandle *pc)
 {
-  struct RevokeMessage rm;
-
-  rm.purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_REVOCATION);
-  rm.purpose.size = htonl (sizeof(struct GNUNET_CRYPTO_EccSignaturePurpose)
-                           + sizeof(struct GNUNET_CRYPTO_EcdsaPublicKey));
-  GNUNET_CRYPTO_ecdsa_key_get_public (key, &rm.public_key);
-  GNUNET_assert (GNUNET_OK ==
-                 GNUNET_CRYPTO_ecdsa_sign_ (key,
-                                            &rm.purpose,
-                                            sig));
+  GNUNET_free (pc);
 }
 
 
diff --git a/src/revocation/test_revocation.c b/src/revocation/test_revocation.c
index 012bac09e..f193d5f6c 100644
--- a/src/revocation/test_revocation.c
+++ b/src/revocation/test_revocation.c
@@ -45,7 +45,7 @@ struct TestPeer
   struct GNUNET_IDENTITY_EgoLookup *ego_lookup;
   struct GNUNET_REVOCATION_Handle *revok_handle;
   struct GNUNET_CORE_Handle *ch;
-  uint64_t pow;
+  struct GNUNET_REVOCATION_PowCalculationHandle *pow;
 };
 
 static struct TestPeer testpeers[2];
@@ -131,7 +131,7 @@ check_revocation (void *cls)
 
 
 static void
-revocation_cb (void *cls, int is_valid)
+revocation_cb (void *cls, enum GNUNET_GenericReturnValue is_valid)
 {
   testpeers[1].revok_handle = NULL;
   if (GNUNET_NO == is_valid)
@@ -141,11 +141,14 @@ revocation_cb (void *cls, int is_valid)
   }
 }
 
+struct GNUNET_REVOCATION_Pow proof_of_work;
+
 
 static void
 ego_cb (void *cls, const struct GNUNET_IDENTITY_Ego *ego)
 {
   static int completed = 0;
+  const struct GNUNET_CRYPTO_EcdsaPrivateKey *privkey;
 
   if ((NULL != ego) && (cls == &testpeers[0]))
   {
@@ -159,17 +162,20 @@ ego_cb (void *cls, const struct GNUNET_IDENTITY_Ego *ego)
     testpeers[1].ego_lookup = NULL;
     testpeers[1].privkey = GNUNET_IDENTITY_ego_get_private_key (ego);
     GNUNET_IDENTITY_ego_get_public_key (ego, &testpeers[1].pubkey);
-    GNUNET_REVOCATION_sign_revocation (testpeers[1].privkey, &testpeers[1].sig);
-
     GNUNET_log (GNUNET_ERROR_TYPE_INFO, "Calculating proof of work...\n");
-    testpeers[1].pow = 0;
+    privkey = GNUNET_IDENTITY_ego_get_private_key (ego);
+    memset (&proof_of_work, 0, sizeof (proof_of_work));
+    GNUNET_REVOCATION_pow_init (privkey,
+                                &proof_of_work);
+    testpeers[1].pow = GNUNET_REVOCATION_pow_start (&proof_of_work,
+                                                    1,
+                                                    5);
     int res =
-      GNUNET_REVOCATION_check_pow (&testpeers[1].pubkey, testpeers[1].pow, 5);
+      GNUNET_REVOCATION_pow_round (testpeers[1].pow);
     while (GNUNET_OK != res)
     {
-      testpeers[1].pow++;
       res =
-        GNUNET_REVOCATION_check_pow (&testpeers[1].pubkey, testpeers[1].pow, 5);
+        GNUNET_REVOCATION_pow_round (testpeers[1].pow);
     }
     fprintf (stderr, "Done calculating proof of work\n");
     completed++;
@@ -178,11 +184,10 @@ ego_cb (void *cls, const struct GNUNET_IDENTITY_Ego *ego)
   {
     GNUNET_log (GNUNET_ERROR_TYPE_INFO, "Egos retrieved\n");
     testpeers[1].revok_handle = GNUNET_REVOCATION_revoke (testpeers[1].cfg,
-                                                          &testpeers[1].pubkey,
-                                                          &testpeers[1].sig,
-                                                          testpeers[1].pow,
+                                                          &proof_of_work,
                                                           &revocation_cb,
                                                           NULL);
+    GNUNET_REVOCATION_pow_stop (testpeers[1].pow);
   }
 }
 
diff --git a/src/revocation/test_revocation.conf b/src/revocation/test_revocation.conf
index 3b04150c1..66e2cdcc9 100644
--- a/src/revocation/test_revocation.conf
+++ b/src/revocation/test_revocation.conf
@@ -7,6 +7,7 @@ SERVICEHOME=$GNUNET_TMP/test-revocation-service
 [revocation]
 WORKBITS = 3
 IMMEDIATE_START = YES
+EPOCH_DURATION = 365 d
 
 [identity]
 # Directory where we store information about our egos