Module `0x1::CRSN`

A module implementing conflict-resistant sequence numbers (CRSNs). The specification, and formal description of the acceptance and rejection criteria, force expiration and window shifting of CRSNs are described in DIP-168.

Resource CRSN
Constants
Function publish
Function record
Function check
Function force_expire
Function has_crsn
Function shift_window_right

<pre><code>use <a href="../../../../../../move-stdlib/docs/BitVector.md#0x1_BitVector">0x1::BitVector</a>; 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 `CRSN`

A CRSN represents a finite slice or window of an "infinite" bitvector starting at zero with a size <code>k</code> defined dynamically at the time of publication of CRSN resource. The <code>min_nonce</code> defines the left-hand side of the slice, and the slice's state is held in <code>slots</code> and is of size <code>k</code>. Diagrammatically:

1111...000000100001000000...0100001000000...0000...
^             ...                ^
|____..._____slots______...______|
min_nonce                       min_nonce + k - 1

<pre><code>struct <a href="CRSN.md#0x1_CRSN">CRSN</a> has key </code></pre> <details> <summary>Fields</summary> <dl> <dt> <code>min_nonce: u64</code> </dt> <dd> </dd> <dt> <code>size: u64</code> </dt> <dd> </dd> <dt> <code>slots: <a href="../../../../../../move-stdlib/docs/BitVector.md#0x1_BitVector_BitVector">BitVector::BitVector</a></code> </dt> <dd> </dd> </dl> </details>

Constants

The size given to the CRSN at the time of publishing was larger than the largest allowed CRSN size

<pre><code>const <a href="CRSN.md#0x1_CRSN_ECRSN_SIZE_TOO_LARGE">ECRSN_SIZE_TOO_LARGE</a>: u64 = 3; </code></pre>

A CRSN resource wasn't expected, but one was found

<pre><code>const <a href="CRSN.md#0x1_CRSN_EHAS_CRSN">EHAS_CRSN</a>: u64 = 1; </code></pre>

the amount to shift the CRSN window was zero

<pre><code>const <a href="CRSN.md#0x1_CRSN_EINVALID_SHIFT">EINVALID_SHIFT</a>: u64 = 4; </code></pre>

No CRSN resource exists

<pre><code>const <a href="CRSN.md#0x1_CRSN_ENO_CRSN">ENO_CRSN</a>: u64 = 0; </code></pre>

The size given to the CRSN at the time of publishing was zero, which is not supported

<pre><code>const <a href="CRSN.md#0x1_CRSN_EZERO_SIZE_CRSN">EZERO_SIZE_CRSN</a>: u64 = 2; </code></pre>

<pre><code>const <a href="CRSN.md#0x1_CRSN_MAX_CRSN_SIZE">MAX_CRSN_SIZE</a>: u64 = 256; </code></pre>

Function `publish`

Publish a DSN under <code>account</code>. Cannot already have a DSN published.

<pre><code>public(friend) fun <a href="CRSN.md#0x1_CRSN_publish">publish</a>(account: &signer, min_nonce: u64, size: u64) </code></pre> <details> <summary>Implementation</summary> <pre><code>public(friend) fun <a href="CRSN.md#0x1_CRSN_publish">publish</a>(account: &signer, min_nonce: u64, size: u64) { assert(!<a href="CRSN.md#0x1_CRSN_has_crsn">has_crsn</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_invalid_state">Errors::invalid_state</a>(<a href="CRSN.md#0x1_CRSN_EHAS_CRSN">EHAS_CRSN</a>)); assert(size > 0, <a href="../../../../../../move-stdlib/docs/Errors.md#0x1_Errors_invalid_argument">Errors::invalid_argument</a>(<a href="CRSN.md#0x1_CRSN_EZERO_SIZE_CRSN">EZERO_SIZE_CRSN</a>)); assert(size <= <a href="CRSN.md#0x1_CRSN_MAX_CRSN_SIZE">MAX_CRSN_SIZE</a>, <a href="../../../../../../move-stdlib/docs/Errors.md#0x1_Errors_invalid_argument">Errors::invalid_argument</a>(<a href="CRSN.md#0x1_CRSN_ECRSN_SIZE_TOO_LARGE">ECRSN_SIZE_TOO_LARGE</a>)); move_to(account, <a href="CRSN.md#0x1_CRSN">CRSN</a> { min_nonce, size, slots: <a href="../../../../../../move-stdlib/docs/BitVector.md#0x1_BitVector_new">BitVector::new</a>(size), }) } </code></pre> </details> <details> <summary>Specification</summary> <pre><code>include <a href="../../../../../../move-stdlib/docs/BitVector.md#0x1_BitVector_NewAbortsIf">BitVector::NewAbortsIf</a>{length: size}; aborts_if <a href="CRSN.md#0x1_CRSN_has_crsn">has_crsn</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_INVALID_STATE">Errors::INVALID_STATE</a>; aborts_if size == 0 with <a href="../../../../../../move-stdlib/docs/Errors.md#0x1_Errors_INVALID_ARGUMENT">Errors::INVALID_ARGUMENT</a>; aborts_if size > <a href="CRSN.md#0x1_CRSN_MAX_CRSN_SIZE">MAX_CRSN_SIZE</a> with <a href="../../../../../../move-stdlib/docs/Errors.md#0x1_Errors_INVALID_ARGUMENT">Errors::INVALID_ARGUMENT</a>; ensures exists<<a href="CRSN.md#0x1_CRSN">CRSN</a>>(<a href="../../../../../../move-stdlib/docs/Signer.md#0x1_Signer_spec_address_of">Signer::spec_address_of</a>(account)); </code></pre> </details>

Function `record`

Record <code>sequence_nonce</code> under the <code>account</code>. Returns true if <code>sequence_nonce</code> is accepted, returns false if the <code>sequence_nonce</code> is rejected.

<pre><code>public(friend) fun <a href="CRSN.md#0x1_CRSN_record">record</a>(account: &signer, sequence_nonce: u64): bool </code></pre> <details> <summary>Implementation</summary> <pre><code>public(friend) fun <a href="CRSN.md#0x1_CRSN_record">record</a>(account: &signer, sequence_nonce: u64): bool acquires <a href="CRSN.md#0x1_CRSN">CRSN</a> { let addr = <a href="../../../../../../move-stdlib/docs/Signer.md#0x1_Signer_address_of">Signer::address_of</a>(account); if (<a href="CRSN.md#0x1_CRSN_check">check</a>(account, sequence_nonce)) { // <a href="CRSN.md#0x1_CRSN">CRSN</a> exists by `check`. let crsn = borrow_global_mut<<a href="CRSN.md#0x1_CRSN">CRSN</a>>(addr); // accept nonce let scaled_nonce = sequence_nonce - crsn.min_nonce; <a href="../../../../../../move-stdlib/docs/BitVector.md#0x1_BitVector_set">BitVector::set</a>(&mut crsn.slots, scaled_nonce); <a href="CRSN.md#0x1_CRSN_shift_window_right">shift_window_right</a>(crsn); return true } else if (exists<<a href="CRSN.md#0x1_CRSN">CRSN</a>>(addr)) { // window was force shifted in this transaction let crsn = borrow_global<<a href="CRSN.md#0x1_CRSN">CRSN</a>>(addr); if (crsn.min_nonce > sequence_nonce) return true }; false } </code></pre> </details>

Function `check`

A stateless version of <code>record</code>: returns <code>true</code> if the <code>sequence_nonce</code> will be accepted, and <code>false</code> otherwise.

<pre><code>public(friend) fun <a href="CRSN.md#0x1_CRSN_check">check</a>(account: &signer, sequence_nonce: u64): bool </code></pre> <details> <summary>Implementation</summary> <pre><code>public(friend) fun <a href="CRSN.md#0x1_CRSN_check">check</a>(account: &signer, sequence_nonce: u64): bool acquires <a href="CRSN.md#0x1_CRSN">CRSN</a> { let addr = <a href="../../../../../../move-stdlib/docs/Signer.md#0x1_Signer_address_of">Signer::address_of</a>(account); assert(<a href="CRSN.md#0x1_CRSN_has_crsn">has_crsn</a>(addr), <a href="../../../../../../move-stdlib/docs/Errors.md#0x1_Errors_invalid_state">Errors::invalid_state</a>(<a href="CRSN.md#0x1_CRSN_ENO_CRSN">ENO_CRSN</a>)); let crsn = borrow_global_mut<<a href="CRSN.md#0x1_CRSN">CRSN</a>>(addr); // Don't accept if it's outside of the window if ((sequence_nonce < crsn.min_nonce) || ((sequence_nonce as u128) >= (crsn.min_nonce as u128) + (<a href="../../../../../../move-stdlib/docs/BitVector.md#0x1_BitVector_length">BitVector::length</a>(&crsn.slots) as u128))) { false } else { // scaled nonce is the index in the window let scaled_nonce = sequence_nonce - crsn.min_nonce; // Bit already set, reject, otherwise accept !<a href="../../../../../../move-stdlib/docs/BitVector.md#0x1_BitVector_is_index_set">BitVector::is_index_set</a>(&crsn.slots, scaled_nonce) } } </code></pre> </details> <details> <summary>Specification</summary> <pre><code>include <a href="CRSN.md#0x1_CRSN_CheckAbortsIf">CheckAbortsIf</a>{addr: <a href="../../../../../../move-stdlib/docs/Signer.md#0x1_Signer_spec_address_of">Signer::spec_address_of</a>(account)}; </code></pre>

<pre><code>schema <a href="CRSN.md#0x1_CRSN_CheckAbortsIf">CheckAbortsIf</a> { addr: address; sequence_nonce: u64; let crsn = global<<a href="CRSN.md#0x1_CRSN">CRSN</a>>(addr); let scaled_nonce = sequence_nonce - crsn.min_nonce; aborts_if !<a href="CRSN.md#0x1_CRSN_has_crsn">has_crsn</a>(addr) with <a href="../../../../../../move-stdlib/docs/Errors.md#0x1_Errors_INVALID_STATE">Errors::INVALID_STATE</a>; include <a href="CRSN.md#0x1_CRSN_has_crsn">has_crsn</a>(addr) && (sequence_nonce >= crsn.min_nonce) && (sequence_nonce + crsn.min_nonce < <a href="../../../../../../move-stdlib/docs/BitVector.md#0x1_BitVector_length">BitVector::length</a>(crsn.slots)) ==> <a href="../../../../../../move-stdlib/docs/BitVector.md#0x1_BitVector_IsIndexSetAbortsIf">BitVector::IsIndexSetAbortsIf</a>{bitvector: crsn.slots, bit_index: scaled_nonce }; } </code></pre>

<pre><code>fun <a href="CRSN.md#0x1_CRSN_spec_check">spec_check</a>(addr: address, sequence_nonce: u64): bool { let crsn = global<<a href="CRSN.md#0x1_CRSN">CRSN</a>>(addr); if ((sequence_nonce < crsn.min_nonce) || (sequence_nonce >= crsn.min_nonce + <a href="../../../../../../move-stdlib/docs/BitVector.md#0x1_BitVector_length">BitVector::length</a>(crsn.slots))) { false } else { let scaled_nonce = sequence_nonce - crsn.min_nonce; !<a href="../../../../../../move-stdlib/docs/BitVector.md#0x1_BitVector_spec_is_index_set">BitVector::spec_is_index_set</a>(crsn.slots, scaled_nonce) } } </code></pre> </details>

Function `force_expire`

Force expire transactions by forcibly shifting the window by <code>shift_amount</code>. After the window has been shifted by <code>shift_amount</code> it is then shifted over set bits as define by the <code>shift_window_right</code> function.

<pre><code>public fun <a href="CRSN.md#0x1_CRSN_force_expire">force_expire</a>(account: &signer, shift_amount: u64) </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="CRSN.md#0x1_CRSN_force_expire">force_expire</a>(account: &signer, shift_amount: u64) acquires <a href="CRSN.md#0x1_CRSN">CRSN</a> { assert(shift_amount > 0, <a href="../../../../../../move-stdlib/docs/Errors.md#0x1_Errors_invalid_argument">Errors::invalid_argument</a>(<a href="CRSN.md#0x1_CRSN_EINVALID_SHIFT">EINVALID_SHIFT</a>)); let addr = <a href="../../../../../../move-stdlib/docs/Signer.md#0x1_Signer_address_of">Signer::address_of</a>(account); assert(<a href="CRSN.md#0x1_CRSN_has_crsn">has_crsn</a>(addr), <a href="../../../../../../move-stdlib/docs/Errors.md#0x1_Errors_invalid_state">Errors::invalid_state</a>(<a href="CRSN.md#0x1_CRSN_ENO_CRSN">ENO_CRSN</a>)); let crsn = borrow_global_mut<<a href="CRSN.md#0x1_CRSN">CRSN</a>>(addr); <a href="../../../../../../move-stdlib/docs/BitVector.md#0x1_BitVector_shift_left">BitVector::shift_left</a>(&mut crsn.slots, shift_amount); crsn.min_nonce = crsn.min_nonce + shift_amount; // shift over any set bits <a href="CRSN.md#0x1_CRSN_shift_window_right">shift_window_right</a>(crsn); } </code></pre> </details>

Function `has_crsn`

Return whether this address has a CRSN resource published under it.

<pre><code>public fun <a href="CRSN.md#0x1_CRSN_has_crsn">has_crsn</a>(addr: address): bool </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="CRSN.md#0x1_CRSN_has_crsn">has_crsn</a>(addr: address): bool { exists<<a href="CRSN.md#0x1_CRSN">CRSN</a>>(addr) } </code></pre> </details>

Function `shift_window_right`

<pre><code>fun <a href="CRSN.md#0x1_CRSN_shift_window_right">shift_window_right</a>(crsn: &mut <a href="CRSN.md#0x1_CRSN_CRSN">CRSN::CRSN</a>) </code></pre> <details> <summary>Implementation</summary> <pre><code>fun <a href="CRSN.md#0x1_CRSN_shift_window_right">shift_window_right</a>(crsn: &mut <a href="CRSN.md#0x1_CRSN">CRSN</a>) { let index = <a href="../../../../../../move-stdlib/docs/BitVector.md#0x1_BitVector_longest_set_sequence_starting_at">BitVector::longest_set_sequence_starting_at</a>(&crsn.slots, 0); // if there is no run of set bits return early if (index == 0) return; <a href="../../../../../../move-stdlib/docs/BitVector.md#0x1_BitVector_shift_left">BitVector::shift_left</a>(&mut crsn.slots, index); crsn.min_nonce = crsn.min_nonce + index; } </code></pre> </details>

Module `0x1::CRSN`

Module 0x1::CRSN

Resource CRSN

Constants

Function publish

Function record

Function check

Function force_expire

Function has_crsn

Function shift_window_right

Module `0x1::CRSN`

Resource `CRSN`

Function `publish`

Function `record`

Function `check`

Function `force_expire`

Function `has_crsn`

Function `shift_window_right`