Urbit and Crypto Synergies
What is this about?
As a mathematician/cryptographer working at Chorus One in the role of Team Lead, I tend to dive deep into the fundamentals of cryptographic, tokenomics and consensus protocols while helping out with due-diligence for investments and network onboarding.
Crypto has been a passion for a long time and it graduated to a work/life obsession in the last 3–4 years. More recently, I have also been diving into Urbit although, on that, I still need to familiarize myself with a lot of the terminology and the overall philosophy.
This article, the second of a series of three on Urbit and Uqbar pieces published by Chorus One, is an attempt to report on my findings and what I consider great about these two projects from a technical perspective. Also, last but not least, it touches on how this all relates to crypto and the fundamental problem of “Crypto = Web3”, explored in the previous article on “Why Web3 needs Urbit”.
There was a certain moment I had when learning about Crypto that one could categorize as an “A-ha!” moment. I really see how this technology can — although not guaranteed — revolutionize how we get together to build things and solve problems.
Similarly, I think a little while back I got an “A-ha!” moment with Urbit. I understood what it was and why it was different. Why perhaps its idiosyncrasies are a feature and not a bug, and how this technology can change how we own private data and compute over it.
But it was just recently that I had a “Eureka!” moment! I know, I’m slow to catch on. It was when I identified the potential synergies between these two realms of blockchain and Urbit. My ideas were embryonic to say the least, and certainly not original. As usual with such things, brighter minds had similar ideas before, and I was very happy that in this case, not only have they arrived at similar conclusions, but the technical execution is much more sophisticated than I had first envisioned.
This article tries to describe each of the ideas involved: What is a blockchain, what is Urbit, and how Uqbar — the first project trying to unify both — is a gem among gems.
Let’s dive in.
What is a blockchain?
Please take a look at this picture. If you have some experience with Crypto, you might identify this somehow.
What you are seeing is an often idealized picture of a blockchain. Each diamond shape represents the state of the chain at that given moment in time. The squares are what is called a block — where the blockchain name comes from — and it contains a set of transactions.
These blocks update the blockchain state in a predictable and sequential manner, represented by the solid vertical lines. Here a transaction can be any data that you want to persist, for example, one encoding the transfer of value. But blockchain technology promises you that they have a mechanism to permissionlessly replicate this structure and to allow any participant to introduce said transactions.
By “permissionlessly”, I mean that so long as you satisfy open and well-defined requirements, no one, not even some set of participants in the network itself, can censor you, i.e. forbid you from replicating or participating in the network.
One can debate to what extent existing blockchains satisfy this property, but it cannot be argued that in principle this is true. Similarly, no one can censor you from sending transactions to the network even if you do not participate fully in the network, that is, you are not replicating this data structure yourself.
On can (understandably) ask oneself, “What is the use case here? Why would someone do something so inefficient?” To this, in my opinion, the answer lies in trustless decentralization.
Applications like payments are an obvious candidate, as the trustless decentralization afforded by cash systems are running against market-fit difficulties in the age of information: for example, you don’t truly own your bank balance as anyone who witnessed a bank run can attest. But due to the ability of many blockchains to support arbitrary computation, there is no limit on the applications that can be run in a trustless and decentralized manner.
Decentralized finance or DeFi is a prominent one but gaming, supply chain tracking and verification, identity distribution, crowd funding and many others are in sight.
A blockchain is able to accomplish all this by merging three paradigms: cryptography for verification, deterministic processing for replication and incentivization for bootstrapping and security.
What you see in the picture above is the idea of determinism: that a new block is deterministically computed from information contained in previous blocks plus new inputs. Since every network participant, when honest, computes the exact same thing, this makes it easy to essentially ”vote” on the current aggregated correct state of the chain, that is, its replicated state.
For the purposes of the present article, this is enough of an understanding of blockchain technology, but I would like to add one particular aspect of the cryptography of blockchains that will be important later on. That is the idea of a Merkle tree. A Merkle tree looks like this:
This is a binary tree! A binary tree is a data structure formed by nodes and directed edges. Each node can contain arbitrary data and incoming and outgoing links to other nodes. In a binary tree each node can have at most two children (incoming edges) and one parent (outgoing edges). A leaf node is a node without children and the root node is the unique node without a parent.
The special thing about it is how it is constructed and its purpose. A Merkle tree serves as a short cryptographic proof of the integrity of an ordered set of data. Imagine that you have an ordered set of data.
For example, a list of transactions. Here is how to build the Merkle tree for this set. You select a hash function and apply it to each transaction. You define these hashes to be the leaf nodes of the tree (the base layer) while keeping the order. Then, you iteratively build a parent node by concatenating the hashes of two neighbouring nodes and hashing it. At the end, the root node is called the Merkle root of the tree.
Its purpose: proof of inclusion. You want to be sure that your transaction has been included in the block that was processed. We can use Merkle trees for this because the only way to arrive at a given Merkle root is via this specific ordered list of transactions! Any change in order or content is detectable since it changes the Merkle root.
If you sent one of these transactions and know its position in the block you hash it and use the Merkle tree to see if it matches all the way to the root. Notice that you only need the hashes of the tree along your path to the root. This is why it is so efficient.
As an extra bonus: error detection. We send transactions over the network together with the Merkle root. The chances that the Merkle root (being short) is corrupted while in transit is much smaller than the chances that a set of transactions is corrupted. At the destination, we compute the Merkle root from the transactions and compare. If they match, we can be certain that the blocks arrived correctly.
For the interested: the main reason for this is that the hash function is close to what we call a one-way function.
What is Urbit?
Now take a look at the following picture:
What you see is Urbit, or an idealized representation of it. Urbit is the first completely functional stack starting at the virtualized operating system up to a computer identity and networking layer.
Here, each diamond represents the state of the computer. The whole computer! Again, the whole computer: memory contents, code, networking stack, buffers and, crucially, identity! Also here, each block represents inputs. Any input. Of course, invalid inputs are ignored, but correct inputs cause the system to update its state in a deterministic manner. This is what is meant by functional.
Like triangles only exist in Plato’s ideal world but interact with the real world via something we call “brains”, so does a functional machine need to interact with the real world. So there is a “brain” in the form of this thin runtime layer that takes care of this interface and allows us to scry the Urbit state.
In Urbit the state can be interpreted seamlessly as a number. A gigantic integer: 2Gb (giga-bits) long! That is a number with approximately 400 million digits! Under this interpretation, one can think of the squares in the image as other numbers (input numbers) and the horizontal arrows as a very complex equation using weird operations that take the state number and the input number and computes a new state number.
Well, THAT is Urbit! But that’s not all: the beauty of Urbit is that it figured out a way to design everything in such a way as to keep this representation intact but actually have a very simple state transition equation. Well, it is still too complicated to be of practical use for a human but it is simple enough for a human to understand what is going on.
This is similar to how one can understand general relativity and develop an intuition for it despite most calculations — except for the most simple ones — having to be left to a computer. This is what is meant with “Urbit is simple and a single developer can understand it all”.
I will go briefly on how this is done below but before that, a reader might rightly be wondering: “But isn’t this how every computer works? Aren’t these all 0s and 1s encoded in some way?”. I want to address this insightful question. The short answer is no. The long answer goes into the heart of what is meant by deterministic and being a true Turing machine.
Urbit being a true Turing machine is, as mentioned above, defined by its starting state and state transition function. It is a mathematical function acting on natural numbers. In this comparison, an ordinary computer is messier. An imperfect but useful analogy is that an ordinary computer is instead like a function on a subset of the real number line.
It is not defined for all numbers, only a subset, and even for the numbers for which it is defined, any small imprecision might cause you to fall outside of this set and fail. Anyone who has worked on trying to build performant mathematical libraries that need to work with arbitrary approximations of irrational numbers using the IEEE floating point specification knows the pain (there are more of us than rightfully deserved), and that’s why we tend to stay away from 80s FORTRAN code. It is not that we can’t rewrite it in C, but we cannot guarantee that it won’t break anything down the line!
As an interesting side note, recall that we shun floating point numbers in the EVM (the Ethereum virtual machine). If you recall adding a token to your wallet in Ethereum you must have noticed this “decimals” field. This is because we would like to represent and work with fractional amounts of this token but the EVM does not support it. Every ERC20 token contract stores address balances in an unsigned integer and there is the “decimals” constant that specifies where to put the decimal point for correct visual representation (usually 18).
So, returning to the Urbit “axiomatic description”, the first step is to define your state number as a specific encoding of a binary tree. So now your state is represented in a data structure as follows (see the previous section on blockchains for a more detailed description of a binary tree):
Each node contains what in Urbit is called an atom and is just a natural number. Here already an important simplification occurs: normally natural numbers and computer unsigned integers are beasts of different worlds: the Platonic world of mathematics and the real world of computer science. In Urbit we are in the platonic world! It is difficult to overstate the importance of this quality to developers.
Next and main step: we build a computer. Perhaps you heard about Conway’s game of life. It is a simple example of how to do this: define some rules to transform some data structure (the state) and show that it is a universal Turing machine. I don’t want to digress here so I will just say that this is exactly what a computer is: a universal Turing machine. The things that can be computed are exactly the things that a universal Turing machine can do.
So in our situation, we do the same: define a set of operations transforming this binary tree so that in conjunction they form a universal Turing machine. We can now encode any algorithm as a sequence of these operations on this binary tree.
This set of operations, together with the initial state of the binary tree, define an input format where a number as input can be interpreted as a pair
(program, arguments), where the
program is the set of operations to perform and
arguments are any extra input for the program. It can then follow the set of instructions and compute a new end state of the binary tree (or never halt).
Urbit found a way to make this work with just a set of 12 operations on this binary tree. It can famously fit on a t-shirt. This encoding standard and set of operations are called Nock and it can be seen as the assembly of Urbit. Here it is — taken from the Nock definition page — in all its glory but still needing some explanation we won’t go into.
Nock 4KA noun is an atom or a cell. An atom is a natural number. A cell is an ordered pair of nouns.Reduce by the first matching pattern; variables match any noun.nock(a) *a
[a b c] [a [b c]]?[a b] 0
+[a b] +[a b]
+a 1 + a
=[a a] 0
=[a b] 1/[1 a] a
/[2 a b] a
/[3 a b] b
/[(a + a) b] /[2 /[a b]]
/[(a + a + 1) b] /[3 /[a b]]
/a /a#[1 a b] a
#[(a + a) b c] #[a [b /[(a + a + 1) c]] c]
#[(a + a + 1) b c] #[a [/[(a + a) c] b] c]
#a #a*[a [b c] d] [*[a b c] *[a d]]*[a 0 b] /[b a]
*[a 1 b] b
*[a 2 b c] *[*[a b] *[a c]]
*[a 3 b] ?*[a b]
*[a 4 b] +*[a b]
*[a 5 b c] =[*[a b] *[a c]]*[a 6 b c d] *[a *[[c d] 0 *[[2 3] 0 *[a 4 4 b]]]]
*[a 7 b c] *[*[a b] c]
*[a 8 b c] *[[*[a b] a] c]
*[a 9 b c] *[*[a c] 2 [0 1] 0 b]
*[a 10 [b c] d] #[b *[a c] *[a d]]*[a 11 [b c] d] *[[*[a c] *[a d]] 0 3]
*[a 11 b c] *[a c]*a *a
This pseudo-code is defining the operators
*. Please go check the source linked above. But here is a short description of these operators:
?checks if a noun is an atom or a cell.
+is the increment function on atoms.
=is the equality operator on nouns.
slot) is a tree addressing operator. So
/[x y]is the subtree of
edit) is for replacing part of a noun with another noun.
#[x y z]replaces the value at slot
/[x z]) with
[x y]is the Nock interpreter function.
xis the subject,
yis the formula.
Not only did Urbit come up with an economical definition of a functional computer (a universal Turing machine in this case) but it made it practical and modern. Urbit is implemented in C as a VM. The performance is already good enough to be useful and there is an engaging community of developers making real-world applications for it. One of them is Uqbar.
There are two very important aspects of Urbit that I still did not touch upon. The goodies don’t end here. First, Urbit is a computer with an identity. More precisely, in the initial state definition of an Urbit instance, there is already encoded a boot procedure that requires a specific kind of cryptographic secret key. Those keys are finite in number and can only be obtained, or correctly derived if you own a type of NFT on Ethereum. The choice of Ethereum here was arbitrary; they chose to use a blockchain for this and chose Ethereum because of its maturity as a platform. More importantly, that means that each Urbit computer is uniquely identified.
Second, Urbit uses this property of identity to pre-define a complete network topology layer for all of the Urbit computers in such a way that routing packets is simple and private — via encryption — between sender and receiver. This consolidates IP, routing tables, DNS, and TLS/SSL all into one single transparent stack accessible by default to any Urbit computer. You just need the receiver’s name (or identity) to be able to talk to it securely and privately. These are called “@p” and take the shape of a tilde (~) followed by a few pronounceable syllables. For example, I’m
Finally, this network is functional and typed in the computer science sense. Every packet in the network is typed and will yield the same result (return packet) every time it is applied to its destination (if it is online). This forces the input packet to contain all necessary input to be properly decoded and inserted into the destination's transition function.
The power of computers with identity cannot be understated. It turns computers into avatars of its users uniformly for all applications. Since the identities are scarce (finite), this helps build a social reputation system in the network and disincentivizes bad behaviors like spamming.
On the other hand, Urbit wants to be a new private server for every user, so that we don’t need to use and keep our data in centralized services. Going back to the pre-internet era is not an option either. We are social animals, and computers are most valuable to us when we use them to network and collaborate. But there is one thing missing: we can message but we can’t transact. We have an identity, but that’s not enough for trust.
Urbit is missing a shared trustless and permissionless piece of state. A blockchain. Enter Uqbar.
What is Uqbar?
Uqbar is exactly what was alluded to above. A part of the Urbit state that is shared in a permissionless and trustless way. It is a blockchain whose client is an Urbit application. So if you think about it, much like the movie Inception we implemented the state transition of the blockchain as part of the state transition of the Urbit computer. Running a blockchain is executing its state transition and we do it by executing Urbit’s state transition.
This is not so shocking when stated as implementing a universal Turing machine — for example, the EVM — in another universal Turing machine. The first and third figures of this article, as you may have noticed, are the same figure after all! But this can be viewed better as enlarging the blockchain context to have at its disposal a full operating system stack. We will go through what this implies in the next section. In this section, I want to delve a little deeper into some aspects of Uqbar to clarify what I meant in the beginning of the article when I said that “the technical execution is much more sophisticated than I had first envisioned”.
If Uqbar was “just” a blockchain client implemented in Urbit it would already be pretty exciting. But Uqbar has a few other things going for it. Most notably, it comes with a compiler that can take any arbitrary Nock code and generate a zero-knowledge prover and verifier for it. Thus not only execution of on-chain code paths, but off-chain as well. This is absolutely huge and goes back to a combination of the functional aspect to the simplicity of Nock.
Recall, Nock is Urbit “assembly” and it translates any algorithm to a lengthy sequence build of 12 basic Nock operations. Seizing the opportunity, Uqbar built a zero-knowledge prover/verifier circuit for each of these operations. This means that block proposers — known as sequencers in Uqbar’s parlance — can post proofs of correct execution when emitting blocks, and verifiers can quickly verify correctness. I won’t go into more details of zero-knowledge magic, there are plenty of good introductory articles about it like this one. Note that, to be precise, we are not even exploiting the zero-knowledge aspect of it only the computational compression aspect.
This allows for very powerful light clients. Since Urbit computers have identities, Sybil resistance is trivial: Uqbar block verification mechanism can be configured to demand verifiers to be stars[¹], and stars are by nature intended to be service providers.
They maintain the state and archive the blockchain while providing state bootstrapping to the light clients. The light clients can/would be run in any end-user ship. This is how blockchains are supposed to be accessed: in your local always-on server. Because it is always-on and maintenance-free, light clients can be bootstrapped once and (almost) never again without the need for an external (to the network) data availability layer much like the Mina network.
But this still goes beyond all of this. As mentioned before, the proofs can be proofs about statements outside the chain, i.e., any Urbit computation. This of course has some caveats as, for example, the off-chain state — at least in some obfuscated form — has still to be made available to verifiers somehow. Nonetheless, it is to be expected that this will have incredible applications in the future. More on this in the next section.
An Urbit application, being a subtree of the state tree, can easily and transparently access read-only information in the Uqbar shared state. For example:
- A front-end for your favorite DEX is distributed via Urbit’s network and runs locally on your Urbit ship. It is uncensorable. It connects to your local copy of the blockchain in case you have it or to any one providing this service via service discovery.
- Similarly, any application can write to the blockchain in the form of emitting signed transactions.
- This application or frontend can perform any kind of off-chain computation and keep this data local to the Urbit instance.
This last point was alluded to in passing in the last section but is worth elaborating on. It is not easy to accomplish this currently, and dApps tend to go to decentralized “indexers” at best or “trust-bottlenecked” services like Infura or OpenSea at worst. A very good read describing this problem, and probably the fairest criticism of “Web3” around, is in my opinion My first impressions of web3 by @moxie.
💡 An Urbit application is free to run and process any “indexing” required to give the user the best UX while keeping this data private.
ZK technology is a game changer and what is/was holding it back is the computational burden for generating proofs. Despite Ethereum recently moving to PoS, and in doing so abandoning wasteful PoW mining, there are multiple projects considering mining hardware — GPUs, ASICs and FPGAs — for proof generation. Talk about full-cycle. Performing this computation exclusively on block proposers is useful but limiting.
One can imagine that in a completely functional OS and network stack, where everyone has access to the shared state while being able to keep their own personal relevant state and emit proofs of statements about it, the lines between on and off-chain will be so blurry as to be meaningless. Well-designed applications will be truly decentralized (as in uncensorable), private (as in they will leak only the necessary information), and scalable (as most computation can/will be done locally).
As a concrete example, one can implement a country’s complete tax system in such a way that the government does not know what particular transactions were made, but they can be sure that they are correctly taxed and paid. This is, of course, very very far off, but it is in the realm of possibility.
It is our belief that the synergies of these two truly remarkable, not too technically dissimilar technologies can truly unlock the capabilities of Web3. In this paradigm, businesses and organizations (DAOs) can prop up from just a few collaborators and truly be uncensorable. Value can be derived from direct measurable KPIs, and not by external parties (most of which are not even democratic in nature, much less egalitarian).
As a final, more immediate set of examples: we can have an automatically monetized, decentralized, uncensorable github, twitter, office, zoom (in small caps!). Games, forums, email: anything in Web2 has a better version here.
[¹]: Planets, stars and galaxies are how Urbit calls its computers depending on their position on the the a priori defined network topology. See the previous section.