Sparkster Development Update. WE 7th September 2018.

Last week, we ended our discussion by pointing out that compiled code can be de-compiled or reverse-engineered, modified, and recompiled. This week, we will discuss the implications for us considering this fact and the steps we have taken to ensure that nodes are being truthful.

A rule in the software engineering space is to assume that the user is always acting maliciously. On a high level, this means that if our program is to receive input from the user, we must design our program in such a way so that if the user was to input bad data (such as a character sequence when we are asking for a number,) we are gracefully recovering from this problem by validating user input. On a low level, however, things become more complex than simply checking if the user’s input is what we expected. For example, a malicious user can execute a “buffer overflow” attack in which they directly modify the running program’s state or the program’s instructions themselves by providing a larger input than was expected, thereby causing the program to write to memory it should not be writing to. In the best cases, buffer overflow attacks result in crashes, but in the worst cases, attackers are able to modify the instructions of the program, possibly injecting malicious code. Computer viruses often use this technique to embed themselves inside unsuspecting computer programs, so that previously “safe” computer programs become hijacked at run-time.

A buffer overflow attack works because memory layout is well-defined on a system, so a malicious user simply writes into adjacent memory locations. While modern operating systems use “canaries” (preventing memory locations from being adjacent, or detecting memory overruns themselves instead of relying on the programs to detect them) to mitigate the problem, the best protection against a buffer overflow is still the developer; we cannot depend on the OS to randomize memory locations, because older operating systems are still not protected.

Another, and more difficult attack to solve, is the case of reverse-engineering. Here, the malicious user will de-compile a program, modify it, recompile it and trick a validation system into believing the program is the unmodified, safe version. For open-source software, where the code is freely available and modifiable, this problem is amplified tenfold because the malicious user can remove all validation checks, or replicate them with ease; more ease than they can with a closed-source solution.

In our situation, we have compute nodes which run virtual machines and execute code on our block chain. The question arises of how do we know the compute nodes haven’t been modified and are not acting maliciously? Instead of depending on the compute nodes themselves, we are validating the efforts of the compute not by demanding consensus. In Ethereum, for instance, a transaction is not considered valid unless all other Ethereum nodes validate the transaction. In other words, all nodes will execute the same code the original node executed. Only if they all come to the same result will the execution be considered true and ultimately committed to the block chain. Ethereum does this because they cannot reasonably trust a node to act truthfully. The common philosophy in block chains is to assume that the acting party is guilty until proven innocent.

One thing we want to avoid with our block chain is latency due to consensus. Instead of having every node verify every other node’s transactions, we employ the assistance of verification nodes. The job of a verifier node will be to double-check a compute node’s truthfulness. The question then becomes that since the verifier nodes can also be reverse-engineered, how can we trust them? The answer is that we will trust them through randomness and demand consensus. We will use “master nodes” to randomly select verifier nodes to check the results of the compute nodes. The verifiers will come to consensus on the validity of the transactions submitted by the compute nodes. Only if a substantial majority agrees on the transaction will it be committed to the block chain; else we will consider the compute node to be untruthful, at which point the compute node’s stake will be taken. We will employ the assistance of some number of master nodes through a random voting process, and each master node will select, at random, one verifier node. Therefore, not all master nodes and all verifier nodes need to participate in the process of consensus. This allows us to arrive at consensus with low latency.

Now that we have written a system for verifying the compute node’s result and solved the problem of untruthful verification nodes through randomness, how do we solve the problem of untruthful master nodes? The answer here is that the master nodes will check each other. Additionally, they will employ true random number generation in a secure and verifiable manner, such that another master node will be able to check that some other master node did truthfully generate a random number. Since the random number generations will be true (we will discuss the meaning of “true” soon,) and verifiable, we can proceed to select a random collection of master nodes to choose random verifier nodes. Through this process of chance, we can effectively eliminate a majority attack based on malicious code.

Let us turn our attention to the use of the word “true.” In Computer Science, two types of random numbers exist: they are either pseudo-random numbers generated through pseudo-random number generators (PRNGs) or true random numbers generated through true random number generators (TRNGs.) The problem is that computers are not built for chance occurrences, so generating a true random number is difficult; they generally use a sophisticated enough algorithm given some pseudo-random input like the computer’s clock to generate what might look like random numbers, when in fact if the proper conditions are emulated, random numbers generated by computers are predictable, or deterministic over some period, hence the term “pseudo-random.” The reason there doesn’t appear to be a pattern is because modern algorithms extend the period enough to where most applications never reach the point of reset.

In order to generate a true random number, a computer must employ a truly random source. A common source is atmospheric noise to act as the input in a random number algorithm. Because the noise is unpredictable, the random sequence becomes unpredictable because the next random number in the sequence is directly related to the input signal (the noise the computer picks up.) Of course, this means that the noise must be random and should not be predictable, like in the case of a motor that has a well-defined period, making a motor an unsuitable source of input. Introducing a nondeterministic input into a random number algorithm effectively gives us a TRNG. Hence, true randomness is impractical for us to achieve.
Our approach to this problem is to generate a random number that we may consider to be sufficiently random. We must consider what is practical given the constraints of computers. For example, a string whose probability of being generated randomly is so small that there are more permutations of this string then there are atoms in the universe. A seed to your crypto wallet is analogues to this idea, it is extremely improbable to guess, so improbable that it may take thousands of years of computation to generate with a brute force methodology.

Along with TRNGs, a further consideration is verifiability of the result. We face a challenge here since TRNGs are nondeterministic and the input condition cannot be “replayed” unlike in the case of deterministic input to a random number generator. How do we verify that the number chosen was truly random if we cannot check the result directly? Our approach is to use a signature scheme to accomplish this, where the signature generated by the master node that generated the random number will give us the proof we require in determining the correctness of the result.