Storage redesign

[PopcornPaws]

Intermezzo on storage

Storing stuff on-chain, under consensus is not very effective and may incur large costs on the runtime. Thankfully, substrate has the option to consistently store large amounts of data in the offchain local storage of the nodes using offchain indexing. The great thing about offchain indexing is that the runtime can write transaction data to the local storage without invoking any offchain worker. It is ensured that off-chain data is consistent among nodes running with the --enable-offchain-indexing flag. We can still store data hashes on-chain that can be used to verify data stored in off-chain storage. This allows validators with limited storage to still join the network (they can run their nodes without the --enable-offchain-indexing flag, thus they won't have all data in their local storage but can still help in verifying data integrity.

Implementing this requires a bit of thought, because off-chain storage only allows writing to it and clearing data. Thus, the runtime cannot read from the off-chain storage. Furthermore, writing to the off-chain storage from runtime is only available through a limited api, i.e. setting a key-value pair.

Intermezzo on requirement types

Static requirements

Free and Allowlist requirements are kind of unique in the sense that they don't require external data retrieval for verification, contrary to balances, number of followers on a platform, etc. Therefore, it might make sense to handle them separately, that is, introduce a static vs dynamic distinction between requirements that don't require external verification data (thus they are verifiable on-chain) and requirements that do require oracle access to off-chain verification data.

This distinction would allow the following requirement setups:

• Free (standalone, cannot be bundled with anything else)
• Allowlist (standalone allowlist that's not bundled with anything else)
• AllowlistWithDynamicRequirements (an Allowlist with AND/OR connection to an arbitrary set of dynamic requirements that require oracle access)
• DynamicRequirements (arbitrary set of dynamic requirements that require verification data retrieved by an oracle)
  In either case, Free and Allowlist would be evaluated on-chain, and only the dynamic requirements would be delegated to oracles. Allowlists would have an optional negation flag that, if enabled, turns the allowlist into a "disallowlist".

Dynamic requirements

As for dynamic requirements, they have the following structure:

• they need to describe the source of the verification data required to evaluate them
• they need to provide (either implicitly or explicitly) parameters to retrieve the data
• they need to have a Relation defined that can be checked whether it's satisfied by the retrieved verification data

A Relation can be thought as something like:

pub enum Relation<T> {
    EqualTo(T),
    GreaterThan(T),
    GreaterOrEqualTo(T),
    LessThan(T),
    LessOrEqualTo(T),
    Between(core::ops::Range<T>),
}

impl Relation {
    pub fn assert(&self, vd: VerificationData) -> bool {
        ...
    }
}

Thus, a dynamic requirement is satisfied if the respective Relation is asserted to be true on the retrieved verification data.

Allowlists in storage

Allowlists are special in the sense that their size can be much larger than other requirements, because they may contain 50k+ addresses which (if we consider a 20 byte Ethereum address) results in data in the size of Megabytes. It is important that the Wasm runtime has an upper limit of 32 MB for allocated memory. After testing the runtime, it accepted 100k entries in an allowlist, but rejected one with 200k entries.

Nevertheless, if we can at least store allowlists in the off-chain storage as a merkle tree and store only it's hash on-chain, we wouldn't have to worry about bloating consensus data. However, on-chain allowlist-verification would be impossible (because the runtime cannot read from the off-chain storage) and modifying the allowlist would be tricky. If we store a merkle root of an allowlist merkle tree, however, we could ask for a merkle proof provided by the user and maybe verify that on-chain using the merkle root only.

Originally posted by @PopcornPaws in #63 (comment)

[PopcornPaws]

Before benchmarking and publishing the chain, the following has to be finished:

• allowlists should be handled as a merkle tree
  • p.o.c. was successfully tested
  • integrate into the guild pallet
  • handle Free and Allowlist separately from other requirements
  • add NOT flag to Allowlist
• identities should be checked on-chain
  • use MultiAddress and MultiSignature from sp-runtime to verify signatures on-chain