litep2p/protocol/libp2p/kademlia/
types.rs

1// Copyright 2018-2019 Parity Technologies (UK) Ltd.
2// Copyright 2023 litep2p developers
3//
4// Permission is hereby granted, free of charge, to any person obtaining a
5// copy of this software and associated documentation files (the "Software"),
6// to deal in the Software without restriction, including without limitation
7// the rights to use, copy, modify, merge, publish, distribute, sublicense,
8// and/or sell copies of the Software, and to permit persons to whom the
9// Software is furnished to do so, subject to the following conditions:
10//
11// The above copyright notice and this permission notice shall be included in
12// all copies or substantial portions of the Software.
13//
14// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS
15// OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
16// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
17// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
18// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
19// FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
20// DEALINGS IN THE SOFTWARE.
21
22//! Kademlia types.
23
24use crate::{protocol::libp2p::kademlia::schema, PeerId};
25
26use multiaddr::Multiaddr;
27use sha2::{
28    digest::generic_array::{typenum::U32, GenericArray},
29    Digest, Sha256,
30};
31use uint::*;
32
33use std::{
34    borrow::Borrow,
35    hash::{Hash, Hasher},
36};
37
38construct_uint! {
39    /// 256-bit unsigned integer.
40    pub(super) struct U256(4);
41}
42
43/// A `Key` in the DHT keyspace with preserved preimage.
44///
45/// Keys in the DHT keyspace identify both the participating nodes, as well as
46/// the records stored in the DHT.
47///
48/// `Key`s have an XOR metric as defined in the Kademlia paper, i.e. the bitwise XOR of
49/// the hash digests, interpreted as an integer. See [`Key::distance`].
50#[derive(Clone, Debug)]
51pub struct Key<T: Clone> {
52    preimage: T,
53    bytes: KeyBytes,
54}
55
56impl<T: Clone> Key<T> {
57    /// Constructs a new `Key` by running the given value through a random
58    /// oracle.
59    ///
60    /// The preimage of type `T` is preserved.
61    /// See [`Key::into_preimage`] for more details.
62    pub fn new(preimage: T) -> Key<T>
63    where
64        T: Borrow<[u8]>,
65    {
66        let bytes = KeyBytes::new(preimage.borrow());
67        Key { preimage, bytes }
68    }
69
70    /// Convert [`Key`] into its preimage.
71    pub fn into_preimage(self) -> T {
72        self.preimage
73    }
74
75    /// Computes the distance of the keys according to the XOR metric.
76    pub fn distance<U>(&self, other: &U) -> Distance
77    where
78        U: AsRef<KeyBytes>,
79    {
80        self.bytes.distance(other)
81    }
82
83    /// Returns the uniquely determined key with the given distance to `self`.
84    ///
85    /// This implements the following equivalence:
86    ///
87    /// `self xor other = distance <==> other = self xor distance`
88    #[cfg(test)]
89    pub fn for_distance(&self, d: Distance) -> KeyBytes {
90        self.bytes.for_distance(d)
91    }
92
93    /// Generate key from `KeyBytes` with a random preimage.
94    ///
95    /// Only used for testing
96    #[cfg(test)]
97    pub fn from_bytes(bytes: KeyBytes, preimage: T) -> Key<T> {
98        Self { bytes, preimage }
99    }
100}
101
102impl<T: Clone> From<Key<T>> for KeyBytes {
103    fn from(key: Key<T>) -> KeyBytes {
104        key.bytes
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 { preimage: p, bytes }
112    }
113}
114
115impl From<Vec<u8>> for Key<Vec<u8>> {
116    fn from(b: Vec<u8>) -> Self {
117        Key::new(b)
118    }
119}
120
121impl<T: Clone> AsRef<KeyBytes> for Key<T> {
122    fn as_ref(&self) -> &KeyBytes {
123        &self.bytes
124    }
125}
126
127impl<T: Clone, U: Clone> PartialEq<Key<U>> for Key<T> {
128    fn eq(&self, other: &Key<U>) -> bool {
129        self.bytes == other.bytes
130    }
131}
132
133impl<T: Clone> Eq for Key<T> {}
134
135impl<T: Clone> Hash for Key<T> {
136    fn hash<H: Hasher>(&self, state: &mut H) {
137        self.bytes.0.hash(state);
138    }
139}
140
141/// The raw bytes of a key in the DHT keyspace.
142#[derive(PartialEq, Eq, Clone, Debug)]
143pub struct KeyBytes(GenericArray<u8, U32>);
144
145impl KeyBytes {
146    /// Creates a new key in the DHT keyspace by running the given
147    /// value through a random oracle.
148    pub fn new<T>(value: T) -> Self
149    where
150        T: Borrow<[u8]>,
151    {
152        KeyBytes(Sha256::digest(value.borrow()))
153    }
154
155    /// Computes the distance of the keys according to the XOR metric.
156    pub fn distance<U>(&self, other: &U) -> Distance
157    where
158        U: AsRef<KeyBytes>,
159    {
160        let a = U256::from(self.0.as_slice());
161        let b = U256::from(other.as_ref().0.as_slice());
162        Distance(a ^ b)
163    }
164
165    /// Returns the uniquely determined key with the given distance to `self`.
166    ///
167    /// This implements the following equivalence:
168    ///
169    /// `self xor other = distance <==> other = self xor distance`
170    #[cfg(test)]
171    pub fn for_distance(&self, d: Distance) -> KeyBytes {
172        let key_int = U256::from(self.0.as_slice()) ^ d.0;
173        KeyBytes(GenericArray::from(<[u8; 32]>::from(key_int)))
174    }
175}
176
177impl AsRef<KeyBytes> for KeyBytes {
178    fn as_ref(&self) -> &KeyBytes {
179        self
180    }
181}
182
183/// A distance between two keys in the DHT keyspace.
184#[derive(Copy, Clone, PartialEq, Eq, Default, PartialOrd, Ord, Debug)]
185pub struct Distance(pub(super) U256);
186
187impl Distance {
188    /// Returns the integer part of the base 2 logarithm of the [`Distance`].
189    ///
190    /// Returns `None` if the distance is zero.
191    pub fn ilog2(&self) -> Option<u32> {
192        (256 - self.0.leading_zeros()).checked_sub(1)
193    }
194}
195
196/// Connection type to peer.
197#[derive(Debug, Copy, Clone, PartialEq, Eq)]
198pub enum ConnectionType {
199    /// Sender does not have a connection to peer.
200    NotConnected,
201
202    /// Sender is connected to the peer.
203    Connected,
204
205    /// Sender has recently been connected to the peer.
206    CanConnect,
207
208    /// Sender is unable to connect to the peer.
209    CannotConnect,
210}
211
212impl TryFrom<i32> for ConnectionType {
213    type Error = ();
214
215    fn try_from(value: i32) -> Result<Self, Self::Error> {
216        match value {
217            0 => Ok(ConnectionType::NotConnected),
218            1 => Ok(ConnectionType::Connected),
219            2 => Ok(ConnectionType::CanConnect),
220            3 => Ok(ConnectionType::CannotConnect),
221            _ => Err(()),
222        }
223    }
224}
225
226impl From<ConnectionType> for i32 {
227    fn from(connection: ConnectionType) -> Self {
228        match connection {
229            ConnectionType::NotConnected => 0,
230            ConnectionType::Connected => 1,
231            ConnectionType::CanConnect => 2,
232            ConnectionType::CannotConnect => 3,
233        }
234    }
235}
236
237/// Kademlia peer.
238#[derive(Debug, Clone, PartialEq, Eq)]
239pub struct KademliaPeer {
240    /// Peer key.
241    pub(super) key: Key<PeerId>,
242
243    /// Peer ID.
244    pub(super) peer: PeerId,
245
246    /// Known addresses of peer.
247    pub(super) addresses: Vec<Multiaddr>,
248
249    /// Connection type.
250    pub(super) connection: ConnectionType,
251}
252
253impl KademliaPeer {
254    /// Create new [`KademliaPeer`].
255    pub fn new(peer: PeerId, addresses: Vec<Multiaddr>, connection: ConnectionType) -> Self {
256        Self {
257            peer,
258            addresses,
259            connection,
260            key: Key::from(peer),
261        }
262    }
263}
264
265impl TryFrom<&schema::kademlia::Peer> for KademliaPeer {
266    type Error = ();
267
268    fn try_from(record: &schema::kademlia::Peer) -> Result<Self, Self::Error> {
269        let peer = PeerId::from_bytes(&record.id).map_err(|_| ())?;
270
271        Ok(KademliaPeer {
272            key: Key::from(peer),
273            peer,
274            addresses: record
275                .addrs
276                .iter()
277                .filter_map(|address| Multiaddr::try_from(address.clone()).ok())
278                .collect(),
279            connection: ConnectionType::try_from(record.connection)?,
280        })
281    }
282}
283
284impl From<&KademliaPeer> for schema::kademlia::Peer {
285    fn from(peer: &KademliaPeer) -> Self {
286        schema::kademlia::Peer {
287            id: peer.peer.to_bytes(),
288            addrs: peer.addresses.iter().map(|address| address.to_vec()).collect(),
289            connection: peer.connection.into(),
290        }
291    }
292}
litep2p/protocol/libp2p/kademlia/types.rs

litep2p/protocol/libp2p/kademlia/
types.rs
