At the end of December 2019, I left Parity to write a voting library with substrate, sunshine. The project is supported by a grant from the Web3 Foundation.

I’ve enjoyed the freedom of exploring substrate without immediate guidance. I stopped trying to find “the right way” to express things and started to just try stuff out. In the process, I’ve learned a few things. This post covers highlights. I’ll add to it over time.

Constant-Time Membership Checks

You can store an unordered set of (Key, Value) pairs in substrate as

map Key => Value

So lots of code that I’ve seen used to store sets looks like

map GroupId => Vec<AccountId>

Checks to see if an AccountId is in a group will use the GroupId as the key, calling GET(GroupId) on the map to retrieve the Vec<AccountId> and then binary search on the elements (so worst-case lookup is logN for set size N). This is definitely more space efficient than what I’m proposing:

Store all elements of the set in the key space so that we can leverage the hash function’s constant-time lookups for membership checks of the set

double_map GroupId, AccountId => bool

To check if an account is a member of the group, call GET(GroupId, AccountId) and it returns true if the member was added and false if it has not been set (because bool::default() == false). Note that we have to write methods that set this to true when new members are added The commits around this comment show how I refactored the modules to take advantage of this pattern.

As mentioned before, this pattern is less space efficient and runs the risk of exhausting the keyspace. Sounds like a good ole tradeoff!

On-Chain Treasury for Every Group

The bank-onchain module intends to implement logic similar to frame/treasury, but, instead of only supporting a single treasury, bank-onchain supports an arbitrary number of treasuries, one for each organization that registers an on-chain bank account.

This works just like frame/treasury, but it provides a way to generate a unique joint account identifier for every group that registers an on-chain bank account. This code is in modules/util/bank.rs:

#[derive(Clone, Copy, Eq, PartialEq, Default, Encode, Decode, sp_runtime::RuntimeDebug)]
pub struct OnChainTreasuryID(pub [u8; 8]);

impl OnChainTreasuryID {
    pub fn iterate(&self) -> OnChainTreasuryID {
        let old_inner = u64::from_be_bytes(self.0);
        let new_inner = old_inner.saturating_add(1u64);
        OnChainTreasuryID(new_inner.to_be_bytes())
    }
}

impl TypeId for OnChainTreasuryID {
    const TYPE_ID: [u8; 4] = *b"bank";
}

We enforce uniqueness in the context of the keyspace for the BankStore map.

// in decl_storage block of bank-onchain/src/lib.rs
BankStores get(fn bank_stores): map
    hasher(opaque_blake2_256) OnChainTreasuryID => Option<BankState<_, _>>;

So, the uniqueness check trait impl looks like

impl<T: Trait> IDIsAvailable<OnChainTreasuryID> for Module<T> {
    fn id_is_available(id: OnChainTreasuryID) -> bool {
        <BankStores<T>>::get(id).is_none()
    }
}

and unique id generation looks like

impl<T: Trait> GenerateUniqueID<(OnChainTreasuryID, BankMapID)> for Module<T> {
    fn generate_unique_id(
        proposed_id: (OnChainTreasuryID, BankMapID),
    ) -> (OnChainTreasuryID, BankMapID) {
        if !Self::id_is_available(proposed_id.clone()) {
            let mut new_id = proposed_id.1.iterate();
            while !Self::id_is_available((proposed_id.0, new_id.clone())) {
                new_id = new_id.iterate();
            }
            (proposed_id.0, new_id)
        } else {
            proposed_id
        }
    }
}

Just like in frame/treasury, the joint account identifier can define spends as the outcome of on-chain governance processes. This allows us to design a bank account permissioned by whatever governance we configure. Pretty exciting!

Right now, I’m doing a refactor of this module in this PR but once it’s done, I’ll have more to share.

Module Inheritance

I separate out functionality for group membership into

  • membership (flat organization group)
  • shares-membership (flat shares subgroup)
  • shares-atomic (weighted shares subgroup)

These modules are combined into a single coherent interface in the sunshine-org module, which is inherited by bank-onchain. The output if you run cargo tree in bank-onchain shows the inheritance hierarchy

sunshine-bank-onchain v0.0.1
├── sunshine-org v0.0.1
│   ├── sunshine-membership v0.0.1
│   │   └── sunshine-util v0.0.2
│   ├── sunshine-shares-atomic v0.0.1
│   │   ├── sunshine-membership v0.0.1
│   │   └── sunshine-util v0.0.2 
│   ├── sunshine-shares-membership v0.0.1
│   │   ├── sunshine-membership v0.0.1
│   │   └── sunshine-util v0.0.2 
│   └── sunshine-util v0.0.2 
└── sunshine-util v0.0.2 

We are inheriting module behavior through types in each module’s Trait object so, while adding more depth does hurt compile times, it doesn’t add any runtime cost. This is because Rust performs monomorphization on this code to fill in the specific types at compile time.

Application Architecture

David and I spent two weeks in Buenos Aires at the beginning of March. During that time, we had many late night (early morning?) discussions about local-first software architectures enabled by a maturing Rust ecosystem.

As mentioned in this comment, mobile application constraints require a single backing database instead of two databases. Likewise, the sunshine mobile application will share its backing sled db between the light client and an embedded ipfs node. It’s pretty badass ;)

We’re also using Rust FFI to talk directly between the light client and the Flutter Dart interface (so we have no dependency on polkadot-js). Props go to Shady Khalifa for configuring cargo make and writing a nice template for anyone else interested in Rust to Dart FFI.