# Accumulator Specification Draft of the accumulator specification for the portal network ## Role of accumulator Provides each node participating in the portal network to have a cost efficient way to track the canonical chain in the network. Each node will store a copy of the accumulator in its own storage. The idea is to store only the essential data that is required to keep track of the canonical chain to keep it the accumulator as light weight as possible. Finding out how much storage is required to store the accumulator in a long run is something that needs to be benchmarked later ## Bootstrapping the accumulator ## Requirements The accumulator should be able to statisfy the following properties: * Ability to handle reorgs up to a certain number of blocks, with the assumption of block finality in the Ghost protocal (assumed to be 256 blocks in Ethereum?) * Ability to verify if a block belongs to the canonical chain ## Accumulator Structure The structure of the accumulator will be based on the double-batched accumulator used [here](https://ethresear.ch/t/double-batched-merkle-log-accumulator/571) consisting of a bottom buffer (epoch trie) and a top buffer (master trie). Similar to that of this [article](https://notes.ethereum.org/oUJE4ZX2Q6eMOgEMiQPkpQ?view). Each buffer will utilize a trie to store the data. Proofing that a particular data is in a trie will only require root hash as well as the proofs just like how other trie works. (eg. to proof that a particular block is in the canonical chain, we will need the roothash of the top buffer with its proof to the hash pointing to the hash of the bottom buffer and the proofs of the bottom buffer to the block of interest) ### Bottom buffer (Epoch trie) A trie structure of a fixed number of layers. ( 8 layers of a binary trie will allow us to have a size 256 slots in each epoch). Number of slots in each epoch has to be equal or larger than the assumed block finality. (eg. if the network assumes that finality only happens after 300 blocks, the total slots in the epoch has to be 300 or more). The root of the trie will be the hash of the current epoch. This will be constantly changing as blocks are being added into the trie and the old blocks being push out of the trie. The latest root hash is stored and updated as the last entry of the Master list until all slots are filled and a new cycle begins. Simple visual of a 5 slot Epoch trie Before: `0` | `1` | `2` | `3` | `4` After 5 has been added to the trie `1` | `2` | `3` | `4` | `5` 5 will be added to the end of the trie while 0 is removed. Once the newer data has fully replaced the older data from the previous epoch, the roothash is then stored the to Master trie The data that will be stored in the epoch trie are the blocknumber and blockhash. We could store it as `List[Container[blocknumber, blockhash], maxlength =..] (SSZ sedes format)` note to self* max length being the length of the list ### Top buffer (Master trie) Will be a list of root hashes of the bottom buffer which has completed the 'cycle'. The data that will be stored in the master trie could be `List[epochnumber, epoch trie root hash]` ## Strategies for Reorgs Reorg happens when a node which is tracking a canonical chain suddenly realized that there is another long chain out there. The node will then switch to track the longest chain instead. Reorgs generally happen due to the delay of block info in the network. The accumulator must have the ability to 'rollback' blocks that was included in the chain previously and replace it with blocks that are in the longest chain. ### Node to 'rollback' the it detects a block which a greater number When the node receives information of a higher block number than the one the node is currently storing, it will request for lower blocks until it finds a common block hash in its storage. it will remove all its existing stored block (up until N, assumed finalized block) and replace it with the new block info. ### Edge case of rollback in the bottom trie When the bottom trie has just only been filled up (say. 2 blocks) and a reorg of (say. 3 blocks) have been detected. The rollback will require the roothash of the master trie to get rolled back as well.