The proof computation code currently uses the very memory-inefficient variant of merkle hashing that materializes the entire tree, even if some parts of the tree are missing (e.g. proving a list element that fits in the types's bound but is not present in a given instance).
There is a much more memory-efficient variant used for computing the hash tree root; the Merkle proving code should utilize it.
One complication is that the current memory-efficient implementation computes the Merkle root in-place overwriting nodes below the root as it walks "up" the tree. This logic could be re-used while retaining the same properties with some sort of "visitor" abstraction that can run during the Merkle computation. If we only care about the tree root, then the visitor can do nothing. If we care about accumulating nodes along some path (e.g. for the Merkle proof), then this visitor can grab a copy of the branch as the computation proceeds.
It is possible that we get to #17 first in which case this visitor approach could be unnecessary as the tree would always be handy so a Merkle prover could just walk along the already materialized nodes.
The proof computation code currently uses the very memory-inefficient variant of merkle hashing that materializes the entire tree, even if some parts of the tree are missing (e.g. proving a list element that fits in the types's bound but is not present in a given instance).
There is a much more memory-efficient variant used for computing the hash tree root; the Merkle proving code should utilize it.
One complication is that the current memory-efficient implementation computes the Merkle root in-place overwriting nodes below the root as it walks "up" the tree. This logic could be re-used while retaining the same properties with some sort of "visitor" abstraction that can run during the Merkle computation. If we only care about the tree root, then the visitor can do nothing. If we care about accumulating nodes along some path (e.g. for the Merkle proof), then this visitor can grab a copy of the branch as the computation proceeds.
It is possible that we get to #17 first in which case this visitor approach could be unnecessary as the tree would always be handy so a Merkle prover could just walk along the already materialized nodes.