Skip to main content

karyon_p2p/discovery/kademlia/
lookup.rs

1use std::{net::IpAddr, sync::Arc, time::Duration};
2
3use futures_util::stream::{FuturesUnordered, StreamExt};
4use log::{error, trace};
5use rand::{TryRng, rngs::SysRng, seq::IndexedRandom};
6
7use karyon_core::{async_runtime::Executor, async_util::timeout, crypto::KeyPair};
8
9use karyon_net::{Addr, Endpoint};
10
11use crate::{
12    Config, Error, PeerID, Result,
13    access_control::{Action, Subject},
14    conn_direction::ConnDirection,
15    connector::Connector,
16    discovery::kademlia::{
17        SUPPORTED_LOOKUP_PROTOCOLS,
18        bloom::BloomRef,
19        messages::{
20            FindPeerMsg, KadNetCmd, KadNetMsg, KadNetMsgCodec, PeerMsg, PeersMsg, PingMsg, PongMsg,
21        },
22        routing_table::RoutingTable,
23    },
24    listener::Listener,
25    message::{PeerAddr, Protocol, ShutdownMsg, pick_endpoint},
26    monitor::{ConnectionKind, DiscoveryKind, Monitor},
27    util::decode,
28    version::version_match,
29};
30
31/// Framed lookup-plane connection.
32type KadConnRef = karyon_net::FramedConn<KadNetMsgCodec>;
33
34/// Maximum number of peers that can be returned in a PeersMsg.
35pub const MAX_PEERS_IN_PEERSMSG: usize = 10;
36
37/// Maximum data-plane addresses a peer may advertise about itself.
38/// Legitimate peers only need one per transport (tcp/tls/quic).
39pub const MAX_ADDRS_PER_PEER: usize = 4;
40
41/// Maximum discovery addresses a peer may advertise about itself.
42/// Legitimate peers only need lookup + refresh.
43pub const MAX_DISCOVERY_ADDRS_PER_PEER: usize = 3;
44
45/// Endpoints the lookup service advertises and binds to.
46pub struct LookupEndpoints {
47    /// Data-plane listen addrs (advertised in PeerMsg.addrs).
48    pub listen: Vec<Endpoint>,
49    /// Local bind for the lookup listener (also advertised).
50    pub lookup: Option<Endpoint>,
51    /// UDP refresh addr to advertise (if any).
52    pub refresh: Option<Endpoint>,
53}
54
55pub struct LookupService {
56    /// Peer's ID
57    id: PeerID,
58
59    /// Routing Table
60    table: Arc<RoutingTable>,
61
62    /// Listener
63    listener: Arc<Listener<KadNetMsgCodec>>,
64    /// Connector
65    connector: Arc<Connector<KadNetMsgCodec>>,
66
67    /// Endpoints this service advertises and binds to.
68    endpoints: LookupEndpoints,
69
70    /// Holds the configuration for the P2P network.
71    config: Arc<Config>,
72
73    /// Responsible for network and system monitoring.
74    monitor: Arc<Monitor>,
75
76    /// Shared local bloom. Snapshotted on every outgoing PeerMsg.
77    bloom: BloomRef,
78}
79
80impl LookupService {
81    /// Creates a new lookup service.
82    pub fn new(
83        key_pair: &KeyPair,
84        table: Arc<RoutingTable>,
85        config: Arc<Config>,
86        monitor: Arc<Monitor>,
87        bloom: BloomRef,
88        endpoints: LookupEndpoints,
89        ex: Executor,
90    ) -> Self {
91        let listener = Listener::new(
92            key_pair,
93            config.lookup_inbound_slots,
94            monitor.clone(),
95            config.handshake_timeout,
96            config.access_control.clone(),
97            ex.clone(),
98        );
99
100        let connector = Connector::new(
101            key_pair,
102            config.lookup_connect_retries,
103            config.lookup_outbound_slots,
104            config.handshake_timeout,
105            monitor.clone(),
106            ex,
107        );
108
109        let id = key_pair
110            .public()
111            .try_into()
112            .expect("Get PeerID from KeyPair");
113        Self {
114            id,
115            table,
116            listener,
117            connector,
118            endpoints,
119            config,
120            monitor,
121            bloom,
122        }
123    }
124
125    /// Start the lookup service.
126    pub async fn start(self: &Arc<Self>) -> Result<()> {
127        self.start_listener().await?;
128        Ok(())
129    }
130
131    pub fn lookup_endpoint(&self) -> Option<&Endpoint> {
132        self.endpoints.lookup.as_ref()
133    }
134
135    /// Shuts down the lookup service.
136    pub async fn shutdown(&self) {
137        self.connector.shutdown().await;
138        self.listener.shutdown().await;
139    }
140
141    /// Starts iterative lookup and populate the routing table.
142    ///
143    /// This method begins by generating a random peer ID and connecting to the
144    /// provided endpoint. It then sends a FindPeer message containing the
145    /// randomly generated peer ID. Upon receiving peers from the initial lookup,
146    /// it starts connecting to these received peers and sends them a FindPeer
147    /// message that contains our own peer ID.
148    pub async fn start_lookup(&self, endpoint: &Endpoint, peer_id: Option<PeerID>) -> Result<()> {
149        trace!("Lookup started {endpoint}");
150        self.monitor
151            .notify(DiscoveryKind::LookupStarted(endpoint.clone()))
152            .await;
153
154        let mut random_peers = vec![];
155        if let Err(err) = self
156            .random_lookup(endpoint, peer_id, &mut random_peers)
157            .await
158        {
159            self.monitor
160                .notify(DiscoveryKind::LookupFailed(endpoint.clone()))
161                .await;
162            return Err(err);
163        };
164
165        let mut peer_buffer = vec![];
166        if let Err(err) = self.self_lookup(&random_peers, &mut peer_buffer).await {
167            self.monitor
168                .notify(DiscoveryKind::LookupFailed(endpoint.clone()))
169                .await;
170            return Err(err);
171        }
172
173        while peer_buffer.len() < MAX_PEERS_IN_PEERSMSG {
174            match random_peers.pop() {
175                Some(p) => peer_buffer.push(p),
176                None => break,
177            }
178        }
179
180        for peer in peer_buffer.iter() {
181            let result = self.table.add_entry(peer.clone().into());
182            trace!("Add entry {result:?}");
183        }
184
185        self.monitor
186            .notify(DiscoveryKind::LookupSucceeded(
187                endpoint.clone(),
188                peer_buffer.len(),
189            ))
190            .await;
191
192        Ok(())
193    }
194
195    /// Starts a random lookup
196    ///
197    /// This will perfom lookup on a random generated PeerID
198    async fn random_lookup(
199        &self,
200        endpoint: &Endpoint,
201        peer_id: Option<PeerID>,
202        random_peers: &mut Vec<PeerMsg>,
203    ) -> Result<()> {
204        for _ in 0..2 {
205            let random_peer_id = PeerID::random()?;
206            let peers = self
207                .connect(endpoint.clone(), peer_id.clone(), &random_peer_id)
208                .await?;
209
210            for peer in peers {
211                if random_peers.contains(&peer)
212                    || peer.peer_id == self.id
213                    || self.table.contains_key(&peer.peer_id.0)
214                {
215                    continue;
216                }
217
218                random_peers.push(peer);
219            }
220        }
221
222        Ok(())
223    }
224
225    /// Starts a self lookup
226    async fn self_lookup(
227        &self,
228        random_peers: &[PeerMsg],
229        peer_buffer: &mut Vec<PeerMsg>,
230    ) -> Result<()> {
231        let mut results = FuturesUnordered::new();
232        for peer in random_peers.sample(&mut rand::rng(), random_peers.len()) {
233            let endpoint = match pick_endpoint(&peer.discovery_addrs, SUPPORTED_LOOKUP_PROTOCOLS) {
234                Some(ep) => ep,
235                None => continue,
236            };
237            results.push(self.connect(endpoint, Some(peer.peer_id.clone()), &self.id))
238        }
239
240        while let Some(result) = results.next().await {
241            match result {
242                Ok(peers) => peer_buffer.extend(peers),
243                Err(err) => {
244                    error!("Failed to do self lookup: {err}");
245                }
246            }
247        }
248
249        Ok(())
250    }
251
252    /// Connects to the given endpoint and initiates a lookup process for the
253    /// provided peer ID.
254    async fn connect(
255        &self,
256        endpoint: Endpoint,
257        peer_id: Option<PeerID>,
258        target_peer_id: &PeerID,
259    ) -> Result<Vec<PeerMsg>> {
260        if !self.config.access_control.allow(
261            &Subject::Endpoint(&endpoint),
262            Action::Lookup(ConnDirection::Outbound),
263        ) {
264            return Err(Error::AccessDenied);
265        }
266
267        // The slot is released when `_slot` drops at the end.
268        let (conn, _slot) = self.connector.connect(&endpoint, &peer_id).await?;
269        let result = self.handle_outbound(conn, target_peer_id).await;
270
271        self.monitor
272            .notify(ConnectionKind::Disconnected(endpoint))
273            .await;
274
275        result
276    }
277
278    /// Handles outbound connection
279    async fn handle_outbound(
280        &self,
281        mut conn: KadConnRef,
282        target_peer_id: &PeerID,
283    ) -> Result<Vec<PeerMsg>> {
284        trace!("Send Ping msg");
285        let mut peers;
286
287        let ping_msg = self.send_ping_msg(&mut conn).await?;
288
289        loop {
290            let t = Duration::from_secs(self.config.lookup_response_timeout);
291            let msg: KadNetMsg = timeout(t, conn.recv_msg()).await??;
292            match msg.header.command {
293                KadNetCmd::Pong => {
294                    let (pong_msg, _) = decode::<PongMsg>(&msg.payload)?;
295                    if ping_msg.nonce != pong_msg.0 {
296                        return Err(Error::InvalidPongMsg);
297                    }
298                    trace!("Send FindPeer msg");
299                    self.send_findpeer_msg(&mut conn, target_peer_id).await?;
300                }
301                KadNetCmd::Peers => {
302                    peers = decode::<PeersMsg>(&msg.payload)?.0.peers;
303                    if peers.len() > MAX_PEERS_IN_PEERSMSG {
304                        return Err(Error::Lookup(
305                            "Received too many peers in PeersMsg".to_string(),
306                        ));
307                    }
308                    for p in &mut peers {
309                        validate_peer_msg(p)?;
310                    }
311                    peers.retain(is_reachable);
312                    break;
313                }
314                c => return Err(Error::InvalidMsg(format!("Unexpected msg: {c:?}"))),
315            };
316        }
317
318        trace!("Send Peer msg");
319        self.send_peer_msg(&mut conn).await?;
320
321        trace!("Send Shutdown msg");
322        self.send_shutdown_msg(&mut conn).await?;
323
324        Ok(peers)
325    }
326
327    /// Start a listener.
328    async fn start_listener(self: &Arc<Self>) -> Result<()> {
329        let endpoint = match self.lookup_endpoint() {
330            Some(e) => e.clone(),
331            None => return Ok(()),
332        };
333
334        if !endpoint.is_tcp() {
335            return Err(Error::Config(format!(
336                "lookup endpoint must be tcp://..., got {endpoint}"
337            )));
338        }
339
340        let callback = {
341            let this = self.clone();
342            |conn: KadConnRef| async move {
343                let t = Duration::from_secs(this.config.lookup_connection_lifespan);
344                timeout(t, this.handle_inbound(conn)).await??;
345                Ok(())
346            }
347        };
348
349        self.listener
350            .start_with_callback(endpoint, callback)
351            .await?;
352        Ok(())
353    }
354
355    /// Handles inbound connection
356    async fn handle_inbound(self: &Arc<Self>, mut conn: KadConnRef) -> Result<()> {
357        loop {
358            let msg: KadNetMsg = conn.recv_msg().await?;
359            trace!("Receive msg {:?}", msg.header.command);
360
361            if let KadNetCmd::Shutdown = msg.header.command {
362                return Ok(());
363            }
364
365            match &msg.header.command {
366                KadNetCmd::Ping => {
367                    let (ping_msg, _) = decode::<PingMsg>(&msg.payload)?;
368                    if !version_match(&self.config.version.req, &ping_msg.version) {
369                        return Err(Error::IncompatibleVersion("system: {}".into()));
370                    }
371                    self.send_pong_msg(ping_msg.nonce, &mut conn).await?;
372                }
373                KadNetCmd::FindPeer => {
374                    let (findpeer_msg, _) = decode::<FindPeerMsg>(&msg.payload)?;
375                    let peer_id = findpeer_msg.0;
376                    self.send_peers_msg(&peer_id, &mut conn).await?;
377                }
378                KadNetCmd::Peer => {
379                    let (mut peer, _) = decode::<PeerMsg>(&msg.payload)?;
380                    validate_peer_msg(&mut peer)?;
381                    if !is_reachable(&peer) {
382                        trace!("Ignore Peer msg without addresses");
383                        continue;
384                    }
385                    let result = self.table.add_entry(peer.into());
386                    trace!("Add entry result: {result:?}");
387                }
388                c => return Err(Error::InvalidMsg(format!("Unexpected msg: {c:?}"))),
389            }
390        }
391    }
392
393    /// Sends a Ping msg.
394    async fn send_ping_msg(&self, conn: &mut KadConnRef) -> Result<PingMsg> {
395        trace!("Send Pong msg");
396        let mut nonce: [u8; 32] = [0; 32];
397        SysRng.try_fill_bytes(&mut nonce)?;
398
399        let ping_msg = PingMsg {
400            version: self.config.version.v.clone(),
401            nonce,
402        };
403        conn.send_msg(KadNetMsg::new(KadNetCmd::Ping, &ping_msg)?)
404            .await?;
405        Ok(ping_msg)
406    }
407
408    /// Sends a Pong msg
409    async fn send_pong_msg(&self, nonce: [u8; 32], conn: &mut KadConnRef) -> Result<()> {
410        trace!("Send Pong msg");
411        conn.send_msg(KadNetMsg::new(KadNetCmd::Pong, PongMsg(nonce))?)
412            .await?;
413        Ok(())
414    }
415
416    /// Sends a FindPeer msg
417    async fn send_findpeer_msg(&self, conn: &mut KadConnRef, peer_id: &PeerID) -> Result<()> {
418        trace!("Send FindPeer msg");
419        conn.send_msg(KadNetMsg::new(
420            KadNetCmd::FindPeer,
421            FindPeerMsg(peer_id.clone()),
422        )?)
423        .await?;
424        Ok(())
425    }
426
427    /// Sends a Peers msg.
428    async fn send_peers_msg(&self, peer_id: &PeerID, conn: &mut KadConnRef) -> Result<()> {
429        trace!("Send Peers msg");
430        let entries = self
431            .table
432            .closest_entries(&peer_id.0, MAX_PEERS_IN_PEERSMSG);
433
434        let peers: Vec<PeerMsg> = entries.into_iter().map(|e| e.into()).collect();
435        conn.send_msg(KadNetMsg::new(KadNetCmd::Peers, PeersMsg { peers })?)
436            .await?;
437        Ok(())
438    }
439
440    /// Sends a Peer msg advertising our listen and discovery addresses.
441    /// `addrs` carries every data-plane listen endpoint; `discovery_addrs`
442    /// carries the lookup endpoint and (when set) the udp refresh endpoint.
443    /// Not sent when both are empty.
444    async fn send_peer_msg(&self, conn: &mut KadConnRef) -> Result<()> {
445        trace!("Send Peer msg");
446
447        let public_ip = self.config.public_ip;
448        let addrs = self
449            .endpoints
450            .listen
451            .iter()
452            .filter_map(|ep| advertised_addr(ep, public_ip))
453            .collect();
454        let discovery_addrs = [&self.endpoints.lookup, &self.endpoints.refresh]
455            .into_iter()
456            .flatten()
457            .filter_map(|ep| advertised_addr(ep, public_ip))
458            .collect();
459
460        let peer_msg = PeerMsg {
461            peer_id: self.id.clone(),
462            addrs,
463            discovery_addrs,
464            protocols: self.bloom.snapshot().advertised,
465        };
466        // Nothing to dial us on: stay out of other routing tables.
467        if !is_reachable(&peer_msg) {
468            return Ok(());
469        }
470        conn.send_msg(KadNetMsg::new(KadNetCmd::Peer, &peer_msg)?)
471            .await?;
472        Ok(())
473    }
474
475    /// Sends a Shutdown msg.
476    async fn send_shutdown_msg(&self, conn: &mut KadConnRef) -> Result<()> {
477        trace!("Send Shutdown msg");
478        conn.send_msg(KadNetMsg::new(KadNetCmd::Shutdown, ShutdownMsg(0))?)
479            .await?;
480        Ok(())
481    }
482}
483
484/// The PeerAddr to advertise for `ep`, with its IP replaced by
485/// `public_ip` when both are the same family.
486fn advertised_addr(ep: &Endpoint, public_ip: Option<IpAddr>) -> Option<PeerAddr> {
487    let mut pa = PeerAddr::from_endpoint(ep, 0)?;
488    if let (Some(public), Addr::Ip(ip)) = (public_ip, &pa.addr)
489        && public.is_ipv4() == ip.is_ipv4()
490    {
491        pa.addr = Addr::Ip(public);
492    }
493    Some(pa)
494}
495
496/// True if the peer advertises at least one address to reach it on.
497/// Peers with only discovery addresses (e.g. bootstrap nodes) count.
498fn is_reachable(p: &PeerMsg) -> bool {
499    !p.addrs.is_empty() || !p.discovery_addrs.is_empty()
500}
501
502/// Reject PeerMsgs that advertise more addresses than a legitimate
503/// peer would. Caps memory blow-up from malicious or buggy peers.
504fn validate_peer_msg(p: &mut PeerMsg) -> Result<()> {
505    if p.addrs.len() > MAX_ADDRS_PER_PEER {
506        return Err(Error::InvalidMsg(format!(
507            "PeerMsg.addrs has {} entries, max {MAX_ADDRS_PER_PEER}",
508            p.addrs.len()
509        )));
510    }
511    p.discovery_addrs
512        .retain(|a| !matches!(a.protocol, Protocol::Tls));
513    if p.discovery_addrs.len() > MAX_DISCOVERY_ADDRS_PER_PEER {
514        return Err(Error::InvalidMsg(format!(
515            "PeerMsg.discovery_addrs has {} entries, max {MAX_DISCOVERY_ADDRS_PER_PEER}",
516            p.discovery_addrs.len()
517        )));
518    }
519    Ok(())
520}
521
522#[cfg(test)]
523mod tests {
524    use super::*;
525
526    #[test]
527    fn reachable_needs_some_address() {
528        let addr = PeerAddr::from_endpoint(&"tcp://10.0.0.1:8000".parse().unwrap(), 0).unwrap();
529        let mut peer = PeerMsg {
530            peer_id: PeerID::from([1u8; 32]),
531            addrs: vec![],
532            discovery_addrs: vec![],
533            protocols: Default::default(),
534        };
535        assert!(!is_reachable(&peer));
536
537        // A discovery-only peer (e.g. a bootstrap node) is reachable.
538        peer.discovery_addrs = vec![addr.clone()];
539        assert!(is_reachable(&peer));
540
541        peer.discovery_addrs = vec![];
542        peer.addrs = vec![addr];
543        assert!(is_reachable(&peer));
544    }
545
546    #[test]
547    fn advertised_addr_replaces_same_family_ip() {
548        let public: IpAddr = "203.0.113.9".parse().unwrap();
549
550        let ep: Endpoint = "tcp://0.0.0.0:8000".parse().unwrap();
551        let pa = advertised_addr(&ep, Some(public)).unwrap();
552        assert_eq!(pa.to_endpoint(), "tcp://203.0.113.9:8000".parse().unwrap());
553
554        // Other family and no public IP keep the configured address.
555        let ep: Endpoint = "quic://[::]:9000".parse().unwrap();
556        assert_eq!(
557            advertised_addr(&ep, Some(public)).unwrap().to_endpoint(),
558            ep
559        );
560        let ep: Endpoint = "udp://10.0.0.1:7000".parse().unwrap();
561        assert_eq!(advertised_addr(&ep, None).unwrap().to_endpoint(), ep);
562    }
563}