Module `0x1::SlidingNonce`

Allows transactions to be executed out-of-order while ensuring that they are executed at most once. Nonces are assigned to transactions off-chain by clients submitting the transactions. It maintains a sliding window bitvector of 128 flags. A flag of 0 indicates that the transaction with that nonce has not yet been executed. When nonce X is recorded, all transactions with nonces lower then X-128 will abort.

Resource SlidingNonce
Constants
Function record_nonce_or_abort
Function try_record_nonce
Function publish
Module Specification

<pre><code>use <a href="../../../../../../move-stdlib/docs/Errors.md#0x1_Errors">0x1::Errors</a>; use <a href="../../../../../../move-stdlib/docs/Signer.md#0x1_Signer">0x1::Signer</a>; </code></pre>

Resource `SlidingNonce`

<pre><code>struct <a href="SlidingNonce.md#0x1_SlidingNonce">SlidingNonce</a> has key </code></pre> <details> <summary>Fields</summary> <dl> <dt> <code>min_nonce: u64</code> </dt> <dd> Minimum nonce in sliding window. All transactions with smaller nonces will be automatically rejected, since the window cannot tell whether they have been executed or not. </dd> <dt> <code>nonce_mask: u128</code> </dt> <dd> Bit-vector of window of nonce values </dd> </dl> </details>

Constants

The sliding nonce resource was already published

<pre><code>const <a href="SlidingNonce.md#0x1_SlidingNonce_ENONCE_ALREADY_PUBLISHED">ENONCE_ALREADY_PUBLISHED</a>: u64 = 4; </code></pre>

The nonce was already recorded previously

<pre><code>const <a href="SlidingNonce.md#0x1_SlidingNonce_ENONCE_ALREADY_RECORDED">ENONCE_ALREADY_RECORDED</a>: u64 = 3; </code></pre>

The nonce is too large - this protects against nonce exhaustion

<pre><code>const <a href="SlidingNonce.md#0x1_SlidingNonce_ENONCE_TOO_NEW">ENONCE_TOO_NEW</a>: u64 = 2; </code></pre>

The nonce aborted because it's too old (nonce smaller than <code>min_nonce</code>)

<pre><code>const <a href="SlidingNonce.md#0x1_SlidingNonce_ENONCE_TOO_OLD">ENONCE_TOO_OLD</a>: u64 = 1; </code></pre>

The <code><a href="SlidingNonce.md#0x1_SlidingNonce">SlidingNonce</a></code> resource is in an invalid state

<pre><code>const <a href="SlidingNonce.md#0x1_SlidingNonce_ESLIDING_NONCE">ESLIDING_NONCE</a>: u64 = 0; </code></pre>

Size of SlidingNonce::nonce_mask in bits.

<pre><code>const <a href="SlidingNonce.md#0x1_SlidingNonce_NONCE_MASK_SIZE">NONCE_MASK_SIZE</a>: u64 = 128; </code></pre>

Function `record_nonce_or_abort`

Calls <code>try_record_nonce</code> and aborts transaction if returned code is non-0

<pre><code>public fun <a href="SlidingNonce.md#0x1_SlidingNonce_record_nonce_or_abort">record_nonce_or_abort</a>(account: &signer, seq_nonce: u64) </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="SlidingNonce.md#0x1_SlidingNonce_record_nonce_or_abort">record_nonce_or_abort</a>(account: &signer, seq_nonce: u64) acquires <a href="SlidingNonce.md#0x1_SlidingNonce">SlidingNonce</a> { let code = <a href="SlidingNonce.md#0x1_SlidingNonce_try_record_nonce">try_record_nonce</a>(account, seq_nonce); assert(code == 0, <a href="../../../../../../move-stdlib/docs/Errors.md#0x1_Errors_invalid_argument">Errors::invalid_argument</a>(code)); } </code></pre> </details> <details> <summary>Specification</summary> <pre><code>include <a href="SlidingNonce.md#0x1_SlidingNonce_RecordNonceAbortsIf">RecordNonceAbortsIf</a>; </code></pre>

<pre><code>schema <a href="SlidingNonce.md#0x1_SlidingNonce_RecordNonceAbortsIf">RecordNonceAbortsIf</a> { account: signer; seq_nonce: u64; aborts_if !exists<<a href="SlidingNonce.md#0x1_SlidingNonce">SlidingNonce</a>>(<a href="../../../../../../move-stdlib/docs/Signer.md#0x1_Signer_spec_address_of">Signer::spec_address_of</a>(account)) with <a href="../../../../../../move-stdlib/docs/Errors.md#0x1_Errors_NOT_PUBLISHED">Errors::NOT_PUBLISHED</a>; aborts_if <a href="SlidingNonce.md#0x1_SlidingNonce_spec_try_record_nonce">spec_try_record_nonce</a>(account, seq_nonce) != 0 with <a href="../../../../../../move-stdlib/docs/Errors.md#0x1_Errors_INVALID_ARGUMENT">Errors::INVALID_ARGUMENT</a>; } </code></pre> </details>

Function `try_record_nonce`

Explanation of the Algorithm

We have an "infinite" bitvector. The <code>min_nonce</code> tells us the starting index of the window. The window size is the size of the bitmask we can represent in a 128-bit wide bitmap. The <code>seq_nonce</code> that is sent represents setting a bit at index <code>seq_nonce</code> in this infinite bitvector. Because of this, if the same <code>seq_nonce</code> is passed in multiple times, that bit will be set, and we can signal an error. In order to represent the <code>seq_nonce</code> the window we are looking at must be shifted so that <code>seq_nonce</code> lies within that 128-bit window and, since the <code>min_nonce</code> represents the left-hand-side of this window, it must be increased to be no less than <code>seq_nonce - 128</code>.

The process of shifting window will invalidate other transactions that have a <code>seq_nonce</code> number that are to the "left" of this window (i.e., less than <code>min_nonce</code>) since it cannot be represented in the current window, and the window can only move forward and never backwards.

In order to prevent shifting this window over too much at any one time, a <code>jump_limit</code> is imposed. If a <code>seq_nonce</code> is provided that would cause the <code>min_nonce</code> to need to be increased by more than the <code>jump_limit</code> this will cause a failure.

Some Examples

Let's say we start out with a clean <code><a href="SlidingNonce.md#0x1_SlidingNonce">SlidingNonce</a></code> published under <code>account</code>, this will look like this:

000000000000000000...00000000000000000000000000000...
^             ...                ^
|_____________...________________|
min_nonce = 0             min_nonce + NONCE_MASK_SIZE = 0 + 64 = 64

Example 1:

Let's see what happens when we call<code><a href="SlidingNonce.md#0x1_SlidingNonce_try_record_nonce">SlidingNonce::try_record_nonce</a>(account, 8)</code>:

Determine the bit position w.r.t. the current window:

bit_pos = 8 - min_nonce ~~~ 8 - 0 = 8

See if the bit position that was calculated is not within the current window:

bit_pos >= NONCE_MASK_SIZE ~~~ 8 >= 128 = FALSE

<code>bit_pos</code> is in window, so set the 8'th bit in the window:

000000010000000000...00000000000000000000000000000...
^             ...                ^
|_____________...________________|
min_nonce = 0             min_nonce + NONCE_MASK_SIZE = 0 + 64 = 64

Example 2:

Let's see what happens when we call <code><a href="SlidingNonce.md#0x1_SlidingNonce_try_record_nonce">SlidingNonce::try_record_nonce</a>(account, 129)</code>:

Figure out the bit position w.r.t. the current window:

bit_pos = 129 - min_nonce ~~~ 129 - 0 = 129

See if bit position calculated is not within the current window starting at <code>min_nonce</code>:

bit_pos >= NONCE_MASK_SIZE ~~~ 129 >= 128 = TRUE

<code>bit_pos</code> is outside of the current window. So we need to shift the window over. Now calculate the amount that the window needs to be shifted over (i.e., the amount that <code>min_nonce</code> needs to be increased by) so that <code>seq_nonce</code> lies within the <code><a href="SlidingNonce.md#0x1_SlidingNonce_NONCE_MASK_SIZE">NONCE_MASK_SIZE</a></code> window starting at <code>min_nonce</code>. 3a. Calculate the amount that the window needs to be shifted for <code>bit_pos</code> to lie within it:

shift = bit_pos - NONCE_MASK_SIZE + 1 ~~~ 129 - 128 + 1 = 2

3b. See if there is no overlap between the new window that we need to shift to and the old window:

shift >= NONCE_MASK_SIZE ~~~ 2 >= 128 = FALSE

3c. Since there is an overlap between the new window that we need to shift to and the previous window, shift the window over, but keep the current set bits in the overlapping part of the window:

nonce_mask = nonce_mask >> shift; min_nonce += shift;

Now that the window has been shifted over so that the <code>seq_nonce</code> index lies within the new window we recompute the <code>bit_pos</code> w.r.t. to it (recall <code>min_nonce</code> was updated):

bit_pos = seq - min_nonce ~~~ 129 - 2 = 127

We set the bit_pos position bit within the new window:

00000001000000000000000...000000000000000000000000000000000000000000010...
^               ...                                           ^^
|               ...                                           ||
|               ...                                 new_set_bit|
|_______________...____________________________________________|
min_nonce = 2                            min_nonce + NONCE_MASK_SIZE = 2 + 128 = 130

Example 3:

Let's see what happens when we call <code><a href="SlidingNonce.md#0x1_SlidingNonce_try_record_nonce">SlidingNonce::try_record_nonce</a>(account, 400)</code>:

Figure out the bit position w.r.t. the current window:

bit_pos = 400 - min_nonce ~~~ 400 - 2 = 398

See if bit position calculated is not within the current window:

bit_pos >= NONCE_MASK_SIZE ~~~ 398 >= 128 = TRUE

<code>bit_pos</code> is out of the window. Now calculate the amount that the window needs to be shifted over (i.e., that <code>min_nonce</code> needs to be incremented) so <code>seq_nonce</code> lies within the <code><a href="SlidingNonce.md#0x1_SlidingNonce_NONCE_MASK_SIZE">NONCE_MASK_SIZE</a></code> window starting at min_nonce. 3a. Calculate the amount that the window needs to be shifted for <code>bit_pos</code> to lie within it:

shift = bit_pos - NONCE_MASK_SIZE + 1 ~~~ 398 - 128 + 1 = 271

3b. See if there is no overlap between the new window that we need to shift to and the old window:

shift >= NONCE_MASK_SIZE ~~~ 271 >= 128 = TRUE

3c. Since there is no overlap between the new window that we need to shift to and the previous window we zero out the bitmap, and update the <code>min_nonce</code> to start at the out-of-range <code>seq_nonce</code>:

nonce_mask = 0; min_nonce = seq_nonce + 1 - NONCE_MASK_SIZE = 273;

Now that the window has been shifted over so that the <code>seq_nonce</code> index lies within the window we recompute the bit_pos:

bit_pos = seq_nonce - min_nonce ~~~ 400 - 273 = 127

We set the bit_pos position bit within the new window:

...00000001000000000000000...000000000000000000000000000000000000000000010...
^               ...                                           ^^
|               ...                                           ||
|               ...                                 new_set_bit|
|_______________...____________________________________________|
min_nonce = 273                          min_nonce + NONCE_MASK_SIZE = 273 + 128 = 401

Tries to record this nonce in the account. Returns 0 if a nonce was recorded and non-0 otherwise

<pre><code>public fun <a href="SlidingNonce.md#0x1_SlidingNonce_try_record_nonce">try_record_nonce</a>(account: &signer, seq_nonce: u64): u64 </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="SlidingNonce.md#0x1_SlidingNonce_try_record_nonce">try_record_nonce</a>(account: &signer, seq_nonce: u64): u64 acquires <a href="SlidingNonce.md#0x1_SlidingNonce">SlidingNonce</a> { if (seq_nonce == 0) { return 0 }; assert(exists<<a href="SlidingNonce.md#0x1_SlidingNonce">SlidingNonce</a>>(<a href="../../../../../../move-stdlib/docs/Signer.md#0x1_Signer_address_of">Signer::address_of</a>(account)), <a href="../../../../../../move-stdlib/docs/Errors.md#0x1_Errors_not_published">Errors::not_published</a>(<a href="SlidingNonce.md#0x1_SlidingNonce_ESLIDING_NONCE">ESLIDING_NONCE</a>)); let t = borrow_global_mut<<a href="SlidingNonce.md#0x1_SlidingNonce">SlidingNonce</a>>(<a href="../../../../../../move-stdlib/docs/Signer.md#0x1_Signer_address_of">Signer::address_of</a>(account)); // The `seq_nonce` is outside the current window to the "left" and is // no longer valid since we can't shift the window back. if (t.min_nonce > seq_nonce) { return <a href="SlidingNonce.md#0x1_SlidingNonce_ENONCE_TOO_OLD">ENONCE_TOO_OLD</a> }; // Don't allow giant leaps in nonce to protect against nonce exhaustion // If we try to move a window by more than this amount, we will fail. let jump_limit = 10000; if (t.min_nonce + jump_limit <= seq_nonce) { return <a href="SlidingNonce.md#0x1_SlidingNonce_ENONCE_TOO_NEW">ENONCE_TOO_NEW</a> }; // Calculate The bit position in the window that will be set in our window let bit_pos = seq_nonce - t.min_nonce; // See if the bit position that we want to set lies outside the current // window that we have under the current `min_nonce`. if (bit_pos >= <a href="SlidingNonce.md#0x1_SlidingNonce_NONCE_MASK_SIZE">NONCE_MASK_SIZE</a>) { // Determine how much we need to shift the current window over (to // the "right") so that `bit_pos` lies within the new window. let shift = (bit_pos - <a href="SlidingNonce.md#0x1_SlidingNonce_NONCE_MASK_SIZE">NONCE_MASK_SIZE</a> + 1); // If we are shifting the window over by more than one window's width // reset the bits in the window, and update the // new start of the `min_nonce` so that `seq_nonce` is the // right-most bit in the new window. if(shift >= <a href="SlidingNonce.md#0x1_SlidingNonce_NONCE_MASK_SIZE">NONCE_MASK_SIZE</a>) { t.nonce_mask = 0; t.min_nonce = seq_nonce + 1 - <a href="SlidingNonce.md#0x1_SlidingNonce_NONCE_MASK_SIZE">NONCE_MASK_SIZE</a>; } else { // We are shifting the window over by less than a windows width, // so we need to keep the current set bits in the window t.nonce_mask = t.nonce_mask >> (shift as u8); t.min_nonce = t.min_nonce + shift; } }; // The window has been (possibly) shifted over so that `seq_nonce` lies // within the window. Recompute the bit positition that needs to be set // within the (possibly) new window. let bit_pos = seq_nonce - t.min_nonce; let set = 1u128 << (bit_pos as u8); // The bit was already set, so return an error. if (t.nonce_mask & set != 0) { return <a href="SlidingNonce.md#0x1_SlidingNonce_ENONCE_ALREADY_RECORDED">ENONCE_ALREADY_RECORDED</a> }; t.nonce_mask = t.nonce_mask | set; 0 } </code></pre> </details> <details> <summary>Specification</summary>

It is currently assumed that this function raises no arithmetic overflow/underflow.

Note: Verification is turned off. For verifying callers, this is effectively abstracted into a function that returns arbitrary results because <code>spec_try_record_nonce</code> is uninterpreted.

<pre><code>pragma opaque, verify = false; aborts_if !exists<<a href="SlidingNonce.md#0x1_SlidingNonce">SlidingNonce</a>>(<a href="../../../../../../move-stdlib/docs/Signer.md#0x1_Signer_spec_address_of">Signer::spec_address_of</a>(account)) with <a href="../../../../../../move-stdlib/docs/Errors.md#0x1_Errors_NOT_PUBLISHED">Errors::NOT_PUBLISHED</a>; modifies global<<a href="SlidingNonce.md#0x1_SlidingNonce">SlidingNonce</a>>(<a href="../../../../../../move-stdlib/docs/Signer.md#0x1_Signer_spec_address_of">Signer::spec_address_of</a>(account)); ensures result == <a href="SlidingNonce.md#0x1_SlidingNonce_spec_try_record_nonce">spec_try_record_nonce</a>(account, seq_nonce); ensures exists<<a href="SlidingNonce.md#0x1_SlidingNonce">SlidingNonce</a>>(<a href="../../../../../../move-stdlib/docs/Signer.md#0x1_Signer_spec_address_of">Signer::spec_address_of</a>(account)); </code></pre>

Specification version of <code><a href="SlidingNonce.md#0x1_SlidingNonce_try_record_nonce">Self::try_record_nonce</a></code>.

<pre><code>fun <a href="SlidingNonce.md#0x1_SlidingNonce_spec_try_record_nonce">spec_try_record_nonce</a>(account: signer, seq_nonce: u64): u64; </code></pre> </details>

Function `publish`

Publishes nonce resource for <code>account</code> This is required before other functions in this module can be called for <code>account</code>

<pre><code>public(friend) fun <a href="SlidingNonce.md#0x1_SlidingNonce_publish">publish</a>(account: &signer) </code></pre> <details> <summary>Implementation</summary> <pre><code>public(friend) fun <a href="SlidingNonce.md#0x1_SlidingNonce_publish">publish</a>(account: &signer) { assert(!exists<<a href="SlidingNonce.md#0x1_SlidingNonce">SlidingNonce</a>>(<a href="../../../../../../move-stdlib/docs/Signer.md#0x1_Signer_address_of">Signer::address_of</a>(account)), <a href="../../../../../../move-stdlib/docs/Errors.md#0x1_Errors_already_published">Errors::already_published</a>(<a href="SlidingNonce.md#0x1_SlidingNonce_ENONCE_ALREADY_PUBLISHED">ENONCE_ALREADY_PUBLISHED</a>)); move_to(account, <a href="SlidingNonce.md#0x1_SlidingNonce">SlidingNonce</a> { min_nonce: 0, nonce_mask: 0 }); } </code></pre> </details> <details> <summary>Specification</summary> <pre><code>pragma opaque; modifies global<<a href="SlidingNonce.md#0x1_SlidingNonce">SlidingNonce</a>>(<a href="../../../../../../move-stdlib/docs/Signer.md#0x1_Signer_spec_address_of">Signer::spec_address_of</a>(account)); aborts_if exists<<a href="SlidingNonce.md#0x1_SlidingNonce">SlidingNonce</a>>(<a href="../../../../../../move-stdlib/docs/Signer.md#0x1_Signer_spec_address_of">Signer::spec_address_of</a>(account)) with <a href="../../../../../../move-stdlib/docs/Errors.md#0x1_Errors_ALREADY_PUBLISHED">Errors::ALREADY_PUBLISHED</a>; ensures exists<<a href="SlidingNonce.md#0x1_SlidingNonce">SlidingNonce</a>>(<a href="../../../../../../move-stdlib/docs/Signer.md#0x1_Signer_spec_address_of">Signer::spec_address_of</a>(account)); </code></pre> </details>

Module Specification

Sliding nonces are initialized at Diem root and treasury compliance addresses

<pre><code>invariant [suspendable] <a href="DiemTimestamp.md#0x1_DiemTimestamp_is_operating">DiemTimestamp::is_operating</a>() ==> exists<<a href="SlidingNonce.md#0x1_SlidingNonce">SlidingNonce</a>>(@DiemRoot); invariant [suspendable] <a href="DiemTimestamp.md#0x1_DiemTimestamp_is_operating">DiemTimestamp::is_operating</a>() ==> exists<<a href="SlidingNonce.md#0x1_SlidingNonce">SlidingNonce</a>>(@TreasuryCompliance); </code></pre>

Module `0x1::SlidingNonce`

Module 0x1::SlidingNonce

Resource SlidingNonce

Constants

Function record_nonce_or_abort

Function try_record_nonce

Explanation of the Algorithm

Some Examples

Example 1:

Example 2:

Example 3:

Function publish

Module Specification

Module `0x1::SlidingNonce`

Resource `SlidingNonce`

Function `record_nonce_or_abort`

Function `try_record_nonce`

Function `publish`