Merge branch '12498_ed25519_keys_v6'

Fixed numerous conflicts, and ported code to use new base64 api.

29 files changed, 2860 insertions, 255 deletions

diff --git a/src/or/channel.c b/src/or/channel.c
index bf0387f10e..af095026e4 100644
--- a/src/or/channel.c
+++ b/src/or/channel.c
@@ -4431,10 +4431,10 @@ channel_num_circuits(channel_t *chan)
  * This is called when setting up a channel and replaces the old
  * connection_or_set_circid_type()
  */
-void
-channel_set_circid_type(channel_t *chan,
-                        crypto_pk_t *identity_rcvd,
-                        int consider_identity)
+MOCK_IMPL(void,
+channel_set_circid_type,(channel_t *chan,
+                         crypto_pk_t *identity_rcvd,
+                         int consider_identity))
 {
   int started_here;
   crypto_pk_t *our_identity;
diff --git a/src/or/channel.h b/src/or/channel.h
index ecc2a092e4..2b38ca7e19 100644
--- a/src/or/channel.h
+++ b/src/or/channel.h
@@ -562,8 +562,9 @@ int channel_matches_extend_info(channel_t *chan, extend_info_t *extend_info);
 int channel_matches_target_addr_for_extend(channel_t *chan,
                                            const tor_addr_t *target);
 unsigned int channel_num_circuits(channel_t *chan);
-void channel_set_circid_type(channel_t *chan, crypto_pk_t *identity_rcvd,
-                             int consider_identity);
+MOCK_DECL(void,channel_set_circid_type,(channel_t *chan,
+                                        crypto_pk_t *identity_rcvd,
+                                        int consider_identity));
 void channel_timestamp_client(channel_t *chan);
 void channel_update_xmit_queue_size(channel_t *chan);
 
diff --git a/src/or/channeltls.c b/src/or/channeltls.c
index 1cf697ccc5..ecf02182fc 100644
--- a/src/or/channeltls.c
+++ b/src/or/channeltls.c
@@ -13,6 +13,8 @@
 
 #define TOR_CHANNEL_INTERNAL_
 
+#define CHANNELTLS_PRIVATE
+
 #include "or.h"
 #include "channel.h"
 #include "channeltls.h"
@@ -22,6 +24,7 @@
 #include "connection.h"
 #include "connection_or.h"
 #include "control.h"
+#include "link_handshake.h"
 #include "relay.h"
 #include "rephist.h"
 #include "router.h"
@@ -48,9 +51,6 @@ uint64_t stats_n_authorize_cells_processed = 0;
 /** Active listener, if any */
 channel_listener_t *channel_tls_listener = NULL;
 
-/* Utility function declarations */
-static void channel_tls_common_init(channel_tls_t *tlschan);
-
 /* channel_tls_t method declarations */
 
 static void channel_tls_close_method(channel_t *chan);
@@ -92,12 +92,6 @@ static void channel_tls_process_versions_cell(var_cell_t *cell,
                                               channel_tls_t *tlschan);
 static void channel_tls_process_netinfo_cell(cell_t *cell,
                                              channel_tls_t *tlschan);
-static void channel_tls_process_certs_cell(var_cell_t *cell,
-                                           channel_tls_t *tlschan);
-static void channel_tls_process_auth_challenge_cell(var_cell_t *cell,
-                                                    channel_tls_t *tlschan);
-static void channel_tls_process_authenticate_cell(var_cell_t *cell,
-                                                  channel_tls_t *tlschan);
 static int command_allowed_before_handshake(uint8_t command);
 static int enter_v3_handshake_with_cell(var_cell_t *cell,
                                         channel_tls_t *tlschan);
@@ -107,7 +101,7 @@ static int enter_v3_handshake_with_cell(var_cell_t *cell,
  * and channel_tls_handle_incoming().
  */
 
-static void
+STATIC void
 channel_tls_common_init(channel_tls_t *tlschan)
 {
   channel_t *chan;
@@ -1747,16 +1741,17 @@ channel_tls_process_netinfo_cell(cell_t *cell, channel_tls_t *chan)
  * If it's the server side, wait for an AUTHENTICATE cell.
  */
 
-static void
+STATIC void
 channel_tls_process_certs_cell(var_cell_t *cell, channel_tls_t *chan)
 {
-  tor_cert_t *link_cert = NULL;
-  tor_cert_t *id_cert = NULL;
-  tor_cert_t *auth_cert = NULL;
-  uint8_t *ptr;
+#define MAX_CERT_TYPE_WANTED OR_CERT_TYPE_AUTH_1024
+  tor_x509_cert_t *certs[MAX_CERT_TYPE_WANTED + 1];
   int n_certs, i;
+  certs_cell_t *cc = NULL;
+
   int send_netinfo = 0;
 
+  memset(certs, 0, sizeof(certs));
   tor_assert(cell);
   tor_assert(chan);
   tor_assert(chan->conn);
@@ -1786,63 +1781,41 @@ channel_tls_process_certs_cell(var_cell_t *cell, channel_tls_t *chan)
   if (cell->circ_id)
     ERR("It had a nonzero circuit ID");
 
-  n_certs = cell->payload[0];
-  ptr = cell->payload + 1;
+  if (certs_cell_parse(&cc, cell->payload, cell->payload_len) < 0)
+    ERR("It couldn't be parsed.");
+
+  n_certs = cc->n_certs;
+
   for (i = 0; i < n_certs; ++i) {
-    uint8_t cert_type;
-    uint16_t cert_len;
-    if (cell->payload_len < 3)
-      goto truncated;
-    if (ptr > cell->payload + cell->payload_len - 3) {
-      goto truncated;
-    }
-    cert_type = *ptr;
-    cert_len = ntohs(get_uint16(ptr+1));
-    if (cell->payload_len < 3 + cert_len)
-      goto truncated;
-    if (ptr > cell->payload + cell->payload_len - cert_len - 3) {
-      goto truncated;
-    }
-    if (cert_type == OR_CERT_TYPE_TLS_LINK ||
-        cert_type == OR_CERT_TYPE_ID_1024 ||
-        cert_type == OR_CERT_TYPE_AUTH_1024) {
-      tor_cert_t *cert = tor_cert_decode(ptr + 3, cert_len);
-      if (!cert) {
-        log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
-               "Received undecodable certificate in CERTS cell from %s:%d",
-               safe_str(chan->conn->base_.address),
-               chan->conn->base_.port);
+    certs_cell_cert_t *c = certs_cell_get_certs(cc, i);
+
+    uint16_t cert_type = c->cert_type;
+    uint16_t cert_len = c->cert_len;
+    uint8_t *cert_body = certs_cell_cert_getarray_body(c);
+
+    if (cert_type > MAX_CERT_TYPE_WANTED)
+      continue;
+
+    tor_x509_cert_t *cert = tor_x509_cert_decode(cert_body, cert_len);
+    if (!cert) {
+      log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+             "Received undecodable certificate in CERTS cell from %s:%d",
+             safe_str(chan->conn->base_.address),
+             chan->conn->base_.port);
+    } else {
+      if (certs[cert_type]) {
+        tor_x509_cert_free(cert);
+        ERR("Duplicate x509 certificate");
       } else {
-        if (cert_type == OR_CERT_TYPE_TLS_LINK) {
-          if (link_cert) {
-            tor_cert_free(cert);
-            ERR("Too many TLS_LINK certificates");
-          }
-          link_cert = cert;
-        } else if (cert_type == OR_CERT_TYPE_ID_1024) {
-          if (id_cert) {
-            tor_cert_free(cert);
-            ERR("Too many ID_1024 certificates");
-          }
-          id_cert = cert;
-        } else if (cert_type == OR_CERT_TYPE_AUTH_1024) {
-          if (auth_cert) {
-            tor_cert_free(cert);
-            ERR("Too many AUTH_1024 certificates");
-          }
-          auth_cert = cert;
-        } else {
-          tor_cert_free(cert);
-        }
+        certs[cert_type] = cert;
       }
     }
-    ptr += 3 + cert_len;
-    continue;
-
-  truncated:
-    ERR("It ends in the middle of a certificate");
   }
 
+  tor_x509_cert_t *id_cert = certs[OR_CERT_TYPE_ID_1024];
+  tor_x509_cert_t *auth_cert = certs[OR_CERT_TYPE_AUTH_1024];
+  tor_x509_cert_t *link_cert = certs[OR_CERT_TYPE_TLS_LINK];
+
   if (chan->conn->handshake_state->started_here) {
     int severity;
     if (! (id_cert && link_cert))
@@ -1867,7 +1840,7 @@ channel_tls_process_certs_cell(var_cell_t *cell, channel_tls_t *chan)
 
     chan->conn->handshake_state->authenticated = 1;
     {
-      const digests_t *id_digests = tor_cert_get_id_digests(id_cert);
+      const digests_t *id_digests = tor_x509_cert_get_id_digests(id_cert);
       crypto_pk_t *identity_rcvd;
       if (!id_digests)
         ERR("Couldn't compute digests for key in ID cert");
@@ -1891,7 +1864,7 @@ channel_tls_process_certs_cell(var_cell_t *cell, channel_tls_t *chan)
              safe_str(chan->conn->base_.address), chan->conn->base_.port);
 
     chan->conn->handshake_state->id_cert = id_cert;
-    id_cert = NULL;
+    certs[OR_CERT_TYPE_ID_1024] = NULL;
 
     if (!public_server_mode(get_options())) {
       /* If we initiated the connection and we are not a public server, we
@@ -1918,7 +1891,7 @@ channel_tls_process_certs_cell(var_cell_t *cell, channel_tls_t *chan)
 
     chan->conn->handshake_state->id_cert = id_cert;
     chan->conn->handshake_state->auth_cert = auth_cert;
-    id_cert = auth_cert = NULL;
+    certs[OR_CERT_TYPE_ID_1024] = certs[OR_CERT_TYPE_AUTH_1024] = NULL;
   }
 
   chan->conn->handshake_state->received_certs_cell = 1;
@@ -1932,9 +1905,10 @@ channel_tls_process_certs_cell(var_cell_t *cell, channel_tls_t *chan)
   }
 
  err:
-  tor_cert_free(id_cert);
-  tor_cert_free(link_cert);
-  tor_cert_free(auth_cert);
+  for (unsigned i = 0; i < ARRAY_LENGTH(certs); ++i) {
+    tor_x509_cert_free(certs[i]);
+  }
+  certs_cell_free(cc);
 #undef ERR
 }
 
@@ -1949,11 +1923,11 @@ channel_tls_process_certs_cell(var_cell_t *cell, channel_tls_t *chan)
  * want to authenticate, send an AUTHENTICATE cell and then a NETINFO cell.
  */
 
-static void
+STATIC void
 channel_tls_process_auth_challenge_cell(var_cell_t *cell, channel_tls_t *chan)
 {
   int n_types, i, use_type = -1;
-  uint8_t *cp;
+  auth_challenge_cell_t *ac = NULL;
 
   tor_assert(cell);
   tor_assert(chan);
@@ -1966,7 +1940,7 @@ channel_tls_process_auth_challenge_cell(var_cell_t *cell, channel_tls_t *chan)
            safe_str(chan->conn->base_.address),                 \
            chan->conn->base_.port, (s));                        \
     connection_or_close_for_error(chan->conn, 0);               \
-    return;                                                     \
+    goto done;                                                  \
   } while (0)
 
   if (chan->conn->base_.state != OR_CONN_STATE_OR_HANDSHAKING_V3)
@@ -1979,19 +1953,17 @@ channel_tls_process_auth_challenge_cell(var_cell_t *cell, channel_tls_t *chan)
     ERR("We already received one");
   if (!(chan->conn->handshake_state->received_certs_cell))
     ERR("We haven't gotten a CERTS cell yet");
-  if (cell->payload_len < OR_AUTH_CHALLENGE_LEN + 2)
-    ERR("It was too short");
   if (cell->circ_id)
     ERR("It had a nonzero circuit ID");
 
-  n_types = ntohs(get_uint16(cell->payload + OR_AUTH_CHALLENGE_LEN));
-  if (cell->payload_len < OR_AUTH_CHALLENGE_LEN + 2 + 2*n_types)
-    ERR("It looks truncated");
+  if (auth_challenge_cell_parse(&ac, cell->payload, cell->payload_len) < 0)
+    ERR("It was not well-formed.");
+
+  n_types = ac->n_methods;
 
   /* Now see if there is an authentication type we can use */
-  cp = cell->payload+OR_AUTH_CHALLENGE_LEN + 2;
-  for (i = 0; i < n_types; ++i, cp += 2) {
-    uint16_t authtype = ntohs(get_uint16(cp));
+  for (i = 0; i < n_types; ++i) {
+    uint16_t authtype = auth_challenge_cell_get_methods(ac, i);
     if (authtype == AUTHTYPE_RSA_SHA256_TLSSECRET)
       use_type = authtype;
   }
@@ -2002,7 +1974,7 @@ channel_tls_process_auth_challenge_cell(var_cell_t *cell, channel_tls_t *chan)
     /* If we're not a public server then we don't want to authenticate on a
        connection we originated, and we already sent a NETINFO cell when we
        got the CERTS cell. We have nothing more to do. */
-    return;
+    goto done;
   }
 
   if (use_type >= 0) {
@@ -2016,7 +1988,7 @@ channel_tls_process_auth_challenge_cell(var_cell_t *cell, channel_tls_t *chan)
       log_warn(LD_OR,
                "Couldn't send authenticate cell");
       connection_or_close_for_error(chan->conn, 0);
-      return;
+      goto done;
     }
   } else {
     log_info(LD_OR,
@@ -2029,9 +2001,12 @@ channel_tls_process_auth_challenge_cell(var_cell_t *cell, channel_tls_t *chan)
   if (connection_or_send_netinfo(chan->conn) < 0) {
     log_warn(LD_OR, "Couldn't send netinfo cell");
     connection_or_close_for_error(chan->conn, 0);
-    return;
+    goto done;
   }
 
+done:
+  auth_challenge_cell_free(ac);
+
 #undef ERR
 }
 
@@ -2045,10 +2020,10 @@ channel_tls_process_auth_challenge_cell(var_cell_t *cell, channel_tls_t *chan)
  * the identity of the router on the other side of the connection.
  */
 
-static void
+STATIC void
 channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
 {
-  uint8_t expected[V3_AUTH_FIXED_PART_LEN];
+  uint8_t expected[V3_AUTH_FIXED_PART_LEN+256];
   const uint8_t *auth;
   int authlen;
 
@@ -2104,11 +2079,13 @@ channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
   if (authlen < V3_AUTH_BODY_LEN + 1)
     ERR("Authenticator was too short");
 
-  if (connection_or_compute_authenticate_cell_body(
-                        chan->conn, expected, sizeof(expected), NULL, 1) < 0)
+  ssize_t bodylen =
+    connection_or_compute_authenticate_cell_body(
+                        chan->conn, expected, sizeof(expected), NULL, 1);
+  if (bodylen < 0 || bodylen != V3_AUTH_FIXED_PART_LEN)
     ERR("Couldn't compute expected AUTHENTICATE cell body");
 
-  if (tor_memneq(expected, auth, sizeof(expected)))
+  if (tor_memneq(expected, auth, bodylen))
     ERR("Some field in the AUTHENTICATE cell body was not as expected");
 
   {
@@ -2154,7 +2131,7 @@ channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
     crypto_pk_t *identity_rcvd =
       tor_tls_cert_get_key(chan->conn->handshake_state->id_cert);
     const digests_t *id_digests =
-      tor_cert_get_id_digests(chan->conn->handshake_state->id_cert);
+      tor_x509_cert_get_id_digests(chan->conn->handshake_state->id_cert);
 
     /* This must exist; we checked key type when reading the cert. */
     tor_assert(id_digests);
diff --git a/src/or/channeltls.h b/src/or/channeltls.h
index 507429420b..a0df9faac2 100644
--- a/src/or/channeltls.h
+++ b/src/or/channeltls.h
@@ -52,5 +52,15 @@ void channel_tls_update_marks(or_connection_t *conn);
 /* Cleanup at shutdown */
 void channel_tls_free_all(void);
 
+#ifdef CHANNELTLS_PRIVATE
+STATIC void channel_tls_process_certs_cell(var_cell_t *cell,
+                                           channel_tls_t *tlschan);
+STATIC void channel_tls_process_auth_challenge_cell(var_cell_t *cell,
+                                                    channel_tls_t *tlschan);
+STATIC void channel_tls_common_init(channel_tls_t *tlschan);
+STATIC void channel_tls_process_authenticate_cell(var_cell_t *cell,
+                                                  channel_tls_t *tlschan);
+#endif
+
 #endif
 
diff --git a/src/or/config.c b/src/or/config.c
index e4a2d1c5ae..ef249a653b 100644
--- a/src/or/config.c
+++ b/src/or/config.c
@@ -300,6 +300,7 @@ static config_var_t option_vars_[] = {
   VAR("ServerTransportPlugin",   LINELIST, ServerTransportPlugin,  NULL),
   V(ServerTransportListenAddr,   LINELIST, NULL),
   V(ServerTransportOptions,      LINELIST, NULL),
+  V(SigningKeyLifetime,          INTERVAL, "30 days"),
   V(Socks4Proxy,                 STRING,   NULL),
   V(Socks5Proxy,                 STRING,   NULL),
   V(Socks5ProxyUsername,         STRING,   NULL),
@@ -358,6 +359,13 @@ static config_var_t option_vars_[] = {
   V(TestingTorNetwork,           BOOL,     "0"),
   V(TestingMinExitFlagThreshold, MEMUNIT,  "0"),
   V(TestingMinFastFlagThreshold, MEMUNIT,  "0"),
+
+  V(TestingLinkCertLifetime,          INTERVAL, "2 days"),
+  V(TestingAuthKeyLifetime,          INTERVAL, "2 days"),
+  V(TestingLinkKeySlop,              INTERVAL, "3 hours"),
+  V(TestingAuthKeySlop,              INTERVAL, "3 hours"),
+  V(TestingSigningKeySlop,           INTERVAL, "1 day"),
+
   V(OptimisticData,              AUTOBOOL, "auto"),
   V(PortForwarding,              BOOL,     "0"),
   V(PortForwardingHelper,        FILENAME, "tor-fw-helper"),
@@ -3688,8 +3696,20 @@ options_validate(or_options_t *old_options, or_options_t *options,
   CHECK_DEFAULT(TestingDescriptorMaxDownloadTries);
   CHECK_DEFAULT(TestingMicrodescMaxDownloadTries);
   CHECK_DEFAULT(TestingCertMaxDownloadTries);
+  CHECK_DEFAULT(TestingAuthKeyLifetime);
+  CHECK_DEFAULT(TestingLinkCertLifetime);
+  CHECK_DEFAULT(TestingSigningKeySlop);
+  CHECK_DEFAULT(TestingAuthKeySlop);
+  CHECK_DEFAULT(TestingLinkKeySlop);
 #undef CHECK_DEFAULT
 
+  if (options->SigningKeyLifetime < options->TestingSigningKeySlop*2)
+    REJECT("SigningKeyLifetime is too short.");
+  if (options->TestingLinkCertLifetime < options->TestingAuthKeySlop*2)
+    REJECT("LinkCertLifetime is too short.");
+  if (options->TestingAuthKeyLifetime < options->TestingLinkKeySlop*2)
+    REJECT("TestingAuthKeyLifetime is too short.");
+
   if (options->TestingV3AuthInitialVotingInterval
       < MIN_VOTE_INTERVAL_TESTING_INITIAL) {
     REJECT("TestingV3AuthInitialVotingInterval is insanely low.");
diff --git a/src/or/config.h b/src/or/config.h
index 74b28f45ca..0ee1e1a3c4 100644
--- a/src/or/config.h
+++ b/src/or/config.h
@@ -61,6 +61,10 @@ char *options_get_datadir_fname2_suffix(const or_options_t *options,
  * get_datadir_fname2_suffix.  */
 #define get_datadir_fname2(sub1,sub2) \
   get_datadir_fname2_suffix((sub1), (sub2), NULL)
+/** Return a newly allocated string containing datadir/sub1/sub2 relative to
+ * opts.  See get_datadir_fname2_suffix.  */
+#define options_get_datadir_fname2(opts,sub1,sub2)                      \
+  options_get_datadir_fname2_suffix((opts),(sub1), (sub2), NULL)
 /** Return a newly allocated string containing datadir/sub1suffix.  See
  * get_datadir_fname2_suffix. */
 #define get_datadir_fname_suffix(sub1, suffix) \
diff --git a/src/or/connection_or.c b/src/or/connection_or.c
index e0dff1c915..48128d6335 100644
--- a/src/or/connection_or.c
+++ b/src/or/connection_or.c
@@ -30,6 +30,7 @@
 #include "entrynodes.h"
 #include "geoip.h"
 #include "main.h"
+#include "link_handshake.h"
 #include "networkstatus.h"
 #include "nodelist.h"
 #include "reasons.h"
@@ -1318,8 +1319,8 @@ connection_or_close_normally(or_connection_t *orconn, int flush)
  * the error state.
  */
 
-void
-connection_or_close_for_error(or_connection_t *orconn, int flush)
+MOCK_IMPL(void,
+connection_or_close_for_error,(or_connection_t *orconn, int flush))
 {
   channel_t *chan = NULL;
 
@@ -1879,8 +1880,8 @@ or_handshake_state_free(or_handshake_state_t *state)
     return;
   crypto_digest_free(state->digest_sent);
   crypto_digest_free(state->digest_received);
-  tor_cert_free(state->auth_cert);
-  tor_cert_free(state->id_cert);
+  tor_x509_cert_free(state->auth_cert);
+  tor_x509_cert_free(state->id_cert);
   memwipe(state, 0xBE, sizeof(or_handshake_state_t));
   tor_free(state);
 }
@@ -2013,9 +2014,9 @@ connection_or_write_cell_to_buf(const cell_t *cell, or_connection_t *conn)
  * <b>conn</b>'s outbuf.  Right now, this <em>DOES NOT</em> support cells that
  * affect a circuit.
  */
-void
-connection_or_write_var_cell_to_buf(const var_cell_t *cell,
-                                    or_connection_t *conn)
+MOCK_IMPL(void,
+connection_or_write_var_cell_to_buf,(const var_cell_t *cell,
+                                     or_connection_t *conn))
 {
   int n;
   char hdr[VAR_CELL_MAX_HEADER_SIZE];
@@ -2158,8 +2159,8 @@ connection_or_send_versions(or_connection_t *conn, int v3_plus)
 
 /** Send a NETINFO cell on <b>conn</b>, telling the other server what we know
  * about their address, our address, and the current time. */
-int
-connection_or_send_netinfo(or_connection_t *conn)
+MOCK_IMPL(int,
+connection_or_send_netinfo,(or_connection_t *conn))
 {
   cell_t cell;
   time_t now = time(NULL);
@@ -2228,7 +2229,7 @@ connection_or_send_netinfo(or_connection_t *conn)
 int
 connection_or_send_certs_cell(or_connection_t *conn)
 {
-  const tor_cert_t *link_cert = NULL, *id_cert = NULL;
+  const tor_x509_cert_t *link_cert = NULL, *id_cert = NULL;
   const uint8_t *link_encoded = NULL, *id_encoded = NULL;
   size_t link_len, id_len;
   var_cell_t *cell;
@@ -2243,8 +2244,8 @@ connection_or_send_certs_cell(or_connection_t *conn)
   server_mode = ! conn->handshake_state->started_here;
   if (tor_tls_get_my_certs(server_mode, &link_cert, &id_cert) < 0)
     return -1;
-  tor_cert_get_der(link_cert, &link_encoded, &link_len);
-  tor_cert_get_der(id_cert, &id_encoded, &id_len);
+  tor_x509_cert_get_der(link_cert, &link_encoded, &link_len);
+  tor_x509_cert_get_der(id_cert, &id_encoded, &id_len);
 
   cell_len = 1 /* 1 byte: num certs in cell */ +
              2 * ( 1 + 2 ) /* For each cert: 1 byte for type, 2 for length */ +
@@ -2280,28 +2281,37 @@ connection_or_send_certs_cell(or_connection_t *conn)
 int
 connection_or_send_auth_challenge_cell(or_connection_t *conn)
 {
-  var_cell_t *cell;
-  uint8_t *cp;
-  uint8_t challenge[OR_AUTH_CHALLENGE_LEN];
+  var_cell_t *cell = NULL;
+  int r = -1;
   tor_assert(conn->base_.state == OR_CONN_STATE_OR_HANDSHAKING_V3);
 
   if (! conn->handshake_state)
     return -1;
 
-  if (crypto_rand((char*)challenge, OR_AUTH_CHALLENGE_LEN) < 0)
-    return -1;
-  cell = var_cell_new(OR_AUTH_CHALLENGE_LEN + 4);
+  auth_challenge_cell_t *ac = auth_challenge_cell_new();
+
+  if (crypto_rand((char*)ac->challenge, sizeof(ac->challenge)) < 0)
+    goto done;
+
+  auth_challenge_cell_add_methods(ac, AUTHTYPE_RSA_SHA256_TLSSECRET);
+  auth_challenge_cell_set_n_methods(ac,
+                                    auth_challenge_cell_getlen_methods(ac));
+
+  cell = var_cell_new(auth_challenge_cell_encoded_len(ac));
+  ssize_t len = auth_challenge_cell_encode(cell->payload, cell->payload_len,
+                                           ac);
+  if (len != cell->payload_len)
+    goto done;
   cell->command = CELL_AUTH_CHALLENGE;
-  memcpy(cell->payload, challenge, OR_AUTH_CHALLENGE_LEN);
-  cp = cell->payload + OR_AUTH_CHALLENGE_LEN;
-  set_uint16(cp, htons(1)); /* We recognize one authentication type. */
-  set_uint16(cp+2, htons(AUTHTYPE_RSA_SHA256_TLSSECRET));
 
   connection_or_write_var_cell_to_buf(cell, conn);
+  r = 0;
+
+ done:
   var_cell_free(cell);
-  memwipe(challenge, 0, sizeof(challenge));
+  auth_challenge_cell_free(ac);
 
-  return 0;
+  return r;
 }
 
 /** Compute the main body of an AUTHENTICATE cell that a client can use
@@ -2328,28 +2338,28 @@ connection_or_compute_authenticate_cell_body(or_connection_t *conn,
                                              crypto_pk_t *signing_key,
                                              int server)
 {
-  uint8_t *ptr;
+  auth1_t *auth = NULL;
+  auth_ctx_t *ctx = auth_ctx_new();
+  int result;
 
   /* assert state is reasonable XXXX */
 
-  if (outlen < V3_AUTH_FIXED_PART_LEN ||
-      (!server && outlen < V3_AUTH_BODY_LEN))
-    return -1;
+  ctx->is_ed = 0;
 
-  ptr = out;
+  auth = auth1_new();
 
   /* Type: 8 bytes. */
-  memcpy(ptr, "AUTH0001", 8);
-  ptr += 8;
+  memcpy(auth1_getarray_type(auth), "AUTH0001", 8);
 
   {
-    const tor_cert_t *id_cert=NULL, *link_cert=NULL;
+    const tor_x509_cert_t *id_cert=NULL, *link_cert=NULL;
     const digests_t *my_digests, *their_digests;
     const uint8_t *my_id, *their_id, *client_id, *server_id;
     if (tor_tls_get_my_certs(server, &link_cert, &id_cert))
       return -1;
-    my_digests = tor_cert_get_id_digests(id_cert);
-    their_digests = tor_cert_get_id_digests(conn->handshake_state->id_cert);
+    my_digests = tor_x509_cert_get_id_digests(id_cert);
+    their_digests =
+      tor_x509_cert_get_id_digests(conn->handshake_state->id_cert);
     tor_assert(my_digests);
     tor_assert(their_digests);
     my_id = (uint8_t*)my_digests->d[DIGEST_SHA256];
@@ -2359,12 +2369,10 @@ connection_or_compute_authenticate_cell_body(or_connection_t *conn,
     server_id = server ? my_id : their_id;
 
     /* Client ID digest: 32 octets. */
-    memcpy(ptr, client_id, 32);
-    ptr += 32;
+    memcpy(auth->cid, client_id, 32);
 
     /* Server ID digest: 32 octets. */
-    memcpy(ptr, server_id, 32);
-    ptr += 32;
+    memcpy(auth->sid, server_id, 32);
   }
 
   {
@@ -2378,73 +2386,101 @@ connection_or_compute_authenticate_cell_body(or_connection_t *conn,
     }
 
     /* Server log digest : 32 octets */
-    crypto_digest_get_digest(server_d, (char*)ptr, 32);
-    ptr += 32;
+    crypto_digest_get_digest(server_d, (char*)auth->slog, 32);
 
     /* Client log digest : 32 octets */
-    crypto_digest_get_digest(client_d, (char*)ptr, 32);
-    ptr += 32;
+    crypto_digest_get_digest(client_d, (char*)auth->clog, 32);
   }
 
   {
     /* Digest of cert used on TLS link : 32 octets. */
-    const tor_cert_t *cert = NULL;
-    tor_cert_t *freecert = NULL;
+    const tor_x509_cert_t *cert = NULL;
+    tor_x509_cert_t *freecert = NULL;
     if (server) {
       tor_tls_get_my_certs(1, &cert, NULL);
     } else {
       freecert = tor_tls_get_peer_cert(conn->tls);
       cert = freecert;
     }
-    if (!cert)
-      return -1;
-    memcpy(ptr, tor_cert_get_cert_digests(cert)->d[DIGEST_SHA256], 32);
+    if (!cert) {
+      log_warn(LD_OR, "Unable to find cert when making AUTH1 data.");
+      goto err;
+    }
+
+    memcpy(auth->scert,
+           tor_x509_cert_get_cert_digests(cert)->d[DIGEST_SHA256], 32);
 
     if (freecert)
-      tor_cert_free(freecert);
-    ptr += 32;
+      tor_x509_cert_free(freecert);
   }
 
   /* HMAC of clientrandom and serverrandom using master key : 32 octets */
-  tor_tls_get_tlssecrets(conn->tls, ptr);
-  ptr += 32;
-
-  tor_assert(ptr - out == V3_AUTH_FIXED_PART_LEN);
-
-  if (server)
-    return V3_AUTH_FIXED_PART_LEN; // ptr-out
+  tor_tls_get_tlssecrets(conn->tls, auth->tlssecrets);
 
   /* 8 octets were reserved for the current time, but we're trying to get out
    * of the habit of sending time around willynilly.  Fortunately, nothing
    * checks it.  That's followed by 16 bytes of nonce. */
-  crypto_rand((char*)ptr, 24);
-  ptr += 24;
+  crypto_rand((char*)auth->rand, 24);
 
-  tor_assert(ptr - out == V3_AUTH_BODY_LEN);
+  ssize_t len;
+  if ((len = auth1_encode(out, outlen, auth, ctx)) < 0) {
+    log_warn(LD_OR, "Unable to encode signed part of AUTH1 data.");
+    goto err;
+  }
 
-  if (!signing_key)
-    return V3_AUTH_BODY_LEN; // ptr - out
+  if (server) {
+    auth1_t *tmp = NULL;
+    ssize_t len2 = auth1_parse(&tmp, out, len, ctx);
+    if (!tmp) {
+      log_warn(LD_OR, "Unable to parse signed part of AUTH1 data.");
+      goto err;
+    }
+    result = (int) (tmp->end_of_fixed_part - out);
+    auth1_free(tmp);
+    if (len2 != len) {
+      log_warn(LD_OR, "Mismatched length when re-parsing AUTH1 data.");
+      goto err;
+    }
+    goto done;
+  }
+
+  if (signing_key) {
+    auth1_setlen_sig(auth, crypto_pk_keysize(signing_key));
 
-  {
-    int siglen;
     char d[32];
-    crypto_digest256(d, (char*)out, ptr-out, DIGEST_SHA256);
-    siglen = crypto_pk_private_sign(signing_key,
-                                    (char*)ptr, outlen - (ptr-out),
+    crypto_digest256(d, (char*)out, len, DIGEST_SHA256);
+    int siglen = crypto_pk_private_sign(signing_key,
+                                    (char*)auth1_getarray_sig(auth),
+                                    auth1_getlen_sig(auth),
                                     d, 32);
-    if (siglen < 0)
+    if (siglen < 0) {
+      log_warn(LD_OR, "Unable to sign AUTH1 data.");
       return -1;
+    }
 
-    ptr += siglen;
-    tor_assert(ptr <= out+outlen);
-    return (int)(ptr - out);
+    auth1_setlen_sig(auth, siglen);
+
+    len = auth1_encode(out, outlen, auth, ctx);
+    if (len < 0) {
+      log_warn(LD_OR, "Unable to encode signed AUTH1 data.");
+      goto err;
+    }
   }
+  result = (int) len;
+  goto done;
+
+ err:
+  result = -1;
+ done:
+  auth1_free(auth);
+  auth_ctx_free(ctx);
+  return result;
 }
 
 /** Send an AUTHENTICATE cell on the connection <b>conn</b>.  Return 0 on
  * success, -1 on failure */
-int
-connection_or_send_authenticate_cell(or_connection_t *conn, int authtype)
+MOCK_IMPL(int,
+connection_or_send_authenticate_cell,(or_connection_t *conn, int authtype))
 {
   var_cell_t *cell;
   crypto_pk_t *pk = tor_tls_get_my_client_auth_key();
diff --git a/src/or/connection_or.h b/src/or/connection_or.h
index fc261c6bac..3877fd5a13 100644
--- a/src/or/connection_or.h
+++ b/src/or/connection_or.h
@@ -43,7 +43,8 @@ MOCK_DECL(or_connection_t *,
            const char *id_digest, channel_tls_t *chan));
 
 void connection_or_close_normally(or_connection_t *orconn, int flush);
-void connection_or_close_for_error(or_connection_t *orconn, int flush);
+MOCK_DECL(void,connection_or_close_for_error,
+          (or_connection_t *orconn, int flush));
 
 void connection_or_report_broken_states(int severity, int domain);
 
@@ -77,17 +78,18 @@ void or_handshake_state_record_var_cell(or_connection_t *conn,
 int connection_or_set_state_open(or_connection_t *conn);
 void connection_or_write_cell_to_buf(const cell_t *cell,
                                      or_connection_t *conn);
-void connection_or_write_var_cell_to_buf(const var_cell_t *cell,
-                                         or_connection_t *conn);
+MOCK_DECL(void,connection_or_write_var_cell_to_buf,(const var_cell_t *cell,
+                                                   or_connection_t *conn));
 int connection_or_send_versions(or_connection_t *conn, int v3_plus);
-int connection_or_send_netinfo(or_connection_t *conn);
+MOCK_DECL(int,connection_or_send_netinfo,(or_connection_t *conn));
 int connection_or_send_certs_cell(or_connection_t *conn);
 int connection_or_send_auth_challenge_cell(or_connection_t *conn);
 int connection_or_compute_authenticate_cell_body(or_connection_t *conn,
                                                  uint8_t *out, size_t outlen,
                                                  crypto_pk_t *signing_key,
                                                  int server);
-int connection_or_send_authenticate_cell(or_connection_t *conn, int type);
+MOCK_DECL(int,connection_or_send_authenticate_cell,
+          (or_connection_t *conn, int type));
 
 int is_or_protocol_version_known(uint16_t version);
 
diff --git a/src/or/dircollate.c b/src/or/dircollate.c
new file mode 100644
index 0000000000..20dfb357a8
--- /dev/null
+++ b/src/or/dircollate.c
@@ -0,0 +1,257 @@
+/* Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2014, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file dircollate.c
+ *
+ * \brief Collation code for figuring out which identities to vote for in
+ *   the directory voting process.
+ */
+
+#define DIRCOLLATE_PRIVATE
+#include "dircollate.h"
+#include "dirvote.h"
+
+static void dircollator_collate_by_rsa(dircollator_t *dc);
+static void dircollator_collate_by_ed25519(dircollator_t *dc);
+
+typedef struct ddmap_entry_s {
+  HT_ENTRY(ddmap_entry_s) node;
+  uint8_t d[DIGEST_LEN + DIGEST256_LEN];
+  vote_routerstatus_t *vrs_lst[FLEXIBLE_ARRAY_MEMBER];
+} ddmap_entry_t;
+
+struct double_digest_map_s *by_both_ids;
+
+static void
+ddmap_entry_free(ddmap_entry_t *e)
+{
+  tor_free(e);
+}
+
+static ddmap_entry_t *
+ddmap_entry_new(int n_votes)
+{
+  return tor_malloc_zero(STRUCT_OFFSET(ddmap_entry_t, vrs_lst) +
+                         sizeof(vote_routerstatus_t *) * n_votes);
+}
+
+static unsigned
+ddmap_entry_hash(const ddmap_entry_t *ent)
+{
+  return (unsigned) siphash24g(ent->d, sizeof(ent->d));
+}
+
+static unsigned
+ddmap_entry_eq(const ddmap_entry_t *a, const ddmap_entry_t *b)
+{
+  return fast_memeq(a->d, b->d, sizeof(a->d));
+}
+
+static void
+ddmap_entry_set_digests(ddmap_entry_t *ent,
+                        const uint8_t *rsa_sha1,
+                        const uint8_t *ed25519)
+{
+  memcpy(ent->d, rsa_sha1, DIGEST_LEN);
+  memcpy(ent->d + DIGEST_LEN, ed25519, DIGEST256_LEN);
+}
+
+HT_PROTOTYPE(double_digest_map, ddmap_entry_s, node, ddmap_entry_hash, ddmap_entry_eq);
+HT_GENERATE2(double_digest_map, ddmap_entry_s, node, ddmap_entry_hash, ddmap_entry_eq, 0.6, tor_reallocarray, tor_free_);
+static void
+dircollator_add_routerstatus(dircollator_t *dc,
+                             int vote_num,
+                             networkstatus_t *vote,
+                             vote_routerstatus_t *vrs)
+{
+  const char *id = vrs->status.identity_digest;
+
+  (void) vote;
+  vote_routerstatus_t **vrs_lst = digestmap_get(dc->by_rsa_sha1, id);
+  if (NULL == vrs_lst) {
+    vrs_lst = tor_calloc(sizeof(vote_routerstatus_t *), dc->n_votes);
+    digestmap_set(dc->by_rsa_sha1, id, vrs_lst);
+  }
+  tor_assert(vrs_lst[vote_num] == NULL);
+  vrs_lst[vote_num] = vrs;
+
+  const uint8_t *ed = vrs->ed25519_id;
+
+  if (tor_mem_is_zero((char*)ed, DIGEST256_LEN))
+    return;
+
+  ddmap_entry_t search, *found;
+  memset(&search, 0, sizeof(search));
+  ddmap_entry_set_digests(&search, (const uint8_t *)id, ed);
+  found = HT_FIND(double_digest_map, &dc->by_both_ids, &search);
+  if (NULL == found) {
+    found = ddmap_entry_new(dc->n_votes);
+    ddmap_entry_set_digests(found, (const uint8_t *)id, ed);
+    HT_INSERT(double_digest_map, &dc->by_both_ids, found);
+  }
+  vrs_lst = found->vrs_lst;
+  tor_assert(vrs_lst[vote_num] == NULL);
+  vrs_lst[vote_num] = vrs;
+}
+
+dircollator_t *
+dircollator_new(int n_votes, int n_authorities)
+{
+  dircollator_t *dc = tor_malloc_zero(sizeof(dircollator_t));
+
+  tor_assert(n_votes <= n_authorities);
+
+  dc->n_votes = n_votes;
+  dc->n_authorities = n_authorities;
+
+  dc->by_rsa_sha1 = digestmap_new();
+  HT_INIT(double_digest_map, &dc->by_both_ids);
+
+  return dc;
+}
+
+void
+dircollator_free(dircollator_t *dc)
+{
+  if (!dc)
+    return;
+
+  if (dc->by_collated_rsa_sha1 != dc->by_rsa_sha1)
+    digestmap_free(dc->by_collated_rsa_sha1, NULL);
+
+  digestmap_free(dc->by_rsa_sha1, tor_free_);
+
+  ddmap_entry_t **e, **next, *this;
+  for (e = HT_START(double_digest_map, &dc->by_both_ids);
+       e != NULL; e = next) {
+    this = *e;
+    next = HT_NEXT_RMV(double_digest_map, &dc->by_both_ids, e);
+    ddmap_entry_free(this);
+  }
+  HT_CLEAR(double_digest_map, &dc->by_both_ids);
+
+  tor_free(dc);
+}
+
+void
+dircollator_add_vote(dircollator_t *dc, networkstatus_t *v)
+{
+  tor_assert(v->type == NS_TYPE_VOTE);
+  tor_assert(dc->next_vote_num < dc->n_votes);
+  tor_assert(!dc->is_collated);
+
+  const int votenum = dc->next_vote_num++;
+
+  SMARTLIST_FOREACH_BEGIN(v->routerstatus_list, vote_routerstatus_t *, vrs) {
+    dircollator_add_routerstatus(dc, votenum, v, vrs);
+  } SMARTLIST_FOREACH_END(vrs);
+}
+
+void
+dircollator_collate(dircollator_t *dc, int consensus_method)
+{
+  tor_assert(!dc->is_collated);
+  dc->all_rsa_sha1_lst = smartlist_new();
+
+  if (consensus_method < MIN_METHOD_FOR_ED25519_ID_VOTING + 10/*XXX*/)
+    dircollator_collate_by_rsa(dc);
+  else
+    dircollator_collate_by_ed25519(dc);
+
+  smartlist_sort_digests(dc->all_rsa_sha1_lst);
+  dc->is_collated = 1;
+}
+
+static void
+dircollator_collate_by_rsa(dircollator_t *dc)
+{
+  const int total_authorities = dc->n_authorities;
+
+  DIGESTMAP_FOREACH(dc->by_rsa_sha1, k, vote_routerstatus_t **, vrs_lst) {
+    int n = 0, i;
+    for (i = 0; i < dc->n_votes; ++i) {
+      if (vrs_lst[i] != NULL)
+        ++n;
+    }
+
+    if (n <= total_authorities / 2)
+      continue;
+
+    smartlist_add(dc->all_rsa_sha1_lst, (char *)k);
+  } DIGESTMAP_FOREACH_END;
+
+  dc->by_collated_rsa_sha1 = dc->by_rsa_sha1;
+}
+
+static void
+dircollator_collate_by_ed25519(dircollator_t *dc)
+{
+  const int total_authorities = dc->n_authorities;
+  digestmap_t *rsa_digests = digestmap_new();
+
+  ddmap_entry_t **iter;
+
+  HT_FOREACH(iter, double_digest_map, &dc->by_both_ids) {
+    ddmap_entry_t *ent = *iter;
+    int n = 0, i;
+    for (i = 0; i < dc->n_votes; ++i) {
+      if (ent->vrs_lst[i] != NULL)
+        ++n;
+    }
+
+    if (n <= total_authorities / 2)
+      continue;
+
+    vote_routerstatus_t **vrs_lst2 = digestmap_get(dc->by_rsa_sha1,
+                                                   (char*)ent->d);
+    tor_assert(vrs_lst2);
+
+    for (i = 0; i < dc->n_votes; ++i) {
+      if (ent->vrs_lst[i] != NULL) {
+        ent->vrs_lst[i]->ed25519_reflects_consensus = 1;
+      } else if (vrs_lst2[i] && ! vrs_lst2[i]->has_ed25519_listing) {
+        ent->vrs_lst[i] = vrs_lst2[i];
+      }
+    }
+
+    digestmap_set(rsa_digests, (char*)ent->d, ent->vrs_lst);
+    smartlist_add(dc->all_rsa_sha1_lst, ent->d);
+  }
+
+  DIGESTMAP_FOREACH(dc->by_rsa_sha1, k, vote_routerstatus_t **, vrs_lst) {
+    if (digestmap_get(rsa_digests, k) != NULL)
+      continue;
+
+    int n = 0, i;
+    for (i = 0; i < dc->n_votes; ++i) {
+      if (vrs_lst[i] != NULL)
+        ++n;
+    }
+
+    if (n <= total_authorities / 2)
+      continue;
+
+    digestmap_set(rsa_digests, k, vrs_lst);
+    smartlist_add(dc->all_rsa_sha1_lst, (char *)k);
+  } DIGESTMAP_FOREACH_END;
+
+  dc->by_collated_rsa_sha1 = rsa_digests;
+}
+
+int
+dircollator_n_routers(dircollator_t *dc)
+{
+  return smartlist_len(dc->all_rsa_sha1_lst);
+}
+
+vote_routerstatus_t **
+dircollator_get_votes_for_router(dircollator_t *dc, int idx)
+{
+  tor_assert(idx < smartlist_len(dc->all_rsa_sha1_lst));
+  return digestmap_get(dc->by_collated_rsa_sha1,
+                       smartlist_get(dc->all_rsa_sha1_lst, idx));
+}
+
diff --git a/src/or/dircollate.h b/src/or/dircollate.h
new file mode 100644
index 0000000000..9eba37a010
--- /dev/null
+++ b/src/or/dircollate.h
@@ -0,0 +1,49 @@
+/* Copyright (c) 2001 Matej Pfajfar.
+ * Copyright (c) 2001-2004, Roger Dingledine.
+ * Copyright (c) 2004-2006, Roger Dingledine, Nick Mathewson.
+ * Copyright (c) 2007-2014, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+/**
+ * \file dirvote.h
+ * \brief Header file for dirvote.c.
+ **/
+
+#ifndef TOR_DIRCOLLATE_H
+#define TOR_DIRCOLLATE_H
+
+#include "testsupport.h"
+#include "or.h"
+
+typedef struct dircollator_s dircollator_t;
+
+dircollator_t *dircollator_new(int n_votes, int n_authorities);
+void dircollator_free(dircollator_t *obj);
+void dircollator_add_vote(dircollator_t *dc, networkstatus_t *v);
+
+void dircollator_collate(dircollator_t *dc, int consensus_method);
+
+int dircollator_n_routers(dircollator_t *dc);
+vote_routerstatus_t **dircollator_get_votes_for_router(dircollator_t *dc,
+                                                       int idx);
+
+#ifdef DIRCOLLATE_PRIVATE
+struct ddmap_entry_s;
+typedef HT_HEAD(double_digest_map, ddmap_entry_s) double_digest_map_t;
+struct dircollator_s {
+  /**DOCDOC */
+  int is_collated;
+  int n_votes;
+  int n_authorities;
+
+  int next_vote_num;
+  digestmap_t *by_rsa_sha1;
+  struct double_digest_map by_both_ids;
+
+  digestmap_t *by_collated_rsa_sha1;
+
+  smartlist_t *all_rsa_sha1_lst;
+};
+#endif
+
+#endif
diff --git a/src/or/dirserv.c b/src/or/dirserv.c
index a024be8342..bee67cf749 100644
--- a/src/or/dirserv.c
+++ b/src/or/dirserv.c
@@ -18,6 +18,7 @@
 #include "dirserv.h"
 #include "dirvote.h"
 #include "hibernate.h"
+#include "keypin.h"
 #include "microdesc.h"
 #include "networkstatus.h"
 #include "nodelist.h"
@@ -27,6 +28,7 @@
 #include "routerlist.h"
 #include "routerparse.h"
 #include "routerset.h"
+#include "torcert.h"
 
 /**
  * \file dirserv.c
@@ -225,6 +227,16 @@ dirserv_load_fingerprint_file(void)
   return 0;
 }
 
+/* If this is set, then we don't allow routers that have advertised an Ed25519
+ * identity to stop doing so.  This is going to be essential for good identity
+ * security: otherwise anybody who can attack RSA-1024 but not Ed25519 could
+ * just sign fake descriptors missing the Ed25519 key.  But we won't actually
+ * be able to prevent that kind of thing until we're confident that there
+ * isn't actually a legit reason to downgrade to 0.2.5.  So for now, we have
+ * to leave this #undef.
+ */
+#undef DISABLE_DISABLING_ED25519
+
 /** Check whether <b>router</b> has a nickname/identity key combination that
  * we recognize from the fingerprint list, or an IP we automatically act on
  * according to our configuration.  Return the appropriate router status.
@@ -243,6 +255,36 @@ dirserv_router_get_status(const routerinfo_t *router, const char **msg)
     return FP_REJECT;
   }
 
+  if (router->signing_key_cert) {
+    /* This has an ed25519 identity key. */
+    if (KEYPIN_MISMATCH ==
+        keypin_check((const uint8_t*)router->cache_info.identity_digest,
+                     router->signing_key_cert->signing_key.pubkey)) {
+      if (msg) {
+        *msg = "Ed25519 identity key or RSA identity key has changed.";
+      }
+      log_warn(LD_DIR, "Router %s uploaded a descriptor with a Ed25519 key "
+               "but the <rsa,ed25519> keys don't match what they were before.",
+               router_describe(router));
+      return FP_REJECT;
+    }
+  } else {
+    /* No ed25519 key */
+    if (KEYPIN_MISMATCH == keypin_check_lone_rsa(
+                        (const uint8_t*)router->cache_info.identity_digest)) {
+      log_warn(LD_DIR, "Router %s uploaded a descriptor with no Ed25519 key, "
+               "when we previously knew an Ed25519 for it. Ignoring for now, "
+               "since Tor 0.2.6 is under development.",
+               router_describe(router));
+#ifdef DISABLE_DISABLING_ED25519
+      if (msg) {
+        *msg = "Ed25519 identity key has disappeared.";
+      }
+      return FP_REJECT;
+#endif
+    }
+  }
+
   return dirserv_get_status_impl(d, router->nickname,
                                  router->addr, router->or_port,
                                  router->platform, msg, 1);
@@ -578,6 +620,28 @@ dirserv_add_descriptor(routerinfo_t *ri, const char **msg, const char *source)
     return ROUTER_IS_ALREADY_KNOWN;
   }
 
+  /* Do keypinning again ... this time, to add the pin if appropriate */
+  int keypin_status;
+  if (ri->signing_key_cert) {
+    keypin_status = keypin_check_and_add(
+      (const uint8_t*)ri->cache_info.identity_digest,
+      ri->signing_key_cert->signing_key.pubkey);
+  } else {
+    keypin_status = keypin_check_lone_rsa(
+      (const uint8_t*)ri->cache_info.identity_digest);
+#ifndef DISABLE_DISABLING_ED25519
+    if (keypin_status == KEYPIN_MISMATCH)
+      keypin_status = KEYPIN_NOT_FOUND;
+#endif
+  }
+  if (keypin_status == KEYPIN_MISMATCH) {
+    log_info(LD_DIRSERV, "Dropping descriptor from %s (source: %s) because "
+             "its key did not match an older RSA/Ed25519 keypair",
+             router_describe(ri), source);
+    *msg = "Looks like your keypair does not match its older value.";
+    return ROUTER_AUTHDIR_REJECTS;
+  }
+
   /* Make a copy of desc, since router_add_to_routerlist might free
    * ri and its associated signed_descriptor_t. */
   desc = tor_strndup(ri->cache_info.signed_descriptor_body, desclen);
@@ -1929,6 +1993,16 @@ routerstatus_format_entry(const routerstatus_t *rs, const char *version,
       smartlist_add_asprintf(chunks, "p %s\n", summary);
       tor_free(summary);
     }
+
+    if (format == NS_V3_VOTE && vrs) {
+      if (tor_mem_is_zero((char*)vrs->ed25519_id, ED25519_PUBKEY_LEN)) {
+        smartlist_add(chunks, tor_strdup("id ed25519 none\n"));
+      } else {
+        char ed_b64[BASE64_DIGEST256_LEN+1];
+        digest256_to_base64(ed_b64, (const char*)vrs->ed25519_id);
+        smartlist_add_asprintf(chunks, "id ed25519 %s\n", ed_b64);
+      }
+    }
   }
 
  done:
@@ -2751,6 +2825,11 @@ dirserv_generate_networkstatus_vote_obj(crypto_pk_t *private_key,
                                        listbadexits,
                                        vote_on_hsdirs);
 
+      if (ri->signing_key_cert) {
+        memcpy(vrs->ed25519_id, ri->signing_key_cert->signing_key.pubkey,
+               ED25519_PUBKEY_LEN);
+      }
+
       if (digestmap_get(omit_as_sybil, ri->cache_info.identity_digest))
         clear_status_flags_on_sybil(rs);
 
diff --git a/src/or/dirvote.c b/src/or/dirvote.c
index 3009026ee7..e037794fc7 100644
--- a/src/or/dirvote.c
+++ b/src/or/dirvote.c
@@ -6,6 +6,7 @@
 #define DIRVOTE_PRIVATE
 #include "or.h"
 #include "config.h"
+#include "dircollate.h"
 #include "directory.h"
 #include "dirserv.h"
 #include "dirvote.h"
@@ -17,6 +18,7 @@
 #include "routerlist.h"
 #include "routerparse.h"
 #include "entrynodes.h" /* needed for guardfraction methods */
+#include "torcert.h"
 
 /**
  * \file dirvote.c
@@ -1138,6 +1140,7 @@ networkstatus_compute_consensus(smartlist_t *votes,
   char *params = NULL;
   char *packages = NULL;
   int added_weights = 0;
+  dircollator_t *collator = NULL;
   tor_assert(flavor == FLAV_NS || flavor == FLAV_MICRODESC);
   tor_assert(total_authorities >= smartlist_len(votes));
 
@@ -1493,12 +1496,24 @@ networkstatus_compute_consensus(smartlist_t *votes,
        }
     );
 
+    /* Populate the collator */
+    collator = dircollator_new(smartlist_len(votes), total_authorities);
+    SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
+      dircollator_add_vote(collator, v);
+    } SMARTLIST_FOREACH_END(v);
+
+    dircollator_collate(collator, consensus_method);
+
     /* Now go through all the votes */
     flag_counts = tor_calloc(smartlist_len(flags), sizeof(int));
-    while (1) {
+    const int num_routers = dircollator_n_routers(collator);
+    for (i = 0; i < num_routers; ++i) {
+      vote_routerstatus_t **vrs_lst =
+        dircollator_get_votes_for_router(collator, i);
+
       vote_routerstatus_t *rs;
       routerstatus_t rs_out;
-      const char *lowest_id = NULL;
+      const char *current_rsa_id = NULL;
       const char *chosen_version;
       const char *chosen_name = NULL;
       int exitsummary_disagreement = 0;
@@ -1506,23 +1521,9 @@ networkstatus_compute_consensus(smartlist_t *votes,
       int is_guard = 0, is_exit = 0, is_bad_exit = 0;
       int naming_conflict = 0;
       int n_listing = 0;
-      int i;
       char microdesc_digest[DIGEST256_LEN];
       tor_addr_port_t alt_orport = {TOR_ADDR_NULL, 0};
 
-      /* Of the next-to-be-considered digest in each voter, which is first? */
-      SMARTLIST_FOREACH(votes, networkstatus_t *, v, {
-        if (index[v_sl_idx] < size[v_sl_idx]) {
-          rs = smartlist_get(v->routerstatus_list, index[v_sl_idx]);
-          if (!lowest_id ||
-              fast_memcmp(rs->status.identity_digest,
-                          lowest_id, DIGEST_LEN) < 0)
-            lowest_id = rs->status.identity_digest;
-        }
-      });
-      if (!lowest_id) /* we're out of routers. */
-        break;
-
       memset(flag_counts, 0, sizeof(int)*smartlist_len(flags));
       smartlist_clear(matching_descs);
       smartlist_clear(chosen_flags);
@@ -1532,29 +1533,25 @@ networkstatus_compute_consensus(smartlist_t *votes,
       num_guardfraction_inputs = 0;
 
       /* Okay, go through all the entries for this digest. */
-      SMARTLIST_FOREACH_BEGIN(votes, networkstatus_t *, v) {
-        if (index[v_sl_idx] >= size[v_sl_idx])
-          continue; /* out of entries. */
-        rs = smartlist_get(v->routerstatus_list, index[v_sl_idx]);
-        if (fast_memcmp(rs->status.identity_digest, lowest_id, DIGEST_LEN))
-          continue; /* doesn't include this router. */
-        /* At this point, we know that we're looking at a routerstatus with
-         * identity "lowest".
-         */
-        ++index[v_sl_idx];
+      for (int voter_idx = 0; voter_idx < smartlist_len(votes); ++voter_idx) {
+        if (vrs_lst[voter_idx] == NULL)
+          continue; /* This voter had nothig to say about this entry. */
+        rs = vrs_lst[voter_idx];
         ++n_listing;
 
+        current_rsa_id = rs->status.identity_digest;
+
         smartlist_add(matching_descs, rs);
         if (rs->version && rs->version[0])
           smartlist_add(versions, rs->version);
 
         /* Tally up all the flags. */
-        for (i = 0; i < n_voter_flags[v_sl_idx]; ++i) {
-          if (rs->flags & (U64_LITERAL(1) << i))
-            ++flag_counts[flag_map[v_sl_idx][i]];
+        for (int flag = 0; flag < n_voter_flags[voter_idx]; ++flag) {
+          if (rs->flags & (U64_LITERAL(1) << flag))
+            ++flag_counts[flag_map[voter_idx][flag]];
         }
-        if (named_flag[v_sl_idx] >= 0 &&
-            (rs->flags & (U64_LITERAL(1) << named_flag[v_sl_idx]))) {
+        if (named_flag[voter_idx] >= 0 &&
+            (rs->flags & (U64_LITERAL(1) << named_flag[voter_idx]))) {
           if (chosen_name && strcmp(chosen_name, rs->status.nickname)) {
             log_notice(LD_DIR, "Conflict on naming for router: %s vs %s",
                        chosen_name, rs->status.nickname);
@@ -1575,7 +1572,7 @@ networkstatus_compute_consensus(smartlist_t *votes,
 
         if (rs->status.has_bandwidth)
           bandwidths_kb[num_bandwidths++] = rs->status.bandwidth_kb;
-      } SMARTLIST_FOREACH_END(v);
+      }
 
       /* We don't include this router at all unless more than half of
        * the authorities we believe in list it. */
@@ -1589,8 +1586,9 @@ networkstatus_compute_consensus(smartlist_t *votes,
                                           microdesc_digest, &alt_orport);
       /* Copy bits of that into rs_out. */
       memset(&rs_out, 0, sizeof(rs_out));
-      tor_assert(fast_memeq(lowest_id, rs->status.identity_digest,DIGEST_LEN));
-      memcpy(rs_out.identity_digest, lowest_id, DIGEST_LEN);
+      tor_assert(fast_memeq(current_rsa_id,
+                            rs->status.identity_digest,DIGEST_LEN));
+      memcpy(rs_out.identity_digest, current_rsa_id, DIGEST_LEN);
       memcpy(rs_out.descriptor_digest, rs->status.descriptor_digest,
              DIGEST_LEN);
       rs_out.addr = rs->status.addr;
@@ -1614,7 +1612,7 @@ networkstatus_compute_consensus(smartlist_t *votes,
         const char *d = strmap_get_lc(name_to_id_map, rs_out.nickname);
         if (!d) {
           is_named = is_unnamed = 0;
-        } else if (fast_memeq(d, lowest_id, DIGEST_LEN)) {
+        } else if (fast_memeq(d, current_rsa_id, DIGEST_LEN)) {
           is_named = 1; is_unnamed = 0;
         } else {
           is_named = 0; is_unnamed = 1;
@@ -1980,6 +1978,7 @@ networkstatus_compute_consensus(smartlist_t *votes,
 
  done:
 
+  dircollator_free(collator);
   tor_free(client_versions);
   tor_free(server_versions);
   tor_free(packages);
@@ -3487,9 +3486,18 @@ dirvote_create_microdescriptor(const routerinfo_t *ri, int consensus_method)
   }
 
   if (consensus_method >= MIN_METHOD_FOR_ID_HASH_IN_MD) {
-    char idbuf[BASE64_DIGEST_LEN+1];
-    digest_to_base64(idbuf, ri->cache_info.identity_digest);
-    smartlist_add_asprintf(chunks, "id rsa1024 %s\n", idbuf);
+    char idbuf[ED25519_BASE64_LEN+1];
+    const char *keytype;
+    if (consensus_method >= MIN_METHOD_FOR_ED25519_ID_IN_MD &&
+        ri->signing_key_cert &&
+        ri->signing_key_cert->signing_key_included) {
+      keytype = "ed25519";
+      ed25519_public_to_base64(idbuf, &ri->signing_key_cert->signing_key);
+    } else {
+      keytype = "rsa1024";
+      digest_to_base64(idbuf, ri->cache_info.identity_digest);
+    }
+    smartlist_add_asprintf(chunks, "id %s %s\n", keytype, idbuf);
   }
 
   output = smartlist_join_strings(chunks, "", 0, NULL);
@@ -3562,7 +3570,8 @@ static const struct consensus_method_range_t {
   {MIN_METHOD_FOR_A_LINES, MIN_METHOD_FOR_P6_LINES - 1},
   {MIN_METHOD_FOR_P6_LINES, MIN_METHOD_FOR_NTOR_KEY - 1},
   {MIN_METHOD_FOR_NTOR_KEY, MIN_METHOD_FOR_ID_HASH_IN_MD - 1},
-  {MIN_METHOD_FOR_ID_HASH_IN_MD,  MAX_SUPPORTED_CONSENSUS_METHOD},
+  {MIN_METHOD_FOR_ID_HASH_IN_MD, MIN_METHOD_FOR_ED25519_ID_IN_MD - 1},
+  {MIN_METHOD_FOR_ED25519_ID_IN_MD, MAX_SUPPORTED_CONSENSUS_METHOD},
   {-1, -1}
 };
 
diff --git a/src/or/dirvote.h b/src/or/dirvote.h
index 542563b708..0fb2b2599b 100644
--- a/src/or/dirvote.h
+++ b/src/or/dirvote.h
@@ -55,7 +55,7 @@
 #define MIN_SUPPORTED_CONSENSUS_METHOD 13
 
 /** The highest consensus method that we currently support. */
-#define MAX_SUPPORTED_CONSENSUS_METHOD 20
+#define MAX_SUPPORTED_CONSENSUS_METHOD 21
 
 /** Lowest consensus method where microdesc consensuses omit any entry
  * with no microdesc. */
@@ -86,6 +86,13 @@
  * GuardFraction information in microdescriptors. */
 #define MIN_METHOD_FOR_GUARDFRACTION 20
 
+/** Lowest consensus method where authorities may include an "id" line for
+ * ed25519 identities in microdescriptors. */
+#define MIN_METHOD_FOR_ED25519_ID_IN_MD 21
+/** Lowest consensus method where authorities vote on ed25519 ids and ensure
+ * ed25519 id consistency. */
+#define MIN_METHOD_FOR_ED25519_ID_VOTING MIN_METHOD_FOR_ED25519_ID_IN_MD
+
 /** Default bandwidth to clip unmeasured bandwidths to using method >=
  * MIN_METHOD_TO_CLIP_UNMEASURED_BW.  (This is not a consensus method; do not
  * get confused with the above macros.) */
diff --git a/src/or/include.am b/src/or/include.am
index 0ce3cdc5c3..6bbf78871c 100644
--- a/src/or/include.am
+++ b/src/or/include.am
@@ -43,6 +43,7 @@ LIBTOR_A_SOURCES = \
 	src/or/connection_or.c				\
 	src/or/control.c				\
 	src/or/cpuworker.c				\
+	src/or/dircollate.c				\
 	src/or/directory.c				\
 	src/or/dirserv.c				\
 	src/or/dirvote.c				\
@@ -53,6 +54,7 @@ LIBTOR_A_SOURCES = \
 	src/or/entrynodes.c				\
 	src/or/ext_orport.c				\
 	src/or/hibernate.c				\
+	src/or/keypin.c					\
 	src/or/main.c					\
 	src/or/microdesc.c				\
 	src/or/networkstatus.c				\
@@ -71,12 +73,14 @@ LIBTOR_A_SOURCES = \
 	src/or/rephist.c				\
 	src/or/replaycache.c				\
 	src/or/router.c					\
+	src/or/routerkeys.c				\
 	src/or/routerlist.c				\
 	src/or/routerparse.c				\
 	src/or/routerset.c				\
 	src/or/scheduler.c				\
 	src/or/statefile.c				\
 	src/or/status.c					\
+	src/or/torcert.c				\
 	src/or/onion_ntor.c				\
 	$(evdns_source)					\
 	$(tor_platform_source)
@@ -84,11 +88,6 @@ LIBTOR_A_SOURCES = \
 src_or_libtor_a_SOURCES = $(LIBTOR_A_SOURCES)
 src_or_libtor_testing_a_SOURCES = $(LIBTOR_A_SOURCES)
 
-#libtor_a_LIBADD = $(top_builddir)/common/libor.a \
-#    $(top_builddir)/common/libor-crypto.a \
-#    $(top_builddir)/common/libor-event.a
-
-
 src_or_tor_SOURCES = src/or/tor_main.c
 AM_CPPFLAGS += -I$(srcdir)/src/or -Isrc/or
 
@@ -109,7 +108,7 @@ src_or_libtor_testing_a_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS)
 src_or_tor_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ @TOR_LDFLAGS_libevent@
 src_or_tor_LDADD = src/or/libtor.a src/common/libor.a \
 	src/common/libor-crypto.a $(LIBDONNA) \
-	src/common/libor-event.a \
+	src/common/libor-event.a src/trunnel/libor-trunnel.a \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ @TOR_OPENSSL_LIBS@ \
 	@TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ @TOR_SYSTEMD_LIBS@
 
@@ -120,7 +119,7 @@ src_or_tor_cov_CFLAGS = $(AM_CFLAGS) $(TEST_CFLAGS)
 src_or_tor_cov_LDFLAGS = @TOR_LDFLAGS_zlib@ @TOR_LDFLAGS_openssl@ @TOR_LDFLAGS_libevent@
 src_or_tor_cov_LDADD = src/or/libtor-testing.a src/common/libor-testing.a \
 	src/common/libor-crypto-testing.a $(LIBDONNA) \
-	src/common/libor-event-testing.a \
+	src/common/libor-event-testing.a src/trunnel/libor-trunnel-testing.a \
 	@TOR_ZLIB_LIBS@ @TOR_LIB_MATH@ @TOR_LIBEVENT_LIBS@ @TOR_OPENSSL_LIBS@ \
 	@TOR_LIB_WS32@ @TOR_LIB_GDI@ @CURVE25519_LIBS@ @TOR_SYSTEMD_LIBS@
 TESTING_TOR_BINARY = $(top_builddir)/src/or/tor-cov
@@ -148,6 +147,7 @@ ORHEADERS = \
 	src/or/connection_or.h				\
 	src/or/control.h				\
 	src/or/cpuworker.h				\
+	src/or/dircollate.h				\
 	src/or/directory.h				\
 	src/or/dirserv.h				\
 	src/or/dirvote.h				\
@@ -159,6 +159,7 @@ ORHEADERS = \
 	src/or/geoip.h					\
 	src/or/entrynodes.h				\
 	src/or/hibernate.h				\
+	src/or/keypin.h					\
 	src/or/main.h					\
 	src/or/microdesc.h				\
 	src/or/networkstatus.h				\
@@ -180,12 +181,15 @@ ORHEADERS = \
 	src/or/rephist.h				\
 	src/or/replaycache.h				\
 	src/or/router.h					\
+	src/or/routerkeys.h				\
 	src/or/routerlist.h				\
+	src/or/routerkeys.h				\
 	src/or/routerset.h				\
 	src/or/routerparse.h				\
 	src/or/scheduler.h				\
 	src/or/statefile.h				\
-	src/or/status.h
+	src/or/status.h					\
+	src/or/torcert.h
 
 noinst_HEADERS+= $(ORHEADERS) micro-revision.i
 
diff --git a/src/or/keypin.c b/src/or/keypin.c
new file mode 100644
index 0000000000..7b0c0c7dcf
--- /dev/null
+++ b/src/or/keypin.c
@@ -0,0 +1,419 @@
+/* Copyright (c) 2014, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#define KEYPIN_PRIVATE
+
+#include "orconfig.h"
+#include "compat.h"
+#include "crypto.h"
+#include "di_ops.h"
+#include "ht.h"
+#include "keypin.h"
+#include "siphash.h"
+#include "torint.h"
+#include "torlog.h"
+#include "util.h"
+
+#ifdef HAVE_UNISTD_H
+#include <unistd.h>
+#endif
+#ifdef HAVE_FCNTL_H
+#include <fcntl.h>
+#endif
+
+#ifdef _WIN32
+#include <io.h>
+#endif
+
+/**
+ * @file keypin.c
+ * @brief Key-pinning for RSA and Ed25519 identity keys at directory
+ *  authorities.
+ *
+ * This module implements a key-pinning mechanism to ensure that it's safe
+ * to use RSA keys as identitifers even as we migrate to Ed25519 keys.  It
+ * remembers, for every Ed25519 key we've seen, what the associated Ed25519
+ * key is.  This way, if we see a different Ed25519 key with that RSA key,
+ * we'll know that there's a mismatch.
+ *
+ * We persist these entries to disk using a simple format, where each line
+ * has a base64-encoded RSA SHA1 hash, then a base64-endoded Ed25519 key.
+ * Empty lines, misformed lines, and lines beginning with # are
+ * ignored. Lines beginning with @ are reserved for future extensions.
+ */
+
+static int keypin_journal_append_entry(const uint8_t *rsa_id_digest,
+                                       const uint8_t *ed25519_id_key);
+static int keypin_check_and_add_impl(const uint8_t *rsa_id_digest,
+                                     const uint8_t *ed25519_id_key,
+                                     int do_not_add);
+
+static HT_HEAD(rsamap, keypin_ent_st) the_rsa_map = HT_INITIALIZER();
+static HT_HEAD(edmap, keypin_ent_st) the_ed_map = HT_INITIALIZER();
+
+/** Hashtable helper: compare two keypin table entries and return true iff
+ * they have the same RSA key IDs. */
+static INLINE int
+keypin_ents_eq_rsa(const keypin_ent_t *a, const keypin_ent_t *b)
+{
+  return tor_memeq(a->rsa_id, b->rsa_id, sizeof(a->rsa_id));
+}
+
+/** Hashtable helper: hash a keypin table entries based on its RSA key ID */
+static INLINE unsigned
+keypin_ent_hash_rsa(const keypin_ent_t *a)
+{
+return (unsigned) siphash24g(a->rsa_id, sizeof(a->rsa_id));
+}
+
+/** Hashtable helper: compare two keypin table entries and return true iff
+ * they have the same ed25519 keys */
+static INLINE int
+keypin_ents_eq_ed(const keypin_ent_t *a, const keypin_ent_t *b)
+{
+  return tor_memeq(a->ed25519_key, b->ed25519_key, sizeof(a->ed25519_key));
+}
+
+/** Hashtable helper: hash a keypin table entries based on its ed25519 key */
+static INLINE unsigned
+keypin_ent_hash_ed(const keypin_ent_t *a)
+{
+return (unsigned) siphash24g(a->ed25519_key, sizeof(a->ed25519_key));
+}
+
+HT_PROTOTYPE(rsamap, keypin_ent_st, rsamap_node, keypin_ent_hash_rsa,
+               keypin_ents_eq_rsa);
+HT_GENERATE2(rsamap, keypin_ent_st, rsamap_node, keypin_ent_hash_rsa,
+               keypin_ents_eq_rsa, 0.6, tor_reallocarray, tor_free_);
+
+HT_PROTOTYPE(edmap, keypin_ent_st, edmap_node, keypin_ent_hash_ed,
+               keypin_ents_eq_ed);
+HT_GENERATE2(edmap, keypin_ent_st, edmap_node, keypin_ent_hash_ed,
+               keypin_ents_eq_ed, 0.6, tor_reallocarray, tor_free_);
+
+/**
+ * Check whether we already have an entry in the key pinning table for a
+ * router with RSA ID digest <b>rsa_id_digest</b> or for ed25519 key
+ * <b>ed25519_id_key</b>.  If we have an entry that matches both keys,
+ * return KEYPIN_FOUND. If we find an entry that matches one key but
+ * not the other, return KEYPIN_MISMATCH.  If we have no entry for either
+ * key, add such an entry to the table and return KEYPIN_ADDED.
+ */
+int
+keypin_check_and_add(const uint8_t *rsa_id_digest,
+                     const uint8_t *ed25519_id_key)
+{
+  return keypin_check_and_add_impl(rsa_id_digest, ed25519_id_key, 0);
+}
+
+/**
+ * As keypin_check_and_add, but do not add.  Return KEYPIN_NOT_FOUND if
+ * we would add.
+ */
+int
+keypin_check(const uint8_t *rsa_id_digest,
+             const uint8_t *ed25519_id_key)
+{
+  return keypin_check_and_add_impl(rsa_id_digest, ed25519_id_key, 1);
+}
+
+/**
+ * Helper: implements keypin_check and keypin_check_and_add.
+ */
+static int
+keypin_check_and_add_impl(const uint8_t *rsa_id_digest,
+                          const uint8_t *ed25519_id_key,
+                          int do_not_add)
+{
+  keypin_ent_t search, *ent;
+  memset(&search, 0, sizeof(search));
+  memcpy(search.rsa_id, rsa_id_digest, sizeof(search.rsa_id));
+  memcpy(search.ed25519_key, ed25519_id_key, sizeof(search.ed25519_key));
+
+  /* Search by RSA key digest first */
+  ent = HT_FIND(rsamap, &the_rsa_map, &search);
+  if (ent) {
+    tor_assert(fast_memeq(ent->rsa_id, rsa_id_digest, sizeof(ent->rsa_id)));
+    if (tor_memeq(ent->ed25519_key, ed25519_id_key,sizeof(ent->ed25519_key))) {
+      return KEYPIN_FOUND; /* Match on both keys. Great. */
+    } else {
+      return KEYPIN_MISMATCH; /* Found RSA with different Ed key */
+    }
+  }
+
+  /* See if we know a different RSA key for this ed key */
+  ent = HT_FIND(edmap, &the_ed_map, &search);
+  if (ent) {
+    /* If we got here, then the ed key matches and the RSA doesn't */
+    tor_assert(fast_memeq(ent->ed25519_key, ed25519_id_key,
+                          sizeof(ent->ed25519_key)));
+    tor_assert(fast_memneq(ent->rsa_id, rsa_id_digest, sizeof(ent->rsa_id)));
+    return KEYPIN_MISMATCH;
+  }
+
+  /* Okay, this one is new to us. */
+  if (do_not_add)
+    return KEYPIN_NOT_FOUND;
+
+  ent = tor_memdup(&search, sizeof(search));
+  keypin_add_entry_to_map(ent);
+  keypin_journal_append_entry(rsa_id_digest, ed25519_id_key);
+  return KEYPIN_ADDED;
+}
+
+/**
+ * Helper: add <b>ent</b> to the hash tables.
+ */
+MOCK_IMPL(STATIC void,
+keypin_add_entry_to_map, (keypin_ent_t *ent))
+{
+  HT_INSERT(rsamap, &the_rsa_map, ent);
+  HT_INSERT(edmap, &the_ed_map, ent);
+}
+
+/**
+ * Check whether we already have an entry in the key pinning table for a
+ * router with RSA ID digest <b>rsa_id_digest</b>.  If we have no such entry,
+ * return KEYPIN_NOT_FOUND.  If we find an entry that matches the RSA key but
+ * which has an ed25519 key, return KEYPIN_MISMATCH.
+ */
+int
+keypin_check_lone_rsa(const uint8_t *rsa_id_digest)
+{
+  keypin_ent_t search, *ent;
+  memset(&search, 0, sizeof(search));
+  memcpy(search.rsa_id, rsa_id_digest, sizeof(search.rsa_id));
+
+  /* Search by RSA key digest first */
+  ent = HT_FIND(rsamap, &the_rsa_map, &search);
+  if (ent) {
+    return KEYPIN_MISMATCH;
+  } else {
+    return KEYPIN_NOT_FOUND;
+  }
+}
+
+/** Open fd to the keypinning journal file. */
+static int keypin_journal_fd = -1;
+
+/** Open the key-pinning journal to append to <b>fname</b>.  Return 0 on
+ * success, -1 on failure. */
+int
+keypin_open_journal(const char *fname)
+{
+  /* O_SYNC ??*/
+  int fd = tor_open_cloexec(fname, O_WRONLY|O_CREAT, 0600);
+  if (fd < 0)
+    goto err;
+
+  if (tor_fd_seekend(fd) < 0)
+    goto err;
+
+  /* Add a newline in case the last line was only partially written */
+  if (write(fd, "\n", 1) < 1)
+    goto err;
+
+  /* Add something about when we opened this file. */
+  char buf[80];
+  char tbuf[ISO_TIME_LEN+1];
+  format_iso_time(tbuf, approx_time());
+  tor_snprintf(buf, sizeof(buf), "@opened-at %s\n", tbuf);
+  if (write_all(fd, buf, strlen(buf), 0) < 0)
+    goto err;
+
+  keypin_journal_fd = fd;
+  return 0;
+ err:
+  if (fd >= 0)
+    close(fd);
+  return -1;
+}
+
+/** Close the keypinning journal file. */
+int
+keypin_close_journal(void)
+{
+  if (keypin_journal_fd >= 0)
+    close(keypin_journal_fd);
+  keypin_journal_fd = -1;
+  return 0;
+}
+
+/** Length of a keypinning journal line, including terminating newline. */
+#define JOURNAL_LINE_LEN (BASE64_DIGEST_LEN + BASE64_DIGEST256_LEN + 2)
+
+/** Add an entry to the keypinning journal to map <b>rsa_id_digest</b> and
+ * <b>ed25519_id_key</b>. */
+static int
+keypin_journal_append_entry(const uint8_t *rsa_id_digest,
+                            const uint8_t *ed25519_id_key)
+{
+  if (keypin_journal_fd == -1)
+    return -1;
+  char line[JOURNAL_LINE_LEN];
+  digest_to_base64(line, (const char*)rsa_id_digest);
+  line[BASE64_DIGEST_LEN] = ' ';
+  digest256_to_base64(line + BASE64_DIGEST_LEN + 1,
+                      (const char*)ed25519_id_key);
+  line[BASE64_DIGEST_LEN+1+BASE64_DIGEST256_LEN] = '\n';
+
+  if (write_all(keypin_journal_fd, line, JOURNAL_LINE_LEN, 0)<0) {
+    log_warn(LD_DIRSERV, "Error while adding a line to the key-pinning "
+             "journal: %s", strerror(errno));
+    keypin_close_journal();
+    return -1;
+  }
+
+  return 0;
+}
+
+/** Load a journal from the <b>size</b>-byte region at <b>data</b>.  Return 0
+ * on success, -1 on failure. */
+STATIC int
+keypin_load_journal_impl(const char *data, size_t size)
+{
+  const char *start = data, *end = data + size, *next;
+
+  int n_corrupt_lines = 0;
+  int n_entries = 0;
+  int n_duplicates = 0;
+  int n_conflicts = 0;
+
+  for (const char *cp = start; cp < end; cp = next) {
+    const char *eol = memchr(cp, '\n', end-cp);
+    const char *eos = eol ? eol : end;
+    const size_t len = eos - cp;
+
+    next = eol ? eol + 1 : end;
+
+    if (len == 0) {
+      continue;
+    }
+
+    if (*cp == '@') {
+      /* Lines that start with @ are reserved. Ignore for now. */
+      continue;
+    }
+    if (*cp == '#') {
+      /* Lines that start with # are comments. */
+      continue;
+    }
+
+    /* Is it the right length?  (The -1 here is for the newline.) */
+    if (len != JOURNAL_LINE_LEN - 1) {
+      /* Lines with a bad length are corrupt unless they are empty.
+       * Ignore them either way */
+      for (const char *s = cp; s < eos; ++s) {
+        if (! TOR_ISSPACE(*s)) {
+          ++n_corrupt_lines;
+          break;
+        }
+      }
+      continue;
+    }
+
+    keypin_ent_t *ent = keypin_parse_journal_line(cp);
+
+    if (ent == NULL) {
+      ++n_corrupt_lines;
+      continue;
+    }
+
+    const keypin_ent_t *ent2;
+    if ((ent2 = HT_FIND(rsamap, &the_rsa_map, ent))) {
+      if (fast_memeq(ent2->ed25519_key, ent->ed25519_key, DIGEST256_LEN)) {
+        ++n_duplicates;
+      } else {
+        ++n_conflicts;
+      }
+      tor_free(ent);
+      continue;
+    } else if (HT_FIND(edmap, &the_ed_map, ent)) {
+      tor_free(ent);
+      ++n_conflicts;
+      continue;
+    }
+
+    keypin_add_entry_to_map(ent);
+    ++n_entries;
+  }
+
+  int severity = (n_corrupt_lines || n_duplicates) ? LOG_WARN : LOG_INFO;
+  tor_log(severity, LD_DIRSERV,
+          "Loaded %d entries from keypin journal. "
+          "Found %d corrupt lines, %d duplicates, and %d conflicts.",
+          n_entries, n_corrupt_lines, n_duplicates, n_conflicts);
+
+  return 0;
+}
+
+/**
+ * Load a journal from the file called <b>fname</b>. Return 0 on success,
+ * -1 on failure.
+ */
+int
+keypin_load_journal(const char *fname)
+{
+  tor_mmap_t *map = tor_mmap_file(fname);
+  if (!map) {
+    if (errno == ENOENT)
+      return 0;
+    else
+      return -1;
+  }
+  int r = keypin_load_journal_impl(map->data, map->size);
+  tor_munmap_file(map);
+  return r;
+}
+
+/** Parse a single keypinning journal line entry from <b>cp</b>.  The input
+ * does not need to be NUL-terminated, but it <em>does</em> need to have
+ * KEYPIN_JOURNAL_LINE_LEN -1 bytes available to read.  Return a new entry
+ * on success, and NULL on failure.
+ */
+STATIC keypin_ent_t *
+keypin_parse_journal_line(const char *cp)
+{
+  /* XXXX assumes !USE_OPENSSL_BASE64 */
+  keypin_ent_t *ent = tor_malloc_zero(sizeof(keypin_ent_t));
+
+  if (base64_decode((char*)ent->rsa_id, sizeof(ent->rsa_id),
+             cp, BASE64_DIGEST_LEN) != DIGEST_LEN ||
+      cp[BASE64_DIGEST_LEN] != ' ' ||
+      base64_decode((char*)ent->ed25519_key, sizeof(ent->ed25519_key),
+             cp+BASE64_DIGEST_LEN+1, BASE64_DIGEST256_LEN) != DIGEST256_LEN) {
+    tor_free(ent);
+    return NULL;
+  } else {
+    return ent;
+  }
+}
+
+/** Remove all entries from the keypinning table.*/
+void
+keypin_clear(void)
+{
+  int bad_entries = 0;
+  {
+    keypin_ent_t **ent, **next, *this;
+    for (ent = HT_START(rsamap, &the_rsa_map); ent != NULL; ent = next) {
+      this = *ent;
+      next = HT_NEXT_RMV(rsamap, &the_rsa_map, ent);
+
+      keypin_ent_t *other_ent = HT_REMOVE(edmap, &the_ed_map, this);
+      bad_entries += (other_ent != this);
+
+      tor_free(this);
+    }
+  }
+  bad_entries += HT_SIZE(&the_ed_map);
+
+  HT_CLEAR(edmap,&the_ed_map);
+  HT_CLEAR(rsamap,&the_rsa_map);
+
+  if (bad_entries) {
+    log_warn(LD_BUG, "Found %d discrepencies in the the keypin database.",
+             bad_entries);
+  }
+}
+
diff --git a/src/or/keypin.h b/src/or/keypin.h
new file mode 100644
index 0000000000..2a5b3f1786
--- /dev/null
+++ b/src/or/keypin.h
@@ -0,0 +1,46 @@
+/* Copyright (c) 2014, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_KEYPIN_H
+#define TOR_KEYPIN_H
+
+#include "testsupport.h"
+
+int keypin_check_and_add(const uint8_t *rsa_id_digest,
+                         const uint8_t *ed25519_id_key);
+int keypin_check(const uint8_t *rsa_id_digest,
+                 const uint8_t *ed25519_id_key);
+
+int keypin_open_journal(const char *fname);
+int keypin_close_journal(void);
+int keypin_load_journal(const char *fname);
+void keypin_clear(void);
+int keypin_check_lone_rsa(const uint8_t *rsa_id_digest);
+
+#define KEYPIN_FOUND 0
+#define KEYPIN_ADDED 1
+#define KEYPIN_MISMATCH -1
+#define KEYPIN_NOT_FOUND -2
+
+#ifdef KEYPIN_PRIVATE
+
+/**
+ * In-memory representation of a key-pinning table entry.
+ */
+typedef struct keypin_ent_st {
+  HT_ENTRY(keypin_ent_st) rsamap_node;
+  HT_ENTRY(keypin_ent_st) edmap_node;
+  /** SHA1 hash of the RSA key */
+  uint8_t rsa_id[DIGEST_LEN];
+  /** Ed2219 key. */
+  uint8_t ed25519_key[DIGEST256_LEN];
+} keypin_ent_t;
+
+STATIC keypin_ent_t * keypin_parse_journal_line(const char *cp);
+STATIC int keypin_load_journal_impl(const char *data, size_t size);
+
+MOCK_DECL(STATIC void, keypin_add_entry_to_map, (keypin_ent_t *ent));
+#endif
+
+#endif
+
diff --git a/src/or/main.c b/src/or/main.c
index 74e6b33397..bbee8e0fb9 100644
--- a/src/or/main.c
+++ b/src/or/main.c
@@ -37,6 +37,7 @@
 #include "entrynodes.h"
 #include "geoip.h"
 #include "hibernate.h"
+#include "keypin.h"
 #include "main.h"
 #include "microdesc.h"
 #include "networkstatus.h"
@@ -51,6 +52,7 @@
 #include "rendservice.h"
 #include "rephist.h"
 #include "router.h"
+#include "routerkeys.h"
 #include "routerlist.h"
 #include "routerparse.h"
 #include "scheduler.h"
@@ -1223,10 +1225,13 @@ typedef struct {
   time_t check_descriptor;
   /** When do we next launch DNS wildcarding checks? */
   time_t check_for_correct_dns;
+  /** When do we next make sure our Ed25519 keys aren't about to expire? */
+  time_t check_ed_keys;
+
 } time_to_t;
 
 static time_to_t time_to = {
-  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
+  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 };
 
 /** Reset all the time_to's so we'll do all our actions again as if we
@@ -1297,6 +1302,18 @@ run_scheduled_events(time_t now)
       router_upload_dir_desc_to_dirservers(0);
   }
 
+  if (is_server && time_to.check_ed_keys < now) {
+    if (should_make_new_ed_keys(options, now)) {
+      if (load_ed_keys(options, now) < 0 ||
+          generate_ed_link_cert(options, now)) {
+        log_err(LD_OR, "Unable to update Ed25519 keys!  Exiting.");
+        tor_cleanup();
+        exit(0);
+      }
+    }
+    time_to.check_ed_keys = now + 30;
+  }
+
   if (!should_delay_dir_fetches(options, NULL) &&
       time_to.try_getting_descriptors < now) {
     update_all_descriptor_downloads(now);
@@ -2015,6 +2032,23 @@ do_main_loop(void)
   /* initialize the bootstrap status events to know we're starting up */
   control_event_bootstrap(BOOTSTRAP_STATUS_STARTING, 0);
 
+  /* Initialize the keypinning log. */
+  if (authdir_mode_v3(get_options())) {
+    char *fname = get_datadir_fname("key-pinning-entries");
+    int r = 0;
+    if (keypin_load_journal(fname)<0) {
+      log_err(LD_DIR, "Error loading key-pinning journal: %s",strerror(errno));
+      r = -1;
+    }
+    if (keypin_open_journal(fname)<0) {
+      log_err(LD_DIR, "Error opening key-pinning journal: %s",strerror(errno));
+      r = -1;
+    }
+    tor_free(fname);
+    if (r)
+      return r;
+  }
+
   if (trusted_dirs_reload_certs()) {
     log_warn(LD_DIR,
              "Couldn't load all cached v3 certificates. Starting anyway.");
@@ -2695,6 +2729,7 @@ tor_free_all(int postfork)
     config_free_all();
     or_state_free_all();
     router_free_all();
+    routerkeys_free_all();
     policies_free_all();
   }
   if (!postfork) {
@@ -2752,6 +2787,7 @@ tor_cleanup(void)
     or_state_save(now);
     if (authdir_mode_tests_reachability(options))
       rep_hist_record_mtbf_data(now, 0);
+    keypin_close_journal();
   }
 #ifdef USE_DMALLOC
   dmalloc_log_stats();
diff --git a/src/or/microdesc.c b/src/or/microdesc.c
index 0511e870d1..ee48f6a419 100644
--- a/src/or/microdesc.c
+++ b/src/or/microdesc.c
@@ -738,6 +738,7 @@ microdesc_free_(microdesc_t *md, const char *fname, int lineno)
   if (md->onion_pkey)
     crypto_pk_free(md->onion_pkey);
   tor_free(md->onion_curve25519_pkey);
+  tor_free(md->ed25519_identity_pkey);
   if (md->body && md->saved_location != SAVED_IN_CACHE)
     tor_free(md->body);
 
diff --git a/src/or/or.h b/src/or/or.h
index af3496765e..81e1c1c1db 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -96,6 +96,7 @@
 #include "ht.h"
 #include "replaycache.h"
 #include "crypto_curve25519.h"
+#include "crypto_ed25519.h"
 #include "tor_queue.h"
 
 /* These signals are defined to help handle_control_signal work.
@@ -1353,6 +1354,8 @@ typedef struct listener_connection_t {
  * in the v3 handshake.  The subject key must be a 1024-bit RSA key; it
  * must be signed by the identity key */
 #define OR_CERT_TYPE_AUTH_1024 3
+/** DOCDOC */
+#define OR_CERT_TYPE_RSA_ED_CROSSCERT 7
 /**@}*/
 
 /** The one currently supported type of AUTHENTICATE cell.  It contains
@@ -1428,9 +1431,9 @@ typedef struct or_handshake_state_t {
    * @{
    */
   /** The cert for the key that's supposed to sign the AUTHENTICATE cell */
-  tor_cert_t *auth_cert;
+  tor_x509_cert_t *auth_cert;
   /** A self-signed identity certificate */
-  tor_cert_t *id_cert;
+  tor_x509_cert_t *id_cert;
   /**@}*/
 } or_handshake_state_t;
 
@@ -2023,6 +2026,8 @@ typedef int16_t country_t;
 /** Information about another onion router in the network. */
 typedef struct {
   signed_descriptor_t cache_info;
+  /** A SHA256-digest of the extrainfo (if any) */
+  char extra_info_digest256[DIGEST256_LEN];
   char *nickname; /**< Human-readable OR name. */
 
   uint32_t addr; /**< IPv4 address of OR, in host order. */
@@ -2040,6 +2045,11 @@ typedef struct {
   crypto_pk_t *identity_pkey;  /**< Public RSA key for signing. */
   /** Public curve25519 key for onions */
   curve25519_public_key_t *onion_curve25519_pkey;
+  /** Certificate for ed25519 signing key */
+  struct tor_cert_st *signing_key_cert;
+  /** What's the earliest expiration time on all the certs in this
+   * routerinfo? */
+  time_t cert_expiration_time;
 
   char *platform; /**< What software/operating system is this OR using? */
 
@@ -2099,8 +2109,12 @@ typedef struct {
 /** Information needed to keep and cache a signed extra-info document. */
 typedef struct extrainfo_t {
   signed_descriptor_t cache_info;
+  /** SHA256 digest of this document */
+  uint8_t digest256[DIGEST256_LEN];
   /** The router's nickname. */
   char nickname[MAX_NICKNAME_LEN+1];
+  /** Certificate for ed25519 signing key */
+  struct tor_cert_st *signing_key_cert;
   /** True iff we found the right key for this extra-info, verified the
    * signature, and found it to be bad. */
   unsigned int bad_sig : 1;
@@ -2245,6 +2259,8 @@ typedef struct microdesc_t {
   crypto_pk_t *onion_pkey;
   /** As routerinfo_t.onion_curve25519_pkey */
   curve25519_public_key_t *onion_curve25519_pkey;
+  /** Ed25519 identity key, if included. */
+  ed25519_public_key_t *ed25519_identity_pkey;
   /** As routerinfo_t.ipv6_add */
   tor_addr_t ipv6_addr;
   /** As routerinfo_t.ipv6_orport */
@@ -2359,9 +2375,13 @@ typedef struct vote_routerstatus_t {
   char *version; /**< The version that the authority says this router is
                   * running. */
   unsigned int has_measured_bw:1; /**< The vote had a measured bw */
+  unsigned int has_ed25519_listing:1; /** DOCDOC */
+  unsigned int ed25519_reflects_consensus:1; /** DOCDOC */
   uint32_t measured_bw_kb; /**< Measured bandwidth (capacity) of the router */
   /** The hash or hashes that the authority claims this microdesc has. */
   vote_microdesc_hash_t *microdesc;
+  /** Ed25519 identity for this router, or zero if it has none. */
+  uint8_t ed25519_id[ED25519_PUBKEY_LEN];
 } vote_routerstatus_t;
 
 /** A signature of some document by an authority. */
@@ -4261,6 +4281,21 @@ typedef struct {
    * XXXX Eventually, the default will be 0. */
   int ExitRelay;
 
+
+  /** For how long (seconds) do we declare our singning keys to be valid? */
+  int SigningKeyLifetime;
+  /** For how long (seconds) do we declare our link keys to be valid? */
+  int TestingLinkCertLifetime;
+  /** For how long (seconds) do we declare our auth keys to be valid? */
+  int TestingAuthKeyLifetime;
+
+  /** How long before signing keys expire will we try to make a new one? */
+  int TestingSigningKeySlop;
+  /** How long before link keys expire will we try to make a new one? */
+  int TestingLinkKeySlop;
+  /** How long before auth keys expire will we try to make a new one? */
+  int TestingAuthKeySlop;
+
 } or_options_t;
 
 /** Persistent state for an onion router, as saved to disk. */
@@ -5065,6 +5100,8 @@ typedef enum was_router_added_t {
   /* Router descriptor was rejected because it was older than
    * OLD_ROUTER_DESC_MAX_AGE. */
   ROUTER_WAS_TOO_OLD = -7, /* note contrast with 'NOT_NEW' */
+  /* DOCDOC */
+  ROUTER_CERTS_EXPIRED = -8
 } was_router_added_t;
 
 /********************************* routerparse.c ************************/
diff --git a/src/or/router.c b/src/or/router.c
index 24b7c750f6..6532f97d24 100644
--- a/src/or/router.c
+++ b/src/or/router.c
@@ -26,9 +26,11 @@
 #include "relay.h"
 #include "rephist.h"
 #include "router.h"
+#include "routerkeys.h"
 #include "routerlist.h"
 #include "routerparse.h"
 #include "statefile.h"
+#include "torcert.h"
 #include "transports.h"
 #include "routerset.h"
 
@@ -204,6 +206,8 @@ set_server_identity_key(crypto_pk_t *k)
 static void
 assert_identity_keys_ok(void)
 {
+  if (1)
+    return;
   tor_assert(client_identitykey);
   if (public_server_mode(get_options())) {
     /* assert that we have set the client and server keys to be equal */
@@ -863,6 +867,10 @@ init_keys(void)
     set_client_identity_key(prkey);
   }
 
+  /* 1d. Load all ed25519 keys */
+  if (load_ed_keys(options,now) < 0)
+    return -1;
+
   /* 2. Read onion key.  Make it if none is found. */
   keydir = get_datadir_fname2("keys", "secret_onion_key");
   log_info(LD_GENERAL,"Reading/making onion key \"%s\"...",keydir);
@@ -928,6 +936,13 @@ init_keys(void)
     return -1;
   }
 
+  /* 3b. Get an ed25519 link certificate.  Note that we need to do this
+   * after we set up the TLS context */
+  if (generate_ed_link_cert(options, now) < 0) {
+    log_err(LD_GENERAL,"Couldn't make link cert");
+    return -1;
+  }
+
   /* 4. Build our router descriptor. */
   /* Must be called after keys are initialized. */
   mydesc = router_get_my_descriptor();
@@ -1872,6 +1887,8 @@ router_build_fresh_descriptor(routerinfo_t **r, extrainfo_t **e)
     routerinfo_free(ri);
     return -1;
   }
+  ri->signing_key_cert = tor_cert_dup(get_master_signing_key_cert());
+
   get_platform_str(platform, sizeof(platform));
   ri->platform = tor_strdup(platform);
 
@@ -1962,10 +1979,12 @@ router_build_fresh_descriptor(routerinfo_t **r, extrainfo_t **e)
   ei->cache_info.is_extrainfo = 1;
   strlcpy(ei->nickname, get_options()->Nickname, sizeof(ei->nickname));
   ei->cache_info.published_on = ri->cache_info.published_on;
+  ei->signing_key_cert = tor_cert_dup(get_master_signing_key_cert());
   memcpy(ei->cache_info.identity_digest, ri->cache_info.identity_digest,
          DIGEST_LEN);
   if (extrainfo_dump_to_string(&ei->cache_info.signed_descriptor_body,
-                               ei, get_server_identity_key()) < 0) {
+                               ei, get_server_identity_key(),
+                               get_master_signing_keypair()) < 0) {
     log_warn(LD_BUG, "Couldn't generate extra-info descriptor.");
     extrainfo_free(ei);
     ei = NULL;
@@ -1975,6 +1994,10 @@ router_build_fresh_descriptor(routerinfo_t **r, extrainfo_t **e)
     router_get_extrainfo_hash(ei->cache_info.signed_descriptor_body,
                               ei->cache_info.signed_descriptor_len,
                               ei->cache_info.signed_descriptor_digest);
+    crypto_digest256((char*) ei->digest256,
+                     ei->cache_info.signed_descriptor_body,
+                     ei->cache_info.signed_descriptor_len,
+                     DIGEST_SHA256);
   }
 
   /* Now finish the router descriptor. */
@@ -1982,12 +2005,18 @@ router_build_fresh_descriptor(routerinfo_t **r, extrainfo_t **e)
     memcpy(ri->cache_info.extra_info_digest,
            ei->cache_info.signed_descriptor_digest,
            DIGEST_LEN);
+    memcpy(ri->extra_info_digest256,
+           ei->digest256,
+           DIGEST256_LEN);
   } else {
     /* ri was allocated with tor_malloc_zero, so there is no need to
      * zero ri->cache_info.extra_info_digest here. */
   }
-  if (! (ri->cache_info.signed_descriptor_body = router_dump_router_to_string(
-                                           ri, get_server_identity_key()))) {
+  if (! (ri->cache_info.signed_descriptor_body =
+          router_dump_router_to_string(ri, get_server_identity_key(),
+                                       get_onion_key(),
+                                       get_current_curve25519_keypair(),
+                                       get_master_signing_keypair())) ) {
     log_warn(LD_BUG, "Couldn't generate router descriptor.");
     routerinfo_free(ri);
     extrainfo_free(ei);
@@ -2328,22 +2357,28 @@ get_platform_str(char *platform, size_t len)
  */
 char *
 router_dump_router_to_string(routerinfo_t *router,
-                             crypto_pk_t *ident_key)
+                             const crypto_pk_t *ident_key,
+                             const crypto_pk_t *tap_key,
+                             const curve25519_keypair_t *ntor_keypair,
+                             const ed25519_keypair_t *signing_keypair)
 {
   char *address = NULL;
   char *onion_pkey = NULL; /* Onion key, PEM-encoded. */
   char *identity_pkey = NULL; /* Identity key, PEM-encoded. */
-  char digest[DIGEST_LEN];
+  char digest[DIGEST256_LEN];
   char published[ISO_TIME_LEN+1];
   char fingerprint[FINGERPRINT_LEN+1];
-  int has_extra_info_digest;
-  char extra_info_digest[HEX_DIGEST_LEN+1];
+  char *extra_info_line = NULL;
   size_t onion_pkeylen, identity_pkeylen;
   char *family_line = NULL;
   char *extra_or_address = NULL;
   const or_options_t *options = get_options();
   smartlist_t *chunks = NULL;
   char *output = NULL;
+  const int emit_ed_sigs = signing_keypair && router->signing_key_cert;
+  char *ed_cert_line = NULL;
+  char *rsa_tap_cc_line = NULL;
+  char *ntor_cc_line = NULL;
 
   /* Make sure the identity key matches the one in the routerinfo. */
   if (!crypto_pk_eq_keys(ident_key, router->identity_pkey)) {
@@ -2351,6 +2386,16 @@ router_dump_router_to_string(routerinfo_t *router,
              "match router's public key!");
     goto err;
   }
+  if (emit_ed_sigs) {
+    if (!router->signing_key_cert->signing_key_included ||
+        !ed25519_pubkey_eq(&router->signing_key_cert->signed_key,
+                           &signing_keypair->pubkey)) {
+      log_warn(LD_BUG, "Tried to sign a router descriptor with a mismatched "
+               "ed25519 key chain %d",
+               router->signing_key_cert->signing_key_included);
+      goto err;
+    }
+  }
 
   /* record our fingerprint, so we can include it in the descriptor */
   if (crypto_pk_get_fingerprint(router->identity_pkey, fingerprint, 1)<0) {
@@ -2358,6 +2403,22 @@ router_dump_router_to_string(routerinfo_t *router,
     goto err;
   }
 
+  if (emit_ed_sigs) {
+    /* Encode ed25519 signing cert */
+    char ed_cert_base64[256];
+    if (base64_encode(ed_cert_base64, sizeof(ed_cert_base64),
+                      (const char*)router->signing_key_cert->encoded,
+                      router->signing_key_cert->encoded_len,
+                      BASE64_ENCODE_MULTILINE) < 0) {
+      log_err(LD_BUG,"Couldn't base64-encode signing key certificate!");
+      goto err;
+    }
+    tor_asprintf(&ed_cert_line, "identity-ed25519\n"
+                 "-----BEGIN ED25519 CERT-----\n"
+                 "%s"
+                 "-----END ED25519 CERT-----\n", ed_cert_base64);
+  }
+
   /* PEM-encode the onion key */
   if (crypto_pk_write_public_key_to_string(router->onion_pkey,
                                            &onion_pkey,&onion_pkeylen)<0) {
@@ -2372,6 +2433,69 @@ router_dump_router_to_string(routerinfo_t *router,
     goto err;
   }
 
+  /* Cross-certify with RSA key */
+  if (tap_key && router->signing_key_cert &&
+      router->signing_key_cert->signing_key_included) {
+    char buf[256];
+    int tap_cc_len = 0;
+    uint8_t *tap_cc =
+      make_tap_onion_key_crosscert(tap_key,
+                                   &router->signing_key_cert->signing_key,
+                                   router->identity_pkey,
+                                   &tap_cc_len);
+    if (!tap_cc) {
+      log_warn(LD_BUG,"make_tap_onion_key_crosscert failed!");
+      goto err;
+    }
+
+    if (base64_encode(buf, sizeof(buf), (const char*)tap_cc, tap_cc_len,
+                      BASE64_ENCODE_MULTILINE) < 0) {
+      log_warn(LD_BUG,"base64_encode(rsa_crosscert) failed!");
+      tor_free(tap_cc);
+      goto err;
+    }
+    tor_free(tap_cc);
+
+    tor_asprintf(&rsa_tap_cc_line,
+                 "onion-key-crosscert\n"
+                 "-----BEGIN CROSSCERT-----\n"
+                 "%s"
+                 "-----END CROSSCERT-----\n", buf);
+  }
+
+  /* Cross-certify with onion keys */
+  if (ntor_keypair && router->signing_key_cert &&
+      router->signing_key_cert->signing_key_included) {
+    int sign = 0;
+    char buf[256];
+    /* XXXX Base the expiration date on the actual onion key expiration time?*/
+    tor_cert_t *cert =
+      make_ntor_onion_key_crosscert(ntor_keypair,
+                                &router->signing_key_cert->signing_key,
+                                router->cache_info.published_on,
+                                MIN_ONION_KEY_LIFETIME, &sign);
+    if (!cert) {
+      log_warn(LD_BUG,"make_ntor_onion_key_crosscert failed!");
+      goto err;
+    }
+    tor_assert(sign == 0 || sign == 1);
+
+    if (base64_encode(buf, sizeof(buf),
+                      (const char*)cert->encoded, cert->encoded_len,
+                      BASE64_ENCODE_MULTILINE)<0) {
+      log_warn(LD_BUG,"base64_encode(ntor_crosscert) failed!");
+      tor_cert_free(cert);
+      goto err;
+    }
+    tor_cert_free(cert);
+
+    tor_asprintf(&ntor_cc_line,
+                 "ntor-onion-key-crosscert %d\n"
+                 "-----BEGIN ED25519 CERT-----\n"
+                 "%s"
+                 "-----END ED25519 CERT-----\n", sign, buf);
+  }
+
   /* Encode the publication time. */
   format_iso_time(published, router->cache_info.published_on);
 
@@ -2384,12 +2508,19 @@ router_dump_router_to_string(routerinfo_t *router,
     family_line = tor_strdup("");
   }
 
-  has_extra_info_digest =
-    ! tor_digest_is_zero(router->cache_info.extra_info_digest);
-
-  if (has_extra_info_digest) {
+  if (!tor_digest_is_zero(router->cache_info.extra_info_digest)) {
+    char extra_info_digest[HEX_DIGEST_LEN+1];
     base16_encode(extra_info_digest, sizeof(extra_info_digest),
                   router->cache_info.extra_info_digest, DIGEST_LEN);
+    if (!tor_digest256_is_zero(router->extra_info_digest256)) {
+      char d256_64[BASE64_DIGEST256_LEN+1];
+      digest256_to_base64(d256_64, router->extra_info_digest256);
+      tor_asprintf(&extra_info_line, "extra-info-digest %s %s\n",
+                   extra_info_digest, d256_64);
+    } else {
+      tor_asprintf(&extra_info_line, "extra-info-digest %s\n",
+                   extra_info_digest);
+    }
   }
 
   if (router->ipv6_orport &&
@@ -2411,20 +2542,23 @@ router_dump_router_to_string(routerinfo_t *router,
   smartlist_add_asprintf(chunks,
                     "router %s %s %d 0 %d\n"
                     "%s"
+                    "%s"
                     "platform %s\n"
                     "protocols Link 1 2 Circuit 1\n"
                     "published %s\n"
                     "fingerprint %s\n"
                     "uptime %ld\n"
                     "bandwidth %d %d %d\n"
-                    "%s%s%s%s"
+                    "%s%s"
                     "onion-key\n%s"
                     "signing-key\n%s"
+                    "%s%s"
                     "%s%s%s%s",
     router->nickname,
     address,
     router->or_port,
     decide_to_advertise_dirport(options, router->dir_port),
+    ed_cert_line ? ed_cert_line : "",
     extra_or_address ? extra_or_address : "",
     router->platform,
     published,
@@ -2433,12 +2567,12 @@ router_dump_router_to_string(routerinfo_t *router,
     (int) router->bandwidthrate,
     (int) router->bandwidthburst,
     (int) router->bandwidthcapacity,
-    has_extra_info_digest ? "extra-info-digest " : "",
-    has_extra_info_digest ? extra_info_digest : "",
-    has_extra_info_digest ? "\n" : "",
+    extra_info_line ? extra_info_line : "",
     (options->DownloadExtraInfo || options->V3AuthoritativeDir) ?
                          "caches-extra-info\n" : "",
     onion_pkey, identity_pkey,
+    rsa_tap_cc_line ? rsa_tap_cc_line : "",
+    ntor_cc_line ? ntor_cc_line : "",
     family_line,
     we_are_hibernating() ? "hibernating 1\n" : "",
     options->HidServDirectoryV2 ? "hidden-service-dir\n" : "",
@@ -2481,7 +2615,24 @@ router_dump_router_to_string(routerinfo_t *router,
     tor_free(p6);
   }
 
-  /* Sign the descriptor */
+  /* Sign the descriptor with Ed25519 */
+  if (emit_ed_sigs)  {
+    smartlist_add(chunks, tor_strdup("router-sig-ed25519 "));
+    crypto_digest_smartlist_prefix(digest, DIGEST256_LEN,
+                                   ED_DESC_SIGNATURE_PREFIX,
+                                   chunks, "", DIGEST_SHA256);
+    ed25519_signature_t sig;
+    char buf[ED25519_SIG_BASE64_LEN+1];
+    if (ed25519_sign(&sig, (const uint8_t*)digest, DIGEST256_LEN,
+                     signing_keypair) < 0)
+      goto err;
+    if (ed25519_signature_to_base64(buf, &sig) < 0)
+      goto err;
+
+    smartlist_add_asprintf(chunks, "%s\n", buf);
+  }
+
+  /* Sign the descriptor with RSA */
   smartlist_add(chunks, tor_strdup("router-signature\n"));
 
   crypto_digest_smartlist(digest, DIGEST_LEN, chunks, "", DIGEST_SHA1);
@@ -2533,6 +2684,10 @@ router_dump_router_to_string(routerinfo_t *router,
   tor_free(onion_pkey);
   tor_free(identity_pkey);
   tor_free(extra_or_address);
+  tor_free(ed_cert_line);
+  tor_free(rsa_tap_cc_line);
+  tor_free(ntor_cc_line);
+  tor_free(extra_info_line);
 
   return output;
 }
@@ -2676,7 +2831,8 @@ load_stats_file(const char *filename, const char *end_line, time_t now,
  * success, negative on failure. */
 int
 extrainfo_dump_to_string(char **s_out, extrainfo_t *extrainfo,
-                         crypto_pk_t *ident_key)
+                         crypto_pk_t *ident_key,
+                         const ed25519_keypair_t *signing_keypair)
 {
   const or_options_t *options = get_options();
   char identity[HEX_DIGEST_LEN+1];
@@ -2686,18 +2842,45 @@ extrainfo_dump_to_string(char **s_out, extrainfo_t *extrainfo,
   int result;
   static int write_stats_to_extrainfo = 1;
   char sig[DIROBJ_MAX_SIG_LEN+1];
-  char *s, *pre, *contents, *cp, *s_dup = NULL;
+  char *s = NULL, *pre, *contents, *cp, *s_dup = NULL;
   time_t now = time(NULL);
   smartlist_t *chunks = smartlist_new();
   extrainfo_t *ei_tmp = NULL;
+  const int emit_ed_sigs = signing_keypair && extrainfo->signing_key_cert;
+  char *ed_cert_line = NULL;
 
   base16_encode(identity, sizeof(identity),
                 extrainfo->cache_info.identity_digest, DIGEST_LEN);
   format_iso_time(published, extrainfo->cache_info.published_on);
   bandwidth_usage = rep_hist_get_bandwidth_lines();
+  if (emit_ed_sigs) {
+    if (!extrainfo->signing_key_cert->signing_key_included ||
+        !ed25519_pubkey_eq(&extrainfo->signing_key_cert->signed_key,
+                           &signing_keypair->pubkey)) {
+      log_warn(LD_BUG, "Tried to sign a extrainfo descriptor with a "
+               "mismatched ed25519 key chain %d",
+               extrainfo->signing_key_cert->signing_key_included);
+      goto err;
+    }
+    char ed_cert_base64[256];
+    if (base64_encode(ed_cert_base64, sizeof(ed_cert_base64),
+                      (const char*)extrainfo->signing_key_cert->encoded,
+                      extrainfo->signing_key_cert->encoded_len,
+                      BASE64_ENCODE_MULTILINE) < 0) {
+      log_err(LD_BUG,"Couldn't base64-encode signing key certificate!");
+      goto err;
+    }
+    tor_asprintf(&ed_cert_line, "identity-ed25519\n"
+                 "-----BEGIN ED25519 CERT-----\n"
+                 "%s"
+                 "-----END ED25519 CERT-----\n", ed_cert_base64);
+  } else {
+    ed_cert_line = tor_strdup("");
+  }
 
-  tor_asprintf(&pre, "extra-info %s %s\npublished %s\n%s",
+  tor_asprintf(&pre, "extra-info %s %s\n%spublished %s\n%s",
                extrainfo->nickname, identity,
+               ed_cert_line,
                published, bandwidth_usage);
   tor_free(bandwidth_usage);
   smartlist_add(chunks, pre);
@@ -2757,6 +2940,23 @@ extrainfo_dump_to_string(char **s_out, extrainfo_t *extrainfo,
     }
   }
 
+  if (emit_ed_sigs) {
+    char digest[DIGEST256_LEN];
+    smartlist_add(chunks, tor_strdup("router-sig-ed25519 "));
+    crypto_digest_smartlist_prefix(digest, DIGEST256_LEN,
+                                   ED_DESC_SIGNATURE_PREFIX,
+                                   chunks, "", DIGEST_SHA256);
+    ed25519_signature_t sig;
+    char buf[ED25519_SIG_BASE64_LEN+1];
+    if (ed25519_sign(&sig, (const uint8_t*)digest, DIGEST256_LEN,
+                     signing_keypair) < 0)
+      goto err;
+    if (ed25519_signature_to_base64(buf, &sig) < 0)
+      goto err;
+
+    smartlist_add_asprintf(chunks, "%s\n", buf);
+  }
+
   smartlist_add(chunks, tor_strdup("router-signature\n"));
   s = smartlist_join_strings(chunks, "", 0, NULL);
 
@@ -2805,7 +3005,8 @@ extrainfo_dump_to_string(char **s_out, extrainfo_t *extrainfo,
                            "adding statistics to this or any future "
                            "extra-info descriptors.");
       write_stats_to_extrainfo = 0;
-      result = extrainfo_dump_to_string(s_out, extrainfo, ident_key);
+      result = extrainfo_dump_to_string(s_out, extrainfo, ident_key,
+                                        signing_keypair);
       goto done;
     } else {
       log_warn(LD_BUG, "We just generated an extrainfo descriptor we "
@@ -2827,6 +3028,7 @@ extrainfo_dump_to_string(char **s_out, extrainfo_t *extrainfo,
   SMARTLIST_FOREACH(chunks, char *, cp, tor_free(cp));
   smartlist_free(chunks);
   tor_free(s_dup);
+  tor_free(ed_cert_line);
   extrainfo_free(ei_tmp);
 
   return result;
diff --git a/src/or/router.h b/src/or/router.h
index 73b43bc751..61b35d6b5a 100644
--- a/src/or/router.h
+++ b/src/or/router.h
@@ -92,7 +92,10 @@ int router_pick_published_address(const or_options_t *options, uint32_t *addr);
 int router_build_fresh_descriptor(routerinfo_t **r, extrainfo_t **e);
 int router_rebuild_descriptor(int force);
 char *router_dump_router_to_string(routerinfo_t *router,
-                                   crypto_pk_t *ident_key);
+                                   const crypto_pk_t *ident_key,
+                                   const crypto_pk_t *tap_key,
+                                   const curve25519_keypair_t *ntor_keypair,
+                                   const ed25519_keypair_t *signing_keypair);
 char *router_dump_exit_policy_to_string(const routerinfo_t *router,
                                          int include_ipv4,
                                          int include_ipv6);
@@ -107,7 +110,8 @@ int router_has_addr(const routerinfo_t *router, const tor_addr_t *addr);
 int router_has_orport(const routerinfo_t *router,
                       const tor_addr_port_t *orport);
 int extrainfo_dump_to_string(char **s, extrainfo_t *extrainfo,
-                             crypto_pk_t *ident_key);
+                             crypto_pk_t *ident_key,
+                             const ed25519_keypair_t *signing_keypair);
 int is_legal_nickname(const char *s);
 int is_legal_nickname_or_hexdigest(const char *s);
 int is_legal_hexdigest(const char *s);
diff --git a/src/or/routerkeys.c b/src/or/routerkeys.c
new file mode 100644
index 0000000000..556ab45732
--- /dev/null
+++ b/src/or/routerkeys.c
@@ -0,0 +1,648 @@
+/* Copyright (c) 2014, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "or.h"
+#include "config.h"
+#include "router.h"
+#include "routerkeys.h"
+#include "torcert.h"
+
+/**
+ * Read an ed25519 key and associated certificates from files beginning with
+ * <b>fname</b>, with certificate type <b>cert_type</b>.  On failure, return
+ * NULL; on success return the keypair.
+ *
+ * If INIT_ED_KEY_CREATE is set in <b>flags</b>, then create the key (and
+ * certificate if requested) if it doesn't exist, and save it to disk.
+ *
+ * If INIT_ED_KEY_NEEDCERT is set in <b>flags</b>, load/create a certificate
+ * too and store it in *<b>cert_out</b>.  Fail if the cert can't be
+ * found/created.  To create a certificate, <b>signing_key</b> must be set to
+ * the key that should sign it; <b>now</b> to the current time, and
+ * <b>lifetime</b> to the lifetime of the key.
+ *
+ * If INIT_ED_KEY_REPLACE is set in <b>flags</b>, then create and save new key
+ * whether we can read the old one or not.
+ *
+ * If INIT_ED_KEY_EXTRA_STRONG is set in <b>flags</b>, set the extra_strong
+ * flag when creating the secret key.
+ *
+ * If INIT_ED_KEY_INCLUDE_SIGNING_KEY_IN_CERT is set in <b>flags</b>, and
+ * we create a new certificate, create it with the signing key embedded.
+ *
+ * If INIT_ED_KEY_SPLIT is set in <b>flags</b>, and we create a new key,
+ * store the public key in a separate file from the secret key.
+ *
+ * If INIT_ED_KEY_MISSING_SECRET_OK is set in <b>flags</b>, and we find a
+ * public key file but no secret key file, return successfully anyway.
+ *
+ * If INIT_ED_KEY_OMIT_SECRET is set in <b>flags</b>, do not even try to
+ * load or return a secret key (but create and save on if needed).
+ */
+ed25519_keypair_t *
+ed_key_init_from_file(const char *fname, uint32_t flags,
+                      int severity,
+                      const ed25519_keypair_t *signing_key,
+                      time_t now,
+                      time_t lifetime,
+                      uint8_t cert_type,
+                      struct tor_cert_st **cert_out)
+{
+  char *secret_fname = NULL;
+  char *public_fname = NULL;
+  char *cert_fname = NULL;
+  int created_pk = 0, created_sk = 0, created_cert = 0;
+  const int try_to_load = ! (flags & INIT_ED_KEY_REPLACE);
+
+  char tag[8];
+  tor_snprintf(tag, sizeof(tag), "type%d", (int)cert_type);
+
+  tor_cert_t *cert = NULL;
+  char *got_tag = NULL;
+  ed25519_keypair_t *keypair = tor_malloc_zero(sizeof(ed25519_keypair_t));
+
+  tor_asprintf(&secret_fname, "%s_secret_key", fname);
+  tor_asprintf(&public_fname, "%s_public_key", fname);
+  tor_asprintf(&cert_fname, "%s_cert", fname);
+
+  /* Try to read the secret key. */
+  const int have_secret = try_to_load &&
+    !(flags & INIT_ED_KEY_OMIT_SECRET) &&
+    ed25519_seckey_read_from_file(&keypair->seckey,
+                                  &got_tag, secret_fname) == 0;
+
+  if (have_secret) {
+    if (strcmp(got_tag, tag)) {
+      tor_log(severity, LD_OR, "%s has wrong tag", secret_fname);
+      goto err;
+    }
+    /* Derive the public key */
+    if (ed25519_public_key_generate(&keypair->pubkey, &keypair->seckey)<0) {
+      tor_log(severity, LD_OR, "%s can't produce a public key", secret_fname);
+      goto err;
+    }
+  }
+
+  /* If it's absent and that's okay, try to read the pubkey. */
+  int found_public = 0;
+  if (!have_secret && try_to_load) {
+    tor_free(got_tag);
+    found_public = ed25519_pubkey_read_from_file(&keypair->pubkey,
+                                                 &got_tag, public_fname) == 0;
+    if (found_public && strcmp(got_tag, tag)) {
+      tor_log(severity, LD_OR, "%s has wrong tag", public_fname);
+      goto err;
+    }
+  }
+
+  /* If the secret key is absent and it's not allowed to be, fail. */
+  if (!have_secret && found_public && !(flags & INIT_ED_KEY_MISSING_SECRET_OK))
+    goto err;
+
+  /* If it's absent, and we're not supposed to make a new keypair, fail. */
+  if (!have_secret && !found_public && !(flags & INIT_ED_KEY_CREATE))
+    goto err;
+
+  /* if it's absent, make a new keypair and save it. */
+  if (!have_secret && !found_public) {
+    const int split = !! (flags & INIT_ED_KEY_SPLIT);
+    tor_free(keypair);
+    keypair = ed_key_new(signing_key, flags, now, lifetime,
+                         cert_type, &cert);
+    if (!keypair) {
+      tor_log(severity, LD_OR, "Couldn't create keypair");
+      goto err;
+    }
+
+    created_pk = created_sk = created_cert = 1;
+    if (ed25519_seckey_write_to_file(&keypair->seckey, secret_fname, tag) < 0
+        ||
+        (split &&
+         ed25519_pubkey_write_to_file(&keypair->pubkey, public_fname, tag) < 0)
+        ||
+        (cert &&
+         crypto_write_tagged_contents_to_file(cert_fname, "ed25519v1-cert",
+                                 tag, cert->encoded, cert->encoded_len) < 0)) {
+      tor_log(severity, LD_OR, "Couldn't write keys or cert to file.");
+      goto err;
+    }
+    goto done;
+  }
+
+  /* If we're not supposed to get a cert, we're done. */
+  if (! (flags & INIT_ED_KEY_NEEDCERT))
+    goto done;
+
+  /* Read a cert. */
+  uint8_t certbuf[256];
+  ssize_t cert_body_len = crypto_read_tagged_contents_from_file(
+                 cert_fname, "ed25519v1-cert",
+                 &got_tag, certbuf, sizeof(certbuf));
+  if (cert_body_len >= 0 && !strcmp(got_tag, tag))
+    cert = tor_cert_parse(certbuf, cert_body_len);
+
+  /* If we got it, check it to the extent we can. */
+  if (cert) {
+    int bad_cert = 0;
+
+    if (! cert) {
+      tor_log(severity, LD_OR, "Cert was unparseable");
+      bad_cert = 1;
+    } else if (!tor_memeq(cert->signed_key.pubkey, keypair->pubkey.pubkey,
+                          ED25519_PUBKEY_LEN)) {
+      tor_log(severity, LD_OR, "Cert was for wrong key");
+      bad_cert = 1;
+    } else if (tor_cert_checksig(cert, &signing_key->pubkey, now) < 0 &&
+               (signing_key || cert->cert_expired)) {
+      tor_log(severity, LD_OR, "Can't check certificate");
+      bad_cert = 1;
+    }
+
+    if (bad_cert) {
+      tor_cert_free(cert);
+      cert = NULL;
+    }
+  }
+
+  /* If we got a cert, we're done. */
+  if (cert)
+    goto done;
+
+  /* If we didn't get a cert, and we're not supposed to make one, fail. */
+  if (!signing_key || !(flags & INIT_ED_KEY_CREATE))
+    goto err;
+
+  /* We have keys but not a certificate, so make one. */
+  uint32_t cert_flags = 0;
+  if (flags & INIT_ED_KEY_INCLUDE_SIGNING_KEY_IN_CERT)
+    cert_flags |= CERT_FLAG_INCLUDE_SIGNING_KEY;
+  cert = tor_cert_create(signing_key, cert_type,
+                         &keypair->pubkey,
+                         now, lifetime,
+                         cert_flags);
+
+  if (! cert)
+    goto err;
+
+  /* Write it to disk. */
+  created_cert = 1;
+  if (crypto_write_tagged_contents_to_file(cert_fname, "ed25519v1-cert",
+                             tag, cert->encoded, cert->encoded_len) < 0) {
+    tor_log(severity, LD_OR, "Couldn't write cert to disk.");
+    goto err;
+  }
+
+ done:
+  if (cert_out)
+    *cert_out = cert;
+  else
+    tor_cert_free(cert);
+
+  goto cleanup;
+
+ err:
+  memwipe(keypair, 0, sizeof(*keypair));
+  tor_free(keypair);
+  tor_cert_free(cert);
+  if (cert_out)
+    *cert_out = NULL;
+  if (created_sk)
+    unlink(secret_fname);
+  if (created_pk)
+    unlink(public_fname);
+  if (created_cert)
+    unlink(cert_fname);
+
+ cleanup:
+  tor_free(secret_fname);
+  tor_free(public_fname);
+  tor_free(cert_fname);
+
+  return keypair;
+}
+
+/**
+ * Create a new signing key and (optionally) certficiate; do not read or write
+ * from disk.  See ed_key_init_from_file() for more information.
+ */
+ed25519_keypair_t *
+ed_key_new(const ed25519_keypair_t *signing_key,
+           uint32_t flags,
+           time_t now,
+           time_t lifetime,
+           uint8_t cert_type,
+           struct tor_cert_st **cert_out)
+{
+  if (cert_out)
+    *cert_out = NULL;
+
+  const int extra_strong = !! (flags & INIT_ED_KEY_EXTRA_STRONG);
+  ed25519_keypair_t *keypair = tor_malloc_zero(sizeof(ed25519_keypair_t));
+  if (ed25519_keypair_generate(keypair, extra_strong) < 0)
+    goto err;
+
+  if (! (flags & INIT_ED_KEY_NEEDCERT))
+    return keypair;
+
+  tor_assert(signing_key);
+  tor_assert(cert_out);
+  uint32_t cert_flags = 0;
+  if (flags & INIT_ED_KEY_INCLUDE_SIGNING_KEY_IN_CERT)
+    cert_flags |= CERT_FLAG_INCLUDE_SIGNING_KEY;
+  tor_cert_t *cert = tor_cert_create(signing_key, cert_type,
+                                     &keypair->pubkey,
+                                     now, lifetime,
+                                     cert_flags);
+  if (! cert)
+    goto err;
+
+  *cert_out = cert;
+  return keypair;
+
+ err:
+  tor_free(keypair);
+  return NULL;
+}
+
+static ed25519_keypair_t *master_identity_key = NULL;
+static ed25519_keypair_t *master_signing_key = NULL;
+static ed25519_keypair_t *current_auth_key = NULL;
+static tor_cert_t *signing_key_cert = NULL;
+static tor_cert_t *link_cert_cert = NULL;
+static tor_cert_t *auth_key_cert = NULL;
+
+static uint8_t *rsa_ed_crosscert = NULL;
+static size_t rsa_ed_crosscert_len = 0;
+
+/**
+ * Running as a server: load, reload, or refresh our ed25519 keys and
+ * certificates, creating and saving new ones as needed.
+ */
+int
+load_ed_keys(const or_options_t *options, time_t now)
+{
+  ed25519_keypair_t *id = NULL;
+  ed25519_keypair_t *sign = NULL;
+  ed25519_keypair_t *auth = NULL;
+  const ed25519_keypair_t *sign_signing_key_with_id = NULL;
+  const ed25519_keypair_t *use_signing = NULL;
+  const tor_cert_t *check_signing_cert = NULL;
+  tor_cert_t *sign_cert = NULL;
+  tor_cert_t *auth_cert = NULL;
+
+#define FAIL(msg) do {                          \
+    log_warn(LD_OR, (msg));                     \
+    goto err;                                   \
+  } while (0)
+#define SET_KEY(key, newval) do {               \
+    ed25519_keypair_free(key);                  \
+    key = (newval);                             \
+  } while (0)
+#define SET_CERT(cert, newval) do {             \
+    tor_cert_free(cert);                        \
+    cert = (newval);                            \
+  } while (0)
+#define EXPIRES_SOON(cert, interval)            \
+  (!(cert) || (cert)->valid_until < now + (interval))
+
+  /* XXXX support encrypted identity keys fully */
+
+  /* First try to get the signing key to see how it is. */
+  if (master_signing_key) {
+    check_signing_cert = signing_key_cert;
+    use_signing = master_signing_key;
+  } else {
+    sign = ed_key_init_from_file(
+               options_get_datadir_fname2(options, "keys", "ed25519_signing"),
+               INIT_ED_KEY_NEEDCERT|
+               INIT_ED_KEY_INCLUDE_SIGNING_KEY_IN_CERT,
+               LOG_INFO,
+               NULL, 0, 0, CERT_TYPE_ID_SIGNING, &sign_cert);
+    check_signing_cert = sign_cert;
+    use_signing = sign;
+  }
+
+  const int need_new_signing_key =
+    NULL == use_signing ||
+    EXPIRES_SOON(check_signing_cert, 0);
+  const int want_new_signing_key =
+    need_new_signing_key ||
+    EXPIRES_SOON(check_signing_cert, options->TestingSigningKeySlop);
+
+  {
+    uint32_t flags =
+      (INIT_ED_KEY_CREATE|INIT_ED_KEY_SPLIT|
+       INIT_ED_KEY_EXTRA_STRONG);
+    if (! need_new_signing_key)
+      flags |= INIT_ED_KEY_MISSING_SECRET_OK;
+    if (! want_new_signing_key)
+      flags |= INIT_ED_KEY_OMIT_SECRET;
+
+    id = ed_key_init_from_file(
+             options_get_datadir_fname2(options, "keys", "ed25519_master_id"),
+             flags,
+             LOG_WARN, NULL, 0, 0, 0, NULL);
+    if (!id)
+      FAIL("Missing identity key");
+    if (tor_mem_is_zero((char*)id->seckey.seckey, sizeof(id->seckey)))
+      sign_signing_key_with_id = NULL;
+    else
+      sign_signing_key_with_id = id;
+  }
+
+  if (need_new_signing_key && NULL == sign_signing_key_with_id)
+    FAIL("Can't load master key make a new signing key.");
+
+  if (want_new_signing_key && sign_signing_key_with_id) {
+    uint32_t flags = (INIT_ED_KEY_CREATE|
+                      INIT_ED_KEY_REPLACE|
+                      INIT_ED_KEY_EXTRA_STRONG|
+                      INIT_ED_KEY_NEEDCERT|
+                      INIT_ED_KEY_INCLUDE_SIGNING_KEY_IN_CERT);
+    sign = ed_key_init_from_file(
+               options_get_datadir_fname2(options, "keys", "ed25519_signing"),
+                                 flags, LOG_WARN,
+                                 sign_signing_key_with_id, now,
+                                 options->SigningKeyLifetime,
+                                 CERT_TYPE_ID_SIGNING, &sign_cert);
+    if (!sign)
+      FAIL("Missing signing key");
+    use_signing = sign;
+  } else if (want_new_signing_key) {
+    static ratelim_t missing_master = RATELIM_INIT(3600);
+    log_fn_ratelim(&missing_master, LOG_WARN, LD_OR,
+                   "Signing key will expire soon, but I can't load the "
+                   "master key to sign a new one!");
+  }
+
+  tor_assert(use_signing);
+
+  /* At this point we no longer need our secret identity key.  So wipe
+   * it, if we loaded it in the first place. */
+  memwipe(id->seckey.seckey, 0, sizeof(id->seckey));
+
+  if (!rsa_ed_crosscert && server_mode(options)) {
+    uint8_t *crosscert;
+    ssize_t crosscert_len = tor_make_rsa_ed25519_crosscert(&id->pubkey,
+                                                   get_server_identity_key(),
+                                                   now+10*365*86400,/*XXXX*/
+                                                   &crosscert);
+    rsa_ed_crosscert_len = crosscert_len;
+    rsa_ed_crosscert = crosscert;
+  }
+
+  if (!current_auth_key ||
+      EXPIRES_SOON(auth_key_cert, options->TestingAuthKeySlop)) {
+    auth = ed_key_new(use_signing, INIT_ED_KEY_NEEDCERT,
+                      now,
+                      options->TestingAuthKeyLifetime,
+                      CERT_TYPE_SIGNING_AUTH, &auth_cert);
+
+    if (!auth)
+      FAIL("Can't create auth key");
+  }
+
+  /* We've generated or loaded everything.  Put them in memory. */
+
+  if (! master_identity_key) {
+    SET_KEY(master_identity_key, id);
+  } else {
+    tor_free(id);
+  }
+  if (sign) {
+    SET_KEY(master_signing_key, sign);
+    SET_CERT(signing_key_cert, sign_cert);
+  }
+  if (auth) {
+    SET_KEY(current_auth_key, auth);
+    SET_CERT(auth_key_cert, auth_cert);
+  }
+
+  return 0;
+ err:
+  ed25519_keypair_free(id);
+  ed25519_keypair_free(sign);
+  ed25519_keypair_free(auth);
+  tor_cert_free(sign_cert);
+  tor_cert_free(auth_cert);
+  return -1;
+}
+
+/**DOCDOC*/
+int
+generate_ed_link_cert(const or_options_t *options, time_t now)
+{
+  const tor_x509_cert_t *link = NULL, *id = NULL;
+  tor_cert_t *link_cert = NULL;
+
+  if (tor_tls_get_my_certs(1, &link, &id) < 0 || link == NULL) {
+    log_warn(LD_OR, "Can't get my x509 link cert.");
+    return -1;
+  }
+
+  const digests_t *digests = tor_x509_cert_get_cert_digests(link);
+
+  if (link_cert_cert &&
+      ! EXPIRES_SOON(link_cert_cert, options->TestingLinkKeySlop) &&
+      fast_memeq(digests->d[DIGEST_SHA256], link_cert_cert->signed_key.pubkey,
+                 DIGEST256_LEN)) {
+    return 0;
+  }
+
+  ed25519_public_key_t dummy_key;
+  memcpy(dummy_key.pubkey, digests->d[DIGEST_SHA256], DIGEST256_LEN);
+
+  link_cert = tor_cert_create(get_master_signing_keypair(),
+                              CERT_TYPE_SIGNING_LINK,
+                              &dummy_key,
+                              now,
+                              options->TestingLinkCertLifetime, 0);
+
+  if (link_cert) {
+    SET_CERT(link_cert_cert, link_cert);
+  }
+  return 0;
+}
+
+#undef FAIL
+#undef SET_KEY
+#undef SET_CERT
+
+int
+should_make_new_ed_keys(const or_options_t *options, const time_t now)
+{
+  if (!master_identity_key ||
+      !master_signing_key ||
+      !current_auth_key ||
+      !link_cert_cert ||
+      EXPIRES_SOON(signing_key_cert, options->TestingSigningKeySlop) ||
+      EXPIRES_SOON(auth_key_cert, options->TestingAuthKeySlop) ||
+      EXPIRES_SOON(link_cert_cert, options->TestingLinkKeySlop))
+    return 1;
+
+  const tor_x509_cert_t *link = NULL, *id = NULL;
+
+  if (tor_tls_get_my_certs(1, &link, &id) < 0 || link == NULL)
+    return 1;
+
+  const digests_t *digests = tor_x509_cert_get_cert_digests(link);
+
+  if (!fast_memeq(digests->d[DIGEST_SHA256],
+                  link_cert_cert->signed_key.pubkey,
+                  DIGEST256_LEN)) {
+    return 1;
+  }
+
+  return 0;
+}
+
+#undef EXPIRES_SOON
+
+const ed25519_public_key_t *
+get_master_identity_key(void)
+{
+  if (!master_identity_key)
+    return NULL;
+  return &master_identity_key->pubkey;
+}
+
+const ed25519_keypair_t *
+get_master_signing_keypair(void)
+{
+  return master_signing_key;
+}
+
+const struct tor_cert_st *
+get_master_signing_key_cert(void)
+{
+  return signing_key_cert;
+}
+
+const ed25519_keypair_t *
+get_current_auth_keypair(void)
+{
+  return current_auth_key;
+}
+
+const tor_cert_t *
+get_current_link_cert_cert(void)
+{
+  return link_cert_cert;
+}
+
+const tor_cert_t *
+get_current_auth_key_cert(void)
+{
+  return auth_key_cert;
+}
+
+void
+get_master_rsa_crosscert(const uint8_t **cert_out,
+                         size_t *size_out)
+{
+  *cert_out = rsa_ed_crosscert;
+  *size_out = rsa_ed_crosscert_len;
+}
+
+/** Construct cross-certification for the master identity key with
+ * the ntor onion key. Store the sign of the corresponding ed25519 public key
+ * in *<b>sign_out</b>. */
+tor_cert_t *
+make_ntor_onion_key_crosscert(const curve25519_keypair_t *onion_key,
+      const ed25519_public_key_t *master_id_key, time_t now, time_t lifetime,
+      int *sign_out)
+{
+  tor_cert_t *cert = NULL;
+  ed25519_keypair_t ed_onion_key;
+
+  if (ed25519_keypair_from_curve25519_keypair(&ed_onion_key, sign_out,
+                                              onion_key) < 0)
+    goto end;
+
+  cert = tor_cert_create(&ed_onion_key, CERT_TYPE_ONION_ID, master_id_key,
+      now, lifetime, 0);
+
+ end:
+  memwipe(&ed_onion_key, 0, sizeof(ed_onion_key));
+  return cert;
+}
+
+/** Construct and return an RSA signature for the TAP onion key to
+ * cross-certify the RSA and Ed25519 identity keys. Set <b>len_out</b> to its
+ * length. */
+uint8_t *
+make_tap_onion_key_crosscert(const crypto_pk_t *onion_key,
+                             const ed25519_public_key_t *master_id_key,
+                             const crypto_pk_t *rsa_id_key,
+                             int *len_out)
+{
+  uint8_t signature[PK_BYTES];
+  uint8_t signed_data[DIGEST_LEN + ED25519_PUBKEY_LEN];
+
+  *len_out = 0;
+  crypto_pk_get_digest(rsa_id_key, (char*)signed_data);
+  memcpy(signed_data + DIGEST_LEN, master_id_key->pubkey, ED25519_PUBKEY_LEN);
+
+  int r = crypto_pk_private_sign(onion_key,
+                               (char*)signature, sizeof(signature),
+                               (const char*)signed_data, sizeof(signed_data));
+  if (r < 0)
+    return NULL;
+
+  *len_out = r;
+
+  return tor_memdup(signature, r);
+}
+
+/** Check whether an RSA-TAP cross-certification is correct. Return 0 if it
+ * is, -1 if it isn't. */
+int
+check_tap_onion_key_crosscert(const uint8_t *crosscert,
+                              int crosscert_len,
+                              const crypto_pk_t *onion_pkey,
+                              const ed25519_public_key_t *master_id_pkey,
+                              const uint8_t *rsa_id_digest)
+{
+  uint8_t *cc = tor_malloc(crypto_pk_keysize(onion_pkey));
+  int cc_len =
+    crypto_pk_public_checksig(onion_pkey,
+                              (char*)cc,
+                              crypto_pk_keysize(onion_pkey),
+                              (const char*)crosscert,
+                              crosscert_len);
+  if (cc_len < 0) {
+    goto err;
+  }
+  if (cc_len < DIGEST_LEN + ED25519_PUBKEY_LEN) {
+    log_warn(LD_DIR, "Short signature on cross-certification with TAP key");
+    goto err;
+  }
+  if (tor_memneq(cc, rsa_id_digest, DIGEST_LEN) ||
+      tor_memneq(cc + DIGEST_LEN, master_id_pkey->pubkey,
+                 ED25519_PUBKEY_LEN)) {
+    log_warn(LD_DIR, "Incorrect cross-certification with TAP key");
+    goto err;
+  }
+
+  tor_free(cc);
+  return 0;
+ err:
+  tor_free(cc);
+  return -1;
+}
+
+void
+routerkeys_free_all(void)
+{
+  ed25519_keypair_free(master_identity_key);
+  ed25519_keypair_free(master_signing_key);
+  ed25519_keypair_free(current_auth_key);
+  tor_cert_free(signing_key_cert);
+  tor_cert_free(link_cert_cert);
+  tor_cert_free(auth_key_cert);
+
+  master_identity_key = master_signing_key = NULL;
+  current_auth_key = NULL;
+  signing_key_cert = link_cert_cert = auth_key_cert = NULL;
+}
+
diff --git a/src/or/routerkeys.h b/src/or/routerkeys.h
new file mode 100644
index 0000000000..b45a22ac12
--- /dev/null
+++ b/src/or/routerkeys.h
@@ -0,0 +1,67 @@
+/* Copyright (c) 2014, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TOR_ROUTERKEYS_H
+#define TOR_ROUTERKEYS_H
+
+#include "crypto_ed25519.h"
+
+#define INIT_ED_KEY_CREATE                      (1u<<0)
+#define INIT_ED_KEY_REPLACE                     (1u<<1)
+#define INIT_ED_KEY_SPLIT                       (1u<<2)
+#define INIT_ED_KEY_MISSING_SECRET_OK           (1u<<3)
+#define INIT_ED_KEY_NEEDCERT                    (1u<<4)
+#define INIT_ED_KEY_EXTRA_STRONG                (1u<<5)
+#define INIT_ED_KEY_INCLUDE_SIGNING_KEY_IN_CERT (1u<<6)
+#define INIT_ED_KEY_OMIT_SECRET                 (1u<<7)
+
+struct tor_cert_st;
+ed25519_keypair_t *ed_key_init_from_file(const char *fname, uint32_t flags,
+                                         int severity,
+                                         const ed25519_keypair_t *signing_key,
+                                         time_t now,
+                                         time_t lifetime,
+                                         uint8_t cert_type,
+                                         struct tor_cert_st **cert_out);
+ed25519_keypair_t *ed_key_new(const ed25519_keypair_t *signing_key,
+                              uint32_t flags,
+                              time_t now,
+                              time_t lifetime,
+                              uint8_t cert_type,
+                              struct tor_cert_st **cert_out);
+const ed25519_public_key_t *get_master_identity_key(void);
+const ed25519_keypair_t *get_master_signing_keypair(void);
+const struct tor_cert_st *get_master_signing_key_cert(void);
+
+const ed25519_keypair_t *get_current_auth_keypair(void);
+const struct tor_cert_st *get_current_link_cert_cert(void);
+const struct tor_cert_st *get_current_auth_key_cert(void);
+
+void get_master_rsa_crosscert(const uint8_t **cert_out,
+                              size_t *size_out);
+
+struct tor_cert_st *make_ntor_onion_key_crosscert(
+                                  const curve25519_keypair_t *onion_key,
+                                  const ed25519_public_key_t *master_id_key,
+                                  time_t now, time_t lifetime,
+                                  int *sign_out);
+uint8_t *make_tap_onion_key_crosscert(const crypto_pk_t *onion_key,
+                                  const ed25519_public_key_t *master_id_key,
+                                  const crypto_pk_t *rsa_id_key,
+                                  int *len_out);
+
+int check_tap_onion_key_crosscert(const uint8_t *crosscert,
+                                  int crosscert_len,
+                                  const crypto_pk_t *onion_pkey,
+                                  const ed25519_public_key_t *master_id_pkey,
+                                  const uint8_t *rsa_id_digest);
+
+int load_ed_keys(const or_options_t *options, time_t now);
+int should_make_new_ed_keys(const or_options_t *options, const time_t now);
+
+int generate_ed_link_cert(const or_options_t *options, time_t now);
+
+void routerkeys_free_all(void);
+
+#endif
+
diff --git a/src/or/routerlist.c b/src/or/routerlist.c
index fd096799de..7eba13a544 100644
--- a/src/or/routerlist.c
+++ b/src/or/routerlist.c
@@ -13,6 +13,7 @@
 
 #define ROUTERLIST_PRIVATE
 #include "or.h"
+#include "crypto_ed25519.h"
 #include "circuitstats.h"
 #include "config.h"
 #include "connection.h"
@@ -38,6 +39,8 @@
 #include "routerparse.h"
 #include "routerset.h"
 #include "sandbox.h"
+#include "torcert.h"
+
 // #define DEBUG_ROUTERLIST
 
 /****************************************************************************/
@@ -2660,6 +2663,7 @@ routerinfo_free(routerinfo_t *router)
   tor_free(router->onion_curve25519_pkey);
   if (router->identity_pkey)
     crypto_pk_free(router->identity_pkey);
+  tor_cert_free(router->signing_key_cert);
   if (router->declared_family) {
     SMARTLIST_FOREACH(router->declared_family, char *, s, tor_free(s));
     smartlist_free(router->declared_family);
@@ -2678,6 +2682,7 @@ extrainfo_free(extrainfo_t *extrainfo)
 {
   if (!extrainfo)
     return;
+  tor_cert_free(extrainfo->signing_key_cert);
   tor_free(extrainfo->cache_info.signed_descriptor_body);
   tor_free(extrainfo->pending_sig);
 
@@ -3288,6 +3293,11 @@ router_add_to_routerlist(routerinfo_t *router, const char **msg,
 
   old_router = router_get_mutable_by_digest(id_digest);
 
+  /* Make sure that it isn't expired. */
+  if (router->cert_expiration_time < approx_time()) {
+    return ROUTER_CERTS_EXPIRED;
+  }
+
   /* Make sure that we haven't already got this exact descriptor. */
   if (sdmap_get(routerlist->desc_digest_map,
                 router->cache_info.signed_descriptor_digest)) {
@@ -4894,7 +4904,7 @@ routerinfo_incompatible_with_extrainfo(const routerinfo_t *ri,
                                        signed_descriptor_t *sd,
                                        const char **msg)
 {
-  int digest_matches, r=1;
+  int digest_matches, digest256_matches, r=1;
   tor_assert(ri);
   tor_assert(ei);
   if (!sd)
@@ -4907,6 +4917,11 @@ routerinfo_incompatible_with_extrainfo(const routerinfo_t *ri,
 
   digest_matches = tor_memeq(ei->cache_info.signed_descriptor_digest,
                            sd->extra_info_digest, DIGEST_LEN);
+  /* Set digest256_matches to 1 if the digest is correct, or if no
+   * digest256 was in the ri. */
+  digest256_matches = tor_memeq(ei->digest256,
+                                ri->extra_info_digest256, DIGEST256_LEN);
+  digest256_matches |= tor_mem_is_zero(ri->extra_info_digest256, DIGEST256_LEN);
 
   /* The identity must match exactly to have been generated at the same time
    * by the same router. */
@@ -4917,6 +4932,11 @@ routerinfo_incompatible_with_extrainfo(const routerinfo_t *ri,
     goto err; /* different servers */
   }
 
+  if (! tor_cert_opt_eq(ri->signing_key_cert, ei->signing_key_cert)) {
+    if (msg) *msg = "Extrainfo signing key cert didn't match routerinfo";
+    goto err; /* different servers */
+  }
+
   if (ei->pending_sig) {
     char signed_digest[128];
     if (crypto_pk_public_checksig(ri->identity_pkey,
@@ -4943,6 +4963,11 @@ routerinfo_incompatible_with_extrainfo(const routerinfo_t *ri,
     goto err;
   }
 
+  if (!digest256_matches) {
+    if (msg) *msg = "Extrainfo digest did not match digest256 from routerdesc";
+    goto err; /* Digest doesn't match declared value. */
+  }
+
   if (!digest_matches) {
     if (msg) *msg = "Extrainfo digest did not match value from routerdesc";
     goto err; /* Digest doesn't match declared value. */
diff --git a/src/or/routerlist.h b/src/or/routerlist.h
index 78c3fbb880..200533fe91 100644
--- a/src/or/routerlist.h
+++ b/src/or/routerlist.h
@@ -118,13 +118,15 @@ WRA_WAS_ADDED(was_router_added_t s) {
  * - not in the consensus
  * - neither in the consensus nor in any networkstatus document
  * - it was outdated.
+ * - its certificates were expired.
  */
 static INLINE int WRA_WAS_OUTDATED(was_router_added_t s)
 {
   return (s == ROUTER_WAS_TOO_OLD ||
           s == ROUTER_IS_ALREADY_KNOWN ||
           s == ROUTER_NOT_IN_CONSENSUS ||
-          s == ROUTER_NOT_IN_CONSENSUS_OR_NETWORKSTATUS);
+          s == ROUTER_NOT_IN_CONSENSUS_OR_NETWORKSTATUS ||
+          s == ROUTER_CERTS_EXPIRED);
 }
 /** Return true iff the outcome code in <b>s</b> indicates that the descriptor
  * was flat-out rejected. */
@@ -138,7 +140,8 @@ static INLINE int WRA_NEVER_DOWNLOADABLE(was_router_added_t s)
 {
   return (s == ROUTER_AUTHDIR_REJECTS ||
           s == ROUTER_BAD_EI ||
-          s == ROUTER_WAS_TOO_OLD);
+          s == ROUTER_WAS_TOO_OLD ||
+          s == ROUTER_CERTS_EXPIRED);
 }
 was_router_added_t router_add_to_routerlist(routerinfo_t *router,
                                             const char **msg,
diff --git a/src/or/routerparse.c b/src/or/routerparse.c
index f15aeeb0cf..c3dc241573 100644
--- a/src/or/routerparse.c
+++ b/src/or/routerparse.c
@@ -24,8 +24,11 @@
 #include "microdesc.h"
 #include "networkstatus.h"
 #include "rephist.h"
+#include "routerkeys.h"
 #include "routerparse.h"
 #include "entrynodes.h"
+#include "torcert.h"
+
 #undef log
 #include <math.h>
 
@@ -69,6 +72,7 @@ typedef enum {
   K_CLIENT_VERSIONS,
   K_SERVER_VERSIONS,
   K_OR_ADDRESS,
+  K_ID,
   K_P,
   K_P6,
   K_R,
@@ -83,6 +87,10 @@ typedef enum {
   K_HIDDEN_SERVICE_DIR,
   K_ALLOW_SINGLE_HOP_EXITS,
   K_IPV6_POLICY,
+  K_ROUTER_SIG_ED25519,
+  K_IDENTITY_ED25519,
+  K_ONION_KEY_CROSSCERT,
+  K_NTOR_ONION_KEY_CROSSCERT,
 
   K_DIRREQ_END,
   K_DIRREQ_V2_IPS,
@@ -293,6 +301,12 @@ static token_rule_t routerdesc_token_table[] = {
   T01("write-history",       K_WRITE_HISTORY,       ARGS,    NO_OBJ ),
   T01("extra-info-digest",   K_EXTRA_INFO_DIGEST,   GE(1),   NO_OBJ ),
   T01("hidden-service-dir",  K_HIDDEN_SERVICE_DIR,  NO_ARGS, NO_OBJ ),
+  T01("identity-ed25519",    K_IDENTITY_ED25519,    NO_ARGS, NEED_OBJ ),
+  T01("router-sig-ed25519",  K_ROUTER_SIG_ED25519,  GE(1),   NO_OBJ ),
+  T01("onion-key-crosscert", K_ONION_KEY_CROSSCERT, NO_ARGS, NEED_OBJ ),
+  T01("ntor-onion-key-crosscert", K_NTOR_ONION_KEY_CROSSCERT,
+                                                    EQ(1),   NEED_OBJ ),
+
   T01("allow-single-hop-exits",K_ALLOW_SINGLE_HOP_EXITS,    NO_ARGS, NO_OBJ ),
 
   T01("family",              K_FAMILY,              ARGS,    NO_OBJ ),
@@ -310,6 +324,8 @@ static token_rule_t routerdesc_token_table[] = {
 static token_rule_t extrainfo_token_table[] = {
   T1_END( "router-signature",    K_ROUTER_SIGNATURE,    NO_ARGS, NEED_OBJ ),
   T1( "published",           K_PUBLISHED,       CONCAT_ARGS, NO_OBJ ),
+  T01("identity-ed25519",    K_IDENTITY_ED25519,    NO_ARGS, NEED_OBJ ),
+  T01("router-sig-ed25519",  K_ROUTER_SIG_ED25519,  GE(1),   NO_OBJ ),
   T0N("opt",                 K_OPT,             CONCAT_ARGS, OBJ_OK ),
   T01("read-history",        K_READ_HISTORY,        ARGS,    NO_OBJ ),
   T01("write-history",       K_WRITE_HISTORY,       ARGS,    NO_OBJ ),
@@ -353,6 +369,7 @@ static token_rule_t rtrstatus_token_table[] = {
   T01("v",                   K_V,               CONCAT_ARGS, NO_OBJ ),
   T01("w",                   K_W,                   ARGS,    NO_OBJ ),
   T0N("m",                   K_M,               CONCAT_ARGS, NO_OBJ ),
+  T0N("id",                  K_ID,                  GE(2),   NO_OBJ ),
   T0N("opt",                 K_OPT,             CONCAT_ARGS, OBJ_OK ),
   END_OF_TABLE
 };
@@ -490,6 +507,7 @@ static token_rule_t networkstatus_detached_signature_token_table[] = {
 static token_rule_t microdesc_token_table[] = {
   T1_START("onion-key",        K_ONION_KEY,        NO_ARGS,     NEED_KEY_1024),
   T01("ntor-onion-key",        K_ONION_KEY_NTOR,   GE(1),       NO_OBJ ),
+  T0N("id",                    K_ID,               GE(2),       NO_OBJ ),
   T0N("a",                     K_A,                GE(1),       NO_OBJ ),
   T01("family",                K_FAMILY,           ARGS,        NO_OBJ ),
   T01("p",                     K_P,                CONCAT_ARGS, NO_OBJ ),
@@ -506,6 +524,10 @@ static addr_policy_t *router_parse_addr_policy(directory_token_t *tok,
                                                unsigned fmt_flags);
 static addr_policy_t *router_parse_addr_policy_private(directory_token_t *tok);
 
+static int router_get_hash_impl_helper(const char *s, size_t s_len,
+                            const char *start_str,
+                            const char *end_str, char end_c,
+                            const char **start_out, const char **end_out);
 static int router_get_hash_impl(const char *s, size_t s_len, char *digest,
                                 const char *start_str, const char *end_str,
                                 char end_char,
@@ -637,7 +659,7 @@ router_get_extrainfo_hash(const char *s, size_t s_len, char *digest)
 char *
 router_get_dirobj_signature(const char *digest,
                             size_t digest_len,
-                            crypto_pk_t *private_key)
+                            const crypto_pk_t *private_key)
 {
   char *signature;
   size_t i, keysize;
@@ -858,8 +880,8 @@ check_signature_token(const char *digest,
     tor_free(signed_digest);
     return -1;
   }
-//  log_debug(LD_DIR,"Signed %s hash starts %s", doctype,
-//            hex_str(signed_digest,4));
+  //  log_debug(LD_DIR,"Signed %s hash starts %s", doctype,
+  //            hex_str(signed_digest,4));
   if (tor_memneq(digest, signed_digest, digest_len)) {
     log_warn(LD_DIR, "Error reading %s: signature does not match.", doctype);
     tor_free(signed_digest);
@@ -1106,6 +1128,7 @@ router_parse_entry_from_string(const char *s, const char *end,
   size_t prepend_len = prepend_annotations ? strlen(prepend_annotations) : 0;
   int ok = 1;
   memarea_t *area = NULL;
+  tor_cert_t *ntor_cc_cert = NULL;
   /* Do not set this to '1' until we have parsed everything that we intend to
    * parse that's covered by the hash. */
   int can_dl_again = 0;
@@ -1178,9 +1201,11 @@ router_parse_entry_from_string(const char *s, const char *end,
   }
 
   tok = find_by_keyword(tokens, K_ROUTER);
+  const int router_token_pos = smartlist_pos(tokens, tok);
   tor_assert(tok->n_args >= 5);
 
   router = tor_malloc_zero(sizeof(routerinfo_t));
+  router->cert_expiration_time = TIME_MAX;
   router->cache_info.routerlist_index = -1;
   router->cache_info.annotations_len = s-start_of_annotations + prepend_len;
   router->cache_info.signed_descriptor_len = end-s;
@@ -1311,6 +1336,147 @@ router_parse_entry_from_string(const char *s, const char *end,
     log_warn(LD_DIR, "Couldn't calculate key digest"); goto err;
   }
 
+  {
+    directory_token_t *ed_sig_tok, *ed_cert_tok, *cc_tap_tok, *cc_ntor_tok;
+    ed_sig_tok = find_opt_by_keyword(tokens, K_ROUTER_SIG_ED25519);
+    ed_cert_tok = find_opt_by_keyword(tokens, K_IDENTITY_ED25519);
+    cc_tap_tok = find_opt_by_keyword(tokens, K_ONION_KEY_CROSSCERT);
+    cc_ntor_tok = find_opt_by_keyword(tokens, K_NTOR_ONION_KEY_CROSSCERT);
+    int n_ed_toks = !!ed_sig_tok + !!ed_cert_tok +
+      !!cc_tap_tok + !!cc_ntor_tok;
+    if ((n_ed_toks != 0 && n_ed_toks != 4) ||
+        (n_ed_toks == 4 && !router->onion_curve25519_pkey)) {
+      log_warn(LD_DIR, "Router descriptor with only partial ed25519/"
+               "cross-certification support");
+      goto err;
+    }
+    if (ed_sig_tok) {
+      tor_assert(ed_cert_tok && cc_tap_tok && cc_ntor_tok);
+      const int ed_cert_token_pos = smartlist_pos(tokens, ed_cert_tok);
+      if (ed_cert_token_pos == -1 || router_token_pos == -1 ||
+          (ed_cert_token_pos != router_token_pos + 1 &&
+           ed_cert_token_pos != router_token_pos - 1)) {
+        log_warn(LD_DIR, "Ed25519 certificate in wrong position");
+        goto err;
+      }
+      if (ed_sig_tok != smartlist_get(tokens, smartlist_len(tokens)-2)) {
+        log_warn(LD_DIR, "Ed25519 signature in wrong position");
+        goto err;
+      }
+      if (strcmp(ed_cert_tok->object_type, "ED25519 CERT")) {
+        log_warn(LD_DIR, "Wrong object type on identity-ed25519 in decriptor");
+        goto err;
+      }
+      if (strcmp(cc_ntor_tok->object_type, "ED25519 CERT")) {
+        log_warn(LD_DIR, "Wrong object type on ntor-onion-key-crosscert "
+                 "in decriptor");
+        goto err;
+      }
+      if (strcmp(cc_tap_tok->object_type, "CROSSCERT")) {
+        log_warn(LD_DIR, "Wrong object type on onion-key-crosscert "
+                 "in decriptor");
+        goto err;
+      }
+      if (strcmp(cc_ntor_tok->args[0], "0") &&
+          strcmp(cc_ntor_tok->args[0], "1")) {
+        log_warn(LD_DIR, "Bad sign bit on ntor-onion-key-crosscert");
+        goto err;
+      }
+      int ntor_cc_sign_bit = !strcmp(cc_ntor_tok->args[0], "1");
+
+      uint8_t d256[DIGEST256_LEN];
+      const char *signed_start, *signed_end;
+      tor_cert_t *cert = tor_cert_parse(
+                       (const uint8_t*)ed_cert_tok->object_body,
+                       ed_cert_tok->object_size);
+      if (! cert) {
+        log_warn(LD_DIR, "Couldn't parse ed25519 cert");
+        goto err;
+      }
+      router->signing_key_cert = cert; /* makes sure it gets freed. */
+      if (cert->cert_type != CERT_TYPE_ID_SIGNING ||
+          ! cert->signing_key_included) {
+        log_warn(LD_DIR, "Invalid form for ed25519 cert");
+        goto err;
+      }
+
+      ntor_cc_cert = tor_cert_parse((const uint8_t*)cc_ntor_tok->object_body,
+                                    cc_ntor_tok->object_size);
+      if (!ntor_cc_cert) {
+        log_warn(LD_DIR, "Couldn't parse ntor-onion-key-crosscert cert");
+        goto err;
+      }
+      if (ntor_cc_cert->cert_type != CERT_TYPE_ONION_ID ||
+          ! ed25519_pubkey_eq(&ntor_cc_cert->signed_key, &cert->signing_key)) {
+        log_warn(LD_DIR, "Invalid contents for ntor-onion-key-crosscert cert");
+        goto err;
+      }
+
+      ed25519_public_key_t ntor_cc_pk;
+      if (ed25519_public_key_from_curve25519_public_key(&ntor_cc_pk,
+                                            router->onion_curve25519_pkey,
+                                            ntor_cc_sign_bit)<0) {
+        log_warn(LD_DIR, "Error converting onion key to ed25519");
+        goto err;
+      }
+
+      if (router_get_hash_impl_helper(s, end-s, "router ",
+                                      "\nrouter-sig-ed25519",
+                                      ' ', &signed_start, &signed_end) < 0) {
+        log_warn(LD_DIR, "Can't find ed25519-signed portion of descriptor");
+        goto err;
+      }
+      crypto_digest_t *d = crypto_digest256_new(DIGEST_SHA256);
+      crypto_digest_add_bytes(d, ED_DESC_SIGNATURE_PREFIX,
+        strlen(ED_DESC_SIGNATURE_PREFIX));
+      crypto_digest_add_bytes(d, signed_start, signed_end-signed_start);
+      crypto_digest_get_digest(d, (char*)d256, sizeof(d256));
+      crypto_digest_free(d);
+
+      ed25519_checkable_t check[3];
+      int check_ok[3];
+      if (tor_cert_get_checkable_sig(&check[0], cert, NULL) < 0) {
+        log_err(LD_BUG, "Couldn't create 'checkable' for cert.");
+        goto err;
+      }
+      if (tor_cert_get_checkable_sig(&check[1],
+                                     ntor_cc_cert, &ntor_cc_pk) < 0) {
+        log_err(LD_BUG, "Couldn't create 'checkable' for ntor_cc_cert.");
+        goto err;
+      }
+
+      if (ed25519_signature_from_base64(&check[2].signature,
+                                        ed_sig_tok->args[0])<0) {
+        log_warn(LD_DIR, "Couldn't decode ed25519 signature");
+        goto err;
+      }
+      check[2].pubkey = &cert->signed_key;
+      check[2].msg = d256;
+      check[2].len = DIGEST256_LEN;
+
+      if (ed25519_checksig_batch(check_ok, check, 3) < 0) {
+        log_warn(LD_DIR, "Incorrect ed25519 signature(s)");
+        goto err;
+      }
+
+      if (check_tap_onion_key_crosscert(
+                      (const uint8_t*)cc_tap_tok->object_body,
+                      (int)cc_tap_tok->object_size,
+                      router->onion_pkey,
+                      &cert->signing_key,
+                      (const uint8_t*)router->cache_info.identity_digest)<0) {
+        log_warn(LD_DIR, "Incorrect TAP cross-verification");
+        goto err;
+      }
+
+      /* We check this before adding it to the routerlist. */
+      if (cert->valid_until < ntor_cc_cert->valid_until)
+        router->cert_expiration_time = cert->valid_until;
+      else
+        router->cert_expiration_time = ntor_cc_cert->valid_until;
+    }
+  }
+
   if ((tok = find_opt_by_keyword(tokens, K_FINGERPRINT))) {
     /* If there's a fingerprint line, it must match the identity digest. */
     char d[DIGEST_LEN];
@@ -1402,6 +1568,14 @@ router_parse_entry_from_string(const char *s, const char *end,
     } else {
       log_warn(LD_DIR, "Invalid extra info digest %s", escaped(tok->args[0]));
     }
+
+    if (tok->n_args >= 2) {
+      if (digest256_from_base64(router->extra_info_digest256, tok->args[1])
+          < 0) {
+        log_warn(LD_DIR, "Invalid extra info digest256 %s",
+                 escaped(tok->args[1]));
+      }
+    }
   }
 
   if (find_opt_by_keyword(tokens, K_HIDDEN_SERVICE_DIR)) {
@@ -1437,6 +1611,7 @@ router_parse_entry_from_string(const char *s, const char *end,
   routerinfo_free(router);
   router = NULL;
  done:
+  tor_cert_free(ntor_cc_cert);
   if (tokens) {
     SMARTLIST_FOREACH(tokens, directory_token_t *, t, token_clear(t));
     smartlist_free(tokens);
@@ -1503,6 +1678,7 @@ extrainfo_parse_entry_from_string(const char *s, const char *end,
     goto err;
   }
 
+  /* XXXX Accept this in position 1 too, and ed identity in position 0. */
   tok = smartlist_get(tokens,0);
   if (tok->tp != K_EXTRA_INFO) {
     log_warn(LD_DIR,"Entry does not start with \"extra-info\"");
@@ -1515,6 +1691,7 @@ extrainfo_parse_entry_from_string(const char *s, const char *end,
     extrainfo->cache_info.signed_descriptor_body = tor_memdup_nulterm(s,end-s);
   extrainfo->cache_info.signed_descriptor_len = end-s;
   memcpy(extrainfo->cache_info.signed_descriptor_digest, digest, DIGEST_LEN);
+  crypto_digest256((char*)extrainfo->digest256, s, end-s, DIGEST_SHA256);
 
   tor_assert(tok->n_args >= 2);
   if (!is_legal_nickname(tok->args[0])) {
@@ -1537,6 +1714,87 @@ extrainfo_parse_entry_from_string(const char *s, const char *end,
     goto err;
   }
 
+  {
+    directory_token_t *ed_sig_tok, *ed_cert_tok;
+    ed_sig_tok = find_opt_by_keyword(tokens, K_ROUTER_SIG_ED25519);
+    ed_cert_tok = find_opt_by_keyword(tokens, K_IDENTITY_ED25519);
+    int n_ed_toks = !!ed_sig_tok + !!ed_cert_tok;
+    if (n_ed_toks != 0 && n_ed_toks != 2) {
+      log_warn(LD_DIR, "Router descriptor with only partial ed25519/"
+               "cross-certification support");
+      goto err;
+    }
+    if (ed_sig_tok) {
+      tor_assert(ed_cert_tok);
+      const int ed_cert_token_pos = smartlist_pos(tokens, ed_cert_tok);
+      if (ed_cert_token_pos != 1) {
+        /* Accept this in position 0 XXXX */
+        log_warn(LD_DIR, "Ed25519 certificate in wrong position");
+        goto err;
+      }
+      if (ed_sig_tok != smartlist_get(tokens, smartlist_len(tokens)-2)) {
+        log_warn(LD_DIR, "Ed25519 signature in wrong position");
+        goto err;
+      }
+      if (strcmp(ed_cert_tok->object_type, "ED25519 CERT")) {
+        log_warn(LD_DIR, "Wrong object type on identity-ed25519 in decriptor");
+        goto err;
+      }
+
+      uint8_t d256[DIGEST256_LEN];
+      const char *signed_start, *signed_end;
+      tor_cert_t *cert = tor_cert_parse(
+                       (const uint8_t*)ed_cert_tok->object_body,
+                       ed_cert_tok->object_size);
+      if (! cert) {
+        log_warn(LD_DIR, "Couldn't parse ed25519 cert");
+        goto err;
+      }
+      extrainfo->signing_key_cert = cert; /* makes sure it gets freed. */
+      if (cert->cert_type != CERT_TYPE_ID_SIGNING ||
+          ! cert->signing_key_included) {
+        log_warn(LD_DIR, "Invalid form for ed25519 cert");
+        goto err;
+      }
+
+      if (router_get_hash_impl_helper(s, end-s, "extra-info ",
+                                      "\nrouter-sig-ed25519",
+                                      ' ', &signed_start, &signed_end) < 0) {
+        log_warn(LD_DIR, "Can't find ed25519-signed portion of extrainfo");
+        goto err;
+      }
+      crypto_digest_t *d = crypto_digest256_new(DIGEST_SHA256);
+      crypto_digest_add_bytes(d, ED_DESC_SIGNATURE_PREFIX,
+        strlen(ED_DESC_SIGNATURE_PREFIX));
+      crypto_digest_add_bytes(d, signed_start, signed_end-signed_start);
+      crypto_digest_get_digest(d, (char*)d256, sizeof(d256));
+      crypto_digest_free(d);
+
+      ed25519_checkable_t check[2];
+      int check_ok[2];
+      if (tor_cert_get_checkable_sig(&check[0], cert, NULL) < 0) {
+        log_err(LD_BUG, "Couldn't create 'checkable' for cert.");
+        goto err;
+      }
+
+      if (ed25519_signature_from_base64(&check[1].signature,
+                                        ed_sig_tok->args[0])<0) {
+        log_warn(LD_DIR, "Couldn't decode ed25519 signature");
+        goto err;
+      }
+      check[1].pubkey = &cert->signed_key;
+      check[1].msg = d256;
+      check[1].len = DIGEST256_LEN;
+
+      if (ed25519_checksig_batch(check_ok, check, 2) < 0) {
+        log_warn(LD_DIR, "Incorrect ed25519 signature(s)");
+        goto err;
+      }
+      /* We don't check the certificate expiration time: checking that it
+       * matches the cert in the router descriptor is adequate. */
+    }
+  }
+
   /* We've checked everything that's covered by the hash. */
   can_dl_again = 1;
 
@@ -2089,6 +2347,17 @@ routerstatus_parse_entry_from_string(memarea_t *area,
         line->microdesc_hash_line = tor_strdup(t->args[0]);
         vote_rs->microdesc = line;
       }
+      if (t->tp == K_ID) {
+        tor_assert(t->n_args >= 2);
+        if (!strcmp(t->args[0], "ed25519")) {
+          vote_rs->has_ed25519_listing = 1;
+          if (strcmp(t->args[1], "none") &&
+              digest256_from_base64((char*)vote_rs->ed25519_id, t->args[1])<0) {
+            log_warn(LD_DIR, "Bogus ed25519 key in networkstatus vote");
+            goto err;
+          }
+        }
+      }
     } SMARTLIST_FOREACH_END(t);
   } else if (flav == FLAV_MICRODESC) {
     tok = find_opt_by_keyword(tokens, K_M);
@@ -2913,6 +3182,21 @@ networkstatus_parse_vote_from_string(const char *s, const char **eos_out,
       goto err;
     }
   }
+  if (ns_type != NS_TYPE_CONSENSUS) {
+    digest256map_t *ed_id_map = digest256map_new();
+    SMARTLIST_FOREACH_BEGIN(ns->routerstatus_list, vote_routerstatus_t *, vrs) {
+      if (! vrs->has_ed25519_listing ||
+          tor_mem_is_zero((const char *)vrs->ed25519_id, DIGEST256_LEN))
+        continue;
+      if (digest256map_get(ed_id_map, vrs->ed25519_id) != NULL) {
+        log_warn(LD_DIR, "Vote networkstatus ed25519 identities were not "
+                 "unique");
+        goto err;
+      }
+      digest256map_set(ed_id_map, vrs->ed25519_id, (void*)1);
+    } SMARTLIST_FOREACH_END(vrs);
+    digest256map_free(ed_id_map, NULL);
+  }
 
   /* Parse footer; check signature. */
   footer_tokens = smartlist_new();
@@ -4210,6 +4494,26 @@ microdescs_parse_from_string(const char *s, const char *eos,
         tor_memdup(&k, sizeof(curve25519_public_key_t));
     }
 
+    smartlist_t *id_lines = find_all_by_keyword(tokens, K_ID);
+    if (id_lines) {
+      SMARTLIST_FOREACH_BEGIN(id_lines, directory_token_t *, t) {
+        tor_assert(t->n_args >= 2);
+        if (!strcmp(t->args[0], "ed25519")) {
+          if (md->ed25519_identity_pkey) {
+            log_warn(LD_DIR, "Extra ed25519 key in microdesc");
+            goto next;
+          }
+          ed25519_public_key_t k;
+          if (ed25519_public_from_base64(&k, t->args[1])<0) {
+            log_warn(LD_DIR, "Bogus ed25519 key in microdesc");
+            goto next;
+          }
+          md->ed25519_identity_pkey = tor_memdup(&k, sizeof(k));
+        }
+      } SMARTLIST_FOREACH_END(t);
+      smartlist_free(id_lines);
+    }
+
     {
       smartlist_t *a_lines = find_all_by_keyword(tokens, K_A);
       if (a_lines) {
diff --git a/src/or/routerparse.h b/src/or/routerparse.h
index e294d95391..85e4b7d88e 100644
--- a/src/or/routerparse.h
+++ b/src/or/routerparse.h
@@ -19,7 +19,7 @@ int router_get_extrainfo_hash(const char *s, size_t s_len, char *digest);
 #define DIROBJ_MAX_SIG_LEN 256
 char *router_get_dirobj_signature(const char *digest,
                                   size_t digest_len,
-                                  crypto_pk_t *private_key);
+                                  const crypto_pk_t *private_key);
 int router_append_dirobj_signature(char *buf, size_t buf_len,
                                    const char *digest,
                                    size_t digest_len,
@@ -91,5 +91,7 @@ STATIC int routerstatus_parse_guardfraction(const char *guardfraction_str,
                                             routerstatus_t *rs);
 #endif
 
+#define ED_DESC_SIGNATURE_PREFIX "Tor router descriptor signature v1"
+
 #endif
 
diff --git a/src/or/torcert.c b/src/or/torcert.c
new file mode 100644
index 0000000000..e2ddffd7a9
--- /dev/null
+++ b/src/or/torcert.c
@@ -0,0 +1,280 @@
+/* Copyright (c) 2014, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#include "crypto.h"
+#include "torcert.h"
+#include "ed25519_cert.h"
+#include "torlog.h"
+#include "util.h"
+#include "compat.h"
+#include "link_handshake.h"
+
+/** Helper for tor_cert_create(): signs any 32 bytes, not just an ed25519
+ * key.
+ */
+static tor_cert_t *
+tor_cert_sign_impl(const ed25519_keypair_t *signing_key,
+                      uint8_t cert_type,
+                      uint8_t signed_key_type,
+                      const uint8_t signed_key_info[32],
+                      time_t now, time_t lifetime,
+                      uint32_t flags)
+{
+  tor_cert_t *torcert = NULL;
+
+  ed25519_cert_t *cert = ed25519_cert_new();
+  cert->cert_type = cert_type;
+  cert->exp_field = (uint32_t) CEIL_DIV(now + lifetime, 3600);
+  cert->cert_key_type = signed_key_type;
+  memcpy(cert->certified_key, signed_key_info, 32);
+
+  if (flags & CERT_FLAG_INCLUDE_SIGNING_KEY) {
+    ed25519_cert_extension_t *ext = ed25519_cert_extension_new();
+    ext->ext_type = CERTEXT_SIGNED_WITH_KEY;
+    memcpy(ext->un_signing_key, signing_key->pubkey.pubkey, 32);
+    ed25519_cert_add_ext(cert, ext);
+    ++cert->n_extensions;
+  }
+
+  const ssize_t alloc_len = ed25519_cert_encoded_len(cert);
+  tor_assert(alloc_len > 0);
+  uint8_t *encoded = tor_malloc(alloc_len);
+  const ssize_t real_len = ed25519_cert_encode(encoded, alloc_len, cert);
+  if (real_len < 0)
+    goto err;
+  tor_assert(real_len == alloc_len);
+  tor_assert(real_len > ED25519_SIG_LEN);
+  uint8_t *sig = encoded + (real_len - ED25519_SIG_LEN);
+  tor_assert(tor_mem_is_zero((char*)sig, ED25519_SIG_LEN));
+
+  ed25519_signature_t signature;
+  if (ed25519_sign(&signature, encoded,
+                   real_len-ED25519_SIG_LEN, signing_key)<0) {
+    log_warn(LD_BUG, "Can't sign certificate");
+    goto err;
+  }
+  memcpy(sig, signature.sig, ED25519_SIG_LEN);
+
+  torcert = tor_cert_parse(encoded, real_len);
+  if (! torcert) {
+    log_warn(LD_BUG, "Generated a certificate we cannot parse");
+    goto err;
+  }
+
+  if (tor_cert_checksig(torcert, &signing_key->pubkey, now) < 0) {
+    log_warn(LD_BUG, "Generated a certificate whose signature we can't check");
+    goto err;
+  }
+
+  tor_free(encoded);
+
+  return torcert;
+
+ err:
+  tor_cert_free(torcert);
+  ed25519_cert_free(cert);
+  tor_free(encoded);
+  return NULL;
+}
+
+/**
+ * Create and return a new new certificate of type <b>cert_type</b> to
+ * authenticate <b>signed_key</b> using the key <b>signing_key</b>.  The
+ * certificate should remain valid for at least <b>lifetime</b> seconds after
+ * <b>now</b>.
+ *
+ * If CERT_FLAG_INCLUDE_SIGNING_KEY is set in <b>flags</b>, embed
+ * the public part of <b>signing_key</b> in the certificate.
+ */
+tor_cert_t *
+tor_cert_create(const ed25519_keypair_t *signing_key,
+                uint8_t cert_type,
+                const ed25519_public_key_t *signed_key,
+                time_t now, time_t lifetime,
+                uint32_t flags)
+{
+  return tor_cert_sign_impl(signing_key, cert_type,
+                            SIGNED_KEY_TYPE_ED25519, signed_key->pubkey,
+                            now, lifetime, flags);
+}
+
+/** Release all storage held for <b>cert</>. */
+void
+tor_cert_free(tor_cert_t *cert)
+{
+  if (! cert)
+    return;
+
+  if (cert->encoded)
+    memwipe(cert->encoded, 0, cert->encoded_len);
+  tor_free(cert->encoded);
+
+  memwipe(cert, 0, sizeof(tor_cert_t));
+  tor_free(cert);
+}
+
+/** Parse a certificate encoded with <b>len</b> bytes in <b>encoded</b>. */
+tor_cert_t *
+tor_cert_parse(const uint8_t *encoded, const size_t len)
+{
+  tor_cert_t *cert = NULL;
+  ed25519_cert_t *parsed = NULL;
+  ssize_t got_len = ed25519_cert_parse(&parsed, encoded, len);
+  if (got_len < 0 || (size_t) got_len != len)
+    goto err;
+
+  cert = tor_malloc_zero(sizeof(tor_cert_t));
+  cert->encoded = tor_memdup(encoded, len);
+  cert->encoded_len = len;
+
+  memcpy(cert->signed_key.pubkey, parsed->certified_key, 32);
+  cert->valid_until = parsed->exp_field * 3600;
+  cert->cert_type = parsed->cert_type;
+
+  for (unsigned i = 0; i < ed25519_cert_getlen_ext(parsed); ++i) {
+    ed25519_cert_extension_t *ext = ed25519_cert_get_ext(parsed, i);
+    if (ext->ext_type == CERTEXT_SIGNED_WITH_KEY) {
+      if (cert->signing_key_included)
+        goto err;
+
+      cert->signing_key_included = 1;
+      memcpy(cert->signing_key.pubkey, ext->un_signing_key, 32);
+    } else if (ext->ext_flags & CERTEXT_FLAG_AFFECTS_VALIDATION) {
+      /* Unrecognized extension with affects_validation set */
+      goto err;
+    }
+  }
+
+  return cert;
+ err:
+  ed25519_cert_free(parsed);
+  tor_cert_free(cert);
+  return NULL;
+}
+
+/** Fill in <b>checkable_out</b> with the information needed to check
+ * the signature on <b>cert</b> with <b>pubkey</b>. */
+int
+tor_cert_get_checkable_sig(ed25519_checkable_t *checkable_out,
+                           const tor_cert_t *cert,
+                           const ed25519_public_key_t *pubkey)
+{
+  if (! pubkey) {
+    if (cert->signing_key_included)
+      pubkey = &cert->signing_key;
+    else
+      return -1;
+  }
+
+  checkable_out->msg = cert->encoded;
+  checkable_out->pubkey = pubkey;
+  tor_assert(cert->encoded_len > ED25519_SIG_LEN);
+  const size_t signed_len = cert->encoded_len - ED25519_SIG_LEN;
+  checkable_out->len = signed_len;
+  memcpy(checkable_out->signature.sig,
+         cert->encoded + signed_len, ED25519_SIG_LEN);
+
+  return 0;
+}
+
+/** Validates the signature on <b>cert</b> with <b>pubkey</b> relative to
+ * the current time <b>now</b>.  Return 0 on success, -1 on failure.
+ * Sets flags in <b>cert</b> as appropriate.
+ */
+int
+tor_cert_checksig(tor_cert_t *cert,
+                  const ed25519_public_key_t *pubkey, time_t now)
+{
+  ed25519_checkable_t checkable;
+  int okay;
+
+  if (now > cert->valid_until) {
+    cert->cert_expired = 1;
+    return -1;
+  }
+
+  if (tor_cert_get_checkable_sig(&checkable, cert, pubkey) < 0)
+    return -1;
+
+  if (ed25519_checksig_batch(&okay, &checkable, 1) < 0) {
+    cert->sig_bad = 1;
+    return -1;
+  } else {
+    cert->sig_ok = 1;
+    memcpy(cert->signing_key.pubkey, checkable.pubkey->pubkey, 32);
+    cert->cert_valid = 1;
+    return 0;
+  }
+}
+
+/** Return a new copy of <b>cert</b> */
+tor_cert_t *
+tor_cert_dup(const tor_cert_t *cert)
+{
+  tor_cert_t *newcert = tor_memdup(cert, sizeof(tor_cert_t));
+  if (cert->encoded)
+    newcert->encoded = tor_memdup(cert->encoded, cert->encoded_len);
+  return newcert;
+}
+
+/** Return true iff cert1 and cert2 are the same cert. */
+int
+tor_cert_eq(const tor_cert_t *cert1, const tor_cert_t *cert2)
+{
+  tor_assert(cert1);
+  tor_assert(cert2);
+  return cert1->encoded_len == cert2->encoded_len &&
+    tor_memeq(cert1->encoded, cert2->encoded, cert1->encoded_len);
+}
+
+/** Return true iff cert1 and cert2 are the same cert, or if they are both
+ * NULL. */
+int
+tor_cert_opt_eq(const tor_cert_t *cert1, const tor_cert_t *cert2)
+{
+  if (cert1 == NULL && cert2 == NULL)
+    return 1;
+  if (!cert1 || !cert2)
+    return 0;
+  return tor_cert_eq(cert1, cert2);
+}
+
+/** Create new cross-certification object to certify <b>ed_key</b> as the
+ * master ed25519 identity key for the RSA identity key <b>rsa_key</b>.
+ * Allocates and stores the encoded certificate in *<b>cert</b>, and returns
+ * the number of bytes stored. Returns negative on error.*/
+ssize_t
+tor_make_rsa_ed25519_crosscert(const ed25519_public_key_t *ed_key,
+                               const crypto_pk_t *rsa_key,
+                               time_t expires,
+                               uint8_t **cert)
+{
+  uint8_t *res;
+
+  rsa_ed_crosscert_t *cc = rsa_ed_crosscert_new();
+  memcpy(cc->ed_key, ed_key->pubkey, ED25519_PUBKEY_LEN);
+  cc->expiration = (uint32_t) CEIL_DIV(expires, 3600);
+  cc->sig_len = crypto_pk_keysize(rsa_key);
+  rsa_ed_crosscert_setlen_sig(cc, crypto_pk_keysize(rsa_key));
+
+  ssize_t alloc_sz = rsa_ed_crosscert_encoded_len(cc);
+  tor_assert(alloc_sz > 0);
+  res = tor_malloc_zero(alloc_sz);
+  ssize_t sz = rsa_ed_crosscert_encode(res, alloc_sz, cc);
+  tor_assert(sz > 0 && sz <= alloc_sz);
+
+  const int signed_part_len = 32 + 4;
+  int siglen = crypto_pk_private_sign(rsa_key,
+                                      (char*)rsa_ed_crosscert_getarray_sig(cc),
+                                      rsa_ed_crosscert_getlen_sig(cc),
+                                      (char*)res, signed_part_len);
+  tor_assert(siglen > 0 && siglen <= (int)crypto_pk_keysize(rsa_key));
+  tor_assert(siglen <= UINT8_MAX);
+  cc->sig_len = siglen;
+  rsa_ed_crosscert_setlen_sig(cc, siglen);
+
+  sz = rsa_ed_crosscert_encode(res, alloc_sz, cc);
+  rsa_ed_crosscert_free(cc);
+  *cert = res;
+  return sz;
+}
diff --git a/src/or/torcert.h b/src/or/torcert.h
new file mode 100644
index 0000000000..b67dc525a2
--- /dev/null
+++ b/src/or/torcert.h
@@ -0,0 +1,76 @@
+/* Copyright (c) 2014, The Tor Project, Inc. */
+/* See LICENSE for licensing information */
+
+#ifndef TORCERT_H_INCLUDED
+#define TORCERT_H_INCLUDED
+
+#include "crypto_ed25519.h"
+
+#define SIGNED_KEY_TYPE_ED25519 0x01
+
+#define CERT_TYPE_ID_SIGNING    0x04
+#define CERT_TYPE_SIGNING_LINK  0x05
+#define CERT_TYPE_SIGNING_AUTH  0x06
+#define CERT_TYPE_ONION_ID      0x0A
+
+#define CERT_FLAG_INCLUDE_SIGNING_KEY 0x1
+
+/** An ed25519-signed certificate as used throughout the Tor protocol.
+ **/
+typedef struct tor_cert_st {
+  /** The key authenticated by this certificate */
+  ed25519_public_key_t signed_key;
+  /** The key that signed this certificate. This value may be unset if the
+   * certificate has never been checked, and didn't include its own key. */
+  ed25519_public_key_t signing_key;
+  /** A time after which this certificate will no longer be valid. */
+  time_t valid_until;
+
+  /** The encoded representation of this certificate */
+  uint8_t *encoded;
+  /** The length of <b>encoded</b> */
+  size_t encoded_len;
+
+  /** One of CERT_TYPE_... */
+  uint8_t cert_type;
+  /** True iff we received a signing key embedded in this certificate */
+  unsigned signing_key_included : 1;
+  /** True iff we checked the signature and found it bad */
+  unsigned sig_bad : 1;
+  /** True iff we checked the signature and found it correct */
+  unsigned sig_ok : 1;
+  /** True iff we checked the signature and first found that the cert
+   * had expired */
+  unsigned cert_expired : 1;
+  /** True iff we checked the signature and found the whole cert valid */
+  unsigned cert_valid : 1;
+} tor_cert_t;
+
+tor_cert_t *tor_cert_create(const ed25519_keypair_t *signing_key,
+                            uint8_t cert_type,
+                            const ed25519_public_key_t *signed_key,
+                            time_t now, time_t lifetime,
+                            uint32_t flags);
+
+tor_cert_t *tor_cert_parse(const uint8_t *cert, size_t certlen);
+
+void tor_cert_free(tor_cert_t *cert);
+
+int tor_cert_get_checkable_sig(ed25519_checkable_t *checkable_out,
+                                 const tor_cert_t *out,
+                                 const ed25519_public_key_t *pubkey);
+
+int tor_cert_checksig(tor_cert_t *cert,
+                      const ed25519_public_key_t *pubkey, time_t now);
+
+tor_cert_t *tor_cert_dup(const tor_cert_t *cert);
+int tor_cert_eq(const tor_cert_t *cert1, const tor_cert_t *cert2);
+int tor_cert_opt_eq(const tor_cert_t *cert1, const tor_cert_t *cert2);
+
+ssize_t tor_make_rsa_ed25519_crosscert(const ed25519_public_key_t *ed_key,
+                                       const crypto_pk_t *rsa_key,
+                                       time_t expires,
+                                       uint8_t **cert);
+
+#endif
+