Edge Cases: The Metanet Blog
Part 2 — The Metanet Protocol
Welcome back to Edge Cases, the Metanet blog series.
In the first post of the series, we introduced the concepts of the Metanet and the Metanet protocol, which you can find here. Today we begin our odyssey into all things technical that form the Metanet protocol.
So, without further ado, let’s crack on.
Part 2 — The Metanet Protocol
In the last post I was careful to make the distinction between the Metanet as a concept and the Metanet protocol.
I did so because the Metanet — the grand vision for the creation of a global value network — will, over time, undoubtedly comprise a variety of aspects, standards, and techniques. Things are similar in principle here to how the current infrastructure underpinning the Internet consists of many interwoven protocols and architectures, such as HTTPS, FTP, and XML.
The Metanet protocol, on the other hand, can be treated as one such self-contained protocol, which has a particular function and role within the wider ecosystem of the Metanet. In the same vein that the Internet makes use of the protocols listed above to define standards for communications, file transfer, and interoperability for the Internet, the Metanet protocol can be used for a specific purpose for the Metanet.
So, just what is that purpose?
Metanet is data structure over Bitcoin.
— _unwriter, Medium
I’ll give you fair warning, it is not the first time I have quoted
in this series, and it will certainly not be the last. Their highly detailed post ‘The Metanet Starts’ is easily one of the most complete, articulate, and profound explanations of both the Metanet and the Metanet protocol to date, which is why you will find I am forced to refer to it throughout the series.The quote above is really the nutshell phrase that describes the purpose and function of the Metanet protocol. At the CoinGeek Toronto conference, I chose to express the same point using a similar (if less elegant) phrasing:
A protocol for structuring the on-chain Internet.
I’m sure the picture is now becoming clear that the primary goal of the Metanet protocol is to provide some kind of structure and organisation for Internet-like data that is mined into the blockchain. It is no secret that the Bitcoin SV blockchain has been a substrate for many impressive and enterprising applications, all of which utilise on-chain data, in recent months.
The Metanet protocol, then, is a tool that can allow the on-chain data used in these applications — and many more in the future — to be woven together. We thereby allow disparate on-chain data to be structured in ways that improve the functionality of the applications they are powering and help achieve the mission of allowing users to truly own their data on the Metanet.
The technical summary of the Metanet protocol is currently available on the Bitcoin SV website:
— nChain
I would highly recommend reading this technical summary at some point in time. It contains a distillation of the Metanet protocol into its fundamental concepts, which includes all the ingredients required to understand and build on-chain structures for the Metanet.
But, as I’ve said previously, the purpose of my blog is to explain these concepts in depth and subsequently augment these fundamental building blocks to explore further ideas.
Over the next four posts, we will be breaking down the concepts outlined in the document above, and establishing our base understanding of the Metanet protocol. We will see exactly how it works, and discuss some of the reasons underpinning the design choices made in its development.
The content of the document containing the technical summary will be broken up into the following sub-topics, each of which will be given a dedicated post for discussion:
- 2.1 — Node and edge structure
- 2.2 — Domains, naming & locating
- 2.3 — The Metanet & existing protocols
- 2.4 — Data insertion and transaction structure
Before diving into the details of the Metanet protocol itself, though, we will first use today’s post to preface our discussion with some essential background: a brief overview of directed acyclic graphs (DAGs).
Directed Acyclic Graphs (DAGs)
In order to discuss the Metanet protocol, we need to understand what is meant when we talk about directed acyclic graphs (DAGs).
Inevitably, we must dip our toes into graph theory here — a branch of mathematics whose origin is widely attributed to Leonhard Euler. The seminal paper on the ‘Seven Bridges of Königsberg’, from Euler, effectively birthed the scientific study of graph structures.
When we use the term graph, in the context of graph theory, we refer generally to any structure comprising nodes (also known as vertices) and edges. The terminology here may be unfamiliar, but all we really mean by ‘node’ is some object and by ‘edge’ we mean some connection between a pair of nodes.
So, to put it simply:
A graph is a structure of nodes connected by edges.
An interesting property of edges — the pair-wise connections between nodes — is that they may have a specific direction. A graph in which all edges are given a direction is known as a directed graph.
Given a pair of nodes in a directed graph, say node A and node B, the edge connecting them may be directed either from A → B or from B → A.
Depending on which direction is chosen between two such nodes, we will define a different relationship between them. What we mean is that, for a pair of nodes A and B connected by a directed edge, one node will be considered the ‘parent’ node and the other the ‘child’ node.
To see it more clearly, we have drawn the pair of nodes in the diagram below:
In our depiction, the nodes A and B are represented by two circles (i.e. generic ‘objects’), and the directed edge between them is represented by an arrow. In our case, the arrow goes from A → B, which means node A is the parent and node B is the child.
We will use such simple facts about directed graphs throughout today’s post, and indeed the remainder of the series. Now that we have a good understanding of directed graphs, we only need to introduce one final aspect: the acyclic property.
A directed graph is considered acyclic if there is no path along directed edges that starts and ends at the same node. For example, if we had a graph comprising three nodes A, B, and C, we would have a cycle if it were possible to follow a path A → B → C → A . An acyclic graph, therefore, is simply a directed graph in which no such cycle is possible.
Following our very brief crash-course in some of the absolute basics of graph theory, we are now at a point where we can define a directed acyclic graph (DAG).
A DAG is a structure which has the following properties:
- Directed — every edge between a pair of nodes is directed.
- Acyclic — contains no cycles.
- Graph — comprises nodes and edges.
So, why have I taken up so much of your valuable time just to talk about graph structures?
The answer here is simple: not only are DAGs prevalent in a wide variety of natural circumstances, they are also a staple of modern data structures and information systems — including Bitcoin.
We find DAGs occurring in real-world scenarios such as in family trees, for time-constrained scheduling systems and in contemporary version-control systems such as in the widely-used Git data-model. But things begin to get really interesting when we observe that the blockchain itself as a data structure also comprises DAGs.
Blockchain DAGs
The blockchain, as specified by the Bitcoin white paper, is a DAG. It is remarkable how often this observation is either misinterpreted or missed entirely as a property of the proof-of-work blockchain. It is not uncommon to find articles ‘comparing’ blockchains and DAGs as if they were alien concepts — which could not be further from the truth.
Not only can the blockchain, under the definition we have just established, be considered a valid example of a DAG, under the definition we have just established, but we can in fact find multiple distinct DAG structures within the blockchain, if we are willing to go looking for them with an open mind.
For the purpose of today’s discussion, I will focus on the two most obvious examples of DAG structures that exist as part of the Bitcoin blockchain:
- the Block DAG; and
- the Transaction DAG.
Let’s look at how both of these DAGs are formed.
The Block DAG
As I’m sure virtually all readers are aware, the blockchain, under its simplest possible description, is a chain of cryptographically linked blocks of data. The data in each block in-turn comprises a block header and a set of transactions, but when viewing them through the lens of graph theory, we will only consider the entire block of data as a discrete object – without breaking it up further into its components.
It is important, though, to understand the origin of the ‘cryptographic link’ between blocks that I alluded to a few lines ago. The key fact to know here is that:
Each block contains the cryptographic hash of the previous block header.
The statement is just a fancy way of saying that every new block has a reference to the previous block. The clever part is that the reference is in the form of a cryptographic hash of the header of the previous block, where a cryptographic hash is simply the output of a one-way cryptographic hash function.
The fact that the hash of the previous block is included in each new block is what allows us to consider the blockchain as a DAG:
In the diagram above, each block represents a node in a graph. These nodes are connected in pairs, one-by-one in sequence, by edges that are represented by the respective cryptographic hash of the previous block. For instance, node B1 is connected to node B2 by an edge B1 → B2 because B2 contains the cryptographic hash H(B1), where H( ) denotes the hash function.
Strictly speaking, we should be talking about the block header in particular here, but for all intents and purposes the term block suffices.
As an aside, the directionality of edges between blocks that I have shown above may, at first glance, seem in conflict with the notion of ‘orphan blocks.’
For those unfamiliar with the concept, orphan blocks are blocks which are mined, and perhaps temporarily valid, but not built upon, as a result of multiple miners finding valid proof-of-work solutions at similar times. The term ‘orphan block’ thereby implies it has no parent, but an orphan block is built on a previous block, referencing it via H(Tx_prev), which does mean that the orphan has a parent but no children.
Maybe it is more an issue with the term ‘orphan’ in general, but why do we call a block with a predecessor an ‘orphan?’ Surely the key feature is that the block has no successor?
In any case, I am going to stick with using the convention for edge direction that is shown in the diagram above — that is Bi → Bi+1 for successive blocks.
In my mind, it is more logical to do so as more recent blocks are the descendants (or children) of older blocks, which is in line with the conventions used in the original Bitcoin white paper.
Without labouring the technical details too much farther, we can see how the blockchain is a graph (i.e. comprises nodes and edges), is directed (i.e. each edge is directed from Bi → Bi+1), and is acyclic. The reason that the ‘Block DAG’ is acyclic lies in the collision-resistant property of cryptographic hash functions. Essentially, for a cycle to occur, we would have to violate this property by finding two distinct blocks that have the same hash of their respective block headers.
We can conclude, then, that the blocks in a blockchain satisfy all of the properties required to consider the blockchain a DAG. It is worth noting that, while it is indeed a DAG, the blockchain is restricted to being a simple linear structure.
Now, what about transactions?
The Transaction DAG
In each block of the blockchain, there is a set of transactions, which are collectively represented by a Merkle root included as part of the block header for the respective block. In other words, the transactions in a block are effectively also an input to the cryptographic hash used to create edges between blocks in the blockchain.
For the same reason, one could argue that the ‘Block DAG’ we have just described and the ‘Transaction DAG’ we are about to describe are linked themselves. But, if we just consider blocks as one distinct type of node, which form the Block DAG, then we may consider the transactions of a blockchain as another distinct type of node, which form the Transaction DAG.
We can understand the Transaction DAG using much of the same logic that we applied in determining that blocks form a DAG. The transaction graph we wish to describe here may look something like the following:
The blockchain operates under the UTXO model, where ‘UTXO’ simply means ‘unspent transaction output.’ Without going into too much detail here, the important thing to know is:
A transaction consumes (i.e. spends) UTXOs from previous transactions.
In effect, the statement means that every new transaction will contain a reference to a previous transaction. The reference is in fact a transaction ID (TxID), which is nothing more than the cryptographic hash of a previous transaction, which we can write as H(Tx_prev).
So, in the same way that blocks form a block DAG by referencing the previous block through a hash value, transactions form a transaction DAG by referencing previous transactions through hash values.
The key difference here is that we have used ‘block’ in the singular and ‘transactions’ in the plural; a block can only ever reference one previous block, since they are appended one by one to the blockchain, whereas a transaction can reference many previous transactions as the source of funds for many different transaction inputs.
As such, we see that the transaction DAG takes on a much more involved form than the more simplistic block DAG. Where the block DAG was a simple, linear sequence of connected nodes, the transaction DAG can sprawl out into a complex structure, with transactions referencing (and being referenced by) many, many other transactions. Here is a good place to introduce a final bit of terminology for directed graphs that we will need going forward, namely the in-degree and out-degree of a node:
- In-degree — the number of edges pointing into a node.
- Out-degree — the number of edges pointing out of a node.
Using these new terms, we can see that the Block DAG is very simple because the underlying blockchain protocol dictates that the blocks must always have an in-degree and out-degree of one. Conversely, the blockchain protocol allows a transaction to have an in-degree and out-degree that are free. We can see that here lies the reason that our transaction DAG looks so much more complex than our block DAG.
I have been liberal with the terms ‘one’ and ‘free’ here for simplicity. In the event that there is an ephemeral blockchain fork, the out-degree of the block on which the fork started will temporarily be >1, but for a deep, ‘steady-state’ block the in- and out-degree will always be 1. Similarly, the in- and out-degree of a transaction are limited (rather than ‘free’) in practice by the size constraints that may be imposed on a transaction, but the limit need not apply in principle.
The concept of how the in-degree and out-degree of a DAG affect the structures that can be represented by the corresponding graph is something we will re-visit when looking at the Metanet graph next time.
But don’t just take my word for it – you can verify these concepts for yourself and become lost in the rabbit hole of the transaction DAG by, for example, using the wonderful transaction graph visualiser from you-know-who.
The Metanet Graph
We have seen how one rule set — that of the blockchain protocol — allows us to describe two distinct DAGs: one for blocks, and another for transactions.
The Metanet protocol is simply another set of rules, which are applied on top of the blockchain protocol, that allow us to define another DAG: the Metanet graph.
In the next post, we will look at the details of the rule set described by the Metanet protocol, and how we can implement its rules to form a directed graph of on-chain data. But for today, I would like to briefly explain some of the motivations for such a protocol to structure on-chain data in the specified way.
Why use a DAG?
There are a number of inherent properties of directed graph structures which lend themselves ideally to the use cases for Internet-like data. We will go through more in some detail next time, but some of them can be listed here:
- Efficient;
- Searchable;
- Flexible; and
- Native.
The one point I would like to really emphasise today is the native property— that the use of a DAG as a data structure is directly compatible with the underlying data structures of the blockchain.
It may be more obvious now why I have spent the majority of today’s post building up the concepts of directed graphs, and explaining how they are fundamental to how the blockchain functions on multiple levels. By choosing to structure on-chain Internet-like data using a DAG, we are directly leveraging the existing infrastructure of the blockchain to achieve our goals.
In other words, when building the Metanet, we are able to do so in such a way that works in conjunction with the base use case of the blockchain as a peer-to-peer electronic cash system. We are using the useful properties of the base-layer blockchain to facilitate the goal of an on-chain value network in a way that both empowers the use of micropayments and allows true ownership of data that is being commoditised.
Co-existing Graphs
As a final thought for today’s post, I want to draw your attention to how the transaction DAG and the Metanet graph will intertwine and co-exist.
As we will see next time, the nodes that make up the Metanet graph are also transactions. So any nodes that are part of the Metanet graph will necessarily also be a part of the Transaction DAG we described earlier.
The diagram above should serve as a useful illustration of how the Metanet graph is able to co-exist concurrently with the Transaction DAG. The relationship between the graphs can be summarised as:
All Metanet nodes are transactions but not all transactions are Metanet nodes.
So, what are the rules of the Metanet graph, and how do we make it a reality?
Stay tuned for the next instalment in the series, where we’ll examine the details, and the advantageous properties, of the node & edge structure used to create the Metanet graph.
Resources
The following resources will be useful as supporting material for the blog series in general:
- Metanet Protocol (Technical Summary).
- _unwriter’s explanation of the Metanet.
- Metanet slides from CoinGeek Toronto (2019).
- The Genesis Metanet tree: graph, thread.
- The MetaWriter tool: github, thread.
- Metanet planaria.
For today’s post, I can recommend the following additional resources:
7. Explanation of DAGs in Git.
8. Transaction-graph visualiser: tool, docs.
9. The Bitcoin white paper.
Copyright
© 2019 nChain Limited. All rights reserved. This article is provided without any warranties whatsoever and shall not result in the grant of any license, whether implied or otherwise. nChain Limited shall not be liable in any way for the use of the information provided herein.
