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.
One 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 numbers, do I get back the number I wanted to factor?"). Some methods are very general, like zkSNARKs. Unfortunately, even though these general methods for verification are shockingly efficient compared to performing the whole underlying computation yourself, the verification is still not feasible with human-scale time and resources (without depending on some kind of automatic computer). In order to verify computations at human-scale, we'll need to make the verification very efficient, and also take advantage of tasks that are easy for humans to do at massive scale, without the aid of computers.
Usually when we think about executing a program, we think about executing steps sequentially. But we can also think about certain computations as circuits. Instead of manipulating variables step by step, the data gets transformed by many "gates": simple functions that transform data (1s and 0s) from input "wires" to output "wires", like AND(X, Y) (which is 1 when its inputs are both 1, and 0 otherwise), XOR(X, Y) (which is 1 when exactly one of its inputs is 1, and 0 otherwise) and NOT(X)(which is 1 if its input is 0 and vice versa). These gates are chained together to form potentially very complicated circuits, that can do a lot of useful work. Given such a circuit and an input, a "trace" is an assignment of a value (in this case, 0 or 1) to every wire in the circuit, which should correspond to what you get by executing each gate on its inputs until you've produced the outputs.
And if we have a program implemented as a logic circuit, there's a neat way to quickly verify a trace of that circuit "by eye", much faster than checking each operation one at a time.
visually verifying circuits
Start by deciding on a "layout" for the circuit: Every wire in the circuit gets a location in a large rectangular grid, with the input wires at the top and the output wires at the bottom. In principle, wires can go anywhere, but it will work better if there's only a small number of offset patterns for each gate type (like, for an AND gate, if the input wires are always next to each other and the output wire is always directly beneath the left input, that's only one offset pattern; if it's that way sometimes but sometimes the output is under the right input, that's two offset patterns). We'll call a combination of a gate and an offset pattern a "gate pattern".
Then, we want a way to check that the data in a trace, when arranged into our chosen layout, doesn't contain any errors: For each gate in the circuit, we want a way to notice if the output wire doesn't match the gate's action on its inputs.
In order to achieve this, we'll punch holes in paper: Each cell in the grid layout has either its left or right half (left for 0 and right for 1) "punched out" based on its value in the trace, so that the pattern of transparent holes in the sheet indicates the values in the trace.
The untrusted computer gives us a bunch of copies of the same trace sheet for the computation; assume for now that we have a way to easily check that all these trace sheets are identical, and that the cells all obey the proper format (where exactly one of the two halves is punched out).
Each simple logic gate has only a finite number of ways that it might be incorrect: An AND gate is incorrect when either (a) its left input is 0 and its output is 1, (b) its right input is 0 and its output is 1, or (c) its inputs are both 1 and its output is 0. Because of the way we've encoded our circuits, we can overlay our copies of the trace sheets on top of each other with carefully chosen offsets, and then check if light shines through at the relevant locations in order to verify that each error is not present in our gate: light shining through means there's an error; no light means the none of the gates in this pattern exhibit this error. And we only need to run one of these checks per gate pattern on a given sheet.
For example, let's assume our AND gates are always laid out with the inputs next to each other and the output underneath the left input.
To check that a 0 on the left input never corresponds to a 1 at the output, we take two sheets and stack them so that the top sheet is offset upward ("north") by one cell and left ("west") by half a cell. Because the top sheet now has its "output 1" right on top of the bottom sheet's "left input 0", light will only shine through that location if this error is present in that gate. And to test the same thing about the right input, we just do a shift of 1 cell north and a shift east by half a cell. Finally we add a third trace sheet, and line them all up so that light shines through exactly when the inputs are both 1 and the output is 0. Now we've checked all the possible errors for AND gates.
The key thing here is that we can do many of these checks at the same time, since we can check every instance of a gate pattern all at once. We only need a small number of error checks per gate pattern, and for at least some important computations we need a small number of gate patterns. If the tolerances are tight enough, we can have loads of gates in a small space, and thereby verify large circuits.
In order to verify a circuit with multiple gate patterns, we use a trusted "gate pattern mask" for the circuit, that only exposes the relevant gates given an appropriate offset.
Given all of the offset-and-overlapped well-formed traces and gate pattern masks, if all the checks produce no light, we know that none of the potential error syndromes are present, meaning the circuit trace really does compute the given output.
Here's an example, where we can verify a full 32-bit multiplication circuit. It takes some effort, but if you walk through all the checks, you will see at least one lit cell when there's an error introduced.
checking that cells are well formed
So far we've assumed we can check that two traces are identical, and that all traces are well-formed (every cell has exactly one of the two halves punched out). A trace might be ill-formed in one or both of two ways: It might have too much open space (e.g. a cell with both halves punched) or it might have too little open space (e.g. a cell with no punched part at all). Too much open space is actually not a big problem: All of our tests indicate a problem when we see light through the card stack, so if a trace has extra open space, this can only make the tests more likely to indicate an error. But we do still need a way to find cells with too little open space.
We basically need to do this by looking for a dark spot. We could make it relatively easy, by using fancier patterns at the cost of making the system more complicated, and making other parts of the verification a little harder (e.g. if we use Truchet quarter-circle arc tiles, ill-formed cells cause discontinuities that can be easily seen.). A good compromise is to use vertical rectangular stripes that are near-continuous, but also highlight (near-) discontinuities.
To check that two well-formed traces are identical, we can check that (a) the cells are still well-formed when overlaid (i.e., no extra dark cells) and also (b) there's no light when the sheets are shifted so that one's 0-halves are overlaid onto the other's 1-halves (though by the argument above, we can actually skip this second check: extra empty spaces in one of the sheets can only make a verification fail, never incorrectly succeed).
what can you do with this?
Say you want to use this technique to bootstrap to verifying arbitrary computations, like zkSNARKs. Unfortunately I think the circuits you need for this take too long to verify by hand in a human lifetime. But you can use it to verify a hash function, which in turn can be useful for certain interactive proof schemes.
Here's a nontrivial worked example: a set of sheets and stencils for a SHA-256 hash. Ken Shirriff estimated it would take about 18 hours to do a full SHA-256 hash by hand with pencil and paper; verifying them this way is comparable to computing them that way, though I'd guess it's also much less error-prone. Note, however, that this is still areally difficult undertaking, and that you need to zoom into the image in order to see what the errors might look like in the context of a very large verification.
I mostly think it's cool that you can verify arbitrary circuits like this, in a way that might actually be feasible for real humans. I don't have real threat models that indicate that this is going to matter at all. If I were going to try to actually use this scheme, I'd probably order some solder paste stencils from a PCB company. Given reasonable guesses about how large the cells should be, here are some guesses about the resources it would take to implement this scheme.
acknowledgements
While I originally had this basic idea in 2021, Claude Fable 5.2 fleshed out the whole thing, partly based on its knowledge of prior work on visual cryptography and transparency computing, some by Naor, Shamir, Pinkas, and Head. Claude also produced all of the interactive diagrams and tables.
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.
One 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 numbers, do I get back the number I wanted to factor?"). Some methods are very general, like zkSNARKs. Unfortunately, even though these general methods for verification are shockingly efficient compared to performing the whole underlying computation yourself, the verification is still not feasible with human-scale time and resources (without depending on some kind of automatic computer). In order to verify computations at human-scale, we'll need to make the verification very efficient, and also take advantage of tasks that are easy for humans to do at massive scale, without the aid of computers.
Usually when we think about executing a program, we think about executing steps sequentially. But we can also think about certain computations as circuits. Instead of manipulating variables step by step, the data gets transformed by many "gates": simple functions that transform data (1s and 0s) from input "wires" to output "wires", like
AND(X, Y)(which is 1 when its inputs are both 1, and 0 otherwise),XOR(X, Y)(which is 1 when exactly one of its inputs is 1, and 0 otherwise) andNOT(X)(which is 1 if its input is 0 and vice versa). These gates are chained together to form potentially very complicated circuits, that can do a lot of useful work. Given such a circuit and an input, a "trace" is an assignment of a value (in this case, 0 or 1) to every wire in the circuit, which should correspond to what you get by executing each gate on its inputs until you've produced the outputs.And if we have a program implemented as a logic circuit, there's a neat way to quickly verify a trace of that circuit "by eye", much faster than checking each operation one at a time.
visually verifying circuits
Start by deciding on a "layout" for the circuit: Every wire in the circuit gets a location in a large rectangular grid, with the input wires at the top and the output wires at the bottom. In principle, wires can go anywhere, but it will work better if there's only a small number of offset patterns for each gate type (like, for an AND gate, if the input wires are always next to each other and the output wire is always directly beneath the left input, that's only one offset pattern; if it's that way sometimes but sometimes the output is under the right input, that's two offset patterns). We'll call a combination of a gate and an offset pattern a "gate pattern".
Then, we want a way to check that the data in a trace, when arranged into our chosen layout, doesn't contain any errors: For each gate in the circuit, we want a way to notice if the output wire doesn't match the gate's action on its inputs.
In order to achieve this, we'll punch holes in paper: Each cell in the grid layout has either its left or right half (left for 0 and right for 1) "punched out" based on its value in the trace, so that the pattern of transparent holes in the sheet indicates the values in the trace.
The untrusted computer gives us a bunch of copies of the same trace sheet for the computation; assume for now that we have a way to easily check that all these trace sheets are identical, and that the cells all obey the proper format (where exactly one of the two halves is punched out).
Each simple logic gate has only a finite number of ways that it might be incorrect: An AND gate is incorrect when either (a) its left input is 0 and its output is 1, (b) its right input is 0 and its output is 1, or (c) its inputs are both 1 and its output is 0. Because of the way we've encoded our circuits, we can overlay our copies of the trace sheets on top of each other with carefully chosen offsets, and then check if light shines through at the relevant locations in order to verify that each error is not present in our gate: light shining through means there's an error; no light means the none of the gates in this pattern exhibit this error. And we only need to run one of these checks per gate pattern on a given sheet.
For example, let's assume our AND gates are always laid out with the inputs next to each other and the output underneath the left input.
To check that a 0 on the left input never corresponds to a 1 at the output, we take two sheets and stack them so that the top sheet is offset upward ("north") by one cell and left ("west") by half a cell. Because the top sheet now has its "output 1" right on top of the bottom sheet's "left input 0", light will only shine through that location if this error is present in that gate. And to test the same thing about the right input, we just do a shift of 1 cell north and a shift east by half a cell. Finally we add a third trace sheet, and line them all up so that light shines through exactly when the inputs are both 1 and the output is 0. Now we've checked all the possible errors for AND gates.
The key thing here is that we can do many of these checks at the same time, since we can check every instance of a gate pattern all at once. We only need a small number of error checks per gate pattern, and for at least some important computations we need a small number of gate patterns. If the tolerances are tight enough, we can have loads of gates in a small space, and thereby verify large circuits.
In order to verify a circuit with multiple gate patterns, we use a trusted "gate pattern mask" for the circuit, that only exposes the relevant gates given an appropriate offset.
Given all of the offset-and-overlapped well-formed traces and gate pattern masks, if all the checks produce no light, we know that none of the potential error syndromes are present, meaning the circuit trace really does compute the given output.
Here's an example, where we can verify a full 32-bit multiplication circuit. It takes some effort, but if you walk through all the checks, you will see at least one lit cell when there's an error introduced.
checking that cells are well formed
So far we've assumed we can check that two traces are identical, and that all traces are well-formed (every cell has exactly one of the two halves punched out). A trace might be ill-formed in one or both of two ways: It might have too much open space (e.g. a cell with both halves punched) or it might have too little open space (e.g. a cell with no punched part at all). Too much open space is actually not a big problem: All of our tests indicate a problem when we see light through the card stack, so if a trace has extra open space, this can only make the tests more likely to indicate an error. But we do still need a way to find cells with too little open space.
We basically need to do this by looking for a dark spot. We could make it relatively easy, by using fancier patterns at the cost of making the system more complicated, and making other parts of the verification a little harder (e.g. if we use Truchet quarter-circle arc tiles, ill-formed cells cause discontinuities that can be easily seen.). A good compromise is to use vertical rectangular stripes that are near-continuous, but also highlight (near-) discontinuities.
To check that two well-formed traces are identical, we can check that (a) the cells are still well-formed when overlaid (i.e., no extra dark cells) and also (b) there's no light when the sheets are shifted so that one's 0-halves are overlaid onto the other's 1-halves (though by the argument above, we can actually skip this second check: extra empty spaces in one of the sheets can only make a verification fail, never incorrectly succeed).
what can you do with this?
Say you want to use this technique to bootstrap to verifying arbitrary computations, like zkSNARKs. Unfortunately I think the circuits you need for this take too long to verify by hand in a human lifetime. But you can use it to verify a hash function, which in turn can be useful for certain interactive proof schemes.
Here's a nontrivial worked example: a set of sheets and stencils for a SHA-256 hash. Ken Shirriff estimated it would take about 18 hours to do a full SHA-256 hash by hand with pencil and paper; verifying them this way is comparable to computing them that way, though I'd guess it's also much less error-prone. Note, however, that this is still a really difficult undertaking, and that you need to zoom into the image in order to see what the errors might look like in the context of a very large verification.
I mostly think it's cool that you can verify arbitrary circuits like this, in a way that might actually be feasible for real humans. I don't have real threat models that indicate that this is going to matter at all. If I were going to try to actually use this scheme, I'd probably order some solder paste stencils from a PCB company. Given reasonable guesses about how large the cells should be, here are some guesses about the resources it would take to implement this scheme.
acknowledgements
While I originally had this basic idea in 2021, Claude Fable 5.2 fleshed out the whole thing, partly based on its knowledge of prior work on visual cryptography and transparency computing, some by Naor, Shamir, Pinkas, and Head. Claude also produced all of the interactive diagrams and tables.