From 34b174fe6a42ab0023fdd920abef150758677492 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Tue, 28 Mar 2023 14:38:28 +0200 Subject: [PATCH 1/3] DAL/GS: introduce fail_if/fail_if_not helpers to avoid 'else unit' --- src/lib_gossipsub/tezos_gossipsub.ml | 45 +++++++++++++--------------- 1 file changed, 21 insertions(+), 24 deletions(-) diff --git a/src/lib_gossipsub/tezos_gossipsub.ml b/src/lib_gossipsub/tezos_gossipsub.ml index 521e1a5ecf34..66727db432cd 100644 --- a/src/lib_gossipsub/tezos_gossipsub.ml +++ b/src/lib_gossipsub/tezos_gossipsub.ml @@ -286,6 +286,12 @@ module Make (C : AUTOMATON_CONFIG) : } module Helpers = struct + let fail_if cond output_err = + let open Monad.Syntax in + if cond then fail output_err else unit + + let fail_if_not cond output_err = fail_if (not cond) output_err + (* These projections enable let-punning. *) let max_recv_ihave_per_heartbeat state = state.limits.max_recv_ihave_per_heartbeat @@ -510,8 +516,7 @@ module Make (C : AUTOMATON_CONFIG) : let _check_peer_score peer = let open Monad.Syntax in let*! peer_score = get_score ~default:Score.zero peer in - if Score.(peer_score < zero) then Negative_peer_score peer_score |> fail - else unit + fail_if Score.(peer_score < zero) @@ Negative_peer_score peer_score end include Helpers @@ -520,10 +525,9 @@ module Make (C : AUTOMATON_CONFIG) : let check_too_many_recv_ihave_message count = let open Monad.Syntax in let*! max_recv_ihave_per_heartbeat in - if count > max_recv_ihave_per_heartbeat then - Too_many_recv_ihave_messages {count; max = max_recv_ihave_per_heartbeat} - |> fail - else unit + fail_if (count > max_recv_ihave_per_heartbeat) + @@ Too_many_recv_ihave_messages + {count; max = max_recv_ihave_per_heartbeat} (* FIXME https://gitlab.com/tezos/tezos/-/issues/5016 @@ -533,21 +537,18 @@ module Make (C : AUTOMATON_CONFIG) : let check_too_many_sent_iwant_message count = let open Monad.Syntax in let*! max_sent_iwant_per_heartbeat in - if count > max_sent_iwant_per_heartbeat then - Too_many_sent_iwant_messages {count; max = max_sent_iwant_per_heartbeat} - |> fail - else unit + fail_if (count > max_sent_iwant_per_heartbeat) + @@ Too_many_sent_iwant_messages + {count; max = max_sent_iwant_per_heartbeat} let check_topic_tracked topic = let open Monad.Syntax in let*! is_topic_tracked = topic_is_tracked topic in - if not is_topic_tracked then Message_topic_not_tracked |> fail else unit + fail_if (not is_topic_tracked) Message_topic_not_tracked let check_not_empty iwant_message_ids = - let open Monad.Syntax in - match iwant_message_ids with - | [] -> Message_requested_message_ids [] |> fail - | _ -> unit + fail_if (List.is_empty iwant_message_ids) + @@ Message_requested_message_ids [] let filter peer message_ids : Message_id.t list Monad.t = let open Monad.Syntax in @@ -645,7 +646,7 @@ module Make (C : AUTOMATON_CONFIG) : let check_filter peer = let open Monad.Syntax in let*! peer_filter in - if peer_filter peer `Graft then unit else Peer_filtered |> fail + fail_if_not (peer_filter peer `Graft) Peer_filtered let check_topic_known mesh_opt = let open Monad.Syntax in @@ -654,8 +655,7 @@ module Make (C : AUTOMATON_CONFIG) : | Some mesh -> pass mesh let check_not_in_mesh mesh peer = - let open Monad.Syntax in - if Peer.Set.mem peer mesh then Peer_already_in_mesh |> fail else unit + fail_if (Peer.Set.mem peer mesh) Peer_already_in_mesh let check_not_direct peer = let open Monad.Syntax in @@ -733,9 +733,8 @@ module Make (C : AUTOMATON_CONFIG) : let open Monad.Syntax in let*! accept_px_threshold in let*! score = get_score ~default:Score.zero peer in - if Compare.Float.(score |> Score.float < accept_px_threshold) then - Ignore_PX_score_too_low score |> fail - else unit + fail_if Compare.Float.(score |> Score.float < accept_px_threshold) + @@ Ignore_PX_score_too_low score let handle peer topic ~px ~backoff = let open Monad.Syntax in @@ -856,9 +855,7 @@ module Make (C : AUTOMATON_CONFIG) : let check_is_not_subscribed topic : (unit, [`Join] output) Monad.check = let open Monad.Syntax in let*! mesh in - match Topic.Map.find topic mesh with - | None -> unit - | Some _ -> Already_subscribed |> fail + fail_if (Topic.Map.mem topic mesh) Already_subscribed let init_mesh topic : [`Join] output Monad.t = let open Monad.Syntax in -- GitLab From 70e34c358e2db321791ac7d8cb37eabfaff8c938 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Wed, 29 Mar 2023 14:00:05 +0200 Subject: [PATCH 2/3] DAL/GS: add more doc in gossipsub_inft --- src/lib_gossipsub/gossipsub_intf.ml | 93 +++++++++++++++++++++++----- src/lib_gossipsub/tezos_gossipsub.ml | 8 +-- 2 files changed, 83 insertions(+), 18 deletions(-) diff --git a/src/lib_gossipsub/gossipsub_intf.ml b/src/lib_gossipsub/gossipsub_intf.ml index 015aa4478198..212677dc3bc8 100644 --- a/src/lib_gossipsub/gossipsub_intf.ml +++ b/src/lib_gossipsub/gossipsub_intf.ml @@ -218,49 +218,109 @@ module type AUTOMATON = sig (** Output produced by one of the actions below. *) type _ output = | Negative_peer_score : Score.t -> [`IHave] output + (** The peer who sent an [`IHave] message has a negative score. *) | Too_many_recv_ihave_messages : {count : int; max : int} -> [`IHave] output + (** The peer sent us more than [max] ihave messages within two + successive heartbeat calls. *) | Too_many_sent_iwant_messages : {count : int; max : int} -> [`IHave] output + (** We sent more than [max] iwant messages to this peer within two + successive heartbeat calls. *) | Message_topic_not_tracked : [`IHave] output + (** We received an [`IHave] message for a topic we don't track. *) | Message_requested_message_ids : Message_id.t list -> [`IHave] output + (** The messages IDs we want to request from the peer which sent us an + [`IHave] message. The implementation honors the + [max_sent_iwant_per_heartbeat] limit. *) | On_iwant_messages_to_route : { routed_message_ids : [`Ignored | `Not_found | `Message of message] Message_id.Map.t; } -> [`IWant] output + (** As an answer for an [`IWant] message, the automaton returns a map + associating to each requested message_id either [`Ignored] if the + peer is filtered out by [peer_filter], [`Not_found] if the message + is not found, or [Message m] if [m] is the message of the given + ID. *) | Peer_filtered : [`Graft] output + (** The peer we attempt to graft has not been selected by + [peer_filter]. *) | Unknown_topic : [`Graft] output + (** We didn't join the topic for which we are attempting to graft a + peer. *) | Peer_already_in_mesh : [`Graft] output + (** Attempting to graft a peer which has already been grafted. *) | Grafting_direct_peer : [`Graft] output + (** Attempting to graft a direct peer. *) | Unexpected_grafting_peer : [`Graft] output + (** The peer we attempt to graft is not known. *) | Grafting_peer_with_negative_score : [`Graft] output + (** Attempting to graft a peer with a negative score. *) | Grafting_successfully : [`Graft] output + (** Grafting the given peer for the provided topic succeeded. *) | Peer_backed_off : [`Graft] output + (** We cannot graft the given peer because it is backed off. *) | Mesh_full : [`Graft] output + (** Grafting a peer for a topic whose mesh has already sufficiently many + peers. *) | No_peer_in_mesh : [`Prune] output + (** Attempting to prune a peer which is not in the mesh. *) | Ignore_PX_score_too_low : Score.t -> [`Prune] output + (** The given peer has been pruned for the given topic, but no + alternative peers are returned because the peer's score is too low. + The score of the peer is included in the return value. *) | No_PX : [`Prune] output + (** The given peer has been pruned for the given topic. But the given + set of peers alternatives in {!prune} is empty. *) + (* FIXME: https://gitlab.com/tezos/tezos/-/issues/5251 + + Some fixes might be needed for the prune case. Once done, update the + docstring. *) | PX : Peer.Set.t -> [`Prune] output + (** The given peer has been pruned for the given topic. The given set of + peers alternatives in {!prune} for that topic is returned. *) | Publish_message : Peer.Set.t -> [`Publish] output - | Already_subscribed : [`Join] output + (** If the peer is subscribed to the topic, returns the set of peers in the topic's mesh. + Otherwise, it will return the set of peers in the topic's fanout.*) + | Already_joined : [`Join] output + (** Attempting to join a topic we already joined. *) | Joining_topic : {to_graft : Peer.Set.t} -> [`Join] output - | Not_subscribed : [`Leave] output + (** When successfully joining a topic, the set of grafted peers for that + topic is returned. *) + | Not_joined : [`Leave] output + (** Attempting to leave a topic which we didn't join or had already + left. *) | Leaving_topic : {to_prune : Peer.Set.t} -> [`Leave] output + (** When successfully leaving a topic, the set of pruned peers for that + topic is returned. *) | Heartbeat : { - (* topics per peer to graft to *) to_graft : Topic.Set.t Peer.Map.t; - (* topics per peer to prune from *) + (** The set of topics per peer that have been grafted. *) to_prune : Topic.Set.t Peer.Map.t; - (* set of peers for which peer exchange (PX) will not be proposed *) + (** The set of topics per peer that have been pruned. *) noPX_peers : Peer.Set.t; + (** Set of peers for which peer exchange (PX) will not be + proposed. *) } -> [`Heartbeat] output | Peer_added : [`Add_peer] output + (** The output returned when successfully adding a peer. *) | Peer_already_known : [`Add_peer] output + (** The output returned when attempting to add a peer which is already + known. *) | Removing_peer : [`Remove_peer] output + (** The output returned when successfully removing a peer. *) | Subscribed : [`Subscribe] output + (** The output returned once we successfully processed a subscribe + request sent from a peer. *) | Subscribe_to_unknown_peer : [`Subscribe] output + (** The output returned when we receive a subscribe message from a peer + we don't know.*) | Unsubscribed : [`Unsubscribe] output + (** The output returned once we successfully processed an unsubscribe + request sent from a peer. *) | Unsubscribe_from_unknown_peer : [`Unsubscribe] output + (** The output returned when we receive an unsubscribe message from a + peer we don't know.*) (** A type alias for the state monad. *) type 'a monad := state -> state * 'a output @@ -301,26 +361,31 @@ module type AUTOMATON = sig on this topic. *) val handle_prune : prune -> [`Prune] monad - (** [publish { sender; topic; message_id; message }] allows to route a - message on the gossip network. If [sender=None], the message - comes from the application layer and the local node is the sender. *) + (** [publish { sender; topic; message_id; message }] allows to route a message + on the gossip network. If [sender=None], the message comes from the + application layer and the local node is the sender. The function returns a + set of peers to which the (full) message will be directly forwarded. *) val publish : publish -> [`Publish] monad (** [heartbeat] executes the heartbeat routine of the algorithm. *) val heartbeat : [`Heartbeat] monad - (** [handle_subscribe {topic; peer}] handles a request from a remote [peer] to - subscribe to a [topic]. *) + (** [handle_subscribe {topic; peer}] handles a request from a remote [peer] + informing us that it is subscribed to [topic]. *) val handle_subscribe : subscribe -> [`Subscribe] monad - (** [handle_unsubscribe {topic; peer}] handles a request from a remote [peer] to - unsubscribe to a [topic]. *) + (** [handle_unsubscribe {topic; peer}] handles a request from a remote [peer] + informing us that it unsubscribed from [topic]. *) val handle_unsubscribe : unsubscribe -> [`Unsubscribe] monad - (** [join { topic }] handles a join/subscribe to a new topic. *) + (** [join { topic }] handles a join to a new topic. On success, the function + returns the set of peers that have been grafted to form the mesh of the + joined topic. *) val join : join -> [`Join] monad - (** [leave { topic }] handles a leave/unsubscribe from a topic. *) + (** [leave { topic }] handles a leave from a topic. On success, the function + returns the set of peers, forming the mesh, that have been pruned for that + topic. *) val leave : leave -> [`Leave] monad val pp_add_peer : Format.formatter -> add_peer -> unit diff --git a/src/lib_gossipsub/tezos_gossipsub.ml b/src/lib_gossipsub/tezos_gossipsub.ml index 66727db432cd..9d14659be835 100644 --- a/src/lib_gossipsub/tezos_gossipsub.ml +++ b/src/lib_gossipsub/tezos_gossipsub.ml @@ -142,9 +142,9 @@ module Make (C : AUTOMATON_CONFIG) : | No_PX : [`Prune] output | PX : Peer.Set.t -> [`Prune] output | Publish_message : Peer.Set.t -> [`Publish] output - | Already_subscribed : [`Join] output + | Already_joined : [`Join] output | Joining_topic : {to_graft : Peer.Set.t} -> [`Join] output - | Not_subscribed : [`Leave] output + | Not_joined : [`Leave] output | Leaving_topic : {to_prune : Peer.Set.t} -> [`Leave] output | Heartbeat : { to_graft : Topic.Set.t Peer.Map.t; @@ -855,7 +855,7 @@ module Make (C : AUTOMATON_CONFIG) : let check_is_not_subscribed topic : (unit, [`Join] output) Monad.check = let open Monad.Syntax in let*! mesh in - fail_if (Topic.Map.mem topic mesh) Already_subscribed + fail_if (Topic.Map.mem topic mesh) Already_joined let init_mesh topic : [`Join] output Monad.t = let open Monad.Syntax in @@ -919,7 +919,7 @@ module Make (C : AUTOMATON_CONFIG) : let open Monad.Syntax in let*! mesh in match Topic.Map.find topic mesh with - | None -> Not_subscribed |> fail + | None -> Not_joined |> fail | Some mesh -> pass mesh let handle_mesh topic mesh : [`Leave] output Monad.t = -- GitLab From 1bfc60086fbc77524b299e6e843f581e291ed1a7 Mon Sep 17 00:00:00 2001 From: "iguerNL@Functori" Date: Tue, 28 Mar 2023 20:08:59 +0200 Subject: [PATCH 3/3] DAL/GS: some code refactoring --- src/lib_gossipsub/tezos_gossipsub.ml | 104 +++++++++++++++------------ 1 file changed, 57 insertions(+), 47 deletions(-) diff --git a/src/lib_gossipsub/tezos_gossipsub.ml b/src/lib_gossipsub/tezos_gossipsub.ml index 9d14659be835..399b1eb6ee0f 100644 --- a/src/lib_gossipsub/tezos_gossipsub.ml +++ b/src/lib_gossipsub/tezos_gossipsub.ml @@ -544,7 +544,7 @@ module Make (C : AUTOMATON_CONFIG) : let check_topic_tracked topic = let open Monad.Syntax in let*! is_topic_tracked = topic_is_tracked topic in - fail_if (not is_topic_tracked) Message_topic_not_tracked + fail_if_not is_topic_tracked Message_topic_not_tracked let check_not_empty iwant_message_ids = fail_if (List.is_empty iwant_message_ids) @@ -620,18 +620,18 @@ module Make (C : AUTOMATON_CONFIG) : exceed some pre-defined limit. *) List.fold_left (fun (memory_cache, messages) message_id -> - match - Memory_cache.record_message_access peer message_id memory_cache - with - | None -> - (memory_cache, Message_id.Map.add message_id `Not_found messages) - | Some (memory_cache, message) -> - let messages = - if peer_filter peer (`IWant message_id) then - Message_id.Map.add message_id (`Message message) messages - else Message_id.Map.add message_id `Ignored messages - in - (memory_cache, messages)) + let memory_cache, info = + match + Memory_cache.record_message_access peer message_id memory_cache + with + | None -> (memory_cache, `Not_found) + | Some (memory_cache, message) -> + ( memory_cache, + if peer_filter peer (`IWant message_id) then + `Message message + else `Ignored ) + in + (memory_cache, Message_id.Map.add message_id info messages)) (memory_cache, routed_message_ids) message_ids in @@ -648,8 +648,9 @@ module Make (C : AUTOMATON_CONFIG) : let*! peer_filter in fail_if_not (peer_filter peer `Graft) Peer_filtered - let check_topic_known mesh_opt = + let check_topic_known topic = let open Monad.Syntax in + let*! mesh_opt = find_mesh topic in match mesh_opt with | None -> Unknown_topic |> fail | Some mesh -> pass mesh @@ -676,12 +677,13 @@ module Make (C : AUTOMATON_CONFIG) : let check_mesh_size mesh connection = let open Monad.Syntax in let*! degree_high in - (* Check the number of mesh peers; if it is at (or over) [degree_high], we only accept grafts - from peers with outbound connections; this is a defensive check to restrict potential - mesh takeover attacks combined with love bombing *) - if Peer.Set.cardinal mesh >= degree_high && not connection.outbound then - Mesh_full |> fail - else unit + (* Check the number of mesh peers; if it is at (or over) [degree_high], we + only accept grafts from peers with outbound connections; this is a + defensive check to restrict potential mesh takeover attacks combined + with love bombing *) + fail_if + ((not connection.outbound) && Peer.Set.cardinal mesh >= degree_high) + Mesh_full let check_backoff peer topic {backoff; score; _} = let open Monad.Syntax in @@ -708,8 +710,7 @@ module Make (C : AUTOMATON_CONFIG) : Be sure that the peers that requested failed/rejected graft are properly pruned. *) let open Monad.Syntax in let*? () = check_filter peer in - let*! mesh_opt = find_mesh topic in - let*? mesh = check_topic_known mesh_opt in + let*? mesh = check_topic_known topic in let*? () = check_not_in_mesh mesh peer in let*? connection = check_not_direct peer in let*? () = check_backoff peer topic connection in @@ -736,23 +737,27 @@ module Make (C : AUTOMATON_CONFIG) : fail_if Compare.Float.(score |> Score.float < accept_px_threshold) @@ Ignore_PX_score_too_low score - let handle peer topic ~px ~backoff = + let check_topic_known topic = let open Monad.Syntax in let*! mesh_opt = find_mesh topic in match mesh_opt with - | None -> return No_peer_in_mesh - | Some mesh -> - (* FIXME https://gitlab.com/tezos/tezos/-/issues/5006 - - backoff computation. *) - let mesh = Peer.Set.remove peer mesh in - let* () = set_mesh_topic topic mesh in - let* _ = add_backoff backoff topic peer in - let px = Peer.Set.of_seq px in - if Peer.Set.is_empty px then No_PX |> return - else - let*? () = check_px_score peer in - return (PX px) + | None -> No_peer_in_mesh |> fail + | Some mesh -> pass mesh + + let handle peer topic ~px ~backoff = + let open Monad.Syntax in + let*? mesh = check_topic_known topic in + (* FIXME https://gitlab.com/tezos/tezos/-/issues/5006 + + backoff computation. *) + let mesh = Peer.Set.remove peer mesh in + let* () = set_mesh_topic topic mesh in + let* () = add_backoff backoff topic peer in + let px = Peer.Set.of_seq px in + if Peer.Set.is_empty px then No_PX |> return + else + let*? () = check_px_score peer in + return (PX px) end let handle_prune : prune -> [`Prune] output Monad.t = @@ -809,22 +814,24 @@ module Make (C : AUTOMATON_CONFIG) : let*! fanout_opt = find_fanout topic in match fanout_opt with | None -> - let filter _peer {direct; score; _} = - (not direct) - && Compare.Float.(score |> Score.float >= gossip_publish_threshold) + let filter_by_score score = + Compare.Float.(score |> Score.float >= gossip_publish_threshold) + in + let filter1 _peer {direct; score; _} = + (not direct) && filter_by_score score in let* not_direct_peers = - select_peers topic ~filter ~max:degree_optimal + select_peers topic ~filter:filter1 ~max:degree_optimal in let* () = set_fanout_topic topic now not_direct_peers in (* FIXME https://gitlab.com/tezos/tezos/-/issues/5010 We could avoid this call by directly having a map of direct peers in the state. *) - let filter peer ({direct; _} as connection) = - filter peer connection || direct + let filter2 _peer {direct; score; _} = + direct || filter_by_score score in - select_peers topic ~filter ~max:degree_optimal + select_peers topic ~filter:filter2 ~max:degree_optimal | Some fanout -> let* () = set_fanout_topic topic now fanout.peers in return fanout.peers @@ -844,6 +851,10 @@ module Make (C : AUTOMATON_CONFIG) : ~some:(fun peer -> Peer.Set.remove peer peers) sender in + (* TODO: https://gitlab.com/tezos/tezos/-/issues/5272 + + Filter out peers from which we already received the message, or an + IHave message? *) Publish_message peers |> return end @@ -882,12 +893,11 @@ module Make (C : AUTOMATON_CONFIG) : (* We prioritize fanout peers to be in the mesh for this topic. If we need more peers, we look at all our peers subscribed to this topic. *) - if Peer.Set.cardinal valid_fanout_peers >= degree_optimal then + let valid_fanout_peers_len = Peer.Set.cardinal valid_fanout_peers in + if valid_fanout_peers_len >= degree_optimal then return valid_fanout_peers else - let max = - max 0 (degree_optimal - Peer.Set.cardinal valid_fanout_peers) - in + let max = max 0 (degree_optimal - valid_fanout_peers_len) in let* more_peers = let filter peer {backoff; score; direct; _} = not -- GitLab