On chain state compression using Crypthographic Accumulators

[paluh]

The memory limitations of the Marlowe Validator on-chain present considerable challenges due to memory constraints (for example we have the capacity to store merely five distinct native tokens in the state). While we must also take into account the computational load, theoretically, state compression through providing a subset of the state could reduce the datum decoding volume.

I propose we explore various strategies and potentially conduct performance analyses for each. Brian has suggested that, alongside Merkle Trees, we could experiment with other Cryptographic Accumulator techniques.

Let's briefly examine the properties of Merkle Trees in this context:

• They offer logarithmic complexity for membership proof (assuming non pathological balanced trees), allowing a minimal optimization from batch proofs through the provision of a subtree.
• During insertions and updates, we must ensure the tree doesn't contain duplicates. We could utilize a standard approach and employ sorted Merkle Trees, though this necessitates additional witnesses for neighbors (key questions arise: what is the cost of an insertion? what about tree balancing?)

Alternatively, we could consider working with the full potential state tree from the outset. The complete structure of the tree — encompassing all possible choices, variables, and accounts — is known and could be fully initialized (all set to 0 or Nothing?).

This approach might minimize the proof size needed for updates and insertions, although it could add more overhead to initial operations when the tree is small. However, an added benefit of this methodology is that we can achieve perfect balance within the tree.