Non-determinism in the context of zkSNARKs refers not to randomness, but rather to NP-style non-determinism. I.e., zkSNARKs support statements of the form "Ther

Non-determinism in the context of zkSNARKs refers not to randomness, but rather to NP-style non-determinism. I.e., zkSNARKs support statements of the form "There exists a witness w such that f(x, w) = true", where f is a predicate, and x is a publicly known value. This allows cool things. For example, if you wanted to use a zkSNARK to check if something was sorted, you don't have to implement a sorting algorithm in the zkSNARK language (this would take time nlogn). Instead, you can just implement an algorithm that takes as input a list, and checks that it is in ascending order (which takes time O(n)). In this case, the witness is the sorted list, and the actual sorting happens outside the zkSNARK. This enables the zkSNARK impl to be more efficient.