Merge branch 'feature15056_v1_squashed'

35 files changed, 2290 insertions, 348 deletions

diff --git a/changes/feature15056 b/changes/feature15056
new file mode 100644
index 0000000000..46226f881f
--- /dev/null
+++ b/changes/feature15056
@@ -0,0 +1,28 @@
+  o Major features (ed25519 identity keys):
+    - Relays now understand requests to extend to other relays
+      by their Ed25519 identity keys. When an Ed25519 identity key
+      is included in an EXTEND2 cell, the relay will only extend
+      the circuit if the other relay can prove ownership of that identity.
+      Implements part of ticket 15056; part of proposal 220.
+    - Clients now support including Ed25519 identity keys in the EXTEND2
+      cells they generate.  By default, this is controlled by a consensus
+      parameter, currently disabled.  You can turn this feature on for
+      testing by setting ExtendByEd25519ID in your configuration. This might
+      make your traffic appear different than the traffic generated by other
+      users, however.
+      Implements part of ticket 15056; part of proposal 220.
+
+  o Code simplification and refactoring:
+    - The code to generate and parse EXTEND and EXTEND2 cells has
+      been replaced with code automatically generated by the "trunnel"
+      utility.
+    - Remove data structures that were used to index or_connection objects by
+      their RSA identity digests. These structures are fully redundant with
+      the similar structures used in the channel abstraction.
+
+  o Minor features (directory authority):
+    - Add a new authority-only AuthDirTestEd25519LinkKeys option (on by
+      default) to control whether authorities should try to probe relays by
+      their Ed25519 link keys.  This option will go away in a few
+      releases--unless we encounter major trouble in our ed25519 link
+      protocol rollout, in which case it will serve as a safety option.
diff --git a/doc/tor.1.txt b/doc/tor.1.txt
index c4219d96b0..9b8a0f00bf 100644
--- a/doc/tor.1.txt
+++ b/doc/tor.1.txt
@@ -719,6 +719,13 @@ GENERAL OPTIONS
     127.0.0.1 or 10.0.0.1.  This is mostly useful for debugging
     rate-limiting.  (Default: 0)
 
+[[ExtendByEd25519ID]] **ExtendByEd25519ID** **0**|**1**|**auto**::
+    If this option is set to 1, we always try to include a relay's Ed25519 ID
+    when telling the proceeding relay in a circuit to extend to it.
+    If this option is set to 0, we never include Ed25519 IDs when extending
+    circuits.  If the option is set to "default", we obey a
+    parameter in the consensus document. (Default: auto)
+
 CLIENT OPTIONS
 --------------
 
@@ -2266,6 +2273,13 @@ on the public Tor network.
     (default), the flag "shared-rand-participate" is added to the authority
     vote indicating participation in the protocol. (Default: 1)
 
+[[AuthDirTestEd25519LinkKeys]] **AuthDirTestEd25519LinkKeys**  **0**|**1**::
+    Authoritative directories only. If this option is set to 0, then we treat
+    relays as "Running" if their RSA key is correct when we probe them,
+    regardless of their Ed25519 key. We should only ever set this option to 0
+    if there is some major bug in Ed25519 link authentication that causes us
+    to label all the relays as not Running.  (Default: 1)
+
 [[BridgePassword]] **BridgePassword** __Password__::
     If set, contains an HTTP authenticator that tells a bridge authority to
     serve all requested bridge information. Used by the (only partially
diff --git a/src/common/crypto_ed25519.c b/src/common/crypto_ed25519.c
index 30ed772274..b7c8311475 100644
--- a/src/common/crypto_ed25519.c
+++ b/src/common/crypto_ed25519.c
@@ -211,6 +211,14 @@ ed25519_keypair_generate(ed25519_keypair_t *keypair_out, int extra_strong)
   return 0;
 }
 
+/** Return true iff 'pubkey' is set to zero (eg to indicate that it is not
+ * set). */
+int
+ed25519_public_key_is_zero(const ed25519_public_key_t *pubkey)
+{
+  return tor_mem_is_zero((char*)pubkey->pubkey, ED25519_PUBKEY_LEN);
+}
+
 /* Return a heap-allocated array that contains <b>msg</b> prefixed by the
  * string <b>prefix_str</b>. Set <b>final_msg_len_out</b> to the size of the
  * final array. If an error occured, return NULL. It's the resonsibility of the
@@ -620,6 +628,18 @@ ed25519_pubkey_eq(const ed25519_public_key_t *key1,
   return tor_memeq(key1->pubkey, key2->pubkey, ED25519_PUBKEY_LEN);
 }
 
+/**
+ * Set <b>dest</b> to contain the same key as <b>src</b>.
+ */
+void
+ed25519_pubkey_copy(ed25519_public_key_t *dest,
+                    const ed25519_public_key_t *src)
+{
+  tor_assert(dest);
+  tor_assert(src);
+  memcpy(dest, src, sizeof(ed25519_public_key_t));
+}
+
 /** Check whether the given Ed25519 implementation seems to be working.
  * If so, return 0; otherwise return -1. */
 static int
diff --git a/src/common/crypto_ed25519.h b/src/common/crypto_ed25519.h
index 31afc49ccc..929b2b51dd 100644
--- a/src/common/crypto_ed25519.h
+++ b/src/common/crypto_ed25519.h
@@ -66,6 +66,9 @@ ed25519_checksig_prefixed(const ed25519_signature_t *signature,
                           const char *prefix_str,
                           const ed25519_public_key_t *pubkey);
 
+int ed25519_public_key_is_zero(const ed25519_public_key_t *pubkey);
+
+
 /**
  * A collection of information necessary to check an Ed25519 signature. Used
  * for batch verification.
@@ -118,6 +121,9 @@ void ed25519_keypair_free(ed25519_keypair_t *kp);
 
 int ed25519_pubkey_eq(const ed25519_public_key_t *key1,
                       const ed25519_public_key_t *key2);
+void ed25519_pubkey_copy(ed25519_public_key_t *dest,
+                         const ed25519_public_key_t *src);
+
 
 void ed25519_set_impl_params(int use_donna);
 void ed25519_init(void);
diff --git a/src/common/crypto_format.c b/src/common/crypto_format.c
index 2f6d847c83..483013ee68 100644
--- a/src/common/crypto_format.c
+++ b/src/common/crypto_format.c
@@ -161,6 +161,22 @@ curve25519_public_from_base64(curve25519_public_key_t *pkey,
   }
 }
 
+/** For convenience: Convert <b>pkey</b> to a statically allocated base64
+ * string and return it. Not threadsafe. Subsequent calls invalidate
+ * previous returns. */
+const char *
+ed25519_fmt(const ed25519_public_key_t *pkey)
+{
+  static char formatted[ED25519_BASE64_LEN+1];
+  if (pkey) {
+    int r = ed25519_public_to_base64(formatted, pkey);
+    tor_assert(!r);
+  } else {
+    strlcpy(formatted, "<null>", sizeof(formatted));
+  }
+  return formatted;
+}
+
 /** Try to decode the string <b>input</b> into an ed25519 public key. On
  * success, store the value in <b>pkey</b> and return 0. Otherwise return
  * -1. */
diff --git a/src/common/crypto_format.h b/src/common/crypto_format.h
index 012e228cc4..86c29d319c 100644
--- a/src/common/crypto_format.h
+++ b/src/common/crypto_format.h
@@ -28,6 +28,7 @@ int ed25519_public_from_base64(ed25519_public_key_t *pkey,
                                const char *input);
 int ed25519_public_to_base64(char *output,
                              const ed25519_public_key_t *pkey);
+const char *ed25519_fmt(const ed25519_public_key_t *pkey);
 
 /* XXXX move these to crypto_format.h */
 #define ED25519_SIG_BASE64_LEN 86
diff --git a/src/or/channel.c b/src/or/channel.c
index af5810788c..7984558b40 100644
--- a/src/or/channel.c
+++ b/src/or/channel.c
@@ -733,27 +733,62 @@ channel_find_by_global_id(uint64_t global_identifier)
   return rv;
 }
 
+/** Return true iff <b>chan</b> matches <b>rsa_id_digest</b> and <b>ed_id</b>.
+ * as its identity keys.  If either is NULL, do not check for a match. */
+static int
+channel_remote_identity_matches(const channel_t *chan,
+                                const char *rsa_id_digest,
+                                const ed25519_public_key_t *ed_id)
+{
+  if (BUG(!chan))
+    return 0;
+  if (rsa_id_digest) {
+    if (tor_memneq(rsa_id_digest, chan->identity_digest, DIGEST_LEN))
+      return 0;
+  }
+  if (ed_id) {
+    if (tor_memneq(ed_id->pubkey, chan->ed25519_identity.pubkey,
+                   ED25519_PUBKEY_LEN))
+      return 0;
+  }
+  return 1;
+}
+
 /**
- * Find channel by digest of the remote endpoint
+ * Find channel by RSA/Ed25519 identity of of the remote endpoint
+ *
+ * This function looks up a channel by the digest of its remote endpoint's RSA
+ * identity key.  If <b>ed_id</b> is provided and nonzero, only a channel
+ * matching the <b>ed_id</b> will be returned.
  *
- * This function looks up a channel by the digest of its remote endpoint in
- * the channel digest map.  It's possible that more than one channel to a
- * given endpoint exists.  Use channel_next_with_digest() to walk the list.
+ * It's possible that more than one channel to a given endpoint exists.  Use
+ * channel_next_with_rsa_identity() to walk the list of channels; make sure
+ * to test for Ed25519 identity match too (as appropriate)
  */
-
 channel_t *
-channel_find_by_remote_digest(const char *identity_digest)
+channel_find_by_remote_identity(const char *rsa_id_digest,
+                                const ed25519_public_key_t *ed_id)
 {
   channel_t *rv = NULL;
   channel_idmap_entry_t *ent, search;
 
-  tor_assert(identity_digest);
+  tor_assert(rsa_id_digest); /* For now, we require that every channel have
+                              * an RSA identity, and that every lookup
+                              * contain an RSA identity */
+  if (ed_id && ed25519_public_key_is_zero(ed_id)) {
+    /* Treat zero as meaning "We don't care about the presence or absence of
+     * an Ed key", not "There must be no Ed key". */
+    ed_id = NULL;
+  }
 
-  memcpy(search.digest, identity_digest, DIGEST_LEN);
+  memcpy(search.digest, rsa_id_digest, DIGEST_LEN);
   ent = HT_FIND(channel_idmap, &channel_identity_map, &search);
   if (ent) {
     rv = TOR_LIST_FIRST(&ent->channel_list);
   }
+  while (rv && ! channel_remote_identity_matches(rv, rsa_id_digest, ed_id)) {
+    rv = channel_next_with_rsa_identity(rv);
+  }
 
   return rv;
 }
@@ -766,7 +801,7 @@ channel_find_by_remote_digest(const char *identity_digest)
  */
 
 channel_t *
-channel_next_with_digest(channel_t *chan)
+channel_next_with_rsa_identity(channel_t *chan)
 {
   tor_assert(chan);
 
@@ -1433,10 +1468,10 @@ channel_clear_identity_digest(channel_t *chan)
  * This function sets the identity digest of the remote endpoint for a
  * channel; this is intended for use by the lower layer.
  */
-
 void
 channel_set_identity_digest(channel_t *chan,
-                            const char *identity_digest)
+                            const char *identity_digest,
+                            const ed25519_public_key_t *ed_identity)
 {
   int was_in_digest_map, should_be_in_digest_map, state_not_in_map;
 
@@ -1475,6 +1510,11 @@ channel_set_identity_digest(channel_t *chan,
     memset(chan->identity_digest, 0,
            sizeof(chan->identity_digest));
   }
+  if (ed_identity) {
+    memcpy(&chan->ed25519_identity, ed_identity, sizeof(*ed_identity));
+  } else {
+    memset(&chan->ed25519_identity, 0, sizeof(*ed_identity));
+  }
 
   /* Put it in the digest map if we should */
   if (should_be_in_digest_map)
@@ -3296,7 +3336,8 @@ channel_is_better(time_t now, channel_t *a, channel_t *b,
  */
 
 channel_t *
-channel_get_for_extend(const char *digest,
+channel_get_for_extend(const char *rsa_id_digest,
+                       const ed25519_public_key_t *ed_id,
                        const tor_addr_t *target_addr,
                        const char **msg_out,
                        int *launch_out)
@@ -3309,14 +3350,14 @@ channel_get_for_extend(const char *digest,
   tor_assert(msg_out);
   tor_assert(launch_out);
 
-  chan = channel_find_by_remote_digest(digest);
+  chan = channel_find_by_remote_identity(rsa_id_digest, ed_id);
 
   /* Walk the list, unrefing the old one and refing the new at each
    * iteration.
    */
-  for (; chan; chan = channel_next_with_digest(chan)) {
+  for (; chan; chan = channel_next_with_rsa_identity(chan)) {
     tor_assert(tor_memeq(chan->identity_digest,
-                         digest, DIGEST_LEN));
+                         rsa_id_digest, DIGEST_LEN));
 
    if (CHANNEL_CONDEMNED(chan))
       continue;
@@ -3327,6 +3368,11 @@ channel_get_for_extend(const char *digest,
       continue;
     }
 
+    /* The Ed25519 key has to match too */
+    if (!channel_remote_identity_matches(chan, rsa_id_digest, ed_id)) {
+      continue;
+    }
+
     /* Never return a non-open connection. */
     if (!CHANNEL_IS_OPEN(chan)) {
       /* If the address matches, don't launch a new connection for this
@@ -4498,6 +4544,81 @@ channel_set_circid_type,(channel_t *chan,
   }
 }
 
+/** Helper for channel_update_bad_for_new_circs(): Perform the
+ * channel_update_bad_for_new_circs operation on all channels in <b>lst</b>,
+ * all of which MUST have the same RSA ID.  (They MAY have different
+ * Ed25519 IDs.) */
+static void
+channel_rsa_id_group_set_badness(struct channel_list_s *lst, int force)
+{
+  /*XXXX This function should really be about channels. 15056 */
+  channel_t *chan;
+
+  /* First, get a minimal list of the ed25519 identites */
+  smartlist_t *ed_identities = smartlist_new();
+  TOR_LIST_FOREACH(chan, lst, next_with_same_id) {
+    uint8_t *id_copy =
+      tor_memdup(&chan->ed25519_identity.pubkey, DIGEST256_LEN);
+    smartlist_add(ed_identities, id_copy);
+  }
+  smartlist_sort_digests256(ed_identities);
+  smartlist_uniq_digests256(ed_identities);
+
+  /* Now, for each Ed identity, build a smartlist and find the best entry on
+   * it.  */
+  smartlist_t *or_conns = smartlist_new();
+  SMARTLIST_FOREACH_BEGIN(ed_identities, const uint8_t *, ed_id) {
+    TOR_LIST_FOREACH(chan, lst, next_with_same_id) {
+      channel_tls_t *chantls = BASE_CHAN_TO_TLS(chan);
+      if (tor_memneq(ed_id, &chan->ed25519_identity.pubkey, DIGEST256_LEN))
+        continue;
+      or_connection_t *orconn = chantls->conn;
+      if (orconn) {
+        tor_assert(orconn->chan == chantls);
+        smartlist_add(or_conns, orconn);
+      }
+    }
+
+    connection_or_group_set_badness_(or_conns, force);
+    smartlist_clear(or_conns);
+  } SMARTLIST_FOREACH_END(ed_id);
+
+  /* XXXX 15056 we may want to do something special with connections that have
+   * no set Ed25519 identity! */
+
+  smartlist_free(or_conns);
+
+  SMARTLIST_FOREACH(ed_identities, uint8_t *, ed_id, tor_free(ed_id));
+  smartlist_free(ed_identities);
+}
+
+/** Go through all the channels (or if <b>digest</b> is non-NULL, just
+ * the OR connections with that digest), and set the is_bad_for_new_circs
+ * flag based on the rules in connection_or_group_set_badness() (or just
+ * always set it if <b>force</b> is true).
+ */
+void
+channel_update_bad_for_new_circs(const char *digest, int force)
+{
+  if (digest) {
+    channel_idmap_entry_t *ent;
+    channel_idmap_entry_t search;
+    memset(&search, 0, sizeof(search));
+    memcpy(search.digest, digest, DIGEST_LEN);
+    ent = HT_FIND(channel_idmap, &channel_identity_map, &search);
+    if (ent) {
+      channel_rsa_id_group_set_badness(&ent->channel_list, force);
+    }
+    return;
+  }
+
+  /* no digest; just look at everything. */
+  channel_idmap_entry_t **iter;
+  HT_FOREACH(iter, channel_idmap, &channel_identity_map) {
+    channel_rsa_id_group_set_badness(&(*iter)->channel_list, force);
+  }
+}
+
 /**
  * Update the estimated number of bytes queued to transmit for this channel,
  * and notify the scheduler.  The estimate includes both the channel queue and
diff --git a/src/or/channel.h b/src/or/channel.h
index 7e7b2ec899..26aa93b5e2 100644
--- a/src/or/channel.h
+++ b/src/or/channel.h
@@ -153,16 +153,32 @@ struct channel_s {
   int (*write_var_cell)(channel_t *, var_cell_t *);
 
   /**
-   * Hash of the public RSA key for the other side's identity key, or
-   * zeroes if the other side hasn't shown us a valid identity key.
+   * Hash of the public RSA key for the other side's RSA identity key -- or
+   * zeroes if we don't have an RSA identity in mind for the other side, and
+   * it hasn't shown us one.
+   *
+   * Note that this is the RSA identity that we hope the other side has -- not
+   * necessarily its true identity.  Don't believe this identity unless
+   * authentication has happened.
    */
   char identity_digest[DIGEST_LEN];
+  /**
+   * Ed25519 key for the other side of this channel -- or zeroes if we don't
+   * have an Ed25519 identity in mind for the other side, and it hasn't shown
+   * us one.
+   *
+   * Note that this is the identity that we hope the other side has -- not
+   * necessarily its true identity.  Don't believe this identity unless
+   * authentication has happened.
+   */
+  ed25519_public_key_t ed25519_identity;
+
   /** Nickname of the OR on the other side, or NULL if none. */
   char *nickname;
 
   /**
-   * Linked list of channels with the same identity digest, for the
-   * digest->channel map
+   * Linked list of channels with the same RSA identity digest, for use with
+   * the digest->channel map
    */
   TOR_LIST_ENTRY(channel_s) next_with_same_id;
 
@@ -427,7 +443,8 @@ void channel_mark_incoming(channel_t *chan);
 void channel_mark_outgoing(channel_t *chan);
 void channel_mark_remote(channel_t *chan);
 void channel_set_identity_digest(channel_t *chan,
-                                 const char *identity_digest);
+                                 const char *identity_digest,
+                                 const ed25519_public_key_t *ed_identity);
 void channel_set_remote_end(channel_t *chan,
                             const char *identity_digest,
                             const char *nickname);
@@ -489,10 +506,11 @@ int channel_send_destroy(circid_t circ_id, channel_t *chan,
  */
 
 channel_t * channel_connect(const tor_addr_t *addr, uint16_t port,
-                            const char *id_digest,
+                            const char *rsa_id_digest,
                             const ed25519_public_key_t *ed_id);
 
-channel_t * channel_get_for_extend(const char *digest,
+channel_t * channel_get_for_extend(const char *rsa_id_digest,
+                                   const ed25519_public_key_t *ed_id,
                                    const tor_addr_t *target_addr,
                                    const char **msg_out,
                                    int *launch_out);
@@ -506,11 +524,13 @@ int channel_is_better(time_t now,
  */
 
 channel_t * channel_find_by_global_id(uint64_t global_identifier);
-channel_t * channel_find_by_remote_digest(const char *identity_digest);
+channel_t * channel_find_by_remote_identity(const char *rsa_id_digest,
+                                            const ed25519_public_key_t *ed_id);
 
 /** For things returned by channel_find_by_remote_digest(), walk the list.
+ * The RSA key will match for all returned elements; the Ed25519 key might not.
  */
-channel_t * channel_next_with_digest(channel_t *chan);
+channel_t * channel_next_with_rsa_identity(channel_t *chan);
 
 /*
  * Helper macros to lookup state of given channel.
@@ -582,6 +602,8 @@ void channel_listener_dump_statistics(channel_listener_t *chan_l,
 void channel_listener_dump_transport_statistics(channel_listener_t *chan_l,
                                                 int severity);
 
+void channel_update_bad_for_new_circs(const char *digest, int force);
+
 /* Flow control queries */
 uint64_t channel_get_global_queue_estimate(void);
 int channel_num_cells_writeable(channel_t *chan);
diff --git a/src/or/channeltls.c b/src/or/channeltls.c
index 9fb309d0fd..aef0143c9d 100644
--- a/src/or/channeltls.c
+++ b/src/or/channeltls.c
@@ -174,7 +174,6 @@ channel_tls_connect(const tor_addr_t *addr, uint16_t port,
                     const char *id_digest,
                     const ed25519_public_key_t *ed_id)
 {
-  (void) ed_id; // XXXX not fully used yet
   channel_tls_t *tlschan = tor_malloc_zero(sizeof(*tlschan));
   channel_t *chan = &(tlschan->base_);
 
@@ -1652,9 +1651,10 @@ channel_tls_process_netinfo_cell(cell_t *cell, channel_tls_t *chan)
         connection_or_init_conn_from_address(chan->conn,
                   &(chan->conn->base_.addr),
                   chan->conn->base_.port,
+                  /* zero, checked above */
                   (const char*)(chan->conn->handshake_state->
                                 authenticated_rsa_peer_id),
-                  NULL, // XXXX Ed key
+                  NULL, /* Ed25519 ID: Also checked as zero */
                   0);
       }
     }
@@ -1993,12 +1993,15 @@ channel_tls_process_certs_cell(var_cell_t *cell, channel_tls_t *chan)
              checked_ed_id, sizeof(ed25519_public_key_t));
     }
 
+    log_debug(LD_HANDSHAKE, "calling client_learned_peer_id from "
+              "process_certs_cell");
+
     if (connection_or_client_learned_peer_id(chan->conn,
                   chan->conn->handshake_state->authenticated_rsa_peer_id,
                   checked_ed_id) < 0)
       ERR("Problem setting or checking peer id");
 
-    log_info(LD_OR,
+    log_info(LD_HANDSHAKE,
              "Got some good certificates from %s:%d: Authenticated it with "
              "RSA%s",
              safe_str(chan->conn->base_.address), chan->conn->base_.port,
@@ -2334,6 +2337,13 @@ channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
                chan->conn->link_proto < MIN_LINK_PROTO_FOR_WIDE_CIRC_IDS);
     crypto_pk_free(identity_rcvd);
 
+    log_debug(LD_HANDSHAKE,
+              "Calling connection_or_init_conn_from_address for %s "
+              " from %s, with%s ed25519 id.",
+              safe_str(chan->conn->base_.address),
+              __func__,
+              ed_identity_received ? "" : "out");
+
     connection_or_init_conn_from_address(chan->conn,
                   &(chan->conn->base_.addr),
                   chan->conn->base_.port,
@@ -2342,7 +2352,7 @@ channel_tls_process_authenticate_cell(var_cell_t *cell, channel_tls_t *chan)
                   ed_identity_received,
                   0);
 
-    log_info(LD_OR,
+    log_debug(LD_HANDSHAKE,
              "Got an AUTHENTICATE cell from %s:%d, type %d: Looks good.",
              safe_str(chan->conn->base_.address),
              chan->conn->base_.port,
diff --git a/src/or/circuitbuild.c b/src/or/circuitbuild.c
index dee8ac05ff..f60a8bfa89 100644
--- a/src/or/circuitbuild.c
+++ b/src/or/circuitbuild.c
@@ -63,8 +63,9 @@
 #include "transports.h"
 
 static channel_t * channel_connect_for_circuit(const tor_addr_t *addr,
-                                               uint16_t port,
-                                               const char *id_digest);
+                                            uint16_t port,
+                                            const char *id_digest,
+                                            const ed25519_public_key_t *ed_id);
 static int circuit_deliver_create_cell(circuit_t *circ,
                                        const create_cell_t *create_cell,
                                        int relayed);
@@ -80,13 +81,12 @@ static int onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice);
  */
 static channel_t *
 channel_connect_for_circuit(const tor_addr_t *addr, uint16_t port,
-                            const char *id_digest)
+                            const char *id_digest,
+                            const ed25519_public_key_t *ed_id)
 {
   channel_t *chan;
 
-  chan = channel_connect(addr, port, id_digest,
-                         NULL // XXXX Ed25519 id.
-                         );
+  chan = channel_connect(addr, port, id_digest, ed_id);
   if (chan) command_setup_channel(chan);
 
   return chan;
@@ -556,6 +556,7 @@ circuit_handle_first_hop(origin_circuit_t *circ)
                          firsthop->extend_info->port));
 
   n_chan = channel_get_for_extend(firsthop->extend_info->identity_digest,
+                                  &firsthop->extend_info->ed_identity,
                                   &firsthop->extend_info->addr,
                                   &msg,
                                   &should_launch);
@@ -573,7 +574,8 @@ circuit_handle_first_hop(origin_circuit_t *circ)
       n_chan = channel_connect_for_circuit(
           &firsthop->extend_info->addr,
           firsthop->extend_info->port,
-          firsthop->extend_info->identity_digest);
+          firsthop->extend_info->identity_digest,
+          &firsthop->extend_info->ed_identity);
       if (!n_chan) { /* connect failed, forget the whole thing */
         log_info(LD_CIRC,"connect to firsthop failed. Closing.");
         return -END_CIRC_REASON_CONNECTFAILED;
@@ -1041,6 +1043,9 @@ circuit_send_next_onion_skin(origin_circuit_t *circ)
     ec.orport_ipv4.port = hop->extend_info->port;
     tor_addr_make_unspec(&ec.orport_ipv6.addr);
     memcpy(ec.node_id, hop->extend_info->identity_digest, DIGEST_LEN);
+    /* Set the ED25519 identity too -- it will only get included
+     * in the extend2 cell if we're configured to use it, though. */
+    ed25519_pubkey_copy(&ec.ed_pubkey, &hop->extend_info->ed_identity);
 
     len = onion_skin_create(ec.create_cell.handshake_type,
                             hop->extend_info,
@@ -1169,6 +1174,18 @@ circuit_extend(cell_t *cell, circuit_t *circ)
     return -1;
   }
 
+  /* Fill in ed_pubkey if it was not provided and we can infer it from
+   * our networkstatus */
+  if (ed25519_public_key_is_zero(&ec.ed_pubkey)) {
+    const node_t *node = node_get_by_id((const char*)ec.node_id);
+    const ed25519_public_key_t *node_ed_id = NULL;
+    if (node &&
+        node_supports_ed25519_link_authentication(node) &&
+        (node_ed_id = node_get_ed25519_id(node))) {
+      ed25519_pubkey_copy(&ec.ed_pubkey, node_ed_id);
+    }
+  }
+
   /* Next, check if we're being asked to connect to the hop that the
    * extend cell came from. There isn't any reason for that, and it can
    * assist circular-path attacks. */
@@ -1180,7 +1197,17 @@ circuit_extend(cell_t *cell, circuit_t *circ)
     return -1;
   }
 
+  /* Check the previous hop Ed25519 ID too */
+  if (! ed25519_public_key_is_zero(&ec.ed_pubkey) &&
+      ed25519_pubkey_eq(&ec.ed_pubkey,
+                        &TO_OR_CIRCUIT(circ)->p_chan->ed25519_identity)) {
+    log_fn(LOG_PROTOCOL_WARN, LD_PROTOCOL,
+           "Client asked me to extend back to the previous hop "
+           "(by Ed25519 ID).");
+  }
+
   n_chan = channel_get_for_extend((const char*)ec.node_id,
+                                  &ec.ed_pubkey,
                                   &ec.orport_ipv4.addr,
                                   &msg,
                                   &should_launch);
@@ -1192,8 +1219,9 @@ circuit_extend(cell_t *cell, circuit_t *circ)
 
     circ->n_hop = extend_info_new(NULL /*nickname*/,
                                   (const char*)ec.node_id,
-                                  NULL /*onion_key*/,
-                                  NULL /*curve25519_key*/,
+                                  &ec.ed_pubkey,
+                                  NULL, /*onion_key*/
+                                  NULL, /*curve25519_key*/
                                   &ec.orport_ipv4.addr,
                                   ec.orport_ipv4.port);
 
@@ -1206,7 +1234,8 @@ circuit_extend(cell_t *cell, circuit_t *circ)
       /* we should try to open a connection */
       n_chan = channel_connect_for_circuit(&ec.orport_ipv4.addr,
                                            ec.orport_ipv4.port,
-                                           (const char*)ec.node_id);
+                                           (const char*)ec.node_id,
+                                           &ec.ed_pubkey);
       if (!n_chan) {
         log_info(LD_CIRC,"Launching n_chan failed. Closing circuit.");
         circuit_mark_for_close(circ, END_CIRC_REASON_CONNECTFAILED);
@@ -2356,19 +2385,23 @@ onion_append_hop(crypt_path_t **head_ptr, extend_info_t *choice)
 
 /** Allocate a new extend_info object based on the various arguments. */
 extend_info_t *
-extend_info_new(const char *nickname, const char *digest,
+extend_info_new(const char *nickname,
+                const char *rsa_id_digest,
+                const ed25519_public_key_t *ed_id,
                 crypto_pk_t *onion_key,
-                const curve25519_public_key_t *curve25519_key,
+                const curve25519_public_key_t *ntor_key,
                 const tor_addr_t *addr, uint16_t port)
 {
   extend_info_t *info = tor_malloc_zero(sizeof(extend_info_t));
-  memcpy(info->identity_digest, digest, DIGEST_LEN);
+  memcpy(info->identity_digest, rsa_id_digest, DIGEST_LEN);
+  if (ed_id && !ed25519_public_key_is_zero(ed_id))
+    memcpy(&info->ed_identity, ed_id, sizeof(ed25519_public_key_t));
   if (nickname)
     strlcpy(info->nickname, nickname, sizeof(info->nickname));
   if (onion_key)
     info->onion_key = crypto_pk_dup_key(onion_key);
-  if (curve25519_key)
-    memcpy(&info->curve25519_onion_key, curve25519_key,
+  if (ntor_key)
+    memcpy(&info->curve25519_onion_key, ntor_key,
            sizeof(curve25519_public_key_t));
   tor_addr_copy(&info->addr, addr);
   info->port = port;
@@ -2418,20 +2451,35 @@ extend_info_from_node(const node_t *node, int for_direct_connect)
     return NULL;
   }
 
+  const ed25519_public_key_t *ed_pubkey = NULL;
+
+  /* Don't send the ed25519 pubkey unless the target node actually supports
+   * authenticating with it. */
+  if (node_supports_ed25519_link_authentication(node)) {
+    log_info(LD_CIRC, "Including Ed25519 ID for %s", node_describe(node));
+    ed_pubkey = node_get_ed25519_id(node);
+  } else if (node_get_ed25519_id(node)) {
+    log_info(LD_CIRC, "Not including the ed25519 ID for %s, since it won't "
+             " be able to authenticate it.",
+             node_describe(node));
+  }
+
   if (valid_addr && node->ri)
     return extend_info_new(node->ri->nickname,
-                             node->identity,
-                             node->ri->onion_pkey,
-                             node->ri->onion_curve25519_pkey,
-                             &ap.addr,
-                             ap.port);
+                           node->identity,
+                           ed_pubkey,
+                           node->ri->onion_pkey,
+                           node->ri->onion_curve25519_pkey,
+                           &ap.addr,
+                           ap.port);
   else if (valid_addr && node->rs && node->md)
     return extend_info_new(node->rs->nickname,
-                             node->identity,
-                             node->md->onion_pkey,
-                             node->md->onion_curve25519_pkey,
-                             &ap.addr,
-                             ap.port);
+                           node->identity,
+                           ed_pubkey,
+                           node->md->onion_pkey,
+                           node->md->onion_curve25519_pkey,
+                           &ap.addr,
+                           ap.port);
   else
     return NULL;
 }
diff --git a/src/or/circuitbuild.h b/src/or/circuitbuild.h
index 7a6758919f..54d14bbc7f 100644
--- a/src/or/circuitbuild.h
+++ b/src/or/circuitbuild.h
@@ -47,9 +47,11 @@ MOCK_DECL(int, circuit_all_predicted_ports_handled, (time_t now,
 int circuit_append_new_exit(origin_circuit_t *circ, extend_info_t *info);
 int circuit_extend_to_new_exit(origin_circuit_t *circ, extend_info_t *info);
 void onion_append_to_cpath(crypt_path_t **head_ptr, crypt_path_t *new_hop);
-extend_info_t *extend_info_new(const char *nickname, const char *digest,
+extend_info_t *extend_info_new(const char *nickname,
+                               const char *rsa_id_digest,
+                               const ed25519_public_key_t *ed_id,
                                crypto_pk_t *onion_key,
-                               const curve25519_public_key_t *curve25519_key,
+                               const curve25519_public_key_t *ntor_key,
                                const tor_addr_t *addr, uint16_t port);
 extend_info_t *extend_info_from_node(const node_t *r, int for_direct_connect);
 extend_info_t *extend_info_dup(extend_info_t *info);
diff --git a/src/or/circuituse.c b/src/or/circuituse.c
index bc72015a5f..04c5af92e8 100644
--- a/src/or/circuituse.c
+++ b/src/or/circuituse.c
@@ -2168,6 +2168,10 @@ circuit_get_open_circ_or_launch(entry_connection_t *conn,
           if (want_onehop && conn->chosen_exit_name[0] == '$') {
             /* We're asking for a one-hop circuit to a router that
              * we don't have a routerinfo about. Make up an extend_info. */
+            /* XXX prop220: we need to make chosen_exit_name able to
+             * encode both key formats. This is not absolutely critical
+             * since this is just for one-hop circuits, but we should
+             * still get it done */
             char digest[DIGEST_LEN];
             char *hexdigest = conn->chosen_exit_name+1;
             tor_addr_t addr;
@@ -2182,9 +2186,12 @@ circuit_get_open_circ_or_launch(entry_connection_t *conn,
                        escaped_safe_str_client(conn->socks_request->address));
               return -1;
             }
+            /* XXXX prop220 add a workaround for ed25519 ID below*/
             extend_info = extend_info_new(conn->chosen_exit_name+1,
-                                          digest, NULL, NULL, &addr,
-                                          conn->socks_request->port);
+                                          digest,
+                                          NULL, /* Ed25519 ID */
+                                          NULL, NULL, /* onion keys */
+                                          &addr, conn->socks_request->port);
           } else { /* ! (want_onehop && conn->chosen_exit_name[0] == '$') */
             /* We will need an onion key for the router, and we
              * don't have one. Refuse or relax requirements. */
diff --git a/src/or/config.c b/src/or/config.c
index 81be2a4b3a..6948bdbdb4 100644
--- a/src/or/config.c
+++ b/src/or/config.c
@@ -305,6 +305,7 @@ static config_var_t option_vars_[] = {
   V(ExtORPortCookieAuthFile,     STRING,   NULL),
   V(ExtORPortCookieAuthFileGroupReadable, BOOL, "0"),
   V(ExtraInfoStatistics,         BOOL,     "1"),
+  V(ExtendByEd25519ID,           AUTOBOOL, "auto"),
   V(FallbackDir,                 LINELIST, NULL),
   V(UseDefaultFallbackDirs,      BOOL,     "1"),
 
@@ -497,6 +498,7 @@ static config_var_t option_vars_[] = {
   V(User,                        STRING,   NULL),
   OBSOLETE("UserspaceIOCPBuffers"),
   V(AuthDirSharedRandomness,     BOOL,     "1"),
+  V(AuthDirTestEd25519LinkKeys,  BOOL,     "1"),
   OBSOLETE("V1AuthoritativeDirectory"),
   OBSOLETE("V2AuthoritativeDirectory"),
   VAR("V3AuthoritativeDirectory",BOOL, V3AuthoritativeDir,   "0"),
diff --git a/src/or/connection.c b/src/or/connection.c
index bdf14bb2fc..ac3408a72e 100644
--- a/src/or/connection.c
+++ b/src/or/connection.c
@@ -644,7 +644,7 @@ connection_free_(connection_t *conn)
   if (conn->type == CONN_TYPE_OR &&
       !tor_digest_is_zero(TO_OR_CONN(conn)->identity_digest)) {
     log_warn(LD_BUG, "called on OR conn with non-zeroed identity_digest");
-    connection_or_remove_from_identity_map(TO_OR_CONN(conn));
+    connection_or_clear_identity(TO_OR_CONN(conn));
   }
   if (conn->type == CONN_TYPE_OR || conn->type == CONN_TYPE_EXT_OR) {
     connection_or_remove_from_ext_or_id_map(TO_OR_CONN(conn));
@@ -675,7 +675,7 @@ connection_free,(connection_t *conn))
   }
   if (connection_speaks_cells(conn)) {
     if (!tor_digest_is_zero(TO_OR_CONN(conn)->identity_digest)) {
-      connection_or_remove_from_identity_map(TO_OR_CONN(conn));
+      connection_or_clear_identity(TO_OR_CONN(conn));
     }
   }
   if (conn->type == CONN_TYPE_CONTROL) {
diff --git a/src/or/connection_or.c b/src/or/connection_or.c
index eb67f0653f..635d3e416a 100644
--- a/src/or/connection_or.c
+++ b/src/or/connection_or.c
@@ -75,56 +75,25 @@ static void connection_or_mark_bad_for_new_circs(or_connection_t *or_conn);
 
 static void connection_or_change_state(or_connection_t *conn, uint8_t state);
 
-/**************************************************************/
+static void connection_or_check_canonicity(or_connection_t *conn,
+                                           int started_here);
 
-/** Map from identity digest of connected OR or desired OR to a connection_t
- * with that identity digest.  If there is more than one such connection_t,
- * they form a linked list, with next_with_same_id as the next pointer. */
-static digestmap_t *orconn_identity_map = NULL;
+/**************************************************************/
 
 /** Global map between Extended ORPort identifiers and OR
  *  connections. */
 static digestmap_t *orconn_ext_or_id_map = NULL;
 
-/** If conn is listed in orconn_identity_map, remove it, and clear
- * conn->identity_digest.  Otherwise do nothing. */
+/** Clear clear conn->identity_digest and update other data
+ * structures as appropriate.*/
 void
-connection_or_remove_from_identity_map(or_connection_t *conn)
+connection_or_clear_identity(or_connection_t *conn)
 {
-  or_connection_t *tmp;
   tor_assert(conn);
-  if (!orconn_identity_map)
-    return;
-  tmp = digestmap_get(orconn_identity_map, conn->identity_digest);
-  if (!tmp) {
-    if (!tor_digest_is_zero(conn->identity_digest)) {
-      log_warn(LD_BUG, "Didn't find connection '%s' on identity map when "
-               "trying to remove it.",
-               conn->nickname ? conn->nickname : "NULL");
-    }
-    return;
-  }
-  if (conn == tmp) {
-    if (conn->next_with_same_id)
-      digestmap_set(orconn_identity_map, conn->identity_digest,
-                    conn->next_with_same_id);
-    else
-      digestmap_remove(orconn_identity_map, conn->identity_digest);
-  } else {
-    while (tmp->next_with_same_id) {
-      if (tmp->next_with_same_id == conn) {
-        tmp->next_with_same_id = conn->next_with_same_id;
-        break;
-      }
-      tmp = tmp->next_with_same_id;
-    }
-  }
   memset(conn->identity_digest, 0, DIGEST_LEN);
-  conn->next_with_same_id = NULL;
 }
 
-/** Remove all entries from the identity-to-orconn map, and clear
- * all identities in OR conns.*/
+/** Clear all identities in OR conns.*/
 void
 connection_or_clear_identity_map(void)
 {
@@ -132,60 +101,72 @@ connection_or_clear_identity_map(void)
   SMARTLIST_FOREACH(conns, connection_t *, conn,
   {
     if (conn->type == CONN_TYPE_OR) {
-      or_connection_t *or_conn = TO_OR_CONN(conn);
-      memset(or_conn->identity_digest, 0, DIGEST_LEN);
-      or_conn->next_with_same_id = NULL;
+      connection_or_clear_identity(TO_OR_CONN(conn));
     }
   });
-
-  digestmap_free(orconn_identity_map, NULL);
-  orconn_identity_map = NULL;
 }
 
 /** Change conn->identity_digest to digest, and add conn into
- * orconn_digest_map. */
+ * the appropriate digest maps.
+ *
+ * NOTE that this function only allows two kinds of transitions: from
+ * unset identity to set identity, and from idempotent re-settings
+ * of the same identity.  It's not allowed to clear an identity or to
+ * change an identity.  Return 0 on success, and -1 if the transition
+ * is not allowed.
+ **/
 static void
 connection_or_set_identity_digest(or_connection_t *conn,
                                   const char *rsa_digest,
                                   const ed25519_public_key_t *ed_id)
 {
-  (void) ed_id; // DOCDOC // XXXX not implemented yet.
-  or_connection_t *tmp;
+  channel_t *chan = NULL;
   tor_assert(conn);
   tor_assert(rsa_digest);
 
-  if (!orconn_identity_map)
-    orconn_identity_map = digestmap_new();
-  if (tor_memeq(conn->identity_digest, rsa_digest, DIGEST_LEN))
+  if (conn->chan)
+    chan = TLS_CHAN_TO_BASE(conn->chan);
+
+  log_info(LD_HANDSHAKE, "Set identity digest for %p (%s): %s %s.",
+           conn,
+           escaped_safe_str(conn->base_.address),
+           hex_str(rsa_digest, DIGEST_LEN),
+           ed25519_fmt(ed_id));
+  log_info(LD_HANDSHAKE, "   (Previously: %s %s)",
+           hex_str(conn->identity_digest, DIGEST_LEN),
+           chan ? ed25519_fmt(&chan->ed25519_identity) : "<null>");
+
+  const int rsa_id_was_set = ! tor_digest_is_zero(conn->identity_digest);
+  const int ed_id_was_set =
+    chan && !ed25519_public_key_is_zero(&chan->ed25519_identity);
+  const int rsa_changed =
+    tor_memneq(conn->identity_digest, rsa_digest, DIGEST_LEN);
+  const int ed_changed = ed_id_was_set &&
+    (!ed_id || !ed25519_pubkey_eq(ed_id, &chan->ed25519_identity));
+
+  tor_assert(!rsa_changed || !rsa_id_was_set);
+  tor_assert(!ed_changed || !ed_id_was_set);
+
+  if (!rsa_changed && !ed_changed)
     return;
 
   /* If the identity was set previously, remove the old mapping. */
-  if (! tor_digest_is_zero(conn->identity_digest)) {
-    connection_or_remove_from_identity_map(conn);
-    if (conn->chan)
-      channel_clear_identity_digest(TLS_CHAN_TO_BASE(conn->chan));
+  if (rsa_id_was_set) {
+    connection_or_clear_identity(conn);
+    if (chan)
+      channel_clear_identity_digest(chan);
   }
 
   memcpy(conn->identity_digest, rsa_digest, DIGEST_LEN);
 
-  /* If we're setting the ID to zero, don't add a mapping. */
-  if (tor_digest_is_zero(rsa_digest))
+  /* If we're initializing the IDs to zero, don't add a mapping yet. */
+  if (tor_digest_is_zero(rsa_digest) &&
+      (!ed_id || ed25519_public_key_is_zero(ed_id)))
     return;
 
-  tmp = digestmap_set(orconn_identity_map, rsa_digest, conn);
-  conn->next_with_same_id = tmp;
-
   /* Deal with channels */
-  if (conn->chan)
-    channel_set_identity_digest(TLS_CHAN_TO_BASE(conn->chan), rsa_digest);
-
-#if 1
-  /* Testing code to check for bugs in representation. */
-  for (; tmp; tmp = tmp->next_with_same_id) {
-    tor_assert(tor_memeq(tmp->identity_digest, rsa_digest, DIGEST_LEN));
-    tor_assert(tmp != conn);
-  }
-#endif
+  if (chan)
+    channel_set_identity_digest(chan, rsa_digest, ed_id);
 }
 
 /** Remove the Extended ORPort identifier of <b>conn</b> from the
@@ -883,14 +864,44 @@ connection_or_init_conn_from_address(or_connection_t *conn,
                                      const ed25519_public_key_t *ed_id,
                                      int started_here)
 {
-  (void) ed_id; // not fully used yet.
-  const node_t *r = node_get_by_id(id_digest);
+  log_debug(LD_HANDSHAKE, "init conn from address %s: %s, %s (%d)",
+            fmt_addr(addr),
+            hex_str((const char*)id_digest, DIGEST_LEN),
+            ed25519_fmt(ed_id),
+            started_here);
+
   connection_or_set_identity_digest(conn, id_digest, ed_id);
   connection_or_update_token_buckets_helper(conn, 1, get_options());
 
   conn->base_.port = port;
   tor_addr_copy(&conn->base_.addr, addr);
   tor_addr_copy(&conn->real_addr, addr);
+
+  connection_or_check_canonicity(conn, started_here);
+}
+
+/** Check whether the identity of <b>conn</b> matches a known node.  If it
+ * does, check whether the address of conn matches the expected address, and
+ * update the connection's is_canonical flag, nickname, and address fields as
+ * appropriate. */
+static void
+connection_or_check_canonicity(or_connection_t *conn, int started_here)
+{
+  const char *id_digest = conn->identity_digest;
+  const ed25519_public_key_t *ed_id = NULL;
+  const tor_addr_t *addr = &conn->real_addr;
+  if (conn->chan)
+    ed_id = & TLS_CHAN_TO_BASE(conn->chan)->ed25519_identity;
+
+  const node_t *r = node_get_by_id(id_digest);
+  if (r &&
+      node_supports_ed25519_link_authentication(r) &&
+      ! node_ed25519_id_matches(r, ed_id)) {
+    /* If this node is capable of proving an ed25519 ID,
+     * we can't call this a canonical connection unless both IDs match. */
+     r = NULL;
+  }
+
   if (r) {
     tor_addr_port_t node_ap;
     node_get_pref_orport(r, &node_ap);
@@ -912,10 +923,12 @@ connection_or_init_conn_from_address(or_connection_t *conn,
       tor_addr_copy(&conn->base_.addr, &node_ap.addr);
       conn->base_.port = node_ap.port;
     }
+    tor_free(conn->nickname);
     conn->nickname = tor_strdup(node_get_nickname(r));
     tor_free(conn->base_.address);
     conn->base_.address = tor_addr_to_str_dup(&node_ap.addr);
   } else {
+    tor_free(conn->nickname);
     conn->nickname = tor_malloc(HEX_DIGEST_LEN+2);
     conn->nickname[0] = '$';
     base16_encode(conn->nickname+1, HEX_DIGEST_LEN+1,
@@ -961,7 +974,7 @@ connection_or_mark_bad_for_new_circs(or_connection_t *or_conn)
  * too old for new circuits? */
 #define TIME_BEFORE_OR_CONN_IS_TOO_OLD (60*60*24*7)
 
-/** Given the head of the linked list for all the or_connections with a given
+/** Given a list of all the or_connections with a given
  * identity, set elements of that list as is_bad_for_new_circs as
  * appropriate. Helper for connection_or_set_bad_connections().
  *
@@ -978,16 +991,19 @@ connection_or_mark_bad_for_new_circs(or_connection_t *or_conn)
  * See channel_is_better() in channel.c for our idea of what makes one OR
  * connection better than another.
  */
-static void
-connection_or_group_set_badness(or_connection_t *head, int force)
+void
+connection_or_group_set_badness_(smartlist_t *group, int force)
 {
-  or_connection_t *or_conn = NULL, *best = NULL;
+  /* XXXX this function should be entirely about channels, not OR
+   * XXXX connections. */
+
+  or_connection_t *best = NULL;
   int n_old = 0, n_inprogress = 0, n_canonical = 0, n_other = 0;
   time_t now = time(NULL);
 
   /* Pass 1: expire everything that's old, and see what the status of
    * everything else is. */
-  for (or_conn = head; or_conn; or_conn = or_conn->next_with_same_id) {
+  SMARTLIST_FOREACH_BEGIN(group, or_connection_t *, or_conn) {
     if (or_conn->base_.marked_for_close ||
         connection_or_is_bad_for_new_circs(or_conn))
       continue;
@@ -1011,11 +1027,11 @@ connection_or_group_set_badness(or_connection_t *head, int force)
     } else {
       ++n_other;
     }
-  }
+  } SMARTLIST_FOREACH_END(or_conn);
 
   /* Pass 2: We know how about how good the best connection is.
    * expire everything that's worse, and find the very best if we can. */
-  for (or_conn = head; or_conn; or_conn = or_conn->next_with_same_id) {
+  SMARTLIST_FOREACH_BEGIN(group, or_connection_t *, or_conn) {
     if (or_conn->base_.marked_for_close ||
         connection_or_is_bad_for_new_circs(or_conn))
       continue; /* This one doesn't need to be marked bad. */
@@ -1042,7 +1058,7 @@ connection_or_group_set_badness(or_connection_t *head, int force)
                           0)) {
       best = or_conn;
     }
-  }
+  } SMARTLIST_FOREACH_END(or_conn);
 
   if (!best)
     return;
@@ -1061,7 +1077,7 @@ connection_or_group_set_badness(or_connection_t *head, int force)
    *   0.1.2.x dies out, the first case will go away, and the second one is
    *   "mostly harmless", so a fix can wait until somebody is bored.
    */
-  for (or_conn = head; or_conn; or_conn = or_conn->next_with_same_id) {
+  SMARTLIST_FOREACH_BEGIN(group, or_connection_t *, or_conn) {
     if (or_conn->base_.marked_for_close ||
         connection_or_is_bad_for_new_circs(or_conn) ||
         or_conn->base_.state != OR_CONN_STATE_OPEN)
@@ -1095,24 +1111,7 @@ connection_or_group_set_badness(or_connection_t *head, int force)
         connection_or_mark_bad_for_new_circs(or_conn);
       }
     }
-  }
-}
-
-/** Go through all the OR connections (or if <b>digest</b> is non-NULL, just
- * the OR connections with that digest), and set the is_bad_for_new_circs
- * flag based on the rules in connection_or_group_set_badness() (or just
- * always set it if <b>force</b> is true).
- */
-void
-connection_or_set_bad_connections(const char *digest, int force)
-{
-  if (!orconn_identity_map)
-    return;
-
-  DIGESTMAP_FOREACH(orconn_identity_map, identity, or_connection_t *, conn) {
-    if (!digest || tor_memeq(digest, conn->identity_digest, DIGEST_LEN))
-      connection_or_group_set_badness(conn, force);
-  } DIGESTMAP_FOREACH_END;
+  } SMARTLIST_FOREACH_END(or_conn);
 }
 
 /** <b>conn</b> is in the 'connecting' state, and it failed to complete
@@ -1182,7 +1181,6 @@ connection_or_connect, (const tor_addr_t *_addr, uint16_t port,
                         const ed25519_public_key_t *ed_id,
                         channel_tls_t *chan))
 {
-  (void) ed_id; // XXXX not fully used yet.
   or_connection_t *conn;
   const or_options_t *options = get_options();
   int socket_error = 0;
@@ -1201,6 +1199,11 @@ connection_or_connect, (const tor_addr_t *_addr, uint16_t port,
     log_info(LD_PROTOCOL,"Client asked me to connect to myself. Refusing.");
     return NULL;
   }
+  if (server_mode(options) && router_ed25519_id_is_me(ed_id)) {
+    log_info(LD_PROTOCOL,"Client asked me to connect to myself by Ed25519 "
+             "identity. Refusing.");
+    return NULL;
+  }
 
   conn = or_connection_new(CONN_TYPE_OR, tor_addr_family(&addr));
 
@@ -1570,20 +1573,25 @@ connection_or_check_valid_tls_handshake(or_connection_t *conn,
 
   crypto_pk_free(identity_rcvd);
 
-  if (started_here)
+  if (started_here) {
+    /* A TLS handshake can't teach us an Ed25519 ID, so we set it to NULL
+     * here. */
+    log_debug(LD_HANDSHAKE, "Calling client_learned_peer_id from "
+              "check_valid_tls_handshake");
     return connection_or_client_learned_peer_id(conn,
                                         (const uint8_t*)digest_rcvd_out,
-                                        NULL // Ed25519 ID
-                                        );
+                                        NULL);
+  }
 
   return 0;
 }
 
 /** Called when we (as a connection initiator) have definitively,
  * authenticatedly, learned that ID of the Tor instance on the other
- * side of <b>conn</b> is <b>peer_id</b>.  For v1 and v2 handshakes,
+ * side of <b>conn</b> is <b>rsa_peer_id</b> and optionally <b>ed_peer_id</b>.
+ * For v1 and v2 handshakes,
  * this is right after we get a certificate chain in a TLS handshake
- * or renegotiation.  For v3 handshakes, this is right after we get a
+ * or renegotiation.  For v3+ handshakes, this is right after we get a
  * certificate chain in a CERTS cell.
  *
  * If we did not know the ID before, record the one we got.
@@ -1607,11 +1615,26 @@ connection_or_client_learned_peer_id(or_connection_t *conn,
                                      const uint8_t *rsa_peer_id,
                                      const ed25519_public_key_t *ed_peer_id)
 {
-  (void) ed_peer_id; // not used yet.
-
   const or_options_t *options = get_options();
-
-  if (tor_digest_is_zero(conn->identity_digest)) {
+  channel_tls_t *chan_tls = conn->chan;
+  channel_t *chan = channel_tls_to_base(chan_tls);
+  int changed_identity = 0;
+  tor_assert(chan);
+
+  const int expected_rsa_key =
+    ! tor_digest_is_zero(conn->identity_digest);
+  const int expected_ed_key =
+    ! ed25519_public_key_is_zero(&chan->ed25519_identity);
+
+  log_info(LD_HANDSHAKE, "learned peer id for %p (%s): %s, %s",
+           conn,
+           safe_str_client(conn->base_.address),
+           hex_str((const char*)rsa_peer_id, DIGEST_LEN),
+           ed25519_fmt(ed_peer_id));
+
+  if (! expected_rsa_key && ! expected_ed_key) {
+    log_info(LD_HANDSHAKE, "(we had no ID in mind when we made this "
+             "connection.");
     connection_or_set_identity_digest(conn,
                                       (const char*)rsa_peer_id, ed_peer_id);
     tor_free(conn->nickname);
@@ -1625,16 +1648,39 @@ connection_or_client_learned_peer_id(or_connection_t *conn,
     /* if it's a bridge and we didn't know its identity fingerprint, now
      * we do -- remember it for future attempts. */
     learned_router_identity(&conn->base_.addr, conn->base_.port,
-                            (const char*)rsa_peer_id /*, ed_peer_id XXXX */);
+                            (const char*)rsa_peer_id, ed_peer_id);
+    changed_identity = 1;
   }
 
-  if (tor_memneq(rsa_peer_id, conn->identity_digest, DIGEST_LEN)) {
+  const int rsa_mismatch = expected_rsa_key &&
+    tor_memneq(rsa_peer_id, conn->identity_digest, DIGEST_LEN);
+  /* It only counts as an ed25519 mismatch if we wanted an ed25519 identity
+   * and didn't get it. It's okay if we get one that we didn't ask for. */
+  const int ed25519_mismatch =
+    expected_ed_key &&
+    (ed_peer_id == NULL ||
+     ! ed25519_pubkey_eq(&chan->ed25519_identity, ed_peer_id));
+
+  if (rsa_mismatch || ed25519_mismatch) {
     /* I was aiming for a particular digest. I didn't get it! */
-    char seen[HEX_DIGEST_LEN+1];
-    char expected[HEX_DIGEST_LEN+1];
-    base16_encode(seen, sizeof(seen), (const char*)rsa_peer_id, DIGEST_LEN);
-    base16_encode(expected, sizeof(expected), conn->identity_digest,
+    char seen_rsa[HEX_DIGEST_LEN+1];
+    char expected_rsa[HEX_DIGEST_LEN+1];
+    char seen_ed[ED25519_BASE64_LEN+1];
+    char expected_ed[ED25519_BASE64_LEN+1];
+    base16_encode(seen_rsa, sizeof(seen_rsa),
+                  (const char*)rsa_peer_id, DIGEST_LEN);
+    base16_encode(expected_rsa, sizeof(expected_rsa), conn->identity_digest,
                   DIGEST_LEN);
+    if (ed_peer_id) {
+      ed25519_public_to_base64(seen_ed, ed_peer_id);
+    } else {
+      strlcpy(seen_ed, "no ed25519 key", sizeof(seen_ed));
+    }
+    if (! ed25519_public_key_is_zero(&chan->ed25519_identity)) {
+      ed25519_public_to_base64(expected_ed, &chan->ed25519_identity);
+    } else {
+      strlcpy(expected_ed, "no ed25519 key", sizeof(expected_ed));
+    }
     const int using_hardcoded_fingerprints =
       !networkstatus_get_reasonably_live_consensus(time(NULL),
                                                    usable_consensus_flavor());
@@ -1669,9 +1715,11 @@ connection_or_client_learned_peer_id(or_connection_t *conn,
     }
 
     log_fn(severity, LD_HANDSHAKE,
-           "Tried connecting to router at %s:%d, but identity key was not "
-           "as expected: wanted %s but got %s.%s",
-           conn->base_.address, conn->base_.port, expected, seen, extra_log);
+           "Tried connecting to router at %s:%d, but RSA identity key was not "
+           "as expected: wanted %s + %s but got %s + %s.%s",
+           conn->base_.address, conn->base_.port,
+           expected_rsa, expected_ed, seen_rsa, seen_ed, extra_log);
+
     entry_guard_register_connect_status(conn->identity_digest, 0, 1,
                                         time(NULL));
     control_event_or_conn_status(conn, OR_CONN_EVENT_FAILED,
@@ -1683,9 +1731,24 @@ connection_or_client_learned_peer_id(or_connection_t *conn,
                                 conn);
     return -1;
   }
+
+  if (!expected_ed_key && ed_peer_id) {
+    log_info(LD_HANDSHAKE, "(we had no Ed25519 ID in mind when we made this "
+             "connection.");
+    connection_or_set_identity_digest(conn,
+                                      (const char*)rsa_peer_id, ed_peer_id);
+    changed_identity = 1;
+  }
+
+  if (changed_identity) {
+    /* If we learned an identity for this connection, then we might have
+     * just discovered it to be canonical. */
+    connection_or_check_canonicity(conn, conn->handshake_state->started_here);
+  }
+
   if (authdir_mode_tests_reachability(options)) {
     dirserv_orconn_tls_done(&conn->base_.addr, conn->base_.port,
-                            (const char*)rsa_peer_id /*, ed_id XXXX */);
+                            (const char*)rsa_peer_id, ed_peer_id);
   }
 
   return 0;
diff --git a/src/or/connection_or.h b/src/or/connection_or.h
index da95718ac9..80a5bddb14 100644
--- a/src/or/connection_or.h
+++ b/src/or/connection_or.h
@@ -12,14 +12,13 @@
 #ifndef TOR_CONNECTION_OR_H
 #define TOR_CONNECTION_OR_H
 
-void connection_or_remove_from_identity_map(or_connection_t *conn);
+void connection_or_clear_identity(or_connection_t *conn);
 void connection_or_clear_identity_map(void);
 void clear_broken_connection_map(int disable);
 or_connection_t *connection_or_get_for_extend(const char *digest,
                                               const tor_addr_t *target_addr,
                                               const char **msg_out,
                                               int *launch_out);
-void connection_or_set_bad_connections(const char *digest, int force);
 
 void connection_or_block_renegotiation(or_connection_t *conn);
 int connection_or_reached_eof(or_connection_t *conn);
@@ -111,5 +110,7 @@ void var_cell_free(var_cell_t *cell);
 /* DOCDOC */
 #define MIN_LINK_PROTO_FOR_WIDE_CIRC_IDS 4
 
+void connection_or_group_set_badness_(smartlist_t *group, int force);
+
 #endif
 
diff --git a/src/or/dirserv.c b/src/or/dirserv.c
index e2a6943708..399d5ea955 100644
--- a/src/or/dirserv.c
+++ b/src/or/dirserv.c
@@ -3176,7 +3176,8 @@ dirserv_get_routerdescs(smartlist_t *descs_out, const char *key,
 void
 dirserv_orconn_tls_done(const tor_addr_t *addr,
                         uint16_t or_port,
-                        const char *digest_rcvd)
+                        const char *digest_rcvd,
+                        const ed25519_public_key_t *ed_id_rcvd)
 {
   node_t *node = NULL;
   tor_addr_port_t orport;
@@ -3188,8 +3189,25 @@ dirserv_orconn_tls_done(const tor_addr_t *addr,
   node = node_get_mutable_by_id(digest_rcvd);
   if (node == NULL || node->ri == NULL)
     return;
+
   ri = node->ri;
 
+  if (get_options()->AuthDirTestEd25519LinkKeys &&
+      ri->cache_info.signing_key_cert) {
+    /* We allow the node to have an ed25519 key if we haven't been told one in
+     * the routerinfo, but if we *HAVE* been told one in the routerinfo, it
+     * needs to match. */
+    const ed25519_public_key_t *expected_id =
+      &ri->cache_info.signing_key_cert->signing_key;
+    tor_assert(!ed25519_public_key_is_zero(expected_id));
+    if (! ed_id_rcvd || ! ed25519_pubkey_eq(ed_id_rcvd, expected_id)) {
+      log_info(LD_DIRSERV, "Router at %s:%d with RSA ID %s "
+               "did not present expected Ed25519 ID.",
+               fmt_addr(addr), or_port, hex_str(digest_rcvd, DIGEST_LEN));
+      return; /* Don't mark it as reachable. */
+    }
+  }
+
   tor_addr_copy(&orport.addr, addr);
   orport.port = or_port;
   if (router_has_orport(ri, &orport)) {
@@ -3245,23 +3263,31 @@ dirserv_should_launch_reachability_test(const routerinfo_t *ri,
 void
 dirserv_single_reachability_test(time_t now, routerinfo_t *router)
 {
+  const or_options_t *options = get_options();
   channel_t *chan = NULL;
   node_t *node = NULL;
   tor_addr_t router_addr;
+  const ed25519_public_key_t *ed_id_key;
   (void) now;
 
   tor_assert(router);
   node = node_get_mutable_by_id(router->cache_info.identity_digest);
   tor_assert(node);
 
+  if (options->AuthDirTestEd25519LinkKeys &&
+      node_supports_ed25519_link_authentication(node)) {
+    ed_id_key = &router->cache_info.signing_key_cert->signing_key;
+  } else {
+    ed_id_key = NULL;
+  }
+
   /* IPv4. */
   log_debug(LD_OR,"Testing reachability of %s at %s:%u.",
             router->nickname, fmt_addr32(router->addr), router->or_port);
   tor_addr_from_ipv4h(&router_addr, router->addr);
   chan = channel_tls_connect(&router_addr, router->or_port,
                              router->cache_info.identity_digest,
-                             NULL // XXXX Ed25519 ID.
-                             );
+                             ed_id_key);
   if (chan) command_setup_channel(chan);
 
   /* Possible IPv6. */
@@ -3274,8 +3300,7 @@ dirserv_single_reachability_test(time_t now, routerinfo_t *router)
               router->ipv6_orport);
     chan = channel_tls_connect(&router->ipv6_addr, router->ipv6_orport,
                                router->cache_info.identity_digest,
-                               NULL // XXXX Ed25519 ID.
-                               );
+                               ed_id_key);
     if (chan) command_setup_channel(chan);
   }
 }
diff --git a/src/or/dirserv.h b/src/or/dirserv.h
index 1e4f27e3d7..e83da5e5ac 100644
--- a/src/or/dirserv.h
+++ b/src/or/dirserv.h
@@ -73,7 +73,8 @@ int dirserv_get_routerdescs(smartlist_t *descs_out, const char *key,
                             const char **msg);
 void dirserv_orconn_tls_done(const tor_addr_t *addr,
                              uint16_t or_port,
-                             const char *digest_rcvd);
+                             const char *digest_rcvd,
+                             const ed25519_public_key_t *ed_id_rcvd);
 int dirserv_should_launch_reachability_test(const routerinfo_t *ri,
                                             const routerinfo_t *ri_old);
 void dirserv_single_reachability_test(time_t now, routerinfo_t *router);
diff --git a/src/or/entrynodes.c b/src/or/entrynodes.c
index b3fa31df7b..af1b1a39ab 100644
--- a/src/or/entrynodes.c
+++ b/src/or/entrynodes.c
@@ -15,13 +15,13 @@
 #define ENTRYNODES_PRIVATE
 
 #include "or.h"
+#include "channel.h"
 #include "circpathbias.h"
 #include "circuitbuild.h"
 #include "circuitstats.h"
 #include "config.h"
 #include "confparse.h"
 #include "connection.h"
-#include "connection_or.h"
 #include "control.h"
 #include "directory.h"
 #include "entrynodes.h"
@@ -2108,18 +2108,34 @@ node_is_a_configured_bridge(const node_t *node)
  */
 void
 learned_router_identity(const tor_addr_t *addr, uint16_t port,
-                        const char *digest)
+                        const char *digest,
+                        const ed25519_public_key_t *ed_id)
 {
+  // XXXX prop220 use ed_id here, once there is some way to specify
+  (void)ed_id;
+  int learned = 0;
   bridge_info_t *bridge =
     get_configured_bridge_by_addr_port_digest(addr, port, digest);
   if (bridge && tor_digest_is_zero(bridge->identity)) {
+    memcpy(bridge->identity, digest, DIGEST_LEN);
+    learned = 1;
+  }
+  /* XXXX prop220 remember bridge ed25519 identities -- add a field */
+#if 0
+  if (bridge && ed_id &&
+      ed25519_public_key_is_zero(&bridge->ed25519_identity) &&
+      !ed25519_public_key_is_zero(ed_id)) {
+    memcpy(&bridge->ed25519_identity, ed_id, sizeof(*ed_id));
+    learned = 1;
+  }
+#endif
+  if (learned) {
     char *transport_info = NULL;
     const char *transport_name =
       find_transport_name_by_bridge_addrport(addr, port);
     if (transport_name)
       tor_asprintf(&transport_info, " (with transport '%s')", transport_name);
-
-    memcpy(bridge->identity, digest, DIGEST_LEN);
+    // XXXX prop220 log both fingerprints.
     log_notice(LD_DIR, "Learned fingerprint %s for bridge %s%s.",
                hex_str(digest, DIGEST_LEN), fmt_addrport(addr, port),
                transport_info ? transport_info : "");
@@ -2216,6 +2232,8 @@ bridge_add_from_config(bridge_line_t *bridge_line)
 {
   bridge_info_t *b;
 
+  // XXXX prop220 add a way to specify ed25519 ID to bridge_line_t.
+
   { /* Log the bridge we are about to register: */
     log_debug(LD_GENERAL, "Registering bridge at %s (transport: %s) (%s)",
               fmt_addrport(&bridge_line->addr, bridge_line->port),
@@ -2306,7 +2324,10 @@ routerset_contains_bridge(const routerset_t *routerset,
     return 0;
 
   extinfo = extend_info_new(
-         NULL, bridge->identity, NULL, NULL, &bridge->addr, bridge->port);
+         NULL, bridge->identity,
+         NULL, /* Ed25519 ID */
+         NULL, NULL, /* onion keys */
+         &bridge->addr, bridge->port);
   result = routerset_contains_extendinfo(routerset, extinfo);
   extend_info_free(extinfo);
   return result;
@@ -2746,7 +2767,7 @@ entries_retry_helper(const or_options_t *options, int act)
            * the node down and undermine the retry attempt. We mark even
            * the established conns, since if the network just came back
            * we'll want to attach circuits to fresh conns. */
-          connection_or_set_bad_connections(node->identity, 1);
+          channel_update_bad_for_new_circs(node->identity, 1);
 
           /* mark this entry node for retry */
           router_set_status(node->identity, 1);
diff --git a/src/or/entrynodes.h b/src/or/entrynodes.h
index 00f96916b6..f8aaedf171 100644
--- a/src/or/entrynodes.h
+++ b/src/or/entrynodes.h
@@ -167,7 +167,8 @@ int extend_info_is_a_configured_bridge(const extend_info_t *ei);
 int routerinfo_is_a_configured_bridge(const routerinfo_t *ri);
 int node_is_a_configured_bridge(const node_t *node);
 void learned_router_identity(const tor_addr_t *addr, uint16_t port,
-                             const char *digest);
+                             const char *digest,
+                             const ed25519_public_key_t *ed_id);
 struct bridge_line_t;
 void bridge_add_from_config(struct bridge_line_t *bridge_line);
 void retry_bridge_descriptor_fetch_directly(const char *digest);
diff --git a/src/or/main.c b/src/or/main.c
index c10f62724a..8239606c08 100644
--- a/src/or/main.c
+++ b/src/or/main.c
@@ -362,7 +362,7 @@ connection_unlink(connection_t *conn)
   }
   if (conn->type == CONN_TYPE_OR) {
     if (!tor_digest_is_zero(TO_OR_CONN(conn)->identity_digest))
-      connection_or_remove_from_identity_map(TO_OR_CONN(conn));
+      connection_or_clear_identity(TO_OR_CONN(conn));
     /* connection_unlink() can only get called if the connection
      * was already on the closeable list, and it got there by
      * connection_mark_for_close(), which was called from
@@ -1426,7 +1426,7 @@ run_scheduled_events(time_t now)
   }
 
   /* 5. We do housekeeping for each connection... */
-  connection_or_set_bad_connections(NULL, 0);
+  channel_update_bad_for_new_circs(NULL, 0);
   int i;
   for (i=0;i<smartlist_len(connection_array);i++) {
     run_connection_housekeeping(i, now);
diff --git a/src/or/nodelist.c b/src/or/nodelist.c
index 4d180dc1ab..6117b86d65 100644
--- a/src/or/nodelist.c
+++ b/src/or/nodelist.c
@@ -49,10 +49,12 @@
 #include "networkstatus.h"
 #include "nodelist.h"
 #include "policies.h"
+#include "protover.h"
 #include "rendservice.h"
 #include "router.h"
 #include "routerlist.h"
 #include "routerset.h"
+#include "torcert.h"
 
 #include <string.h>
 
@@ -646,6 +648,74 @@ node_get_by_nickname,(const char *nickname, int warn_if_unnamed))
   }
 }
 
+/** Return the Ed25519 identity key for the provided node, or NULL if it
+ * doesn't have one. */
+const ed25519_public_key_t *
+node_get_ed25519_id(const node_t *node)
+{
+  if (node->ri) {
+    if (node->ri->cache_info.signing_key_cert) {
+      const ed25519_public_key_t *pk =
+        &node->ri->cache_info.signing_key_cert->signing_key;
+      if (BUG(ed25519_public_key_is_zero(pk)))
+        goto try_the_md;
+      return pk;
+    }
+  }
+ try_the_md:
+  if (node->md) {
+    if (node->md->ed25519_identity_pkey) {
+      return node->md->ed25519_identity_pkey;
+    }
+  }
+  return NULL;
+}
+
+/** Return true iff this node's Ed25519 identity matches <b>id</b>.
+ * (An absent Ed25519 identity matches NULL or zero.) */
+int
+node_ed25519_id_matches(const node_t *node, const ed25519_public_key_t *id)
+{
+  const ed25519_public_key_t *node_id = node_get_ed25519_id(node);
+  if (node_id == NULL || ed25519_public_key_is_zero(node_id)) {
+    return id == NULL || ed25519_public_key_is_zero(id);
+  } else {
+    return id && ed25519_pubkey_eq(node_id, id);
+  }
+}
+
+/** Return true iff <b>node</b> supports authenticating itself
+ * by ed25519 ID during the link handshake in a way that we can understand
+ * when we probe it. */
+int
+node_supports_ed25519_link_authentication(const node_t *node)
+{
+  /* XXXX Oh hm. What if some day in the future there are link handshake
+   * versions that aren't 3 but which are ed25519 */
+  if (! node_get_ed25519_id(node))
+    return 0;
+  if (node->ri) {
+    const char *protos = node->ri->protocol_list;
+    if (protos == NULL)
+      return 0;
+    return protocol_list_supports_protocol(protos, PRT_LINKAUTH, 3);
+  }
+  if (node->rs) {
+    return node->rs->supports_ed25519_link_handshake;
+  }
+  tor_assert_nonfatal_unreached_once();
+  return 0;
+}
+
+/** Return the RSA ID key's SHA1 digest for the provided node. */
+const uint8_t *
+node_get_rsa_id_digest(const node_t *node)
+{
+  tor_assert(node);
+  return (const uint8_t*)node->identity;
+}
+
+
 /** Return the nickname of <b>node</b>, or NULL if we can't find one. */
 const char *
 node_get_nickname(const node_t *node)
diff --git a/src/or/nodelist.h b/src/or/nodelist.h
index bfee935fe9..8456d21c6c 100644
--- a/src/or/nodelist.h
+++ b/src/or/nodelist.h
@@ -55,6 +55,11 @@ void node_get_address_string(const node_t *node, char *cp, size_t len);
 long node_get_declared_uptime(const node_t *node);
 time_t node_get_published_on(const node_t *node);
 const smartlist_t *node_get_declared_family(const node_t *node);
+const ed25519_public_key_t *node_get_ed25519_id(const node_t *node);
+int node_ed25519_id_matches(const node_t *node,
+                            const ed25519_public_key_t *id);
+int node_supports_ed25519_link_authentication(const node_t *node);
+const uint8_t *node_get_rsa_id_digest(const node_t *node);
 
 int node_has_ipv6_addr(const node_t *node);
 int node_has_ipv6_orport(const node_t *node);
diff --git a/src/or/onion.c b/src/or/onion.c
index a987883802..42b9ca4b18 100644
--- a/src/or/onion.c
+++ b/src/or/onion.c
@@ -76,6 +76,9 @@
 #include "rephist.h"
 #include "router.h"
 
+// trunnel
+#include "ed25519_cert.h"
+
 /** Type for a linked list of circuits that are waiting for a free CPU worker
  * to process a waiting onion handshake. */
 typedef struct onion_queue_t {
@@ -871,13 +874,114 @@ check_extend_cell(const extend_cell_t *cell)
   return check_create_cell(&cell->create_cell, 1);
 }
 
-/** Protocol constants for specifier types in EXTEND2
- * @{
- */
-#define SPECTYPE_IPV4 0
-#define SPECTYPE_IPV6 1
-#define SPECTYPE_LEGACY_ID 2
-/** @} */
+static int
+extend_cell_from_extend1_cell_body(extend_cell_t *cell_out,
+                                   const extend1_cell_body_t *cell)
+{
+  tor_assert(cell_out);
+  tor_assert(cell);
+  memset(cell_out, 0, sizeof(*cell_out));
+  tor_addr_make_unspec(&cell_out->orport_ipv4.addr);
+  tor_addr_make_unspec(&cell_out->orport_ipv6.addr);
+
+  cell_out->cell_type = RELAY_COMMAND_EXTEND;
+  tor_addr_from_ipv4h(&cell_out->orport_ipv4.addr, cell->ipv4addr);
+  cell_out->orport_ipv4.port = cell->port;
+  if (tor_memeq(cell->onionskin, NTOR_CREATE_MAGIC, 16)) {
+    cell_out->create_cell.cell_type = CELL_CREATE2;
+    cell_out->create_cell.handshake_type = ONION_HANDSHAKE_TYPE_NTOR;
+    cell_out->create_cell.handshake_len = NTOR_ONIONSKIN_LEN;
+    memcpy(cell_out->create_cell.onionskin, cell->onionskin + 16,
+           NTOR_ONIONSKIN_LEN);
+  } else {
+    cell_out->create_cell.cell_type = CELL_CREATE;
+    cell_out->create_cell.handshake_type = ONION_HANDSHAKE_TYPE_TAP;
+    cell_out->create_cell.handshake_len = TAP_ONIONSKIN_CHALLENGE_LEN;
+    memcpy(cell_out->create_cell.onionskin, cell->onionskin,
+           TAP_ONIONSKIN_CHALLENGE_LEN);
+  }
+  memcpy(cell_out->node_id, cell->identity, DIGEST_LEN);
+  return 0;
+}
+
+static int
+create_cell_from_create2_cell_body(create_cell_t *cell_out,
+                                   const create2_cell_body_t *cell)
+{
+  tor_assert(cell_out);
+  tor_assert(cell);
+  memset(cell_out, 0, sizeof(create_cell_t));
+  if (BUG(cell->handshake_len > sizeof(cell_out->onionskin))) {
+    /* This should be impossible because there just isn't enough room in the
+     * input cell to make the handshake_len this large and provide a
+     * handshake_data to match. */
+    return -1;
+  }
+
+  cell_out->cell_type = CELL_CREATE2;
+  cell_out->handshake_type = cell->handshake_type;
+  cell_out->handshake_len = cell->handshake_len;
+  memcpy(cell_out->onionskin,
+       create2_cell_body_getconstarray_handshake_data(cell),
+       cell->handshake_len);
+  return 0;
+}
+
+static int
+extend_cell_from_extend2_cell_body(extend_cell_t *cell_out,
+                                   const extend2_cell_body_t *cell)
+{
+  tor_assert(cell_out);
+  tor_assert(cell);
+  int found_ipv4 = 0, found_ipv6 = 0, found_rsa_id = 0, found_ed_id = 0;
+  memset(cell_out, 0, sizeof(*cell_out));
+  tor_addr_make_unspec(&cell_out->orport_ipv4.addr);
+  tor_addr_make_unspec(&cell_out->orport_ipv6.addr);
+  cell_out->cell_type = RELAY_COMMAND_EXTEND2;
+
+  unsigned i;
+  for (i = 0; i < cell->n_spec; ++i) {
+    const link_specifier_t *ls = extend2_cell_body_getconst_ls(cell, i);
+    switch (ls->ls_type) {
+      case LS_IPV4:
+        if (found_ipv4)
+          continue;
+        found_ipv4 = 1;
+        tor_addr_from_ipv4h(&cell_out->orport_ipv4.addr, ls->un_ipv4_addr);
+        cell_out->orport_ipv4.port = ls->un_ipv4_port;
+        break;
+      case LS_IPV6:
+        if (found_ipv6)
+          continue;
+        found_ipv6 = 1;
+        tor_addr_from_ipv6_bytes(&cell_out->orport_ipv6.addr,
+                                 (const char *)ls->un_ipv6_addr);
+        cell_out->orport_ipv6.port = ls->un_ipv6_port;
+        break;
+      case LS_LEGACY_ID:
+        if (found_rsa_id)
+          return -1;
+        found_rsa_id = 1;
+        memcpy(cell_out->node_id, ls->un_legacy_id, 20);
+        break;
+      case LS_ED25519_ID:
+        if (found_ed_id)
+          return -1;
+        found_ed_id = 1;
+        memcpy(cell_out->ed_pubkey.pubkey, ls->un_ed25519_id, 32);
+        break;
+      default:
+        /* Ignore this, whatever it is. */
+        break;
+    }
+  }
+
+  if (!found_rsa_id || !found_ipv4) /* These are mandatory */
+    return -1;
+
+  return create_cell_from_create2_cell_body(&cell_out->create_cell,
+                                            cell->create2);
+}
 
 /** Parse an EXTEND or EXTEND2 cell (according to <b>command</b>) from the
  * <b>payload_length</b> bytes of <b>payload</b> into <b>cell_out</b>. Return
@@ -886,101 +990,44 @@ int
 extend_cell_parse(extend_cell_t *cell_out, const uint8_t command,
                   const uint8_t *payload, size_t payload_length)
 {
-  const uint8_t *eop;
 
-  memset(cell_out, 0, sizeof(*cell_out));
+  tor_assert(cell_out);
+  tor_assert(payload);
+
   if (payload_length > RELAY_PAYLOAD_SIZE)
     return -1;
-  eop = payload + payload_length;
 
   switch (command) {
   case RELAY_COMMAND_EXTEND:
     {
-      if (payload_length != 6 + TAP_ONIONSKIN_CHALLENGE_LEN + DIGEST_LEN)
+      extend1_cell_body_t *cell = NULL;
+      if (extend1_cell_body_parse(&cell, payload, payload_length)<0 ||
+          cell == NULL) {
+        if (cell)
+          extend1_cell_body_free(cell);
         return -1;
-
-      cell_out->cell_type = RELAY_COMMAND_EXTEND;
-      tor_addr_from_ipv4n(&cell_out->orport_ipv4.addr, get_uint32(payload));
-      cell_out->orport_ipv4.port = ntohs(get_uint16(payload+4));
-      tor_addr_make_unspec(&cell_out->orport_ipv6.addr);
-      if (tor_memeq(payload + 6, NTOR_CREATE_MAGIC, 16)) {
-        cell_out->create_cell.cell_type = CELL_CREATE2;
-        cell_out->create_cell.handshake_type = ONION_HANDSHAKE_TYPE_NTOR;
-        cell_out->create_cell.handshake_len = NTOR_ONIONSKIN_LEN;
-        memcpy(cell_out->create_cell.onionskin, payload + 22,
-               NTOR_ONIONSKIN_LEN);
-      } else {
-        cell_out->create_cell.cell_type = CELL_CREATE;
-        cell_out->create_cell.handshake_type = ONION_HANDSHAKE_TYPE_TAP;
-        cell_out->create_cell.handshake_len = TAP_ONIONSKIN_CHALLENGE_LEN;
-        memcpy(cell_out->create_cell.onionskin, payload + 6,
-               TAP_ONIONSKIN_CHALLENGE_LEN);
       }
-      memcpy(cell_out->node_id, payload + 6 + TAP_ONIONSKIN_CHALLENGE_LEN,
-             DIGEST_LEN);
-      break;
+      int r = extend_cell_from_extend1_cell_body(cell_out, cell);
+      extend1_cell_body_free(cell);
+      if (r < 0)
+        return r;
     }
+    break;
   case RELAY_COMMAND_EXTEND2:
     {
-      uint8_t n_specs, spectype, speclen;
-      int i;
-      int found_ipv4 = 0, found_ipv6 = 0, found_id = 0;
-      tor_addr_make_unspec(&cell_out->orport_ipv4.addr);
-      tor_addr_make_unspec(&cell_out->orport_ipv6.addr);
-
-      if (payload_length == 0)
+      extend2_cell_body_t *cell = NULL;
+      if (extend2_cell_body_parse(&cell, payload, payload_length) < 0 ||
+          cell == NULL) {
+        if (cell)
+          extend2_cell_body_free(cell);
         return -1;
-
-      cell_out->cell_type = RELAY_COMMAND_EXTEND2;
-      n_specs = *payload++;
-      /* Parse the specifiers. We'll only take the first IPv4 and first IPv6
-       * address, and the node ID, and ignore everything else */
-      for (i = 0; i < n_specs; ++i) {
-        if (eop - payload < 2)
-          return -1;
-        spectype = payload[0];
-        speclen = payload[1];
-        payload += 2;
-        if (eop - payload < speclen)
-          return -1;
-        switch (spectype) {
-        case SPECTYPE_IPV4:
-          if (speclen != 6)
-            return -1;
-          if (!found_ipv4) {
-            tor_addr_from_ipv4n(&cell_out->orport_ipv4.addr,
-                                get_uint32(payload));
-            cell_out->orport_ipv4.port = ntohs(get_uint16(payload+4));
-            found_ipv4 = 1;
-          }
-          break;
-        case SPECTYPE_IPV6:
-          if (speclen != 18)
-            return -1;
-          if (!found_ipv6) {
-            tor_addr_from_ipv6_bytes(&cell_out->orport_ipv6.addr,
-                                     (const char*)payload);
-            cell_out->orport_ipv6.port = ntohs(get_uint16(payload+16));
-            found_ipv6 = 1;
-          }
-          break;
-        case SPECTYPE_LEGACY_ID:
-          if (speclen != 20)
-            return -1;
-          if (found_id)
-            return -1;
-          memcpy(cell_out->node_id, payload, 20);
-          found_id = 1;
-          break;
-        }
-        payload += speclen;
       }
-      if (!found_id || !found_ipv4)
-        return -1;
-      if (parse_create2_payload(&cell_out->create_cell,payload,eop-payload)<0)
-        return -1;
-      break;
+      int r = extend_cell_from_extend2_cell_body(cell_out, cell);
+      extend2_cell_body_free(cell);
+      if (r < 0)
+        return r;
     }
+    break;
   default:
     return -1;
   }
@@ -992,6 +1039,7 @@ extend_cell_parse(extend_cell_t *cell_out, const uint8_t command,
 static int
 check_extended_cell(const extended_cell_t *cell)
 {
+  tor_assert(cell);
   if (cell->created_cell.cell_type == CELL_CREATED) {
     if (cell->cell_type != RELAY_COMMAND_EXTENDED)
       return -1;
@@ -1013,6 +1061,9 @@ extended_cell_parse(extended_cell_t *cell_out,
                     const uint8_t command, const uint8_t *payload,
                     size_t payload_len)
 {
+  tor_assert(cell_out);
+  tor_assert(payload);
+
   memset(cell_out, 0, sizeof(*cell_out));
   if (payload_len > RELAY_PAYLOAD_SIZE)
     return -1;
@@ -1129,6 +1180,21 @@ created_cell_format(cell_t *cell_out, const created_cell_t *cell_in)
   return 0;
 }
 
+/** Return true iff we are configured (by torrc or by the networkstatus
+ * parameters) to use Ed25519 identities in our Extend2 cells. */
+static int
+should_include_ed25519_id_extend_cells(const networkstatus_t *ns,
+                                       const or_options_t *options)
+{
+  if (options->ExtendByEd25519ID != -1)
+    return options->ExtendByEd25519ID; /* The user has an opinion. */
+
+  return (int) networkstatus_get_param(ns, "ExtendByEd25519ID",
+                                       0 /* default */,
+                                       0 /* min */,
+                                       1 /*max*/);
+}
+
 /** Format the EXTEND{,2} cell in <b>cell_in</b>, storing its relay payload in
  * <b>payload_out</b>, the number of bytes used in *<b>len_out</b>, and the
  * relay command in *<b>command_out</b>. The <b>payload_out</b> must have
@@ -1137,12 +1203,11 @@ int
 extend_cell_format(uint8_t *command_out, uint16_t *len_out,
                    uint8_t *payload_out, const extend_cell_t *cell_in)
 {
-  uint8_t *p, *eop;
+  uint8_t *p;
   if (check_extend_cell(cell_in) < 0)
     return -1;
 
   p = payload_out;
-  eop = payload_out + RELAY_PAYLOAD_SIZE;
 
   memset(p, 0, RELAY_PAYLOAD_SIZE);
 
@@ -1165,33 +1230,56 @@ extend_cell_format(uint8_t *command_out, uint16_t *len_out,
     break;
   case RELAY_COMMAND_EXTEND2:
     {
-      uint8_t n = 2;
+      uint8_t n_specifiers = 2;
       *command_out = RELAY_COMMAND_EXTEND2;
-
-      *p++ = n; /* 2 identifiers */
-      *p++ = SPECTYPE_IPV4; /* First is IPV4. */
-      *p++ = 6; /* It's 6 bytes long. */
-      set_uint32(p, tor_addr_to_ipv4n(&cell_in->orport_ipv4.addr));
-      set_uint16(p+4, htons(cell_in->orport_ipv4.port));
-      p += 6;
-      *p++ = SPECTYPE_LEGACY_ID; /* Next is an identity digest. */
-      *p++ = 20; /* It's 20 bytes long */
-      memcpy(p, cell_in->node_id, DIGEST_LEN);
-      p += 20;
-
-      /* Now we can send the handshake */
-      set_uint16(p, htons(cell_in->create_cell.handshake_type));
-      set_uint16(p+2, htons(cell_in->create_cell.handshake_len));
-      p += 4;
-
-      if (cell_in->create_cell.handshake_len > eop - p)
-        return -1;
-
-      memcpy(p, cell_in->create_cell.onionskin,
+      extend2_cell_body_t *cell = extend2_cell_body_new();
+      link_specifier_t *ls;
+      {
+        /* IPv4 specifier first. */
+        ls = link_specifier_new();
+        extend2_cell_body_add_ls(cell, ls);
+        ls->ls_type = LS_IPV4;
+        ls->ls_len = 6;
+        ls->un_ipv4_addr = tor_addr_to_ipv4h(&cell_in->orport_ipv4.addr);
+        ls->un_ipv4_port = cell_in->orport_ipv4.port;
+      }
+      {
+        /* Then RSA id */
+        ls = link_specifier_new();
+        extend2_cell_body_add_ls(cell, ls);
+        ls->ls_type = LS_LEGACY_ID;
+        ls->ls_len = DIGEST_LEN;
+        memcpy(ls->un_legacy_id, cell_in->node_id, DIGEST_LEN);
+      }
+      if (should_include_ed25519_id_extend_cells(NULL, get_options()) &&
+          !ed25519_public_key_is_zero(&cell_in->ed_pubkey)) {
+        /* Then, maybe, the ed25519 id! */
+        ++n_specifiers;
+        ls = link_specifier_new();
+        extend2_cell_body_add_ls(cell, ls);
+        ls->ls_type = LS_ED25519_ID;
+        ls->ls_len = 32;
+        memcpy(ls->un_ed25519_id, cell_in->ed_pubkey.pubkey, 32);
+      }
+      cell->n_spec = n_specifiers;
+
+      /* Now, the handshake */
+      cell->create2 = create2_cell_body_new();
+      cell->create2->handshake_type = cell_in->create_cell.handshake_type;
+      cell->create2->handshake_len = cell_in->create_cell.handshake_len;
+      create2_cell_body_setlen_handshake_data(cell->create2,
+                                         cell_in->create_cell.handshake_len);
+      memcpy(create2_cell_body_getarray_handshake_data(cell->create2),
+             cell_in->create_cell.onionskin,
              cell_in->create_cell.handshake_len);
 
-      p += cell_in->create_cell.handshake_len;
-      *len_out = p - payload_out;
+      ssize_t len_encoded = extend2_cell_body_encode(
+                             payload_out, RELAY_PAYLOAD_SIZE,
+                             cell);
+      extend2_cell_body_free(cell);
+      if (len_encoded < 0 || len_encoded > UINT16_MAX)
+        return -1;
+      *len_out = (uint16_t) len_encoded;
     }
     break;
   default:
diff --git a/src/or/onion.h b/src/or/onion.h
index 0275fa00d2..19e4a7c381 100644
--- a/src/or/onion.h
+++ b/src/or/onion.h
@@ -85,6 +85,8 @@ typedef struct extend_cell_t {
   tor_addr_port_t orport_ipv6;
   /** Identity fingerprint of the node we're conecting to.*/
   uint8_t node_id[DIGEST_LEN];
+  /** Ed25519 public identity key. Zero if not set. */
+  ed25519_public_key_t ed_pubkey;
   /** The "create cell" embedded in this extend cell. Note that unlike the
    * create cells we generate ourself, this once can have a handshake type we
    * don't recognize. */
diff --git a/src/or/or.h b/src/or/or.h
index eb94f63d5e..7e11bf05aa 100644
--- a/src/or/or.h
+++ b/src/or/or.h
@@ -1581,8 +1581,6 @@ typedef struct or_connection_t {
                     * bandwidthburst. (OPEN ORs only) */
   int write_bucket; /**< When this hits 0, stop writing. Like read_bucket. */
 
-  struct or_connection_t *next_with_same_id; /**< Next connection with same
-                                              * identity digest as this one. */
   /** Last emptied read token bucket in msec since midnight; only used if
    * TB_EMPTY events are enabled. */
   uint32_t read_emptied_time;
@@ -1660,6 +1658,8 @@ typedef struct entry_connection_t {
   edge_connection_t edge_;
 
   /** Nickname of planned exit node -- used with .exit support. */
+  /* XXX prop220: we need to make chosen_exit_name able to encode Ed IDs too.
+   * That's logically part of the UI parts for prop220 though. */
   char *chosen_exit_name;
 
   socks_request_t *socks_request; /**< SOCKS structure describing request (AP
@@ -2710,7 +2710,10 @@ typedef struct {
 typedef struct extend_info_t {
   char nickname[MAX_HEX_NICKNAME_LEN+1]; /**< This router's nickname for
                                           * display. */
-  char identity_digest[DIGEST_LEN]; /**< Hash of this router's identity key. */
+  /** Hash of this router's RSA identity key. */
+  char identity_digest[DIGEST_LEN];
+  /** Ed25519 identity for this router, if any. */
+  ed25519_public_key_t ed_identity;
   uint16_t port; /**< OR port. */
   tor_addr_t addr; /**< IP address. */
   crypto_pk_t *onion_key; /**< Current onionskin key. */
@@ -4570,6 +4573,15 @@ typedef struct {
 
   /** If 1, we skip all OOS checks. */
   int DisableOOSCheck;
+
+  /** Autobool: Should we include Ed25519 identities in extend2 cells?
+   * If -1, we should do whatever the consensus parameter says. */
+  int ExtendByEd25519ID;
+
+  /** Bool (default: 1): When testing routerinfos as a directory authority,
+   * do we enforce Ed25519 identity match? */
+  /* NOTE: remove this option someday. */
+  int AuthDirTestEd25519LinkKeys;
 } or_options_t;
 
 /** Persistent state for an onion router, as saved to disk. */
diff --git a/src/or/router.c b/src/or/router.c
index fd2942ec67..917caaa1f5 100644
--- a/src/or/router.c
+++ b/src/or/router.c
@@ -1312,8 +1312,15 @@ extend_info_from_router(const routerinfo_t *r)
   /* Make sure we don't need to check address reachability */
   tor_assert_nonfatal(router_skip_or_reachability(get_options(), 0));
 
+  const ed25519_public_key_t *ed_id_key;
+  if (r->cache_info.signing_key_cert)
+    ed_id_key = &r->cache_info.signing_key_cert->signing_key;
+  else
+    ed_id_key = NULL;
+
   router_get_prim_orport(r, &ap);
   return extend_info_new(r->nickname, r->cache_info.identity_digest,
+                         ed_id_key,
                          r->onion_pkey, r->onion_curve25519_pkey,
                          &ap.addr, ap.port);
 }
diff --git a/src/or/routerkeys.c b/src/or/routerkeys.c
index 6c53c50305..51802b15e5 100644
--- a/src/or/routerkeys.c
+++ b/src/or/routerkeys.c
@@ -1099,6 +1099,14 @@ get_master_identity_key(void)
   return &master_identity_key->pubkey;
 }
 
+/** Return true iff <b>id</b> is our Ed25519 master identity key. */
+int
+router_ed25519_id_is_me(const ed25519_public_key_t *id)
+{
+  return id && master_identity_key &&
+    ed25519_pubkey_eq(id, &master_identity_key->pubkey);
+}
+
 #ifdef TOR_UNIT_TESTS
 /* only exists for the unit tests, since otherwise the identity key
  * should be used to sign nothing but the signing key. */
diff --git a/src/or/routerkeys.h b/src/or/routerkeys.h
index 307a1cd234..98894cdc0b 100644
--- a/src/or/routerkeys.h
+++ b/src/or/routerkeys.h
@@ -45,6 +45,8 @@ 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);
 
+int router_ed25519_id_is_me(const ed25519_public_key_t *id);
+
 struct tor_cert_st *make_ntor_onion_key_crosscert(
                                   const curve25519_keypair_t *onion_key,
                                   const ed25519_public_key_t *master_id_key,
diff --git a/src/test/test_cell_formats.c b/src/test/test_cell_formats.c
index f839a5b72c..bbcff38d6d 100644
--- a/src/test/test_cell_formats.c
+++ b/src/test/test_cell_formats.c
@@ -11,6 +11,7 @@
 #include "channel.h"
 #include "connection_edge.h"
 #include "connection_or.h"
+#include "config.h"
 #include "onion.h"
 #include "onion_tap.h"
 #include "onion_fast.h"
@@ -698,6 +699,7 @@ test_cfmt_extend_cells(void *arg)
   tt_int_op(61681, OP_EQ, ec.orport_ipv4.port);
   tt_str_op("2002::f0:c51e", OP_EQ, fmt_addr(&ec.orport_ipv6.addr));
   tt_int_op(4370, OP_EQ, ec.orport_ipv6.port);
+  tt_assert(ed25519_public_key_is_zero(&ec.ed_pubkey));
   tt_mem_op(ec.node_id,OP_EQ, "anthropomorphization", 20);
   tt_int_op(cc->cell_type, OP_EQ, CELL_CREATE2);
   tt_int_op(cc->handshake_type, OP_EQ, 0x105);
@@ -717,6 +719,37 @@ test_cfmt_extend_cells(void *arg)
   tt_mem_op(p2+1+8+22+4,OP_EQ, b, 99+20);
   tt_int_op(0, OP_EQ, create_cell_format_relayed(&cell, cc));
 
+  /* Now let's add an ed25519 key to that extend2 cell. */
+  memcpy(ec.ed_pubkey.pubkey,
+         "brownshoesdontmakeit/brownshoesd", 32);
+
+  /* As before, since we aren't extending by ed25519. */
+  get_options_mutable()->ExtendByEd25519ID = 0;
+  tt_int_op(0, OP_EQ, extend_cell_format(&p2_cmd, &p2_len, p2, &ec));
+  tt_int_op(p2_len, OP_EQ, 89+99-34-20);
+  test_memeq_hex(p2,
+                 "02000612F40001F0F1"
+                 "0214616e7468726f706f6d6f727068697a6174696f6e"
+                 "01050063");
+
+  /* Now try with the ed25519 ID. */
+  get_options_mutable()->ExtendByEd25519ID = 1;
+  tt_int_op(0, OP_EQ, extend_cell_format(&p2_cmd, &p2_len, p2, &ec));
+  tt_int_op(p2_len, OP_EQ, 89+99-34-20 + 34);
+  test_memeq_hex(p2,
+                 "03000612F40001F0F1"
+                 "0214616e7468726f706f6d6f727068697a6174696f6e"
+                 // ed digest follows:
+                 "0320" "62726f776e73686f6573646f6e746d616b656"
+                        "9742f62726f776e73686f657364"
+                 "01050063");
+  /* Can we parse that? Did the key come through right? */
+  memset(&ec, 0, sizeof(ec));
+  tt_int_op(0, OP_EQ, extend_cell_parse(&ec, RELAY_COMMAND_EXTEND2,
+                                        p2, p2_len));
+  tt_mem_op("brownshoesdontmakeit/brownshoesd", OP_EQ,
+            ec.ed_pubkey.pubkey, 32);
+
   /* == Now try parsing some junk */
 
   /* Try a too-long handshake */
@@ -1257,7 +1290,7 @@ struct testcase_t cell_format_tests[] = {
   TEST(connected_cells, 0),
   TEST(create_cells, 0),
   TEST(created_cells, 0),
-  TEST(extend_cells, 0),
+  TEST(extend_cells, TT_FORK),
   TEST(extended_cells, 0),
   TEST(resolved_cells, 0),
   TEST(is_destroy, 0),
diff --git a/src/test/test_channel.c b/src/test/test_channel.c
index e87f99ef50..f158b1a495 100644
--- a/src/test/test_channel.c
+++ b/src/test/test_channel.c
@@ -1768,6 +1768,111 @@ test_channel_write(void *arg)
   return;
 }
 
+static void
+test_channel_id_map(void *arg)
+{
+  (void)arg;
+  const int N_CHAN = 6;
+  char rsa_id[N_CHAN][DIGEST_LEN];
+  ed25519_public_key_t *ed_id[N_CHAN];
+  channel_t *chan[N_CHAN];
+  int i;
+  ed25519_public_key_t ed_zero;
+  memset(&ed_zero, 0, sizeof(ed_zero));
+
+  tt_assert(sizeof(rsa_id[0]) == DIGEST_LEN); // Do I remember C?
+
+  for (i = 0; i < N_CHAN; ++i) {
+    crypto_rand(rsa_id[i], DIGEST_LEN);
+    ed_id[i] = tor_malloc_zero(sizeof(*ed_id[i]));
+    crypto_rand((char*)ed_id[i]->pubkey, sizeof(ed_id[i]->pubkey));
+  }
+
+  /* For channel 3, have no Ed identity. */
+  tor_free(ed_id[3]);
+
+  /* Channel 2 and 4 have same ROSA identity */
+  memcpy(rsa_id[4], rsa_id[2], DIGEST_LEN);
+
+  /* Channel 2 and 4 and 5 have same RSA identity */
+  memcpy(rsa_id[4], rsa_id[2], DIGEST_LEN);
+  memcpy(rsa_id[5], rsa_id[2], DIGEST_LEN);
+
+  /* Channels 2 and 5 have same Ed25519 identity */
+  memcpy(ed_id[5], ed_id[2], sizeof(*ed_id[2]));
+
+  for (i = 0; i < N_CHAN; ++i) {
+    chan[i] = new_fake_channel();
+    channel_register(chan[i]);
+    channel_set_identity_digest(chan[i], rsa_id[i], ed_id[i]);
+  }
+
+  /* Lookup by RSA id only */
+  tt_ptr_op(chan[0], OP_EQ,
+            channel_find_by_remote_identity(rsa_id[0], NULL));
+  tt_ptr_op(chan[1], OP_EQ,
+            channel_find_by_remote_identity(rsa_id[1], NULL));
+  tt_ptr_op(chan[3], OP_EQ,
+            channel_find_by_remote_identity(rsa_id[3], NULL));
+  channel_t *ch;
+  ch = channel_find_by_remote_identity(rsa_id[2], NULL);
+  tt_assert(ch == chan[2] || ch == chan[4] || ch == chan[5]);
+  ch = channel_next_with_rsa_identity(ch);
+  tt_assert(ch == chan[2] || ch == chan[4] || ch == chan[5]);
+  ch = channel_next_with_rsa_identity(ch);
+  tt_assert(ch == chan[2] || ch == chan[4] || ch == chan[5]);
+  ch = channel_next_with_rsa_identity(ch);
+  tt_assert(ch == NULL);
+
+  /* As above, but with zero Ed25519 ID (meaning "any ID") */
+  tt_ptr_op(chan[0], OP_EQ,
+            channel_find_by_remote_identity(rsa_id[0], &ed_zero));
+  tt_ptr_op(chan[1], OP_EQ,
+            channel_find_by_remote_identity(rsa_id[1], &ed_zero));
+  tt_ptr_op(chan[3], OP_EQ,
+            channel_find_by_remote_identity(rsa_id[3], &ed_zero));
+  ch = channel_find_by_remote_identity(rsa_id[2], &ed_zero);
+  tt_assert(ch == chan[2] || ch == chan[4] || ch == chan[5]);
+  ch = channel_next_with_rsa_identity(ch);
+  tt_assert(ch == chan[2] || ch == chan[4] || ch == chan[5]);
+  ch = channel_next_with_rsa_identity(ch);
+  tt_assert(ch == chan[2] || ch == chan[4] || ch == chan[5]);
+  ch = channel_next_with_rsa_identity(ch);
+  tt_assert(ch == NULL);
+
+  /* Lookup nonexistent RSA identity */
+  tt_ptr_op(NULL, OP_EQ,
+            channel_find_by_remote_identity("!!!!!!!!!!!!!!!!!!!!", NULL));
+
+  /* Look up by full identity pair */
+  tt_ptr_op(chan[0], OP_EQ,
+            channel_find_by_remote_identity(rsa_id[0], ed_id[0]));
+  tt_ptr_op(chan[1], OP_EQ,
+            channel_find_by_remote_identity(rsa_id[1], ed_id[1]));
+  tt_ptr_op(chan[3], OP_EQ,
+            channel_find_by_remote_identity(rsa_id[3], ed_id[3] /*NULL*/));
+  tt_ptr_op(chan[4], OP_EQ,
+            channel_find_by_remote_identity(rsa_id[4], ed_id[4]));
+  ch = channel_find_by_remote_identity(rsa_id[2], ed_id[2]);
+  tt_assert(ch == chan[2] || ch == chan[5]);
+
+  /* Look up RSA identity with wrong ed25519 identity */
+  tt_ptr_op(NULL, OP_EQ,
+            channel_find_by_remote_identity(rsa_id[4], ed_id[0]));
+  tt_ptr_op(NULL, OP_EQ,
+            channel_find_by_remote_identity(rsa_id[2], ed_id[1]));
+  tt_ptr_op(NULL, OP_EQ,
+            channel_find_by_remote_identity(rsa_id[3], ed_id[1]));
+
+ done:
+  for (i = 0; i < N_CHAN; ++i) {
+    channel_clear_identity_digest(chan[i]);
+    channel_unregister(chan[i]);
+    free_fake_channel(chan[i]);
+    tor_free(ed_id[i]);
+  }
+}
+
 struct testcase_t channel_tests[] = {
   { "dumpstats", test_channel_dumpstats, TT_FORK, NULL, NULL },
   { "flush", test_channel_flush, TT_FORK, NULL, NULL },
@@ -1780,6 +1885,7 @@ struct testcase_t channel_tests[] = {
   { "queue_incoming", test_channel_queue_incoming, TT_FORK, NULL, NULL },
   { "queue_size", test_channel_queue_size, TT_FORK, NULL, NULL },
   { "write", test_channel_write, TT_FORK, NULL, NULL },
+  { "id_map", test_channel_id_map, TT_FORK, NULL, NULL },
   END_OF_TESTCASES
 };
 
diff --git a/src/test/test_link_handshake.c b/src/test/test_link_handshake.c
index 9899e54231..421f3aaedf 100644
--- a/src/test/test_link_handshake.c
+++ b/src/test/test_link_handshake.c
@@ -117,6 +117,9 @@ test_link_handshake_certs_ok(void *arg)
   crypto_pk_t *key1 = NULL, *key2 = NULL;
   const int with_ed = !strcmp((const char *)arg, "Ed25519");
 
+  tor_addr_from_ipv4h(&c1->base_.addr, 0x7f000001);
+  tor_addr_from_ipv4h(&c2->base_.addr, 0x7f000001);
+
   scheduler_init();
 
   MOCK(tor_tls_cert_matches_key, mock_tls_cert_matches_key);
@@ -323,7 +326,7 @@ recv_certs_cleanup(const struct testcase_t *test, void *obj)
   if (d) {
     tor_free(d->cell);
     certs_cell_free(d->ccell);
-    connection_or_remove_from_identity_map(d->c);
+    connection_or_clear_identity(d->c);
     connection_free_(TO_CONN(d->c));
     circuitmux_free(d->chan->base_.cmux);
     tor_free(d->chan);
@@ -354,6 +357,7 @@ recv_certs_setup(const struct testcase_t *test)
   d->chan = tor_malloc_zero(sizeof(*d->chan));
   d->c->chan = d->chan;
   d->c->base_.address = tor_strdup("HaveAnAddress");
+  tor_addr_from_ipv4h(&d->c->base_.addr, 0x801f0127);
   d->c->base_.state = OR_CONN_STATE_OR_HANDSHAKING_V3;
   d->chan->conn = d->c;
   tt_int_op(connection_init_or_handshake_state(d->c, 1), ==, 0);
@@ -1133,8 +1137,8 @@ authenticate_data_cleanup(const struct testcase_t *test, void *arg)
   authenticate_data_t *d = arg;
   if (d) {
     tor_free(d->cell);
-    connection_or_remove_from_identity_map(d->c1);
-    connection_or_remove_from_identity_map(d->c2);
+    connection_or_clear_identity(d->c1);
+    connection_or_clear_identity(d->c2);
     connection_free_(TO_CONN(d->c1));
     connection_free_(TO_CONN(d->c2));
     circuitmux_free(d->chan2->base_.cmux);
diff --git a/src/trunnel/ed25519_cert.c b/src/trunnel/ed25519_cert.c
index dd5088b231..e4e4d68209 100644
--- a/src/trunnel/ed25519_cert.c
+++ b/src/trunnel/ed25519_cert.c
@@ -28,6 +28,281 @@ int edcert_deadcode_dummy__ = 0;
     }                                                            \
   } while (0)
 
+create2_cell_body_t *
+create2_cell_body_new(void)
+{
+  create2_cell_body_t *val = trunnel_calloc(1, sizeof(create2_cell_body_t));
+  if (NULL == val)
+    return NULL;
+  return val;
+}
+
+/** Release all storage held inside 'obj', but do not free 'obj'.
+ */
+static void
+create2_cell_body_clear(create2_cell_body_t *obj)
+{
+  (void) obj;
+  TRUNNEL_DYNARRAY_WIPE(&obj->handshake_data);
+  TRUNNEL_DYNARRAY_CLEAR(&obj->handshake_data);
+}
+
+void
+create2_cell_body_free(create2_cell_body_t *obj)
+{
+  if (obj == NULL)
+    return;
+  create2_cell_body_clear(obj);
+  trunnel_memwipe(obj, sizeof(create2_cell_body_t));
+  trunnel_free_(obj);
+}
+
+uint16_t
+create2_cell_body_get_handshake_type(create2_cell_body_t *inp)
+{
+  return inp->handshake_type;
+}
+int
+create2_cell_body_set_handshake_type(create2_cell_body_t *inp, uint16_t val)
+{
+  inp->handshake_type = val;
+  return 0;
+}
+uint16_t
+create2_cell_body_get_handshake_len(create2_cell_body_t *inp)
+{
+  return inp->handshake_len;
+}
+int
+create2_cell_body_set_handshake_len(create2_cell_body_t *inp, uint16_t val)
+{
+  inp->handshake_len = val;
+  return 0;
+}
+size_t
+create2_cell_body_getlen_handshake_data(const create2_cell_body_t *inp)
+{
+  return TRUNNEL_DYNARRAY_LEN(&inp->handshake_data);
+}
+
+uint8_t
+create2_cell_body_get_handshake_data(create2_cell_body_t *inp, size_t idx)
+{
+  return TRUNNEL_DYNARRAY_GET(&inp->handshake_data, idx);
+}
+
+uint8_t
+create2_cell_body_getconst_handshake_data(const create2_cell_body_t *inp, size_t idx)
+{
+  return create2_cell_body_get_handshake_data((create2_cell_body_t*)inp, idx);
+}
+int
+create2_cell_body_set_handshake_data(create2_cell_body_t *inp, size_t idx, uint8_t elt)
+{
+  TRUNNEL_DYNARRAY_SET(&inp->handshake_data, idx, elt);
+  return 0;
+}
+int
+create2_cell_body_add_handshake_data(create2_cell_body_t *inp, uint8_t elt)
+{
+#if SIZE_MAX >= UINT16_MAX
+  if (inp->handshake_data.n_ == UINT16_MAX)
+    goto trunnel_alloc_failed;
+#endif
+  TRUNNEL_DYNARRAY_ADD(uint8_t, &inp->handshake_data, elt, {});
+  return 0;
+ trunnel_alloc_failed:
+  TRUNNEL_SET_ERROR_CODE(inp);
+  return -1;
+}
+
+uint8_t *
+create2_cell_body_getarray_handshake_data(create2_cell_body_t *inp)
+{
+  return inp->handshake_data.elts_;
+}
+const uint8_t  *
+create2_cell_body_getconstarray_handshake_data(const create2_cell_body_t *inp)
+{
+  return (const uint8_t  *)create2_cell_body_getarray_handshake_data((create2_cell_body_t*)inp);
+}
+int
+create2_cell_body_setlen_handshake_data(create2_cell_body_t *inp, size_t newlen)
+{
+  uint8_t *newptr;
+#if UINT16_MAX < SIZE_MAX
+  if (newlen > UINT16_MAX)
+    goto trunnel_alloc_failed;
+#endif
+  newptr = trunnel_dynarray_setlen(&inp->handshake_data.allocated_,
+                 &inp->handshake_data.n_, inp->handshake_data.elts_, newlen,
+                 sizeof(inp->handshake_data.elts_[0]), (trunnel_free_fn_t) NULL,
+                 &inp->trunnel_error_code_);
+  if (newlen != 0 && newptr == NULL)
+    goto trunnel_alloc_failed;
+  inp->handshake_data.elts_ = newptr;
+  return 0;
+ trunnel_alloc_failed:
+  TRUNNEL_SET_ERROR_CODE(inp);
+  return -1;
+}
+const char *
+create2_cell_body_check(const create2_cell_body_t *obj)
+{
+  if (obj == NULL)
+    return "Object was NULL";
+  if (obj->trunnel_error_code_)
+    return "A set function failed on this object";
+  if (TRUNNEL_DYNARRAY_LEN(&obj->handshake_data) != obj->handshake_len)
+    return "Length mismatch for handshake_data";
+  return NULL;
+}
+
+ssize_t
+create2_cell_body_encoded_len(const create2_cell_body_t *obj)
+{
+  ssize_t result = 0;
+
+  if (NULL != create2_cell_body_check(obj))
+     return -1;
+
+
+  /* Length of u16 handshake_type */
+  result += 2;
+
+  /* Length of u16 handshake_len */
+  result += 2;
+
+  /* Length of u8 handshake_data[handshake_len] */
+  result += TRUNNEL_DYNARRAY_LEN(&obj->handshake_data);
+  return result;
+}
+int
+create2_cell_body_clear_errors(create2_cell_body_t *obj)
+{
+  int r = obj->trunnel_error_code_;
+  obj->trunnel_error_code_ = 0;
+  return r;
+}
+ssize_t
+create2_cell_body_encode(uint8_t *output, const size_t avail, const create2_cell_body_t *obj)
+{
+  ssize_t result = 0;
+  size_t written = 0;
+  uint8_t *ptr = output;
+  const char *msg;
+#ifdef TRUNNEL_CHECK_ENCODED_LEN
+  const ssize_t encoded_len = create2_cell_body_encoded_len(obj);
+#endif
+
+  if (NULL != (msg = create2_cell_body_check(obj)))
+    goto check_failed;
+
+#ifdef TRUNNEL_CHECK_ENCODED_LEN
+  trunnel_assert(encoded_len >= 0);
+#endif
+
+  /* Encode u16 handshake_type */
+  trunnel_assert(written <= avail);
+  if (avail - written < 2)
+    goto truncated;
+  trunnel_set_uint16(ptr, trunnel_htons(obj->handshake_type));
+  written += 2; ptr += 2;
+
+  /* Encode u16 handshake_len */
+  trunnel_assert(written <= avail);
+  if (avail - written < 2)
+    goto truncated;
+  trunnel_set_uint16(ptr, trunnel_htons(obj->handshake_len));
+  written += 2; ptr += 2;
+
+  /* Encode u8 handshake_data[handshake_len] */
+  {
+    size_t elt_len = TRUNNEL_DYNARRAY_LEN(&obj->handshake_data);
+    trunnel_assert(obj->handshake_len == elt_len);
+    trunnel_assert(written <= avail);
+    if (avail - written < elt_len)
+      goto truncated;
+    if (elt_len)
+      memcpy(ptr, obj->handshake_data.elts_, elt_len);
+    written += elt_len; ptr += elt_len;
+  }
+
+
+  trunnel_assert(ptr == output + written);
+#ifdef TRUNNEL_CHECK_ENCODED_LEN
+  {
+    trunnel_assert(encoded_len >= 0);
+    trunnel_assert((size_t)encoded_len == written);
+  }
+
+#endif
+
+  return written;
+
+ truncated:
+  result = -2;
+  goto fail;
+ check_failed:
+  (void)msg;
+  result = -1;
+  goto fail;
+ fail:
+  trunnel_assert(result < 0);
+  return result;
+}
+
+/** As create2_cell_body_parse(), but do not allocate the output
+ * object.
+ */
+static ssize_t
+create2_cell_body_parse_into(create2_cell_body_t *obj, const uint8_t *input, const size_t len_in)
+{
+  const uint8_t *ptr = input;
+  size_t remaining = len_in;
+  ssize_t result = 0;
+  (void)result;
+
+  /* Parse u16 handshake_type */
+  CHECK_REMAINING(2, truncated);
+  obj->handshake_type = trunnel_ntohs(trunnel_get_uint16(ptr));
+  remaining -= 2; ptr += 2;
+
+  /* Parse u16 handshake_len */
+  CHECK_REMAINING(2, truncated);
+  obj->handshake_len = trunnel_ntohs(trunnel_get_uint16(ptr));
+  remaining -= 2; ptr += 2;
+
+  /* Parse u8 handshake_data[handshake_len] */
+  CHECK_REMAINING(obj->handshake_len, truncated);
+  TRUNNEL_DYNARRAY_EXPAND(uint8_t, &obj->handshake_data, obj->handshake_len, {});
+  obj->handshake_data.n_ = obj->handshake_len;
+  if (obj->handshake_len)
+    memcpy(obj->handshake_data.elts_, ptr, obj->handshake_len);
+  ptr += obj->handshake_len; remaining -= obj->handshake_len;
+  trunnel_assert(ptr + remaining == input + len_in);
+  return len_in - remaining;
+
+ truncated:
+  return -2;
+ trunnel_alloc_failed:
+  return -1;
+}
+
+ssize_t
+create2_cell_body_parse(create2_cell_body_t **output, const uint8_t *input, const size_t len_in)
+{
+  ssize_t result;
+  *output = create2_cell_body_new();
+  if (NULL == *output)
+    return -1;
+  result = create2_cell_body_parse_into(*output, input, len_in);
+  if (result < 0) {
+    create2_cell_body_free(*output);
+    *output = NULL;
+  }
+  return result;
+}
 ed25519_cert_extension_t *
 ed25519_cert_extension_new(void)
 {
@@ -430,6 +705,287 @@ ed25519_cert_extension_parse(ed25519_cert_extension_t **output, const uint8_t *i
   }
   return result;
 }
+extend1_cell_body_t *
+extend1_cell_body_new(void)
+{
+  extend1_cell_body_t *val = trunnel_calloc(1, sizeof(extend1_cell_body_t));
+  if (NULL == val)
+    return NULL;
+  return val;
+}
+
+/** Release all storage held inside 'obj', but do not free 'obj'.
+ */
+static void
+extend1_cell_body_clear(extend1_cell_body_t *obj)
+{
+  (void) obj;
+}
+
+void
+extend1_cell_body_free(extend1_cell_body_t *obj)
+{
+  if (obj == NULL)
+    return;
+  extend1_cell_body_clear(obj);
+  trunnel_memwipe(obj, sizeof(extend1_cell_body_t));
+  trunnel_free_(obj);
+}
+
+uint32_t
+extend1_cell_body_get_ipv4addr(extend1_cell_body_t *inp)
+{
+  return inp->ipv4addr;
+}
+int
+extend1_cell_body_set_ipv4addr(extend1_cell_body_t *inp, uint32_t val)
+{
+  inp->ipv4addr = val;
+  return 0;
+}
+uint16_t
+extend1_cell_body_get_port(extend1_cell_body_t *inp)
+{
+  return inp->port;
+}
+int
+extend1_cell_body_set_port(extend1_cell_body_t *inp, uint16_t val)
+{
+  inp->port = val;
+  return 0;
+}
+size_t
+extend1_cell_body_getlen_onionskin(const extend1_cell_body_t *inp)
+{
+  (void)inp;  return 186;
+}
+
+uint8_t
+extend1_cell_body_get_onionskin(extend1_cell_body_t *inp, size_t idx)
+{
+  trunnel_assert(idx < 186);
+  return inp->onionskin[idx];
+}
+
+uint8_t
+extend1_cell_body_getconst_onionskin(const extend1_cell_body_t *inp, size_t idx)
+{
+  return extend1_cell_body_get_onionskin((extend1_cell_body_t*)inp, idx);
+}
+int
+extend1_cell_body_set_onionskin(extend1_cell_body_t *inp, size_t idx, uint8_t elt)
+{
+  trunnel_assert(idx < 186);
+  inp->onionskin[idx] = elt;
+  return 0;
+}
+
+uint8_t *
+extend1_cell_body_getarray_onionskin(extend1_cell_body_t *inp)
+{
+  return inp->onionskin;
+}
+const uint8_t  *
+extend1_cell_body_getconstarray_onionskin(const extend1_cell_body_t *inp)
+{
+  return (const uint8_t  *)extend1_cell_body_getarray_onionskin((extend1_cell_body_t*)inp);
+}
+size_t
+extend1_cell_body_getlen_identity(const extend1_cell_body_t *inp)
+{
+  (void)inp;  return 20;
+}
+
+uint8_t
+extend1_cell_body_get_identity(extend1_cell_body_t *inp, size_t idx)
+{
+  trunnel_assert(idx < 20);
+  return inp->identity[idx];
+}
+
+uint8_t
+extend1_cell_body_getconst_identity(const extend1_cell_body_t *inp, size_t idx)
+{
+  return extend1_cell_body_get_identity((extend1_cell_body_t*)inp, idx);
+}
+int
+extend1_cell_body_set_identity(extend1_cell_body_t *inp, size_t idx, uint8_t elt)
+{
+  trunnel_assert(idx < 20);
+  inp->identity[idx] = elt;
+  return 0;
+}
+
+uint8_t *
+extend1_cell_body_getarray_identity(extend1_cell_body_t *inp)
+{
+  return inp->identity;
+}
+const uint8_t  *
+extend1_cell_body_getconstarray_identity(const extend1_cell_body_t *inp)
+{
+  return (const uint8_t  *)extend1_cell_body_getarray_identity((extend1_cell_body_t*)inp);
+}
+const char *
+extend1_cell_body_check(const extend1_cell_body_t *obj)
+{
+  if (obj == NULL)
+    return "Object was NULL";
+  if (obj->trunnel_error_code_)
+    return "A set function failed on this object";
+  return NULL;
+}
+
+ssize_t
+extend1_cell_body_encoded_len(const extend1_cell_body_t *obj)
+{
+  ssize_t result = 0;
+
+  if (NULL != extend1_cell_body_check(obj))
+     return -1;
+
+
+  /* Length of u32 ipv4addr */
+  result += 4;
+
+  /* Length of u16 port */
+  result += 2;
+
+  /* Length of u8 onionskin[186] */
+  result += 186;
+
+  /* Length of u8 identity[20] */
+  result += 20;
+  return result;
+}
+int
+extend1_cell_body_clear_errors(extend1_cell_body_t *obj)
+{
+  int r = obj->trunnel_error_code_;
+  obj->trunnel_error_code_ = 0;
+  return r;
+}
+ssize_t
+extend1_cell_body_encode(uint8_t *output, const size_t avail, const extend1_cell_body_t *obj)
+{
+  ssize_t result = 0;
+  size_t written = 0;
+  uint8_t *ptr = output;
+  const char *msg;
+#ifdef TRUNNEL_CHECK_ENCODED_LEN
+  const ssize_t encoded_len = extend1_cell_body_encoded_len(obj);
+#endif
+
+  if (NULL != (msg = extend1_cell_body_check(obj)))
+    goto check_failed;
+
+#ifdef TRUNNEL_CHECK_ENCODED_LEN
+  trunnel_assert(encoded_len >= 0);
+#endif
+
+  /* Encode u32 ipv4addr */
+  trunnel_assert(written <= avail);
+  if (avail - written < 4)
+    goto truncated;
+  trunnel_set_uint32(ptr, trunnel_htonl(obj->ipv4addr));
+  written += 4; ptr += 4;
+
+  /* Encode u16 port */
+  trunnel_assert(written <= avail);
+  if (avail - written < 2)
+    goto truncated;
+  trunnel_set_uint16(ptr, trunnel_htons(obj->port));
+  written += 2; ptr += 2;
+
+  /* Encode u8 onionskin[186] */
+  trunnel_assert(written <= avail);
+  if (avail - written < 186)
+    goto truncated;
+  memcpy(ptr, obj->onionskin, 186);
+  written += 186; ptr += 186;
+
+  /* Encode u8 identity[20] */
+  trunnel_assert(written <= avail);
+  if (avail - written < 20)
+    goto truncated;
+  memcpy(ptr, obj->identity, 20);
+  written += 20; ptr += 20;
+
+
+  trunnel_assert(ptr == output + written);
+#ifdef TRUNNEL_CHECK_ENCODED_LEN
+  {
+    trunnel_assert(encoded_len >= 0);
+    trunnel_assert((size_t)encoded_len == written);
+  }
+
+#endif
+
+  return written;
+
+ truncated:
+  result = -2;
+  goto fail;
+ check_failed:
+  (void)msg;
+  result = -1;
+  goto fail;
+ fail:
+  trunnel_assert(result < 0);
+  return result;
+}
+
+/** As extend1_cell_body_parse(), but do not allocate the output
+ * object.
+ */
+static ssize_t
+extend1_cell_body_parse_into(extend1_cell_body_t *obj, const uint8_t *input, const size_t len_in)
+{
+  const uint8_t *ptr = input;
+  size_t remaining = len_in;
+  ssize_t result = 0;
+  (void)result;
+
+  /* Parse u32 ipv4addr */
+  CHECK_REMAINING(4, truncated);
+  obj->ipv4addr = trunnel_ntohl(trunnel_get_uint32(ptr));
+  remaining -= 4; ptr += 4;
+
+  /* Parse u16 port */
+  CHECK_REMAINING(2, truncated);
+  obj->port = trunnel_ntohs(trunnel_get_uint16(ptr));
+  remaining -= 2; ptr += 2;
+
+  /* Parse u8 onionskin[186] */
+  CHECK_REMAINING(186, truncated);
+  memcpy(obj->onionskin, ptr, 186);
+  remaining -= 186; ptr += 186;
+
+  /* Parse u8 identity[20] */
+  CHECK_REMAINING(20, truncated);
+  memcpy(obj->identity, ptr, 20);
+  remaining -= 20; ptr += 20;
+  trunnel_assert(ptr + remaining == input + len_in);
+  return len_in - remaining;
+
+ truncated:
+  return -2;
+}
+
+ssize_t
+extend1_cell_body_parse(extend1_cell_body_t **output, const uint8_t *input, const size_t len_in)
+{
+  ssize_t result;
+  *output = extend1_cell_body_new();
+  if (NULL == *output)
+    return -1;
+  result = extend1_cell_body_parse_into(*output, input, len_in);
+  if (result < 0) {
+    extend1_cell_body_free(*output);
+    *output = NULL;
+  }
+  return result;
+}
 link_specifier_t *
 link_specifier_new(void)
 {
@@ -1528,6 +2084,343 @@ ed25519_cert_parse(ed25519_cert_t **output, const uint8_t *input, const size_t l
   }
   return result;
 }
+extend2_cell_body_t *
+extend2_cell_body_new(void)
+{
+  extend2_cell_body_t *val = trunnel_calloc(1, sizeof(extend2_cell_body_t));
+  if (NULL == val)
+    return NULL;
+  return val;
+}
+
+/** Release all storage held inside 'obj', but do not free 'obj'.
+ */
+static void
+extend2_cell_body_clear(extend2_cell_body_t *obj)
+{
+  (void) obj;
+  {
+
+    unsigned idx;
+    for (idx = 0; idx < TRUNNEL_DYNARRAY_LEN(&obj->ls); ++idx) {
+      link_specifier_free(TRUNNEL_DYNARRAY_GET(&obj->ls, idx));
+    }
+  }
+  TRUNNEL_DYNARRAY_WIPE(&obj->ls);
+  TRUNNEL_DYNARRAY_CLEAR(&obj->ls);
+  create2_cell_body_free(obj->create2);
+  obj->create2 = NULL;
+}
+
+void
+extend2_cell_body_free(extend2_cell_body_t *obj)
+{
+  if (obj == NULL)
+    return;
+  extend2_cell_body_clear(obj);
+  trunnel_memwipe(obj, sizeof(extend2_cell_body_t));
+  trunnel_free_(obj);
+}
+
+uint8_t
+extend2_cell_body_get_n_spec(extend2_cell_body_t *inp)
+{
+  return inp->n_spec;
+}
+int
+extend2_cell_body_set_n_spec(extend2_cell_body_t *inp, uint8_t val)
+{
+  inp->n_spec = val;
+  return 0;
+}
+size_t
+extend2_cell_body_getlen_ls(const extend2_cell_body_t *inp)
+{
+  return TRUNNEL_DYNARRAY_LEN(&inp->ls);
+}
+
+struct link_specifier_st *
+extend2_cell_body_get_ls(extend2_cell_body_t *inp, size_t idx)
+{
+  return TRUNNEL_DYNARRAY_GET(&inp->ls, idx);
+}
+
+ const struct link_specifier_st *
+extend2_cell_body_getconst_ls(const extend2_cell_body_t *inp, size_t idx)
+{
+  return extend2_cell_body_get_ls((extend2_cell_body_t*)inp, idx);
+}
+int
+extend2_cell_body_set_ls(extend2_cell_body_t *inp, size_t idx, struct link_specifier_st * elt)
+{
+  link_specifier_t *oldval = TRUNNEL_DYNARRAY_GET(&inp->ls, idx);
+  if (oldval && oldval != elt)
+    link_specifier_free(oldval);
+  return extend2_cell_body_set0_ls(inp, idx, elt);
+}
+int
+extend2_cell_body_set0_ls(extend2_cell_body_t *inp, size_t idx, struct link_specifier_st * elt)
+{
+  TRUNNEL_DYNARRAY_SET(&inp->ls, idx, elt);
+  return 0;
+}
+int
+extend2_cell_body_add_ls(extend2_cell_body_t *inp, struct link_specifier_st * elt)
+{
+#if SIZE_MAX >= UINT8_MAX
+  if (inp->ls.n_ == UINT8_MAX)
+    goto trunnel_alloc_failed;
+#endif
+  TRUNNEL_DYNARRAY_ADD(struct link_specifier_st *, &inp->ls, elt, {});
+  return 0;
+ trunnel_alloc_failed:
+  TRUNNEL_SET_ERROR_CODE(inp);
+  return -1;
+}
+
+struct link_specifier_st * *
+extend2_cell_body_getarray_ls(extend2_cell_body_t *inp)
+{
+  return inp->ls.elts_;
+}
+const struct link_specifier_st *  const  *
+extend2_cell_body_getconstarray_ls(const extend2_cell_body_t *inp)
+{
+  return (const struct link_specifier_st *  const  *)extend2_cell_body_getarray_ls((extend2_cell_body_t*)inp);
+}
+int
+extend2_cell_body_setlen_ls(extend2_cell_body_t *inp, size_t newlen)
+{
+  struct link_specifier_st * *newptr;
+#if UINT8_MAX < SIZE_MAX
+  if (newlen > UINT8_MAX)
+    goto trunnel_alloc_failed;
+#endif
+  newptr = trunnel_dynarray_setlen(&inp->ls.allocated_,
+                 &inp->ls.n_, inp->ls.elts_, newlen,
+                 sizeof(inp->ls.elts_[0]), (trunnel_free_fn_t) link_specifier_free,
+                 &inp->trunnel_error_code_);
+  if (newlen != 0 && newptr == NULL)
+    goto trunnel_alloc_failed;
+  inp->ls.elts_ = newptr;
+  return 0;
+ trunnel_alloc_failed:
+  TRUNNEL_SET_ERROR_CODE(inp);
+  return -1;
+}
+struct create2_cell_body_st *
+extend2_cell_body_get_create2(extend2_cell_body_t *inp)
+{
+  return inp->create2;
+}
+const struct create2_cell_body_st *
+extend2_cell_body_getconst_create2(const extend2_cell_body_t *inp)
+{
+  return extend2_cell_body_get_create2((extend2_cell_body_t*) inp);
+}
+int
+extend2_cell_body_set_create2(extend2_cell_body_t *inp, struct create2_cell_body_st *val)
+{
+  if (inp->create2 && inp->create2 != val)
+    create2_cell_body_free(inp->create2);
+  return extend2_cell_body_set0_create2(inp, val);
+}
+int
+extend2_cell_body_set0_create2(extend2_cell_body_t *inp, struct create2_cell_body_st *val)
+{
+  inp->create2 = val;
+  return 0;
+}
+const char *
+extend2_cell_body_check(const extend2_cell_body_t *obj)
+{
+  if (obj == NULL)
+    return "Object was NULL";
+  if (obj->trunnel_error_code_)
+    return "A set function failed on this object";
+  {
+    const char *msg;
+
+    unsigned idx;
+    for (idx = 0; idx < TRUNNEL_DYNARRAY_LEN(&obj->ls); ++idx) {
+      if (NULL != (msg = link_specifier_check(TRUNNEL_DYNARRAY_GET(&obj->ls, idx))))
+        return msg;
+    }
+  }
+  if (TRUNNEL_DYNARRAY_LEN(&obj->ls) != obj->n_spec)
+    return "Length mismatch for ls";
+  {
+    const char *msg;
+    if (NULL != (msg = create2_cell_body_check(obj->create2)))
+      return msg;
+  }
+  return NULL;
+}
+
+ssize_t
+extend2_cell_body_encoded_len(const extend2_cell_body_t *obj)
+{
+  ssize_t result = 0;
+
+  if (NULL != extend2_cell_body_check(obj))
+     return -1;
+
+
+  /* Length of u8 n_spec */
+  result += 1;
+
+  /* Length of struct link_specifier ls[n_spec] */
+  {
+
+    unsigned idx;
+    for (idx = 0; idx < TRUNNEL_DYNARRAY_LEN(&obj->ls); ++idx) {
+      result += link_specifier_encoded_len(TRUNNEL_DYNARRAY_GET(&obj->ls, idx));
+    }
+  }
+
+  /* Length of struct create2_cell_body create2 */
+  result += create2_cell_body_encoded_len(obj->create2);
+  return result;
+}
+int
+extend2_cell_body_clear_errors(extend2_cell_body_t *obj)
+{
+  int r = obj->trunnel_error_code_;
+  obj->trunnel_error_code_ = 0;
+  return r;
+}
+ssize_t
+extend2_cell_body_encode(uint8_t *output, const size_t avail, const extend2_cell_body_t *obj)
+{
+  ssize_t result = 0;
+  size_t written = 0;
+  uint8_t *ptr = output;
+  const char *msg;
+#ifdef TRUNNEL_CHECK_ENCODED_LEN
+  const ssize_t encoded_len = extend2_cell_body_encoded_len(obj);
+#endif
+
+  if (NULL != (msg = extend2_cell_body_check(obj)))
+    goto check_failed;
+
+#ifdef TRUNNEL_CHECK_ENCODED_LEN
+  trunnel_assert(encoded_len >= 0);
+#endif
+
+  /* Encode u8 n_spec */
+  trunnel_assert(written <= avail);
+  if (avail - written < 1)
+    goto truncated;
+  trunnel_set_uint8(ptr, (obj->n_spec));
+  written += 1; ptr += 1;
+
+  /* Encode struct link_specifier ls[n_spec] */
+  {
+
+    unsigned idx;
+    for (idx = 0; idx < TRUNNEL_DYNARRAY_LEN(&obj->ls); ++idx) {
+      trunnel_assert(written <= avail);
+      result = link_specifier_encode(ptr, avail - written, TRUNNEL_DYNARRAY_GET(&obj->ls, idx));
+      if (result < 0)
+        goto fail; /* XXXXXXX !*/
+      written += result; ptr += result;
+    }
+  }
+
+  /* Encode struct create2_cell_body create2 */
+  trunnel_assert(written <= avail);
+  result = create2_cell_body_encode(ptr, avail - written, obj->create2);
+  if (result < 0)
+    goto fail; /* XXXXXXX !*/
+  written += result; ptr += result;
+
+
+  trunnel_assert(ptr == output + written);
+#ifdef TRUNNEL_CHECK_ENCODED_LEN
+  {
+    trunnel_assert(encoded_len >= 0);
+    trunnel_assert((size_t)encoded_len == written);
+  }
+
+#endif
+
+  return written;
+
+ truncated:
+  result = -2;
+  goto fail;
+ check_failed:
+  (void)msg;
+  result = -1;
+  goto fail;
+ fail:
+  trunnel_assert(result < 0);
+  return result;
+}
+
+/** As extend2_cell_body_parse(), but do not allocate the output
+ * object.
+ */
+static ssize_t
+extend2_cell_body_parse_into(extend2_cell_body_t *obj, const uint8_t *input, const size_t len_in)
+{
+  const uint8_t *ptr = input;
+  size_t remaining = len_in;
+  ssize_t result = 0;
+  (void)result;
+
+  /* Parse u8 n_spec */
+  CHECK_REMAINING(1, truncated);
+  obj->n_spec = (trunnel_get_uint8(ptr));
+  remaining -= 1; ptr += 1;
+
+  /* Parse struct link_specifier ls[n_spec] */
+  TRUNNEL_DYNARRAY_EXPAND(link_specifier_t *, &obj->ls, obj->n_spec, {});
+  {
+    link_specifier_t * elt;
+    unsigned idx;
+    for (idx = 0; idx < obj->n_spec; ++idx) {
+      result = link_specifier_parse(&elt, ptr, remaining);
+      if (result < 0)
+        goto relay_fail;
+      trunnel_assert((size_t)result <= remaining);
+      remaining -= result; ptr += result;
+      TRUNNEL_DYNARRAY_ADD(link_specifier_t *, &obj->ls, elt, {link_specifier_free(elt);});
+    }
+  }
+
+  /* Parse struct create2_cell_body create2 */
+  result = create2_cell_body_parse(&obj->create2, ptr, remaining);
+  if (result < 0)
+    goto relay_fail;
+  trunnel_assert((size_t)result <= remaining);
+  remaining -= result; ptr += result;
+  trunnel_assert(ptr + remaining == input + len_in);
+  return len_in - remaining;
+
+ truncated:
+  return -2;
+ relay_fail:
+  trunnel_assert(result < 0);
+  return result;
+ trunnel_alloc_failed:
+  return -1;
+}
+
+ssize_t
+extend2_cell_body_parse(extend2_cell_body_t **output, const uint8_t *input, const size_t len_in)
+{
+  ssize_t result;
+  *output = extend2_cell_body_new();
+  if (NULL == *output)
+    return -1;
+  result = extend2_cell_body_parse_into(*output, input, len_in);
+  if (result < 0) {
+    extend2_cell_body_free(*output);
+    *output = NULL;
+  }
+  return result;
+}
 link_specifier_list_t *
 link_specifier_list_new(void)
 {
diff --git a/src/trunnel/ed25519_cert.h b/src/trunnel/ed25519_cert.h
index 571e6d1a53..7cb1e9aa00 100644
--- a/src/trunnel/ed25519_cert.h
+++ b/src/trunnel/ed25519_cert.h
@@ -14,6 +14,15 @@
 #define LS_IPV6 1
 #define LS_LEGACY_ID 2
 #define LS_ED25519_ID 3
+#if !defined(TRUNNEL_OPAQUE) && !defined(TRUNNEL_OPAQUE_CREATE2_CELL_BODY)
+struct create2_cell_body_st {
+  uint16_t handshake_type;
+  uint16_t handshake_len;
+  TRUNNEL_DYNARRAY_HEAD(, uint8_t) handshake_data;
+  uint8_t trunnel_error_code_;
+};
+#endif
+typedef struct create2_cell_body_st create2_cell_body_t;
 #if !defined(TRUNNEL_OPAQUE) && !defined(TRUNNEL_OPAQUE_ED25519_CERT_EXTENSION)
 struct ed25519_cert_extension_st {
   uint16_t ext_length;
@@ -25,6 +34,16 @@ struct ed25519_cert_extension_st {
 };
 #endif
 typedef struct ed25519_cert_extension_st ed25519_cert_extension_t;
+#if !defined(TRUNNEL_OPAQUE) && !defined(TRUNNEL_OPAQUE_EXTEND1_CELL_BODY)
+struct extend1_cell_body_st {
+  uint32_t ipv4addr;
+  uint16_t port;
+  uint8_t onionskin[186];
+  uint8_t identity[20];
+  uint8_t trunnel_error_code_;
+};
+#endif
+typedef struct extend1_cell_body_st extend1_cell_body_t;
 #if !defined(TRUNNEL_OPAQUE) && !defined(TRUNNEL_OPAQUE_LINK_SPECIFIER)
 struct link_specifier_st {
   uint8_t ls_type;
@@ -54,6 +73,15 @@ struct ed25519_cert_st {
 };
 #endif
 typedef struct ed25519_cert_st ed25519_cert_t;
+#if !defined(TRUNNEL_OPAQUE) && !defined(TRUNNEL_OPAQUE_EXTEND2_CELL_BODY)
+struct extend2_cell_body_st {
+  uint8_t n_spec;
+  TRUNNEL_DYNARRAY_HEAD(, struct link_specifier_st *) ls;
+  struct create2_cell_body_st *create2;
+  uint8_t trunnel_error_code_;
+};
+#endif
+typedef struct extend2_cell_body_st extend2_cell_body_t;
 #if !defined(TRUNNEL_OPAQUE) && !defined(TRUNNEL_OPAQUE_LINK_SPECIFIER_LIST)
 struct link_specifier_list_st {
   uint8_t n_spec;
@@ -62,6 +90,95 @@ struct link_specifier_list_st {
 };
 #endif
 typedef struct link_specifier_list_st link_specifier_list_t;
+/** Return a newly allocated create2_cell_body with all elements set
+ * to zero.
+ */
+create2_cell_body_t *create2_cell_body_new(void);
+/** Release all storage held by the create2_cell_body in 'victim'. (Do
+ * nothing if 'victim' is NULL.)
+ */
+void create2_cell_body_free(create2_cell_body_t *victim);
+/** Try to parse a create2_cell_body from the buffer in 'input', using
+ * up to 'len_in' bytes from the input buffer. On success, return the
+ * number of bytes consumed and set *output to the newly allocated
+ * create2_cell_body_t. On failure, return -2 if the input appears
+ * truncated, and -1 if the input is otherwise invalid.
+ */
+ssize_t create2_cell_body_parse(create2_cell_body_t **output, const uint8_t *input, const size_t len_in);
+/** Return the number of bytes we expect to need to encode the
+ * create2_cell_body in 'obj'. On failure, return a negative value.
+ * Note that this value may be an overestimate, and can even be an
+ * underestimate for certain unencodeable objects.
+ */
+ssize_t create2_cell_body_encoded_len(const create2_cell_body_t *obj);
+/** Try to encode the create2_cell_body from 'input' into the buffer
+ * at 'output', using up to 'avail' bytes of the output buffer. On
+ * success, return the number of bytes used. On failure, return -2 if
+ * the buffer was not long enough, and -1 if the input was invalid.
+ */
+ssize_t create2_cell_body_encode(uint8_t *output, size_t avail, const create2_cell_body_t *input);
+/** Check whether the internal state of the create2_cell_body in 'obj'
+ * is consistent. Return NULL if it is, and a short message if it is
+ * not.
+ */
+const char *create2_cell_body_check(const create2_cell_body_t *obj);
+/** Clear any errors that were set on the object 'obj' by its setter
+ * functions. Return true iff errors were cleared.
+ */
+int create2_cell_body_clear_errors(create2_cell_body_t *obj);
+/** Return the value of the handshake_type field of the
+ * create2_cell_body_t in 'inp'
+ */
+uint16_t create2_cell_body_get_handshake_type(create2_cell_body_t *inp);
+/** Set the value of the handshake_type field of the
+ * create2_cell_body_t in 'inp' to 'val'. Return 0 on success; return
+ * -1 and set the error code on 'inp' on failure.
+ */
+int create2_cell_body_set_handshake_type(create2_cell_body_t *inp, uint16_t val);
+/** Return the value of the handshake_len field of the
+ * create2_cell_body_t in 'inp'
+ */
+uint16_t create2_cell_body_get_handshake_len(create2_cell_body_t *inp);
+/** Set the value of the handshake_len field of the
+ * create2_cell_body_t in 'inp' to 'val'. Return 0 on success; return
+ * -1 and set the error code on 'inp' on failure.
+ */
+int create2_cell_body_set_handshake_len(create2_cell_body_t *inp, uint16_t val);
+/** Return the length of the dynamic array holding the handshake_data
+ * field of the create2_cell_body_t in 'inp'.
+ */
+size_t create2_cell_body_getlen_handshake_data(const create2_cell_body_t *inp);
+/** Return the element at position 'idx' of the dynamic array field
+ * handshake_data of the create2_cell_body_t in 'inp'.
+ */
+uint8_t create2_cell_body_get_handshake_data(create2_cell_body_t *inp, size_t idx);
+/** As create2_cell_body_get_handshake_data, but take and return a
+ * const pointer
+ */
+uint8_t create2_cell_body_getconst_handshake_data(const create2_cell_body_t *inp, size_t idx);
+/** Change the element at position 'idx' of the dynamic array field
+ * handshake_data of the create2_cell_body_t in 'inp', so that it will
+ * hold the value 'elt'.
+ */
+int create2_cell_body_set_handshake_data(create2_cell_body_t *inp, size_t idx, uint8_t elt);
+/** Append a new element 'elt' to the dynamic array field
+ * handshake_data of the create2_cell_body_t in 'inp'.
+ */
+int create2_cell_body_add_handshake_data(create2_cell_body_t *inp, uint8_t elt);
+/** Return a pointer to the variable-length array field handshake_data
+ * of 'inp'.
+ */
+uint8_t * create2_cell_body_getarray_handshake_data(create2_cell_body_t *inp);
+/** As create2_cell_body_get_handshake_data, but take and return a
+ * const pointer
+ */
+const uint8_t  * create2_cell_body_getconstarray_handshake_data(const create2_cell_body_t *inp);
+/** Change the length of the variable-length array field
+ * handshake_data of 'inp' to 'newlen'.Fill extra elements with 0.
+ * Return 0 on success; return -1 and set the error code on 'inp' on
+ * failure.
+ */
+int create2_cell_body_setlen_handshake_data(create2_cell_body_t *inp, size_t newlen);
 /** Return a newly allocated ed25519_cert_extension with all elements
  * set to zero.
  */
@@ -184,6 +301,109 @@ const uint8_t  * ed25519_cert_extension_getconstarray_un_unparsed(const ed25519_
  * success; return -1 and set the error code on 'inp' on failure.
  */
 int ed25519_cert_extension_setlen_un_unparsed(ed25519_cert_extension_t *inp, size_t newlen);
+/** Return a newly allocated extend1_cell_body with all elements set
+ * to zero.
+ */
+extend1_cell_body_t *extend1_cell_body_new(void);
+/** Release all storage held by the extend1_cell_body in 'victim'. (Do
+ * nothing if 'victim' is NULL.)
+ */
+void extend1_cell_body_free(extend1_cell_body_t *victim);
+/** Try to parse a extend1_cell_body from the buffer in 'input', using
+ * up to 'len_in' bytes from the input buffer. On success, return the
+ * number of bytes consumed and set *output to the newly allocated
+ * extend1_cell_body_t. On failure, return -2 if the input appears
+ * truncated, and -1 if the input is otherwise invalid.
+ */
+ssize_t extend1_cell_body_parse(extend1_cell_body_t **output, const uint8_t *input, const size_t len_in);
+/** Return the number of bytes we expect to need to encode the
+ * extend1_cell_body in 'obj'. On failure, return a negative value.
+ * Note that this value may be an overestimate, and can even be an
+ * underestimate for certain unencodeable objects.
+ */
+ssize_t extend1_cell_body_encoded_len(const extend1_cell_body_t *obj);
+/** Try to encode the extend1_cell_body from 'input' into the buffer
+ * at 'output', using up to 'avail' bytes of the output buffer. On
+ * success, return the number of bytes used. On failure, return -2 if
+ * the buffer was not long enough, and -1 if the input was invalid.
+ */
+ssize_t extend1_cell_body_encode(uint8_t *output, size_t avail, const extend1_cell_body_t *input);
+/** Check whether the internal state of the extend1_cell_body in 'obj'
+ * is consistent. Return NULL if it is, and a short message if it is
+ * not.
+ */
+const char *extend1_cell_body_check(const extend1_cell_body_t *obj);
+/** Clear any errors that were set on the object 'obj' by its setter
+ * functions. Return true iff errors were cleared.
+ */
+int extend1_cell_body_clear_errors(extend1_cell_body_t *obj);
+/** Return the value of the ipv4addr field of the extend1_cell_body_t
+ * in 'inp'
+ */
+uint32_t extend1_cell_body_get_ipv4addr(extend1_cell_body_t *inp);
+/** Set the value of the ipv4addr field of the extend1_cell_body_t in
+ * 'inp' to 'val'. Return 0 on success; return -1 and set the error
+ * code on 'inp' on failure.
+ */
+int extend1_cell_body_set_ipv4addr(extend1_cell_body_t *inp, uint32_t val);
+/** Return the value of the port field of the extend1_cell_body_t in
+ * 'inp'
+ */
+uint16_t extend1_cell_body_get_port(extend1_cell_body_t *inp);
+/** Set the value of the port field of the extend1_cell_body_t in
+ * 'inp' to 'val'. Return 0 on success; return -1 and set the error
+ * code on 'inp' on failure.
+ */
+int extend1_cell_body_set_port(extend1_cell_body_t *inp, uint16_t val);
+/** Return the (constant) length of the array holding the onionskin
+ * field of the extend1_cell_body_t in 'inp'.
+ */
+size_t extend1_cell_body_getlen_onionskin(const extend1_cell_body_t *inp);
+/** Return the element at position 'idx' of the fixed array field
+ * onionskin of the extend1_cell_body_t in 'inp'.
+ */
+uint8_t extend1_cell_body_get_onionskin(extend1_cell_body_t *inp, size_t idx);
+/** As extend1_cell_body_get_onionskin, but take and return a const
+ * pointer
+ */
+uint8_t extend1_cell_body_getconst_onionskin(const extend1_cell_body_t *inp, size_t idx);
+/** Change the element at position 'idx' of the fixed array field
+ * onionskin of the extend1_cell_body_t in 'inp', so that it will hold
+ * the value 'elt'.
+ */
+int extend1_cell_body_set_onionskin(extend1_cell_body_t *inp, size_t idx, uint8_t elt);
+/** Return a pointer to the 186-element array field onionskin of
+ * 'inp'.
+ */
+uint8_t * extend1_cell_body_getarray_onionskin(extend1_cell_body_t *inp);
+/** As extend1_cell_body_get_onionskin, but take and return a const
+ * pointer
+ */
+const uint8_t  * extend1_cell_body_getconstarray_onionskin(const extend1_cell_body_t *inp);
+/** Return the (constant) length of the array holding the identity
+ * field of the extend1_cell_body_t in 'inp'.
+ */
+size_t extend1_cell_body_getlen_identity(const extend1_cell_body_t *inp);
+/** Return the element at position 'idx' of the fixed array field
+ * identity of the extend1_cell_body_t in 'inp'.
+ */
+uint8_t extend1_cell_body_get_identity(extend1_cell_body_t *inp, size_t idx);
+/** As extend1_cell_body_get_identity, but take and return a const
+ * pointer
+ */
+uint8_t extend1_cell_body_getconst_identity(const extend1_cell_body_t *inp, size_t idx);
+/** Change the element at position 'idx' of the fixed array field
+ * identity of the extend1_cell_body_t in 'inp', so that it will hold
+ * the value 'elt'.
+ */
+int extend1_cell_body_set_identity(extend1_cell_body_t *inp, size_t idx, uint8_t elt);
+/** Return a pointer to the 20-element array field identity of 'inp'.
+ */
+uint8_t * extend1_cell_body_getarray_identity(extend1_cell_body_t *inp);
+/** As extend1_cell_body_get_identity, but take and return a const
+ * pointer
+ */
+const uint8_t  * extend1_cell_body_getconstarray_identity(const extend1_cell_body_t *inp);
 /** Return a newly allocated link_specifier with all elements set to
  * zero.
  */
@@ -536,6 +756,104 @@ uint8_t * ed25519_cert_getarray_signature(ed25519_cert_t *inp);
 /** As ed25519_cert_get_signature, but take and return a const pointer
  */
 const uint8_t  * ed25519_cert_getconstarray_signature(const ed25519_cert_t *inp);
+/** Return a newly allocated extend2_cell_body with all elements set
+ * to zero.
+ */
+extend2_cell_body_t *extend2_cell_body_new(void);
+/** Release all storage held by the extend2_cell_body in 'victim'. (Do
+ * nothing if 'victim' is NULL.)
+ */
+void extend2_cell_body_free(extend2_cell_body_t *victim);
+/** Try to parse a extend2_cell_body from the buffer in 'input', using
+ * up to 'len_in' bytes from the input buffer. On success, return the
+ * number of bytes consumed and set *output to the newly allocated
+ * extend2_cell_body_t. On failure, return -2 if the input appears
+ * truncated, and -1 if the input is otherwise invalid.
+ */
+ssize_t extend2_cell_body_parse(extend2_cell_body_t **output, const uint8_t *input, const size_t len_in);
+/** Return the number of bytes we expect to need to encode the
+ * extend2_cell_body in 'obj'. On failure, return a negative value.
+ * Note that this value may be an overestimate, and can even be an
+ * underestimate for certain unencodeable objects.
+ */
+ssize_t extend2_cell_body_encoded_len(const extend2_cell_body_t *obj);
+/** Try to encode the extend2_cell_body from 'input' into the buffer
+ * at 'output', using up to 'avail' bytes of the output buffer. On
+ * success, return the number of bytes used. On failure, return -2 if
+ * the buffer was not long enough, and -1 if the input was invalid.
+ */
+ssize_t extend2_cell_body_encode(uint8_t *output, size_t avail, const extend2_cell_body_t *input);
+/** Check whether the internal state of the extend2_cell_body in 'obj'
+ * is consistent. Return NULL if it is, and a short message if it is
+ * not.
+ */
+const char *extend2_cell_body_check(const extend2_cell_body_t *obj);
+/** Clear any errors that were set on the object 'obj' by its setter
+ * functions. Return true iff errors were cleared.
+ */
+int extend2_cell_body_clear_errors(extend2_cell_body_t *obj);
+/** Return the value of the n_spec field of the extend2_cell_body_t in
+ * 'inp'
+ */
+uint8_t extend2_cell_body_get_n_spec(extend2_cell_body_t *inp);
+/** Set the value of the n_spec field of the extend2_cell_body_t in
+ * 'inp' to 'val'. Return 0 on success; return -1 and set the error
+ * code on 'inp' on failure.
+ */
+int extend2_cell_body_set_n_spec(extend2_cell_body_t *inp, uint8_t val);
+/** Return the length of the dynamic array holding the ls field of the
+ * extend2_cell_body_t in 'inp'.
+ */
+size_t extend2_cell_body_getlen_ls(const extend2_cell_body_t *inp);
+/** Return the element at position 'idx' of the dynamic array field ls
+ * of the extend2_cell_body_t in 'inp'.
+ */
+struct link_specifier_st * extend2_cell_body_get_ls(extend2_cell_body_t *inp, size_t idx);
+/** As extend2_cell_body_get_ls, but take and return a const pointer
+ */
+ const struct link_specifier_st * extend2_cell_body_getconst_ls(const extend2_cell_body_t *inp, size_t idx);
+/** Change the element at position 'idx' of the dynamic array field ls
+ * of the extend2_cell_body_t in 'inp', so that it will hold the value
+ * 'elt'. Free the previous value, if any.
+ */
+int extend2_cell_body_set_ls(extend2_cell_body_t *inp, size_t idx, struct link_specifier_st * elt);
+/** As extend2_cell_body_set_ls, but does not free the previous value.
+ */
+int extend2_cell_body_set0_ls(extend2_cell_body_t *inp, size_t idx, struct link_specifier_st * elt);
+/** Append a new element 'elt' to the dynamic array field ls of the
+ * extend2_cell_body_t in 'inp'.
+ */
+int extend2_cell_body_add_ls(extend2_cell_body_t *inp, struct link_specifier_st * elt);
+/** Return a pointer to the variable-length array field ls of 'inp'.
+ */
+struct link_specifier_st * * extend2_cell_body_getarray_ls(extend2_cell_body_t *inp);
+/** As extend2_cell_body_get_ls, but take and return a const pointer
+ */
+const struct link_specifier_st *  const  * extend2_cell_body_getconstarray_ls(const extend2_cell_body_t *inp);
+/** Change the length of the variable-length array field ls of 'inp'
+ * to 'newlen'.Fill extra elements with NULL; free removed elements.
+ * Return 0 on success; return -1 and set the error code on 'inp' on
+ * failure.
+ */
+int extend2_cell_body_setlen_ls(extend2_cell_body_t *inp, size_t newlen);
+/** Return the value of the create2 field of the extend2_cell_body_t
+ * in 'inp'
+ */
+struct create2_cell_body_st * extend2_cell_body_get_create2(extend2_cell_body_t *inp);
+/** As extend2_cell_body_get_create2, but take and return a const
+ * pointer
+ */
+const struct create2_cell_body_st * extend2_cell_body_getconst_create2(const extend2_cell_body_t *inp);
+/** Set the value of the create2 field of the extend2_cell_body_t in
+ * 'inp' to 'val'. Free the old value if any. Steals the referenceto
+ * 'val'.Return 0 on success; return -1 and set the error code on
+ * 'inp' on failure.
+ */
+int extend2_cell_body_set_create2(extend2_cell_body_t *inp, struct create2_cell_body_st *val);
+/** As extend2_cell_body_set_create2, but does not free the previous
+ * value.
+ */
+int extend2_cell_body_set0_create2(extend2_cell_body_t *inp, struct create2_cell_body_st *val);
 /** Return a newly allocated link_specifier_list with all elements set
  * to zero.
  */
diff --git a/src/trunnel/ed25519_cert.trunnel b/src/trunnel/ed25519_cert.trunnel
index 012b2afc30..e424ce5464 100644
--- a/src/trunnel/ed25519_cert.trunnel
+++ b/src/trunnel/ed25519_cert.trunnel
@@ -23,40 +23,6 @@ struct ed25519_cert_extension {
   };
 }
 
-/*
-struct cert_revocation {
-  u8 prefix[8];
-  u8 version IN [1];
-  u8 keytype;
-  u8 identity_key[32];
-  u8 revoked_key[32];
-  u64 published;
-  u8 n_extensions;
-  struct cert_extension ext[n_extensions];
-  u8 signature[64];
-}
-
-struct crosscert_ed_rsa {
-  u8 ed_key[32];
-  u32 expiration_date;
-  u8 signature[128];
-}
-
-struct auth02_cell {
-  u8 type[8];
-  u8 cid[32];
-  u8 sid[32];
-  u8 cid_ed[32];
-  u8 sid_ed[32];
-  u8 slog[32];
-  u8 clog[32];
-  u8 scert[32];
-  u8 tlssecrets[32];
-  u8 rand[24];
-  u8 sig[64];
-}
-*/
-
 const LS_IPV4 = 0x00;
 const LS_IPV6 = 0x01;
 const LS_LEGACY_ID = 0x02;
@@ -79,3 +45,22 @@ struct link_specifier_list {
   u8 n_spec;
   struct link_specifier spec[n_spec];
 }
+
+struct extend1_cell_body {
+  u32 ipv4addr;
+  u16 port;
+  u8 onionskin[186];
+  u8 identity[20];
+}
+
+struct create2_cell_body {
+  u16 handshake_type;
+  u16 handshake_len;
+  u8 handshake_data[handshake_len];
+}
+
+struct extend2_cell_body {
+  u8 n_spec;
+  struct link_specifier ls[n_spec];
+  struct create2_cell_body create2;
+}