We’ve discussed an idea that seems to solve this issue on discord, so I will also write it down here for anyone interested.
Basically, if you assume that the data containers are only ever appended to, then the tree depth increasing is really just adding an extra “left” movement to the start of the path from the root to the leaf in question. For example, if the leaf element you are interested in is currently “right” then “left” from the root, your verifier smart contract would probably look like this:
function verify(bytes32[] proof, bytes32 root, bytes32 node) internal {
node = keccak256(abi.encodePacked(node, proof[0]));
node = keccak256(abi.encodePacked(proof[1], node));
require(root == node);
}
The point we are making is that any time the tree depth increases from newly appended properties, the existing container properties will be in the left subtree, so the verifier could have just been implemented like this:
function verify(bytes32[] proof, bytes32 root, bytes32 node) internal {
node = keccak256(abi.encodePacked(node, proof[0]));
node = keccak256(abi.encodePacked(proof[1], node));
for (uint256 i = 2; i < proof.length; ++i) {
node = keccak256(abi.encodePacked(node, proof[i]));
}
require(root == node);
}
to allow longer proofs if they are needed in the future.