From 12ac92e88f04c49aa2e59a75b31834e9ec03901c Mon Sep 17 00:00:00 2001 From: Rodi-Can Bozman Date: Wed, 19 Oct 2022 14:57:45 +0200 Subject: [PATCH 1/2] Proto/Dal: dal proofs serialization --- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 144 ++++++++++++------ .../lib_protocol/dal_slot_repr.mli | 10 +- .../lib_protocol/test/helpers/dal_helpers.ml | 2 +- 3 files changed, 110 insertions(+), 46 deletions(-) diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index a3c3dba0b2c2..fcd41ccf1fce 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -471,7 +471,7 @@ module History = struct *) - type proof = + type proof_repr = | Page_confirmed of { target_cell : history; (** [target_cell] is a cell whose content contains the slot to @@ -533,11 +533,11 @@ module History = struct (** The case where the slot's page doesn't exist or is not confirmed on L1. *) - let proof_encoding = + let proof_repr_encoding = let open Data_encoding in let case_page_confirmed = case - ~title:"confirmed dal page proof" + ~title:"confirmed dal page proof representation" (Tag 0) (obj5 (req "kind" (constant "confirmed")) @@ -553,7 +553,7 @@ module History = struct Page_confirmed {target_cell; inc_proof; page_data; page_proof}) and case_page_unconfirmed = case - ~title:"unconfirmed dal page proof" + ~title:"unconfirmed dal page proof representation" (Tag 1) (obj4 (req "kind" (constant "unconfirmed")) @@ -570,37 +570,87 @@ module History = struct union [case_page_confirmed; case_page_unconfirmed] + (** Proof's type is set to bytes and not a structural datatype because + when a proof appears in a tezos operation or in an rpc, a user can not + reasonably understand the proof, thus it eases the work of people decoding + the proof by only supporting bytes and not the whole structured proof. *) + + type proof = bytes + + (** DAL/FIXME: https://gitlab.com/tezos/tezos/-/issues/4084 + DAL proof's encoding should be bounded *) + let proof_encoding = Data_encoding.bytes + + type error += Dal_invalid_proof_serialization + + let () = + register_error_kind + `Permanent + ~id:"Dal_slot_repr.invalid_proof_serialization" + ~title:"Dal invalid proof serialization" + ~description:"Error occured during dal proof serialization" + Data_encoding.unit + (function Dal_invalid_proof_serialization -> Some () | _ -> None) + (fun () -> Dal_invalid_proof_serialization) + + let serialize_proof proof = + match Data_encoding.Binary.to_bytes_opt proof_repr_encoding proof with + | None -> error Dal_invalid_proof_serialization + | Some serialized_proof -> ok serialized_proof + + type error += Dal_invalid_proof_deserialization + + let () = + register_error_kind + `Permanent + ~id:"Dal_slot_repr.invalid_proof_deserialization" + ~title:"Dal invalid proof deserialization" + ~description:"Error occured during dal proof deserialization" + Data_encoding.unit + (function Dal_invalid_proof_deserialization -> Some () | _ -> None) + (fun () -> Dal_invalid_proof_deserialization) + + let deserialize_proof proof = + match Data_encoding.Binary.of_bytes_opt proof_repr_encoding proof with + | None -> error Dal_invalid_proof_deserialization + | Some deserialized_proof -> ok deserialized_proof + let pp_inclusion_proof = Format.pp_print_list pp_history let pp_history_opt = Format.pp_print_option pp_history - let pp_proof fmt p = - match p with - | Page_confirmed {target_cell; inc_proof; page_data; page_proof} -> - Format.fprintf - fmt - "Page_confirmed (target_cell=%a, data=%s,@ inc_proof:[size=%d |@ \ - path=%a]@ page_proof:%a)" - pp_history - target_cell - (Bytes.to_string page_data) - (List.length inc_proof) - pp_inclusion_proof - inc_proof - Page.pp_proof - page_proof - | Page_unconfirmed {prev_cell; next_cell_opt; next_inc_proof} -> - Format.fprintf - fmt - "Page_unconfirmed (prev_cell = %a | next_cell = %a | \ - prev_inc_proof:[size=%d@ | path=%a])" - pp_history - prev_cell - pp_history_opt - next_cell_opt - (List.length next_inc_proof) - pp_inclusion_proof - next_inc_proof + let pp_proof ~serialized fmt p = + if serialized then Format.pp_print_string fmt (Bytes.to_string p) + else + match deserialize_proof p with + | Error msg -> Error_monad.pp_trace fmt msg + | Ok proof -> ( + match proof with + | Page_confirmed {target_cell; inc_proof; page_data; page_proof} -> + Format.fprintf + fmt + "Page_confirmed (target_cell=%a, data=%s,@ \ + inc_proof:[size=%d |@ path=%a]@ page_proof:%a)" + pp_history + target_cell + (Bytes.to_string page_data) + (List.length inc_proof) + pp_inclusion_proof + inc_proof + Page.pp_proof + page_proof + | Page_unconfirmed {prev_cell; next_cell_opt; next_inc_proof} -> + Format.fprintf + fmt + "Page_unconfirmed (prev_cell = %a | next_cell = %a | \ + prev_inc_proof:[size=%d@ | path=%a])" + pp_history + prev_cell + pp_history_opt + next_cell_opt + (List.length next_inc_proof) + pp_inclusion_proof + next_inc_proof) type error += Dal_proof_error of string @@ -682,11 +732,12 @@ module History = struct (List.is_empty inc_proof) (dal_proof_error "The inclusion proof cannot be empty") in - (* All checks succeeded. We return a `Page_confirmed` proof. *) - let status = - Page_confirmed {inc_proof; target_cell; page_data; page_proof} + (* All checks succeeded. We return a serialized `Page_confirmed` proof. *) + let*? page_confirmed = + serialize_proof + @@ Page_confirmed {inc_proof; target_cell; page_data; page_proof} in - return (status, Some page_data) + return (page_confirmed, Some page_data) | None, Nearest {lower = prev_cell; upper = next_cell_opt} -> (* There is no previously confirmed slot in the skip list whose ID corresponds to the {published_level; slot_index} information @@ -711,8 +762,11 @@ module History = struct in return @@ List.rev rev_next_inc_proof in - return - (Page_unconfirmed {prev_cell; next_cell_opt; next_inc_proof}, None) + let*? page_unconfirmed = + serialize_proof + @@ Page_unconfirmed {prev_cell; next_cell_opt; next_inc_proof} + in + return (page_unconfirmed, None) | None, Found _ -> proof_error "The page ID's slot is confirmed, but no page content and proof \ @@ -744,8 +798,9 @@ module History = struct path) (dal_proof_error "verify_proof: invalid inclusion Dal proof.") - let verify_proof dal_params page_id snapshot proof = + let verify_proof dal_params page_id snapshot serialized_proof = let open Lwt_tzresult_syntax in + let*? proof = deserialize_proof serialized_proof in let Page.{slot_id; page_index = _} = page_id in match proof with | Page_confirmed {target_cell; page_data; page_proof; inc_proof} -> @@ -835,11 +890,14 @@ module History = struct module Internal_for_tests = struct let content = Skip_list.content - let proof_statement_is proof expected = - match (expected, proof) with - | `Confirmed, Page_confirmed _ | `Unconfirmed, Page_unconfirmed _ -> - true - | _ -> false + let proof_statement_is serialized_proof expected = + match deserialize_proof serialized_proof with + | Error _ -> false + | Ok proof -> ( + match (expected, proof) with + | `Confirmed, Page_confirmed _ | `Unconfirmed, Page_unconfirmed _ -> + true + | _ -> false) end end diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.mli b/src/proto_alpha/lib_protocol/dal_slot_repr.mli index 9166a8984876..f348d498dc8a 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.mli +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.mli @@ -267,8 +267,10 @@ module History : sig (** Encoding for {!proof}. *) val proof_encoding : proof Data_encoding.t - (** Pretty-printer for {!proof}. *) - val pp_proof : Format.formatter -> proof -> unit + (** Pretty-printer for {!proof}. If [serialized] is [false] it will print + the abstracted proof representation, otherwise if it's [true] it will + print the serialized version of the proof (i.e. a sequence of bytes). *) + val pp_proof : serialized:bool -> Format.formatter -> proof -> unit (** [produce_proof dal_parameters page_id page_info slots_hist hist_cache] produces a proof that either: @@ -315,6 +317,10 @@ module History : sig module Internal_for_tests : sig val content : t -> Header.t + (** [proof_statement_is serialized_proof expected] will return [true] if + the deserialized proof and the [expected] proof shape match and [false] + otherwise. + Note that it will also return [false] if deserialization fails. *) val proof_statement_is : proof -> [`Confirmed | `Unconfirmed] -> bool end end diff --git a/src/proto_alpha/lib_protocol/test/helpers/dal_helpers.ml b/src/proto_alpha/lib_protocol/test/helpers/dal_helpers.ml index 221181ef6b0d..5075435e46cf 100644 --- a/src/proto_alpha/lib_protocol/test/helpers/dal_helpers.ml +++ b/src/proto_alpha/lib_protocol/test/helpers/dal_helpers.ml @@ -202,7 +202,7 @@ struct failwith "Expected to have a %s page proof. Got %a@." (proof_status_to_string proof_status) - Hist.pp_proof + (Hist.pp_proof ~serialized:false) proof in assert_content_is -- GitLab From bbb11efed259d1fec645e8e4440597b44b4a20f7 Mon Sep 17 00:00:00 2001 From: Rodi-Can Bozman Date: Mon, 24 Oct 2022 10:14:50 +0200 Subject: [PATCH 2/2] Proto/Dal: separate produce/verify proof representation from its serialized version --- src/proto_alpha/lib_protocol/dal_slot_repr.ml | 53 +++++++++++-------- 1 file changed, 31 insertions(+), 22 deletions(-) diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml index fcd41ccf1fce..bafb194f8bcc 100644 --- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml @@ -440,8 +440,8 @@ module History = struct case where the slot's header is published, but the endorsers didn't confirm the availability of its data. - To produce a proof for a page (see function {!produce_proof} below), we - assume given: + To produce a proof representation for a page (see function {!produce_proof_repr} + below), we assume given: - [page_id], identifies the page; @@ -695,7 +695,7 @@ module History = struct dal_params.page_size (Bytes.length page.content) - let produce_proof dal_params page_id ~page_info slots_hist hist_cache = + let produce_proof_repr dal_params page_id ~page_info slots_hist hist_cache = let open Lwt_tzresult_syntax in let Page.{slot_id; page_index = _} = page_id in let deref ptr = History_cache.find ptr hist_cache in @@ -732,12 +732,10 @@ module History = struct (List.is_empty inc_proof) (dal_proof_error "The inclusion proof cannot be empty") in - (* All checks succeeded. We return a serialized `Page_confirmed` proof. *) - let*? page_confirmed = - serialize_proof - @@ Page_confirmed {inc_proof; target_cell; page_data; page_proof} - in - return (page_confirmed, Some page_data) + (* All checks succeeded. We return a `Page_confirmed` proof. *) + return + ( Page_confirmed {inc_proof; target_cell; page_data; page_proof}, + Some page_data ) | None, Nearest {lower = prev_cell; upper = next_cell_opt} -> (* There is no previously confirmed slot in the skip list whose ID corresponds to the {published_level; slot_index} information @@ -762,11 +760,8 @@ module History = struct in return @@ List.rev rev_next_inc_proof in - let*? page_unconfirmed = - serialize_proof - @@ Page_unconfirmed {prev_cell; next_cell_opt; next_inc_proof} - in - return (page_unconfirmed, None) + return + (Page_unconfirmed {prev_cell; next_cell_opt; next_inc_proof}, None) | None, Found _ -> proof_error "The page ID's slot is confirmed, but no page content and proof \ @@ -776,6 +771,14 @@ module History = struct "The page ID's slot is not confirmed, but page content and proof \ are provided." + let produce_proof dal_params page_id ~page_info slots_hist hist_cache = + let open Lwt_tzresult_syntax in + let* proof_repr, page_data = + produce_proof_repr dal_params page_id ~page_info slots_hist hist_cache + in + let*? serialized_proof = serialize_proof proof_repr in + return (serialized_proof, page_data) + (* Given a starting cell [snapshot] and a (final) [target], this function checks that the provided [inc_proof] encodes a minimal path from [snapshot] to [target]. *) @@ -796,11 +799,10 @@ module History = struct ~cell_ptr:snapshot_ptr ~target_ptr path) - (dal_proof_error "verify_proof: invalid inclusion Dal proof.") + (dal_proof_error "verify_proof_repr: invalid inclusion Dal proof.") - let verify_proof dal_params page_id snapshot serialized_proof = + let verify_proof_repr dal_params page_id snapshot proof = let open Lwt_tzresult_syntax in - let*? proof = deserialize_proof serialized_proof in let Page.{slot_id; page_index = _} = page_id in match proof with | Page_confirmed {target_cell; page_data; page_proof; inc_proof} -> @@ -811,8 +813,8 @@ module History = struct fail_when Compare.Int.(Header.compare_slot_id id Header.zero.id = 0) (dal_proof_error - "verify_proof: cannot construct a confirmation page proof \ - with 'zero' as target slot.") + "verify_proof_repr: cannot construct a confirmation page \ + proof with 'zero' as target slot.") in let* () = verify_inclusion_proof inc_proof ~src:snapshot ~dest:target_cell @@ -837,7 +839,8 @@ module History = struct let* () = fail_unless (List.is_empty next_inc_proof) - (dal_proof_error "verify_proof: invalid next_inc_proof") + (dal_proof_error + "verify_proof_repr: invalid next_inc_proof") in (* In case the inclusion proof has no elements, we check that: - the prev_cell slot's id is smaller than the unconfirmed slot's ID @@ -850,7 +853,7 @@ module History = struct fail_unless ((Skip_list.content prev_cell).id < slot_id && equal_history snapshot prev_cell) - (dal_proof_error "verify_proof: invalid next_inc_proof") + (dal_proof_error "verify_proof_repr: invalid next_inc_proof") | Some next_cell -> (* In case the inclusion proof has at least one element, we check that: @@ -878,7 +881,8 @@ module History = struct Pointer_hash.equal prev_ptr (hash_skip_list_cell prev_cell)) - (dal_proof_error "verify_proof: invalid next_inc_proof") + (dal_proof_error + "verify_proof_repr: invalid next_inc_proof") in verify_inclusion_proof next_inc_proof @@ -887,6 +891,11 @@ module History = struct in return_none + let verify_proof dal_params page_id snapshot serialized_proof = + let open Lwt_tzresult_syntax in + let*? proof_repr = deserialize_proof serialized_proof in + verify_proof_repr dal_params page_id snapshot proof_repr + module Internal_for_tests = struct let content = Skip_list.content -- GitLab