Edge Cases: The Metanet Blog

Part 2.1 — Nodes & Edges

Welcome back to Edge Cases, the Metanet blog series.

In the last post, we introduced several concepts underpinning directed acyclic graphs (DAGs), and looked at how they are related to the Metanet protocol. If you’re just joining us, you can find the start of the series here. In today’s post, we are going to look at exactly how the Metanet protocol can be used to create on-chain DAG structures that can facilitate a peer-to-peer value network on Bitcoin SV.

Part 2.1 — Node and Edge Structure

In part 2 of the series, we met a little bit of graph theory, and I introduced some of its foundational concepts that allowed us to describe DAGs. As a brief recap, the salient points are:

• graphs — structures comprising nodes and edges;
• directionality — the direction of an edge in a directed graph;
• DAGs — structures that are graphs, have directed edges and are acyclic;
• in-degree — the number of edges pointing into a node; and
• out-degree — the number of edges pointing out of a node.

These simple facts allowed us to build up an understanding of directed acyclic graph structures in principle. From here, we were able to apply our basic comprehension of their related concepts to help us describe three graphs:

1. the Block DAG;
2. the Transaction DAG; and
3. the Metanet DAG.

We observed that, for a proof-of-work blockchain such as Bitcoin SV, the blocks indeed form a simple, linear DAG, which we named the ‘Block DAG.’ Similarly, we found that the transactions also form a DAG, albeit a much more complex one, which we termed the ‘Transaction DAG.’

Finally, we introduced the notion of the Metanet graph, which is also a directed acyclic graph. We have discussed how the Metanet protocol defines a set of rules that allow us to create the Metanet graph, analogously to how the underlying blockchain protocol defines the set of rules that allow us to create both the Block and the Transaction DAGs.

In today’s post, we will look in detail at how the Metanet protocol achieves on-chain graph structures, built natively and exclusively on the Bitcoin SV blockchain, before looking to formalise the rule set of the Metanet protocol, and explore the features and properties of the graph structures its rules facilitate.

We start, then, by looking at what exactly constitutes the nodes and edges of the Metanet graph.

Metanet Nodes

In accordance with the technical summary, a Metanet node is simply a transaction that follows the rule set of the Metanet protocol.

Nodes are transactions.

As we will learn, the rules governing what a Metanet node actually looks like are highly unrestrictive, which means that Metanet nodes can take many different shapes, sizes and forms. Indeed, any transaction which follows the very simple Metanet node format, as a skeletal outline, is considered a Metanet node. So, what is this format?

The most basic outline structure of a Metanet node requires a transaction to meet the following criteria:

• The transaction has at least one OP_RETURN output;
• The OP_RETURN payload includes: (i) the Metanet flag, (ii) a node address ‘P(node),’ and (iii) a parent transaction ID ‘TxID(parent).’
• The transaction contains an input signed by a parent node, denoted by ‘SigP(parent),’ if that node does indeed have a parent.

What may sound like a lot of requirements when written down is often much clearer when expressed diagrammatically in Bitcoin. The simplest outline structure of a Metanet node, which satisfies all of the criteria above, is shown in the diagram below:

A Metanet node transaction.

Note that we take ‘OP_RETURN’ to mean the combined opcodes ‘OP_FALSE OP_RETURN’ throughout the blog series.

We can see that the given example is a very simple transaction in reality. Taken at face value, it just looks like a fairly standard OP_RETURN transaction with three elements in its OP_RETURN data payload. The key difference between Metanet nodes and such transactions, which we are highly familiar with and seeing already in Bitcoin SV, is that the Metanet protocol imbues meaning to the components of such transactions.

What exactly do I mean here?

The transaction above, showing the skeleton for a Metanet node, can be viewed as comprising six elements:

• TxID(node);
• SigP(parent);
• P(parent);
• Metanet flag;
• P(node); and
• TxID(parent).

The first three of these elements, the TxID(node), SigP(parent), and P(parent), would be present as part of any typical transaction. Moreover, in a typical OP_RETURN output payload, we would expect at least one element, and so it is not unreasonable to say that the remaining three elements, the Metanet flag, P(node), and TxID(parent), may also be present in any typical OP_RETURN payload.

The core of the Metanet protocol is that we ascribe very specific meaning to each of these six elements, where, in the traditional case, only a few of them may have intrinsic meaning. These specific meanings applied by the Metanet protocol are:

• TxID(node) — the unique transaction ID of the node;
• SigP(parent) — a signature created by the parent of the node;
• P(parent) — the address defining the parent of the node;
• Metanet flag — a protocol prefix signalling a Metanet transaction;
• P(node) — the address defining the node; and
• TxID(parent) — the unique transaction ID of the parent of the node.

I want to reiterate once more here the crucial aspect is that we have ascribed meaning to all six of these basic elements of the node transaction. The Metanet protocol thereby stands in contrast to existing OP_RETURN protocols, which tend to ignore the utility of the input signature and only stipulate a specific meaning for elements in the OP_RETURN payload.

Herein lies a subtle point that demonstrates how the Metanet protocol has been designed to leverage all of the existing infrastructure of the underlying blockchain. The signature and public key* in the input of an OP_RETURN transaction do not typically have any greater meaning associated with them, whereas the Metanet protocol directly utilises them as an intrinsic part of the Metanet graph structure.

*At this point in the series, I want to establish clearly how the Metanet graph is formed, using transactions and signatures, at a high level. If you have questioned my usage of the term ‘address’ in this section to conflate addresses and their underlying public key counter parts, then you are right to. We will discuss the lower-level specifications for the Metanet protocol in later posts, but for now we will use the terms ‘address’ and ‘public key’ interchangeably.

So, now that we know that a Metanet node contains six important elements, can we simplify the scenario any further to express things more concisely?

The answer is yes — we can narrow it down to just four elements, which can be interpreted as follows:

• P(node) — the address of the node;
• TxID(node) — the version of a node;
• P(parent) — the address of the parent of the node; and
• TxID(parent) — the version of the parent of the node.

We have made simplifications by putting the Metanet flag to the back of our minds, as we know it will always be present and unchanging, and by treating P(parent) and SigP(parent) as one ‘element.’ It is appreciated that they are, of course, separate things, but the important aspect is that the key pair for P(parent) associated with the signature SigP(parent) belongs to the parent of the node. As such, it is cleaner to represent the two elements simply as P(parent), as doing so expresses the key point much more concisely.

As is clear from this simplified set of four elements, we are interpreting the address of a node with as public key specified by the node, and the version of a node as the hash of the transaction. We will explore both in more detail at a later point, but it is useful to keep the same interpretations in mind as we move forward.

With this simplification, we can now represent a Metanet node diagrammatically as:

Metanet nodes.

There are two options, as shown above, for possible Metanet node types:

• Root nodes: have no parent; and
• Nodes: have exactly one parent.

As such, ‘standard’ nodes, with exactly one parent, will have four important elements: P(node), TxID(node), P(parent), and TxID(parent), which collectively allow us to fully specify a standard node in the Metanet graph.

In the case of a root node, with no parent, we will naturally only have two important elements: P(node) and TxID(node), which allow us to fully specify a root node in the Metanet graph. In the diagram above, we have highlighted how a root node will simply have a valid signature from any public key in its input, and its parent transaction ID can be replaced with a null value.

Metanet Edges

We have described what nodes look like in our on-chain Metanet graph, but what about the edges?

Edges are created by signatures.

To put it simply, edges are created by signatures. That is, in order to create an edge from a parent node to a child node, the child node must be signed using the key pair associated with its parent — SigP(parent) must appear in the input of the child node.

This scenario is best illustrated by way of an example. Consider a node A, which is defined by the pair P(A), TxID(A), where P(A) is associated with a key pair that is controlled by Alice. We now wish to create a second node B, which is to be defined by the pair P(B), TxID(B), where P(B) is associated with a key pair controlled by Bob.

In order to create a parent → child edge from A → B, we need to ensure that node B includes a signature from from P(A) in its input. The following figure illustrates what creating such an edge looks like:

A Metanet edge from A → B.

The appearance of the signature SigP(A) in the input of node B is the reason the edge between the two nodes is created. The direction of the edge tells us that node A is the parent and node B is the child. We see also that, because of how we have defined Metanet nodes in the previous section, node B must also include TxID(A) as its ‘parent transaction ID’ in its OP_RETURN payload.

So, when we create an edge from parent to child, we must ensure that the child node (B) includes both a signature from the address of its parent and the transaction ID of its parent.

Using our simplified view of nodes from the last section, and noting that node A is a root node, the relationship can be seen as:

• node A being defined by P(A), TxID(A), P(any), and TxID(null); and
• node B being defined by P(B), TxID(B), P(A), and TxID(A).

The crucial aspect here is that the Metanet protocol leverages the input signatures and requires that they include signatures from the parent node to enforce permissioning structure on the Metanet graph. In other words, the ‘write access’ to write a new Metanet node to a tree requires creating a node edge, which in turn requires a signature.

In the example above, Alice (who controls P(A)) has the sole authority to create the child node B because only she can produce the required signature SigP(A) in its input. Consider, instead, what happens if Bob attempts to create node B himself:

An invalid Metanet edge A — / — B.

In this scenario, Bob can only provide an input signature for a key pair that he controls, such as for P(B). Simply by applying the rules of the Metanet protocol to this pair of transactions, we can determine that node A and node B do not have a valid edge between them.

This is how the Metanet protocol achieves a well-defined permissioning structure for on-chain data. The power to add to the graph is always defined by the parent node, which allows either a single thread of one user’s authority or, indeed, a chain of authority to be established on top of a user’s on-chain data.

Unique Node Identifiers

Now that we have established exactly what constitutes nodes and edges in the Metanet DAG, we can introduce another concept: the unique node identifier.

Each node has a unique identifier: ID(node).

As we have discussed, we can consider each node as comprising four essential elements: P(node), TxID(node), P(parent) and TxID(parent).

The first two of these elements, P(node) and TxID(node), specify the node itself, while the latter two elements, P(parent) and TxID(parent), specify the parent of the node (if it has one).

We can see, then, how assigning each node a unique node identifier ID(node) based on the two elements P(node) and TxID(node) will allow us to uniquely identify any node in the graph. The ID(node) itself is derived from these elements as the hash of their concatenation, as shown in the equations of the diagram below:

Unique node identifiers, ID_node and ID_parent.

It may become clearer now why we chose to distil our conception of Metanet nodes into four fundamental components; these four elements are enough to uniquely define both ID(node) and ID(parent) for any given Metanet node.

This brings us to one of the fundamental design elements of the Metanet protocol:

Each node specifies itself and its parent.

We can understand the statement now to mean that a node must contain enough information to determine both ID(node) and ID(parent).

It is worth mentioning the elephant in the room: the fact that TxID(node) also serves as unique identifier for any given Metanet node. One could propose, therefore, that the ID(node) would not be required as we could simply identify each and every Metanet node ever created using only their unique TxID(node) values.

But, this is where we return to our interpretation of TxID(node) as the version of a node. We have purposefully chosen to derive the unique node identifier ID(node) from both P(node) and TxID(node) because they have specific, yet separate meanings. When considered separately, their meanings can be used to achieve much greater functionality — compared to simply using TxID(node) as the node identifier.

So, by choosing ID(node) to be derived from both P(node) and TxID(node), we are able to ensure that we can describe the Metanet graph without losing any of the functionalities we gain from being able to compare nodes with different addresses and versions (more on such functionalities later).

Genealogy

We can use the ideas we have discussed already in today’s post and quickly gain an understanding of how the simple node and edge structure of the Metanet protocol allows us to build a virtually unbounded number of different on-chain graph structures.

It is worth emphasising here, then, that the simple permissioning structure we described above, for the simple two-node case, extends generally to any graph structure that we can create with the Metanet protocol. In other words, what the rules of the protocol allow us to do is describe a consistent on-chain genealogy — the ability to describe, trace, and extend the flow of permissions throughout the graph as a kind of on-chain lineage.

On-chain lineage of permissions.

Consider the circled blue node above. This node must reference and be signed by its parent. Similarly, the child of the blue node must reference and be signed by the blue node. The grand child of the blue node (not shown) would need to reference and be signed by the child of the blue node, which can continue on ad infinitum.

We can see, as shown in the diagram above, that the Metanet protocol allows the permission to extend any such Metanet graph to be inherited. The very same write access we described earlier is passed-on, from generation to generation, as the graph grows and extends.

Graphs and Trees

I have been consistent in using the term ‘graph’ to describe structures that can be created with the Metanet protocol. But, as the series continues, you may notice that I begin to use the term interchangeably with ‘tree.’ From here, I will try and stick to the following definitions:

• Metanet graph: the global collection of Metanet DAG structures.
• Metanet tree: a single instance of a Metanet DAG structure.

The reason for using both is that it may sometimes be easier to consider ‘the Metanet DAG’ as the larger, over-arching DAG structure that encompasses the entirety of on-chain content that utilises the Metanet protocol. It is for the same reason simpler to talk about each individual instance where the protocol is used (i.e. each individual structure) as a tree. As such, the Metanet graph becomes the global collection of trees, where each tree starts from its own root node and can have its own localised permissioning structure.

A single, localised Metanet tree — which is a part of the global Metanet graph.

The tree above is just one simple example of a DAG structure that can be created using the Metanet protocol. We will learn more about some of its features, such as domain structure and version control, in the coming posts.

Rules of the Metanet Protocol

To summarise what we have discussed so far, we can now distil the fundamental rule set of the Metanet protocol to the following:

1. Nodes are transactions;

2. Edges are created by signatures;

3. Each node is uniquely defined by the pair (P(node), TxID(node)); and

4. Each node must specify the node ID of itself and its parent.

These core rules are the absolute essential building blocks that allow us to construct well-defined, on-chain graph structures. Everything that can be achieved with the Metanet protocol is built on these four tenets.

In the technical summary, we also introduce some additional rules to ensure Metanet trees can be mapped easily onto other hierarchical structures, such as file systems, website domains, and organisational chains of command:

5. The in-degree of a node should be 0 (no parent) or 1 (one parent);

6. The out-degree of a node should be free.

So, to summarise, the rule set of the Metanet protocol as outlined in the technical summary document is as follows:

Throughout the majority of the Metanet blog series, the above set of rules is what we will use as our base understanding of the Metanet to explore what exactly can be achieved using on-chain graph structures. Later in the series, we will also explore what is possible when rules 5. and 6. are relaxed, and we really only confine ourselves to rules 1. — 4. as outlined above.

Properties of the Metanet Graph

Today’s post has probably gone on for too long already, but it would be remiss of me not to highlight some of the core properties of the Metanet DAG now that we have described its construction.

Generality

The concept of generality is an easy one to explain. The Metanet protocol, using the basic four rules we have just outlined, is highly generic. In other words, the protocol does not restrict a developer from building any specific type of structure.

Metanet is a very specific protocol that is also very generic at the same time, so generic that it becomes philosophical.

— _unwriter, Medium

The protocol is designed to accommodate not only all the existing use cases that we can currently conceive of for structured on-chain data, but also any future applications that we have not yet foreseen. The design should allow the Metanet protocol to be as future-proof and robust as possible, which is clearly a requirement if it is to be used as one of the protocols that underpin the over-arching ambition of the Metanet.

Permissioning

We have already discussed the native permissioning structure that is baked in to the Metanet protocol. If we now consider some real-world use cases for its structure, our motivation for using an acyclic graph will become clearer.

A typical example of a hierarchy of authority would be a company or business, where the CEO sits atop the chain of command, while at the bottom would lie a standard employee — or even an intern. If we wish to map such a hierarchy to a Metanet tree, we may get something like the following:

Company hierarchy as a Metanet tree.

We see here that the permission to add to the graph flows in the logical direction, delegating ‘write access’ from person to person down the chain, and establishing a clear flow of permissions for the graph. The crucial thing to note here is that, because we have defined the graph such that it must always be acyclic, there is no way that the chain of command can be undermined.

For instance, consider the red line in the diagram above, which represents the hypothetical unwanted scenario where there is a cycle in the graph. In which case, the intern would suddenly be given authority to overwrite the node representing the CEO. Any cycle or loop in a permissioning hierarchy such as this would clearly have dire consequences, and the same goes for any other situation where we require a permissioning hierarchy of some sort.

The fact that the Metanet protocol is designed to create a DAG ensures that no such cycle of permissions is possible.

Efficiency

I acknowledge that it is difficult to talk in absolutes here, as there are multiple factors that need to be considered in a complete analysis. But, I’m sure it is no great leap to say that the Metanet protocol is a highly efficient protocol for storing data.

Bitcoin is the most efficient data storage protocol, and Metanet is the most efficient data structure protocol which sits on top of it.

— _unwriter, Medium

We have essentially managed to create an on-chain data-storage and data-structuring protocol, which distils everything into four core elements in each transaction: P(node), TxID(node), P(parent), and TxID(parent), clearly presenting a minimalist approach to the problem that requires very little overhead to implement.

Despite using so few elements to define the Metanet DAG, we have not sacrificed any of the important functionalities, like version control and domain structure, that we aimed to preserve for such on-chain structures.

For a more in-depth look at the efficiency of the Metanet protocol, I would again direct you towards

_unwriter

’s discussion here, with particular regards to how it relates to the scalability of the UTXO model that is native to Bitcoin SV.

The Metanet Starts

Version Control

As a final point, I would like to once again point to the fact that using the Metanet protocol to structure data, in conjunction with a public, proof-of-work blockchain, allows for a powerful, immutable versioning system that is yet again native to the underlying blockchain.

Proof of work versioning.

We won’t describe the details of how version control, within the Metanet protocol, works just yet, as I feel it deserves its own separate discussion to do it justice. The important point to make, for now at least, is that herein lies one of the key advantages that the Metanet protocol can leverage on the Bitcoin SV blockchain provides.

Stay tuned for the next instalment, where we’ll look at the rich domain structure that emerges from the Metanet graph and see how we can interact with it.

Resources

The following resources will be useful as supporting material for this series in general:

1. Metanet Protocol (Technical Summary).
2. _unwriter’s explanation of the Metanet.
3. Metanet slides from CoinGeek Toronto (2019).
4. The Genesis Metanet tree: graph, thread.
5. The MetaWriter tool: github, thread.
6. Metanet planaria.

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.