What happens to runtime when the code contains conditional branches?

[makoConstruct]

Consider a program that branches K different ways depending on the input data, then has to do something different for each contingency that costs about G. A regular processor, crucially, would run this program in G steps. I'm guessing that Risc0 would do it in K*G steps, because the conditional branching would tell us something about the data, so to keep the inputs secret, every branch would have to be run? And that seems important? But this doesn't seem to be mentioned anywhere in the documentation or past discussion of performance? (Is it actually not very important? Are most decentralized computations quite linear?)

[intoverflow]

This is a great question!

The zkVM runs guest programs the same as any other CPU. In particular, it does not attempt to follow all possible code paths.

At the end of execution, the ZK proof does not precisely tell you the number of cycles that ran. Instead, it rounds up to the next power of 2. This rounding is a side effect of the STARK construction.

This side channel is likely to be removed in the future.

[makoConstruct]

And, can you confirm that there's no way to learn anything about the inputs by watching the control flow as the program runs?

Another question I have is, do any of us have a strong sense of when it is or isn't practical to pad/limit runtime to a constant number of cycles? Are there common types of computation that risc0 wouldn't obviously be applicable to due to the blinding timing attacks becoming prohibitively expensive? This might be the sort of question we can only answer after using systems built on risc0 in deployment for a time, but some people have very strong foresight and will already have intuitions about this.

[flaub]

The host (the machine doing the proving) has full access to the guest, and so can see all control flow that is occurring. The execution trace is needed by the proving system to construct a receipt, but this trace can't be derived from the receipt. That means verifiers won't be able to see the control flow of the program.

I don't know that timing attacks make as much sense in the ZKP context. That's because the only leaky value currently is the nearest power of 2 cycle size, but even this will probably disappear in a future release once Continuations lands. Continuations are a way to allow an unlimited number of cycles to execute, by splitting the program up into 'segments'. At that point, each segment can be a fixed size (probably 1M cycles) in which case the only information an attacker can recover is the number of segments, but this will have a granularity of 1M cycles.