package tezos-protocol-017-PtNairob

You can search for identifiers within the package.
in-package search v0.2.0
tezos-protocol-017-PtNairob
Legend:
Page
Library
Module
Module type
Parameter
Class
Class type
Source
Source file `dal_attestation_repr.ml`

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
(*****************************************************************************)
(*                                                                           *)
(* Open Source License                                                       *)
(* Copyright (c) 2022 Nomadic Labs <contact@nomadic-labs.com>                *)
(*                                                                           *)
(* Permission is hereby granted, free of charge, to any person obtaining a   *)
(* copy of this software and associated documentation files (the "Software"),*)
(* to deal in the Software without restriction, including without limitation *)
(* the rights to use, copy, modify, merge, publish, distribute, sublicense,  *)
(* and/or sell copies of the Software, and to permit persons to whom the     *)
(* Software is furnished to do so, subject to the following conditions:      *)
(*                                                                           *)
(* The above copyright notice and this permission notice shall be included   *)
(* in all copies or substantial portions of the Software.                    *)
(*                                                                           *)
(* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR*)
(* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,  *)
(* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL   *)
(* THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER*)
(* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING   *)
(* FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER       *)
(* DEALINGS IN THE SOFTWARE.                                                 *)
(*                                                                           *)
(*****************************************************************************)

(* DAL/FIXME https://gitlab.com/tezos/tezos/-/issues/3103

   This may be a bit heavy in practice. We could also assume that in
   practice, many bits in this bitfield will be set to one. Hence, we
   could consider a better encoding which is smaller in the optimistic
   case. For example:

   1. When all the slots are attested, the encoding can be represented
   in one bit.

   2. Otherwise, we can pack slots by [8]. Have a header of [slots/8]
   which is [1] if all the slots in this set are [1], [0]
   otherwise. For all pack with a bit set to [0], we give the explicit
   representation. Hence, if there are [256] slots, and [2] are not
   attested, this representation will be of size [32] bits + [16] bits
   = [48] bits which is better than [256] bits. *)

(* A set of (attested) slot indexes. *)
type t = Bitset.t

type operation = {
  attestor : Signature.Public_key_hash.t;
      (* FIXME/DAL: https://gitlab.com/tezos/tezos/-/issues/4165
         Compute the endorser from the attested slots in [slot_attestation] below,
         or provide a field `min_endorser_slot : int / int32` *)
  attestation : t;
  level : Raw_level_repr.t;
}

let encoding = Bitset.encoding

let empty = Bitset.empty

let is_attested t index =
  let open Dal_slot_index_repr in
  match Bitset.mem t (to_int index) with
  | Ok b -> b
  | Error _ ->
      (* DAL/FIXME https://gitlab.com/tezos/tezos/-/issues/3104

         Should we do something here? *)
      false

let commit t index =
  let open Dal_slot_index_repr in
  match Bitset.add t (to_int index) with
  | Ok t -> t
  | Error _ ->
      (* DAL/FIXME https://gitlab.com/tezos/tezos/-/issues/3104

         Should we do something here? *)
      t

let occupied_size_in_bits = Bitset.occupied_size_in_bits

let expected_size_in_bits ~max_index =
  (* We compute an encoding of the data-availability attestations
     which is a (tight) upper bound of what we expect. *)
  let open Bitset in
  let open Dal_slot_index_repr in
  match add empty @@ to_int max_index with
  | Error _ -> (* Happens if max_index < 1 *) 0
  | Ok t -> occupied_size_in_bits t

type shard_index = int

module Shard_map = Map.Make (struct
  type t = shard_index

  let compare = Compare.Int.compare
end)

module Accountability = struct
  type attested_slots = t

  (* DAL/FIXME https://gitlab.com/tezos/tezos/-/issues/3109

     Think hard about this data structure and whether it needs to be
     optimized.
  *)

  (* A list of set of shard indexes (a set of shards per slot) *)
  type t = Bitset.t list

  let init ~length =
    let l =
      List.init
        ~when_negative_length:
          "Dal_attestation_repr.Accountability.init: length cannot be negative"
        length
        (fun _ -> Bitset.empty)
    in
    match l with Error msg -> invalid_arg msg | Ok l -> l

  let record_slot_shard_availability bitset shards =
    List.fold_left
      (fun bitset shard ->
        Bitset.add bitset shard |> Result.value ~default:bitset)
      bitset
      shards

  let record_attested_shards shard_bitset_per_slot attested_slots shards =
    List.mapi
      (fun slot bitset ->
        match Bitset.mem attested_slots slot with
        | Error _ ->
            (* slot index is above the length provided at initialisation *)
            bitset
        | Ok slot_attested ->
            if slot_attested then record_slot_shard_availability bitset shards
            else bitset)
      shard_bitset_per_slot

  let is_slot_attested shard_bitset_per_slot ~threshold ~number_of_shards index
      =
    match List.nth shard_bitset_per_slot (Dal_slot_index_repr.to_int index) with
    | None -> false
    | Some bitset ->
        let acc = ref 0 in
        List.iter
          (fun x ->
            match Bitset.mem bitset x with
            | Error _ | Ok false -> ()
            | Ok true -> incr acc)
          Misc.(0 --> (number_of_shards - 1)) ;
        Compare.Int.(!acc >= threshold * number_of_shards / 100)
end
package tezos-protocol-017-PtNairob

Source file dal_attestation_repr.ml

Source file `dal_attestation_repr.ml`
