To enable a private fallback, we could make the function tree (which exists within a contract class) an indexed merkle tree, so that it supports non-membership proofs. Each leaf would contain a pointer to the value of the next-highest function selector. The correctness of these pointers would need to be validated at deployment.
If a non-existent function selector is called, the pxe would need to feed two function tree membership witness into the kernel circuit: one of the “pointer” leaf (which “jumps over” the called function’s selector), and one of the fallback function. The kernel would then realise the called function doesn’t exist, and fall back to accepting the vk hash (and hence accepting the proof) of the fallback function instead.
The function tree might be relatively small, say 64 leaves, so we’re causing 6 extra hashes, plus a couple more hashes to hash the larger leaf values.
To enable a public fallback, the public vm will need to take an approach similar to the evm.