Move towards using pollard for both bridge nodes and csns

[kcalvinalvin]

Right now we have two of everything for the bridge and compact state nodes. This does add tons of duplicate code that I see could be a problem when trying to propose it to Core.

How is slowly transitioning everything to pollard? We do have full pollard working that can replace forest. We tried getting full pollard working because of hopes of it being faster, but gave up on it because there wasn't much difference. However, it's still a huge win in simplifying the codebase.

@dergoegge @adiabat

[dergoegge]

I attempted to remove some duplicate code in the C++ version with the equivalent of an interface in Go. I didn't quite remove all the ram/disk forest code, but there is no duplicate code for Add or Remove.

type Accumulator interface {
    // Swap two sub trees in the forest and return the dirty node.
    // This is used for swaps during Remove
    SwapSubTrees(from, to uint64) Node
    // Append a new leaf to the forest
    NewLeaf(hash Hash, remember bool) Node
    // Merge two roots into one.
    // Supposed to be called after NewLeaf for all the consecutive 1 bits in num_leaves.
    MergeRoot(parentPos uint64, parentHash Hash) Node
}

There are probably more functions needed in that interface since we can't store variables on interfaces. (e.g.: GetNumLeaves SetNumLeaves)

Pollard and Ram/Disk Forest implement this interface and then Add and Remove can be written in a generic way for the Accumulator interface.

Add(acc, leaves)
Remove(acc,  targets, targetHashes)

I think Prove could also be generic but currently isn't.

I am also doing something similar with nodes in the forest. This helps with abstracting individual nodes in the forest for any type of accumulator. For example in Remove the SwapSubTrees function returns such a Node which is dirty and supposed to be rehashed. We can traverse upwards using Node.Parent() and rehash every node on that path with Node.ReHash() independent of the underlying forest implementation (pollard or ram/disk forest).

type Node interface {
     Parent() Node
     GetHash() Hash
     ReHash()
     GetPosition() uint64
}

Both pollard and any type of forest have node types (i.e. PollardNode, RamForestNode, ...) that implement this interface.
Note: the pollard still has an internal node type that does not implement Node and just stores a hash and two niece pointers.

^ this was all born out of comments that Tadge made during some of the meetings.

I am definitely in favor of removing unneeded or duplicate code. I am not sure if a "pollard only" approach is sufficient since not having everything in ram has value but that would be the simplest solution in code terms. What do you think of the approach i outlined above? (That would likely be quite a large refactor)

[kcalvinalvin]

Looks like it could work. I guess it also makes newer types of forest or pollard easier to implement as well.

I'm not sure what I think about having an interface for node types just yet..

[adiabat]

The idea behind having the forest struct is that the data storage is simpler, as it's a big flat file. You can immediately seek to a location and read / write. That lower complexity is pretty much the only advantage forest has over pollard, but with the swap based accumulator design, it's probably worth the code duplication of having both forest and pollard.

With a swapless design, however, forest gets another big disadvantage: if left as is, the storage used will increase ~10X (from about 64 bytes per utxo to 64 bytes per txo ever).

So it might make sense to just get rid of forest completely, and only have pollard, maybe with a full bool to let it know it's acting like a forest once did.