Description du poste
tl;dr: You can use stacks of sheets with holes in them to visually verify moderately-large computations including widely used cryptographic hash functions, within human-scale timeframes.
Imagine that all the world's computers have been taken over by an AI swarm. You don't know whether you can trust the AI swarm to be honest with you - you're skeptical, in part because it just took over all the world's computers, which doesn't seem like an act of a particularly trustworthy AI swarm.
Here's the thing: you really need to run an important program you've written down. Maybe you need to check a cryptographically signed message from your spy friend. Or maybe you work in a map factory and you really need to figure out how many colors you need to color all the countries on your latest map. An AI tells you that it would be happy to run the program for you, but you think you heard it snickering behind your back. Is there any way you can trust the results it gives you? You don't trust anything you can see on a screen, since the AI swarm controls all the screens and can change the results it shows you. Fortunately, back in [today's date] when you did trust the internet, you read a post about visually verifying computations, and made preparations for just this scenario. You open a dusty drawer, pull out a stack of stencils and a lightbox, and settle in for a cozy evening of carefully lining up sheets of punched holes and checking if any light comes through.
trustable computationsOne way you might trust a computation, is if you saw the entire trace (the values of all the variables at every time step) as a printout. You could walk through it line by line, checking the operations one after another. But this would be almost as slow as doing the computation yourself.
There are many ways to verify that some computation has been faithfully accomplished. Some methods are specific to particular problems (e.g. it's easy to verify that a number has been factored: "When I multiply the output