New contract state: node support

[abizjak]

Task description

This builds on top of #236 .

Develop a new smart contract state implementation that supports efficiently updating part of the contract state. The high-level requirements are

• Existing smart contracts must continue to work as they did.
• Smart contracts must be able to store in their state large ledgers, i.e., mappings from addresses to data about that address.
• State must be efficiently updateable. It must be possible to update a small part of the state and the cost should be based on the size of the updated state plus possibly some overhead based on the size of the entire state. Note that initially looking up the key will depend on the length of the key. Once the value is found, further updates to it will only depend on the updated data, not on the key length.
• Costs of smart contract execution should be based only on the part of the state of the contract that is needed. Similarly, if no state is updated then there should be no charge for that.

The new state implementation will be based on a radix tree (with data at every node). Each contract state is a single radix tree and it is up to the contract implementation to organize different parts of the state by using disjoint prefixes. The implementation needs to support the following API exposed to smart contracts (note that this is subject to minor changes as learnings from development of the feature arrive)

    /// Lookup an entry with the given key. The return value is either
    /// u64::MAX if the entry at the given key does not exist, or else
    /// the first bit of the result is 0, and the remaining bits
    /// are an entry identifier that may be used in subsequent calls.
    pub(crate) fn state_lookup_entry(key_start: *const u8, key_length: u32) -> u64;

    /// Create an empty entry with the given key. The return value is either
    /// u64::MAX if creating the entry failed because of an iterator lock on
    /// the part of the tree, or else the first bit is 0, and the remaining
    /// bits are an entry identifier that maybe used in subsequent calls.
    /// If an entry at that key already exists it is set to the empty entry.
    pub(crate) fn state_create_entry(key_start: *const u8, key_length: u32) -> u64;

    /// Delete the entry. Returns one of
    /// - 0 if the part of the tree this entry was in is locked
    /// - 1 if the entry did not exist
    /// - 2 if the entry was deleted as a result of this call.
    pub(crate) fn state_delete_entry(key_start: *const u8, key_length: u32) -> u32;

    /// Delete a prefix in the tree, that is, delete all parts of the tree that
    /// have the given key as prefix. Returns
    /// - 0 if the tree was locked and thus deletion failed.
    /// - 1 if the tree **was not locked**, but the key points to an empty part
    ///   of the tree
    /// - 2 if a part of the tree was successfully deleted
    pub(crate) fn state_delete_prefix(key_start: *const u8, key_length: u32) -> u32;

    /// Construct an iterator over a part of the tree. This **locks the part of
    /// the tree that has the given prefix**. Locking means that no
    /// deletions or insertions of entries may occur in that subtree.
    /// Returns
    /// - all 1 bits if too many iterators already exist with this key
    /// - all but second bit set to 1 if there is no value in the state with the
    ///   given key
    /// - otherwise the first bit is 0, and the remaining bits are the iterator
    ///   identifier
    /// that may be used in subsequent calls to advance it, or to get its key.
    pub(crate) fn state_iterate_prefix(prefix_start: *const u8, prefix_length: u32) -> u64;

    /// Return the next entry along the iterator, and advance the iterator.
    /// The return value is
    /// - u64::MAX if the iterator does not exist (it was deleted, or the ID is
    ///   invalid)
    /// - all but the second bit set to 1 if no more entries are left, the
    ///   iterator
    /// is exhausted. All further calls will yield the same until the iterator
    /// is deleted.
    /// - otherwise the first bit is 0, and the remaining bits encode an entry
    ///   identifier that can be passed to any of the entry methods.
    pub(crate) fn state_iterator_next(iterator: u64) -> u64;

    /// Delete the iterator, unlocking the subtree. Returns
    /// - u64::MAX if the iterator does not exist.
    /// - 0 if the iterator was already deleted
    /// - 1 if the iterator was successfully deleted as a result of this call.
    pub(crate) fn state_iterator_delete(iterator: u64) -> u32;

    /// Get the length of the key that the iterator is currently pointing at.
    /// Returns
    /// - u32::MAX if the iterator does not exist
    /// - otherwise the length of the key in bytes.
    pub(crate) fn state_iterator_key_size(iterator: u64) -> u32;

    /// Read a section of the key the iterator is currently pointing at. Returns
    /// either
    /// - u32::MAX if the iterator has already been deleted
    /// - the amount of data that was copied. This will never be more than the
    ///   supplied length.
    /// Before the first call to the [state_iterator_next] function this returns
    /// (sections of) the key that was used to create the iterator. After
    /// [state_iterator_next] returns (the encoding of) [None] this method
    /// returns (sections of) the key at the first node returned by the
    /// iterator.
    pub(crate) fn state_iterator_key_read(
        iterator: u64,
        start: *mut u8,
        length: u32,
        offset: u32,
    ) -> u32;

    // Operations on the entry.

    /// Read a part of the entry. The arguments are
    /// entry ... entry id returned by state_iterator_next or state_create_entry
    /// start ... where to write in Wasm memory
    /// length ... length of the data to read
    /// offset ... where to start reading in the entry
    /// The return value is
    /// - u32::MAX if the entry does not exist (has been invalidated, or never
    /// existed). In this case no data is written.
    /// - amount of data that was read. This is never more than length.
    pub(crate) fn state_entry_read(entry: u64, start: *mut u8, length: u32, offset: u32) -> u32;

    /// Write a part of the entry. The arguments are
    /// entry ... entry id returned by state_iterator_next or state_create_entry
    /// start ... where to read from Wasm memory
    /// length ... length of the data to read
    /// offset ... where to start writing in the entry
    /// The return value is
    /// - u32::MAX if the entry does not exist (has been invalidated, or never
    /// existed). In this case no data is written.
    /// - amount of data that was written. This is never more than length.
    pub(crate) fn state_entry_write(entry: u64, start: *const u8, length: u32, offset: u32) -> u32;

    /// Return the current size of the entry in bytes.
    /// The return value is either
    /// - u32::MAX if the entry does not exist (has been invalidated, or never
    /// existed). In this case no data is written.
    /// - or the size of the entry.
    pub(crate) fn state_entry_size(entry: u64) -> u32;

    /// Resize the entry to the given size. Returns
    /// - u32::MAX if the entry has already been invalidated
    /// - 0 if the attempt was unsuccessful because new_size exceeds maximum
    ///   entry size
    /// - 1 if the entry was successfully resized.
    pub(crate) fn state_entry_resize(entry: u64, new_size: u32) -> u32;

Tasks

• Implement the data structure and integrate it into global state. The latter part will mean likely mean revising a lot of the boilerplate abstractions since currently in many places abstractions rely on having the entire state of the contract in memory.
• Add handling of new state to V1 contracts in the scheduler. Since V1 contracts report back on whether they were modified on out-calls it is necessary to track of when
• Add documentation of the data structure choices, and extensive unit tests for the data structure.
• Write and perform benchmarks for data structure operations in realistic and worst-case scenarios. This is needed to assign good costs to contract operations.
• Add sample contracts with unit tests in the scheduler.