I've been reading through the bitcoin source code. I'm interested in working with anyone who tries to implement this. Here's what I've found:
All the relevant code seems to be in main.cpp and main.h.
As currently implemented, we can traverse the blocktree from leaves->root, but Aviv and Yonatan's algorithm requires us to be able to traverse the blocktree from root->leaves. The first thing that needs to be done is that we need to rewrite the tree to make it traversable in both directions.
After this, the code to determine which block is the "BestBlock" to append a new child block to needs to be pretty much completely rewritten. The code currently computes the ChainWork (the amount of work needed to compute the current block and all blocks above the current block on the tree) of each block in the tree. It then searches through the entirety of (the still valid parts of) the tree for the block that has the largest ChainWork, and it assigns this block as the BestBlock. Instead, we need to traverse the tree from root->leaves, and compare the work in each subtree whenever we come to a fork.
Hi, thanks for taking a look! I think it's a good idea to map out all the changes that need to take place.
Comments:
1) I might be wrong about this, because I haven't looked at the implementation too carefully, but in principle, I think forward and backward traversal of the chain should already be possible: as far as I'm aware, the unspent transaction output set needs to be rolled back if a recent part of the chain is replaced. If I'm not mistaken (and somebody please correct me if I am) the unspent outputs are only maintained for the "best block" and if this is replaced by an alternate chain, it isn't built from scratch.
2) There is also a need to add hashes (or other identifiers) of newly discovered off-chain blocks into each block ("newly discovered" here means: not included inside any other previously reachable block). Nodes must then request such blocks if they do not already have them, and the propagation mechanisms / inv messages need to be adjusted accordingly.
Also, the code to invalidate and discard blocks on the tree needs to be rewritten. I'm lost on how this works and how it should be rewritten.
3) I'm not sure what you mean by "the code to invalidate and discard blocks". Can you explain in more detail?