Mempool proof references

[dergoegge]

Proofs for leaves that get spend by transactions in a mempool need to be remembered in the pollard and we need the mempool entries to keep a reference to the proofs somehow. (e.g.: if a node wants to rebroadcast a tx it needs to be able to quickly access the proof)

I have been thinking about how to implement the proof references and it seems a bit tricky.
The tricky part is that proofs can change when the pollard is modified.

Idea 1: Use a pointer that points to the remembered leaf polNode.

This does not quite work because we move leaves around by moving the hashes in the polNode but not the actual polNode. Also just having a reference to a leaf does not help that much, we would need pointers to the parents/aunts, to retrieve the entire proof.

Idea 2: The pollard keeps a position map for remembered leaves

Keeping a position map (hash->pos) would work, the proofs could be requested from the pollard given the leaf hashes. The mempool entries then have to keep the leaf hashes as reference for the proofs.

I kind of like the idea of pointers more since they feel less complex and better for performance than adding a position map to the pollard. But since the pointers don't quite work we probably have to use a position map.

Any ideas on how to make the pointers work? Or a totally different approach?

[kcalvinalvin]

For how the current Pollard is structured, I think Idea 2 is the only workable idea. For Idea 1, wouldn't it not work even if the polNode was a pointer because they don't point up to their aunts?

I'm thinking more and more that we should just have a aunt pointer in all the polNodes. Then a pointer to a polNode leaf would be enough to generate proofs for since we can follow aunts until we get to the root (and this would be O(log n)).

[Shymaa-Arafat]

Although this is some time ago, I think this is exactly the point I'm suggesting u should use a variable row size 2D array easier or if u don't like it use the traditional 1D vector compact storage of a a complete tree with math indexing formula (no need for an aunt/niece pointer u can reach it through some Mathematical formula