Guess-and-check programming

[matthiasgoergens]

Fully proven execution in ZK VMs will probably always be slower than native execution.

Luckily, we get to 'cheat': our guest programs in the VM can ask their host for advice. So instead of eg sorting a list of numbers, they can 'guess' a permutation (via advice from the host), apply that permutation and check that the numbers are now ordered.

I want to discuss ways for making this style of programming easy. Especially, I want to explore whether we can perhaps write tooling or a library for Rust to make it natural there.

Miden and Risc0 have some support for this style. Miden's support is relatively clunky, as you have to prepare your advice tapes ahead of time. Risc0 makes these calls look like client/server programming or API calls. But I was wondering, if we can simplify things even more.