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#![allow(clippy::manual_div_ceil)]
21
22use std::{
23    borrow::Borrow,
24    hash::{Hash, Hasher},
25};
26
27use libp2p_core::multihash::Multihash;
28use libp2p_identity::PeerId;
29use sha2::{
30    digest::generic_array::{typenum::U32, GenericArray},
31    Digest, Sha256,
32};
33use uint::*;
34
35use crate::record;
36
37construct_uint! {
38    /// 256-bit unsigned integer.
39    pub struct U256(4);
40}
41
42/// A `Key` in the DHT keyspace with preserved preimage.
43///
44/// Keys in the DHT keyspace identify both the participating nodes, as well as
45/// the records stored in the DHT.
46///
47/// `Key`s have an XOR metric as defined in the Kademlia paper, i.e. the bitwise XOR of
48/// the hash digests, interpreted as an integer. See [`Key::distance`].
49#[derive(Clone, Copy, Debug)]
50pub struct Key<T> {
51    preimage: T,
52    bytes: KeyBytes,
53}
54
55impl<T> Key<T> {
56    /// Constructs a new `Key` by running the given value through a random
57    /// oracle.
58    ///
59    /// The preimage of type `T` is preserved. See [`Key::preimage`] and
60    /// [`Key::into_preimage`].
61    pub fn new(preimage: T) -> Key<T>
62    where
63        T: Borrow<[u8]>,
64    {
65        let bytes = KeyBytes::new(preimage.borrow());
66        Key { preimage, bytes }
67    }
68
69    /// Borrows the preimage of the key.
70    pub fn preimage(&self) -> &T {
71        &self.preimage
72    }
73
74    /// Converts the key into its preimage.
75    pub fn into_preimage(self) -> T {
76        self.preimage
77    }
78
79    /// Computes the distance of the keys according to the XOR metric.
80    pub fn distance<U>(&self, other: &U) -> Distance
81    where
82        U: AsRef<KeyBytes>,
83    {
84        self.bytes.distance(other)
85    }
86
87    /// Exposing the hashed bytes.
88    pub fn hashed_bytes(&self) -> &[u8] {
89        &self.bytes.0
90    }
91
92    /// Returns the uniquely determined key with the given distance to `self`.
93    ///
94    /// This implements the following equivalence:
95    ///
96    /// `self xor other = distance <==> other = self xor distance`
97    pub fn for_distance(&self, d: Distance) -> KeyBytes {
98        self.bytes.for_distance(d)
99    }
100}
101
102impl<T> From<Key<T>> for KeyBytes {
103    fn from(key: Key<T>) -> KeyBytes {
104        key.bytes
105    }
106}
107
108impl<const S: usize> From<Multihash<S>> for Key<Multihash<S>> {
109    fn from(m: Multihash<S>) -> Self {
110        let bytes = KeyBytes(Sha256::digest(m.to_bytes()));
111        Key { preimage: m, bytes }
112    }
113}
114
115impl From<PeerId> for Key<PeerId> {
116    fn from(p: PeerId) -> Self {
117        let bytes = KeyBytes(Sha256::digest(p.to_bytes()));
118        Key { preimage: p, bytes }
119    }
120}
121
122impl From<Vec<u8>> for Key<Vec<u8>> {
123    fn from(b: Vec<u8>) -> Self {
124        Key::new(b)
125    }
126}
127
128impl From<record::Key> for Key<record::Key> {
129    fn from(k: record::Key) -> Self {
130        Key::new(k)
131    }
132}
133
134impl<T> AsRef<KeyBytes> for Key<T> {
135    fn as_ref(&self) -> &KeyBytes {
136        &self.bytes
137    }
138}
139
140impl<T, U> PartialEq<Key<U>> for Key<T> {
141    fn eq(&self, other: &Key<U>) -> bool {
142        self.bytes == other.bytes
143    }
144}
145
146impl<T> Eq for Key<T> {}
147
148impl<T> Hash for Key<T> {
149    fn hash<H: Hasher>(&self, state: &mut H) {
150        self.bytes.0.hash(state);
151    }
152}
153
154/// The raw bytes of a key in the DHT keyspace.
155#[derive(PartialEq, Eq, Clone, Copy, Debug)]
156pub struct KeyBytes(GenericArray<u8, U32>);
157
158impl KeyBytes {
159    /// Creates a new key in the DHT keyspace by running the given
160    /// value through a random oracle.
161    pub fn new<T>(value: T) -> Self
162    where
163        T: Borrow<[u8]>,
164    {
165        KeyBytes(Sha256::digest(value.borrow()))
166    }
167
168    /// Computes the distance of the keys according to the XOR metric.
169    pub fn distance<U>(&self, other: &U) -> Distance
170    where
171        U: AsRef<KeyBytes>,
172    {
173        let a = U256::from_big_endian(self.0.as_slice());
174        let b = U256::from_big_endian(other.as_ref().0.as_slice());
175        Distance(a ^ b)
176    }
177
178    /// Returns the uniquely determined key with the given distance to `self`.
179    ///
180    /// This implements the following equivalence:
181    ///
182    /// `self xor other = distance <==> other = self xor distance`
183    pub fn for_distance(&self, d: Distance) -> KeyBytes {
184        let key_int = U256::from_big_endian(self.0.as_slice()) ^ d.0;
185        KeyBytes(GenericArray::from(key_int.to_big_endian()))
186    }
187}
188
189impl AsRef<KeyBytes> for KeyBytes {
190    fn as_ref(&self) -> &KeyBytes {
191        self
192    }
193}
194
195/// A distance between two keys in the DHT keyspace.
196#[derive(Copy, Clone, PartialEq, Eq, Default, PartialOrd, Ord, Debug)]
197pub struct Distance(pub U256);
198
199impl Distance {
200    /// Returns the integer part of the base 2 logarithm of the [`Distance`].
201    ///
202    /// Returns `None` if the distance is zero.
203    pub fn ilog2(&self) -> Option<u32> {
204        (256 - self.0.leading_zeros()).checked_sub(1)
205    }
206}
207
208#[cfg(test)]
209mod tests {
210    use quickcheck::*;
211
212    use super::*;
213    use crate::SHA_256_MH;
214
215    impl Arbitrary for Key<PeerId> {
216        fn arbitrary(_: &mut Gen) -> Key<PeerId> {
217            Key::from(PeerId::random())
218        }
219    }
220
221    impl Arbitrary for Key<Multihash<64>> {
222        fn arbitrary(g: &mut Gen) -> Key<Multihash<64>> {
223            let hash: [u8; 32] = core::array::from_fn(|_| u8::arbitrary(g));
224            Key::from(Multihash::wrap(SHA_256_MH, &hash).unwrap())
225        }
226    }
227
228    #[test]
229    fn identity() {
230        fn prop(a: Key<PeerId>) -> bool {
231            a.distance(&a) == Distance::default()
232        }
233        quickcheck(prop as fn(_) -> _)
234    }
235
236    #[test]
237    fn symmetry() {
238        fn prop(a: Key<PeerId>, b: Key<PeerId>) -> bool {
239            a.distance(&b) == b.distance(&a)
240        }
241        quickcheck(prop as fn(_, _) -> _)
242    }
243
244    #[test]
245    fn triangle_inequality() {
246        fn prop(a: Key<PeerId>, b: Key<PeerId>, c: Key<PeerId>) -> TestResult {
247            let ab = a.distance(&b);
248            let bc = b.distance(&c);
249            let (ab_plus_bc, overflow) = ab.0.overflowing_add(bc.0);
250            if overflow {
251                TestResult::discard()
252            } else {
253                TestResult::from_bool(a.distance(&c) <= Distance(ab_plus_bc))
254            }
255        }
256        quickcheck(prop as fn(_, _, _) -> _)
257    }
258
259    #[test]
260    fn unidirectionality() {
261        fn prop(a: Key<PeerId>, b: Key<PeerId>) -> bool {
262            let d = a.distance(&b);
263            (0..100).all(|_| {
264                let c = Key::from(PeerId::random());
265                a.distance(&c) != d || b == c
266            })
267        }
268        quickcheck(prop as fn(_, _) -> _)
269    }
270}
libp2p_kad/kbucket/key.rs

libp2p_kad/kbucket/
key.rs
