From 4a4f063024e79ec162c72c4959bea674b924a1e3 Mon Sep 17 00:00:00 2001
From: "iguerNL@Functori" <iguer@functori.com>
Date: Thu, 17 Oct 2024 17:02:39 +0200
Subject: [PATCH 1/5] Dal/Proto: Functions that tell if a slot is attested by
 the protocol also return attestation ratio

---
 src/proto_alpha/lib_protocol/alpha_context.ml |  1 +
 .../lib_protocol/alpha_context.mli            |  8 ++++++-
 .../lib_protocol/dal_attestation_repr.ml      | 17 +++++++++++++--
 .../lib_protocol/dal_attestation_repr.mli     | 21 +++++++++++++++++--
 .../lib_protocol/dal_slot_storage.ml          |  4 +++-
 .../lib_protocol/dal_slot_storage.mli         |  4 +++-
 src/proto_alpha/lib_protocol/raw_context.mli  | 15 +++++++++----
 7 files changed, 59 insertions(+), 11 deletions(-)

diff --git a/src/proto_alpha/lib_protocol/alpha_context.ml b/src/proto_alpha/lib_protocol/alpha_context.ml
index 7e7944632c3f..f0731d911004 100644
--- a/src/proto_alpha/lib_protocol/alpha_context.ml
+++ b/src/proto_alpha/lib_protocol/alpha_context.ml
@@ -142,6 +142,7 @@ module Dal = struct
   end
 
   module Attestation = struct
+    include Dal_attestation_repr.Accountability
     include Dal_attestation_repr
     include Raw_context.Dal
   end
diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli
index 8532ba0fc656..9754dcb3f5e3 100644
--- a/src/proto_alpha/lib_protocol/alpha_context.mli
+++ b/src/proto_alpha/lib_protocol/alpha_context.mli
@@ -2776,6 +2776,12 @@ module Dal : sig
 
     type shard_index = int
 
+    type attestation_status = {
+      total_shards : int;
+      attested_shards : int;
+      is_proto_attested : bool;
+    }
+
     module Shard_map : Map.S with type key = shard_index
 
     val encoding : t Data_encoding.t
@@ -2876,7 +2882,7 @@ module Dal : sig
       context -> number_of_slots:int -> (context * Attestation.t) tzresult Lwt.t
 
     val compute_attested_slot_headers :
-      is_slot_attested:(Header.t -> bool) ->
+      is_slot_attested:(Header.t -> Attestation.attestation_status) ->
       Header.t list ->
       Header.t list * Attestation.t
   end
diff --git a/src/proto_alpha/lib_protocol/dal_attestation_repr.ml b/src/proto_alpha/lib_protocol/dal_attestation_repr.ml
index 920e04d7da5c..ae2d974204d6 100644
--- a/src/proto_alpha/lib_protocol/dal_attestation_repr.ml
+++ b/src/proto_alpha/lib_protocol/dal_attestation_repr.ml
@@ -95,6 +95,12 @@ module Accountability = struct
 
   type t = {number_of_attested_shards : int SlotMap.t; number_of_slots : int}
 
+  type attestation_status = {
+    total_shards : int;
+    attested_shards : int;
+    is_proto_attested : bool;
+  }
+
   let init ~number_of_slots =
     {number_of_attested_shards = SlotMap.empty; number_of_slots}
 
@@ -136,6 +142,13 @@ module Accountability = struct
       | None -> 0
       | Some v -> v
     in
-    Compare.Int.(
-      number_of_attested_shards >= threshold * number_of_shards / 100)
+    let is_proto_attested =
+      Compare.Int.(
+        number_of_attested_shards >= threshold * number_of_shards / 100)
+    in
+    {
+      is_proto_attested;
+      attested_shards = number_of_attested_shards;
+      total_shards = number_of_shards;
+    }
 end
diff --git a/src/proto_alpha/lib_protocol/dal_attestation_repr.mli b/src/proto_alpha/lib_protocol/dal_attestation_repr.mli
index a9edc93ac34c..b92370870223 100644
--- a/src/proto_alpha/lib_protocol/dal_attestation_repr.mli
+++ b/src/proto_alpha/lib_protocol/dal_attestation_repr.mli
@@ -92,6 +92,15 @@ module Accountability : sig
   (** The data-structure used to record the shards attestations. *)
   type t
 
+  type attestation_status = {
+    total_shards : int;  (** The total number of (attestable) shards. *)
+    attested_shards : int;
+        (** The total number of shards that have been attested. *)
+    is_proto_attested : bool;
+        (** The boolean is set to [true] IFF the [attestation_ratio] is below or
+            equal to the threshold defined by the protocol. *)
+  }
+
   (** DAL/FIXME https://gitlab.com/tezos/tezos/-/issues/3145
 
      Consider using the [Bounded] module. In particular, change the
@@ -113,7 +122,15 @@ module Accountability : sig
       [threshold] with respect to the total number of shards specified by
       [number_of_shards]. Returns [false] otherwise or if the [index] is out of
       the interval [0; number_of_slots - 1] where [number_of_slots] is the value
-      provided to the [init] function. *)
+      provided to the [init] function.
+
+      Whether the slot is attested by the protocol or not, the function also
+      returns the ratio of attested shards w.r.t. total shards, as a rational
+      number. *)
   val is_slot_attested :
-    t -> threshold:int -> number_of_shards:int -> Dal_slot_index_repr.t -> bool
+    t ->
+    threshold:int ->
+    number_of_shards:int ->
+    Dal_slot_index_repr.t ->
+    attestation_status
 end
diff --git a/src/proto_alpha/lib_protocol/dal_slot_storage.ml b/src/proto_alpha/lib_protocol/dal_slot_storage.ml
index 6245a97db954..a3894e5c4267 100644
--- a/src/proto_alpha/lib_protocol/dal_slot_storage.ml
+++ b/src/proto_alpha/lib_protocol/dal_slot_storage.ml
@@ -36,7 +36,9 @@ let finalize_current_slot_headers ctxt =
 let compute_attested_slot_headers ~is_slot_attested seen_slot_headers =
   let open Dal_slot_repr in
   let fold_attested_slots (rev_attested_slot_headers, attestation) slot =
-    if is_slot_attested slot then
+    let attestation_status = is_slot_attested slot in
+    if attestation_status.Dal_attestation_repr.Accountability.is_proto_attested
+    then
       ( slot :: rev_attested_slot_headers,
         Dal_attestation_repr.commit attestation slot.Header.id.index )
     else (rev_attested_slot_headers, attestation)
diff --git a/src/proto_alpha/lib_protocol/dal_slot_storage.mli b/src/proto_alpha/lib_protocol/dal_slot_storage.mli
index 792b69997e05..b5206574252b 100644
--- a/src/proto_alpha/lib_protocol/dal_slot_storage.mli
+++ b/src/proto_alpha/lib_protocol/dal_slot_storage.mli
@@ -87,6 +87,8 @@ val get_slot_headers_history :
     filter the given [published_slot_headers] and return the list of attested
     slot headers and the corresponding bitset. *)
 val compute_attested_slot_headers :
-  is_slot_attested:(Dal_slot_repr.Header.t -> bool) ->
+  is_slot_attested:
+    (Dal_slot_repr.Header.t ->
+    Dal_attestation_repr.Accountability.attestation_status) ->
   Dal_slot_repr.Header.t list ->
   Dal_slot_repr.Header.t list * Dal_attestation_repr.t
diff --git a/src/proto_alpha/lib_protocol/raw_context.mli b/src/proto_alpha/lib_protocol/raw_context.mli
index 9fa26519d4dd..d9de5caa5341 100644
--- a/src/proto_alpha/lib_protocol/raw_context.mli
+++ b/src/proto_alpha/lib_protocol/raw_context.mli
@@ -454,8 +454,15 @@ module Dal : sig
   val candidates : t -> Dal_slot_repr.Header.t list
 
   (** [is_slot_index_attested ctxt slot_index] returns [true] if the
-     [slot_index] is declared available by the protocol. [false]
-     otherwise. If the [index] is out of the interval
-     [0;number_of_slots - 1], returns [false]. *)
-  val is_slot_index_attested : t -> Dal_slot_index_repr.t -> bool
+      [slot_index] is declared available by the protocol. [false] otherwise. If
+      the [index] is out of the interval [0;number_of_slots - 1], returns
+      [false].
+
+      Whether the slot is attested by the protocol or not, the function also
+      returns the ratio of attested shards w.r.t. total shards, as a rational
+      number. *)
+  val is_slot_index_attested :
+    t ->
+    Dal_slot_index_repr.t ->
+    Dal_attestation_repr.Accountability.attestation_status
 end
-- 
GitLab


From 948a39e8ba6f4b4db8230d91cb51d42fb1ca753b Mon Sep 17 00:00:00 2001
From: "iguerNL@Functori" <iguer@functori.com>
Date: Fri, 18 Oct 2024 11:25:43 +0200
Subject: [PATCH 2/5] DAL/Proto: rework the interface of
 compute_attested_slot_headers

The function becomes compute_slot_headers_statuses, and it's not used/
accessed from alpha_context anymore, since indexing is done in a simpler
manner since MR https://gitlab.com/tezos/tezos/-/merge_requests/15320
---
 .../lib_protocol/alpha_context.mli            |  5 ---
 .../lib_protocol/dal_slot_storage.ml          | 33 ++++++++++++-------
 .../lib_protocol/dal_slot_storage.mli         | 10 ------
 3 files changed, 21 insertions(+), 27 deletions(-)

diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli
index 9754dcb3f5e3..a77d4f2df48a 100644
--- a/src/proto_alpha/lib_protocol/alpha_context.mli
+++ b/src/proto_alpha/lib_protocol/alpha_context.mli
@@ -2880,11 +2880,6 @@ module Dal : sig
 
     val finalize_pending_slot_headers :
       context -> number_of_slots:int -> (context * Attestation.t) tzresult Lwt.t
-
-    val compute_attested_slot_headers :
-      is_slot_attested:(Header.t -> Attestation.attestation_status) ->
-      Header.t list ->
-      Header.t list * Attestation.t
   end
 
   module Operations : sig
diff --git a/src/proto_alpha/lib_protocol/dal_slot_storage.ml b/src/proto_alpha/lib_protocol/dal_slot_storage.ml
index a3894e5c4267..18a1ed234e0d 100644
--- a/src/proto_alpha/lib_protocol/dal_slot_storage.ml
+++ b/src/proto_alpha/lib_protocol/dal_slot_storage.ml
@@ -33,15 +33,20 @@ let finalize_current_slot_headers ctxt =
     (Raw_context.current_level ctxt).level
     (Raw_context.Dal.candidates ctxt)
 
-let compute_attested_slot_headers ~is_slot_attested seen_slot_headers =
+let compute_slot_headers_statuses ~is_slot_attested seen_slot_headers =
   let open Dal_slot_repr in
   let fold_attested_slots (rev_attested_slot_headers, attestation) slot =
     let attestation_status = is_slot_attested slot in
-    if attestation_status.Dal_attestation_repr.Accountability.is_proto_attested
-    then
-      ( slot :: rev_attested_slot_headers,
-        Dal_attestation_repr.commit attestation slot.Header.id.index )
-    else (rev_attested_slot_headers, attestation)
+    let rev_attested_slot_headers =
+      (slot, attestation_status) :: rev_attested_slot_headers
+    in
+    let attestation =
+      if
+        attestation_status.Dal_attestation_repr.Accountability.is_proto_attested
+      then Dal_attestation_repr.commit attestation slot.Header.id.index
+      else attestation
+    in
+    (rev_attested_slot_headers, attestation)
   in
   let rev_attested_slot_headers, bitset =
     List.fold_left
@@ -58,7 +63,7 @@ let get_slot_headers_history ctxt =
   | None -> Dal_slot_repr.History.genesis
   | Some slots_history -> slots_history
 
-let update_skip_list ctxt ~confirmed_slot_headers ~level_attested
+let update_skip_list ctxt ~slot_headers_statuses ~level_attested
     ~number_of_slots =
   let open Lwt_result_syntax in
   let open Dal_slot_repr.History in
@@ -70,6 +75,10 @@ let update_skip_list ctxt ~confirmed_slot_headers ~level_attested
     *)
     (* We expect to put exactly [number_of_slots] cells in the cache. *)
     let cache = History_cache.empty ~capacity:(Int64.of_int number_of_slots) in
+    let confirmed_slot_headers =
+      (* WIP/Temporary: will be extended in next commits. *)
+      List.map fst slot_headers_statuses
+    in
     add_confirmed_slot_headers
       ~number_of_slots
       slots_history
@@ -93,24 +102,24 @@ let finalize_pending_slot_headers ctxt ~number_of_slots =
   | Some level_attested ->
       let* seen_slots = find_slot_headers ctxt level_attested in
       let*! ctxt = Storage.Dal.Slot.Headers.remove ctxt level_attested in
-      let* ctxt, attestation, confirmed_slot_headers =
+      let* ctxt, attestation, slot_headers_statuses =
         match seen_slots with
         | None -> return (ctxt, Dal_attestation_repr.empty, [])
         | Some seen_slots ->
-            let attested_slot_headers, attestation =
+            let slot_headers_statuses, attestation =
               let is_slot_attested slot =
                 Raw_context.Dal.is_slot_index_attested
                   ctxt
                   slot.Dal_slot_repr.Header.id.index
               in
-              compute_attested_slot_headers ~is_slot_attested seen_slots
+              compute_slot_headers_statuses ~is_slot_attested seen_slots
             in
-            return (ctxt, attestation, attested_slot_headers)
+            return (ctxt, attestation, slot_headers_statuses)
       in
       let* ctxt =
         update_skip_list
           ctxt
-          ~confirmed_slot_headers
+          ~slot_headers_statuses
           ~level_attested
           ~number_of_slots
       in
diff --git a/src/proto_alpha/lib_protocol/dal_slot_storage.mli b/src/proto_alpha/lib_protocol/dal_slot_storage.mli
index b5206574252b..d93cb76463eb 100644
--- a/src/proto_alpha/lib_protocol/dal_slot_storage.mli
+++ b/src/proto_alpha/lib_protocol/dal_slot_storage.mli
@@ -82,13 +82,3 @@ val finalize_pending_slot_headers :
    in [ctxt], or Slots_history.genesis if no value is stored yet. *)
 val get_slot_headers_history :
   Raw_context.t -> Dal_slot_repr.History.t tzresult Lwt.t
-
-(** [compute_attested_slot_headers ~is_slot_attested published_slot_headers]
-    filter the given [published_slot_headers] and return the list of attested
-    slot headers and the corresponding bitset. *)
-val compute_attested_slot_headers :
-  is_slot_attested:
-    (Dal_slot_repr.Header.t ->
-    Dal_attestation_repr.Accountability.attestation_status) ->
-  Dal_slot_repr.Header.t list ->
-  Dal_slot_repr.Header.t list * Dal_attestation_repr.t
-- 
GitLab


From f3d6f49d56e5606f960299d054781210be91d9b1 Mon Sep 17 00:00:00 2001
From: "iguerNL@Functori" <iguer@functori.com>
Date: Fri, 18 Oct 2024 11:34:32 +0200
Subject: [PATCH 3/5] Dal/Proto: rename function(s) add_confirmed_slot_headers
 to update_skip_list

The semantics of the function(s) will change in the next commits as we
will not only provide the slots that are attested by the protocol, but
all published ones
---
 src/proto_alpha/lib_protocol/alpha_context.mli      |  4 ++--
 src/proto_alpha/lib_protocol/dal_slot_repr.ml       | 13 ++++---------
 src/proto_alpha/lib_protocol/dal_slot_repr.mli      | 12 ++++++------
 src/proto_alpha/lib_protocol/dal_slot_storage.ml    |  2 +-
 .../lib_protocol/test/pbt/test_dal_slot_proof.ml    |  2 +-
 .../test/pbt/test_sc_rollup_encoding.ml             |  6 +-----
 .../lib_protocol/test/unit/test_dal_slot_proof.ml   |  4 ++--
 .../test/test_octez_conversions.ml                  |  4 ++--
 8 files changed, 19 insertions(+), 28 deletions(-)

diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli
index a77d4f2df48a..bb89203812e3 100644
--- a/src/proto_alpha/lib_protocol/alpha_context.mli
+++ b/src/proto_alpha/lib_protocol/alpha_context.mli
@@ -2923,14 +2923,14 @@ module Dal : sig
     module History_cache :
       Bounded_history_repr.S with type key = hash and type value = t
 
-    val add_confirmed_slot_headers_no_cache :
+    val update_skip_list_no_cache :
       t ->
       Raw_level.t ->
       number_of_slots:int ->
       Slot.Header.t list ->
       t tzresult
 
-    val add_confirmed_slot_headers :
+    val update_skip_list :
       t ->
       History_cache.t ->
       Raw_level.t ->
diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml
index c1d216aee885..c2aa20dd31ed 100644
--- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml
+++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml
@@ -584,8 +584,8 @@ module History = struct
        insert exactly [number_of_slots] cells in the skip list per level. This
        will simplify the shape of proofs and help bounding the history cache
        required for their generation. *)
-    let add_confirmed_slot_headers (t : t) cache published_level
-        ~number_of_slots attested_slot_headers =
+    let update_skip_list (t : t) cache published_level ~number_of_slots
+        attested_slot_headers =
       let open Result_syntax in
       let* () =
         List.iter_e
@@ -604,17 +604,12 @@ module History = struct
       in
       List.fold_left_e (add_cell ~number_of_slots) (t, cache) slot_headers
 
-    let add_confirmed_slot_headers_no_cache =
+    let update_skip_list_no_cache =
       let empty_cache = History_cache.empty ~capacity:0L in
       fun t published_level ~number_of_slots slots ->
         let open Result_syntax in
         let+ cell, (_ : History_cache.t) =
-          add_confirmed_slot_headers
-            t
-            empty_cache
-            published_level
-            ~number_of_slots
-            slots
+          update_skip_list t empty_cache published_level ~number_of_slots slots
         in
         cell
 
diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.mli b/src/proto_alpha/lib_protocol/dal_slot_repr.mli
index 40c8f94c91f0..6992dacfd7de 100644
--- a/src/proto_alpha/lib_protocol/dal_slot_repr.mli
+++ b/src/proto_alpha/lib_protocol/dal_slot_repr.mli
@@ -229,12 +229,12 @@ module History : sig
       {!Raw_level_repr.root} as published level and no attested slots. Since Dal
       is not necessarily activated in the genesis block (e.g. this will be the case
       on mainnet), the skip list is reset at the first call to
-      {!add_confirmed_slot_headers} to enforce the invariant that there are no gaps
+      {!update_skip_list} to enforce the invariant that there are no gaps
       in the levels of the cells of the skip list.
 
       So, a skip list is initialized with this genesis cell. It's then replaced
       with a growing (non-dummy) skip list as soon as a call to
-      {!add_confirmed_slot_headers} with a level bigger than
+      {!update_skip_list} with a level bigger than
       {!Raw_level_repr.root} is performed. This allows to activate Dal at any
       level and having a contiguous skip list (w.r.t. L1 levels). This
       representation allows to produce simpler proofs with a bounded history
@@ -254,7 +254,7 @@ module History : sig
   module History_cache :
     Bounded_history_repr.S with type key = hash and type value = t
 
-  (** [add_confirmed_slots hist cache published_level ~number_of_slots
+  (** [update_skip_list hist cache published_level ~number_of_slots
       slot_headers] updates the given structure [hist] with the list of
       [slot_headers]. The given [cache] is also updated to add successive values
       of [cell] to it.
@@ -270,7 +270,7 @@ module History : sig
 
       - [slot_headers] is sorted in increasing order w.r.t. slots indices.
   *)
-  val add_confirmed_slot_headers :
+  val update_skip_list :
     t ->
     History_cache.t ->
     Raw_level_repr.t ->
@@ -278,9 +278,9 @@ module History : sig
     Header.t list ->
     (t * History_cache.t) tzresult
 
-  (** Similiar to {!add_confirmed_slot_headers}, but no cache is provided or
+  (** Similiar to {!update_skip_list}, but no cache is provided or
       updated. *)
-  val add_confirmed_slot_headers_no_cache :
+  val update_skip_list_no_cache :
     t -> Raw_level_repr.t -> number_of_slots:int -> Header.t list -> t tzresult
 
   (** [equal a b] returns true iff a is equal to b. *)
diff --git a/src/proto_alpha/lib_protocol/dal_slot_storage.ml b/src/proto_alpha/lib_protocol/dal_slot_storage.ml
index 18a1ed234e0d..2a5e3ac15d85 100644
--- a/src/proto_alpha/lib_protocol/dal_slot_storage.ml
+++ b/src/proto_alpha/lib_protocol/dal_slot_storage.ml
@@ -79,7 +79,7 @@ let update_skip_list ctxt ~slot_headers_statuses ~level_attested
       (* WIP/Temporary: will be extended in next commits. *)
       List.map fst slot_headers_statuses
     in
-    add_confirmed_slot_headers
+    update_skip_list
       ~number_of_slots
       slots_history
       cache
diff --git a/src/proto_alpha/lib_protocol/test/pbt/test_dal_slot_proof.ml b/src/proto_alpha/lib_protocol/test/pbt/test_dal_slot_proof.ml
index b2d174b5c1eb..e5cdb86749d8 100644
--- a/src/proto_alpha/lib_protocol/test/pbt/test_dal_slot_proof.ml
+++ b/src/proto_alpha/lib_protocol/test/pbt/test_dal_slot_proof.ml
@@ -105,7 +105,7 @@ struct
           slots_headers
       in
       let*?@ cell, cache =
-        Dal_slot_repr.History.add_confirmed_slot_headers
+        Dal_slot_repr.History.update_skip_list
           ~number_of_slots:Parameters.dal_parameters.number_of_slots
           cell
           cache
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 befd6e8f0515..cfa9f949af57 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
@@ -191,11 +191,7 @@ let gen_dal_slots_history () =
             slot_headers
         in
         History.(
-          add_confirmed_slot_headers_no_cache
-            ~number_of_slots
-            history
-            level
-            slot_headers)
+          update_skip_list_no_cache ~number_of_slots history level slot_headers)
         |> function
         | Ok history -> loop history llist
         | Error e ->
diff --git a/src/proto_alpha/lib_protocol/test/unit/test_dal_slot_proof.ml b/src/proto_alpha/lib_protocol/test/unit/test_dal_slot_proof.ml
index cd08a067d255..212c332d9b45 100644
--- a/src/proto_alpha/lib_protocol/test/unit/test_dal_slot_proof.ml
+++ b/src/proto_alpha/lib_protocol/test/unit/test_dal_slot_proof.ml
@@ -63,7 +63,7 @@ struct
     let index = mk_slot_index id in
     let* _data, _poly, slot = mk_slot ~level ~index () in
     let@ result =
-      Hist.add_confirmed_slot_headers_no_cache
+      Hist.update_skip_list_no_cache
         skip_list
         level
         [slot]
@@ -188,7 +188,7 @@ struct
     let open Lwt_result_wrap_syntax in
     let* _slot_data, polynomial, slot = mk_slot ~level ?index () in
     let*?@ skip_list, cache =
-      Hist.add_confirmed_slot_headers
+      Hist.update_skip_list
         ~number_of_slots:Parameters.dal_parameters.number_of_slots
         genesis_history
         genesis_history_cache
diff --git a/src/proto_alpha/lib_sc_rollup_node/test/test_octez_conversions.ml b/src/proto_alpha/lib_sc_rollup_node/test/test_octez_conversions.ml
index d8f5db8cac62..8751a9c286a0 100644
--- a/src/proto_alpha/lib_sc_rollup_node/test/test_octez_conversions.ml
+++ b/src/proto_alpha/lib_sc_rollup_node/test/test_octez_conversions.ml
@@ -258,7 +258,7 @@ let gen_slot_history =
   in
   List.fold_left_e
     (fun hist (published_level, attested_slots) ->
-      Dal.Slots_history.add_confirmed_slot_headers_no_cache
+      Dal.Slots_history.update_skip_list_no_cache
         ~number_of_slots
         hist
         published_level
@@ -286,7 +286,7 @@ let gen_slot_history_cache =
   in
   List.fold_left_e
     (fun (hist, cache) (published_level, attested_slots) ->
-      Dal.Slots_history.add_confirmed_slot_headers
+      Dal.Slots_history.update_skip_list
         ~number_of_slots
         hist
         cache
-- 
GitLab


From 33c756c3c7b7561bae4e038320c91f443795c998 Mon Sep 17 00:00:00 2001
From: "iguerNL@Functori" <iguer@functori.com>
Date: Fri, 18 Oct 2024 15:36:46 +0200
Subject: [PATCH 4/5] Proto/Dal: propagate published slot headers statuses to
 Dal_slot_repr

In a follow-up MR, we'll use the statuses info alongside the extension
of the DAL skip list cells' content to prepare info needed for Adaptive
DAL
---
 src/proto_alpha/lib_protocol/TEZOS_PROTOCOL   |  2 +-
 .../lib_protocol/alpha_context.mli            |  4 +-
 src/proto_alpha/lib_protocol/dal_slot_repr.ml | 21 ++++++----
 .../lib_protocol/dal_slot_repr.mli            | 18 +++++----
 .../lib_protocol/dal_slot_storage.ml          |  6 +--
 src/proto_alpha/lib_protocol/dune             |  8 ++--
 .../test/pbt/test_dal_slot_proof.ml           | 29 +++++++++-----
 .../test/pbt/test_sc_rollup_encoding.ml       | 28 ++++++++++----
 .../test/unit/test_dal_slot_proof.ml          |  9 +++--
 .../test/test_octez_conversions.ml            | 38 +++++++++++++------
 10 files changed, 107 insertions(+), 56 deletions(-)

diff --git a/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL b/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL
index 5cb8ffb7458c..3fb6ea422a9d 100644
--- a/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL
+++ b/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL
@@ -57,8 +57,8 @@
         "Entrypoint_repr",
 
         "Dal_slot_index_repr",
-        "Dal_slot_repr",
         "Dal_attestation_repr",
+        "Dal_slot_repr",
 
         "Michelson_v1_gas_costs_generated",
         "Michelson_v1_gas_costs",
diff --git a/src/proto_alpha/lib_protocol/alpha_context.mli b/src/proto_alpha/lib_protocol/alpha_context.mli
index bb89203812e3..eb0311381e2d 100644
--- a/src/proto_alpha/lib_protocol/alpha_context.mli
+++ b/src/proto_alpha/lib_protocol/alpha_context.mli
@@ -2927,7 +2927,7 @@ module Dal : sig
       t ->
       Raw_level.t ->
       number_of_slots:int ->
-      Slot.Header.t list ->
+      (Slot.Header.t * Attestation.attestation_status) list ->
       t tzresult
 
     val update_skip_list :
@@ -2935,7 +2935,7 @@ module Dal : sig
       History_cache.t ->
       Raw_level.t ->
       number_of_slots:int ->
-      Slot.Header.t list ->
+      (Slot.Header.t * Attestation.attestation_status) list ->
       (t * History_cache.t) tzresult
 
     type proof
diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.ml b/src/proto_alpha/lib_protocol/dal_slot_repr.ml
index c2aa20dd31ed..87fc6d51ab7e 100644
--- a/src/proto_alpha/lib_protocol/dal_slot_repr.ml
+++ b/src/proto_alpha/lib_protocol/dal_slot_repr.ml
@@ -552,7 +552,7 @@ module History = struct
 
        - [l] is well sorted wrt. slots indices. *)
     let fill_slot_headers ~number_of_slots ~published_level
-        attested_slot_headers =
+        slot_headers_with_statuses =
       let open Result_syntax in
       let module I = Dal_slot_index_repr in
       let* all_indices =
@@ -561,6 +561,8 @@ module History = struct
       let mk_unattested index =
         Content.Unattested Header.{published_level; index}
       in
+      (* TODO: Follow-up MR: Take the value of _s_status into account. *)
+      let attested_slot_headers = List.map fst slot_headers_with_statuses in
       (* Hypothesis: both lists are sorted in increasing order w.r.t. slots
          indices. *)
       let rec aux indices slots =
@@ -585,31 +587,36 @@ module History = struct
        will simplify the shape of proofs and help bounding the history cache
        required for their generation. *)
     let update_skip_list (t : t) cache published_level ~number_of_slots
-        attested_slot_headers =
+        slot_headers_with_statuses =
       let open Result_syntax in
       let* () =
         List.iter_e
-          (fun slot_header ->
+          (fun (slot_header, _status) ->
             error_unless
               Raw_level_repr.(
                 published_level = slot_header.Header.id.published_level)
               Add_element_in_slots_skip_list_violates_ordering)
-          attested_slot_headers
+          slot_headers_with_statuses
       in
       let* slot_headers =
         fill_slot_headers
           ~number_of_slots
           ~published_level
-          attested_slot_headers
+          slot_headers_with_statuses
       in
       List.fold_left_e (add_cell ~number_of_slots) (t, cache) slot_headers
 
     let update_skip_list_no_cache =
       let empty_cache = History_cache.empty ~capacity:0L in
-      fun t published_level ~number_of_slots slots ->
+      fun t published_level ~number_of_slots slot_headers_with_statuses ->
         let open Result_syntax in
         let+ cell, (_ : History_cache.t) =
-          update_skip_list t empty_cache published_level ~number_of_slots slots
+          update_skip_list
+            t
+            empty_cache
+            published_level
+            ~number_of_slots
+            slot_headers_with_statuses
         in
         cell
 
diff --git a/src/proto_alpha/lib_protocol/dal_slot_repr.mli b/src/proto_alpha/lib_protocol/dal_slot_repr.mli
index 6992dacfd7de..568e27b34844 100644
--- a/src/proto_alpha/lib_protocol/dal_slot_repr.mli
+++ b/src/proto_alpha/lib_protocol/dal_slot_repr.mli
@@ -255,9 +255,9 @@ module History : sig
     Bounded_history_repr.S with type key = hash and type value = t
 
   (** [update_skip_list hist cache published_level ~number_of_slots
-      slot_headers] updates the given structure [hist] with the list of
-      [slot_headers]. The given [cache] is also updated to add successive values
-      of [cell] to it.
+      slot_headers_with_statuses] updates the given structure [hist] with the
+      list of [slot_headers_with_statuses]. The given [cache] is also updated to
+      add successive values of [cell] to it.
 
 
       This function checks the following pre-conditions before updating the
@@ -268,20 +268,24 @@ module History : sig
 
       - [published_level] is the successor the last inserted cell's level.
 
-      - [slot_headers] is sorted in increasing order w.r.t. slots indices.
-  *)
+      - [slot_headers_with_statuses] is sorted in increasing order w.r.t. slots
+      indices. *)
   val update_skip_list :
     t ->
     History_cache.t ->
     Raw_level_repr.t ->
     number_of_slots:int ->
-    Header.t list ->
+    (Header.t * Dal_attestation_repr.Accountability.attestation_status) list ->
     (t * History_cache.t) tzresult
 
   (** Similiar to {!update_skip_list}, but no cache is provided or
       updated. *)
   val update_skip_list_no_cache :
-    t -> Raw_level_repr.t -> number_of_slots:int -> Header.t list -> t tzresult
+    t ->
+    Raw_level_repr.t ->
+    number_of_slots:int ->
+    (Header.t * Dal_attestation_repr.Accountability.attestation_status) list ->
+    t tzresult
 
   (** [equal a b] returns true iff a is equal to b. *)
   val equal : t -> t -> bool
diff --git a/src/proto_alpha/lib_protocol/dal_slot_storage.ml b/src/proto_alpha/lib_protocol/dal_slot_storage.ml
index 2a5e3ac15d85..a5f8621c6bf4 100644
--- a/src/proto_alpha/lib_protocol/dal_slot_storage.ml
+++ b/src/proto_alpha/lib_protocol/dal_slot_storage.ml
@@ -75,16 +75,12 @@ let update_skip_list ctxt ~slot_headers_statuses ~level_attested
     *)
     (* We expect to put exactly [number_of_slots] cells in the cache. *)
     let cache = History_cache.empty ~capacity:(Int64.of_int number_of_slots) in
-    let confirmed_slot_headers =
-      (* WIP/Temporary: will be extended in next commits. *)
-      List.map fst slot_headers_statuses
-    in
     update_skip_list
       ~number_of_slots
       slots_history
       cache
       level_attested
-      confirmed_slot_headers
+      slot_headers_statuses
   in
   let*! ctxt = Storage.Dal.Slot.History.add ctxt slots_history in
   let*! ctxt =
diff --git a/src/proto_alpha/lib_protocol/dune b/src/proto_alpha/lib_protocol/dune
index 24f8b2a0e103..f50c2d3c1c8a 100644
--- a/src/proto_alpha/lib_protocol/dune
+++ b/src/proto_alpha/lib_protocol/dune
@@ -84,8 +84,8 @@
   Indexable
   Entrypoint_repr
   Dal_slot_index_repr
-  Dal_slot_repr
   Dal_attestation_repr
+  Dal_slot_repr
   Michelson_v1_gas_costs_generated
   Michelson_v1_gas_costs
   Sc_rollup_repr
@@ -379,8 +379,8 @@
   indexable.ml indexable.mli
   entrypoint_repr.ml entrypoint_repr.mli
   dal_slot_index_repr.ml dal_slot_index_repr.mli
-  dal_slot_repr.ml dal_slot_repr.mli
   dal_attestation_repr.ml dal_attestation_repr.mli
+  dal_slot_repr.ml dal_slot_repr.mli
   michelson_v1_gas_costs_generated.ml
   michelson_v1_gas_costs.ml
   sc_rollup_repr.ml sc_rollup_repr.mli
@@ -678,8 +678,8 @@
   indexable.ml indexable.mli
   entrypoint_repr.ml entrypoint_repr.mli
   dal_slot_index_repr.ml dal_slot_index_repr.mli
-  dal_slot_repr.ml dal_slot_repr.mli
   dal_attestation_repr.ml dal_attestation_repr.mli
+  dal_slot_repr.ml dal_slot_repr.mli
   michelson_v1_gas_costs_generated.ml
   michelson_v1_gas_costs.ml
   sc_rollup_repr.ml sc_rollup_repr.mli
@@ -961,8 +961,8 @@
   indexable.ml indexable.mli
   entrypoint_repr.ml entrypoint_repr.mli
   dal_slot_index_repr.ml dal_slot_index_repr.mli
-  dal_slot_repr.ml dal_slot_repr.mli
   dal_attestation_repr.ml dal_attestation_repr.mli
+  dal_slot_repr.ml dal_slot_repr.mli
   michelson_v1_gas_costs_generated.ml
   michelson_v1_gas_costs.ml
   sc_rollup_repr.ml sc_rollup_repr.mli
diff --git a/src/proto_alpha/lib_protocol/test/pbt/test_dal_slot_proof.ml b/src/proto_alpha/lib_protocol/test/pbt/test_dal_slot_proof.ml
index e5cdb86749d8..d3808cc558b1 100644
--- a/src/proto_alpha/lib_protocol/test/pbt/test_dal_slot_proof.ml
+++ b/src/proto_alpha/lib_protocol/test/pbt/test_dal_slot_proof.ml
@@ -99,9 +99,18 @@ struct
               skip_slot ))
           slots_data
       in
-      let attested_slots_headers =
+      let slots_headers =
         List.filter_map
-          (fun (slot, skip_slot) -> if skip_slot then None else Some slot)
+          (fun (slot, skip_slot) ->
+            let attestation_status =
+              Dal_attestation_repr.Accountability.
+                {
+                  attested_shards = (if skip_slot then 0 else 1);
+                  total_shards = 1;
+                  is_proto_attested = not skip_slot;
+                }
+            in
+            if skip_slot then None else Some (slot, attestation_status))
           slots_headers
       in
       let*?@ cell, cache =
@@ -110,12 +119,12 @@ struct
           cell
           cache
           curr_level
-          attested_slots_headers
+          slots_headers
       in
       let slots_info =
         List.fold_left
-          (fun slots_info (slot, skip_slot) ->
-            (polynomial, slot, skip_slot) :: slots_info)
+          (fun slots_info (slot, slot_status) ->
+            (polynomial, slot, slot_status) :: slots_info)
           slots_info
           slots_headers
       in
@@ -128,9 +137,10 @@ struct
 
   (** This function returns the (correct) information of a page to
       prove that it is confirmed, or None if the page's slot is skipped. *)
-  let request_confirmed_page (poly, slot, skip_slot) =
+  let request_confirmed_page (poly, slot, slot_status) =
     let open Lwt_result_syntax in
-    if skip_slot then
+    if not slot_status.Dal_attestation_repr.Accountability.is_proto_attested
+    then
       (* We cannot check that a page of an unconfirmed slot is confirmed. *)
       return_none
     else
@@ -142,10 +152,11 @@ struct
       (but the slot is not confirmed). Otherwise, we increment the publish_level
       field to simulate a non confirmed slot (as for even levels, no slot is
       confirmed. See {!populate_slots_history}). *)
-  let request_unconfirmed_page (poly, slot, skip_slot) =
+  let request_unconfirmed_page (poly, slot, slot_status) =
     let open Lwt_result_syntax in
     let open Dal_slot_repr.Header in
-    if skip_slot then
+    if not slot_status.Dal_attestation_repr.Accountability.is_proto_attested
+    then
       let level = slot.id.published_level in
       let* _page_info, page_id = mk_page_info ~level slot poly in
       (* We should not provide the page's info if we want to build an
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 cfa9f949af57..e24ca6075133 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
@@ -122,13 +122,18 @@ module Index = Dal_slot_index_repr
 let pack_slots_headers_by_level list =
   let module ML = Map.Make (Raw_level_repr) in
   let module SSH = Set.Make (struct
-    include Dal_slot_repr.Header
+    type t =
+      Dal_slot_repr.Header.t
+      * Dal_attestation_repr.Accountability.attestation_status
 
-    let compare a b = Dal_slot_index_repr.compare a.id.index b.id.index
+    let compare (a, _) (b, _) =
+      let open Dal_slot_repr.Header in
+      Dal_slot_index_repr.compare a.id.index b.id.index
   end) in
   let map =
     List.fold_left
-      (fun map (Dal_slot_repr.Header.{id = {published_level; _}; _} as sh) ->
+      (fun map
+           ((Dal_slot_repr.Header.{id = {published_level; _}; _}, _status) as sh) ->
         let l =
           ML.find published_level map |> Option.value ~default:SSH.empty
         in
@@ -160,10 +165,18 @@ let gen_dal_slots_history () =
   in
   let number_of_slots = constants.dal.number_of_slots in
   (* Generate a list of (level * confirmed slot ID). *)
-  let* list = small_list (pair small_nat small_nat) in
+  let* list = small_list (triple small_nat small_nat bool) in
   let list =
     List.rev_map
-      (fun (level, slot_index) ->
+      (fun (level, slot_index, is_proto_attested) ->
+        let attestation_status =
+          Dal_attestation_repr.Accountability.
+            {
+              attested_shards = (if is_proto_attested then 1 else 0);
+              total_shards = 1;
+              is_proto_attested;
+            }
+        in
         let published_level =
           Raw_level_repr.(
             (* use succ to avoid having a published_level = 0, as it's the
@@ -174,7 +187,8 @@ let gen_dal_slots_history () =
           Index.of_int_opt ~number_of_slots slot_index
           |> Option.value ~default:Index.zero
         in
-        Header.{id = {published_level; index}; commitment = Commitment.zero})
+        ( Header.{id = {published_level; index}; commitment = Commitment.zero},
+          attestation_status ))
       list
   in
   let rec loop history = function
@@ -183,7 +197,7 @@ let gen_dal_slots_history () =
         let slot_headers =
           (* Sort the list in the right ordering before adding slots to slots_history. *)
           List.sort_uniq
-            (fun {Header.id = a; _} {id = b; _} ->
+            (fun ({Header.id = a; _}, _status) ({id = b; _}, _status) ->
               let c =
                 Raw_level_repr.compare a.published_level b.published_level
               in
diff --git a/src/proto_alpha/lib_protocol/test/unit/test_dal_slot_proof.ml b/src/proto_alpha/lib_protocol/test/unit/test_dal_slot_proof.ml
index 212c332d9b45..f767d21e5971 100644
--- a/src/proto_alpha/lib_protocol/test/unit/test_dal_slot_proof.ml
+++ b/src/proto_alpha/lib_protocol/test/unit/test_dal_slot_proof.ml
@@ -51,6 +51,10 @@ struct
       Dal_helpers.mk_cryptobox Parameters.dal_parameters.cryptobox_parameters
   end)
 
+  let mk_attested =
+    Dal_attestation_repr.Accountability.
+      {total_shards = 1; attested_shards = 1; is_proto_attested = true}
+
   (* Tests to check insertion of slots in a dal skip list. *)
 
   (** Check insertion of a new slot in the given skip list. *)
@@ -66,10 +70,9 @@ struct
       Hist.update_skip_list_no_cache
         skip_list
         level
-        [slot]
+        [(slot, mk_attested)]
         ~number_of_slots:Parameters.dal_parameters.number_of_slots
     in
-
     check_result result
 
   (** This test attempts to add a slot on top of genesis cell zero which would
@@ -193,7 +196,7 @@ struct
         genesis_history
         genesis_history_cache
         level
-        [slot]
+        [(slot, mk_attested)]
     in
     let* page_info, page_id = mk_page_info slot polynomial in
     produce_and_verify_proof
diff --git a/src/proto_alpha/lib_sc_rollup_node/test/test_octez_conversions.ml b/src/proto_alpha/lib_sc_rollup_node/test/test_octez_conversions.ml
index 8751a9c286a0..614a3c5d26d2 100644
--- a/src/proto_alpha/lib_sc_rollup_node/test/test_octez_conversions.ml
+++ b/src/proto_alpha/lib_sc_rollup_node/test/test_octez_conversions.ml
@@ -220,39 +220,53 @@ let compare_slot_header_id (s1 : Octez_smart_rollup.Dal.Slot_header.id)
   let c = Int32.compare s1.published_level s2.published_level in
   if c <> 0 then c else Int.compare s1.index s2.index
 
-let gen_slot_headers =
+let gen_slot_header_with_status =
+  let open Protocol.Alpha_context in
+  let open QCheck2.Gen in
+  let* status = bool in
+  let status =
+    let total_shards = 1 in
+    let attested_shards = if status then total_shards else 0 in
+    Dal.Attestation.{total_shards; attested_shards; is_proto_attested = status}
+  in
+  let+ header = gen_slot_header in
+  (header, status)
+
+let gen_slot_headers_with_statuses =
   let open QCheck2.Gen in
   let size = int_bound 50 in
-  let+ l = list_size size gen_slot_header in
+  let+ l = list_size size gen_slot_header_with_status in
   List.sort
-    (fun (h1 : Octez_smart_rollup.Dal.Slot_header.t)
-         (h2 : Octez_smart_rollup.Dal.Slot_header.t) ->
+    (fun ((h1 : Octez_smart_rollup.Dal.Slot_header.t), _status1)
+         ((h2 : Octez_smart_rollup.Dal.Slot_header.t), _status2) ->
       compare_slot_header_id h1.id h2.id)
     l
   |> fun l ->
   match l with
   | [] -> []
-  | (h : Octez_smart_rollup.Dal.Slot_header.t) :: _ ->
+  | ((h : Octez_smart_rollup.Dal.Slot_header.t), _status) :: _ ->
       let min_level = h.id.published_level in
       (* smallest level *)
       List.mapi
-        (fun i (h : Octez_smart_rollup.Dal.Slot_header.t) ->
+        (fun i ((h : Octez_smart_rollup.Dal.Slot_header.t), status) ->
           (* patch the published level to comply with the invariants *)
           let published_level = Int32.(add min_level (of_int i)) in
           let h = {h with id = {h.id with published_level}} in
-          (published_level, [h]))
+          (published_level, [(h, status)]))
         l
 
 let gen_slot_history =
   let open Protocol.Alpha_context in
   let open QCheck2.Gen in
-  let+ l = gen_slot_headers in
+  let+ l = gen_slot_headers_with_statuses in
   let l =
     List.map
       (fun (lvl, h) ->
         ( Raw_level.of_int32_exn lvl,
           List.map
-            (Sc_rollup_proto_types.Dal.Slot_header.of_octez ~number_of_slots)
+            (fun (h, status) ->
+              ( Sc_rollup_proto_types.Dal.Slot_header.of_octez ~number_of_slots h,
+                status ))
             h ))
       l
   in
@@ -273,14 +287,16 @@ let gen_slot_history =
 let gen_slot_history_cache =
   let open Protocol.Alpha_context in
   let open QCheck2.Gen in
-  let+ l = gen_slot_headers in
+  let+ l = gen_slot_headers_with_statuses in
   let cache = Dal.Slots_history.History_cache.empty ~capacity:Int64.max_int in
   let l =
     List.map
       (fun (lvl, h) ->
         ( Raw_level.of_int32_exn lvl,
           List.map
-            (Sc_rollup_proto_types.Dal.Slot_header.of_octez ~number_of_slots)
+            (fun (h, status) ->
+              ( Sc_rollup_proto_types.Dal.Slot_header.of_octez ~number_of_slots h,
+                status ))
             h ))
       l
   in
-- 
GitLab


From 2c15348d0a51decce0088472b7d02484fa08f2aa Mon Sep 17 00:00:00 2001
From: "iguerNL@Functori" <iguer@functori.com>
Date: Wed, 23 Oct 2024 08:16:36 +0200
Subject: [PATCH 5/5] DAL/Proto: move the code that computes proto attestation
 status into a separate function

---
 .../lib_protocol/dal_attestation_repr.ml      | 25 +++++++++++++++++--
 1 file changed, 23 insertions(+), 2 deletions(-)

diff --git a/src/proto_alpha/lib_protocol/dal_attestation_repr.ml b/src/proto_alpha/lib_protocol/dal_attestation_repr.ml
index ae2d974204d6..d8429e61a2e9 100644
--- a/src/proto_alpha/lib_protocol/dal_attestation_repr.ml
+++ b/src/proto_alpha/lib_protocol/dal_attestation_repr.ml
@@ -135,6 +135,25 @@ module Accountability = struct
     let number_of_attested_shards = iter 0 t.number_of_attested_shards in
     {t with number_of_attested_shards}
 
+  (* Given a slot encoded as [number_of_shards] shards and for which
+     [number_of_attested_shards] are attested by the bakers. The slot is
+     declated as attested_slots IFF at least [threshold] % of the total shards
+     are attested by bakers.
+
+     On rationals, the condition above means:
+
+     number_of_attested_shards / number_of_shards >= threshold / 100,
+
+     which is equivalent, on rationals, to:
+
+     number_of_attested_shards >= (threshold * number_of_shards) / 100
+
+     Note that the last reformulation translates to integers. *)
+  let compute_proto_attestation_status ~number_of_attested_shards ~threshold
+      ~number_of_shards =
+    Compare.Int.(
+      number_of_attested_shards >= threshold * number_of_shards / 100)
+
   let is_slot_attested t ~threshold ~number_of_shards slot_index =
     let index = Dal_slot_index_repr.to_int slot_index in
     let number_of_attested_shards =
@@ -143,8 +162,10 @@ module Accountability = struct
       | Some v -> v
     in
     let is_proto_attested =
-      Compare.Int.(
-        number_of_attested_shards >= threshold * number_of_shards / 100)
+      compute_proto_attestation_status
+        ~number_of_attested_shards
+        ~threshold
+        ~number_of_shards
     in
     {
       is_proto_attested;
-- 
GitLab