From 517cd42fb0de63c7c7f27f558db5adc128298559 Mon Sep 17 00:00:00 2001 From: Valentin Chaboche Date: Wed, 24 Aug 2022 09:40:19 +0200 Subject: [PATCH 1/5] Scoru: take snapshot at the beginning of a block level --- src/proto_alpha/lib_protocol/alpha_context.mli | 2 +- .../lib_protocol/sc_rollup_inbox_repr.ml | 18 ++++++++++++++---- .../lib_protocol/sc_rollup_inbox_repr.mli | 11 +++++++---- .../sc_rollup_refutation_storage.ml | 3 ++- .../test/pbt/test_sc_rollup_encoding.ml | 2 +- .../test/unit/test_sc_rollup_inbox.ml | 9 ++++++--- 6 files changed, 31 insertions(+), 14 deletions(-) diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli index f0905280e2c0..62b463dad7d0 100644 --- a/src/proto_alpha/lib_protocol/alpha_context.mli +++ b/src/proto_alpha/lib_protocol/alpha_context.mli @@ -3072,7 +3072,7 @@ module Sc_rollup : sig tree option -> (History.t * history_proof) tzresult Lwt.t - val take_snapshot : t -> history_proof + val take_snapshot : current_level:Raw_level.t -> t -> history_proof type inclusion_proof diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml index e0504dbd4d46..2a4dfe664391 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.ml @@ -445,7 +445,7 @@ module type Merkelized_operations = sig tree option -> (History.t * history_proof) tzresult Lwt.t - val take_snapshot : t -> history_proof + val take_snapshot : current_level:Raw_level_repr.t -> t -> history_proof type inclusion_proof @@ -602,10 +602,20 @@ struct previous levels of the inbox. *) let no_history = History.empty ~capacity:0L - let take_snapshot inbox = + let take_snapshot ~current_level inbox = let prev_cell = inbox.old_levels_messages in - let prev_cell_ptr = hash_skip_list_cell prev_cell in - Skip_list.next ~prev_cell ~prev_cell_ptr (current_level_hash inbox) + if Raw_level_repr.(inbox.level < current_level) then + (* If the level of the inbox is lower than the current level, there + is no new messages in the inbox for the current level. It is then safe + to take a snapshot of the actual inbox. *) + let prev_cell_ptr = hash_skip_list_cell prev_cell in + Skip_list.next ~prev_cell ~prev_cell_ptr (current_level_hash inbox) + else + (* If there is a level tree for the [current_level] in the inbox, we need + to ignore this new level as it is not finished yet (regarding the + block's completion). We take the inbox's current predecessor instead. + *) + prev_cell let key_of_level level = let level_bytes = diff --git a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli index 0a78a3e48f10..3965a6d6a24f 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli +++ b/src/proto_alpha/lib_protocol/sc_rollup_inbox_repr.mli @@ -311,10 +311,13 @@ module type Merkelized_operations = sig the beginning of a refutation game to create the snapshot against which proofs in that game must be valid. - This will however produce a [history_proof] with exactly the same - hash as the one produced by [form_history_proof], run on a node - with a complete [inbox_context]. *) - val take_snapshot : t -> history_proof + One important note: + It takes the snapshot of the inbox for the [current_level]. The snapshot + points to the inbox at the *beginning* of the current block level. + This prevents to create a mid-level snapshot for a refutation game + if new messages are added before and/or after in the same block. + *) + val take_snapshot : current_level:Raw_level_repr.t -> t -> history_proof (** Given a inbox [A] at some level [L] and another inbox [B] at some level [L' >= L], an [inclusion_proof] guarantees that [A] is diff --git a/src/proto_alpha/lib_protocol/sc_rollup_refutation_storage.ml b/src/proto_alpha/lib_protocol/sc_rollup_refutation_storage.ml index 6a849251bea7..9931865f1ea2 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_refutation_storage.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_refutation_storage.ml @@ -257,9 +257,10 @@ let start_game ctxt rollup ~player:refuter ~opponent:defender = Constants_storage.sc_rollup_number_of_sections_in_dissection ctxt in + let current_level = (Raw_context.current_level ctxt).level in let game = Sc_rollup_game_repr.initial - (Sc_rollup_inbox_repr.take_snapshot inbox) + (Sc_rollup_inbox_repr.take_snapshot ~current_level inbox) ~pvm_name:(Sc_rollups.Kind.name_of kind) ~parent:parent_info ~child:child_info diff --git a/src/proto_alpha/lib_protocol/test/pbt/test_sc_rollup_encoding.ml b/src/proto_alpha/lib_protocol/test/pbt/test_sc_rollup_encoding.ml index 882e843e55ea..5fd359984fdd 100644 --- a/src/proto_alpha/lib_protocol/test/pbt/test_sc_rollup_encoding.ml +++ b/src/proto_alpha/lib_protocol/test/pbt/test_sc_rollup_encoding.ml @@ -112,7 +112,7 @@ let gen_inbox rollup level = let gen_inbox_history_proof rollup inbox_level = let open Gen in let* inbox = gen_inbox rollup inbox_level in - return (Sc_rollup_inbox_repr.take_snapshot inbox) + return (Sc_rollup_inbox_repr.take_snapshot ~current_level:inbox_level inbox) let gen_pvm_name = Gen.string_printable 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 4ef6b4b7e091..3bf754fc66df 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 @@ -374,7 +374,8 @@ let test_inbox_proof_production (list_of_payloads, l, n) = for verification. *) setup_inbox_with_messages list_of_payloads @@ fun _ctxt _current_level_tree _history inbox _inboxes -> - let snapshot = take_snapshot inbox in + let current_level = Raw_level_repr.succ (inbox_level inbox) in + let snapshot = take_snapshot ~current_level inbox in let proof = node_proof_to_protocol_proof proof in let*! verification = verify_proof (l, n) snapshot proof in match verification with @@ -404,7 +405,8 @@ let test_inbox_proof_verification (list_of_payloads, l, n) = (* Use the incorrect inbox *) match List.hd inboxes with | Some inbox -> ( - let snapshot = take_snapshot inbox in + let current_level = Raw_level_repr.succ (inbox_level inbox) in + let snapshot = take_snapshot ~current_level inbox in let proof = node_proof_to_protocol_proof proof in let*! verification = verify_proof (l, n) snapshot proof in match verification with @@ -432,7 +434,8 @@ let test_empty_inbox_proof (level, n) = create_context () >>=? fun ctxt -> let*! inbox = empty ctxt rollup level in - let snapshot = take_snapshot inbox in + let current_level = Raw_level_repr.succ (inbox_level inbox) in + let snapshot = take_snapshot ~current_level inbox in let proof = node_proof_to_protocol_proof proof in let*! verification = verify_proof (Raw_level_repr.root, n) snapshot proof -- GitLab From c56001809a450f1c0d47d767c34d14c8728b0c61 Mon Sep 17 00:00:00 2001 From: Valentin Chaboche Date: Wed, 24 Aug 2022 09:40:56 +0200 Subject: [PATCH 2/5] Scoru,Test: test the snapshot of an inbox --- .../test/unit/test_sc_rollup_inbox.ml | 135 ++++++++++++++++++ 1 file changed, 135 insertions(+) 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 3bf754fc66df..7b172ea934d8 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 @@ -642,6 +642,61 @@ let test_inclusion_proofs_depending_on_history_capacity (I.verify_inclusion_proof ip1 hp hp && I.verify_inclusion_proof ip2 hp hp) (err "Inclusion proofs are expected to be valid.") +(** In this test, we make sure that the snapshot of an empty inbox is not + impacted by the [current_level] parameter. *) +let test_empty_inbox_snapshot_taking (origination_level, snapshot_level) = + let open Lwt_result_syntax in + let origination_level = + Raw_level_repr.of_int32_exn @@ Int32.of_int origination_level + in + let snapshot_level = + Raw_level_repr.of_int32_exn @@ Int32.of_int snapshot_level + in + let* ctxt = create_context () in + let*! inbox = empty ctxt rollup origination_level in + (* We take a snapshot of the whole inbox. *) + let current_level = Raw_level_repr.succ origination_level in + let expected_snapshot = take_snapshot ~current_level inbox in + (* We take a snapshot at a random level. *) + let actual_snapshot = take_snapshot ~current_level:snapshot_level inbox in + (* They're expected to be the same. *) + fail_unless + (equal_history_proof expected_snapshot actual_snapshot) + (err + "Snapshot at origination level of an empty inbox should be equal to \ + snapshots at any level.") + +(** In this test, we make sure that the snapshot of an inbox is taken + at the beginning of a block level. *) +let test_inbox_snapshot_taking (list_of_payloads, payloads) = + let open Lwt_result_syntax in + setup_inbox_with_messages list_of_payloads + @@ fun ctxt current_level_tree history inbox inboxes -> + let inbox_level = inbox_level inbox in + (* If we take a snapshot of [inbox_level + 1], we take a snapshot of the + whole inbox. *) + let current_level = Raw_level_repr.succ inbox_level in + let expected_snapshot = take_snapshot ~current_level inbox in + (* Now, if we add messages to the inbox at [current_level], the inbox's + snapshot for this level should not changed. *) + let* _level_tree, _history, inbox, _inboxes = + populate_inboxes + ctxt + current_level + history + inbox + inboxes + (Some current_level_tree) + [payloads] + in + let new_snapshot = take_snapshot ~current_level inbox in + fail_unless + (equal_history_proof expected_snapshot new_snapshot) + (err + "Adding messages in an inbox for a level should not modify the snapshot \ + when the current level is equal to the level where the messages are \ + added.") + (** This test checks that inboxes of the same levels that are supposed to contain the same messages are equal. It also check the level trees obtained from the last calls to add_messages are equal. *) @@ -668,6 +723,59 @@ let test_for_successive_add_messages_with_different_histories_capacities && Option.equal I.Internal_for_tests.eq_tree level_tree1 level_tree2) (err "Trees of (supposedly) equal inboxes should be equal.") +let test_inclusion_proof_of_unarchived_message () = + let open Lwt_result_syntax in + let level_zero = first_level in + let message_counter_zero = Z.zero in + let message = "c4c4" in + let payloads = [[message]] in + + let check_expected_input (input : Sc_rollup_PVM_sig.inbox_message option) = + match input with + | Some {payload; _} -> + let message' = + Sc_rollup_inbox_message_repr.deserialize payload + |> WithExceptions.Result.get_ok ~loc:__LOC__ + in + assert (message' = External message) + | None -> assert false + in + + let* proof = + setup_node_inbox_with_messages payloads + @@ fun ctxt level_tree history inbox _inboxes -> + let* history, history_proof = + Node.form_history_proof ctxt history inbox (Some level_tree) + >|= Environment.wrap_tzresult + in + let* proof, input = + Node.produce_proof + ctxt + history + history_proof + (level_zero, message_counter_zero) + >|= Environment.wrap_tzresult + in + let () = check_expected_input input in + return proof + in + + let* snapshot = + setup_inbox_with_messages payloads + @@ fun _ctxt _level_tree _history inbox _inboxes -> + (* We set the inbox level in the future. *) + let level = Raw_level_repr.of_int32_exn 42l in + return (take_snapshot ~current_level:level inbox) + in + + let proof = node_proof_to_protocol_proof proof in + let* input = + verify_proof (level_zero, message_counter_zero) snapshot proof + >|= Environment.wrap_tzresult + in + let () = check_expected_input input in + return_unit + let tests = let msg_size = QCheck2.Gen.(0 -- 100) in let bounded_string = QCheck2.Gen.string_size msg_size in @@ -771,4 +879,31 @@ let tests = capacities" gen_history_params test_for_successive_add_messages_with_different_histories_capacities; + Tztest.tztest_qcheck2 + ~count:10 + ~name: + "Take snapshot of an empty inbox for any current level gives the same \ + result" + (let open QCheck2.Gen in + let* origination_level = small_nat in + let* offset = small_nat in + let snapshot_level = origination_level + offset + 1 in + return (origination_level, snapshot_level)) + test_empty_inbox_snapshot_taking; + Tztest.tztest_qcheck2 + ~count:10 + ~name: + "Take snapshot is not impacted by messages added during the current \ + level" + (let open QCheck2.Gen in + let* list_of_payloads = + list_size (1 -- 50) (list_size (1 -- 10) bounded_string) + in + let* payloads = list_size (1 -- 10) bounded_string in + return (list_of_payloads, payloads)) + test_inbox_snapshot_taking; + Tztest.tztest + "Test that a unarchived message belongs to the snapshot" + `Quick + test_inclusion_proof_of_unarchived_message; ] -- GitLab From 3f04fdf4769d201c222121dd41af5786add5b339 Mon Sep 17 00:00:00 2001 From: Valentin Chaboche Date: Wed, 24 Aug 2022 10:25:53 +0200 Subject: [PATCH 3/5] Scoru,Test: adapt proof production/verification tests to cover snapshot --- .../test/unit/test_sc_rollup_inbox.ml | 33 +++++++++++++++---- 1 file changed, 26 insertions(+), 7 deletions(-) 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 7b172ea934d8..8a2949582cbd 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 @@ -357,7 +357,7 @@ let next_input ps l n = in aux (idx + 1) -let test_inbox_proof_production (list_of_payloads, l, n) = +let test_inbox_proof_production (list_of_payloads, additional_payloads, l, n) = (* We begin with a Node inbox so we can produce a proof. *) let exp_input = next_input list_of_payloads l n in setup_node_inbox_with_messages list_of_payloads @@ -372,9 +372,17 @@ let test_inbox_proof_production (list_of_payloads, l, n) = | Ok (proof, input) -> ( (* We now switch to a protocol inbox built from the same messages for verification. *) - setup_inbox_with_messages list_of_payloads + setup_inbox_with_messages (list_of_payloads @ [additional_payloads]) @@ fun _ctxt _current_level_tree _history inbox _inboxes -> - let current_level = Raw_level_repr.succ (inbox_level inbox) in + (* If there are [additional_payloads], we will take the snapshot + of the additional level, which should ignore the additional + payloads. Otherwise, we take a snapshot of the whole inbox. *) + let current_level = + let curr = inbox_level inbox in + match additional_payloads with + | [] -> Raw_level_repr.succ curr + | _ -> curr + in let snapshot = take_snapshot ~current_level inbox in let proof = node_proof_to_protocol_proof proof in let*! verification = verify_proof (l, n) snapshot proof in @@ -386,7 +394,8 @@ let test_inbox_proof_production (list_of_payloads, l, n) = | Error _ -> fail [err "Proof verification failed"]) | Error _ -> fail [err "Proof production failed"] -let test_inbox_proof_verification (list_of_payloads, l, n) = +let test_inbox_proof_verification (list_of_payloads, additional_payloads, l, n) + = (* We begin with a Node inbox so we can produce a proof. *) setup_node_inbox_with_messages list_of_payloads @@ fun ctxt current_level_tree history inbox _inboxes -> @@ -400,12 +409,20 @@ let test_inbox_proof_verification (list_of_payloads, l, n) = | Ok (proof, _input) -> ( (* We now switch to a protocol inbox built from the same messages for verification. *) - setup_inbox_with_messages list_of_payloads + setup_inbox_with_messages (list_of_payloads @ [additional_payloads]) @@ fun _ctxt _current_level_tree _history _inbox inboxes -> (* Use the incorrect inbox *) match List.hd inboxes with | Some inbox -> ( - let current_level = Raw_level_repr.succ (inbox_level inbox) in + (* If there are [additional_payloads], we will take the snapshot + of the additional level, which should ignore the additional + payloads. Otherwise, we take a snapshot of the whole inbox. *) + let current_level = + let curr = inbox_level inbox in + match additional_payloads with + | [] -> Raw_level_repr.succ curr + | _ -> curr + in let snapshot = take_snapshot ~current_level inbox in let proof = node_proof_to_protocol_proof proof in let*! verification = verify_proof (l, n) snapshot proof in @@ -810,7 +827,9 @@ let tests = let* after = list_size small (list_size small bounded_string) in let payloads = List.append before (at :: after) in let* n = 0 -- (List.length at + 3) in - return (payloads, level_of_int (succ level), Z.of_int n)) + let* additional_payloads = small_list bounded_string in + return + (payloads, additional_payloads, level_of_int (succ level), Z.of_int n)) in let gen_history_params = QCheck2.Gen.( -- GitLab From f3a3a17e1245f396493a0ed5563852b5ded6f984 Mon Sep 17 00:00:00 2001 From: Valentin Chaboche Date: Mon, 29 Aug 2022 11:35:34 +0200 Subject: [PATCH 4/5] Scoru,Test: cover new [take_snapshot] with refutation game tests --- .../test/pbt/test_refutation_game.ml | 37 +++++++++++++++++-- .../test/unit/test_sc_rollup_game.ml | 6 ++- 2 files changed, 38 insertions(+), 5 deletions(-) diff --git a/src/proto_alpha/lib_protocol/test/pbt/test_refutation_game.ml b/src/proto_alpha/lib_protocol/test/pbt/test_refutation_game.ml index 730721d8c80f..5f0549c67523 100644 --- a/src/proto_alpha/lib_protocol/test/pbt/test_refutation_game.ml +++ b/src/proto_alpha/lib_protocol/test/pbt/test_refutation_game.ml @@ -1490,6 +1490,7 @@ let gen_game ?nonempty_inputs ~p1_strategy ~p2_strategy () = in let* p1_start = bool in let commitment_level = origination_level + commitment_period in + let* additional_payloads = small_list (string_size (1 -- 15)) in return ( block, rollup, @@ -1499,7 +1500,8 @@ let gen_game ?nonempty_inputs ~p1_strategy ~p2_strategy () = p2_client, contract3, p1_start, - levels_and_inputs ) + levels_and_inputs, + additional_payloads ) (** [prepare_game block lcc originated_level p1_client p2_client inputs_and_levels] prepares a context where [p1_client] and [p2_client] @@ -1542,7 +1544,8 @@ let test_game ?nonempty_inputs ~p1_strategy ~p2_strategy () = p2_client, _contract3, p1_start, - levels_and_inputs ) -> + levels_and_inputs, + _additional_payloads ) -> let level = WithExceptions.Result.get_ok ~loc:__LOC__ @@ Context.get_level (B block) in @@ -1585,7 +1588,8 @@ let test_game ?nonempty_inputs ~p1_strategy ~p2_strategy () = p2_client, contract3, p1_start, - levels_and_inputs ) -> + levels_and_inputs, + additional_payloads ) -> let open Lwt_result_syntax in (* Otherwise, there is no conflict. *) QCheck2.assume @@ -1619,7 +1623,32 @@ let test_game ?nonempty_inputs ~p1_strategy ~p2_strategy () = defender.player.pkh None in - let* block = Block.bake ~operation:operation_start_game block in + let* block = + match additional_payloads with + | [] -> Block.bake ~operation:operation_start_game block + | payloads -> + (* Add messages before starting the game. *) + let* operation_add_messages1 = + Op.sc_rollup_add_messages + (B block) + defender.player.contract + rollup + payloads + in + (* Start the game in between adding messages so the latest protocol + inbox is no longer equal to the player's view on inbox. *) + let* operation_add_messages2 = + Op.sc_rollup_add_messages (B block) contract3 rollup payloads + in + Block.bake + ~operations: + [ + operation_add_messages1; + operation_start_game; + operation_add_messages2; + ] + block + in let* game_result = play_until_game_result ~rollup 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 6e828799992d..033c0b553952 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 @@ -317,7 +317,11 @@ let test_invalid_serialized_inbox_proof () = let*! inbox = Sc_rollup.Inbox.empty ctxt Sc_rollup.Address.zero Raw_level.(succ root) in - let snapshot = Sc_rollup.Inbox.take_snapshot inbox in + let snapshot = + Sc_rollup.Inbox.take_snapshot + ~current_level:(Raw_level.of_int32_exn 42l) + inbox + in let ctxt = Tezos_context_memory.make_empty_context () in let*! state = Arith_pvm.initial_state ctxt in -- GitLab From ab3b4f43c687c925fd07e8d952ad8d47a60de239 Mon Sep 17 00:00:00 2001 From: Valentin Chaboche Date: Tue, 6 Sep 2022 09:44:22 +0200 Subject: [PATCH 5/5] Scoru,Proto: fix typo --- src/proto_alpha/bin_sc_rollup_node/refutation_game.ml | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/src/proto_alpha/bin_sc_rollup_node/refutation_game.ml b/src/proto_alpha/bin_sc_rollup_node/refutation_game.ml index 7468353aa1b2..97c3e5926145 100644 --- a/src/proto_alpha/bin_sc_rollup_node/refutation_game.ml +++ b/src/proto_alpha/bin_sc_rollup_node/refutation_game.ml @@ -74,7 +74,7 @@ module Make (Interpreter : Interpreter.S) : | Alice, Bob -> Their_turn | Bob, Alice -> Their_turn - (** [inject_next_move node_ctxt source ~refuation ~opponent] submits an L1 + (** [inject_next_move node_ctxt source ~refutation ~opponent] submits an L1 operation (signed by [source]) to issue the next move in the refutation game. *) let inject_next_move (node_ctxt : Node_context.t) source ~refutation ~opponent -- GitLab