serialization fixes
diff --git a/src/crypto.rs b/src/crypto.rs
index f63b7b4..b0d2e14 100644
--- a/src/crypto.rs
+++ b/src/crypto.rs
@@ -12,7 +12,9 @@
 use serde::ser::{Serialize, Serializer, Error as SerializeError};
 use std::collections::HashMap;
 use std::fmt::{self, Debug, Display};
+use std::hash;
 use std::io::Read;
+use std::cmp::Ordering;
 use std::str::FromStr;
 use std::sync::Arc;
 use untrusted::Input;
@@ -192,13 +194,13 @@
 #[derive(Debug, Clone, PartialEq, Serialize, Deserialize)]
 pub enum SignatureScheme {
     /// [Ed25519](https://ed25519.cr.yp.to/)
-    #[serde(rename="ed25519")]
+    #[serde(rename = "ed25519")]
     Ed25519,
     /// [RSASSA-PSS](https://tools.ietf.org/html/rfc5756) calculated over SHA256
-    #[serde(rename="rsassa-pss-sha256")]
+    #[serde(rename = "rsassa-pss-sha256")]
     RsaSsaPssSha256,
     /// [RSASSA-PSS](https://tools.ietf.org/html/rfc5756) calculated over SHA512
-    #[serde(rename="rsassa-pss-sha512")]
+    #[serde(rename = "rsassa-pss-sha512")]
     RsaSsaPssSha512,
 }
 
@@ -247,7 +249,7 @@
 }
 
 /// Types of public keys.
-#[derive(Clone, PartialEq, Debug)]
+#[derive(Clone, PartialEq, Debug, Eq)]
 pub enum KeyType {
     /// [Ed25519](https://ed25519.cr.yp.to/)
     Ed25519,
@@ -501,7 +503,7 @@
 
 
 /// A structure containing information about a public key.
-#[derive(Clone, Debug, PartialEq)]
+#[derive(Clone, Debug)]
 pub struct PublicKey {
     typ: KeyType,
     key_id: KeyId,
@@ -571,6 +573,34 @@
     }
 }
 
+impl PartialEq for PublicKey {
+    fn eq(&self, other: &Self) -> bool {
+        // the other two fields are derived from this one, we ignore them
+        self.value == other.value
+    }
+}
+
+impl Eq for PublicKey {}
+
+impl Ord for PublicKey {
+    fn cmp(&self, other: &Self) -> Ordering {
+        self.key_id.cmp(&other.key_id)
+    }
+}
+
+impl PartialOrd for PublicKey {
+    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
+        Some(self.key_id.cmp(&other.key_id))
+    }
+}
+
+impl hash::Hash for PublicKey {
+    fn hash<H: hash::Hasher>(&self, state: &mut H) {
+        // the other two fields are derived from this one, we ignore them
+        self.value.hash(state);
+    }
+}
+
 impl Serialize for PublicKey {
     fn serialize<S>(&self, ser: S) -> ::std::result::Result<S::Ok, S::Error>
     where
@@ -608,7 +638,7 @@
     }
 }
 
-#[derive(Clone, PartialEq)]
+#[derive(Clone, PartialEq, Hash, Eq)]
 struct PublicKeyValue(Vec<u8>);
 
 impl Debug for PublicKeyValue {
diff --git a/src/interchange/mod.rs b/src/interchange/mod.rs
index e3f3590..287f59e 100644
--- a/src/interchange/mod.rs
+++ b/src/interchange/mod.rs
@@ -168,10 +168,7 @@
 ///
 /// ```bash
 /// {
-///   "keys": {
-///     KEY_ID: PUB_KEY,
-///     ...
-///   },
+///   "keys": [PUB_KEY, ...]
 ///   "roles": {
 ///     ROLE: DELEGATION,
 ///     ...
diff --git a/src/metadata.rs b/src/metadata.rs
index 5bcee7c..5c66d39 100644
--- a/src/metadata.rs
+++ b/src/metadata.rs
@@ -1279,7 +1279,7 @@
 }
 
 /// Wrapper to described a collections of delegations.
-#[derive(Debug, PartialEq, Clone, Serialize)]
+#[derive(Debug, PartialEq, Clone)]
 pub struct Delegations {
     keys: HashMap<KeyId, PublicKey>,
     roles: Vec<Delegation>,
@@ -1289,7 +1289,7 @@
     // TODO check all keys are used
     // TODO check all roles have their ID in the set of keys
     /// Create a new `Delegations` wrapper from the given set of trusted keys and roles.
-    pub fn new(mut keys: Vec<PublicKey>, roles: Vec<Delegation>) -> Result<Self> {
+    pub fn new(keys: HashSet<PublicKey>, roles: Vec<Delegation>) -> Result<Self> {
         if keys.is_empty() {
             return Err(Error::IllegalArgument("Keys cannot be empty.".into()));
         }
@@ -1311,7 +1311,10 @@
         }
 
         Ok(Delegations {
-            keys: HashMap::from_iter(keys.drain(..).map(|k| (k.key_id().clone(), k))),
+            keys: keys.iter()
+                .cloned()
+                .map(|k| (k.key_id().clone(), k))
+                .collect(),
             roles: roles,
         })
     }
@@ -1327,6 +1330,16 @@
     }
 }
 
+impl Serialize for Delegations {
+    fn serialize<S>(&self, ser: S) -> ::std::result::Result<S::Ok, S::Error>
+    where
+        S: Serializer,
+    {
+        shims::Delegations::from(self).serialize(ser)
+    }
+}
+
+
 impl<'de> Deserialize<'de> for Delegations {
     fn deserialize<D: Deserializer<'de>>(de: D) -> ::std::result::Result<Self, D::Error> {
         let intermediate: shims::Delegations = Deserialize::deserialize(de)?;
@@ -1749,7 +1762,7 @@
     fn serde_targets_with_delegations_metadata() {
         let key = PrivateKey::from_pkcs8(ED25519_1_PK8).unwrap();
         let delegations = Delegations::new(
-            vec![key.public().clone()],
+            hashset![key.public().clone()],
             vec![Delegation::new(
                 MetadataPath::new("foo/bar".into()).unwrap(),
                 false,
@@ -1772,13 +1785,13 @@
             "expires": "2017-01-01T00:00:00Z",
             "targets": {},
             "delegations": {
-                "keys": {
-                    "qfrfBrkB4lBBSDEBlZgaTGS_SrE6UfmON9kP4i3dJFY=": {
+                "keys": [
+                    {
                         "type": "ed25519",
                         "public_key": "MCwwBwYDK2VwBQADIQDrisJrXJ7wJ5474-giYqk7zhb\
                             -WO5CJQDTjK9GHGWjtg==",
                     },
-                },
+                ],
                 "roles": [
                     {
                         "role": "foo/bar",
@@ -1944,7 +1957,7 @@
             .public()
             .clone();
         let delegations = Delegations::new(
-            vec![key.clone()],
+            hashset![key.clone()],
             vec![Delegation::new(
                 MetadataPath::new("foo".into()).unwrap(),
                 false,
@@ -2168,7 +2181,7 @@
             .unwrap()
             .get_mut("keys".into())
             .unwrap()
-            .as_object_mut()
+            .as_array_mut()
             .unwrap()
             .clear();
         assert!(json::from_value::<Delegations>(delegations).is_err());
@@ -2272,4 +2285,43 @@
             .push(dupe);
         assert!(json::from_value::<Delegation>(delegation).is_err());
     }
+
+    // Refuse to deserialize a Delegations struct with duplicate keys
+    #[test]
+    fn deserialize_json_delegations_duplicate_keys() {
+        let key = PrivateKey::from_pkcs8(ED25519_1_PK8)
+            .unwrap()
+            .public()
+            .clone();
+        let delegations = Delegations::new(
+            hashset!(key.clone()),
+            vec![Delegation::new(
+                MetadataPath::new("foo".into()).unwrap(),
+                false,
+                1,
+                hashset!(key.key_id().clone()),
+                hashset!(TargetPath::new("bar".into()).unwrap()),
+            ).unwrap()],
+        ).unwrap();
+        let mut delegations = json::to_value(delegations).unwrap();
+
+        let dupe = delegations
+            .as_object()
+            .unwrap()
+            .get("keys".into())
+            .unwrap()
+            .as_array()
+            .unwrap()
+            [0]
+            .clone();
+        delegations
+            .as_object_mut()
+            .unwrap()
+            .get_mut("keys".into())
+            .unwrap()
+            .as_array_mut()
+            .unwrap()
+            .push(dupe);
+        assert!(json::from_value::<Delegations>(delegations).is_err());
+    }
 }
diff --git a/src/shims.rs b/src/shims.rs
index ce8e6b1..c2b83c2 100644
--- a/src/shims.rs
+++ b/src/shims.rs
@@ -305,33 +305,34 @@
     }
 }
 
-#[derive(Deserialize)]
+#[derive(Serialize, Deserialize)]
 pub struct Delegations {
-    keys: HashMap<crypto::KeyId, crypto::PublicKey>,
+    keys: Vec<crypto::PublicKey>,
     roles: Vec<metadata::Delegation>,
 }
 
 
 impl Delegations {
-    pub fn try_into(mut self) -> Result<metadata::Delegations> {
-        let mut keys = Vec::new();
-        for (key_id, value) in self.keys.drain() {
-            if &key_id != value.key_id() {
-                warn!(
-                    "Received key with ID {:?} but calculated it's value as {:?}. \
-                       Refusing to add it to the set of trusted keys.",
-                    key_id,
-                    value.key_id()
-                );
-            } else {
-                debug!(
-                    "Found key with good ID {:?}. Adding it to the set of trusted keys.",
-                    key_id
-                );
-                keys.push(value);
-            }
-        }
+    pub fn from(delegations: &metadata::Delegations) -> Delegations {
+        let mut keys = delegations
+            .keys()
+            .iter()
+            .map(|(_, k)| k.clone())
+            .collect::<Vec<crypto::PublicKey>>();
+        keys.sort();
 
+        Delegations {
+            keys: keys,
+            roles: delegations.roles().clone(),
+        }
+    }
+
+    pub fn try_into(mut self) -> Result<metadata::Delegations> {
+        let keys_len = self.keys.len();
+        let keys = self.keys.drain(..).collect::<HashSet<crypto::PublicKey>>();
+        if keys.len() != keys_len {
+            return Err(Error::Encoding("Cannot have duplicate keys".into()));
+        }
         metadata::Delegations::new(keys, self.roles)
     }
 }
diff --git a/tests/integration.rs b/tests/integration.rs
index 57101c8..8f743e3 100644
--- a/tests/integration.rs
+++ b/tests/integration.rs
@@ -91,7 +91,7 @@
 
     //// build the targets ////
     let delegations = Delegations::new(
-        vec![delegation_key.public().clone()],
+        hashset![delegation_key.public().clone()],
         vec![
             Delegation::new(
                 MetadataPath::new("delegation".into()).unwrap(),
@@ -222,7 +222,7 @@
 
     //// build the targets ////
     let delegations = Delegations::new(
-        vec![delegation_a_key.public().clone()],
+        hashset![delegation_a_key.public().clone()],
         vec![
             Delegation::new(
                 MetadataPath::new("delegation-a".into()).unwrap(),
@@ -256,7 +256,7 @@
 
     //// build delegation A ////
     let delegations = Delegations::new(
-        vec![delegation_b_key.public().clone()],
+        hashset![delegation_b_key.public().clone()],
         vec![
             Delegation::new(
                 MetadataPath::new("delegation-b".into()).unwrap(),