Infallible immutable tree hash

[michaelsproul]

There's a long-standing issue that calculating a milhouse tree hash properly requires mutable access to the List/Vector so that pending updates can be flushed to the underlying binary tree.

That's the topic of this FIXME:

milhouse/src/list.rs

Lines 358 to 364 in 6347db6

	fn tree_hash_root(&self) -> Hash256 {
	// FIXME(sproul): remove assert
	assert!(!self.interface.has_pending_updates());
	let root = self.interface.backing.tree.tree_hash();
	tree_hash::mix_in_length(&root, self.len())
	}

One way to fix this would be to use interior mutability to flush the updates through the & reference. I had a go at doing this using RwLock for the updates and ArcSwap for the tree on this branch: https://github.com/sigp/milhouse/tree/interior-mutability. I got bogged down by the number of changes that had to be, in particular dealing with references becomes really annoying when you need to punch through a lock/atomic. It's impossible to have methods like fn get(&self, i: usize) -> Option<&T> because the &T outlives the lock guard that you had to take to get it. There may still be a way to do it, by changing all return types to smart references, but it seems like it will be a pain.

Race conditions are also a potential issue if using ArcSwap as concurrent mutations could occur between each access. Doing .load() and then .store() is not safe in general through a & reference.

Another option to remove the panic would be to make TreeHash fallible so that it errors in case of pending updates. This is not ideal, and makes hashing somewhat user unfriendly.

A third option would be to make another version of the TreeHash trait (or another method on the same trait?) which takes &mut self. It's not clear that this would provide improved UX either.

[michaelsproul]

Another option is to drop the update map as a concept entirely. That might have the best UX, but probably the worst performance.

[dapplion]

Another option is to drop the update map as a concept entirely. That might have the best UX, but probably the worst performance.

That may wreck epoch transition's performance. We probably need to build something like the update map to register balances somewhere and then apply.

[michaelsproul]

Another approach:

• Read the hashes from the update map while computing the hash.

This means we can have a tree_hash_root method that always works, but is more efficient if updates are flushed.

Maybe that's ok?