Blocktree/doc/Paper/Paper.tex

\documentclass{article}
\usepackage{amsfonts,amssymb,amsmath}
\usepackage[scale=0.75]{geometry}
\usepackage{hyperref}

\title{Blocktree \\
\large A platform for distributed computing.}
\author{Matthew Carr}
\date{May 28, 2022}
\begin{document}
\maketitle
\begin{abstract}
Blocktree is a platform which aims to make developing reliable distributed systems easy and safe. 
It does this by defining a format for data stored in the system, a mechanism for replicating
that data, and a programming interface for accessing it. It aims to solve the difficult problems
of cryptographic key management, consensus, and global addressing so that user code can focus on
solving problems germane to their application.
\end{abstract}

\section{Introduction}
(Do I need this?)

\section{An Individual Blocktree}
The atomic unit of data storage and privacy and authenticity guarantees is called a block. A
block contains a payload of data. Confidentiality of this data is achieved by encrypting it using 
a symmetric cipher using a random key. This random key is known as the block key.
The block key is encapsualated using
a public key cipher and the resulting cipher text is stored in the header of the block. Thus
only the person possessing the corresponding private key will be able to access the contents of
the block. Blocks are arranged into trees, and the parent of the block also has a block key.
The child's block key is always encapsulated using the parent's key and stored in the block
header. This ensures that if a principal is given access to a block, they automatically have
access to every child of that block. The encapsulated block key is known as a read capability,
or readcap, as it grants the holder the ability to the block.

Authenticity guarantees are provided using a digital signature scheme. In order to change the
contents of a block a data structure called a write capability, or writecap, is needed. A
writecap is approximately an x509 certificate chain. A writecap contains the following data:
\begin{itemize}
\item The path the writecap can be used under.
\item The principal that the writecap was issued to.
\item The timestamp when the writecap expires.
\item The public key of the principal who issued the writecap.
\item A digital signature produced by the private key corresponding to the above public key.
\item Optionally, the next writecap in the chain.
\end{itemize}
The last item is only excluded in the case of a self-signed writecap, i.e. one that was signed by
the same principal it was issued to. A writecap is considered valid for use on a block if all
of the following conditions are true:
\begin{itemize}
\item The signature on every writecap in the chain is valid.
\item The signing principal matches the principal the next writecap was issued to for every
write cap in the chain.
\item The path of the block is contained in the path of every writecap in the chain.
\item The current timestamp is strictly less than the expiration of all the writecaps in the
chain.
\item The principal corresponding to public key used to sign the last writecap in the chain,
is the owner of the blocktree.
\end{itemize}
The intiution behind these rules is that a writecap is only valid if there is a chain of trust
that leads back to the owner of the block tree. The owner may delegate their trust to any number
of intermediaries by issuing them writecaps. These writecaps are scoped based on the path
specified when they are issued. These intermediaries can then delegate this trust as well.
A block is considered valid if it contains a valid writecap, it was signed using the key
corresponding to the first writecap's public key, and this signature is valid.

Blocks are used for more than just orgnaizing data, they also organize computation. A program
participating in the blocktree network is referred to as a node. Multiple nodes may be run on
a single computer. Every node is attached to the blocktree at a specific path. This information
is recorded in the block where the node is attached. A node is responsible for the storage of
the block where it is attached and the blocks that are descended from this block, unless there
is another node attached to a descendent block.
In this way data storage can be delegated, allowing
the system to scale. When more than one node is attached to the same block they form a cluster.
Each node in the cluster contains a copy of the data that the cluster is reponsible for. They
maintain consistency of this data by running the Raft consensus protocol.

\section{Connecting Blocktrees}
In order to allow nodes to access blocks in other blocktrees, a global ledger of events is used.
This ledger is implemented using a proof of work (PoW) blockchain and a corresponding 
cryptocurrency known as blockcoin. Nodes mine chain blocks (not to be confused with the tree 
blocks we've been discussing up till now) in the same way they do in other PoW blockchain
systems such as BitCoin. The node which manages to mine the next chain block receives a reward,
which is the sum of the fees for each event in the chain and a variable amount of newly minted
blockcoin. The amount of new blockcoin created by a chain block is directly proportional to the
amount of data storage events contained in the chain block. Thus the total amount of blockcoin
in circulation has a direct relationship to the amount of data stored in the system, reflecting
the fact that blockcoin exists to provide and accounting mechanism for data stored in the system.

When a node writes data to a tree block, and it wishes this block to be globally accessible, then
it produces what are called fragments. Fragments are the output symbols from an Erasure Coding
algorithm (such as the RaptorQ code). These algorithms are a class of fountain codes which have
the property that only $m$ out of $n$ (where $m < n$) symbols are needed to reconstruct the
original data. Such a code ensures that even if some of the fragments are lost, as long as $m$
remain, the original data can be recovered.

Once these fragments have been computed an event is created for each one and published to the
blockchain. This event indicates to other nodes that this node wishes to store a fragment and
states the amount of blockcoin the node will pay to the first node that accepts the offer. When
another nodes wishes to accept the offer, it directly contacts the first node, who then sends 
it the fragment an publishes and event stating that the fragment is stored with the second 
node. This event includes the path of the block the fragment was computed from, the fragment's 
ID (the sequence number from the erasure code), and the principal of the node which stored it.
Thus any other node in the network can use the information contained in these events to
determine the set of nodes which contain the fragments of any given path.

In order for nodes to be able to conntact other nodes, a mechanism is required for associating
an internet protocol (IP) address with a principal. This is done by having nodes publish events
to the blockchain when their IP address changes. This event includes their new IP address,
their public key, and a digital signature computed using their private key. Other nodes can
then verify this signature to ensure that an attacker cannot bind the wrong
IP address to a principal in order to receive messages it was not meant to have.

While this event ledger is useful for appending new events, and ensuring that previous events
cannot be changed, another data structure is required to ensure that queries on this data can
be performed efficiently. In particular, it's important to be able to quickly perform the
following queries:
\begin{itemize}
\item Find the set of nodes storing the fragments for a given path.
\item Find the IP address of a node or owner given a principal.
\item Find the public key associated with a principal.
\end{itemize}
These are enabled by creating a read model from the data in the event ledger. One possible
implementation of this read  model is the following SQL database.
This database contains two tables:
\begin{itemize}
\item \emph{Fragments}: one column containing path, one for the fragment ID, and another for the principal. Indexed on the path column.
\item \emph{Principals}: one column containing principal, one column for the public key, and
	one column for the IP address, one columns for the amount blockcoin the principal has.
	Indexed on the principal column.
\end{itemize}
This index is built from the event ledger by iterating over it, and modifying the database
appropriately for each event. For instance when a fragment stored event is encountered then
a row is added to the \emph{Fragments} table containing the path of the block, the fragment ID,
and the principal which were recorded in the event. The reader who is experienced with software
patterns will recognize that this is an event sourced architecture.

\section{Programming Interface}

\end{document}