Execution, Ordering, History and State Machines

What Is This All About? and Blockchain-based Authorities were in very abstract terms; we called blockchains digital a Authority without much detail into how they actually work. Into the next two chapters, we take 2 steps towards making this more concrete in two steps.

Verifiable Execution

Recall that so far we modeled authorities down to two components:

• State
• Mutation on the state + its rules

But we didn’t emphasize much on what the said rules are and their importance. After all, to trust an Authority, we need to have an expectation of what it would do. Therefore, we can update our model of an Authority to the following:

• Having a set of rules
• Holding a contentious state
• Performing mutations on the state based on what the rules say, and input from a user (or generally the external world).

Interestingly, this very much resembles what a computer program running on a hardware does:

• The code of the program defines the rules
• The code has access to a persistent memory (state)
• Execution of the code updates the memory
  • Execution of the code may receive some user input to its execution

Another mathematical representation of this would be $F(x,y)\to y\prime$.

• $F$ is the rule of the system, the program’s code
• $y$ is the current state of the program’s input memory
• $x$ is the input defining the mutation
• $y\prime$ is the output of the mutation, the program’s output memory

For example, $F$ is the function that determines the rule of transfer of value in a digital bank, $x$ is a transfer instruction, $y$ is the current balance of all users, and $y\prime$ is the balance of all users after the transfer $x$ is done.

Then, you and I want to execute $F$ to perform a transfer, and agree upon a $y\prime$. Neither you nor I trust one another, and we need an Authority to execute $F$ for us.

We can either delegate this to an authority with Human-based Trust such as a normal bank, or delegate it to a blockchain (with programmability like Ethereum) to achieve Science-based Trust.

So, the first property of a blockchain is verifiable execution of code. Knowing what $F$ is, we can be sure that it is being executed correctly

What about me running an open source code on my server/machine, and letting you verify it however you want?

Yes, that would partially work too, but then we are faced with a number of other challenges. Suppose I am the untrusted party that you want to interact with. Even if I show you the source code of ($F$) of what I am about to execute on my machine, how would you my machine actually did that? Perhaps you want to re-execute the same thing in your computer. If you go down this rabbit hole and do it right, you end up re-inventing all of the core technological pieces of what a blockchain does, explained in this chapter and the next one.

Ordering

Then, imagine we have two subsequent transfers, $x_1$ and $x_2$:

• $F(x_1,y)\to y_1$
• $F(x_2,y)\to y_2$

And in both, $F$ is executed correctly.

But, we still need to decide whether $x_1$ happened first or $x$. Imagine Alice has 10 dollars. $x_1$ is meant to credit 5 to Alice, and $x_2$ is meant to debit 12 from her. The second transfer is successful IFF $x_1$ happens before $x_2$, but not the other way.

So, we need to decide if the above mutations are:

• $F(x_1,y)\to y_1$ , and then $F(x_2,y_1)\to y_{21}$ or
• $F(x_2,y)\to y_2$ , and then $F(x_1,y_2)\to y_{12}$

This is when we realize that a blockchain has to not only execute a code correctly, but also has to determine the correct order of code execution. Without going into how this is achieved, you can take for granted for now that blockchains do solve this problem by establishing a correct order of events. This is often called the canonical order.

In the blockchain terminology, this situation is called a Fork.

Auditing

But is this enough? Yes and no. Suppose we are given the current state of the system, after $n$ mutations, $y_{n+1}$. Without any further means, we would have to trust that $F(x_0,y)$ all the way up until $F(x_n,y)$ has been executed correctly.

One great additional property of Science-based Trust is that, because it is based on rules of mathematics, it is easily auditable. As in, given the public and permissionless rules of the system, one can easily re-execute $F(x_0,y_0)$ all the way up to $F(x_n,y_n)$, and come to the conclusion that $y_{n+1}$ was indeed correct for themselves.**

So, the third property of a blockchain based system is that the entire history is auditable.

Genesis And Syncing

This is why in blockchain systems the notion of a genesis data and syncing is very prominent. We often hear the phrase “you can sync the blockchain”. This means, given the initial state of the system, which is called the “genesis state” ($y_0$), and the known rule of the blockchain, $F$, you can always re-execute (audit) the entire history by executing $F(x_0,y_0)$ all the way up to $F(x_n,y_n)$.

In other words, knowing:

• $y_0$
• $[x_0,x_1,...,x_n]$

You can always re-execute the whole sequence of mutations to reach any final state $y_{n+1}$:

• $F(x_0,y_0)\to y_1$
• $F(x_1,y_1)\to y_2$
• …
• $F(x_n,y_n)\to y_{n+1}$

This is why it is important for all blockchain systems to retain their history of user inputs ($[x_0,x_1,...,x_n]$) as well.

Note that this is not always possible in the Human-based Trust. While audits and regulations are indeed a thing in for Human-based authorities, they rely on further Human-based trust to be verified¹. Moreover, very often the chain of trust is based on the assumed good intention of people, which can never be retroactively audited.

State Machine

Finally, we can model the above 3 properties into a single mathematical model that encapsulates it all, a deterministic state-machine.

..a state machine is an abstract machine that can be in exactly one of a finite number of states at any given time. The state-machine can change from one state to another in response to some inputs; the change from one state to another is called a transition

Moreover, the rules of this change are defined as State Transition Function (STF). Anyone can re-execute the STF from the initial state, and come to the same final state.

So, to take our above example, $F(x,y)\to y\prime$, and model it as a state machine:

• $F$ is the State Transition Function
• $y$ is the current state
• $x$ is the input to the mutation
• $y\prime$ is the new state

graph LR
y["$y$"] -->|"$F(x,y)$"| yp["$y\prime$"] -->|"$F(x,y\prime)$"| ypp["$y\prime\prime$"]

Summary

This chapter was our first step towards a more concrete definition of blockchains. Within it, we modeled blockchains as a system that can do the following:

• It is a verifiable computer that executes some code (its defined set of rules) correctly
• While doing so it maintains a canonical order of events
• It retains enough information for anyone to re-audit the entire history.

We also noted that instead of a computer, a State Machine analogy can be used. This in fact summarized our main 3 abstract mental models to think about blockchains, all 3 of which are listed in Blockchain Models.

Next

We will next take the last step towards a concrete definition of blockchains in Blocks, Transactions, And Blockchain Systems.

Footnotes

1. the phrase “who polices the police?” encapsulates well why auditing a human-based trust often relies on further human-based trust. ↩