From 351f24fe335b17556297eaaf7eed0fddb4fc2aee Mon Sep 17 00:00:00 2001 From: Eugen Zalinescu Date: Sat, 13 Dec 2025 08:56:57 +0100 Subject: [PATCH 1/3] Alpha/DAL: add `Dal_attestation_repr.is_empty` --- src/proto_alpha/lib_protocol/dal_attestation_repr.ml | 2 ++ src/proto_alpha/lib_protocol/dal_attestation_repr.mli | 3 +++ 2 files changed, 5 insertions(+) diff --git a/src/proto_alpha/lib_protocol/dal_attestation_repr.ml b/src/proto_alpha/lib_protocol/dal_attestation_repr.ml index 9a2f3187efa8..bd30924e33ec 100644 --- a/src/proto_alpha/lib_protocol/dal_attestation_repr.ml +++ b/src/proto_alpha/lib_protocol/dal_attestation_repr.ml @@ -30,6 +30,8 @@ let encoding = Bitset.encoding let empty = Bitset.empty +let is_empty = Bitset.is_empty + let to_z = Bitset.to_z let is_attested t index = diff --git a/src/proto_alpha/lib_protocol/dal_attestation_repr.mli b/src/proto_alpha/lib_protocol/dal_attestation_repr.mli index 4f0871ea6e03..4de08b5a5229 100644 --- a/src/proto_alpha/lib_protocol/dal_attestation_repr.mli +++ b/src/proto_alpha/lib_protocol/dal_attestation_repr.mli @@ -52,6 +52,9 @@ val encoding : t Data_encoding.t every slot are unavailable. *) val empty : t +(** [is_empty slot_attestation] returns [true] if no slots are attested. *) +val is_empty : t -> bool + (** [is_attested slot_attestation ~index] returns [true] if the [slot_attestation] commits that the slot at [index] is available. *) -- GitLab From e18c17067de3bc6d143a6df5a78fd707d573b9b6 Mon Sep 17 00:00:00 2001 From: Eugen Zalinescu Date: Thu, 20 Nov 2025 14:43:02 +0100 Subject: [PATCH 2/3] Alpha/DAL: add new module `Dal_attestations_repr` --- src/proto_alpha/lib_protocol/TEZOS_PROTOCOL | 1 + .../lib_protocol/dal_attestations_repr.ml | 121 ++++++++++++++++++ .../lib_protocol/dal_attestations_repr.mli | 121 ++++++++++++++++++ src/proto_alpha/lib_protocol/dune | 4 + 4 files changed, 247 insertions(+) create mode 100644 src/proto_alpha/lib_protocol/dal_attestations_repr.ml create mode 100644 src/proto_alpha/lib_protocol/dal_attestations_repr.mli diff --git a/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL b/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL index cf6b1295d11c..6815fa3a0df6 100644 --- a/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL +++ b/src/proto_alpha/lib_protocol/TEZOS_PROTOCOL @@ -58,6 +58,7 @@ "Dal_slot_index_repr", "Dal_attestation_repr", + "Dal_attestations_repr", "Dal_slot_repr", "Michelson_v1_gas_costs_generated", diff --git a/src/proto_alpha/lib_protocol/dal_attestations_repr.ml b/src/proto_alpha/lib_protocol/dal_attestations_repr.ml new file mode 100644 index 000000000000..421772f61366 --- /dev/null +++ b/src/proto_alpha/lib_protocol/dal_attestations_repr.ml @@ -0,0 +1,121 @@ +(*****************************************************************************) +(* *) +(* SPDX-License-Identifier: MIT *) +(* Copyright (c) 2025 Nomadic Labs, *) +(* *) +(*****************************************************************************) + +(* A compact representation of multiple DAL attestations at different lags. *) +type t = Bitset.t + +let encoding = Bitset.encoding + +let empty = Bitset.empty + +let is_empty = Bitset.is_empty + +(* Helper to safely check membership in a bitset, returning false on error. *) +let bitset_mem bitset idx = + match Bitset.mem bitset idx with Ok b -> b | Error _ -> false + +(* Helper to safely add to a bitset, returning the original bitset on error. *) +let bitset_add bitset idx = + match Bitset.add bitset idx with Ok b -> b | Error _ -> bitset + +(* Helper: compute the data bit position for a slot at a given lag_index. + Returns None if the attestation at lag_index is empty. *) +let compute_data_bit_position t ~number_of_slots ~number_of_lags ~lag_index + slot_index = + (* Check if the attestation at [lag_index] is non-empty *) + let is_non_empty = bitset_mem t lag_index in + if not is_non_empty then None + else + (* Count non-empty attestations before [lag_index] *) + let rec count_preceding acc idx = + if Compare.Int.(idx >= lag_index) then acc + else + let is_set = bitset_mem t idx in + count_preceding (if is_set then acc + 1 else acc) (idx + 1) + in + let num_preceding_non_empty = count_preceding 0 0 in + let slot_bit_idx = Dal_slot_index_repr.to_int slot_index in + let data_bit_pos = + number_of_lags + + (num_preceding_non_empty * number_of_slots) + + slot_bit_idx + in + Some data_bit_pos + +let is_attested t ~number_of_slots ~number_of_lags ~lag_index slot_index = + assert (Compare.Int.(lag_index >= 0 && lag_index < number_of_lags)) ; + assert (Compare.Int.(Dal_slot_index_repr.to_int slot_index < number_of_slots)) ; + match + compute_data_bit_position + t + ~number_of_slots + ~number_of_lags + ~lag_index + slot_index + with + | None -> false + | Some data_bit_pos -> bitset_mem t data_bit_pos + +(* Set a slot bit at a given lag in the encoded bitset. + [bitset] is the full attestations bitset. + [number_of_slots] is the number of slots per attestation. + [lag_index] is the index of the attestation lag (0-based). + [number_of_lags] is the total number of lags. + [slot_index] is the slot to set. + Returns the updated attestations bitset. + + This only sets bits (never clears them), so transitions are: + - Empty -> Non-empty (slow path: inserts attestation data) + - Non-empty -> Non-empty (fast path: sets bit in place) *) +let commit bitset ~number_of_slots ~number_of_lags ~lag_index slot_index = + assert (Compare.Int.(lag_index >= 0 && lag_index < number_of_lags)) ; + assert (Compare.Int.(Dal_slot_index_repr.to_int slot_index < number_of_slots)) ; + + let is_non_empty_at idx = bitset_mem bitset idx in + + (* Count non-empty attestations before [lag_index] *) + let rec count_before acc idx = + if Compare.Int.(idx >= lag_index) then acc + else count_before (if is_non_empty_at idx then acc + 1 else acc) (idx + 1) + in + let num_before = count_before 0 0 in + + if is_non_empty_at lag_index then + (* Fast path: attestation already exists, just set the bit *) + let data_start = number_of_lags + (num_before * number_of_slots) in + let slot_idx = Dal_slot_index_repr.to_int slot_index in + bitset_add bitset (data_start + slot_idx) + else + (* Slow path: attestation is empty. Build new bitset by copying old bits, + shifting those at or after [insertion_point] by [number_of_slots] to make + room for the new attestation data. *) + let insertion_point = number_of_lags + (num_before * number_of_slots) in + (* Copy all existing bits, shifting data bits at or after [insertion_point] *) + let result = + List.fold_left + (fun res index -> + let new_index = + if Compare.Int.(index >= insertion_point) then + index + number_of_slots + else index + in + bitset_add res new_index) + Bitset.empty + (Bitset.to_list bitset) + in + (* Set the new lag index bit in the prefix *) + let result = bitset_add result lag_index in + (* Set the new slot bit at the insertion point *) + let slot_idx = Dal_slot_index_repr.to_int slot_index in + bitset_add result (insertion_point + slot_idx) + +let occupied_size_in_bits = Bitset.occupied_size_in_bits + +let expected_max_size_in_bits ~number_of_slots ~number_of_lags = + (* [number_of_lags] for the prefix and [number_of_lags * number_of_slots] for + the data section. *) + number_of_lags * (1 + number_of_slots) diff --git a/src/proto_alpha/lib_protocol/dal_attestations_repr.mli b/src/proto_alpha/lib_protocol/dal_attestations_repr.mli new file mode 100644 index 000000000000..237da1e99d4d --- /dev/null +++ b/src/proto_alpha/lib_protocol/dal_attestations_repr.mli @@ -0,0 +1,121 @@ +(*****************************************************************************) +(* *) +(* SPDX-License-Identifier: MIT *) +(* Copyright (c) 2025 Nomadic Labs, *) +(* *) +(*****************************************************************************) + +(** Multiple attestations representation for the data-availability layer. + + {1 Overview} + + This module extends {!Dal_attestation_repr} to handle multiple DAL + attestations at different lags. A lag represents the difference between the + attested level of a slot and its published level. + + The structure stores a fixed number of attestations, determined by + [number_of_lags]. Each attestation is indexed by [lag_index] (0-based) and + is a bitset encoding which slots are attested at a particular level. The + slots' (published) level is implicit (it is obtained as "attested level" + minus the lag corresponding to the given lag index), and is not relevant for + this module. + + {1 Encoding} + + The encoding uses a compact bitset representation that minimizes space + when attestations are empty: + + {2 Bitset structure} + + The bitset is stored as an integer, with bit positions starting at 0 (LSB). + The structure is: + + - {b Prefix} ([number_of_lags] bits at positions 0 to [number_of_lags-1]): + Indicates which attestations are non-empty. Bit [i] corresponds to lag + index [i]. If bit [i] = 1, the attestation at lag index [i] is non-empty. + We call this a "prefix" because it logically comes first in the structure, + even though it occupies the {i lowest} bit positions. + + - {b Data section} (starting at bit position [number_of_lags]): For each + non-empty attestation (in order from lag index [0] to [number_of_lags-1]), + exactly [number_of_slots] bits are stored, representing the attested slots. + Empty attestations are not stored in the data section. + + - {b Empty case}: An empty bitset (value 0) represents the case where all + attestations are empty. + + {3 Example} + + For [number_of_lags = 4] and [number_of_slots = 32]: + - Attestation at lag index 0: empty + - Attestation at lag index 1: slots 1, 5 attested + - Attestation at lag index 2: empty + - Attestation at lag index 3: slots 0, 1 attested + + The full bitset in standard binary notation (MSB left, LSB right): + +{v +00000000000000000000000000000011 00000000000000000000000000100010 1010 +<-------- lag 3 data ----------> <-------- lag 1 data ----------> <--> + (32 bits) (32 bits) prefix + slots 0, 1 slots 1, 5 lags 1, 3 +v} + + Bit positions: + - Prefix: bits 0-3 (rightmost 4 bits), value [0b1010 = 10] + - Lag 1 data: bits 4-35, with bits 5 and 9 set (slots 1 and 5) + - Lag 3 data: bits 36-67, with bits 36 and 37 set (slots 0 and 1) + - Total: 68 bits + + {3 Design considerations} + + An {b alternative encoding} would store the actual length of each non-empty + attestation (e.g., 5 bits for length, then that many data bits). This would + save space when attestations have few bits set, at the cost of additional + complexity. *) + +type t + +(** The size of the encoding is not bounded. However, the size of a DAL + attestations bitset is checked during validation of an attestation; and + there is a bound on the size of a generic operation. *) +val encoding : t Data_encoding.t + +(** [empty] returns an empty attestation structure where all slots at all lags + are marked as unavailable. *) +val empty : t + +(** [is_empty t] returns [true] if all attestations at all lags are empty. *) +val is_empty : t -> bool + +(** [is_attested t ~number_of_slots ~number_of_lags ~lag_index slot_index] returns + [true] if the attestation at [lag_index] commits that the slot at + [slot_index] is available. [lag_index] must satisfy [0 <= lag_index < + number_of_lags], and [slot_index] must satisfy [0 <= slot_index < + number_of_slots]. *) +val is_attested : + t -> + number_of_slots:int -> + number_of_lags:int -> + lag_index:int -> + Dal_slot_index_repr.t -> + bool + +(** [commit t ~number_of_slots ~number_of_lags ~lag_index slot_index] commits into + the attestation at [lag_index] that the slot [slot_index] is available. + [lag_index] must satisfy [0 <= lag_index < number_of_lags], and [slot_index] + must satisfy [0 <= slot_index < number_of_slots]. *) +val commit : + t -> + number_of_slots:int -> + number_of_lags:int -> + lag_index:int -> + Dal_slot_index_repr.t -> + t + +(** [occupied_size_in_bits v] returns the size in bits of [v]. *) +val occupied_size_in_bits : t -> int + +(** [expected_max_size_in_bits ~number_of_slots ~number_of_lags] returns the + maximum size (in bits) of a [t] value. *) +val expected_max_size_in_bits : number_of_slots:int -> number_of_lags:int -> int diff --git a/src/proto_alpha/lib_protocol/dune b/src/proto_alpha/lib_protocol/dune index e57a9089a61c..25be8b874c6c 100644 --- a/src/proto_alpha/lib_protocol/dune +++ b/src/proto_alpha/lib_protocol/dune @@ -86,6 +86,7 @@ Entrypoint_repr Dal_slot_index_repr Dal_attestation_repr + Dal_attestations_repr Dal_slot_repr Michelson_v1_gas_costs_generated Michelson_v1_gas_costs @@ -388,6 +389,7 @@ entrypoint_repr.ml entrypoint_repr.mli dal_slot_index_repr.ml dal_slot_index_repr.mli dal_attestation_repr.ml dal_attestation_repr.mli + dal_attestations_repr.ml dal_attestations_repr.mli dal_slot_repr.ml dal_slot_repr.mli michelson_v1_gas_costs_generated.ml michelson_v1_gas_costs.ml @@ -695,6 +697,7 @@ entrypoint_repr.ml entrypoint_repr.mli dal_slot_index_repr.ml dal_slot_index_repr.mli dal_attestation_repr.ml dal_attestation_repr.mli + dal_attestations_repr.ml dal_attestations_repr.mli dal_slot_repr.ml dal_slot_repr.mli michelson_v1_gas_costs_generated.ml michelson_v1_gas_costs.ml @@ -986,6 +989,7 @@ entrypoint_repr.ml entrypoint_repr.mli dal_slot_index_repr.ml dal_slot_index_repr.mli dal_attestation_repr.ml dal_attestation_repr.mli + dal_attestations_repr.ml dal_attestations_repr.mli dal_slot_repr.ml dal_slot_repr.mli michelson_v1_gas_costs_generated.ml michelson_v1_gas_costs.ml -- GitLab From 15fba928ae6b08915fb67b6f6ec9e0f2af68f4fa Mon Sep 17 00:00:00 2001 From: Eugen Zalinescu Date: Sat, 13 Dec 2025 09:00:10 +0100 Subject: [PATCH 3/3] Alpha/DAL: add unit tests for `Dal_attestations_repr` --- manifest/product_octez.ml | 1 + src/proto_alpha/lib_protocol/test/unit/dune | 1 + .../test/unit/test_dal_attestations_repr.ml | 542 ++++++++++++++++++ 3 files changed, 544 insertions(+) create mode 100644 src/proto_alpha/lib_protocol/test/unit/test_dal_attestations_repr.ml diff --git a/manifest/product_octez.ml b/manifest/product_octez.ml index cf73e2e1dd7f..d1c7f41442e1 100644 --- a/manifest/product_octez.ml +++ b/manifest/product_octez.ml @@ -6577,6 +6577,7 @@ end = struct ("test_local_contexts", N.(number >= 016)); ("test_dal_slot_proof", N.(number >= 016)); ("test_dal_past_parameters_storage", N.(number >= 025)); + ("test_dal_attestations_repr", N.(number >= 025)); ("test_adaptive_issuance", N.(number >= 018)); ("test_adaptive_issuance_ema", N.(number <= 023)); ("test_percentage", N.(number >= 019)); diff --git a/src/proto_alpha/lib_protocol/test/unit/dune b/src/proto_alpha/lib_protocol/test/unit/dune index 91736775b47e..6fe842f6beb8 100644 --- a/src/proto_alpha/lib_protocol/test/unit/dune +++ b/src/proto_alpha/lib_protocol/test/unit/dune @@ -72,6 +72,7 @@ test_local_contexts test_dal_slot_proof test_dal_past_parameters_storage + test_dal_attestations_repr test_adaptive_issuance test_percentage test_full_staking_balance_repr diff --git a/src/proto_alpha/lib_protocol/test/unit/test_dal_attestations_repr.ml b/src/proto_alpha/lib_protocol/test/unit/test_dal_attestations_repr.ml new file mode 100644 index 000000000000..653c417a192e --- /dev/null +++ b/src/proto_alpha/lib_protocol/test/unit/test_dal_attestations_repr.ml @@ -0,0 +1,542 @@ +(*****************************************************************************) +(* *) +(* SPDX-License-Identifier: MIT *) +(* Copyright (c) 2025 Nomadic Labs, *) +(* *) +(*****************************************************************************) + +(** Testing + ------- + Component: Protocol (dal attestations representation) + Invocation: dune exec src/proto_alpha/lib_protocol/test/unit/main.exe \ + -- --file test_dal_attestations_repr.ml + Subject: These unit tests check Dal_attestations_repr encoding and operations. +*) + +open Protocol + +let number_of_slots = 32 + +let number_of_lags = 4 + +(** Helper to create a slot index from an int *) +let slot_index_of_int i = + match Dal_slot_index_repr.of_int ~number_of_slots i with + | Ok idx -> idx + | Error _ -> Alcotest.failf "Invalid slot index: %d" i + +(** Helper for boolean assertions *) +let assert_equal_bool ~loc msg expected actual = + Assert.equal ~loc Bool.equal msg Format.pp_print_bool expected actual + +(** Helper for is_attested with pre-filled number_of_slots and number_of_lags *) +let is_attested t ~lag_index slot_index = + Dal_attestations_repr.is_attested + t + ~number_of_slots + ~number_of_lags + ~lag_index + (slot_index_of_int slot_index) + +(** Helper for commit with pre-filled number_of_slots and number_of_lags *) +let commit t ~lag_index slot_index = + Dal_attestations_repr.commit + t + ~number_of_slots + ~number_of_lags + ~lag_index + (slot_index_of_int slot_index) + +(** Test the example from the interface documentation: + - number_of_lags = 4, number_of_slots = 32 + - Lag 0: empty + - Lag 1: slots 0, 2 attested + - Lag 2: empty + - Lag 3: slots 0, 1 attested *) +let test_example_encoding () = + let open Lwt_result_wrap_syntax in + (* Build the example attestations structure *) + let t = Dal_attestations_repr.empty in + (* Lag 1: attest slots 0 and 2 *) + let t = commit t ~lag_index:1 0 in + let t = commit t ~lag_index:1 2 in + (* Lag 3: attest slots 0 and 1 *) + let t = commit t ~lag_index:3 0 in + let t = commit t ~lag_index:3 1 in + + (* Check all combinations of lag_index and slot_index *) + (* Expected attestations: + - Lag 0: all empty (slots 0-31 not attested) + - Lag 1: slots 0 and 2 attested, all others not attested + - Lag 2: all empty (slots 0-31 not attested) + - Lag 3: slots 0 and 1 attested, all others not attested *) + + (* Define expected attestations for each lag *) + let expected lag_idx slot_idx = + match lag_idx with + | 0 -> false (* Lag 0: empty *) + | 1 -> slot_idx = 0 || slot_idx = 2 (* Lag 1: slots 0 and 2 *) + | 2 -> false (* Lag 2: empty *) + | 3 -> slot_idx = 0 || slot_idx = 1 (* Lag 3: slots 0 and 1 *) + | _ -> false + in + + (* Check all lags *) + let* () = + List.iter_es + (fun lag_idx -> + List.iter_es + (fun slot_idx -> + let attested = is_attested t ~lag_index:lag_idx slot_idx in + assert_equal_bool + ~loc:__LOC__ + (Printf.sprintf "Lag %d, slot %d attestation" lag_idx slot_idx) + (expected lag_idx slot_idx) + attested) + (0 -- (number_of_slots - 1))) + (0 -- (number_of_lags - 1)) + in + + return_unit + +(** Test that empty attestations work correctly *) +let test_empty () = + let open Lwt_result_wrap_syntax in + let t = Dal_attestations_repr.empty in + + (* Check that all lags and slots are not attested *) + let* () = + List.iter_es + (fun lag_idx -> + List.iter_es + (fun slot_idx -> + let attested = is_attested t ~lag_index:lag_idx slot_idx in + assert_equal_bool + ~loc:__LOC__ + (Printf.sprintf + "Empty attestation: lag %d, slot %d" + lag_idx + slot_idx) + false + attested) + (0 -- (number_of_slots - 1))) + (0 -- (number_of_lags - 1)) + in + + return_unit + +(** Test committing the same slot multiple times (idempotent) *) +let test_commit_idempotent () = + let open Lwt_result_wrap_syntax in + let t = Dal_attestations_repr.empty in + + (* Commit slot 5 at lag 2 *) + let t = commit t ~lag_index:2 5 in + + (* Commit the same slot again *) + let t = commit t ~lag_index:2 5 in + + (* Check that slot 5 at lag 2 is attested *) + let attested = is_attested t ~lag_index:2 5 in + let* () = + assert_equal_bool ~loc:__LOC__ "Slot 5 at lag 2 attestation" true attested + in + + (* Check that other slots at lag 2 are not attested *) + let* () = + List.iter_es + (fun slot_idx -> + if slot_idx <> 5 then + let attested = is_attested t ~lag_index:2 slot_idx in + assert_equal_bool + ~loc:__LOC__ + (Printf.sprintf "Slot %d at lag 2 attestation" slot_idx) + false + attested + else return_unit) + (0 -- (number_of_slots - 1)) + in + + return_unit + +(** Test encoding and decoding *) +let test_encoding_roundtrip () = + let open Lwt_result_wrap_syntax in + (* Build a non-trivial attestations structure *) + let t = Dal_attestations_repr.empty in + let t = commit t ~lag_index:0 10 in + let t = commit t ~lag_index:1 5 in + let t = commit t ~lag_index:1 15 in + let t = commit t ~lag_index:3 0 in + + (* Encode and decode *) + let encoded = + Data_encoding.Binary.to_bytes_exn Dal_attestations_repr.encoding t + in + let decoded = + Data_encoding.Binary.of_bytes_exn Dal_attestations_repr.encoding encoded + in + + (* Check that the decoded value has the same attestations *) + let check_attestation lag_idx slot_idx expected = + let attested_original = is_attested t ~lag_index:lag_idx slot_idx in + let attested_decoded = is_attested decoded ~lag_index:lag_idx slot_idx in + let* () = + assert_equal_bool + ~loc:__LOC__ + "is_attested" + attested_original + attested_decoded + in + assert_equal_bool + ~loc:__LOC__ + "is_attested vs expected" + expected + attested_decoded + in + + (* Check specific attestations *) + let* () = check_attestation 0 10 true in + let* () = check_attestation 0 5 false in + let* () = check_attestation 1 5 true in + let* () = check_attestation 1 15 true in + let* () = check_attestation 1 10 false in + let* () = check_attestation 2 0 false in + let* () = check_attestation 3 0 true in + let* () = check_attestation 3 1 false in + + return_unit + +(** Test update_attestation fast path: non-empty → non-empty + This tests the optimization where we update bits in place *) +let test_update_existing_attestation () = + let open Lwt_result_wrap_syntax in + (* Create an attestation at lag 1 with slot 5 *) + let t = Dal_attestations_repr.empty in + let t = commit t ~lag_index:1 5 in + + (* Verify slot 5 is attested *) + let* () = + assert_equal_bool + ~loc:__LOC__ + "Slot 5 initially attested" + true + (is_attested t ~lag_index:1 5) + in + + (* Add more slots to the same lag (should use fast path) *) + let t = commit t ~lag_index:1 10 in + let t = commit t ~lag_index:1 15 in + + (* Verify all three slots are attested *) + let* () = + assert_equal_bool + ~loc:__LOC__ + "Slot 5 still attested" + true + (is_attested t ~lag_index:1 5) + in + let* () = + assert_equal_bool + ~loc:__LOC__ + "Slot 10 attested" + true + (is_attested t ~lag_index:1 10) + in + let* () = + assert_equal_bool + ~loc:__LOC__ + "Slot 15 attested" + true + (is_attested t ~lag_index:1 15) + in + + (* Verify other slots are not attested *) + let* () = + assert_equal_bool + ~loc:__LOC__ + "Slot 0 not attested" + false + (is_attested t ~lag_index:1 0) + in + let* () = + assert_equal_bool + ~loc:__LOC__ + "Slot 20 not attested" + false + (is_attested t ~lag_index:1 20) + in + + return_unit + +(** Test creating attestations at different lags (empty → non-empty path) *) +let test_multiple_lag_attestations () = + let open Lwt_result_wrap_syntax in + let t = Dal_attestations_repr.empty in + + (* Create attestations at different lags *) + let t = commit t ~lag_index:0 1 in + let t = commit t ~lag_index:2 2 in + let t = commit t ~lag_index:3 3 in + + (* Verify each lag has only its attested slot *) + let* () = + assert_equal_bool + ~loc:__LOC__ + "Lag 0, slot 1" + true + (is_attested t ~lag_index:0 1) + in + let* () = + assert_equal_bool + ~loc:__LOC__ + "Lag 0, slot 2" + false + (is_attested t ~lag_index:0 2) + in + let* () = + assert_equal_bool + ~loc:__LOC__ + "Lag 1 empty" + false + (is_attested t ~lag_index:1 0) + in + let* () = + assert_equal_bool + ~loc:__LOC__ + "Lag 2, slot 2" + true + (is_attested t ~lag_index:2 2) + in + let* () = + assert_equal_bool + ~loc:__LOC__ + "Lag 3, slot 3" + true + (is_attested t ~lag_index:3 3) + in + + return_unit + +(** Test edge cases: first and last lag, first and last slot *) +let test_edge_cases () = + let open Lwt_result_wrap_syntax in + let t = Dal_attestations_repr.empty in + + (* Test first lag, first slot *) + let t = commit t ~lag_index:0 0 in + let* () = + assert_equal_bool + ~loc:__LOC__ + "First lag, first slot" + true + (is_attested t ~lag_index:0 0) + in + + (* Test last lag, last slot *) + let t = commit t ~lag_index:(number_of_lags - 1) (number_of_slots - 1) in + let* () = + assert_equal_bool + ~loc:__LOC__ + "Last lag, last slot" + true + (is_attested t ~lag_index:(number_of_lags - 1) (number_of_slots - 1)) + in + + (* Test first lag, last slot *) + let t = commit t ~lag_index:0 (number_of_slots - 1) in + let* () = + assert_equal_bool + ~loc:__LOC__ + "First lag, last slot" + true + (is_attested t ~lag_index:0 (number_of_slots - 1)) + in + + (* Test last lag, first slot *) + let t = commit t ~lag_index:(number_of_lags - 1) 0 in + let* () = + assert_equal_bool + ~loc:__LOC__ + "Last lag, first slot" + true + (is_attested t ~lag_index:(number_of_lags - 1) 0) + in + + return_unit + +(** Test many slots attested at same lag (exercises fast path extensively) *) +let test_many_slots_same_lag () = + let open Lwt_result_wrap_syntax in + let t = Dal_attestations_repr.empty in + + (* Attest slots 0, 2, 4, 6, ... (even slots) at lag 2 *) + let t = + List.fold_left + (fun acc slot_idx -> commit acc ~lag_index:2 slot_idx) + t + (List.filter (fun x -> x mod 2 = 0) (0 -- (number_of_slots - 1))) + in + + (* Verify even slots are attested *) + let* () = + List.iter_es + (fun slot_idx -> + let expected = slot_idx mod 2 = 0 in + let attested = is_attested t ~lag_index:2 slot_idx in + assert_equal_bool + ~loc:__LOC__ + (Printf.sprintf "Slot %d at lag 2" slot_idx) + expected + attested) + (0 -- (number_of_slots - 1)) + in + + (* Verify lag 2 doesn't affect other lags *) + let* () = + List.iter_es + (fun lag_idx -> + if lag_idx <> 2 then + let attested = is_attested t ~lag_index:lag_idx 0 in + assert_equal_bool + ~loc:__LOC__ + (Printf.sprintf "Slot 0 at lag %d should be empty" lag_idx) + false + attested + else return_unit) + (0 -- (number_of_lags - 1)) + in + + return_unit + +(** Test size calculation *) +let test_size_calculation () = + let open Lwt_result_wrap_syntax in + (* Empty bitset should be small *) + let t_empty = Dal_attestations_repr.empty in + let size_empty = Dal_attestations_repr.occupied_size_in_bits t_empty in + let* () = + Assert.equal + ~loc:__LOC__ + Int.equal + "Empty size" + Format.pp_print_int + 0 + size_empty + in + + (* Expected max size *) + let expected_max = + Dal_attestations_repr.expected_max_size_in_bits + ~number_of_slots + ~number_of_lags + in + let* () = + Assert.equal + ~loc:__LOC__ + Int.equal + "Expected max size" + Format.pp_print_int + (number_of_lags * (1 + number_of_slots)) + expected_max + in + + (* Create attestations and check size grows *) + let t = commit t_empty ~lag_index:1 5 in + let size_one = Dal_attestations_repr.occupied_size_in_bits t in + let* () = + if size_one > size_empty then return_unit + else + failwith + "Size should grow after first commit: %d <= %d" + size_one + size_empty + in + + (* Add more attestations *) + let t = commit t ~lag_index:2 10 in + let size_two = Dal_attestations_repr.occupied_size_in_bits t in + let* () = + if size_two > size_one then return_unit + else + failwith + "Size should grow after second commit: %d <= %d" + size_two + size_one + in + + return_unit + +(** Test complex pattern: interleaved lags and slots. + The commits are shuffled to test the slow path (inserting attestations + in the middle of the bitset, which requires shifting existing data). *) +let test_complex_pattern () = + let open Lwt_result_wrap_syntax in + let t = Dal_attestations_repr.empty in + + (* Build a complex pattern: + - Lag 0: slots 1, 3, 5 + - Lag 1: slot 10 + - Lag 2: empty + - Lag 3: slots 0, 15, 31 + + Order is shuffled to exercise the slow path: inserting lag 0 after lag 3 + exists forces shifting lag 3's data, and inserting lag 1 between them + forces another shift. *) + let t = commit t ~lag_index:3 15 in + let t = commit t ~lag_index:0 5 in + let t = commit t ~lag_index:0 1 in + let t = commit t ~lag_index:3 0 in + let t = commit t ~lag_index:1 10 in + let t = commit t ~lag_index:0 3 in + let t = commit t ~lag_index:3 31 in + + (* Verify the pattern *) + let check_slot lag slot expected = + let attested = is_attested t ~lag_index:lag slot in + assert_equal_bool + ~loc:__LOC__ + (Printf.sprintf "Lag %d, slot %d" lag slot) + expected + attested + in + + let* () = check_slot 0 1 true in + let* () = check_slot 0 3 true in + let* () = check_slot 0 5 true in + let* () = check_slot 0 0 false in + let* () = check_slot 0 2 false in + let* () = check_slot 1 10 true in + let* () = check_slot 1 0 false in + let* () = check_slot 2 0 false in + let* () = check_slot 2 10 false in + let* () = check_slot 3 0 true in + let* () = check_slot 3 15 true in + let* () = check_slot 3 31 true in + let* () = check_slot 3 1 false in + + return_unit + +let tests = + [ + Tztest.tztest "example encoding from interface" `Quick test_example_encoding; + Tztest.tztest "empty attestations" `Quick test_empty; + Tztest.tztest "commit is idempotent" `Quick test_commit_idempotent; + Tztest.tztest "encoding roundtrip" `Quick test_encoding_roundtrip; + Tztest.tztest + "update existing attestation (fast path)" + `Quick + test_update_existing_attestation; + Tztest.tztest + "multiple lag attestations" + `Quick + test_multiple_lag_attestations; + Tztest.tztest "edge cases" `Quick test_edge_cases; + Tztest.tztest "many slots at same lag" `Quick test_many_slots_same_lag; + Tztest.tztest "size calculation" `Quick test_size_calculation; + Tztest.tztest "complex pattern" `Quick test_complex_pattern; + ] + +let () = + Alcotest_lwt.run ~__FILE__ Protocol.name [("dal attestations repr", tests)] + |> Lwt_main.run -- GitLab