This document describes the Move specification language (MSL), a subset of the Move language that supports specification of the behavior of Move programs. MSL works together with the Move Prover, a tool that can statically verify the correctness of MSL specifications against Move programs. In contrast to traditional testing, verification of MSL is exhaustive and holds for all possible inputs and global states of a Move module or Move script. At the same time, this verification of MSL is fast and automated enough that it can be used at a similar place in the developer workflow where tests are typically conducted (for example, for qualification of pull requests in continuous integration).
While the Move programming language at this point is stable, the subset represented by MSL should be considered evolving. This has no impact on platform stability, since MSL is not running in production; yet MSL is used for offline quality assurance where it is continuously improved for evolving objectives.
This document describes the language only; see Use the Move Prover for instructions. The reader is expected to have basic knowledge of the Move language, as well as basic principles of pre- and post-condition specifications. (See for example the Design by contract). For examples of specifications, we refer to the Aptos framework documentation, which has specifications embedded.
Expressions
Expressions in MSL are a subset of Move program expressions plus a set of additional constructs, as discussed in the following sections.
Type System
The type system of MSL is similar to that of Move, with the following differences:
- There are two types of encodings for integer types:
num
andbv
(bit vector). If an integer (either a constant or a variable) is not involved in any bitwise operations directly or indirectly, regardless of its type in Move (u8
,u16
,u32
,u64
,u128
andu256
), it is treated as the same type. In specifications, this type is callednum
, which is an arbitrary precision signed integer type. When MSL refers to a Move name that represents anu8
or such, it will be automatically widened tonum
. This allows writing MSL expressions likex + 1 <= MAX_U128
orx - y >= 0
without needing to worry about overflow or underflow. Different fromnum
,bv
cannot and does not need to be explicitly used in specifications: if an integer is involved in bitwise operations such as&
,|
or^
, it will be automatically encoded asbv
at the backend. Moreover, abv
integer has a fixed precision, which is consistent with its precision in Move (bv8
,bv16
,bv32
,bv64
,bv128
andbv256
). Note that, in general usingbv
is not so efficient asnum
in the SMT solver such as Z3. Consequently, the Move Prover has some restrictions when using bitwise operations, which are stated in detail below. - The Move types
&T
,&mut T
, andT
are considered equivalent for MSL. Equality is interpreted as value equality. There is no need to worry about dereferencing a reference from the Move program: these are automatically dereferenced as needed. This simplification is possible because MSL cannot modify values from a Move program, and the program cannot directly reason about reference equality (which eliminates the need for doing so in MSL). (Note there is also a restriction in expressiveness coming with this, namely for functions which return&mut T
. However, this is rarely hit in practice, and there are workarounds.) - There is the additional type
type
, which is the type of all types. It can be used only in quantifiers. - There is the additional type
range
, which represents an integer range (and the notationn..m
to denote a value).
Naming
Name resolution in MSL works similar to the Move language. use
declarations can introduce aliases for
imported names. MSL functions and variable names must start with a lowercase letter. Schema names
are treated like types and must start with a capital letter. (Schemas are a named construct
discussed later).
Move functions, MSL functions, Move types, and schemas all share the same namespace and are
therefore unambiguous if aliased via a Move use
clause. Because of the common name space, an MSL
function cannot have the same name as a Move function. This is often handled via the convention to
prefix MSL functions as in spec_has_access
when the related Move function is called has_access
.
Operators
All Move operators are supported in MSL, except &
, &mut
, and *
(dereference).
In addition to the existing operators, vector subscript v[i]
, slicing v[i..j]
, and range
construction i..j
are supported (the type of integer ranges is a new builtin type called range
). Moreover, boolean implication p ==> q
is supported as a more intuitive form than !p || q
.
Function calls
In MSL expressions, functions can be called like in Move. However, the callee must either be an MSL helper function or a pure Move function.
Move functions are considered pure if they do not modify global state and do not use Move expression features that are not supported in MSL expressions (as defined in this document).
There is one extension. If a Move function definition contains a direct assert
, this will be
ignored when it is called from an MSL expression, and the function will be considered pure. For
example:
fun get(addr: address): &T { assert(exists<T>(addr), ERROR_CODE); borrow_global<T>(addr) }
This function is pure and can be called from an MSL expression. The assertion will be ignored, and the function will be interpreted as:
spec fun get(addr: address): T { global<T>(addr) }
This is justified by that MSL having partial semantics.
Statements
Limited sequencing of the form { let x = foo(); x + x }
is supported, as well as if-then-else.
Other statement forms of the Move language are not supported.
Pack and unpack
Pack expressions are supported. Unpack expressions are currently not supported.
Quantifiers
Universal and existential quantification is supported. The general form is:
forall <binding>, ..., <binding> [ where <exp> ] : <exp>
exists <binding>, ..., <binding> [ where <exp> ] : <exp>
- Bindings can either be of the form
name: <type>
orname in <exp>
. For the second form, the expression must either be arange
or a vector. - The optional constraint
where <exp>
allows to restrict the quantified range.forall x: T where p: q
is equivalent toforall x: T : p ==> q
andexists x: T where p: q
is equivalent toexists x: T : p && q
.
Notice that it is possible to quantify over types. For example:
forall t: type, addr: address where exists<R<t>>(addr): exists<T<t>>(addr)
Choice operator
The choice operator allows selecting a value that satisfies a predicate:
choose a: address where exists<R>(a) && global<R>(a).value > 0
If the predicate is not satisfiable, the result of the choice will be undetermined. (See partial semantics).
The choice also comes in a form to select the minimal value from a set of integers, as in:
choose min i: num where in_range(v, i) && v[i] == 2
Cast operator
In the specification language, we can use the same syntax (e as T)
to cast an expression e
with one integer type to T
, an integer type of another size.
Shift operator
Shift operators <<
and >>
are supported in the specification language, and both of them have the same semantics with the Move language. As for abort, if a value v
has width n
, then v << m
or v >> m
will abort if m >= n
.
Bitwise operators
Move programs using bitwise operators &
, |
and ^
can be verified in the prover, and these operators are also supported in the specification language.
Due to encoding and efficiency issues, using bitwise operators has more caveats:
-
Integers involved in bitwise operations are encoded as
bv
types at the backend, and two encodings of integers are not compatible. For instance, if a variablev
is involved in a bitwise operation such asv & 2
orv = a ^ b
, then when it is used in an arithmetic operationv * w
or a shift operationv << w
,w
will be implicitly cast to abv
type in the Move program. However, the specification language does not support implicit type cast so users must explicitly use the built-in functionint2bv
in the specification:v << int2bv(w)
. Not that since eachbv
type has a fixed length (from 8 to 256), values with typenum
cannot be converted intobv
. -
Verification of
bv
types is not efficient and may lead to timeout. As a result, users may prefer isolating bitwise operations from other operations and not usingint2bv
if possible. Moreover, users need to use pragmas to explicitly specify which integer-typed function arguments or struct fields will be used in bitwise computations:
struct C has drop {
a: u64,
b: u64
}
spec C {
// b, the second field of C, will be of bv type
pragma bv=b"1";
}
public fun foo_generic<T>(i: T): T {
i
}
spec foo_generic {
// The first parameter will be of bv type if T is instantiated as a number type
pragma bv=b"0";
// The first return value will be of bv type if T is instantiated as a number type
pragma bv_ret=b"0";
}
public fun test(i: C): u64 {
let x1 = foo_generic(C.b);
x1 ^ x1
}
spec test {
// Explicit type cast is mandatory for generating correct boogie program
ensures result == (0 as u64);
}
Note that if arguments or fields of a generic function or struct are specified with bv
types,
they will be of bv
types in all instances of the function or the struct when the instantiated type is an integer type.
- Values with integer types in vectors and tables can be encoded as
bv
types; indices and keys in tables cannot bebv
types for now. Using other types will lead to internal errors.
Built-in functions
MSL supports a number of built-in constants and functions. Most of them are not available in the Move language:
MAX_U8: num
,MAX_U64: num
,MAX_U128: num
returns the maximum value of the corresponding type.exists<T>(address): bool
returns true if the resource T exists at address.global<T>(address): T
returns the resource value at address.len<T>(vector<T>): num
returns the length of the vector.update<T>(vector<T>, num, T>): vector<T>
returns a new vector with the element replaced at the given index.vec<T>(): vector<T>
returns an empty vector.vec<T>(x): vector<T>
returns a singleton vector.concat<T>(vector<T>, vector<T>): vector<T>
returns the concatenation of the parameters.contains<T>(vector<T>, T): bool
returns true if element is in vector.index_of<T>(vector<T>, T): num
returns the index of the element in the vector, or the length of the vector if it does not contain it.range<T>(vector<T>): range
returns the index range of the vector.in_range<T>(vector<T>, num): bool
returns true if the number is in the index range of the vector.in_range<T>(range, num): bool
returns true if the number is in the range.update_field(S, F, T): S
updates a field in a struct, preserving the values of other fields, whereS
is some struct,F
the name of a field inS
, andT
a value for this field.old(T): T
delivers the value of the passed argument at point of entry into a Move function. This is allowed inensures
post-conditions, inline spec blocks (with additional restrictions), and certain forms of invariants, as discussed later.TRACE(T): T
is semantically the identity function and causes visualization of the argument's value in error messages created by the prover.int2bv(v)
explicitly converts an integerv
into itsbv
representation.bv2int(b)
explicitly converts a 'bv' integer 'b' into thenum
representation. However, it is not encouraged to use it due to efficiency issue.
Built-in functions live in an unnamed outer scope of a module. If the module defines a function len
,
then this definition will shadow that of the according built-in function. To access the built-in
function in such a situation, one can use the notation ::len(v)
.
Partial semantics
In MSL, expressions have partial semantics. This is in contrast to Move program expressions, which have total semantics, since they either deliver a value or abort.
An expression e[X]
that depends on some variables X
may have a known interpretation for
some assignments to variables in X
but is unknown for others. An unknown interpretation for a
sub-expression causes no issue if its value is not needed for the overall expression result.
Therefore, it does not matter if we say y != 0 && x / y > 0
or x / y > 0 && y != 0
: boolean operators are commutative.
This basic principle inherits to higher-level language constructs. For example, in specifications,
it does not matter in which order conditions are supplied: aborts_if y != 0; ensures result == x / y;
is the same as
ensures result == x / y; aborts_if y != 0;
. Also, aborts_if P; aborts_if Q;
is the same
as aborts_if Q || P
.
Moreover, the principle of partial semantics is inherited to specification helper functions, which behave transparently. Specifically, inlining those functions is equivalent to calling them (call-by-expression parameter passing semantics).
Specifications
Specifications are contained in so-called specification blocks (abbreviated spec block) that can appear as module members and inside Move functions. The various types of spec blocks are shown below, and will be discussed in subsequent sections.
module addr::M {
struct Counter has key {
value: u8,
}
public fun increment(a: address) acquires Counter {
let r = borrow_global_mut<Counter>(a);
spec {
// spec block targeting this code position
...
};
r.value = r.value + 1;
}
spec increment {
// spec block targeting function increment
...
}
spec Counter {
// spec block targeting struct Counter
...
}
spec schema Schema {
// spec block declaring a schema
...
}
spec fun f(x: num): num {
// spec block declaring a helper function
...
}
spec module {
// spec block targeting the whole module
...
}
}
Apart from spec blocks inside Move functions, the textual position of spec block is irrelevant. Also, a spec block for a struct, function, or module can be repeated multiple times, accumulating the content.
Separating specifications
Instead of putting specifications into the same module as the regular Move definitions, one can also put them into a separate "specification" module, which can live in the same or a different file:
module addr::M {
...
}
spec addr::M {
spec increment { .. }
}
The syntax of a specification module is the same as for a regular module; however, Move functions and structures are not allowed.
A specification module must be compiled together with the Move module it is targeting and cannot be compiled and verified standalone.
In case Move definitions are far apart (e.g. in different files), it is possible to augment the specification of a Move function with a signature of this function to give sufficient context to understand the specification. This syntax is optionally enabled in regular and in specification modules:
public fun increment(a: address) acquires Counter { .. }
...
spec increment(a: address) { .. }
Pragmas and properties
Pragmas and properties are a generic mechanism to influence interpretation of specifications. They are also an extension point to experiment with new concepts before they become part of the mainstream syntax. Here we give a brief introduction into their general syntax; individual instances are discussed later.
The general form of a pragma is:
spec .. {
pragma <name> = <literal>;
}
The general form of a property is:
spec .. {
<directive> [<name> = <literal>] <content>; // ensures, aborts_if, include, etc..
}
The <literal>
can be any value supported by MSL (or the Move language). A value assignment can
also be omitted, in which case a default is used. For example, it is common to use pragma option;
as a shortcut for pragma option = true;
.
Instead of a single pragma or property, a list can also be provided, as in invariant [global, isolated] P
.
Pragma inheritance
A pragma in a module spec block sets a value that applies to all other spec blocks in the module. A pragma in a function or struct spec block can override this value for the function or struct. Furthermore, the default value of some pragmas can be defined via the prover configuration.
As an example, we look at the verify
pragma. This pragma is used to turn verification on or off.
spec module {
pragma verify = false; // By default, do not verify specs in this module ...
}
spec increment {
pragma verify = true; // ... but do verify this function.
...
}
General pragmas and properties
A number of pragmas control general behavior of verification. Those are listed in the table below.
Name | Description |
---|---|
verify | Turns on or off verification. |
intrinsic | Marks a function to skip the Move implementation and use a prover native implementation. This makes a function behave like a native function even if it not so in Move. |
timeout | Sets a timeout (in seconds) for function or module. Overrides the timeout provided by command line flags. |
verify_duration_estimate | Sets an estimate (in seconds) for how long the verification of function takes. If the configured timeout is less than this value, verification will be skipped. |
seed | Sets a random seed for function or module. Overrides the seed provided by command line flags. |
The following properties control general behavior of verification:
Name | Description |
---|---|
[deactivated] | Excludes the associated condition from verification. |
Pre and post state
Multiple conditions in spec blocks work with a pre and post state, relating them to each other.
Function specifications are one example of this: in the ensures P
condition, the pre-state (at
function entry) and the post-state (at function exit) are related via the predicate P
. However,
the concept is more general and also applied for invariants, where the pre-state is before and
post-state after a global update.
In contexts where a pre/post-state is active, expressions are evaluated implicitly in the
post-state. To evaluate an expression in a pre-state, one uses the built-in function old(exp)
,
which evaluates its parameter in the pre-state and returns its value. It is important to understand
that every sub-expression in exp
is computed in the pre-state as well, including calls to helper
functions.
The 'state' in question here consists of assignments to global resource memory, as well as to any
parameters of the function of type &mut T
. Examples:
fun increment(counter: &mut u64) { *counter = *counter + 1 }
spec increment {
ensures counter == old(counter) + 1;
}
fun increment_R(addr: address) {
let r = borrow_global_mut<R>(addr);
r.value = r.value + 1;
}
spec increment_R {
ensures global<R>(addr).value == old(global<R>(addr).value) + 1;
}
Helper functions
MSL allows defining helper functions. Those functions can then be used in expressions.
Helper functions are defined using the following syntax:
spec fun exists_balance<Currency>(a: address): bool { exists<Balance<Currency>>(a) }
As seen in the example, helper functions can be generic. Moreover, they can access global state.
Definitions of helper functions are neutral regarding whether they apply to
a pre- or post-state. They are evaluated in the currently active state. For
instance, in order to see whether a balance existed in the pre-state, one
uses old(exists_balance<Currency>(a))
. Consequently, the expression old(..)
is not allowed
within the definition of a helper function.
Helper functions are partial functions; see the discussion of partial semantics.
Uninterpreted functions
A helper function can be defined as uninterpreted by simply omitting its body:
spec fun something(x: num): num;
An uninterpreted function is one of the prover is allowed to assign some arbitrary meaning to, as long as it is consistent within a given verification context. Uninterpreted functions are a useful tool for abstraction in specifications (see also abstract specifications).
Axioms
The meaning of helper functions can be further constrained by using axioms. Currently, axioms must be contained in module spec blocks:
spec module {
axiom forall x: num: something(x) == x + 1;
}
Axioms should be used with care as they can introduce unsoundness in the specification logic via
contradicting assumptions. The Move Prover supports a smoke test for detecting unsoundness via
the --check-inconsistency
flag.
Let bindings
A spec block can contain let bindings that introduce names for expressions:
fun get_R(account: signer): R { ... }
spec get_R {
let addr = signer::spec_address_of(account);
aborts_if addr != ROOT;
ensures result == global<R>(addr);
}
In a spec block that has a pre-state and post-state (like a function specification), the let name = e
form will evaluate e
in the pre-state. In order to evaluate an expression in the post-state, use let post name = e
. In the rhs expression of this form, one can use old(..)
to refer to the
pre-state.
Aborts_if condition
The aborts_if
condition is a spec block member that can appear only in a function context. It
specifies conditions under which the function aborts.
In the following example, we specify that the function increment
aborts if the Counter
resource
does not exist at address a
(recall that a
is the name of the parameter of increment
).
spec increment {
aborts_if !exists<Counter>(a);
}
If a function has more than one aborts_if
condition, those conditions are or-ed with each other.
The evaluation of the combined aborts condition (or-ed from each individual condition) depends on
the value of the pragma aborts_if_is_partial
. If this value is false (the default), the function
aborts if and only if the combined aborts condition is true. In this case, the above aborts
specification for increment
will lead to a verification error, since there are additional
situations where increment
can abort, namely if incrementing Counter.value
would lead to an
overflow. To fix this, the specification can be completed like this:
spec increment {
pragma aborts_if_is_partial = false; // This is the default, but added here for illustration.
aborts_if !exists<Counter>(a);
aborts_if global<Counter>(a).value == 255;
}
If the value of aborts_if_is_partial
is true, the combined aborts condition (the or-ed individual
conditions) only implies that the function aborts. Formally, if A
is the combined aborts condition, then
with aborts_if_is_partial = true
, we have A ==> function_aborts
; otherwise we have
A <==> function_aborts
. Therefore, the following does verify:
spec increment {
pragma aborts_if_is_partial = true;
aborts_if !exists<Counter>(a);
}
Note that there is a certain risk in setting
aborts_if_is_partial
to true, and best practice is to avoid it in specifications of public functions and Move scripts once those are considered finalized. This is because changing the code after finalization of the spec can add new (non-trivial, undesired) abort situations the original specification did not anticipate yet will nevertheless silently pass verification.
If no aborts condition is specified for a function, abort behavior is unspecified. The function may
or may not abort, and verification will not raise any errors, whether aborts_if_is_partial
is set
or not. In order to state that a function never aborts, use aborts_if false
. One can use the
pragma aborts_if_is_strict
to change this behavior; this is equivalent to an aborts_if false
being added to each function that does not have an explicit aborts_if
clause.
Aborts_if condition with code
The aborts_if
condition can be augmented with code:
fun get_value(addr: address): u64 {
aborts(exists<Counter>(addr), 3);
borrow_global<Counter>(addr).value
}
spec get_value {
aborts_if !exists<Counter>(addr) with 3;
}
It is a verification error if the above function does not abort with code 3
under the given
condition.
In order to specify a direct VM abort, one can use the special constant EXECUTION_FAILURE
:
fun get(addr: address): &Counter acquires Counter {
borrow_global<Counter>(addr)
}
spec get {
aborts_if !exists<Counter>(addr) with EXECUTION_FAILURE;
}
This same constant can be used for all other VM failures (division by zero, overflow, etc.).
Aborts_with condition
The aborts_with
condition allows specifying with which codes a function can abort, independent
under which condition. It is similar to a 'throws' clause in languages like Java.
fun get_one_off(addr: address): u64 {
aborts(exists<Counter>(addr), 3);
borrow_global<Counter>(addr).value - 1
}
spec get_one_off {
aborts_with 3, EXECUTION_FAILURE;
}
If the function aborts with any other or none of the specified codes, a verification error will be produced.
The aborts_with
condition can be combined with aborts_if
conditions. In this case, the aborts_with
specifies any other codes with which the function may abort, in addition to the ones given in the aborts_if
:
spec get_one_off {
aborts_if !exists<Counter>(addr) with 3;
aborts_with EXECUTION_FAILURE;
}
If this is not wanted, and the aborts_with
should be independent of aborts_if
, one can use the
property [check]
:
spec get_one_off {
aborts_if !exists<Counter>(addr) with 3;
aborts_if global<Counter>(addr) == 0 with EXECUTION_FAILURE;
aborts_with [check] 3, EXECUTION_FAILURE;
}
Requires condition
The requires
condition is a spec block member that postulates a pre-condition for a function. The
Move Prover will produce verification errors for functions that are called with violating
pre-conditions.
A requires
is different from an aborts_if
: in the latter case, the function can be called, and
any aborts it produces will be propagated to the caller context. In the requires
case, the Move Prover
will not allow the function to be called in the first place. Nevertheless, the function can still
be called at runtime if verification is skipped. Because of this, requires
are rare in Move
specifications, and aborts_if
are more common. Specifically, requires
should be avoided for public APIs.
An example of requires
is:
spec increment {
requires global<Counter>(a).value < 255;
}
Ensures condition
The ensures
condition postulates a post-condition for a function that must be satisfied when the
function terminates successfully (i.e. does not abort). The Move Prover will verify each ensures
to
this end.
An example for the ensures
condition is the following:
spec increment {
ensures global<Counter>(a) == old(global<Counter>(a)) + 1;
}
Within the expression for the ensures
condition, one can use the old
function, as discussed in
Pre and post state.
Modifies condition
The modifies
condition is used to provide permissions to a function to modify global storage. The
annotation itself comprises a list of global access expressions. It is specifically used together
with opaque function specifications.
struct S has key {
x: u64
}
fun mutate_at(addr: address) acquires S {
let s = borrow_global_mut<S>(addr);
s.x = 2;
}
spec mutate_at {
pragma opaque;
modifies global<S>(addr);
}
In general, a global access expression has the form global<type_expr>(address_expr)
. The
address-valued expression is evaluated in the pre-state of the annotated function.
fun read_at(addr: address): u64 acquires S {
let s = borrow_global<S>(addr);
s.x
}
fun mutate_S_test(addr1: address, addr2: address): bool acquires T {
assert(addr1 != addr2, 43);
let x = read_at(addr2);
mutate_at(addr1); // Note we are mutating a different address than the one read before and after
x == read_at(addr2)
}
spec mutate_S_test {
aborts_if addr1 == addr2;
ensures result == true;
}
In the function mutate_S_test
, the assertion in the spec block is expected to hold. A benefit of
the modifies specification on mutate_at
is that this assertion can be proved whether mutate_at
is inlined.
If the modifies annotation is omitted on a function, then that function is deemed to have all
possible permissions for those resources it may modify during its execution. The set of all
resources that may be modified by a function is obtained via an interprocedural analysis of the
code. In the example above, mutate_S_test
does not have a modifies specification and modifies
resource S
via the call to mutate_at
. Therefore, it is considered to have modified S
at any
possible address. Instead, if the programmer adds modifies global<S>(addr1)
to the specification of mutate_S_test
, then the call to mutate_at
is checked to make sure that
modify permissions granted to mutate_S_test
cover the permissions it grants to mutate_at
.
Invariant condition
The invariant condition can be applied on structs and on global level.
Function invariants
The invariant
condition on a function is simply a shortcut for a requires
and ensures
with the
same predicate.
Thus, the following spec block:
spec increment {
invariant global<Counter>(a).value < 128;
}
... is equivalent to:
spec increment {
requires global<Counter>(a).value < 128;
ensures global<Counter>(a).value < 128;
}
Struct invariants
When the invariant
condition is applied to a struct, it expresses a well-formedness property of
the struct data. Any instance of this struct that is currently not mutated will satisfy this
property (with exceptions as outlined below).
For example, we can postulate an invariant on our counter that it never must exceed the value of 127:
spec Counter {
invariant value < 128;
}
A struct invariant is checked by the Move Prover whenever the struct value is constructed (packed). While
the struct is mutated (e.g. via a &mut Counter
) the invariant does not hold (but see exception
below). In general, we consider mutation as an implicit unpack, and end of mutation as a pack.
The Move language semantics unambiguously identifies the point when mutation ends and starts. This follows from the borrow semantics of Move and includes mutation via an enclosing struct. (The mutation of an inner struct ends when the mutation of the root struct where mutation started ends.)
There is one exception to this rule. When a mutable reference to a struct declared in module M is passed into a public function of M which does by itself not return any other mutable reference (which could be borrowed from the input parameter), we treat this parameter as "packed". That means, on function entry, we will unpack it and on function exit we will pack again, enforcing the invariant. This reflects that in Move, struct data can be mutated only within the module that declares the struct; so for an outside caller of the public function, the mutable reference can actually not be mutated unless by calling public functions of module M again. It is a significant simplification of the verification problem to exploit this in the semantics.
Global invariants
A global invariant appears as a member of module. It can express a condition over the global state
of the Move program, as represented by resources stored in memory. For example, the below invariant
states that a Counter
resource stored at any given address can never be zero:
module addr::M {
invariant forall a: addr where exists<Counter>(a): global<Counter>(a).value > 0;
}
A global invariant is assumed to hold when data is read from the global state, and is asserted (and may fail to verify) at the moment the state is updated. For example, the below function will never abort with arithmetic underflow because the counter value is always greater than zero; however, it will create a verification error since the counter can drop to zero:
fun decrement_ad(addr: address) acquires Counter {
let counter = borrow_global_mut<Counter>(addr);
let new_value = counter.value - 1; // Will not abort because counter.value > 0
*counter.value = new_value; // Fails verification since value can drop to zero
}
Disabling invariants
There are times when a global invariant holds almost everywhere, except for a brief interval inside a function. In current Move code, this often occurs when something (e.g. an account) is being set up and several structs are published together. Almost everywhere, an invariant holds that all the structs are published or none of them are. But the code that publishes the structs must do so sequentially. While the structs are being published, there will be a point where some are published and others are not.
In order to verify invariants that hold except during small regions, there is a feature to allow users to disable invariants temporarily. Consider the following code fragment:
fn setup() {
publish1();
publish2();
}
}
where publish1
and publish2
publish two different structs, T1
and T2
at address a
.
module addr::M {
invariant [global] exists<T1>(a) == exists<T2>(a)
}
As written, the Move Prover will report that the invariant is violated after the call to publish1
and before the call to publish2
. If either of publish1
or publish2
is without the other, the Move Prover
will also report a violation of the invariant.
By default, a global invariant is checked immediately after the instruction I
that touches the resources mentioned in the global invariant. The [suspendable]
attribute (at the invariant side) together with two pragmas (specified in function spec block) provide fine-grained control on where we hope this invariant to be checked:
disable_invariants_in_body
: the invariant will be checked at the end of the function whereI
resides.delegate_invariants_to_caller
: the invariant will be checked by all callers of the function whereI
resides.
For the example above, we can add the pragma disable_invariants_in_body
:
spec setup {
pragma disable_invariants_in_body;
}
which says that invariants are not required to hold while setup
is executing but are assumed to hold on entry to and exit from setup
.
This pragma changes the Move Prover's behavior. The invariants are assumed on entry to setup
but not proved during or after publish1
and publish2
. Instead, all invariants that could be invalidated in the
body of setup
are asserted and proved at the point of return from setup
. A consequence of this processing is that the user may need to provide stronger post-conditions on publish1
and publish2
to
make it possible to prove the invariants on exit from setup
.
Another consequence of this processing is that invariants cannot safely be assumed to hold during the execution of publish1
and publish2
(unless nothing in the body of setup
changes state
mentioned in the invariant). Therefore, if proving a post-condition requires the invariant to be assumed, the post-condition will fail.
In the example, invariants hold at the call sites of setup
but not in the body. For publish1
, invariants don't necessarily hold at the call site or in the body of the function. In the example, that
behavior is implied because publish1
is called in a context where invariants are disabled.
When invariants are disabled in setup
in the above example, the Move Prover cannot assume them on entry to publish1
and publish2
and should not try to prove them on exit from those functions. The Move Prover
would have the same behavior for any functions called by publish1
or publish2
. The Move Prover automatically adopts this behavior when invariants are disabled in a calling function, but it is possible for the user to declare that a function be treated like publish1
.
For example, if publish2
is only called from the setup function above, and we did not disable invariants in setup
, we could achieve a similar effect by using the pragma delegate_invariants_to_caller
, instead.
spec setup {
pragma delegate_invariants_to_caller;
}
This would be legal only if setup
is a private or public (friend)
function. The difference between this and disabling invariants in setup
is that the invariants would not be assumed at the beginning of setup
and would be proved after setup
returns at each site where it is called.
While both pragmas disable invariants in the body of a function, the difference is that disable_invariants_in_body
assumes invariants on entry and proves them on exit, while delegate_invariants_to_caller
does neither.
There are some limitations on how these pragmas can be used. disable_invariants_in_body
cannot be declared for functions where invariants are delegated to a caller, either explicitly via the pragma
or implicitly because the function is called in a context where invariants have been disabled. (This restriction is to ensure consistent processing, because on pragma assumes that invariants hold
in the calling context and the other does not). Second, it is illegal for a public or script function to delegate invariant checking to its callers (since the Move Prover does not know all the call sites), unless the function cannot possibly invalidate an invariant because it doesn't change any of the state mentioned in exists
and global
expressions appearing in the invariant.
Update invariants
The update
form of a global invariant allows to express a relation between pre-state and post-state of a global state update. For example, the following invariant states that the counter must decrease monotonically whenever it is updated:
module addr::M {
invariant update [global] forall a: addr where old(exists<Counter>(a)) && exists<Counter>(addr):
global<Counter>(a).value <= old(global<Counter>(a));
}
Isolated global invariants
A global invariant can be marked as [isolated]
to indicate that it is not relevant for proving
other properties of the program. An isolated global invariant will not be assumed when the related
global state is read. It will only be assumed before the state is updated to help prove that the
invariant still holds after the update. This feature is for improving performance in situations
where there are many global invariants, but they have no direct influence on verification.
Modular verification and global invariants
Certain usage of global invariants leads to verification problems that cannot be checked in a modular fashion. "Modular" here means that a module can be verified standalone and proven to be universally correct in all usage contexts (if preconditions are met).
A non-modular verification problem may arise if a global invariant refers to state from multiple modules. Consider a situation where module M1
uses module M2
, and M1
contains the following invariant, with the helper function condition
referring to global state of each respective module:
module addr::M1 {
invariant M1::condition() ==> M2::condition();
}
When we verify M1
standalone, the Move Prover will determine that it also needs to verify functions in M2
, namely those which update the M2 memory such that the invariant in M1 can fail.
Assume and assert conditions in code
A spec block might also occur anywhere an ordinary Move statement block can occur. Here is an example:
fun simple1(x: u64, y: u64) {
let z;
y = x;
z = x + y;
spec {
assert x == y;
assert z == 2*x;
}
}