A gentle introduction to algebraic programs and mathematical machines
Programs as algebraic objects
When we think about programs we typically think about computer programs with user interfaces. Something like Microsoft Windows or an internet browser. Internally these programs are a sequence of operations on boolean variables. Symbolically call it where for some that is the architecture of the machine (e.g. 32 or 64 bit). Now, say that I want to prove to you that I ran a specific program and it generated a specific output . To do this I form a math problem that is only solvable given knowledge of (the input to the program). If the problem correctly constrains all dimensions of , then is an argument that a program was run at a point in time. Crucially, must be shaped such that a function exists (representing the validity of the argument).1
Thus we have the shape of an abstract computer as a pair of functions, prover , and verifier which separates the invocation and observation of a function in time:
A theoretical computer running a function , takes a vector of length as input, and outputs indistinguishable elements. The computer is conjectured to have existed by the verifier function which takes the indistinguishable elements and outputs if all the constraints of were fulfilled, and otherwise. The theoretical computer exists if the codomain (output space) of the prover function is equal to the domain (input space) of the verifier function , and the cardinality of the domain of is equal to the cardinality of the domain of .
This is a very strict definition of a mathematical machine insofar as it precludes the existence of invalid values by counting. In reality most systems have slack either as excess dimensionality which is algebraically restricted to fulfill the axioms above, or probabilistically introduced error terms (or both).
Interestingly this implies that lattice constructions can be converted to indistinguishable obfuscation devices by taking the lattice base randomly, instead of as a public constant. The topological shape of the resulting argument exactly matches all other arguments and the randomized lattice base selects a random pair from a high dimension space with cardinality matching that of the lattice base matrix. If the randomized lattice base is sent as an dimension seed for a csprng the cost of such a device is computationally negligible for both prover and verifier. This provides low cost hiding for an argument of knowledge (when compared with algebraic ZK shims), at the expense of requiring a shared secret (instead of embedding the hiding entropy in the witness).
This inverts the existential nature of a theoretical computer described above. Given an indistinguishably obfuscated program it can be verified and decoded given a seed which expands from oracle to a lattice base which is used to verify an argument of knowledge . Given that is a public token function, outputs can be revealed publicly but without the ability to verify validity, or restricted by knowledge of .2 The choice of whether outputs were revealed or not is itself known only to the participants of the system, except by inference/relativity.
A program expressed as a rank-one-constraint-system is a high dimension algebraic object, such that a valid run of the program fulfills . Accordingly, the iO shim described above can be implemented as a mask applied by the prover as , with the verifier function becoming:
In this case a client and a server would agree on a function defined as an R1CS. The client streams to the server which incrementally computes the relation above. This is analogous to a REST API or cryptographic serverless functions. The inherent algebraic nature makes mutating and reasoning about high dimension objects more simple.
This naturally implies things like heteromorphic encryption streamed over an iO device like described above. The more natural model for “the cloud” being theoretical chunks of data that users may write to algebraically. Put differently, a space of data that can only be mutated using a high dimension theoretical tool seeded with a shared secret.
notes
A physical computer argues its existence physically. A human looks at the screen and sees symbols which are consistent with their understanding. This gives rise to mathematical machines: machines that exist and run programs purely symbolically, which are then simulated on digital computers.