From ac25fb93435b7a6a119b30bc769b9277afd7a4d1 Mon Sep 17 00:00:00 2001 From: Sylvain Ribstein Date: Tue, 4 Oct 2022 16:14:18 +0200 Subject: [PATCH 1/5] proto/skip_list: add find fct for cell at index --- .../lib_protocol/skip_list_repr.ml | 33 +++++-- .../lib_protocol/skip_list_repr.mli | 9 ++ .../test/unit/test_skip_list_repr.ml | 98 ++++++++++++++++++- 3 files changed, 132 insertions(+), 8 deletions(-) diff --git a/src/proto_alpha/lib_protocol/skip_list_repr.ml b/src/proto_alpha/lib_protocol/skip_list_repr.ml index b266f6ae1fec..7821e2034257 100644 --- a/src/proto_alpha/lib_protocol/skip_list_repr.ml +++ b/src/proto_alpha/lib_protocol/skip_list_repr.ml @@ -61,6 +61,12 @@ module type S = sig 'content -> ('content, 'ptr) cell + val find : + deref:('ptr -> ('content, 'ptr) cell option) -> + cell_ptr:'ptr -> + target_index:int -> + ('content, 'ptr) cell option + val back_path : deref:('ptr -> ('content, 'ptr) cell option) -> cell_ptr:'ptr -> @@ -285,21 +291,34 @@ end) : S = struct in binary_search 0 (length cell.back_pointers - 1) - let back_path ~deref ~cell_ptr ~target_index = - Option.bind (deref cell_ptr) @@ fun cell -> + let rev_back_path ~deref ~cell_ptr ~target_index = + let open Option_syntax in + let* cell = deref cell_ptr in let powers = list_powers cell in let rec aux path ptr = let path = ptr :: path in - Option.bind (deref ptr) @@ fun cell -> + let* cell = deref ptr in let index = cell.index in - if Compare.Int.(target_index = index) then Some (List.rev path) - else if Compare.Int.(target_index > index) then None + if Compare.Int.(target_index = index) then return path + else if Compare.Int.(target_index > index) then fail else - Option.bind (best_skip cell target_index powers) @@ fun best_idx -> - Option.bind (back_pointer cell best_idx) @@ fun ptr -> aux path ptr + let* best_idx = best_skip cell target_index powers in + let* ptr = back_pointer cell best_idx in + aux path ptr in aux [] cell_ptr + let find ~deref ~cell_ptr ~target_index = + let open Option_syntax in + let* rev_back_path = rev_back_path ~deref ~cell_ptr ~target_index in + let* cell_ptr = List.hd rev_back_path in + deref cell_ptr + + let back_path ~deref ~cell_ptr ~target_index = + let open Option_syntax in + let+ rev_back_path = rev_back_path ~deref ~cell_ptr ~target_index in + List.rev rev_back_path + let mem equal x l = let open FallbackArray in let n = length l in diff --git a/src/proto_alpha/lib_protocol/skip_list_repr.mli b/src/proto_alpha/lib_protocol/skip_list_repr.mli index 621f2f5f3a30..41270ed47435 100644 --- a/src/proto_alpha/lib_protocol/skip_list_repr.mli +++ b/src/proto_alpha/lib_protocol/skip_list_repr.mli @@ -96,6 +96,15 @@ module type S = sig 'content -> ('content, 'ptr) cell + (** [find ~deref ~cell_ptr ~target_index] returns [Some cell] where [cell] is + the cell at position [target_index]. This is done by dereferencing the last + pointer of the path returned by {!back_path}. *) + val find : + deref:('ptr -> ('content, 'ptr) cell option) -> + cell_ptr:'ptr -> + target_index:int -> + ('content, 'ptr) cell option + (** [back_path ~deref ~cell_ptr ~target_index] returns [Some path] where [path] is a sequence of back pointers to traverse to go from [cell_ptr] to the cell at position [target_index] in the diff --git a/src/proto_alpha/lib_protocol/test/unit/test_skip_list_repr.ml b/src/proto_alpha/lib_protocol/test/unit/test_skip_list_repr.ml index ba605fa96fa2..3db8327f5eff 100644 --- a/src/proto_alpha/lib_protocol/test/unit/test_skip_list_repr.ml +++ b/src/proto_alpha/lib_protocol/test/unit/test_skip_list_repr.ml @@ -96,6 +96,9 @@ struct let back_path list start stop = back_path ~deref:(deref list) ~cell_ptr:start ~target_index:stop + let find list start stop = + find ~deref:(deref list) ~cell_ptr:start ~target_index:stop + let search list start target_content = search ~deref:(deref list) @@ -112,6 +115,70 @@ struct let rec nlist basis n = if n = 0 then zero else succ (nlist basis (n - 1)) + let check_find i j = + let open Lwt_result_syntax in + let l = nlist basis i in + let*? () = + match find l i j with + | None -> error (err (Printf.sprintf "There must be a cell (%d)" i)) + | Some cell -> + error_unless + (index cell = j) + (err + (Printf.sprintf + "Found cell is not the correct one (found %d, expected %d)" + (index cell) + j)) + in + let*? path = + match back_path l i j with + | None -> + error (err (Printf.sprintf "There must be path from %d to %d" i j)) + | Some path -> ok path + in + let*? () = + match List.(hd (rev path)) with + | None -> + error + (err + (Printf.sprintf + " There can't be an empty path from %d to %d" + i + j)) + | Some stop_cell -> + error_unless + (j = stop_cell) + (err + (Printf.sprintf + "Found cell is not equal to stop cell of back path (%d to %d)" + i + j)) + in + return_unit + + let check_invalid_find i = + let open Lwt_result_syntax in + let l = nlist basis i in + let check_nothing_found i j = + match find l i j with + | None -> ok () + | Some _v -> + error + (err + (Printf.sprintf + "There should be no value found at %d from %d" + i + j)) + in + let*? () = check_nothing_found i (-1) in + let rec aux j = + if i <= j then return_unit + else + let*? () = check_nothing_found j i in + aux (j + 1) + in + aux 0 + let check_path i j back_path_fn = let l = nlist basis i in match back_path_fn l i j with @@ -264,6 +331,18 @@ let test_skip_list_nat_check_path (basis, i, j) = end) in M.check_path i j M.back_path +let test_skip_list_nat_check_find (basis, i, j) = + let module M = TestNat (struct + let basis = basis + end) in + M.check_find i j + +let test_skip_list_nat_check_invalid_find (basis, i) = + let module M = TestNat (struct + let basis = basis + end) in + M.check_invalid_find i + let test_skip_list_nat_check_invalid_path (basis, i) = let module M = TestNat (struct let basis = basis @@ -394,6 +473,23 @@ let tests = let* j = 0 -- i in return (basis, i, j)) test_skip_list_nat_check_path; + Tztest.tztest_qcheck2 + ~name:"Skip list: find cell with `find` and `check`" + ~count:10 + QCheck2.Gen.( + let* basis = frequency [(5, pure 2); (1, 2 -- 73)] in + let* i = 0 -- 100 in + let* j = 0 -- i in + return (basis, i, j)) + test_skip_list_nat_check_find; + Tztest.tztest_qcheck2 + ~name:"Skip list: `find` won't produce invalid value" + ~count:10 + QCheck2.Gen.( + let* basis = frequency [(5, pure 2); (1, 2 -- 73)] in + let* i = 0 -- 100 in + return (basis, i)) + test_skip_list_nat_check_invalid_find; Tztest.tztest_qcheck2 ~name:"Skip list: `back_path` won't produce invalid paths" ~count:10 @@ -425,7 +521,7 @@ let tests = test_skip_list_nat_check_invalid_path_with_search; (* We cheat here to avoid mixing non-pbt tests with pbt tests. *) Tztest.tztest_qcheck2 - ~name:"Skip list: `seearch` may not produce minimal path" + ~name:"Skip list: `search` may not produce minimal path" ~count:10 QCheck2.Gen.unit test_search_non_minimal_back_path; -- GitLab From 22dcdc12c3bbbe39842bdced78cb9c8173a51d69 Mon Sep 17 00:00:00 2001 From: Sylvain Ribstein Date: Tue, 4 Oct 2022 15:01:41 +0200 Subject: [PATCH 2/5] proto/scoru: add inbox merkelized payload hashes module --- src/proto_alpha/lib_protocol/TEZOS_PROTOCOL | 1 + src/proto_alpha/lib_protocol/alpha_context.ml | 2 + .../lib_protocol/alpha_context.mli | 53 ++++ src/proto_alpha/lib_protocol/dune | 7 + ...up_inbox_merkelized_payload_hashes_repr.ml | 248 ++++++++++++++++++ ...p_inbox_merkelized_payload_hashes_repr.mli | 125 +++++++++ .../sc_rollup_inbox_message_repr.ml | 31 +++ .../sc_rollup_inbox_message_repr.mli | 6 + 8 files changed, 473 insertions(+) create mode 100644 src/proto_alpha/lib_protocol/sc_rollup_inbox_merkelized_payload_hashes_repr.ml create mode 100644 src/proto_alpha/lib_protocol/sc_rollup_inbox_merkelized_payload_hashes_repr.mli diff --git a/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL b/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL index bb377c8e5961..e1655bc866ca 100644 --- a/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL +++ b/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL @@ -56,6 +56,7 @@ "Sc_rollup_metadata_repr", "Sc_rollup_tick_repr", "Sc_rollup_inbox_message_repr", + "Sc_rollup_inbox_merkelized_payload_hashes_repr", "Sc_rollup_outbox_message_repr", "Sc_rollup_PVM_sig", "Sc_rollup_arith", diff --git a/src/proto_alpha/lib_protocol/alpha_context.ml b/src/proto_alpha/lib_protocol/alpha_context.ml index 2a392d8c8a39..597aa79726c2 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.ml +++ b/src/proto_alpha/lib_protocol/alpha_context.ml @@ -61,6 +61,8 @@ module Sc_rollup = struct module ArithPVM = Sc_rollup_arith module Wasm_2_0_0PVM = Sc_rollup_wasm.V2_0_0 module Inbox_message = Sc_rollup_inbox_message_repr + module Inbox_merkelized_payload_hashes = + Sc_rollup_inbox_merkelized_payload_hashes_repr module Inbox = struct include Sc_rollup_inbox_repr diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index 7c3f9ebfb99b..dea775fb8688 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.mli +++ b/src/proto_alpha/lib_protocol/alpha_context.mli @@ -3180,6 +3180,59 @@ module Sc_rollup : sig val serialize : t -> serialized tzresult val deserialize : serialized -> t tzresult + + module Hash : S.HASH + + val hash_serialized_message : serialized -> Hash.t + end + + module Inbox_merkelized_payload_hashes : sig + module Hash : S.HASH + + type t + + val encoding : t Data_encoding.t + + val equal : t -> t -> bool + + val hash : t -> Hash.t + + val get_payload_hash : t -> Inbox_message.Hash.t + + val get_index : t -> int + + type merkelized_and_payload = { + merkelized : t; + payload : Inbox_message.serialized; + } + + module History : sig + include + Bounded_history_repr.S + with type key = Hash.t + and type value = merkelized_and_payload + + val no_history : t + end + + val genesis : + History.t -> Inbox_message.serialized -> (History.t * t) tzresult + + val add_payload : + History.t -> t -> Inbox_message.serialized -> (History.t * t) tzresult + + type proof + + val proof_encoding : proof Data_encoding.t + + val produce_proof : + History.t -> index:int -> t -> (merkelized_and_payload * proof) option + + val verify_proof : proof -> (t * t) tzresult + + module Internal_for_tests : sig + val find_predecessor_payload : History.t -> index:int -> t -> t option + end end type inbox_message = { diff --git a/src/proto_alpha/lib_protocol/dune b/src/proto_alpha/lib_protocol/dune index 3841752d300e..3d544f34579c 100644 --- a/src/proto_alpha/lib_protocol/dune +++ b/src/proto_alpha/lib_protocol/dune @@ -82,6 +82,7 @@ Sc_rollup_metadata_repr Sc_rollup_tick_repr Sc_rollup_inbox_message_repr + Sc_rollup_inbox_merkelized_payload_hashes_repr Sc_rollup_outbox_message_repr Sc_rollup_PVM_sig Sc_rollup_arith @@ -353,6 +354,8 @@ sc_rollup_metadata_repr.ml sc_rollup_metadata_repr.mli sc_rollup_tick_repr.ml sc_rollup_tick_repr.mli sc_rollup_inbox_message_repr.ml sc_rollup_inbox_message_repr.mli + sc_rollup_inbox_merkelized_payload_hashes_repr.ml + sc_rollup_inbox_merkelized_payload_hashes_repr.mli sc_rollup_outbox_message_repr.ml sc_rollup_outbox_message_repr.mli sc_rollup_PVM_sig.ml sc_rollup_arith.ml sc_rollup_arith.mli @@ -607,6 +610,8 @@ sc_rollup_metadata_repr.ml sc_rollup_metadata_repr.mli sc_rollup_tick_repr.ml sc_rollup_tick_repr.mli sc_rollup_inbox_message_repr.ml sc_rollup_inbox_message_repr.mli + sc_rollup_inbox_merkelized_payload_hashes_repr.ml + sc_rollup_inbox_merkelized_payload_hashes_repr.mli sc_rollup_outbox_message_repr.ml sc_rollup_outbox_message_repr.mli sc_rollup_PVM_sig.ml sc_rollup_arith.ml sc_rollup_arith.mli @@ -866,6 +871,8 @@ sc_rollup_metadata_repr.ml sc_rollup_metadata_repr.mli sc_rollup_tick_repr.ml sc_rollup_tick_repr.mli sc_rollup_inbox_message_repr.ml sc_rollup_inbox_message_repr.mli + sc_rollup_inbox_merkelized_payload_hashes_repr.ml + sc_rollup_inbox_merkelized_payload_hashes_repr.mli sc_rollup_outbox_message_repr.ml sc_rollup_outbox_message_repr.mli sc_rollup_PVM_sig.ml sc_rollup_arith.ml sc_rollup_arith.mli diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_merkelized_payload_hashes_repr.ml b/src/proto_alpha/lib_protocol/sc_rollup_inbox_merkelized_payload_hashes_repr.ml new file mode 100644 index 000000000000..44f2efee02df --- /dev/null +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_merkelized_payload_hashes_repr.ml @@ -0,0 +1,248 @@ +(*****************************************************************************) +(* *) +(* Open Source License *) +(* Copyright (c) 2022 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. *) +(* *) +(*****************************************************************************) + +type error += (* `Permanent *) Merkelized_payload_hashes_proof_error of string + +let () = + let open Data_encoding in + register_error_kind + `Permanent + ~id:"sc_rollup_inbox_message_repr.merkelized_payload_hashes_proof_error" + ~title: + "Internal error: error occurred during proof production or validation" + ~description:"A merkelized payload hashes proof error." + ~pp:(fun ppf e -> Format.fprintf ppf "Proof error: %s" e) + (obj1 (req "error" string)) + (function Merkelized_payload_hashes_proof_error e -> Some e | _ -> None) + (fun e -> Merkelized_payload_hashes_proof_error e) + +module Skip_list_parameters = struct + let basis = 2 +end + +module Skip_list = Skip_list_repr.Make (Skip_list_parameters) + +(* 32 *) +let hash_prefix = "\003\250\174\238\238" (* scib2(55) *) + +module Hash = struct + let prefix = "scib2" + + let encoded_size = 55 + + module H = + Blake2B.Make + (Base58) + (struct + let name = "merkelized_payload_hashes_hash" + + let title = + "The merkelized payload hashes' hash of the smart contract rollup \ + inbox" + + let b58check_prefix = hash_prefix + + (* defaults to 32 *) + let size = None + end) + + include H + + let () = Base58.check_encoded_prefix b58check_encoding prefix encoded_size +end + +type t = (Sc_rollup_inbox_message_repr.Hash.t, Hash.t) Skip_list.cell + +let equal = Skip_list.equal Hash.equal Sc_rollup_inbox_message_repr.Hash.equal + +let hash merkelized = + let payload_hash = Skip_list.content merkelized in + let back_pointers_hashes = Skip_list.back_pointers merkelized in + Sc_rollup_inbox_message_repr.Hash.to_bytes payload_hash + :: List.map Hash.to_bytes back_pointers_hashes + |> Hash.hash_bytes + +let pp = + Skip_list.pp ~pp_content:Sc_rollup_inbox_message_repr.Hash.pp ~pp_ptr:Hash.pp + +let encoding = + Skip_list.encoding Hash.encoding Sc_rollup_inbox_message_repr.Hash.encoding + +type merkelized_and_payload = { + merkelized : t; + payload : Sc_rollup_inbox_message_repr.serialized; +} + +let equal_merkelized_and_payload {merkelized; payload} mp2 = + equal merkelized mp2.merkelized + && String.equal (payload :> string) (mp2.payload :> string) + +let pp_merkelized_and_payload fmt {merkelized; payload} = + Format.fprintf + fmt + "@[merkelized:@,%a@,payload: %a@]" + pp + merkelized + Format.pp_print_string + (payload :> string) + +let merkelized_and_payload_encoding = + let open Data_encoding in + conv + (fun {merkelized; payload} -> (merkelized, (payload :> string))) + (fun (merkelized, payload) -> + { + merkelized; + payload = Sc_rollup_inbox_message_repr.unsafe_of_string payload; + }) + (merge_objs encoding (obj1 (req "payload" string))) + +module History = struct + include + Bounded_history_repr.Make + (struct + let name = "level_inbox_history" + end) + (Hash) + (struct + type nonrec t = merkelized_and_payload + + let pp = pp_merkelized_and_payload + + let equal = equal_merkelized_and_payload + + let encoding = merkelized_and_payload_encoding + end) + + let no_history = empty ~capacity:0L +end + +let remember history merkelized payload = + let prev_cell_ptr = hash merkelized in + History.remember prev_cell_ptr {merkelized; payload} history + +let genesis history payload = + let open Result_syntax in + let payload_hash = + Sc_rollup_inbox_message_repr.hash_serialized_message payload + in + let merkelized = Skip_list.genesis payload_hash in + let+ history = remember history merkelized payload in + (history, merkelized) + +let add_payload history prev_merkelized payload = + let open Result_syntax in + let prev_merkelized_ptr = hash prev_merkelized in + let merkelized = + Skip_list.next + ~prev_cell:prev_merkelized + ~prev_cell_ptr:prev_merkelized_ptr + (Sc_rollup_inbox_message_repr.hash_serialized_message payload) + in + let* history = remember history merkelized payload in + return (history, merkelized) + +let get_payload_hash = Skip_list.content + +let get_index = Skip_list.index + +type proof = t list + +let pp_proof = Format.pp_print_list pp + +let proof_encoding = Data_encoding.list encoding + +let produce_proof history ~index merkelized = + let open Option_syntax in + let deref ptr = + let* {merkelized; payload = _} = History.find ptr history in + return merkelized + in + let current_ptr = hash merkelized in + let lift_ptr = + let rec aux acc = function + | [] -> None + | [last_ptr] -> + let+ ({merkelized; _} as merkelized_and_payload) = + History.find last_ptr history + in + (merkelized_and_payload, List.rev (merkelized :: acc)) + | ptr :: rest -> + let* merkelized = deref ptr in + aux (merkelized :: acc) rest + in + aux [] + in + let* ptr_path = + Skip_list.back_path ~deref ~cell_ptr:current_ptr ~target_index:index + in + lift_ptr ptr_path + +let verify_proof inclusion_proof = + let open Result_syntax in + let* cell = + match inclusion_proof with + | cell :: _ -> ok cell + | [] -> + error (Merkelized_payload_hashes_proof_error "inclusion proof is empty") + in + let rec aux (hash_map, ptr_list) = function + | [] -> + error (Merkelized_payload_hashes_proof_error "inclusion proof is empty") + | [target] -> + let target_ptr = hash target in + let hash_map = Hash.Map.add target_ptr target hash_map in + let ptr_list = List.rev (target_ptr :: ptr_list) in + ok (hash_map, ptr_list, target, target_ptr) + | merkelized :: tail -> + let ptr = hash merkelized in + aux (Hash.Map.add ptr merkelized hash_map, ptr :: ptr_list) tail + in + let* hash_map, ptr_list, target, target_ptr = + aux (Hash.Map.empty, []) inclusion_proof + in + let deref ptr = Hash.Map.find ptr hash_map in + let cell_ptr = hash cell in + let* () = + error_unless + (Skip_list.valid_back_path + ~equal_ptr:Hash.equal + ~deref + ~cell_ptr + ~target_ptr + ptr_list) + (Merkelized_payload_hashes_proof_error "invalid inclusion proof") + in + return (target, cell) + +module Internal_for_tests = struct + let find_predecessor_payload payloads_history ~index payloads = + let open Option_syntax in + let deref ptr = + let* {merkelized; _} = History.find ptr payloads_history in + return merkelized + in + let cell_ptr = hash payloads in + Skip_list.find ~deref ~cell_ptr ~target_index:index +end diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_merkelized_payload_hashes_repr.mli b/src/proto_alpha/lib_protocol/sc_rollup_inbox_merkelized_payload_hashes_repr.mli new file mode 100644 index 000000000000..0872181e6c2e --- /dev/null +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_merkelized_payload_hashes_repr.mli @@ -0,0 +1,125 @@ +(*****************************************************************************) +(* *) +(* Open Source License *) +(* Copyright (c) 2022 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. *) +(* *) +(*****************************************************************************) + +type error += Merkelized_payload_hashes_proof_error of string + +module Hash : S.HASH + +(** A type representing the head of a merkelized list of + {!Sc_rollup_inbox_message_repr.serialized} message. It contains the hash of + the payload and the index on the list. *) +type t + +val encoding : t Data_encoding.t + +type merkelized_and_payload = { + merkelized : t; + payload : Sc_rollup_inbox_message_repr.serialized; +} + +(** A [History.t] is a lookup table of {!merkelized_and_payload}s. Payloads are + indexed by their hash {!Hash.t}. This history is needed in order to produce + {!proof}. + + A subtlety of this [history] type is that it is customizable depending on + how much of the inbox history you actually want to remember, using the + [capacity] parameter. In the L1 we use this with [capacity] set to zero, + which makes it immediately forget an old level as soon as we move to the + next. By contrast, the rollup node uses a history that is sufficiently large + to be able to take part in all potential refutation games occurring during + the challenge period. *) +module History : sig + include + Bounded_history_repr.S + with type key = Hash.t + and type value = merkelized_and_payload + + val no_history : t +end + +(** [hash merkelized] is the hash of [merkelized]. It is used as key to remember + a merkelized payload hash in an {!History.t}. *) +val hash : t -> Hash.t + +(** [remember history merkelized payload] remembers the [{merkelized; payload}] + in [history] with key [hash merkelized]. *) +val remember : + History.t -> + t -> + Sc_rollup_inbox_message_repr.serialized -> + History.t tzresult + +(** [genesis history payload] is the initial merkelized payload hashes with + index 0. It is remembered in [history] using [remember]. *) +val genesis : + History.t -> + Sc_rollup_inbox_message_repr.serialized -> + (History.t * t) tzresult + +(** [add_payload history merkelized payload] creates a new {!t} with [payload] + and [merkelized] as ancestor (i.e. [index = succ (get_index + merkelized)]). [merkelized] is remembered in [history] with [remember]. *) +val add_payload : + History.t -> + t -> + Sc_rollup_inbox_message_repr.serialized -> + (History.t * t) tzresult + +val equal : t -> t -> bool + +val pp : Format.formatter -> t -> unit + +(** [get_payload_hash merkelized] returns the + {!Sc_rollup_inbox_message_repr.serialized} payload's hash of + [merkelized]. *) +val get_payload_hash : t -> Sc_rollup_inbox_message_repr.Hash.t + +(** [get_index merkelized] returns the index of [merkelized]. *) +val get_index : t -> int + +(** Given two t [(a, b)] and a {!Sc_rollup_inbox_message_repr.serialized} +[payload], a [proof] guarantees that [payload] hash is equal to [a] and that + [a] is an ancestor of [b]; i.e. [get_index a < get_index b]. *) +type proof + +val pp_proof : Format.formatter -> proof -> unit + +val proof_encoding : proof Data_encoding.t + +(** [produce_proof history ~index into_] returns a {!merkelized_and_payload} + with index [index] and a proof that it is an ancestor of [into_]. Returns + [None] if no merkelized payload with [index] is found (either in the + [history] or [index] is not inferior to [get_index into_]). *) +val produce_proof : + History.t -> index:int -> t -> (merkelized_and_payload * proof) option + +(** [verify_proof proof] returns [(a, b)] where [proof] validates that [a] is an + ancestor of [b]. Fails when [proof] is not a valid inclusion proof. *) +val verify_proof : proof -> (t * t) tzresult + +module Internal_for_tests : sig + (** [find_predecessor_payload history ~index latest_merkelized] looks for the + {!t} with [index] that is an ancestor of [latest_merkelized]. *) + val find_predecessor_payload : History.t -> index:int -> t -> t option +end diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_message_repr.ml b/src/proto_alpha/lib_protocol/sc_rollup_inbox_message_repr.ml index 04310d03af61..62effb1292f0 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_message_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_message_repr.ml @@ -142,3 +142,34 @@ let deserialize s = let unsafe_of_string s = s let unsafe_to_string s = s + +(* 32 *) +let hash_prefix = "\003\250\174\239\012" (* scib3(55) *) + +module Hash = struct + let prefix = "scib3" + + let encoded_size = 55 + + module H = + Blake2B.Make + (Base58) + (struct + let name = "serialized_message_hash" + + let title = + "The hash of a serialized message of the smart contract rollup inbox." + + let b58check_prefix = hash_prefix + + (* defaults to 32 *) + let size = None + end) + + include H + + let () = Base58.check_encoded_prefix b58check_encoding prefix encoded_size +end + +let hash_serialized_message (payload : serialized) = + Hash.hash_string [(payload :> string)] diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_message_repr.mli b/src/proto_alpha/lib_protocol/sc_rollup_inbox_message_repr.mli index 4667640b6526..4c7b27344092 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_message_repr.mli +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_message_repr.mli @@ -81,3 +81,9 @@ val deserialize : serialized -> t tzresult val unsafe_of_string : string -> serialized val unsafe_to_string : serialized -> string + +module Hash : S.HASH + +(** [hash_serialized_message payload] is the hash of [payload]. It is used by + {!Sc_rollup_inbox_merkelized_payload_hashes_repr.t}. *) +val hash_serialized_message : serialized -> Hash.t -- GitLab From 3d5d6f0836fd1417fa598b094752c2de57cb31a9 Mon Sep 17 00:00:00 2001 From: Sylvain Ribstein Date: Tue, 4 Oct 2022 16:00:21 +0200 Subject: [PATCH 3/5] test/scoru: archive inbox_legacy test --- src/proto_alpha/lib_protocol/test/unit/main.ml | 2 +- src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_game.ml | 2 +- ...test_sc_rollup_inbox.ml => test_sc_rollup_inbox_legacy.ml} | 4 +++- 3 files changed, 5 insertions(+), 3 deletions(-) rename src/proto_alpha/lib_protocol/test/unit/{test_sc_rollup_inbox.ml => test_sc_rollup_inbox_legacy.ml} (99%) diff --git a/src/proto_alpha/lib_protocol/test/unit/main.ml b/src/proto_alpha/lib_protocol/test/unit/main.ml index f16000774d7c..a737e5ce6e6d 100644 --- a/src/proto_alpha/lib_protocol/test/unit/main.ml +++ b/src/proto_alpha/lib_protocol/test/unit/main.ml @@ -76,7 +76,7 @@ let () = Unit_test.spec "sc rollup wasm" Test_sc_rollup_wasm.tests; Unit_test.spec "sc rollup arith" Test_sc_rollup_arith.tests; Unit_test.spec "merkle list" Test_merkle_list.tests; - Unit_test.spec "sc rollup inbox" Test_sc_rollup_inbox.tests; + Unit_test.spec "sc rollup inbox" Test_sc_rollup_inbox_legacy.tests; Unit_test.spec "skip list" Test_skip_list_repr.tests; Unit_test.spec "sc rollup management protocol" diff --git a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_game.ml b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_game.ml index 9a0624a8a767..f61effa1d31f 100644 --- a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_game.ml +++ b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_game.ml @@ -269,7 +269,7 @@ module Arith_pvm = Sc_rollup_helpers.Arith_pvm let test_invalid_serialized_inbox_proof () = let open Lwt_result_syntax in let open Alpha_context in - let* ctxt = Test_sc_rollup_inbox.create_context () in + let* ctxt = Test_sc_rollup_inbox_legacy.create_context () in let rollup = Sc_rollup.Address.zero in let level = Raw_level.(succ root) in let*! inbox = Sc_rollup.Inbox.empty ctxt level in diff --git a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox.ml b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox_legacy.ml similarity index 99% rename from src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox.ml rename to src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox_legacy.ml index 28ff48198d1f..035c6dc3c65d 100644 --- a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox.ml +++ b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox_legacy.ml @@ -27,11 +27,13 @@ ------- Component: Protocol (smart contract rollup inbox) Invocation: dune exec src/proto_alpha/lib_protocol/test/unit/main.exe \ - -- test "^\[Unit\] sc rollup inbox$" + -- test "^\[Unit\] sc rollup inbox legacy$" Subject: These unit tests check the off-line inbox implementation for smart contract rollups *) +(* This test file is going to soon disappear. Each tests here are going to be + rewritten in [test_sc_rollup_inbox] in multiples MR. *) open Protocol open Sc_rollup_inbox_repr -- GitLab From 1063d6ad49d95303382cbef80fa36b93b869e6a5 Mon Sep 17 00:00:00 2001 From: Sylvain Ribstein Date: Tue, 4 Oct 2022 16:19:31 +0200 Subject: [PATCH 4/5] test/scoru: add new inbox test file --- .../lib_protocol/test/unit/main.ml | 2 +- .../test/unit/test_sc_rollup_inbox.ml | 35 +++++++++++++++++++ 2 files changed, 36 insertions(+), 1 deletion(-) create mode 100644 src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox.ml diff --git a/src/proto_alpha/lib_protocol/test/unit/main.ml b/src/proto_alpha/lib_protocol/test/unit/main.ml index a737e5ce6e6d..f16000774d7c 100644 --- a/src/proto_alpha/lib_protocol/test/unit/main.ml +++ b/src/proto_alpha/lib_protocol/test/unit/main.ml @@ -76,7 +76,7 @@ let () = Unit_test.spec "sc rollup wasm" Test_sc_rollup_wasm.tests; Unit_test.spec "sc rollup arith" Test_sc_rollup_arith.tests; Unit_test.spec "merkle list" Test_merkle_list.tests; - Unit_test.spec "sc rollup inbox" Test_sc_rollup_inbox_legacy.tests; + Unit_test.spec "sc rollup inbox" Test_sc_rollup_inbox.tests; Unit_test.spec "skip list" Test_skip_list_repr.tests; Unit_test.spec "sc rollup management protocol" diff --git a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox.ml b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox.ml new file mode 100644 index 000000000000..570c77d2e57c --- /dev/null +++ b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox.ml @@ -0,0 +1,35 @@ +(*****************************************************************************) +(* *) +(* Open Source License *) +(* Copyright (c) 2022 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. *) +(* *) +(*****************************************************************************) + +(** Testing + ------- + Component: Protocol (smart contract rollup inbox) + Invocation: dune exec src/proto_alpha/lib_protocol/test/unit/main.exe \ + -- test "^\[Unit\] sc rollup inbox$" + Subject: These unit tests check the off-line inbox implementation for + smart contract rollups +*) + +let tests = Test_sc_rollup_inbox_legacy.tests -- GitLab From 39ac403c659d643e1acb94183fdad23a7618fa85 Mon Sep 17 00:00:00 2001 From: Sylvain Ribstein Date: Tue, 4 Oct 2022 16:57:07 +0200 Subject: [PATCH 5/5] test/scoru: add tests for the merkelized payload hashes --- .../test/unit/test_sc_rollup_inbox.ml | 173 +++++++++++++++++- 1 file changed, 172 insertions(+), 1 deletion(-) diff --git a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox.ml b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox.ml index 570c77d2e57c..81113814d24d 100644 --- a/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox.ml +++ b/src/proto_alpha/lib_protocol/test/unit/test_sc_rollup_inbox.ml @@ -31,5 +31,176 @@ Subject: These unit tests check the off-line inbox implementation for smart contract rollups *) +open Protocol -let tests = Test_sc_rollup_inbox_legacy.tests +let lift k = Environment.wrap_tzresult k + +module Merkelized_payload_hashes = + Alpha_context.Sc_rollup.Inbox_merkelized_payload_hashes + +module Message = Alpha_context.Sc_rollup.Inbox_message + +let assert_equal_payload ~__LOC__ found (expected : Message.serialized) = + Assert.equal_string + ~loc:__LOC__ + (Message.unsafe_to_string expected) + (Message.unsafe_to_string found) + +let assert_equal_payload_hash ~__LOC__ found expected = + Assert.equal + ~loc:__LOC__ + Message.Hash.equal + "Protocol hashes aren't equal" + Message.Hash.pp + expected + found + +let assert_merkelized_payload ~__LOC__ ~payload_hash ~index found = + let open Lwt_result_syntax in + let found_payload_hash = Merkelized_payload_hashes.get_payload_hash found in + let found_index = Merkelized_payload_hashes.get_index found in + let* () = + assert_equal_payload_hash ~__LOC__ found_payload_hash payload_hash + in + Assert.equal_int ~loc:__LOC__ found_index index + +let assert_equal_merkelized_payload ~__LOC__ ~found ~expected = + let payload_hash = Merkelized_payload_hashes.get_payload_hash expected in + let index = Merkelized_payload_hashes.get_index expected in + assert_merkelized_payload ~__LOC__ ~payload_hash ~index found + +let gen_payload_size = QCheck2.Gen.(1 -- 10) + +let gen_payload = + let open QCheck2.Gen in + let+ payload = string_size gen_payload_size in + Message.unsafe_of_string payload + +let gen_payloads = + let open QCheck2.Gen in + list_size (2 -- 50) gen_payload + +let gen_index payloads = + let open QCheck2.Gen in + let max_index = List.length payloads - 1 in + let* index = 0 -- max_index in + return index + +let gen_payloads_and_index = + let open QCheck2.Gen in + let* payloads = gen_payloads in + let* index = gen_index payloads in + return (payloads, index) + +let gen_payloads_and_two_index = + let open QCheck2.Gen in + let* payloads = gen_payloads in + let* index = gen_index payloads in + let* index' = gen_index payloads in + return (payloads, index, index') + +let fill_merkelized_payload history payloads = + let open Lwt_result_syntax in + let* first, payloads = + match payloads with + | x :: xs -> return (x, xs) + | [] -> failwith "empty payloads" + in + let*? history, merkelized_payload = + lift @@ Merkelized_payload_hashes.genesis history first + in + Lwt.return @@ lift + @@ List.fold_left_e + (fun (history, payloads) payload -> + Merkelized_payload_hashes.add_payload history payloads payload) + (history, merkelized_payload) + payloads + +let construct_merkelized_payload payloads = + let history = Merkelized_payload_hashes.History.empty ~capacity:1000L in + fill_merkelized_payload history payloads + +let test_merkelized_payload_history payloads = + let open Lwt_result_syntax in + let nb_payloads = List.length payloads in + let* history, merkelized_payloads = construct_merkelized_payload payloads in + let* () = + Assert.equal_int + ~loc:__LOC__ + nb_payloads + (Merkelized_payload_hashes.get_index merkelized_payloads + 1) + in + List.iteri_es + (fun index (expected_payload : Message.serialized) -> + let expected_payload_hash = + Message.hash_serialized_message expected_payload + in + let found_merkelized_payload = + WithExceptions.Option.get ~loc:__LOC__ + @@ Merkelized_payload_hashes.Internal_for_tests.find_predecessor_payload + history + ~index + merkelized_payloads + in + let found_payload_hash = + Merkelized_payload_hashes.get_payload_hash found_merkelized_payload + in + assert_equal_payload_hash + ~__LOC__ + found_payload_hash + expected_payload_hash) + payloads + +let test_merkelized_payload_proof (payloads, index) = + let open Lwt_result_syntax in + let* history, merkelized_payload = construct_merkelized_payload payloads in + let ( Merkelized_payload_hashes. + {merkelized = target_merkelized_payload; payload = proof_payload}, + proof ) = + WithExceptions.Option.get ~loc:__LOC__ + @@ Merkelized_payload_hashes.produce_proof history ~index merkelized_payload + in + let payload : Message.serialized = + WithExceptions.Option.get ~loc:__LOC__ @@ List.nth payloads index + in + let payload_hash = Message.hash_serialized_message payload in + let* () = assert_equal_payload ~__LOC__ proof_payload payload in + let* () = + assert_merkelized_payload + ~__LOC__ + ~index + ~payload_hash + target_merkelized_payload + in + let*? proof_ancestor_merkelized, proof_current_merkelized = + lift @@ Merkelized_payload_hashes.verify_proof proof + in + let* () = + assert_equal_merkelized_payload + ~__LOC__ + ~found:proof_ancestor_merkelized + ~expected:target_merkelized_payload + in + let* () = + assert_equal_merkelized_payload + ~__LOC__ + ~found:proof_current_merkelized + ~expected:merkelized_payload + in + return_unit + +let merkelized_payload_tests = + [ + Tztest.tztest_qcheck2 + ~count:1000 + ~name:"Merkelized messages: Add messages then retrieve them from history." + gen_payloads + test_merkelized_payload_history; + Tztest.tztest_qcheck2 + ~count:1000 + ~name:"Merkelized messages: Produce proof and verify its validity." + gen_payloads_and_index + test_merkelized_payload_proof; + ] + +let tests = merkelized_payload_tests @ Test_sc_rollup_inbox_legacy.tests -- GitLab