diff --git a/src/lib_base/tzPervasives.ml b/src/lib_base/tzPervasives.ml index c30f7071e408ee179ba008f7210c8d26f76ed366..c20fac1778f2ef126c7dfa2e0c3ce7c4efa9c0a0 100644 --- a/src/lib_base/tzPervasives.ml +++ b/src/lib_base/tzPervasives.ml @@ -78,3 +78,5 @@ module Filename = struct include Stdlib.Filename include Tezos_stdlib.TzFilename end + +module Bounded = Bounded diff --git a/src/lib_base/tzPervasives.mli b/src/lib_base/tzPervasives.mli index a8e03c4bdffc1146594ebc26248f50f321dea56d..04703beaae8c221850c7626b683c88e8ae04b049 100644 --- a/src/lib_base/tzPervasives.mli +++ b/src/lib_base/tzPervasives.mli @@ -115,3 +115,5 @@ module Filename : sig val ( // ) : string -> string -> string end end + +module Bounded = Bounded diff --git a/src/lib_protocol_environment/environment_V5.ml b/src/lib_protocol_environment/environment_V5.ml index 72759b5dda4f0ba9fe86e1eff2ae04c304848f92..3efbcf2ab917363fe10db28e407b2afa41537b76 100644 --- a/src/lib_protocol_environment/environment_V5.ml +++ b/src/lib_protocol_environment/environment_V5.ml @@ -757,6 +757,7 @@ struct module Fitness = Fitness module Operation = Operation module Block_header = Block_header + module Bounded = Bounded module Protocol = Protocol module RPC_arg = RPC_arg module RPC_path = RPC_path diff --git a/src/lib_protocol_environment/sigs/v5.dune.inc b/src/lib_protocol_environment/sigs/v5.dune.inc index 77291a7bcf9b77c0f15a9ca62115e043c8575792..38f63711f9a2d36b39b82f98a55ae639e1701176 100644 --- a/src/lib_protocol_environment/sigs/v5.dune.inc +++ b/src/lib_protocol_environment/sigs/v5.dune.inc @@ -70,12 +70,14 @@ v5/micheline.mli v5/block_header.mli + v5/bounded.mli v5/fitness.mli v5/operation.mli v5/protocol.mli v5/context.mli v5/updater.mli v5/RPC_context.mli + ) (action (with-stdout-to %{targets} (chdir %{workspace_root}} (run %{libexec:tezos-protocol-environment-packer:s_packer} "sigs" %{deps}))))) diff --git a/src/lib_protocol_environment/sigs/v5/bounded.mli b/src/lib_protocol_environment/sigs/v5/bounded.mli new file mode 100644 index 0000000000000000000000000000000000000000..46539808d0884e20c02aa453b83a4f157c4de1e4 --- /dev/null +++ b/src/lib_protocol_environment/sigs/v5/bounded.mli @@ -0,0 +1,70 @@ +(*****************************************************************************) +(* *) +(* Open Source License *) +(* Copyright (c) 2022 Trili Tech, *) +(* *) +(* 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. *) +(* *) +(*****************************************************************************) + +(** This module implements bounded (or refined) versions of data types. *) + +(** Bounded [int32]. *) +module Int32 : sig + (** Bounds. + + Formally each [B : BOUND] represents the interval of all integers + between [B.min_int] and [B.max_int]. This is a closed interval, e.g. + the endpoints are included. + + Intervals can be empty, for example [struct let min_int = 1; let max_int + 0 end] is empty. + *) + module type BOUNDS = sig + val min_int : int32 + + val max_int : int32 + end + + module type S = sig + type t + + include BOUNDS + + include Compare.S with type t := t + + val encoding : t Data_encoding.t + + val to_int32 : t -> int32 + + val of_int32 : int32 -> t option + end + + (** Produce a module [_ : S] of bounded integers. + + If the given interval is empty, [S.t] is the empty type, and [of_int32] + returns [Error] for all inputs. + + {4 Encoding} + [(Make B).encoding] is based on the underlying [int32] encoding. This + allow future compatiblity with larger bounds, at the price of addding 1-3 + redundant bytes to each message. + *) + module Make (_ : BOUNDS) : S +end diff --git a/src/proto_alpha/lib_protocol/sc_rollup_repr.ml b/src/proto_alpha/lib_protocol/sc_rollup_repr.ml index 3abbbbc164ede1441a646c56e1720d89247c8a0c..1c2048a2d58f6274af8f210b6add20d52e2e4c1f 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_repr.ml +++ b/src/proto_alpha/lib_protocol/sc_rollup_repr.ml @@ -2,6 +2,7 @@ (* *) (* Open Source License *) (* Copyright (c) 2021 Nomadic Labs *) +(* Copyright (c) 2022 Trili Tech, *) (* *) (* Permission is hereby granted, free of charge, to any person obtaining a *) (* copy of this software and associated documentation files (the "Software"),*) @@ -79,6 +80,64 @@ module Address = struct | Some nonce -> ok @@ hash_bytes [nonce] end +(* 32 *) +let commitment_hash_prefix = "\017\144\021\100" (* scc1(54) *) + +module Commitment_hash = struct + let prefix = "scc1" + + let encoded_size = 54 + + module H = + Blake2B.Make + (Base58) + (struct + let name = "commitment_hash" + + let title = "The hash of a commitment of a smart contract rollup" + + let b58check_prefix = commitment_hash_prefix + + (* defaults to 32 *) + let size = None + end) + + include H + + let () = Base58.check_encoded_prefix b58check_encoding prefix encoded_size + + include Path_encoding.Make_hex (H) +end + +(* 32 *) +let state_hash_prefix = "\017\144\122\202" (* scs1(54) *) + +module State_hash = struct + let prefix = "scs1" + + let encoded_size = 54 + + module H = + Blake2B.Make + (Base58) + (struct + let name = "state_hash" + + let title = "The hash of the VM state of a smart contract rollup" + + let b58check_prefix = state_hash_prefix + + (* defaults to 32 *) + let size = None + end) + + include H + + let () = Base58.check_encoded_prefix b58check_encoding prefix encoded_size + + include Path_encoding.Make_hex (H) +end + type t = Address.t let description = @@ -154,6 +213,69 @@ module Index = struct let compare = Address.compare end +module Commitment_hash_index = struct + include Commitment_hash +end + +module Number_of_messages = Bounded.Int32.Make (struct + let min_int = 1l + + let max_int = 4096l + (* TODO: check this is reasonable. + See https://gitlab.com/tezos/tezos/-/issues/2373 + *) +end) + +module Number_of_ticks = Bounded.Int32.Make (struct + let min_int = 1l + + let max_int = Int32.max_int +end) + +module Commitment = struct + type t = { + compressed_state : State_hash.t; + inbox_level : Raw_level_repr.t; + predecessor : Commitment_hash.t; + number_of_messages : Number_of_messages.t; + number_of_ticks : Number_of_ticks.t; + } + + let encoding = + let open Data_encoding in + conv + (fun { + compressed_state; + inbox_level; + predecessor; + number_of_messages; + number_of_ticks; + } -> + ( compressed_state, + inbox_level, + predecessor, + number_of_messages, + number_of_ticks )) + (fun ( compressed_state, + inbox_level, + predecessor, + number_of_messages, + number_of_ticks ) -> + { + compressed_state; + inbox_level; + predecessor; + number_of_messages; + number_of_ticks; + }) + (obj5 + (req "compressed_state" State_hash.encoding) + (req "inbox_level" Raw_level_repr.encoding) + (req "predecessor" Commitment_hash.encoding) + (req "number_of_messages" Number_of_messages.encoding) + (req "number_of_ticks" Number_of_ticks.encoding)) +end + module Kind = struct (* diff --git a/src/proto_alpha/lib_protocol/sc_rollup_repr.mli b/src/proto_alpha/lib_protocol/sc_rollup_repr.mli index df68d4559e6f64010490353a978a6fb4b3593ad7..b466ec58e0d1f3eabd7c0fff42998311210a121b 100644 --- a/src/proto_alpha/lib_protocol/sc_rollup_repr.mli +++ b/src/proto_alpha/lib_protocol/sc_rollup_repr.mli @@ -2,6 +2,7 @@ (* *) (* Open Source License *) (* Copyright (c) 2021 Nomadic Labs *) +(* Copyright (c) 2022 Trili Tech, *) (* *) (* Permission is hereby granted, free of charge, to any person obtaining a *) (* copy of this software and associated documentation files (the "Software"),*) @@ -59,6 +60,59 @@ module Address : sig val encoded_size : int end +module Commitment_hash : S.HASH + +module State_hash : S.HASH + +(** Number of messages consumed by a single commitment. This represents a claim + about the shape of the Inbox, which can be disputed as part of a commitment + dispute. + + See also {!Sc_rollup_repr.Commitments}. *) +module Number_of_messages : Bounded.Int32.S + +(** Number of ticks computed by a single commitment. This represents a claim + about the state of the PVM, which can be disputed as part of a commitment + dispute. + + See also {!Sc_rollup_repr.Commitments}. *) +module Number_of_ticks : Bounded.Int32.S + +(** A commitment represents a claim about the state of the Inbox and PVM at + some Inbox level. + + More formally, a commitment is a claim that: + + {ul + {li assuming the PVM and Inbox are in a state implied by [predecessor]} + {li the PVM consumes [number_of_messages] messages tagged with + [inbox_level] from the Inbox} + {li the PVM advances to the state [compressed_state] over + [number_of_ticks] ticks } + } + + Commitments are disjoint. The next correct commitment is a function of the + previous machine state and Inbox. + + [number_of_messages] and [inbox_level] can be proven/disproven by Merkle + proofs on the Inbox state. + + [compressed_state] and [number_of_ticks] can be proven/disproven by PVM + execution, or equivalently, by an interactive proof game between + conflicting parties, such that a correct executor always wins the game. + *) +module Commitment : sig + type t = { + compressed_state : State_hash.t; + inbox_level : Raw_level_repr.t; + predecessor : Commitment_hash.t; + number_of_messages : Number_of_messages.t; + number_of_ticks : Number_of_ticks.t; + } + + val encoding : t Data_encoding.t +end + (** A smart contract rollup is identified by its address. *) type t = Address.t @@ -69,6 +123,9 @@ val rpc_arg : t RPC_arg.t (** The data model uses an index of these addresses. *) module Index : Storage_description.INDEX with type t = Address.t +module Commitment_hash_index : + Storage_description.INDEX with type t = Commitment_hash.t + (** A smart contract rollup has a kind, which assigns meaning to rollup operations. *) module Kind : sig diff --git a/src/proto_alpha/lib_protocol/storage.ml b/src/proto_alpha/lib_protocol/storage.ml index 2efcd3ecf75026aec196c2c5ea91c18321dd9849..42bedac53bfa5a8ff01df4b8ba4d1993d995ad04 100644 --- a/src/proto_alpha/lib_protocol/storage.ml +++ b/src/proto_alpha/lib_protocol/storage.ml @@ -2,6 +2,7 @@ (* *) (* Open Source License *) (* Copyright (c) 2018 Dynamic Ledger Solutions, Inc. *) +(* Copyright (c) 2022 Trili Tech, *) (* *) (* Permission is hereby granted, free of charge, to any person obtaining a *) (* copy of this software and associated documentation files (the "Software"),*) @@ -1703,14 +1704,6 @@ module Sc_rollup = struct end)) (Make_index (Sc_rollup_repr.Index)) - (** - - Each smart contract rollup is associated to: - - - a PVM kind (provided at creation time, read-only) ; - - a boot sector (provided at creation time, read-only). - - a merkelized inbox, of which only the root hash is stored - *) module PVM_kind = Indexed_context.Make_map (struct @@ -1743,4 +1736,65 @@ module Sc_rollup = struct let encoding = Sc_rollup_inbox.encoding end) + + module Last_final_commitment = + Indexed_context.Make_carbonated_map + (struct + let name = ["last_final_commitment"] + end) + (struct + type t = Sc_rollup_repr.Commitment_hash.t + + let encoding = Sc_rollup_repr.Commitment_hash.encoding + end) + + module Stakers = + Make_indexed_carbonated_data_storage + (Make_subcontext (Registered) (Indexed_context.Raw_context) + (struct + let name = ["stakers"] + end)) + (Public_key_hash_index) + (struct + type t = Sc_rollup_repr.Commitment_hash.t + + let encoding = Sc_rollup_repr.Commitment_hash.encoding + end) + + module Stakers_size = + Indexed_context.Make_carbonated_map + (struct + let name = ["stakers_size"] + end) + (struct + type t = int32 + + let encoding = Data_encoding.int32 + end) + + module Commitments = + Make_indexed_carbonated_data_storage + (Make_subcontext (Registered) (Indexed_context.Raw_context) + (struct + let name = ["commitments"] + end)) + (Make_index (Sc_rollup_repr.Commitment_hash_index)) + (struct + type t = Sc_rollup_repr.Commitment.t + + let encoding = Sc_rollup_repr.Commitment.encoding + end) + + module Commitment_stake_count = + Make_indexed_carbonated_data_storage + (Make_subcontext (Registered) (Indexed_context.Raw_context) + (struct + let name = ["commitment_stake_count"] + end)) + (Make_index (Sc_rollup_repr.Commitment_hash_index)) + (struct + type t = int32 + + let encoding = Data_encoding.int32 + end) end diff --git a/src/proto_alpha/lib_protocol/storage.mli b/src/proto_alpha/lib_protocol/storage.mli index 3f7fa305e9be3958fc8fe1dae680a83fa525baff..dc951ca6a4875fbe159c2f4cb7ff6ab137e12752 100644 --- a/src/proto_alpha/lib_protocol/storage.mli +++ b/src/proto_alpha/lib_protocol/storage.mli @@ -2,6 +2,7 @@ (* *) (* Open Source License *) (* Copyright (c) 2018 Dynamic Ledger Solutions, Inc. *) +(* Copyright (c) 2022 Trili Tech, *) (* *) (* Permission is hereby granted, free of charge, to any person obtaining a *) (* copy of this software and associated documentation files (the "Software"),*) @@ -732,15 +733,26 @@ module Tx_rollup : sig 'a Lwt.t end -(** Smart contract rollup *) module Sc_rollup : sig - (** + (** Smart contract rollup. - Each smart contract rollup is associated to: + Storage from this submodule must only be accessed through the + module `Sc_rollup_storage`. - - a PVM kind (provided at creation time, read-only) ; - - a boot sector (provided at creation time, read-only). - - a merkelized inbox, of which only the root hash is stored + Each smart contract rollup is associated to: + + - a PVM kind (provided at creation time, read-only) + - a boot sector (provided at creation time, read-only) + - a merkelized inbox, of which only the root hash is stored + - a tree of commitments, rooted at the last finalized commitment + - a map from stakers to commitments + + For performance reasons we also store (per rollup): + + - the total number of active stakers; + - the number of stakers per commitment. + + See module comments for details. *) module PVM_kind : Indexed_data_storage @@ -759,4 +771,60 @@ module Sc_rollup : sig with type key = Sc_rollup_repr.t and type value = Sc_rollup_inbox.t and type t := Raw_context.t + + module Last_final_commitment : + Non_iterable_indexed_carbonated_data_storage + with type key = Sc_rollup_repr.t + and type value = Sc_rollup_repr.Commitment_hash.t + and type t := Raw_context.t + + module Stakers : + Non_iterable_indexed_carbonated_data_storage + with type key = Signature.Public_key_hash.t + and type value = Sc_rollup_repr.Commitment_hash.t + and type t = Raw_context.t * Sc_rollup_repr.t + + (** Cache: This should always be the size of [Stakers]. + + Combined with {!Commitment_stake_count} (see below), this ensures we can + check that all stakers agree on a commitment prior to finalization in + O(1) - rather than O(n) reads. + *) + module Stakers_size : + Non_iterable_indexed_carbonated_data_storage + with type key = Sc_rollup_repr.t + and type value = int32 + and type t := Raw_context.t + + module Commitments : + Non_iterable_indexed_carbonated_data_storage + with type key = Sc_rollup_repr.Commitment_hash.t + and type value = Sc_rollup_repr.Commitment.t + and type t = Raw_context.t * Sc_rollup_repr.t + + (** Cache: This should always be the number of stakers that are directly or + indirectly staked on this commitment. + + Let Stakers[S] mean "looking up the key S in [Stakers]". + + A staker [S] is directly staked on [C] if [Stakers[S] = C]. A staker + [S] is indirectly staked on [C] if [C] is an ancestor of [Stakers[S]]. + + This ensures we remove unreachable commitments at the end of a + dispute in O(n) reads, where n is the length of the rejected branch. + + We maintain the invariant that each branch has at least one staker. On + rejection, we decrease stake count from the removed staker to the root, + and reclaim commitments whose stake count (refcount) thus reaches zero. + + In the worst case all commitments are dishonest and on the same branch. + In practice we expect the honest branch, to be the longest, and dishonest + branches to be of similar lengths, making removal require a small number + of steps with respect to the total number of commitments. + *) + module Commitment_stake_count : + Non_iterable_indexed_carbonated_data_storage + with type key = Sc_rollup_repr.Commitment_hash.t + and type value = int32 + and type t = Raw_context.t * Sc_rollup_repr.t end