diff --git a/src/lib_base/p2p_point.ml b/src/lib_base/p2p_point.ml index 3363d01587aa429b852133864867b4c438b673fe..e4ae04175a4b97b24eb3a7101eaead9fb7be1156 100644 --- a/src/lib_base/p2p_point.ml +++ b/src/lib_base/p2p_point.ml @@ -33,8 +33,6 @@ module Id = struct let equal p1 p2 = compare p1 p2 = 0 - let hash = Hashtbl.hash - let pp ppf (addr, port) = match Ipaddr.v4_of_v6 addr with | Some addr -> @@ -140,7 +138,14 @@ end module Map = Map.Make (Id) module Set = Set.Make (Id) -module Table = Hashtbl.Make (Id) + +module Table = Hashtbl.MakeSeeded (struct + type t = Id.t + + let equal = Id.equal + + let hash = Hashtbl.seeded_hash +end) module Filter = struct type t = Requested | Accepted | Running | Disconnected diff --git a/src/lib_base/p2p_point.mli b/src/lib_base/p2p_point.mli index dab4a169b8bfd726f39d7be509bb343adc2529d8..9bd0d4afc3b18a04babba88053d93f58e90ae0a5 100644 --- a/src/lib_base/p2p_point.mli +++ b/src/lib_base/p2p_point.mli @@ -58,7 +58,7 @@ module Map : Map.S with type key = Id.t module Set : Set.S with type elt = Id.t -module Table : Hashtbl.S with type key = Id.t +module Table : Hashtbl.SeededS with type key = Id.t module Filter : sig type t = Requested | Accepted | Running | Disconnected diff --git a/src/lib_client_base/client_confirmations.ml b/src/lib_client_base/client_confirmations.ml index 8b29fb42c467704d3dd489bb299b43741a3b1c85..0c25f0f8e0eb119a7c61a5726f12c31dce510072 100644 --- a/src/lib_client_base/client_confirmations.ml +++ b/src/lib_client_base/client_confirmations.ml @@ -51,7 +51,7 @@ let wait_for_operation_inclusion (ctxt : #Client_context.full) ~chain if the `hash` contains the operation in list `i` at position `j` and if `hash` denotes the `n-th` predecessors of the block. *) let blocks : ((Block_hash.t * int * int) * int) option Block_hash.Table.t = - Block_hash.Table.create confirmations + Block_hash.Table.create ~random:true confirmations in (* Fetch _all_ the 'unknown' predecessors af a block. *) let fetch_predecessors (hash, header) = diff --git a/src/lib_crypto/blake2B.ml b/src/lib_crypto/blake2B.ml index 3c7f160c7a20c4f6b5eb68f6ec7f1f20dff775f1..916d1c282cad5b1bb96054e4a988d3b50878698b 100644 --- a/src/lib_crypto/blake2B.ml +++ b/src/lib_crypto/blake2B.ml @@ -188,12 +188,26 @@ struct let open Data_encoding in conv to_bytes of_bytes_exn (Fixed.bytes size) - let hash = - if Compare.Int.(size >= 8) then fun h -> - Int64.to_int (TzEndian.get_int64 (to_bytes h) 0) - else if Compare.Int.(size >= 4) then fun h -> - Int32.to_int (TzEndian.get_int32 (to_bytes h) 0) - else fun h -> + let int_rotate offset i = + let open Stdlib in + assert (0 <= offset) ; + assert (offset < 32) ; + (i lsl offset) lor (i lsr (32 - offset)) + + let seeded_hash = + (* NOTE: we hash to small integers (32bit) because the OCaml hashtable only + cares about a few bits *) + let open Compare.Int + (* shadowing comparators *) in + if size > 4 then fun seed h -> + let seed = abs seed in + int_rotate (seed mod 32) + @@ Int32.to_int + @@ TzEndian.get_int32 (to_bytes h) (seed mod (size - 4)) + else fun seed h -> + let seed = abs seed in + int_rotate (seed mod 32) + @@ let r = ref 0 in let h = to_bytes h in for i = 0 to size - 1 do @@ -201,6 +215,8 @@ struct done ; !r + let hash = seeded_hash 0 + type Base58.data += Data of t let b58check_encoding = @@ -227,6 +243,8 @@ struct let equal = equal let hash = hash + + let seeded_hash = seeded_hash end) end diff --git a/src/lib_crypto/chain_id.ml b/src/lib_crypto/chain_id.ml index d9034470fbe641a3e61b64756d060e9944938493..6cb49e4135702c2c3d82c593bec4db6b08beda06 100644 --- a/src/lib_crypto/chain_id.ml +++ b/src/lib_crypto/chain_id.ml @@ -131,7 +131,18 @@ let raw_encoding = let open Data_encoding in conv to_bytes of_bytes_exn (Fixed.bytes size) -let hash h = Int32.to_int (TzEndian.get_int32 (to_bytes h) 0) +let int_rotate offset i = + let open Stdlib in + assert (0 <= offset) ; + assert (offset < 32) ; + (i lsl offset) lor (i lsr (32 - offset)) + +let seeded_hash seed h = + int_rotate (abs seed mod 32) + @@ Int32.to_int + @@ TzEndian.get_int32 (to_bytes h) 0 + +let hash h = seeded_hash 0 h let of_block_hash bh = hash_bytes [Block_hash.to_bytes bh] @@ -157,4 +168,6 @@ include Helpers.Make (struct let equal = equal let hash = hash + + let seeded_hash = seeded_hash end) diff --git a/src/lib_crypto/helpers.ml b/src/lib_crypto/helpers.ml index 7cff72157550384a390252ec211ea81c01b53f0c..e1be57168f1dcf5b897fddc7b8080378dc6dbb25 100644 --- a/src/lib_crypto/helpers.ml +++ b/src/lib_crypto/helpers.ml @@ -191,6 +191,10 @@ module MakeIterator (H : sig val equal : t -> t -> bool val hash : t -> int + + (* [seeded_hash] is a seeded alternative to [hash] meant to be used to create + seeded hashtables. Check {!Stdlib.Hashtbl.MakeSeeded} for details. *) + val seeded_hash : int -> t -> int end) = struct module Set = struct @@ -224,10 +228,10 @@ struct end module Table = struct - include Hashtbl.Make (struct + include Hashtbl.MakeSeeded (struct type t = H.t - let hash = H.hash + let hash = H.seeded_hash let equal = H.equal end) @@ -295,6 +299,8 @@ module Make (H : sig val equal : t -> t -> bool val hash : t -> int + + val seeded_hash : int -> t -> int end) = struct include MakeB58 (H) diff --git a/src/lib_crypto/s.ml b/src/lib_crypto/s.ml index 2a43d4d74d1a12bea5b51fa23a908269dfc6fdb4..d4a0ea38b472e2abaafc2b23f28de653ae51ff72 100644 --- a/src/lib_crypto/s.ml +++ b/src/lib_crypto/s.ml @@ -138,6 +138,8 @@ module type INDEXES = sig val hash : t -> int + val seeded_hash : int -> t -> int + val to_path : t -> string list -> string list val of_path : string list -> t option @@ -163,7 +165,7 @@ module type INDEXES = sig end module Table : sig - include Hashtbl.S with type key = t + include Hashtbl.SeededS with type key = t val encoding : 'a Data_encoding.t -> 'a t Data_encoding.t end diff --git a/src/lib_crypto/signature.ml b/src/lib_crypto/signature.ml index 54099d8b4873d299c3932231c1f15931ce2d2c14..06d096aa77e64f7692bf6511f8dd8b31773cc288 100644 --- a/src/lib_crypto/signature.ml +++ b/src/lib_crypto/signature.ml @@ -210,6 +210,8 @@ module Public_key_hash = struct let prefix_path _ = assert false (* unused *) + let seeded_hash = Hashtbl.seeded_hash + let hash = Hashtbl.hash include Compare.Make (struct @@ -252,6 +254,8 @@ module Public_key_hash = struct let hash = hash + let seeded_hash = seeded_hash + let compare = compare let equal = equal diff --git a/src/lib_crypto/test/dune b/src/lib_crypto/test/dune index 7ac8114317d1606d6c653d6a0d762697bc58775d..07b5e995fdd1b3eec19f031dfc02d23fc0560f6b 100644 --- a/src/lib_crypto/test/dune +++ b/src/lib_crypto/test/dune @@ -4,6 +4,7 @@ test_base58 test_ed25519 test_blake2b + test_ids test_pvss test_crypto_box test_deterministic_nonce) @@ -23,6 +24,7 @@ test_base58.exe test_ed25519.exe test_blake2b.exe + test_ids.exe test_pvss.exe test_crypto_box.exe test_deterministic_nonce.exe)) @@ -47,6 +49,10 @@ (name runtest_blake2b) (action (run %{exe:test_blake2b.exe}))) +(alias + (name runtest_ids) + (action (run %{exe:test_ids.exe}))) + (alias (name runtest_pvss) (action (run %{exe:test_pvss.exe}))) @@ -67,6 +73,7 @@ (alias runtest_base58) (alias runtest_ed25519) (alias runtest_blake2b) + (alias runtest_ids) (alias runtest_pvss) (alias runtest_crypto_box) (alias runtest_deterministic_nonce))) diff --git a/src/lib_crypto/test/test_ids.ml b/src/lib_crypto/test/test_ids.ml new file mode 100644 index 0000000000000000000000000000000000000000..cef8986d1e5f230915f8297dd1067b4d5c5273ab --- /dev/null +++ b/src/lib_crypto/test/test_ids.ml @@ -0,0 +1,57 @@ +(*****************************************************************************) +(* *) +(* Open Source License *) +(* Copyright (c) 2020 Nomadic Labs *) +(* *) +(* Permission is hereby granted, free of charge, to any person obtaining a *) +(* copy of this software and associated documentation files (the "Software"),*) +(* to deal in the Software without restriction, including without limitation *) +(* the rights to use, copy, modify, merge, publish, distribute, sublicense, *) +(* and/or sell copies of the Software, and to permit persons to whom the *) +(* Software is furnished to do so, subject to the following conditions: *) +(* *) +(* The above copyright notice and this permission notice shall be included *) +(* in all copies or substantial portions of the Software. *) +(* *) +(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*) +(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, *) +(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL *) +(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*) +(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING *) +(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER *) +(* DEALINGS IN THE SOFTWARE. *) +(* *) +(*****************************************************************************) + +let test_seeded_hash (module H : S.HASH) seed input = + ignore @@ H.seeded_hash seed @@ H.hash_string input + +let hashes = + [ (module Chain_id : S.HASH); + (module Block_hash : S.HASH); + (module Operation_hash : S.HASH); + (module Protocol_hash : S.HASH); + (module Context_hash : S.HASH); + (module Crypto_box.Public_key_hash : S.HASH) ] + +let seeds = Array.init 256 (fun i -> i - 128) + +let inputs = + [ []; + [""]; + ["0"]; + ["lkjahflkjahdlfkajshlfkjlfjhalsdfjhlasdjfhlasdjfhlasjdfhlajdflajshdflaksf"]; + ["asldkfj"; "alksjdhfl"; "lkajshdlfkasj"]; + [""; ""; ""; ""; ""; ""]; + ["\x00"; "\x00"; "a"; "\x00"; "a"; "a"] ] + +let seeded_hash_safety () = + ListLabels.iter hashes ~f:(fun hash -> + ArrayLabels.iter seeds ~f:(fun seed -> + ListLabels.iter inputs ~f:(fun input -> + test_seeded_hash hash seed input))) + +let seeded_hash_safety_test = + [("seeded_hash safety", `Quick, seeded_hash_safety)] + +let () = Alcotest.run "tezos-crypto" [("INDEXES", seeded_hash_safety_test)] diff --git a/src/lib_p2p/p2p_acl.ml b/src/lib_p2p/p2p_acl.ml index 9bffe129861b2b2ff99c56e19cd8ebf2cc20c94a..fccfe0be9de87a337d50d6760471c689dd328ea7 100644 --- a/src/lib_p2p/p2p_acl.ml +++ b/src/lib_p2p/p2p_acl.ml @@ -126,7 +126,7 @@ let create size = greylist_ips = IpSet.empty; greylist_peers = PeerFIFOCache.create size; banned_ips = IpTable.create 53; - banned_peers = P2p_peer.Table.create 53; + banned_peers = P2p_peer.Table.create ~random:true 53; } (* Check if an ip is banned. Priority is given to the static diff --git a/src/lib_p2p/p2p_connect_handler.ml b/src/lib_p2p/p2p_connect_handler.ml index bd18332078cb6b0055ec058a2491e91607652e88..f840db3fdb2702fcd8b7a91b17102d26176d107b 100644 --- a/src/lib_p2p/p2p_connect_handler.ml +++ b/src/lib_p2p/p2p_connect_handler.ml @@ -72,7 +72,7 @@ let create ?(p2p_versions = P2p_version.supported) config pool message_config message_config.P2p_params.distributed_db_versions ~p2p_versions; custom_p2p_versions = p2p_versions; - incoming = P2p_point.Table.create 53; + incoming = P2p_point.Table.create ~random:true 53; io_sched; encoding = P2p_message.encoding message_config.P2p_params.encoding; triggers; diff --git a/src/lib_p2p/p2p_pool.ml b/src/lib_p2p/p2p_pool.ml index 82f17702d973c30f686e333598b62bd4f6f3f26b..a59bea6b938d6bdce8aa13478196fa067e945833 100644 --- a/src/lib_p2p/p2p_pool.ml +++ b/src/lib_p2p/p2p_pool.ml @@ -453,11 +453,11 @@ let create config peer_meta_config triggers ~log = { config; peer_meta_config; - my_id_points = P2p_point.Table.create 7; - known_peer_ids = P2p_peer.Table.create 53; - connected_peer_ids = P2p_peer.Table.create 53; - known_points = P2p_point.Table.create 53; - connected_points = P2p_point.Table.create 53; + my_id_points = P2p_point.Table.create ~random:true 7; + known_peer_ids = P2p_peer.Table.create ~random:true 53; + connected_peer_ids = P2p_peer.Table.create ~random:true 53; + known_points = P2p_point.Table.create ~random:true 53; + connected_points = P2p_point.Table.create ~random:true 53; triggers; acl = P2p_acl.create 1023; log; diff --git a/src/lib_requester/requester.ml b/src/lib_requester/requester.ml index f3eefe382fa5c71d3fdf4d419326cf3d9ba06430..3635a004624ea08cfc080373613acb20b28bc273 100644 --- a/src/lib_requester/requester.ml +++ b/src/lib_requester/requester.ml @@ -77,6 +77,7 @@ module type FULL_REQUESTER = sig val pending_requests : t -> int val create : + ?random_table:bool -> ?global_input:(key * value) Lwt_watcher.input -> request_param -> store -> @@ -104,7 +105,7 @@ module type MEMORY_TABLE = sig type key - val create : int -> 'a t + val create : ?random:bool -> int -> 'a t val find : 'a t -> key -> 'a option @@ -458,7 +459,7 @@ end = struct { param; queue = Lwt_pipe.create (); - pending = Table.create 17; + pending = Table.create ~random:true 17; events = Lwt.return_nil; canceler = Lwt_canceler.create (); worker = Lwt.return_unit; @@ -707,9 +708,9 @@ end = struct let watch s = Lwt_watcher.create_stream s.input - let create ?global_input request_param disk = + let create ?random_table:random ?global_input request_param disk = let scheduler = Scheduler.create request_param in - let memory = Memory_table.create 17 in + let memory = Memory_table.create ?random 17 in let input = Lwt_watcher.create_input () in {scheduler; disk; memory; input; global_input} diff --git a/src/lib_requester/requester.mli b/src/lib_requester/requester.mli index cd142e1463f966b99ce829f2f277499f3bc3137a..46203849145e8754bac6060f2d66073f695e03bf 100644 --- a/src/lib_requester/requester.mli +++ b/src/lib_requester/requester.mli @@ -158,9 +158,15 @@ module type FULL_REQUESTER = sig (** Returns the number of requests currently pending *) val pending_requests : t -> int - (** [create ?global_input r s] creates a requester. [r] is the - configuration parameter passed to [Request] functions. *) + (** [create ?random_table ?global_input r s] creates a requester. [r] is the + configuration parameter passed to [Request] functions. + + The value for [random_table] determines whether the underlying hashtable + randomises its hash (see {!Stdlib.Hashtbl.create} and specifically the + documentation of the [random] parameter). The default depends on + environment variables and {!Stdlib.Hashtbl.randomize} has been called. *) val create : + ?random_table:bool -> ?global_input:(key * value) Lwt_watcher.input -> request_param -> store -> @@ -184,12 +190,12 @@ module type DISK_TABLE = sig end module type MEMORY_TABLE = sig - (** subtypes Hashtbl.S *) + (** subtypes {!Hashtbl.SeededS} *) type 'a t type key - val create : int -> 'a t + val create : ?random:bool -> int -> 'a t val find : 'a t -> key -> 'a option diff --git a/src/lib_requester/test/test_requester.ml b/src/lib_requester/test/test_requester.ml index e8ceab9fdd537f026762cf6dcf1a33f463d5ea6f..397ced0668e5885550f42ec986e9ef0d12cf3a54 100644 --- a/src/lib_requester/test/test_requester.ml +++ b/src/lib_requester/test/test_requester.ml @@ -81,10 +81,10 @@ module Test_disk_table_hash = struct let read_opt st k = Lwt.return (find st k) end -module Test_memory_table = Hashtbl.Make (struct +module Test_memory_table = Hashtbl.MakeSeeded (struct type t = test_key - let hash = Hashtbl.hash + let hash = Hashtbl.seeded_hash let equal s1 s2 = s1 = s2 end) diff --git a/src/lib_shell/distributed_db.ml b/src/lib_shell/distributed_db.ml index 6962f8a6b185982eefdccae94b9fed30ae332975..d394539ba0d41885a2c3f39db8665dc026307023 100644 --- a/src/lib_shell/distributed_db.ml +++ b/src/lib_shell/distributed_db.ml @@ -125,8 +125,8 @@ let create disk p2p = let protocol_db = Distributed_db_requester.Raw_protocol.create global_request disk in - let active_chains = Chain_id.Table.create 17 in - let p2p_readers = P2p_peer.Table.create 17 in + let active_chains = Chain_id.Table.create ~random:true 17 in + let p2p_readers = P2p_peer.Table.create ~random:true 17 in let block_input = Lwt_watcher.create_input () in let operation_input = Lwt_watcher.create_input () in let db = @@ -197,7 +197,7 @@ let activate operations_db; callback = noop_callback; active_peers; - active_connections = P2p_peer.Table.create 53; + active_connections = P2p_peer.Table.create ~random:true 53; } in let sends = diff --git a/src/lib_shell/distributed_db_requester.ml b/src/lib_shell/distributed_db_requester.ml index 5f4f53cbcbd932152043aad11f52f6e0b6409c37..3fe1c11b30ef3f630e239f82c0f0e3a46c9268aa 100644 --- a/src/lib_shell/distributed_db_requester.ml +++ b/src/lib_shell/distributed_db_requester.ml @@ -126,8 +126,8 @@ end) scheduler_length; } - let create ?global_input request_param disk = - Table.create ?global_input request_param disk + let create ?random_table ?global_input request_param disk = + Table.create ?random_table ?global_input request_param disk let shutdown t = Requester_event.(emit shutting_down_requester) () @@ -199,10 +199,10 @@ module Raw_block_header = let precheck _ _ v = Some v end) -module Operations_table = Hashtbl.Make (struct +module Operations_table = Hashtbl.MakeSeeded (struct type t = Block_hash.t * int - let hash = Hashtbl.hash + let hash = Hashtbl.seeded_hash let equal (b1, i1) (b2, i2) = Block_hash.equal b1 b2 && i1 = i2 end)