libp2p_kad/kbucket/
key.rs

1// Copyright 2018 Parity Technologies (UK) Ltd.
2//
3// Permission is hereby granted, free of charge, to any person obtaining a
4// copy of this software and associated documentation files (the "Software"),
5// to deal in the Software without restriction, including without limitation
6// the rights to use, copy, modify, merge, publish, distribute, sublicense,
7// and/or sell copies of the Software, and to permit persons to whom the
8// Software is furnished to do so, subject to the following conditions:
9//
10// The above copyright notice and this permission notice shall be included in
11// all copies or substantial portions of the Software.
12//
13// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
14// OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
15// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
16// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
17// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
18// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
19// DEALINGS IN THE SOFTWARE.
20
21use derivative::Derivative;
22use libp2p_core::{PeerId, multihash::Multihash};
23use sha2::digest::generic_array::{typenum::U32, GenericArray};
24use sha2::{Digest, Sha256};
25use std::borrow::Borrow;
26use std::hash::{Hash, Hasher};
27use uint::*;
28use crate::record;
29
30construct_uint! {
31    /// 256-bit unsigned integer.
32    pub(super) struct U256(4);
33}
34
35/// A `Key` in the DHT keyspace with preserved preimage.
36///
37/// Keys in the DHT keyspace identify both the participating nodes, as well as
38/// the records stored in the DHT.
39///
40/// `Key`s have an XOR metric as defined in the Kademlia paper, i.e. the bitwise XOR of
41/// the hash digests, interpreted as an integer. See [`Key::distance`].
42#[derive(Clone, Derivative)]
43#[derivative(Debug)]
44pub struct Key<T> {
45    preimage: T,
46    #[derivative(Debug = "ignore")]
47    bytes: KeyBytes,
48}
49
50impl<T> Key<T> {
51    /// Constructs a new `Key` by running the given value through a random
52    /// oracle.
53    ///
54    /// The preimage of type `T` is preserved. See [`Key::preimage`] and
55    /// [`Key::into_preimage`].
56    pub fn new(preimage: T) -> Key<T>
57    where
58        T: Borrow<[u8]>
59    {
60        let bytes = KeyBytes::new(preimage.borrow());
61        Key { preimage, bytes }
62    }
63
64    /// Borrows the preimage of the key.
65    pub fn preimage(&self) -> &T {
66        &self.preimage
67    }
68
69    /// Converts the key into its preimage.
70    pub fn into_preimage(self) -> T {
71        self.preimage
72    }
73
74    /// Computes the distance of the keys according to the XOR metric.
75    pub fn distance<U>(&self, other: &U) -> Distance
76    where
77        U: AsRef<KeyBytes>
78    {
79        self.bytes.distance(other)
80    }
81
82    /// Returns the uniquely determined key with the given distance to `self`.
83    ///
84    /// This implements the following equivalence:
85    ///
86    /// `self xor other = distance <==> other = self xor distance`
87    pub fn for_distance(&self, d: Distance) -> KeyBytes {
88        self.bytes.for_distance(d)
89    }
90}
91
92impl<T> Into<KeyBytes> for Key<T> {
93    fn into(self) -> KeyBytes {
94        self.bytes
95    }
96}
97
98impl From<Multihash> for Key<Multihash> {
99   fn from(m: Multihash) -> Self {
100       let bytes = KeyBytes(Sha256::digest(&m.to_bytes()));
101       Key {
102           preimage: m,
103           bytes
104       }
105   }
106}
107
108impl From<PeerId> for Key<PeerId> {
109    fn from(p: PeerId) -> Self {
110       let bytes = KeyBytes(Sha256::digest(&p.to_bytes()));
111       Key {
112           preimage: p,
113           bytes
114       }
115    }
116}
117
118impl From<Vec<u8>> for Key<Vec<u8>> {
119    fn from(b: Vec<u8>) -> Self {
120        Key::new(b)
121    }
122}
123
124impl From<record::Key> for Key<record::Key> {
125    fn from(k: record::Key) -> Self {
126        Key::new(k)
127    }
128}
129
130impl<T> AsRef<KeyBytes> for Key<T> {
131    fn as_ref(&self) -> &KeyBytes {
132        &self.bytes
133    }
134}
135
136impl<T, U> PartialEq<Key<U>> for Key<T> {
137    fn eq(&self, other: &Key<U>) -> bool {
138        self.bytes == other.bytes
139    }
140}
141
142impl<T> Eq for Key<T> {}
143
144impl<T> Hash for Key<T> {
145    fn hash<H: Hasher>(&self, state: &mut H) {
146        self.bytes.0.hash(state);
147    }
148}
149
150/// The raw bytes of a key in the DHT keyspace.
151#[derive(PartialEq, Eq, Clone, Debug)]
152pub struct KeyBytes(GenericArray<u8, U32>);
153
154impl KeyBytes {
155    /// Creates a new key in the DHT keyspace by running the given
156    /// value through a random oracle.
157    pub fn new<T>(value: T) -> Self
158    where
159        T: Borrow<[u8]>
160    {
161        KeyBytes(Sha256::digest(value.borrow()))
162    }
163
164    /// Computes the distance of the keys according to the XOR metric.
165    pub fn distance<U>(&self, other: &U) -> Distance
166    where
167        U: AsRef<KeyBytes>
168    {
169        let a = U256::from(self.0.as_slice());
170        let b = U256::from(other.as_ref().0.as_slice());
171        Distance(a ^ b)
172    }
173
174    /// Returns the uniquely determined key with the given distance to `self`.
175    ///
176    /// This implements the following equivalence:
177    ///
178    /// `self xor other = distance <==> other = self xor distance`
179    pub fn for_distance(&self, d: Distance) -> KeyBytes {
180        let key_int = U256::from(self.0.as_slice()) ^ d.0;
181        KeyBytes(GenericArray::from(<[u8; 32]>::from(key_int)))
182    }
183}
184
185impl AsRef<KeyBytes> for KeyBytes {
186    fn as_ref(&self) -> &KeyBytes {
187        self
188    }
189}
190
191impl AsRef<[u8]> for KeyBytes {
192    fn as_ref(&self) -> &[u8] {
193        self.0.as_ref()
194    }
195}
196
197/// A distance between two keys in the DHT keyspace.
198#[derive(Copy, Clone, PartialEq, Eq, Default, PartialOrd, Ord, Debug)]
199pub struct Distance(pub(super) U256);
200
201impl Distance {
202    /// Returns the integer part of the base 2 logarithm of the [`Distance`].
203    ///
204    /// Returns `None` if the distance is zero.
205    pub fn ilog2(&self) -> Option<u32> {
206        (256 - self.0.leading_zeros()).checked_sub(1)
207    }
208}
209
210#[cfg(test)]
211mod tests {
212    use super::*;
213    use libp2p_core::multihash::Code;
214    use quickcheck::*;
215    use rand::Rng;
216
217    impl Arbitrary for Key<PeerId> {
218        fn arbitrary<G: Gen>(_: &mut G) -> Key<PeerId> {
219            Key::from(PeerId::random())
220        }
221    }
222
223    impl Arbitrary for Key<Multihash> {
224        fn arbitrary<G: Gen>(_: &mut G) -> Key<Multihash> {
225            let hash = rand::thread_rng().gen::<[u8; 32]>();
226            Key::from(Multihash::wrap(Code::Sha2_256.into(), &hash).unwrap())
227        }
228    }
229
230    #[test]
231    fn identity() {
232        fn prop(a: Key<PeerId>) -> bool {
233            a.distance(&a) == Distance::default()
234        }
235        quickcheck(prop as fn(_) -> _)
236    }
237
238    #[test]
239    fn symmetry() {
240        fn prop(a: Key<PeerId>, b: Key<PeerId>) -> bool {
241            a.distance(&b) == b.distance(&a)
242        }
243        quickcheck(prop as fn(_, _) -> _)
244    }
245
246    #[test]
247    fn triangle_inequality() {
248        fn prop(a: Key<PeerId>, b: Key<PeerId>, c: Key<PeerId>) -> TestResult {
249            let ab = a.distance(&b);
250            let bc = b.distance(&c);
251            let (ab_plus_bc, overflow) = ab.0.overflowing_add(bc.0);
252            if overflow {
253                TestResult::discard()
254            } else {
255                TestResult::from_bool(a.distance(&c) <= Distance(ab_plus_bc))
256            }
257        }
258        quickcheck(prop as fn(_, _, _) -> _)
259    }
260
261    #[test]
262    fn unidirectionality() {
263        fn prop(a: Key<PeerId>, b: Key<PeerId>) -> bool {
264            let d = a.distance(&b);
265            (0..100).all(|_| {
266                let c = Key::from(PeerId::random());
267                a.distance(&c) != d || b == c
268            })
269        }
270        quickcheck(prop as fn(_, _) -> _)
271    }
272}
libp2p_kad/kbucket/key.rs

libp2p_kad/kbucket/
key.rs
