Optimizing MASP proofing

[zenodeapp]

Hi!

First off, this shielded-sync approach is really a step forward into the right direction! Great job! Before I dive into potential optimizations, I'd like to address a current (small) problem in v0.31.6:

At the moment, I have to re-run the command to let a shielded transfer get reflected in my balance. This possibly due to having an outdated asset list the moment we run the balance query. Perhaps re-running this whenever the asset list is outdated could help. Or, instead give the user feedback that the current state isn't up-to-speed thus the balance for the queried wallet could be outdated.

---

Now for optimizing MASP, I had a couple ideas:

Simple, yet still not a fix for the >= O(n) MASP algorithm problem

1. Could the shielded-sync be a separate process that runs alongside the ledger to keep up with the blockchain and resync whenever a new block (or arbitrary interval of blocks) gets added? This doesn't necessarily speed up MASP but it would make it a separate process running concurrently. I could imagine this may be a potential pitfall for state inconsistencies though.

More complex ideas, but requires changes in infrastructure
I'm not aware of all the ins-and-outs of the MASP algorithm, so what I'm about to say may make it less secure, sound ignorant or might theoretically even not be possible, but:

2. Is it an idea to instead start the scan at the end of the chain and have every block point to multiple other blocks in the past. They then all, concurrently, traverse the chain back in time until they get far enough back (or all the way back) to get to a point where an agreement for the asset list can be made? Perhaps it will be necessary to traverse back up again to the current block and calculate the final state for the asset list in the present (due to else becoming indeterminate).

   This could relief it from its (at minimum?) O(n) time complexity by allowing the algorithm to be a multithreaded activity (if it's actually possible to let this be calculated in multiple threads). Also, the stepInterval to how far back a block should point could be treated as a parameter for how secure the algorithm is.

   This idea could somewhat be thought of as a checkpoint mechanism. Also, reason for starting this at the end of the chain is due to not being able to predict and point to future blocks.

3. If 2. makes the cryptography less secure, there's also some randomization that could get implemented. What if the block selection used for the creation of this asset list is randomized at every new block (or whatever interval)? That way it's less straight-forward to predict which blocks it chooses for the calculation of the new asset list. Though to make this deterministic it would require global tracking of the seed used for randomization on every block.

4. A final idea is to fuse the current method with the above. This would probably be hard to attain. But it might give way to getting the best of both worlds. Let's say you utilize the tree-like traversing method from above for 80% of the chain. The last 20% would then be calculated by scanning every block linearly towards the current block. This would probably be tricky if I think of all the consensus issues this could give rise to, but it could potentially improve the time complexity.

These suggestions kind of point to finding the sweet spot between either saving up on time complexity or improving the granular aspect of the cryptography.

To wrap it up: security or cryptography isn't exactly my strong suit, so apologies if these three latter points sound a bit ignorant to the problem at hand!

ZEN

[zenodeapp]

I seriously am bad with categorizing stuff. This is not a bug, but potential Enhancement/Improvement ofcourse.

(though the first point could be seen as a potential bug)

[zenodeapp]

Sadly, I'm in no way capable of writing a logic as complex as this in Rust as to see how it would play out.

Though, believe this thought process could actually help. Perhaps someone with the skills will see this and take a shot at trying to implement this.

[zenodeapp]

UPDATE: revised everything and also added a 4th contemplation.

[zenodeapp]

Another small side note for 4: this idea of implementing a tree-like traversal fused with the current linear approach kind of reminds me of state-syncing; in that it offers a shortcut to get to the recent height and progresses as usual when it gets to the trusted height.

Though state-syncing has a one-time use, the algorithm above I envision as something that's continuous.

[zenodeapp]

When opening #2867 I got another idea. Adding it here for a 5th contemplation. This is not for improving the O(n) complexity, but to have a set of node runners to offer their resources for shielded syncing. This might not be so private though.

I was working on an IBC app and did have difficulty being able to use the extension's shielded address, highly likely it's related to the current method of shielded syncing and the account not being initialized or something? So that's why perhaps linking this data to RPCs (or call them differently) and being able to request a sync for your viewing-key could become a thing.

Though, in my opinion, the shielded sync approach may cause more difficulty than I first thought. It's an intense operation. There has to be a way to abstract this logic further into the backend. Especially important when it comes to eventually creating front ends for shielded activities.

By the way, I tried to sync a viewing key I did not own in the CLI. This went through the whole chain, but as soon as I again ran the sync it started all over again! Isn't it possible to perform a shielded sync for a not imported viewing key? Asking this for trying to manoeuvre through the building of the IBC app. Perhaps I should create a separate issue for this.

[brentstone]

Will close this now, but tracking in #2900.