There's different proof constructions, but many are depending on recursive SNARKs. You basically have an execution harness prover (proves that the block of VM instructions and inputs were correct in producing the output), and then a folding circuit prover (that proves the execution harness behaved correctly), recursively folding over the outer circuit to a smaller size. In Ethereum world, a lot of the SNARKs use a trusted setup — the assumption is that for as long as one contributor to the ceremony was honest (and that there wasn't a flaw in the ceremony itself), then the trusted setup can be trusted. The outsized benefit of the trusted setup approach is that it allows you to shift the computational hardness assumption over to the statistical improbability of being able to forge proof outputs for desired inputs. This of course, assumes that the trusted setup was safe, and that quantum computers aren't able to break dlog any time soon
supermatt|5 months ago