Echoes from the Future – Chain Reorganizations

As I start writing this post, it is January 2021, and it is snowing. Looking back at the last year, I feel the weather pretty accurately reflects the activity in this blog during that time. My contributions seem as scarce as shoots of green leaves emerging from the winter snow. But if I cast my mind’s eye to the imaginary alter ego that adventures in the pages of this blog, and try to picture my professional endeavours in 2020 as travels through fantastic landscapes; if I see him resting atop a vantage point and looking around to the distant horizon, then he is now far, far away from his starting point.

Long gone are the green moors of Ethereum, the subterranean caves of Zero-Knowledge, or even distant strolls around the lakes of Token-Bonding Curves. This year, the battle has been among rocky, inhospitable hills, in loftier surroundings and within a larger fellowship.

It’s not been an easy year, lots of things have changed in our lives, that made us focus on the essentials and avoid other distractions. Aside from personal life, the whole nature of what I do at work also changed dramatically. This year has brought a wholesale change from researcher and engineer to manager of a team of almost 10 people developing a blockchain on Substrate, the technology powering Polkadot. All along we had to deal with all the changes due to the Covid pandemic, and to top it all, the year ended with a transfer to a sister company. Wow, talk about changes and adaptation!

I haven’t found much time to think and write for this blog, but there are many interesting problems in Substrate. The nature of the issues I face every day has changed dramatically, and perhaps as a consequence so will the tone of this blog. But it’s all part of the journey.

And with this introduction, let me introduce you to one of the most beautiful, inspiring and fascinating bugs I have ever found in my career: a message from the future!

An impossible bug

Off the bat, it may be surprising to call a bug “beautiful” or “inspiring”. But its nature is so different from run-of-the-mill software bugs, that in order to explain I require metaphors that send me easily to other worlds. Stay around, and I’ll try to convince you. A fair note first: this post is just an appetizer, and I will leave the technical stuff for the next one.

It was Friday afternoon. After another long week, I was getting ready to call the day off, pack the computer and get ready for the weekend. But that was too optimistic a thought.

One of my teammates approached me and said in more or less these terms

“Houston, we  have a problem”

“Is it serious?”

“It can be”

This set me up. The tone was ominous. In the next hour or so, we forensically confronted, analysed and debated a problem that on the surface seemed impossible, but nevertheless uniquely exemplifies the nature of blockchains in such a way that it may be mind-bendingly unapproachable to those who are not immersed in this technology every day.

For business reasons, I’ll just use an abstract model that I will summarize here. We have an operation in 4 steps:

1. Blockchain validators agree on an action that requires a call to an external (asynchronous) system
2. A blockchain agent issues a call to the external system
3. The external system receives the request, updates its state and returns a result
4. The result is given back to our blockchain and used to update its global state

It’s not important now to explain why we need this structure. And be advised that I have simplified a few of the steps above, to avoid having to explain just yet deep Substrate technical concepts like Offchain Workers and Unsigned Transactions. Suffice for now to say that this is just a bit like two distributed systems communicating, with the caveat that at least the initiator is a blockchain.

Now, normally this structure works down to a T. But my friend found evidence that sometimes the last step was just being rejected. To make it worse, all the data were correct, the request had been correctly understood and answered in step 3 and there was no obvious reason for the result to be rejected in step 4. Except, that is, that there were no records on the blockchain that the request had ever been made!

Ok, let me try to explain in other words. This is a blockchain we’re talking about, so there is a record of everything we do. And so, for example, in block 100 we have a transaction (in Substrate lingo, we use extrinsic instead) that states we are going to create a request for an external system. 

We do some houseworking, and finally have evidence on block 105 that the request is going to be created by an external agent (technically, an offchain-worker) and will have a unique identifier. 

Finally, we receive another transaction with the result of our request (so that all validators can verify it and change the global chain state) in block 103. Yep, before we were ready to send it.

Wild explanations

Did I get your interest now? When I first heard this description, some interesting analogies sprang to my mind. Ghosts coming from alternate realities; quantum parallel universes; relativity and time-travel. I think the quantum parallel universes are the aptest metaphor here, but I also find it tends to be remarkably inefficient to use any part of quantum mechanics, and much less the multiverse and the theory of parallel worlds, to make any other matter simpler. So, I’ll postpone that a little and start with something else.

Let’s agree that time-travel does not exist in the universe as we know it and that because of that we can’t have programmed it in our blockchain. Ghosts, extra dimensions and other planes of existence are not that far off the mark here, but I haven’t quite found a way to introduce them in an explanation. Let’s go with a little sci-fi scenario.

Imagine that our blockchain is like a generation ship going through space. In our analogy, every time a block is added to our chain, time advances for our ship and it moves a bit through space. When our blockchain sends a request to the external service, the equivalent action for our ship is that a small shuttle is dispatched to a nearby planet. This is an asynchronous request, whatever the settlers have to do takes time, but eventually, they’ll be back and catch the ship at another position: several blocks will have passed for our blockchain.

That is the normal case. But in our bug scenario, what we see is that the shuttle arrives before it leaves the mothership. The trick here, and the solution to our problem, is that the mothership the shuttle left and the one it returns to are not exactly the same. Sure, they have the same name, length, even people and share all the same history: up to just the tiny little bit of recent past time around this whole shuttle business. Somehow, this ship is another “version” of the original one. Another alter-ego.

I’m sure it’s hard to wrap your head around this, because there is nothing in your macro reality that resembles this scenario. The closest thing people will be more or less ready to acknowledge or recognize is something of supernatural origin: a ghost, a reflection, a memory, a resonance of that ship-entity. Not to say that we will believe it, but pop culture is littered with references and tales around this sort of object.

But that does not explain why that second ship would be there or how its timeline would be so close to the original one. It’s not entirely a good simile of our blockchain scenario. For that, dear reader, I’m afraid I will make use of quantum parallel universes. It would be either that or Non-Deterministic Turing Machines.  Both are quite technical and esoteric, and in my view, share quite a few similarities, but at least the former notion has a certain allure and pop culture appeal the second lacks.

Quantum Multiverse and Parallel Realities

So, what is this business of the Multiverse?

You may have already heard of Schrödinger’s Cat (and in a bit more depth here), which hints at one of the fundamental Weirdnesses Principles of Quantum mechanics: the Superposition of States. This is the notion that a quantum particle’s current state can be described as a complex addition of varying degrees of simpler, observable states. Perhaps because of the similarity to how any periodic wave can be seen as a composition of simple sine-waves of varying frequencies, the mathematical equation describing this state superposition is known as wave-function.

In the observable world, the particle can only be in one of the observable states, so at some point, we have to transition from the state superposition to a well-defined state. The traditional (Copenhagen) interpretation states that when we wilfully observe the state of the particle, its wave-function collapses and we see only one of the base states that compose it. The function accurately predicts the probability for each state to appear as the outcome of the observation.

So, instead of saying that Schrödinger’s cat is either Alive or Dead, we say that it is both alive and dead in superposition. And we can say more, we can say there is a factor associated with both states so that there is a probability a that the cat is alive, and a different probability b that it is dead and that a + b = 100%.

Now, the Many-Worlds Interpretation states something very different. In it, there is not a single reality (the one in which we happen to live) nor a wave-function that collapses. Instead, there are multiple timelines in multiple parallel universes all existing at the same time. In each timeline, there is no uncertainty and there are no probabilities. Although we can still look at an observation we have not yet made as having an essentially unwritten result, the fact is that after we measure it we are never able to go back in time and repeat it. In other words, we can adopt the fateful view of the believer and say “Maktub! It was written!” and assume whatever result we got was predetermined and fixed since the beginning of time in this corner of the multi-verse.

However, in another close universe, a sibling of this one that had exactly the same history up to our exact observation, the result may be different. Let me reinforce this a bit more, just for clarity. Our experiment, our single observation, created two universes (assume for simplicity we have only two observable states) that are exactly the same until the point of this observation, and differ only in its outcome.

In our universe, the observation returned result A, and in the second universe, it returned result B. And in both, this different result would have been equally an unavoidable choice of fate.

There are a few reasons why I don’t like this interpretation. The main one is that it requires a practically infinite multiplication of universes at a highly exponential rate. Every little quantum choice we make requires the fork of a universe in two, and since all universes carry on indefinitely side by side, at every moment the number of universes is doubling. In 10 steps, we would go from 1 to ~1000. In 20 steps, we’d go over one million. In one life of the universe, the number of universes required would be beyond astronomical, an astronomical number of times.

But there is one thing that will be very familiar to computer scientists. The history and the creation of universes is organized in a tree structure. Every universe has a parent, which has one or more other children. The birth of a universe is the point at which its history diverged from the parent’s, which carries on in its own timeline. But none is more valid than the other: you could also look at this “second” universe as the canonical one, and that the other one, instead, is the one which diverged.

Think, rather, of these two universes as siblings, with a common parent. And of this parent as being not a universe itself, but rather “the common history of these two universes”. In this way, every universe will have a parent, and a grand-parent and so on until all universes converge to a single unique, genesis event.

Where does this lead to?

I’m sure there are many people out there who are fascinated both by computers and Physics. If you are not one of them, I am sorry. I will finish the Physics digression here, and simply point that we are close to where blockchains make sense again. I even dropped some hints in the last section.

But I don’t want to tax my readers too much. This post will stop here, and work as an appetizer for my next one, where I’ll explain the relation between this Many-Worlds interpretation and Chain reorganizations.