IStore and BlockChain<T> specification

[greymistcube]

As per usual, I blame my lack of writing skills for this seeming like a rant. Also keep in mind, I have absolutely no experience dealing with database. 😗

Case Study

Interface IStore suggests, and is also capable of, storing different chain id's and genesis blocks. I understand this is a design decision to keep business logic out of IStore as much as possible, but my belief is that this might be a case of too much abstraction.

Let's assume BlockChain<T> objects and developers responsible for handling IStore are diligent enough to have a canonical chain id set for IStore whenever at least one genesis block (any Block<T> with index 0) is inserted to IStore ¹²³⁴.

When creating a BlockChain<T> object, let the constructor take in IStore $S$ and genesis Block<T> $g$ and some chain id $id$. Consider the following cases:

• $g \in S$ and $id \in S$: This is equavalent to simply loading $S$.
  • $g = g_{id}$: BlockChain<T> is loaded normally.
  • $g \neq g_{id}$: This results in failure due to genesis mismatch.⁵
• $g \in S$ and $id \notin S$: This is mostly used to introduce a new chain id to $S$ within the network.
  • If inFork flag is set to true, this simply adds $id$ to $S$ with $0$ index appended to $id$.
  • If inFork flag is set to false, then this actually tries to append $g$ to the BlockChain<T> normally.
• $g \notin S$ and $id \in S$: This shouldn't normally happen.⁶⁷
  • $g_{id} \in S$ and $g \neq g_{id}$: This results in failure due to genesis mismatch.
  • $g_{id} \notin S$: This means for whatever reason, $id$ was introduced to $S$ but no genesis was attached to it.
    • If inFork flag is set to true, then $g$ is added to $S$ and $0$ index gets appended to $id$.
    • If inFork flag is set to false, then $g$ is evaluated and appended normally.
• $g \notin S$ and $id \notin S$: This can be used to introduce a new "network chain" to $S$.
  • Then again, the behavior is dictated by the inFork flag whether to simply append index $0$ to $id$ or to evaluate $g$.

On top of all this, the end result may also differ depending on whether $S$ had $id_{0}$ set in the first place with $g_{id_{0}}$ or not.

Issues

Perhaps I'm too dumb to be sure to know where to even start untangling this (or maybe I just lack the understanding to see that everything is actually just peachy), but I still see several issues:

• We need to be clear on whether IStore should be a multi-network-chain or not. If the former, then in my opinion, canonical chain ids should be tied to genesis hashes (that is, there should be a dictionary mapping from genesis hashes to canonical chain ids). Arbitrary decision to set canonical chain ids inside BlockChain<T>'s code, notably in BlockChain<T>() and BlockChain<T>.Swap() are problematic. This allows BlockChain<T> to "hijack" other network's canonical chain id.
  • Some guardrails are in place to prevent talking with other network's node with a different genesis, but no such obvious guardrails are present for possibly locally juggling different network geneses.
  • As far as I know, the entire codebase is devoid of network (i.e. genesis) selecting/switching API.
  • The end result and whether there is any side effect for creating a BlockChain<T> object depends on too many things.
  • Probably the only thing we can be sure of a successfully created BlockChain<T> object is that it has a chain id and some genesis block inside an IStore, possibly newly created or possibly loaded.⁸ We'd pretty much need a table to explain when and how a BlockChain<T> object can be created and what it did to IStore (and/or IStateStore) with given arguments.
• There is a severe lack of data integrety enforcement. This is partly due to making no assumptions about IStore. I have talked a bit on this subject with @longfin, but I'm still on the side of adding some constraints on IStore methods.
  • Falling short of that, there at least needs to be a scheme on how IStore should be managed by Swarm<T> and BlockChain<T>. I understand the argument for keeping things abstract and free of constraints for extensibility down the line, but assume nothing and deal with everything cannot be the answer just because "we might need it someday" or "we can't control everything".

  • I could do the entire thing with only one table: Give it a numeric primary key and a large text field, and programs can parse and populate the text field with whatever data they need, in appropriate formats.⁹

  • It is not even clear which should take precedence, $g$ or $id$. Given both $g$ and $id$, BlockChain<T> tries too many different things. On the conceptual level, as a network selection argument, $g$ should take precedence over $id$. That is, any $id$ that is not compatible with $g$ should be rejected. However, on the storage level (and in implementation), $g_{id}$ is reliant on $id$, which makes the precedence order muddied.
    • If $id \in S$, normally $g_{id} \in S$ takes precedence over $g$. That is, $g$ is rejected if different from $g_{id}$.
      • However, if $id \in S$ and $g_{id} \notin S$, $g$ takes precedence over non-existant $g_{id}$.
    • If $id \notin S$, then $g$ is assigned as $g_{id}$. That is, $g$ takes precedence over non-existant $g_{id}$.

Closing Thoughts and Suggestions

Some thoughts and ideas:

• We can check the integrity of an IStore during load and make sure it satisfies certain properties.
  • It could be on IStore, Swarm<T>, or BlockChain<T> level. All have pros and cons.
  • The smallest step We can probably take is to check all chain ids in IStore to make sure none are empty. Although using only provided methods for IStore interface does not allow this to happen, whether to allow underlying database to have empty chain ids is a different issue.
• Make BlockChain<T> and chain id handling more explicit.
  • Make BlockChain<T> only load valid $g$, $id$, and $S$ tuple. Reject all cases where $id \notin S$ or $g \notin S$. If this fails, either $S$ is corrupted or the caller has made a mistake.
  • As far as I am aware, aside from initial "netowrk" BlockChain<T> creation (creating a brand new BlockChain<T> using an "empty" IStore), there is only one place where chain id creation is needed, namely Fork(). Fork() method can prepair in advance for the forked BlockChain<T>.
• Make IStore.GetCanonicalChainId() to take a genesis Block<T> as an argument. This would require some migration. Similarly, IStore.SetCanonicalChainId() should take a genesis Block<T> as an argument. On the other hand, IStore.GetCanonicalGenesisBlock() should probably be removed.

Footnotes

1. Note that we only assume the canonical chain id to be set if some genesis $g$ is introduced to $S$. This does not assume that $S$ will have $id_{0}$ and $g_{id_{0}}$ by default. ↩

2. I have no way of actually knowing the intention as this is all handled by business logic, which is only implicitly known by the code for BlockChain<T>'s constructor. ↩

3. Although seemingly reasonable, at least for me, this is a rather strong assumption, as IStore does not signal much intention for its use. ↩

4. This is partly due to the fact IStore does not provide a method to unset an already set canonical chain id. ↩

5. The error message currently in BlockChain<T>'s constructor is not worded properly. The exception can be raised simply due to a mismatch between $id$ and $g$ and has nothing to do with "the network's genesis". BlockChain<T> should not be concerned with whatever network expects. ↩

6. Since there is no data integrity enforcement mechanism and as BlockChain<T> has seemingly no opinion about it, it tries to deal with it anyway. In my opinion, this should simply result in failure as existance of $id$ in $S$ without $g$. ↩

7. Then again, we need to consider this case "just in case" because we want to allow "empty" chains. ↩

8. I still can't confidently say even this seemingly simple fact is true for all possible combinations of arguments after a rather long deliberation. I've probably made atleast a mistake or two laying out the cases. ↩

9. Sarcastic quote taken from too much abstraction page. ↩

[greymistcube]

Discussion

The usual warning is that this is heavily biased towards my own opinion. 😗

Based on today's discussion, I think it is apt to ask the following questions:

• Is IStore completely network agnostic in the sense that it is meant to store every and any blocks from any network?
  • If the answer is yes, then how do we identify which blockchain to load from IStore? Regardless of implementing an additional layer between current BlockChain<T> and IStore, there needs to be an identifying information, be it genesis¹ or not, in order to properly load the wanted blockchain from IStore.
  • In my opinion, this runs into a problem of requiring more unnecessary structure just to support possibly never-to-be-used cases. Network identifying information would have to be attached to either a genesis or a chain id²³.
  • Another complicating issue is that Block<T>s are genesis agnostic (at least on the surface level⁴) but Transaction<T>s are genesis relevant. Schematically an IStore would look something like the diagram below for a multi-network storage. Besides being rather unintuitive for most users, dealing with orphaned Block<T>s may become an issue. For example, for a single-network storage, if we want to prune unnecessary Block<T>s, by assuming all Block<T>s belong to the network for the storage at hand, we can simply remove all Block<T>s that is not part of a chain we want to keep. On the other hand, for a multi-network storage, it is impossible to know whether an orphaned Block<T> is needed by a different network or not from a single network's perspective, requiring to compare each Block<T> to an aggregate of networks.
  • If the answer is no but we want to support multi-genesis IStore, then what is the purpose? From IStore level, this suggests genesis switching is allowed. Besides, to load a proper blockchain, something akin to a "network indentifier" mentioned above would be required. Other than semantic difference, I don't see much of syntactic difference that this would make.
• Can IStore be network/blockchain agnostic? Should IStore be network/blockchain agnostic? What does it mean to be network/blockchain agnostic anyway?
  • In my opinion, IStore as a data structure, enforcement of types and/or relations are already assuming quite a bit about how blockchains are going to be handled.
    • For instance, a simple index to BlockHash mapping puts following constraints:
      • Each index is tied to a unique BlockHash.
      • Indices are ordered and must be the full range from $0$ to some number $n$.
    • As such, I don't particularly see this kind of constraint being anything "special" compared to say being able to hold only one genesis block and/or chain id having to be tied to a genesis block.
  • By its nature, I understand there is no realistic way to guarantee the data integrity of IStore. However, this isn't to say that IStore should not provide any scheme on how it should be used.
  • Take IStore.AppendIndex() for an example. In its description, it assumes the Block<T> corresponding to given hash argument is already stored. However, it does not assume the corresponding Block<T> would be the next Block<T>.
    • This means the responsibility of indexing BlockHashes is delegated to the caller.
    • Realistically, we can't possibly check during instantiation of a BlockChain<T> that all Block<T>s have the right indices.
    • If we are to be rigorous, however, we'd have to know every breaking consequences of having an invalid BlockChain<T>. Meaning, either during retrieval of each Block<T> we need to check if the retrieved Block<T> does indeed have the right index or design every method for handling Block<T>s and BlockChain<T>s that retrieved Block<T>s might have invalid indices. I don't see either being particularly a realistic solution.
    • Thus, the current state being, we haphazardsly assume that BlockChain<T> operates under the assumption whoever used IStore.AppendIndex() has done so responsibly. But this is not guaranteed anywhere explicitly. In order to be confident, we have to track down every piece of code calling IStore.AppendIndex() and understand that such property is implicitly enforced⁵.
    • We can at least put a warning sign that says "use with caution", but the problem remains as to if something ever goes wrong, it is hard to know when the offending action has taken place and when and where we will see that something has gone wrong as long as IStore provides means to make itself invalid⁶.
    • On the other hand, we can put a different warning that IStore does not guarantee any kind of data integrity. I think this would require to put such warning on most, if not all, methods for IStore. I don't think this would make usages of IStore any easier and I don't see the point in doing so.
• Is this discussion moot if we are to remove chain reorg and/or chain ids?
  • Again, my opinion on the matter is that it is highly unlikely to be irrelavent.
    • The problem of juggling chain ids is only a part of a larger issue.
    • It might not be as easy as we think to remove them without entirely overhauling IStore, which in and of itself may be costly.
    • Removal of chain ids might make redesigning IStore somewhat easier, but many of the questions asked here still need to be answered⁷ when designing a new IStore.

Diagrams

In below diagrams, subgraphs transactions and blocks correspond to orphaned transactions and orphaned blocks, i.e. not part of a chain.

Multiple Network Storage

flowchart
  subgraph Store
  direction BT
    subgraph Network 1
    direction BT
      subgraph Chain 1
      direction TB
        b1,0 --> b1,1
        b1,1 --> b1,2
        b1,2 --> b1,3
        b1,2 --> b'1,3
        b1,3 --> b1,4
      end

      subgraph Transactions 1
      direction LR
        to1,1
        to1,2
        to1,3
      end
    end

    subgraph Network 2
    direction BT
      subgraph Chain 2
      direction TB
        b2,0 --> b2,1
        b2,1 --> b2,2
        b2,2 --> b2,3
        b2,2 --> b'2,3
        b2,3 --> b2,4
      end

      subgraph Transactions 2
      direction LR
        to2,1
        to2,2
        to2,3
      end
    end

    subgraph Blocks
    direction RL
      bo1
      bo2
      bo3
      bo4
    end
  end

Loading

Single Network Storage

flowchart
  subgraph Store
  direction BT
    subgraph Chain
    direction TB
      b0 --> b1
      b1 --> b2
      b2 --> b3
      b2 --> b'3
      b3 --> b4
    end

    subgraph Transactions
    direction LR
      to1
      to2
      to3
    end

    subgraph Blocks
    direction LR
      bo1
      bo2
      bo3
      bo4
    end
  end

Loading

Footnotes

1. This is how it is implemented currently. ↩

2. Even if we are to move to PBFT with an "ideal" backend doing away with chain ids, network identifier would still be required somewhere. ↩

3. If we don't want to use a genesis as network identifier, then we need to create something else. ↩

4. This is due to Block<T> objects being heavily validated when getting appended to a blockchain. Implicitly, if given Block<T> started with a different genesis, it would not be appendable to the chain held locally. ↩

5. I don't see how this is solved by simply putting another layer between BlockChain<T> and IStore due to public facing nature of IStore. Perhaps if we are to split IStore into IReadOnlyStore and IWritableStore, but to allow various implementations, both would still have to be public (interfaces are meant to be public anyway) and there is no stopping from any actor misusing a provided method. ↩

6. However, I'm not entirely against this method suggested by @dahlia. I think it's the least we can do. ↩

7. Due to differences that might arise, we might even come to a different conclusion on these questions, but must be considered long and hard nonetheless. I'm afraid by simply kicking the can down the road we might make an oversight of these considerations. ↩

[greymistcube]

Redesign and Constraints

On even further thought, seems like the crux of the problem is treating network and/or local "metainfo" the same as other rudimentary entities such as Block<T>s and Transaction<T>s. With this in mind, I propose the following:

• IStore should still act as a simple key-value dictionary for all and any Block<T>s and Transaction<T>s where a Block<T> can be retrieved with its BlockHash and a Transaction<T> can be retrieved with its TxId.
  • Moreover, there should be no performance degradation in terms of inserting and retrieving Block<T>s and Transaction<T>s. This means, IStore.PutBlock(), IStore.GetBlock(), IStore.PutTransaction(), IStore.GetTransaction() should be left intact.
• IStore should treat network and/or local "metainfo" as managed resources. Any newly introduced constraints should only apply to these.
  • For example, network metainfo includes the genesis Block<T> used by the network. Once this is set in IStore, said IStore will only be usable practically for the given network using the same gensis Block<T>.
  • On the otherhand, local metainfo includes the set of chain ids and the canonical chain id.
  • In order to manage these sensibly, we introduce the following constraints:
    • IStore should have its genesis Block<T>, which is part of network metainfo, set before any chain ids, which is part of local metainfo, can be added¹.
    • All chain ids added to IStore must have the same gensesis Block<T> as the genesis Block<T> set for the IStore.
    • Once the network's genesis Block<T> is set, it should not be possible to change to another Block<T>².
    • It should not be possible to set the canonical chain id to a chain id already not in IStore³.
  • If we have managed IStores well enough, pre-existing IStores should be in a reachable state even with the rules above.
    • For example, the current implementation allows adding chain ids without any regard to the network's genesis. Theoretically, this means IStore can contain chain ids with different genesis Block<T>s. However, if we've managed to responsibly access IStore through BlockChain<T> objects with properly managed genesis Block<T>, pre-existing chain ids should point to the same genesis Block<T>⁴.

Formulation

Store State $S$

Let store state be respresented as $S = (\Gamma, g)$ where

• $\Gamma$ is a set of chain ids⁵.
• Canonical genesis hash $g \in \lbrace\texttt{null}\rbrace \cup \mathcal{H}$ where $\mathcal{H}$ is the set of all hashes.

A chain id is defined as any map $\gamma: H \to \mathbb{N_{0}}$ where

• $H \subseteq \mathcal{H}$ and $H \neq \varnothing$.
• $p \neq q \implies \gamma(p) \neq \gamma(q)$
• $\gamma(H) = \lbrace 0, \dots, n \rbrace$ for some $n \in \mathbb{N_{0}}$⁶.

Let legacy store state be defined as any store state such that $S = (\Gamma, g)$ where $g = \texttt{null}$⁷. We say that legacy store state $S = (\Gamma, \texttt{null})$ is semi-valid if

• $\exists h \in \mathcal{H}$ such that $\forall \gamma \in \Gamma, \gamma(h) = 0$.

That is, all chain ids in $\Gamma$ share the same genesis hash $h$ for some hash $h \in \mathcal{H}$.

Finally, we say that store state $S = (\Gamma, g)$ is valid if one of the following is true:

• $g = \texttt{null}$ and $\Gamma = \varnothing$
• $g \neq \texttt{null}$ and $\forall \gamma \in \Gamma, \gamma(g) = 0$⁸.

The above set of rules forces valid store states with $\texttt{null}$ canonical genesis hash to have $\varnothing$ as $\Gamma$⁹.

Mapping $\Phi$

Now let $\Phi$ to be a map defined on any semi-valid legacy store state $S = (\Gamma, \texttt{null})$ where

• $\Phi(S) = \Phi(\Gamma, \texttt{null}) = (\Gamma, g)$

with

• $\Gamma = \varnothing \implies g = \texttt{null}$
• $\Gamma \neq \varnothing \implies g = h$ where $\forall \gamma \in \Gamma, \gamma(h) = 0$.

Lemma 1. The map $\Phi$ is well defined. That is, given any semi-valid legacy store state $S$, $\Phi(S)$ is a store state.

Let $S = (\Gamma, \texttt{null})$ be a semi-valid legacy store state.

If $\Gamma = \varnothing$, we have $\Phi(S) = \Phi(\varnothing, \texttt{null}) = (\varnothing, \texttt{null})$ which is a store state.

On the other hand, if $\Gamma \neq \varnothing$, since $S$ is semi-valid, then there exists $h \in \mathcal{H}$ where $\gamma(h) = 0$ for all $\gamma \in \Gamma$. We simply let such $h$ to be $g$¹⁰. $\blacksquare$

Lemma 2. Given any semi-valid legacy store state $S$, $\Phi(S)$ is a valid store state.

Again, let $S = (\Gamma, \texttt{null})$ be a semi-valid legacy store state. As $\Gamma = \varnothing$ is a degenrate case, so we assume $\Gamma \neq \varnothing$.

As we've seen in the previous lemma, we have $\Phi(S) = (\Gamma, g)$ with $g = h$ where $\gamma(h) = 0$ for all $\gamma \in \Gamma$. Since we have already assumed $\Gamma \neq \varnothing$, this is exactly the latter condition for $\Phi(S)$ to be valid according to the definition of store state validity. $\blacksquare$

Explanation

Contractually enforcing IStore to setting the canonical genesis hash before any chain id can be added and all chain ids added having to have the same genesis hash as the network's genesis hash is equivalent to IStore as state store $S$ being valid.

Now the problem arises where we have legacy IStores. The construction of mapping $\Phi$ is to show that there is a migration path from legacy IStore to a proposed IStore where if legacy IStore were managed reasonably properly, then the migrated result would comply with the new constraints¹¹.

The bigger issue is how to migrate while minimizing disruption. Assuming IStore has been managed well enough to be in semi-valid state, we can do either of the following:

• Implement $\Phi$ inside IStore constructors to migrate on-the-fly.
• Implement an external method that implements $\Phi$ migrating legacy IStore by running it externally.

The former has the advantage of being able to migrate silently with minimal downtime and without any API changes. The disadvantage would be having additional overhead everytime we load an IStore.

The latter has the advantage of being able to validate old IStore's state to see if it is already in semi-valid state so that $\Phi$ can be applied safely. The downside is there being additional operational disruption. As an IStore itself does not know whether it is in legacy state or new state, theoretically, this must be externally checked every time.

Footnotes

1. There can be edge cases where pre-existing IStores do not conform to this rule. ↩

2. This is to prevent IStore having a different genesis Block<T> to all existing chain ids. ↩

3. This is probably going to be operationally heavy as this would require iterating over all chain ids in IStore. ↩

4. If this is not the case, then I see that as a mismanagement of IStore. This should be an evidence as to why we need to refactor IStore. ↩

5. Note that $\Gamma$ can be empty. ↩

6. In practice, the set of rules are a bit different. We aren't particularly concerned with injectivity of $\gamma$ and the shape of its image $\gamma(H)$ in this discussion. ↩

7. This is because in the old version, there is no canonical genesis hash property. ↩

8. Again, note that $\Gamma = \varnothing$ is still allowed. The right hand side simply becomes vacuously true. ↩

9. In terms of implementation, if we are to enforce this property, this means adding a new chain id should not be allowed before setting a canonical genesis hash to IStore. ↩

10. Note that map $\Phi$ is not well-defined if $S$ is simply a legacy store state that is not semi-valid. In particular, if not all chain ids do not share the same genesis hash, $h$ is not defined. ↩

11. As nothing pertains to Block<T> and Transaction<T> directly, this should be safe. ↩