add_block_to_blockchain 2/4 - core algorithm of adding block: if the block(or blocks?) are valid and a new longest chain: invalidate old blocks, fire rollback events, and add the new blocks(and fire rollforward events) about saito-rust HOT 1 CLOSED

I had good conversations with both Stephen and David this morning and want to summarize it here.

There seemed to be some question about what data structure we should use to store blocks so that add_block_to_blockchain will be most efficient. I think we now have agreement that a singly-linked tree stored in a hashmap should be good enough. What this means is using block.parent_hash as a link in the tree and storing all block metadata in a map of block_hash -> block_metadata(which contains the parent_hash). Additionally we'll store a reference to the tip of the longest chain(e.g. latest_block) and each block metadata will contain a bool like is_in_longest_chain.

I believe the BlockIndex type at the top of blockchain.rs was meant to be used for this metadata/parent hash, but I'd like to also suggest that we could change the body of Block to an Option and simply use Block. We would keep body private and access it through a getter and setter which leverages caching.

There is a separate issue for this: #41 I think I'd like to see this done before we tackle the actual add_block algorithm because it will be harder to refactor later.

For version one we don't actually need to do the cache, but we should at least add the get/set methods now so that we save effort in the immediate future. I think it would also be reasonable to have a 10 or 20 minute TTL-based cache mechanism that gets bumped back to 10 or 20 minutes anytime we do a get or set. But this work is actually premature optimization and can happen orthogonally to the rest of add_block_to_blockchain. In this scheme each block simply manages it's own memory usage. i think this is super simple and probably good enough to get us a very robust testnet at least, if not more. I'd like to do it now, but understand if everything things we should hold off.

There are more sophisticated ways to manage block caching which the team has discussed, but I don't want to get into details here.

There are also two thing we must consider which David reminded me of this morning.

One is that we would like to have cached BlockBodies(transactions) at both the top and bottom of the epoch. The top is obvious in the context of add_block_to_blockchain because it helps to do validation and rollback/rollforward more quickly. The bottom is less obvious(especially to those who might not have already been thinkign about Saito for months or years), but it woudl be very helpful for Automatic Rebroadcasting. Unfortunately, the hashmap described above would not be able to handle this alone. Therefore, we'll also need to keep a data structure which maps from block_id -> block_hash and contains all ids in the LC. This and the is_longest_chain bool in the block metadata should be managed when we do rollback/rollforward.

Another issue is how to deal with incoming blocks which don't have a known parent. i.e. a peer could send us a new block which they claim to be the tip of the longest chain(or any block for that matter) which doesn't have a parent in our hashmap. My initial thought was to request the parent from the sender and repeat. However, David described what saito-lite is currently doing and it's much better. Instead of "requesting" the parent from the sender, we simply reply in a RESTFUL way with a message that like "parent-hash-not-found" or something similar. The sender can then continue to push parents at us until we accept the block. The sender can even try to be more efficient by trying 2^n-th parent for the n-th request(which is what saito-lite currently does).

Sending lots of valid blocks with parents in the middle of the blockchain would be a trivial way to attack a node if we don't have some way of expiring() blocks which are not on the LC. So, we will also need some policy for scheduling has_parent_in_known_blocks_hashmap() validation, but also let's not discuss that here in detail since it is orthogonal work.

To facilitate removing non-LC blocks from the hashmap there are sophisticated ways, but again, I think for now a simple TTL mechanism in blockchain.rs should get us very far. Looping through the entire hashmap would work too. Perhaps that would be an even simpler way to do things for now. If we want to do something more sophisticated in the future we'll need to store references to all non-LC blocks. I believe in this case we'd want a FIFO of block hashes, but let's also avoid this discussion for now.

So, the way I see this work getting done:

1. block.rs manages getting, setting, expiring() BlockBody. Also remove BlockIndex. (#41)
2. make the basic datastructure and algorithm for add_block. i.e. the hashmap described above and a pointer to the tip of the longest chain(i.e. latest_block) plus an algo which just adds blocks to the hashmap if their parent is in the hashmap already, computes the LC, and does rollback/rollforward and sets is_on_longest_chain(this issue)
3. blockchain.rs manages removing non-LC blocks from the hashmap(#53)
4. Validate transactions/blocks against UTXO(no sig validation) (#50)

All signature/consistency validation(i.e. "is this a valid block" and "is this a valid tranasction") can be done later. For now let's just worry about maintaining the UTXO set and Blockchain data structures as blocks are added/removed.

from saito-rust.