Sparkster Development Update. WE 24th September 2018.
Last week, we discussed enhancements in our architecture that will allow for guaranteed responses instead of risking that a transaction might be rolled back without the client knowing how to recover from such a rollback. This week, we will relate to the reader another obstacle that plagues all block chains: the problem of nondeterminism.
Recall that 21 verifier nodes will execute the code on our block chain, and through the common output of these nodes, we will be able to reach consensus or reject the transaction. In order to achieve this, we must be certain that the code executed by all 21 verifier nodes is constant. We will first describe the meaning of the word “constant.”
A constant piece of code, or a deterministic piece of code, is code that results in the same output given the same input. By design, all functions are constant. We consider functions to be atomic instructions like the ones we have discussed previously.
For instance, the MIPS Assembly instruction slt $d, $s, $t sets a register to 1 if the value contained in the left-hand side register is less than the value contained in the right-hand side register, and 0 otherwise. The reader should not concern themselves too much with the use of the word “register” here; it is sufficient to know that a register is memory housed on the processor that acts as fastest-access memory. A processor computes the slt instruction by performing left-hand side (called $s) – right-hand side (called $t). If the operation results in a negative number, some register, denoted by $d, is set to 1 (true.) However, if the operation results in a positive number, $d is set to 0 (false.) In Computer Science, a value that is less than or equal to 0 is considered FALSE, and a value greater than 0 is considered to be TRUE. So, slt can be conceptually performed according to the expression !($s - $t). This means that the result of ($s - $t) is “negated” or flipped, so that if ($s-$t) is TRUE (greater than 0,) the result would yield FALSE, and vice versa.
Suppose we give two values to slt (ignoring the register numbers and using the values directly): 2 and 3. The computer will perform (2-3) and get a FALSE value. It will then negate this value and get a TRUE value, which is the result we want because 2 is indeed less than 3. We consider this to be a constant function because given two inputs A and B, if A is less than B, $d will always be set to TRUE. Therefore, slt is a constant function.
The reader might wonder at this point that if atomic instructions such as the one we have shown are constant, how do computers make decisions, which look like nondeterministic code? To answer this question, we return back to the slt instruction with (2-3.) Here, $d has been set to TRUE. Another instruction in MIPS Assembly is the bgtz $s, offset instruction, which moves execution to a different part in the code according to offset if the value contained in $s is greater than 0. Thus, if we wanted to make a decision, we would first set $d to 1 by executing slt given the inputs 2 and 3. Next, we would execute the bgtz instruction given $d (1) and some offset. The computer will see that $d is greater than 0, and will execute a different part of our code according to offset. Notice here that bgtz is also a constant instruction. So, given slt(2-3); bgtz($d, offset), the computer will always perform constant execution.
Variable functions are made up of these smaller constant functions, so while a larger piece of code might be variable, its underlying instructions are constant.
Constant versus variable functions pose a big problem for consensus in block chains. If we have 21 verifier nodes performing slt and bgtz given 2 and 3, our results will be consistent. However, if we execute a larger piece of code, such as one that fetches external data, such as the current time, every verifier node will fetch the current time and compute the function based on the time it has received. This means that all verifier nodes will arrive at different results, and the transaction will be rejected. For instance, if each verifier was to fetch the current point-in-time value of $s, the point-in-time value might change over time, so some verifiers will compute (2-3,) resulting in $d being set to 1, and others will compute (5-3,) resulting in $d being set to 0. So while the underlying functions might be constant, the code execution becomes variable because its inputs are variable.
It becomes obvious at this point that the problem is that of variable input data. Computers are constant execution machines, and are given the illusion of being “smart” by changing their inputs. Block chains solve this problem by restricting all functions to deterministic functions, and disallowing execution of nondeterministic functions so that every node executes the same piece of code and arrives at the same result as its predecessors. However, if we were to take this approach, most of the power of our platform would not be realized on our block chain because we would have to disallow the ability to fetch variable data, such as data from the Internet, to perform a computation. Considering this, our solution to this problem is to execute the code in its variable form only once.
The execution of the variable (or nondeterministic) code will not only execute the code, but will also expand the code to its constant or deterministic form. In other words, calls to external resources and other variable data will occur only once, and the constants that result from these fetches will be injected into the code executed by all other verifiers, making the code constant. Each verifier will only execute the deterministic version of the code, thereby reaching consensus easily.