We can apply this technique to the commitments in a verkle tree.
Every update will then result in an update for one commitment per level of the tree. To proof a value, we need a witness for every level of the tree. For multiple values, we can join the witnesses for the root commitment together, but can not do that for the other levels.
Suppose we go for a verkle tree with 2 levels where the root commitment can hold 2^{20} values and the leaf commitments can hold 2^{10} values each, then we can store up to 2^{30} values in this verkle tree.
Suppose we have 1024 updates and need witnesses for 1024 values per block just as the example above. Then for the root commitment, we will have 1024 updates and need a witness for 1024 values. Plugging this in the formula above means we need under 2^{19} elliptic curve operations for the root commitment.
For the leaf commitment we need to do a single update on 1024 different commitments and need a single witness for 1024 different commitments. Plugging this in the formula means we need 2^{18} elliptic curve operations on the leaf commitments per block.
Together we will need on average a little over 2^{19} elliptic curve operations per block. Is this feasible?
If we go for a verkle tree with 3 levels where the root commitment has 2^{14} values and the two levels below have commitments with 2^{8} values, we need a little over 2^{17} elliptic curve operations per block, which must be feasible.