New storage model (CAS?)

[Shimuuar]

In PoW we lost block uniqueness: there could be multiple blocks at same height. Thus we can't store blocks using height as key. Only other choice is to switch to block hash as key. Obvious consequence of this approach is content addressable storage (CAS). Even PBFT will benefit since we'll be able to deduplicate some values (validator sets for example).

It's not quite clear how we should design API for such store. Let take definition of block:

data GBlock f a = Block
  { blockHeight           :: !Height
  , blockPrevBlockID      :: !(Maybe (BlockID a))
  , blockValidators       :: !(Hashed (Alg a) (ValidatorSet (Alg a)))
  , blockNewValidators    :: !(Hashed (Alg a) (ValidatorSet (Alg a)))
  , blockPrevCommit       :: !(Maybe (MerkleNode f (Alg a) (Commit a)))
  , blockEvidence         :: !(MerkleNode f (Alg a) [ByzantineEvidence a])
  , blockData             :: !(MerkleNode f (Alg a) a)
  , blockStateHash        :: !(Hashed (Alg a) (BlockchainState a))
  }

We want to be able to fetch both block header and complete block. This means we need to store GBlock Hashed a in database and store commit, evidence, and data as separate entries using their hash as key.

This brings us to question of garbage collection. Primarily it's about removing old state snapshots. State snapshots are naturally stored using hash as key however some optimized representation could be used. Anyhow we'll need to prune old snapshots regularly. It's even more complicated for PoW. There inevitably will be blocks which will be abandoned and fall back enough that it could be pruned from BCH.

Additionally we'll need to track head of blockchain and corresponding amount of work for PoW.

[Shimuuar]

Schema description

So we can use following schema for datatbase. Everything is stored in CAS table with hash and CBOR(?) encoded blob. ID is DB local and is used for foreign keys:

CREATE TABLE thm_cas
  ( id   INTEGER PRIMARY KEY
  , hash BLOB NOT NULL UNIQUE
  , blob BLOB NOT NULL
  );

For PBFT we'll need to add few other tables:

CREATE TABLE thm_blockchain
  ( height    INTEGER NOT NULL UNIQUE
  , round     INTEGER NOT NULL -- Commit round (needed for gossip)
  , blockref  INTEGER NOT NULL -- Block at H=height
  , commitref INTEGER NOT NULL -- Locally seen commit
  , FOREIGN KEY (blockref)  REFERENCES thm_cas(id)
  , FOREIGN KEY (commitref) REFERENCES thm_cas(id)
  )

CREATE TABLE thm_wal 
  ( id      INTEGER PRIMARY KEY 
  , height  INTEGER NOT NULL 
  , message BLOB NOT NULL 
  , UNIQUE(height,message)
  )

CREATE TABLE thm_proposals
  ( height   INTEGER NOT NULL
  , round    INTEGER NOT NULL
  , blockref INTEGER NOT NULL
  , UNIQUE (height,round)
  , FOREIGN KEY (blockref) REFERENCES thm_cas(id)
  )

CREATE TABLE thm_ready_block
  ( height  INTEGER NOT NULL
  , attempt INTEGER NOT NULL
  , result  BOOLEAN NOT NULL
  , UNIQUE (height, attempt)
  )

Block storage

Since we want a) to be able to quickly load block header and possibly block data etc. b) we don't want to store same information over and over (validator set) block is stored as several entries in the database: For each block we have following entries:

| id | hash     | blob          |
|----+----------+---------------|
|    | block ID | block header  |
|    |          | validator set |
|    |          | prev. commit  |
|    |          | evidence      |
|    |          | data          |

Which means that we need 5 queries to fetch full block from datatbase. On plus side we do get deduplication.

Garbage collection

This brings us to question of garbage collection. We put proposed but not committed blocks into CAS and they may end up discarded. Thus it would nice to be able to remove data that is no longer needed. But contrary to normal GC most of the data is live and only small fraction is garbage! We also have following problems:

1. Given blob we can't find out which blobs it refers to without deserialising it. Furthermore we don't store type information and there's no easy way to do it anyway
2. One solution is to store references in separate table which is sadly quite fragile. And it's almost impossible to write generic code for it.
3. One approach to deal with scarcity of garbage is to keep track of possible garbage in some table and drop it as it's known that values are not garbage

For PBFT garbage roots are located in tables thm_blockchain & thm_proposals. For PoW problem is slightly more comlicated