forest
forest copied to clipboard
Implement hamt diff algorithm
Issue summary
Our current implementation of the state-diff util library is inefficient. It takes two different state roots and computes which address/ actor state KVs changed, have been added or removed.
A likely faster way to implement this would be to use the same algorithm than from the go-hamt-ipld library.
Other information and links
While implementing this algorithm, I came across many unexpected roadblocks. The go tooling for HAMT and types required to implement this diff aren't available in rust or the FVM, or similar looking functionality behaves completely different. The Go implementation of the algorithm expects two different chainstores. One previous, one current, along with the previous and current CID's to diff. We weren't able to figure out why we need two and we discovered they could not be the same because there was a check to verify they aren't the same store.
I don't think this is a priority anymore. Will re-open if diff performance becomes an issue.