Error-correcting codes work by running some algorithm to decode potentially-corrupted data. But what if the algorithm might also have been corrupted? One approach to dealing with this is triple modular redundancy, in which three copies of the algorithm each do the computation and take the majority vote on what the output should be. But this still creates a single point of failure—the part where the majority voting is implemented. Maybe this is fine if the corruption is random, because the voting algorithm can constitute a very small proportion of the total code. But I’m most interested in the case where the corruption happens adversarially—where the adversary would home in on the voting algorithm as the key thing to corrupt.
After a quick search, I can’t find much work on this specific question. But I want to speculate on what such an “error-correcting algorithm” might look like. The idea of running many copies of it in parallel seems solid, so that it’s hard to corrupt a majority at once. But there can’t be a single voting algorithm (or any other kind of “overseer”) between those copies and the output channel, because that overseer might itself be corrupted. Instead, you need the majority of the copies to be able to “overpower” the few corrupted copies to control the output channel via some process that isn’t mediated by a small easily-corruptible section of code.
The viability of some copies “overpowering” other copies will depend heavily on the substrate on which they’re running. For example, if all the copies are running on different segments of a Universal Turing Machine tape, then a corrupted copy could potentially just loop forever and prevent the others from answering. So in order to make error-correcting algorithms viable we may need a specific type of Universal Turing Machine which somehow enforces parallelism. Then you need some process by which copies that agree on their outputs can “merge” together to form a more powerful entity; and by which entities that disagree can “fight it out”. At the end there should be some way for the most powerful entity to control the output channel (which isn’t accessible while conflict is still ongoing).
The punchline is that we seem to have built up a kind of model of “agency” (and, indeed, almost a kind of politics) from these very basic assumptions. Perhaps there are other ways to create such error-correcting algorithms. If so, I’d be very interested in hearing about them. But I increasingly suspect that agency is a fundamental concept which will emerge in all sorts of surprising places, if only we know how to look for it.
I have some experience in the design of systems designed for high reliability and resistance to adversaries. I feel like I’ve seen this kind of thinking before.
Your current line of thinking is at a stage I would call “pretheoretical noodling around.” I don’t mean any disrespect; all design has to go through this stage. But you’re not going to find any good references, or come to any conclusions, if you stay at this stage. A next step is to settle on a model of what you want to get done, and what capabilities the adversaries have. You need some bounds on the adversaries; otherwise nothing can work. And of course you need some bounds on what the system does, and how reliably. Once you’ve got this, you can either figure out how to do it, or prove that it can’t be done.
For example there are ways of designing hardware which is reliable on the assumption that at most N transistors are corrupt.
The problem of coming to agreement between a number of actors, some of whom are corrupt, is known as the Byzantine generals problem. It is well studied, and you may find it interesting.
I’m also interested in this topic, and I look forward to seeing where this line of thinking takes you.
I’m not familiar with the method used, but maybe it can be adapted to the case you are imagining? Maybe for simplicity only for the voting part of a redundant system.
IIRC in Byzantine fault tolerance the assumption usually is that cryptographic primitives can be trusted and for 3f+1 at most f nodes are corrupted. The corrupted nodes can output anything. E.g. the Dolev-Strong protocol only assumes (1) a known number of nodes, (2) a public key infrastructure and (3) synchronized communication. But I guess your thought is around someone corrupting a specific part of all nodes? Dolev-Strong assumes you run more rounds than there are corrupted nodes.
I guess your thought is around someone corrupting a specific part of all nodes?
No, I’m happy to stick with the standard assumption of limited amounts of corruption.
However, I believe (please correct me if I’m wrong) that Byzantine fault tolerance mostly thinks about cases where the nodes give separate outputs—e.g. in the Byzantine generals problem, the “output” of each node is whether it attacks or retreats. But I’m interested in cases where the nodes need to end up producing a “synthesis” output—i.e. there’s a single output channel under joint control.
After a quick search, I can’t find much work on this specific question. But I want to speculate on what such an “error-correcting algorithm” might look like.
Did you look in places discussing ledger tech and proof of stake? If you are curious to see what’s been discussed, looking into that might be worth it. Information theory will mostly just focus on efficiency and practical trade-offs.
I’d expect the answer to not be apparent to an outsider, reading the literature, but I’d expect people who are good at designing those sorts of systems to be able to give you the answer quite easily if you ask.
Not exactly about adversarial error correction, but: there is a construction (Çapuni & Gács 2021) of a (class of) universal 1-tape (!!) Turing machine that can perform arbitrarily long computation subject to random noise in the per-step action. Despite the non-adversarial noise model, naive majority error correction (or at least their construction of it) only fixes bounded & local error bursts—meaning it doesn’t work in the general case, because even though majority vote reduces error probability, the effective error rate is still positive, so something almost surely goes wrong (eg error burst of size greater than what majority vote can handle) as T→∞.
Their construction, in fact, looks like a hierarchy of simulated turing machines where the higher-level TM is simulated by a level below it but at a bigger tape scale, such that it can resist larger error bursts—and the overall construction looks like “moving” the “live simulation” of the actual program that we want to execute up the hierarchy over time to coarser and more reliable levels.
For this we need a mechanism such that the maintenance of the mechanism is a schelling point. Specifically, the mechanism at T+1 should reward agents for actions at time T that reinforce the mechanism itself (in particular the actions are distributed). The incentive raises the probability of the mechanism being actualized at T+1, which in turn raises the “weight” of the reward offered by the mechanism at T+1, creating a self-fulfilling prophecy.
“Merging” forces parallelism back into sequential structures, which is why most blockchains are slow. You could make it faster by bundling a lot of actions together, but you need to make sure all actions are actually observable & checked by most of the agents (aka the data availability problem)
Just spitballing, but maybe you could incorporate some notion of resource consumption, like in linear logic. You could have a system where the copies have to “feed” on some resource in order to stay active, and data corruption inhibits a copy’s ability to “feed.”
There may be something to find in how distributed systems do leader election, and the leader can then be a majority trusted overseer. Note that I don’t really understand leader election.
In order to do error-correcting computation, you also need a way to prevent errors from accumulating over many serial manipulations. The simplest way to do this is again to use redundancy: break the computation into multiple parts, perform each part multiple times on different pieces of hardware, and use the most common output from one part as input to the next part. [Fn: Of course, the operation that finds the most common output can itself suffer errors, but the procedure can be done in a way such that this is unlikely to happen for a large fraction of the hardware units.]
I’ve forgotten the details about how this was supposed to be done, but they should be in the two papers I linked.
Error-correcting codes work by running some algorithm to decode potentially-corrupted data. But what if the algorithm might also have been corrupted? One approach to dealing with this is triple modular redundancy, in which three copies of the algorithm each do the computation and take the majority vote on what the output should be. But this still creates a single point of failure—the part where the majority voting is implemented. Maybe this is fine if the corruption is random, because the voting algorithm can constitute a very small proportion of the total code. But I’m most interested in the case where the corruption happens adversarially—where the adversary would home in on the voting algorithm as the key thing to corrupt.
After a quick search, I can’t find much work on this specific question. But I want to speculate on what such an “error-correcting algorithm” might look like. The idea of running many copies of it in parallel seems solid, so that it’s hard to corrupt a majority at once. But there can’t be a single voting algorithm (or any other kind of “overseer”) between those copies and the output channel, because that overseer might itself be corrupted. Instead, you need the majority of the copies to be able to “overpower” the few corrupted copies to control the output channel via some process that isn’t mediated by a small easily-corruptible section of code.
The viability of some copies “overpowering” other copies will depend heavily on the substrate on which they’re running. For example, if all the copies are running on different segments of a Universal Turing Machine tape, then a corrupted copy could potentially just loop forever and prevent the others from answering. So in order to make error-correcting algorithms viable we may need a specific type of Universal Turing Machine which somehow enforces parallelism. Then you need some process by which copies that agree on their outputs can “merge” together to form a more powerful entity; and by which entities that disagree can “fight it out”. At the end there should be some way for the most powerful entity to control the output channel (which isn’t accessible while conflict is still ongoing).
The punchline is that we seem to have built up a kind of model of “agency” (and, indeed, almost a kind of politics) from these very basic assumptions. Perhaps there are other ways to create such error-correcting algorithms. If so, I’d be very interested in hearing about them. But I increasingly suspect that agency is a fundamental concept which will emerge in all sorts of surprising places, if only we know how to look for it.
I have some experience in the design of systems designed for high reliability and resistance to adversaries. I feel like I’ve seen this kind of thinking before.
Your current line of thinking is at a stage I would call “pretheoretical noodling around.” I don’t mean any disrespect; all design has to go through this stage. But you’re not going to find any good references, or come to any conclusions, if you stay at this stage. A next step is to settle on a model of what you want to get done, and what capabilities the adversaries have. You need some bounds on the adversaries; otherwise nothing can work. And of course you need some bounds on what the system does, and how reliably. Once you’ve got this, you can either figure out how to do it, or prove that it can’t be done.
For example there are ways of designing hardware which is reliable on the assumption that at most N transistors are corrupt.
The problem of coming to agreement between a number of actors, some of whom are corrupt, is known as the Byzantine generals problem. It is well studied, and you may find it interesting.
I’m also interested in this topic, and I look forward to seeing where this line of thinking takes you.
I think he already came to some conclusions and you already gave some good references (which support some of the conclusions).
Do those methods have names or address problems which have names (like the Byzantine generals problem)?
This makes me think of “radiation-hardened” quines, quines that output themselves even after deleting any one character (or three):
https://github.com/mame/radiation-hardened-quine
https://codegolf.stackexchange.com/a/100785
I’m not familiar with the method used, but maybe it can be adapted to the case you are imagining? Maybe for simplicity only for the voting part of a redundant system.
IIRC in Byzantine fault tolerance the assumption usually is that cryptographic primitives can be trusted and for 3f+1 at most f nodes are corrupted. The corrupted nodes can output anything. E.g. the Dolev-Strong protocol only assumes (1) a known number of nodes, (2) a public key infrastructure and (3) synchronized communication. But I guess your thought is around someone corrupting a specific part of all nodes? Dolev-Strong assumes you run more rounds than there are corrupted nodes.
No, I’m happy to stick with the standard assumption of limited amounts of corruption.
However, I believe (please correct me if I’m wrong) that Byzantine fault tolerance mostly thinks about cases where the nodes give separate outputs—e.g. in the Byzantine generals problem, the “output” of each node is whether it attacks or retreats. But I’m interested in cases where the nodes need to end up producing a “synthesis” output—i.e. there’s a single output channel under joint control.
Did you look in places discussing ledger tech and proof of stake? If you are curious to see what’s been discussed, looking into that might be worth it. Information theory will mostly just focus on efficiency and practical trade-offs.
I’d expect the answer to not be apparent to an outsider, reading the literature, but I’d expect people who are good at designing those sorts of systems to be able to give you the answer quite easily if you ask.
Not exactly about adversarial error correction, but: there is a construction (Çapuni & Gács 2021) of a (class of) universal 1-tape (!!) Turing machine that can perform arbitrarily long computation subject to random noise in the per-step action. Despite the non-adversarial noise model, naive majority error correction (or at least their construction of it) only fixes bounded & local error bursts—meaning it doesn’t work in the general case, because even though majority vote reduces error probability, the effective error rate is still positive, so something almost surely goes wrong (eg error burst of size greater than what majority vote can handle) as T→∞.
Their construction, in fact, looks like a hierarchy of simulated turing machines where the higher-level TM is simulated by a level below it but at a bigger tape scale, such that it can resist larger error bursts—and the overall construction looks like “moving” the “live simulation” of the actual program that we want to execute up the hierarchy over time to coarser and more reliable levels.
For this we need a mechanism such that the maintenance of the mechanism is a schelling point. Specifically, the mechanism at T+1 should reward agents for actions at time T that reinforce the mechanism itself (in particular the actions are distributed). The incentive raises the probability of the mechanism being actualized at T+1, which in turn raises the “weight” of the reward offered by the mechanism at T+1, creating a self-fulfilling prophecy.
“Merging” forces parallelism back into sequential structures, which is why most blockchains are slow. You could make it faster by bundling a lot of actions together, but you need to make sure all actions are actually observable & checked by most of the agents (aka the data availability problem)
Just spitballing, but maybe you could incorporate some notion of resource consumption, like in linear logic. You could have a system where the copies have to “feed” on some resource in order to stay active, and data corruption inhibits a copy’s ability to “feed.”
There may be something to find in how distributed systems do leader election, and the leader can then be a majority trusted overseer. Note that I don’t really understand leader election.
When I wrote about AGI and lock-in I looked into error-correcting computation a bit. I liked the papers von Neumann, 1952 and Pippenger, 1990.
Apparently at the time I wrote:
I’ve forgotten the details about how this was supposed to be done, but they should be in the two papers I linked.