Proving on consensus after the state is pruned

During one of the discussions with the team, we realized that at the moment, for the domains, once a given domain block is confirmed its state is pruned. So if at some point we want to prove something related to domain on consensus state it would not be possible to prove as the state is pruned. This is same case if someone wants to prove something else on consensus runtime for a specific block which is beyond confirmation depth. Ofcourse, we can pull the actual consensus block either through DSN or archival node but to prove it on runtime we either need to inject that state back to the consensus runtime or fetch through through host function. Fetching with host function would require nodes that do not maintain archival history to fetch it through a network and it will be infeasible.

One potential solution we were thinking was to introduce Merkle mountain range into consensus chain that stores consensus block headers. Having this would make it possible to prove anything on the consensus runtime.

Potential storage

  • on runtime, mmr would store the peaks and it should not bloat the overtime
  • on the client which acts as proof providers would need to store all the leaves to generate the required proofs which will bloat the client storage as the chain grows.

Proofs sizes:
Since we just add consensus block header into MMR, there would multiple indirect proofs if we want to prove something on domain state and as a result proof sizes would be much bigger. I think this would be okay ?

Want to gather some feedback and potential alternative data structures instead of MMR. Please let me know what you think.

cc: @nazar-pc @dariolina @Jeremy_Frank


I see your concern and potential solution, however, I fail to see why is this a concern. The definition of the challenge period implies the inability to challenge things beyond that period. So if you need to prove something wrong you should do it before the state is pruned. Would you need to prove something is correct? After the challenge period, everything that was in those blocks is considered correct.
What would you need to prove?

Its not about proving right but rather proving something that has happened on the Domain chain on consensus chain. We do not have a usecase of proving something that existed yet but if such feature does indeed comes in, then there is no way to prove that such event has happened on Domain on Consensus runtime since it does not hold necessary state beyond unconfirmed domain blocks. Having an infrastructure to do that proof verification is required to be added rather than adding such data at a later time. We can ofcourse add the same MMR at a later time but setting the consensus state requires some form trust and migration both of which might not be feasible

Here is background:

In short we have pathological cases with domain runtime upgrade when one of the domains is offline for a prolonged period of time. If/when domain goes back online they should be able to upgrade to the latest runtime version. The problem is that this either means unbounded state on consensus chain to store all intermediate domain runtime versions or access to state at unboudned depth, both of which are very problematic for obvious reasons. This is not necessary for happy case, but definitely required in order to verify domain runtime upgrade fraud proof.

What we thought is that with MMR such a domain would be able to revive itself by providing not only ER that runtime upgrade happened, but also the runtime itself and a proof that it was in fact a correct runtime back then. Maybe we only need this for fraud proof and upgrade can still follow the happy path, but considering the danger I think we should include it during upgrade alongside with ER.

While we don’t need to design the upgrade mechanism itself, we need an infrastructure to be physically able to generate correct proofs in the future without resorting to revival of the domains via governance only.

1 Like

A Merkle mountain range (MMR) is a data structure that supports efficient appends. Also, it is related to vector commitment with efficient updates. Some latest advances are BalanceProofs and this one. To @ved: Do we need aggregatability for our purpose? (See the previous links for its definition.)

Another direction to explore: Just as a Merkle tree can be turned into a Verkle tree, a Merkle mountain range can be turned into a Verkle mountain range.

As an update to this thread, we have found another use case where this may be necessary, and it is XDM. According to discussions in Trusted source of domain state root for cross domain message verification the destination domain will only execute XDM after the challenge period on the source domain has passed and the state has been pruned.