Phase 3 and beyond

[hu55a1n1]

Phase 3 and beyond

As we continue basecoin development into phase-3, this might be a good time to revisit its design based on ICS specs. Described below is the first iteration of a design proposal which is expected to evolve over time.

Modules

ICS 24 - Module system describes the requirements expected of the module system. Modules must be ->
* able to execute self-contained, potentially mutually distrusted packages of code
* able to control how other modules can communicate with them
* identifiable
* manipulatable by a master module or execution environment

Additionally, module code must be deterministic (unless otherwise specified).

We define the 'master module' as the basecoin code that manages the routing of messages and interaction between other modules. Note that the [execution environment <> master module <> module] relation is (somewhat) analogous to the [OS <> Kernel <> thread] relation.

Implementation

We define the below trait and examine how it achieves the above requirements.

pub trait Module<S: Store> {
    /// Error type - expected to envelop all possible errors in the module
    type Error: std::error::Error;

    /// Event type - that can be converted to an `AbciEvent`
    type Event: Into<AbciEvent>;

    /// Message type - expected to envelop all messages that the module can handle
    /// Must be instantiable from a corresponding and supported Protobuf message
    type Message: TryFrom<Any, Error = Self::Error>;

    /// Tries to decode a protobuf message to a module supported Message`
    /// This is used to determine if a message is handleable by this module or not
    /// Do NOT use for validation!
    fn decode(message: Any) -> Result<Self::Message, Self::Error> {
        message.try_into()
    }

    /// Similar to [ABCI CheckTx method](https://docs.tendermint.com/master/spec/abci/abci.html#checktx)
    /// > CheckTx need not execute the transaction in full, but rather a light-weight yet 
    /// > stateful validation, like checking signatures and account balances, but not running 
    /// > code in a virtual machine.
    fn check(store: &Store, message: Any) -> Result<(), Self::Error> {
        let _ = Self::decode(message)?;
        Ok(())
    }

    /// Execute specified `Message`, modify state accordingly and return resulting `Events`
    /// *NOTE* - Implementations MUST be deterministic!
    fn dispatch(store: &mut S, message: Self::Message) -> Result<Vec<Self::Event>, Self::Error>;

    /// Similar to [ABCI DeliverTx method](https://docs.tendermint.com/master/spec/abci/abci.html#delivertx)
    fn deliver(store: &mut S, message: Any) -> Result<Vec<Self::Event>, Self::Error> {
        let message = Self::decode(message)?;
        Self::dispatch(store, message)
    }

    /// Similar to [ABCI InitChain method](https://docs.tendermint.com/master/spec/abci/abci.html#initchain)
    /// Just as with `InitChain`, implementations are encouraged to panic on error
    fn init(_store: &mut S, _app_state: serde_json::Value) {}

    /// Similar to [ABCI Query method](https://docs.tendermint.com/master/spec/abci/abci.html#query)
    fn query<'de, T: Deserialize<'de>>(
        _store: &S,
        _data: impl AsRef<u8>,
        _path: &Path, 
        _height: Height
    ) -> Result<T, Self::Error> {
        unimplemented!()
    }
}

Self-contained

Note that all Module trait functions are static. This means that modules are forced to depend on the 'master module' for access to the state. The 'master module' is responsible for making sure that modules are isolated and have exclusive access to their key-value store paths (described in detail in the store section below).

Module interaction

Note that modules are isolated from each other and unaware of the existence of other modules. They must depend on the master module for interacting with other modules.
TBD - define trait MasterModule? ics-025-handler-interface? ics-05-port-binding-as-module-manager?

Identifiable

We define the IdentifiableBy trait as below ->

pub(crate) trait IdentifiableBy<I: Sized + Eq + Hash> {
    fn identifier(&self) -> I;
}

This requirement is described in detail in ICS 5 - Data Structures ->

host state machine MUST support either object-capability reference or source authentication for modules.

The generic parameter may represent a pointer value (that is guaranteed to be unique) as in the case of the Cosmos SDK StoreKey implementation or an Ethereum smart-contract address or any such unique identifier type.

The identifier() function is purposely not clubbed into the Module trait and separated into its own trait because we MUST guarantee that every module has a unique identifier for a specified type. We could leverage build.rs scripts or procedural/derive macros to generate these identifiers at compile time.

Manipulatable

All supported modules are added to the SupportedModules enum ->

pub enum SupportedModules {
    Ibc(IbcModule),
    // ...
}

Installed modules are stored in a static array ->

lazy_static! {
    static ref INSTALLED_MODULES: [SupportedModules; 1] = [SupportedModules::Ibc(IbcModule::default())];
}

The master module is able to loop over all installed modules and decides which messages to dispatch to which module.
Although this approach might not seem ideal, it does avoid dynamic dispatch. Also, we could use procedural macros to avoid code duplication.

Store

According to ICS 24 - Key/value Store, the host state machine must provide a key/value store that provides the standard get, set and delete functionality. Note however that realistically, the get functionality must be provided for all heights of the blockchain.
ICS24 doesn't impose any particular storage backend or backend data layout.

Implementation

The Store trait is heavily influenced by the tendermock project's definition.

/// A newtype representing a bytestring used as the key for an object stored in state.
/// Must be validated in accordance with [ICS 24 - Path, Identifiers, Separators](https://github.com/cosmos/ibc/blob/0eba039ed65a66eace21124041d39be07ebfb69a/spec/core/ics-024-host-requirements/README.md#path-space)
pub struct Path(String);

/// Block height
pub type RawHeight = u64;

/// Store height to query
pub enum Height {
    Pending,
    Latest,
    Stable(RawHeight), // or equivalently `tendermint::block::Height`
}

/// Store trait - maybe provableStore or privateStore
pub trait Store {
    /// Error type - expected to envelop all possible errors in store
    type Error: std::error::Error;

    /// Set `value` for `path`
    fn set(&mut self, path: &Path, value: Vec<u8>) -> Result<(), Self::Error>;

    /// Get associated `value` for `path` at specified `height`
    fn get(&self, height: Height, path: &Path) -> Option<Vec<u8>>;

    /// Delete specified `path`
    fn delete(&mut self, path: &Path);

    /// Commit `Pending` block to canonical chain and create new `Pending` 
    fn commit(&self) -> Vec<u8>;

    /// Prune historic blocks upto specified `height`
    fn prune(&self, height: RawHeight) -> Result<RawHeight, Self::Error> {
        Ok(height)
    }

    /// Return the current height of the chain
    fn current_height(&self) -> RawHeight;
}

The store trait maybe extended with provided methods such as ->

fn get_value<T: FromBytes>(&self, height: Height, path: &Path) -> Result<T, Error> {
    self.get(height, path).try_into()
}

fn get_pending(&self, path: &Path) -> Option<Vec<u8>> {
    self.get(Height::Pending, path)
}

fn get_latest(&self, path: &Path) -> Option<Vec<u8>> {
    self.get(Height::Latest, path)
}

fn get_at_height(&self, height: RawHeight, path: &Path) -> Option<Vec<u8>> {
    self.get(Height::Stable(height), path)
}

A provableStore must additionally implement the following methods ->

pub trait ProvableStore: Store {
    /// Return a vector commitment 
    fn root_hash(&self) -> Option<tendermint::Hash>;

    // Return proof of existence for key
    fn get_proof(&self, key: &Path) -> Option<ics23::CommitmentProof>;
}

The tendermock project has a AVL tree based store implementation that we could reuse.

provableStore and privateStore

Additionally, host state machines are required to provide two instances of the above interface -

a provableStore for storage read by (i.e. proven to) other chains, and a privateStore for storage local to the host, upon which get, set, and delete can be called, e.g. provableStore.set('some/path', 'value').

The provableStore is required to write to a key/value store whose data can be externally proved with a ICS 23 - vector commitment and must use canonical proto3 data structures.
For the current implementation, we only provide a single instance of a provableStore and Paths that are meant to use the privateStore may also use it. IIUC, this is also how the cosmos-sdk store is currently implemented. Another way to implement this is to allow modules to have state and make Module trait functions non-static by giving them access to self. Modules can then use their state as the privateStore. eg. struct FooModule(FooModulePrivateStore).

Permissioning

Modules are expected to have exclusive access to their Paths.

This can possibly be implemented as a sub-store (prefixed key-space) of a larger key/value store used by the entire state machine.

One way to implement this would be to have an IdentifiableBy<ics24::Identifier> impl for all modules and use that identifier as the sub-store prefix. The master module is expected to guarantee exclusive access of store module paths to modules.

Proxy stores

Host state machines may implement "proxy stores" with path & value mappings which do not directly match the path & value pairs set and retrieved through the store interface — paths could be grouped into buckets & values stored in pages which could be proved in a single commitment, path-spaces could be remapped non-contiguously in some bijective manner, etc — as long as get, set, and delete behave as expected and other machines can verify commitment proofs of path & value pairs (or their absence) in the provable store. If applicable, the store must expose this mapping externally so that clients (including relayers) can determine the store layout & how to construct proofs. Clients of a machine using such a proxy store must also understand the mapping, so it will require either a new client type or a parameterised client.

TBD - implementation details

Concurrency

Rust's preferred way to do concurrency is to use the Monitor pattern with RAII scoped lock guards. One thing to note about this approach is that often there is room for optimizing the granularity of locking.
For example, we could optimize the current implementation of the Store (i.e. BaseCoinState) by using atomic types (e.g. std::sync::atomic::AtomicU64) for the height and having the RwLock on the Store itself. This would allow us to access the height without having to acquire the lock on the store and starve other Store readers/writers. So instead of this ->

pub struct BaseCoinApp {
    state: Arc<RwLock<BaseCoinState>>,
} 

pub struct BaseCoinState {
    pub store: Store,
    height: i64,
}

We have this ->

pub struct BaseCoinApp {
    state: Arc<BaseCoinState>,
} 

pub struct BaseCoinState {
    pub store: RwLock<Store>,
    height: AtomicI64,
}

Partitioning

Ideally, we would like each module to be able to concurrently read/write to their path space. This should be possible because we know that modules are guaranteed exclusive access to their store paths, for example, if the storage was backed by a Vec<u8> we could partition it and use some unsafe code to allow multiple modules to write to their own partitions simultaneously without invoking UB. In practice, however, this would require modifying some of the trait methods described earlier.
TBD - implementation details

Write-ahead logging (WAL) v/s Shadow-paging

Write-ahead logging is a well-known technique for providing atomicity and durability guarantees in storage systems. The idea is to record all changes to 'stable storage' (i.e. a log) before applying them to the actual data store. The log usually records both redo and undo information and this technique allows for in-place data-store updates.
left-right - a popular Rust concurrency primitive uses a technique similar to WAL for achieving high concurrency reads over a single-writer data structure.

Another technique that provides the same guarantees as WAL but differs in its implementation is shadow-paging.

Shadow paging is a copy-on-write technique for avoiding in-place updates of pages. Instead, when a page is to be modified, a shadow page is allocated. Since the shadow page has no references (from other pages on disk), it can be modified liberally, without concern for consistency constraints, etc. When the page is ready to become durable, all pages that referred to the original are updated to refer to the new replacement page instead. Because the page is "activated" only when it is ready, it is atomic.

Note that these backends facilitate further concurrency related optimizations such as those described in Orga's concurrency model or those that rely on account validity predicates.

In the future, it would be nice to have interfaces that support backends that employ both these techniques.

Accounts

Since accounts may be shared between modules, we might want to create an accounts module that exposes an interface for other modules to interact with it. This could also be part of the so-called ModuleManager. Also, for a functional account system, we would need a nonce.
TBD - implementation details

[hu55a1n1]

The module set should be dynamic: chains should be able to add and destroy modules, which can themselves bind to and unbind from ports, at will with a persistent IBC handler.

• ICS 25 - Desired properties

So this basically means we cannot have a static list of installed modules as described above.

[soareschen]

Hey @hu55a1n1, great initiative putting the thoughts and design of how we should design the module system for BaseCoin, which can be served as the foundation for the design for cosmos-rs. Here are some of my suggestions to improve the design:

Design in Rust vs Go

I think the ICS specs serve as very good reference on the high-level architecture that we should aim for designing a good module system. On the other hand, the specific interface design tend to be specific to Go, and I think we can try and improve the design to make it more suited in Rust.

I feel that the reason the Go interface design is specified in English specs is because the Go type system is not strong enough to capture the high-level requirements for different Cosmos Go modules to interoperate. But if we can design Rust types/traits that directly capture the requirements, then it provides more flexibility on how different Rust modules can interoperate.

no_std Support

To support Substrate and also allow similar Wasm runtime in cosmos-rs blockchains in the future, we would want to avoid using std features and instead import from core and alloc. This would means that we want to avoid having std::error::Error used in the trait specifications.

Associated Types

I think the Store type can be specified as an associated type instead of a generic trait parameter. The main difference between the two approaches are that generic trait parameters allow one type to have many trait implementations of different generic parameters, while with associated types means that a type can have at most on implementation for that trait.

However, if a type itself is generic, then each of its specialized type can have different implementation of the trait. For demonstration, we can for example have an AccountModule that is implemented as follows:

trait Module {
    type Error;
    type Store;
    ...
}

struct AccountModule<S> { ... }

impl <S: Store> Module for AccountModule<S> {
    type Error = ...;
    type Store = S;
}

When there are a lot of type parameters, it is usually more ergonomic to specify them as associated types rather than generic parameters. This is because we can usually omit specifying the associated types, thereby making the code shorter.

Immutable State

One things I feel that we can improve from the Go design is to have immutable state values, rather than having a mutable store that is being passed around. With a mutable store, the state can be updated at any time, and it is difficult to tell whether a store/state correspond to a particular height, or has some temporary uncommitted state.

A better approach would be to define a State trait that requires types that implement it to always have immutable values. That way, when a function gets a State value, we can be confident that the key-value pairs in that state would never change.

Our State trait could be implemented as follows:

pub trait State<Path, Value>: Sized {
    type Error;

    fn has(&self, path: Path) ->
        Result<bool, Self::Error>;

    fn get(&self, path: Path) ->
        Result<&Value, Self::Error>;

    fn set(self, path: Path, value: Value) ->
        Result<Self, Self::Error>;

    fn remove(self, path: Path) ->
        Result<Self, Self::Error>
}

Notice that in the set and remove methods, the state value is consumed and a new state value is returned. We keep the Path and Value types as generic parameters, so that the same type can have different implementation of State for different sub-state. With this, we can for example define a simple state such as:

pub struct KeyNotFound;
pub struct SimpleState<Value>(HashMap<String, Value>);
impl <Value: Clone> State<String, Value> for SimpleState<Value>
{
    type Error = KeyNotFound;

    fn has(&self, path: String) ->
        Result<bool, Self::Error>
    {
        Ok(self.0.contains_key(&path))
    }

    fn get(&self, path: String) ->
        Result<Value, Self::Error>
    {
        let value = self.0.get(&path)
            .ok_or(KeyNotFound)?;
        Ok(value.clone())
    }

    fn set(mut self, path: String, value: Value) ->
        Result<Self, Self::Error>
    {
        self.0.insert(path, value);
        Ok(self)
    }

    fn remove(mut self, path: String) ->
        Result<Self, Self::Error>
    {
        self.0.remove(&path);
        Ok(self)
    }
}

It is also worth noting that although a state can appear to be immutable, behind the scene it can still be backed by a mutable data store, or external mutable database. We only requires that the value we get back from a state value always remain the same across multiple calls. This is also why we have all methods returning Result, so that in case if I/O error occurs when the value is retrieved from disk, the state can still return an error.

Prefixed State

The design of the State trait allows us to segment the state into different namespaces to be accessed by different modules. For example, we can implement a PrefixedPath type as follows:

pub trait Prefix {
    fn prefix() -> &'static str;
}

pub struct PrefixedPath<Prefix, Path>{
    path: Path,
    phantom: PhantomData<Prefix>
}

impl <P: Prefix, Path: Display>
    ToString for PrefixedPath<P, Path>
{
    fn to_string(&self) -> String {
        format!("{}/{}", P::prefix(), self.path)
    }
}

Basically, a type implementing Prefix is a proxy type that represents a static string at the type level. We then have a PrefixedPath type that wraps a Path type with a given prefix. Finally, we have a method prefixed_string that converts a PrefixPath to a string. As an example, if we have a prefix type AccountPrefix

struct AccountPrefix;
impl Prefix for AccountPrefix {
    fn prefix() -> &'static str {
        "account"
    }
}

then calling <PrefixedPath<AccountPrefix, String>>::new("foo").to_string() will give us "account/foo".

Using the Prefix trait, we can then implement namespaced state for SimpleState as follows:

impl <P: Prefix, Value: Clone>
    State<PrefixedPath<P, String>, Value>
    for SimpleState<Value>
{
    type Error = KeyNotFound;

    fn has(&self, path: PrefixedPath<P, String>) ->
        Result<bool, Self::Error>
    {
        Ok(self.0.contains_key(&path.to_string()))
    }

    fn get(&self, path: PrefixedPath<P, String>) ->
        Result<Value, Self::Error>
    {
        let value = self.0.get(&path.to_string())
            .ok_or(KeyNotFound)?;
        Ok(value.clone())
    }

    fn set(mut self, path: PrefixedPath<P, String>, value: Value) ->
        Result<Self, Self::Error>
    {
        self.0.insert(path.to_string(), value);
        Ok(self)
    }

    fn remove(mut self, path: PrefixedPath<P, String>) ->
        Result<Self, Self::Error>
    {
        self.0.remove(&path.to_string());
        Ok(self)
    }
}

Mutable Store

With the design of immutable state, we can then seperate the concern of multi-version nature of blockchains with a mutable store. The store would allow us to retrieve the state of the chain in a past height, as well as commit a new state to a new height.

pub trait Store {
    type Error;

    type State;

    type Height: Height;

    fn current_height(&self) -> Self::Height;

    fn current_state(&self) -> Result<Self::State, Self::Error>;

    fn get_state_at(&self, height: Self::Height) ->
        Result<Self::State, Self::Error>;

    fn commit(&mut self, state: Self::State) ->
        Result<(), Self::Error>;

    fn prune_state_at(&self, height: Self::Height) ->
        Result<(), Self::Error>;
}

The design of Store is as follows:

• A store has a current height, and a current state at that height.
• We can retrieve the state of the store at a previous height.
• Since the state value is immutable, the store provides the guarantee that two state values obtained at the height are always the same.
• We can commit a new state to the store to increment its height and set the given state at that height.
• It is worth noting that the associated State type in Store does not implement the State trait. We instead let individual modules impose that requirement

Abstract Height

From the experience of developing ibc-rs and tendermint-rs, we also want the height type to be abstract so that we cannot accidentally mix up two heights coming from different stores. The Height trait provides methods to make an abstract height type isomorphic to u64:

pub trait Height: Sized {
    type Error;

    fn to_raw_height() -> u64;

    fn increment(self) -> Self;

    fn from_raw_height(height: u64) -> Result<Self, Self::Error>;
}

Serialization Lifting

I feel that modules should be implemented without explicit serialization of their data structures. This gives us flexibility to try out alternative serialization strategies, such as switching from protobuf to CBOR or other representations.

In functional programming, there is a technique called lifting that allows us to lift a lower-level interface into a higher level interface.

For example, we may have a state type that stores the values as raw bytes, such as SimpleState<Vec<u8>>. For such a state, it is possible to wrap that state to provide state access to serialized data structures.

pub struct SerializeState<State, Value> {
    state: State,
    phantom: PhantomData<Value>,
}

impl <State, Value> SerializeState<State, Value> {
    pub fn new(state: State) -> Self {
        SerializeState { state, phantom: PhantomData }
    }
}

impl <S, E, Path, Value> State<Path, Vec<u8>>
    for SerializeState<S, Value>
where
    S: State<Path, Value, Error=E>,
    Value: TryFrom<Vec<u8>, Error=E>,
    Value: TryInto<Vec<u8>, Error=E>,
{
    type Error = E;

    fn has(&self, path: Path) ->
        Result<bool, Self::Error>
    {
        self.state.has(path)
    }

    fn get(&self, path: Path) ->
        Result<Vec<u8>, Self::Error>
    {
        let value = self.state.get(path)?;
        Ok(value.try_into()?)
    }

    fn set(self, path: Path, value: Vec<u8>) ->
        Result<Self, Self::Error>
    {
        let state = self.state.set(path, value.try_into()?)?;
        Ok(Self::new(state))
    }

    fn remove(self, path: Path) ->
        Result<Self, Self::Error>
    {
        let state = self.state.remove(path)?;
        Ok(Self::new(state))
    }
}

Here I use TryFrom<Vec<u8>> for simple demonstration purpose. You can imagine that we can do the same lifting with protobuf encoding/decoding operations. With this approach, we can decouple the implementation-specific details of serializing and deserializing data structures, and focus on the core application logic itself.

Transaction Handler

The design of Module actually consist of two aspects: transaction handling and querying. I think it is better to separate them into two separate traits, and here I will focus on the TransactionHandler trait.

Based on the design of State above, I suggest that we can instead implement the TransactionHandler trait as follows:

pub trait TransactionHandler: Sized {
    type Error;

    type State;

    type Message;

    type Event;

    fn check(&self, state: &Self::State, message: Self::Message) ->
        Result<(), Self::Error>;

    fn dispatch(&self, state: Self::State, message: Self::Message) ->
        Result<(Self::State, Vec<Self::Event>), Self::Error>;
}

At the most basic level, a transaction handler handles transaction messages contained in the Message type, update the State, and returns a list of Event.

Here again, we leave the associated types abstract, and we can again use the lifting technique to add additional functionality such as serialization:

pub struct SerializeTransactionHandler<H> {
    handler: H
}

impl <H, E> TransactionHandler for SerializeTransactionHandler<H>
where
    H: TransactionHandler<Error = E>,
    H::Event: TryInto<AbciEvent, Error = E>,
    H::Message: TryFrom<Any, Error = E>,
{
    type Error = E;

    type State = H::State;

    type Message = Any;

    type Event = AbciEvent;

    fn check(&self, state: Self::State, message: Self::Message) ->
        Result<(), Self::Error>
    {
        let in_message = message.try_into()?;
        self.handler.check(state, in_message)
    }

    fn dispatch(&self, state: Self::State, message: Self::Message) ->
        Result<(Self::State, Vec<Self::Event>), Self::Error>
    {
        let in_message = message.try_into()?;
        let (state, mut events) =
            self.handler.dispatch(state, in_message)?;
        let mut out_events = vec![];
        for event in events.drain(0..) {
            let out_event = event.try_into()?;
            out_events.push(out_event);
        }
        Ok((state, out_events))
    }
}

Above we define a SerializeTransactionHandler wrapper that wraps the original handler H and perform encoding operations from H::Event to AbciEvent, and decoding operations from prost_types::Any to H::Message.

With this separation of concern, the actual transaction handler can focus on the application logic, rather than lower-level aspects such as I/O and decoding. This would also allows us to more easily test the core logic, without being distracted by the additional details.

We can also use the same lifting techniques for other things, such as wrapping a module with a Prefix so that it is guaranteed that a module implementation can only access a prefixed sub-space of a state.

More to Come

There are other things such as the design of proof verification which I haven't cover here. But since this has been long enough, I am posting this first and will post another thread for further feedback.

I hope the suggestions make sense. Do let me know if you are confused on anything, or unsure of how to do certain operations with this design!

[hu55a1n1]

Thanks so much @soareschen! 🙏 This is the sort of feedback I was hoping for! You describe some very interesting ideas and I will write a more detailed reply soon.