Implement PoW

[Shimuuar]

It turns out we need to implement PoW consensus. It's not clear how could we squeeze both PBTF0like and PoW consensusn into same library but it does seems to be possible. Consensus algoprithms are completely different but they do share a lot of supporting infrastructure.

[Shimuuar]

It seems easiest and probably best approach is to implement PoW as a separate library, say hschain-pow and reuse libs like hschain-{crypto,merkle,net}. What are main different between PBFT & PoW:

1. Consensus itself is almost comically simple and non-interactive: node only need to find chain with most work and that's
2. Because blockchain reorganizations are possible we need ability to roll back block in contrast with PBFT where we need only to update state!
3. Most complex part is consequently network and it's least well designed part of hschain. Alas documentation on network protocol of bitcoin & Co is light on details when it comes to propagation of blocks, handling of bch reorganizations etc.

[Shimuuar]

Network

Network is quite complicated and has its own subsystems. Probably it would be reasonable to start designing full PoW system starting from network:

1. Peer exchange. We'll need getting new peers, blacklisting of misbehaving peers, ratings for good peers etc. We can copy some parts of implementation from hschain
2. Mempool. Once we get decent mempool in hschain we could just use it
3. Propagation of blocks. In particular propagation of new block is very tricky and latency sensitive. But as starting point we could just use naive approach from early bitcoin. It is reasonable and could get us started

Blockchain state handling

This is big and important topic which was punted somehow in hshchain. Blockchain state is big bad, require serialization.

• We need ability to rollback state which is new and add constaints on possible states
• We may want to store state in separate database (bitcoin does just that)
• We may want to keep only parts of state in memory and offload parts of it into
• Handling of chain reorganizations raise many questions. How should we handle it. Rollback uncoditionally to longer chain. If it has invalid block in the middle? Rollback again
• Should we include hash of state of block. It's quite nice and allows to access/download state but calculating state efficiently is difficult. We certainly don't want to iterate over all unspent outputs.

Storage for blocks

Here we get into the realm of CAS. There's some rudimentary implementation in haschain but it leave much to be desired.

Consensus

Tracking of chain with most work. Conseptually very simple but figuring exact API could take time. We also could check that block has enough work just by looking at header while we need full block to validate it completely. This allows some interplay between

Migrations.

Question which I wasn't able to crack in the hschain. Maybe fresh start will allow some insights

Links

[1] Quite interesting writeup on block propagation in bitcoin https://people.xiph.org/~greg/gmaxwell-sf-prop-2017.pdf