123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582 |
- \documentclass{article}
- \usepackage{amsfonts,amssymb,amsmath}
- \usepackage[scale=0.75]{geometry}
- \usepackage{hyperref}
- \usepackage{biblatex}
- \bibliography{../citations.bib}
- \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}
- The online services that users currently have access to are incredible. They handle all
- the details of backing up user data and implementing access controls to facilitate
- safe sharing. However, because these are closed systems, users are forced to trust that
- the operators are benevolent, and they lack any real way of ensuring that the access
- controls they prescribe will actually be enforced. There have been several systems proposed
- as alternatives to the conventional model \cite{blockstack, filecoin}, but these systems
- suffer from their own shortcomings which Blocktree aims to address.
- The idea behind blocktree is to organize a user's computing devices and data into a single
- tree, called a blocktree. The user is said to own the blocktree, and they wield sovereign authority
- over it.
- The artifacts granting them this authority are their private keys, one for use in an encryption
- scheme and the other in a signing scheme.
- Measures for managing these keys and delegating their authority are important design considerations
- of the system.
- The owners of blocktrees are encouraged to collaborate with each other to replicate data by
- means of a cryptocurrency known as blockcoin.
- The blockchain implementing this cryptocurrency is the source of global state for the system,
- and allows for the creation of a name resolution mechanism.
- A blocktree consists of four different types of blocks: files, directories, servers and processes.
- Each block has a path corresponding to its location in the tree.
- A server is responsible for storing the files and directories that are children of the directory
- it's contained in.
- When multiple servers are contained in the same directory, they form a cluster, and run
- the Raft consensus protocol \cite{raft} to ensure consistency of the data they store.
- A process is either the child of a server, or the child of the process which started it.
- Processes operate under the actor model and exchange messages that are addressed using paths.
- System calls are implemented using this same messaging facility.
- The first component of a fully qualified path is the fingerprint of the blocktree owner's public
- signing key, allowing a block to be globally specified.
- The contents of directories are managed by the system,
- and they may contain links to files, other directories and servers.
- In addition to its payload of data, each file and directory has system managed metadata.
- These metadata are used to implement cryptographic access control mechanism which ensure
- that only authorized users can read and optionally write to the block.
- Access control for a given security principal is set using a hash of the principal's public signing
- key.
- This paper is intended to be a short introduction to the ideas of blocktree. A book is planned which
- will specify the system in greater detail. In keeping with the agile software methodology, this
- book is being written concurrently with an open source implementation of the system.
- The remainder of this paper is organized as follows:
- \begin{enumerate}
- \item A description of the operations of a single blocktree.
- \item The definition of a blockchain which provides global state and links individual blocktrees
- together.
- \item The programming interface for interacting with blocktrees and sending messages.
- \item An exploration of applications that could be written using this platform.
- \item Conclusion.
- \end{enumerate}
- \section{An Individual Blocktree}
- Files and directories are collectively known as data blocks. Data blocks have three components:
- \begin{enumerate}
- \item Their body, which is a sequence of bytes. This is managed by user code in the case of files
- and by the system in the case of directories.
- \item Their metadata, which is managed by the system.
- \item The log of events which have been committed, or are in the process of being committed.
- This is managed by the system.
- \end{enumerate}
- The body of a data block and its metadata are both covered by integrity protection.
- The log is not directory covered, but the events in it are.
- The body of the block may be optionally encrypted to provide it with confidentiality protection.
- Confidentiality of the body is achieved by encrypting it using a symmetric cipher using a random
- key.
- This random key is known as the block key.
- When a principal is to be given access to a data block, it's public encryption key is used to
- encrypt the block key.
- The resulting ciphertext is referred to as a read capability, or readcap, for short.
- It is stored in the metadata of the block in a dictionary under the key which is computed by hashing
- the principal's public signing key.
- We say that the principal has been \emph{issued} a readcap for the block.
- When the principal issued the readcap wishes to read the block it looks for a hash of its public
- signing key in the block's metadata, and if it find a value, uses it's private encryption key
- to decrypt the block key.
- If a block is not the root, then its parent's block key is used to encrypt its block key and the
- result is stored in the block's metadata.
- This enables anyone with a readcap for a block to read all blocks which are descended from it.
- This also enables the contents of any block to be decrypted using only a single private key
- decryption operation.
- The root always contains a readcap for the owner, ensuring they can grant a readcap to any block
- in their blocktree.
- Integrity protection is provided using a digital signature scheme. In order to change the
- contents of a block a data structure called a write capability, or writecap
- \footnote{The names readcap and writecap were taken from the Tahoe Least-Authority Filesystem
- \cite{tahoe}. The access control mechanism described in the Tahoe system heavily influenced the
- design of Blocktree.},
- is used.
- A writecap is a certificate chain and it 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 public key above.
- \item Optionally, the next certificate 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 in a block if all
- of the following conditions are met:
- \begin{itemize}
- \item The signature on every certificate in the chain is valid.
- \item The signing principal matches the principal the next certificate was issued to for every
- certificate in the chain.
- \item The path in every certificate is contained in the path of the next certificate for each
- certificate.
- \item The path of the block is contained in the path of every certificate in the chain.
- \item The current timestamp is strictly less than the expiration of all the certificates.
- \item The principal corresponding to the public key used to sign the last certificate,
- is the owner of the blocktree.
- \end{itemize}
- The intuition 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 blocktree. 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 certificate's public key, and this signature is valid. Note that because
- the first component of the path is the fingerprint
- \footnote{By \emph{fingerprint} I mean the base64url encoding of a hash of the owner's public
- signing key.}
- of the owners public signing key, anyone who receives a block and knowns the block's path can verify
- that the block has not been altered.
- Blocks are used for more than just organizing data, they also organize computation. A program
- participating in a blocktree is referred to as a server. Multiple servers may be run on
- a single computer. Every server is contained in a directory in the blocktree.
- A server is responsible for the storage of
- the directory where it is attached and all of the blocks that are recursively contained within it.
- If there is a child server attached to a subdirectory contained in the directory the server is
- responsible for, then the child server is responsible for the subdirectory.
- In this way data storage can be delegated, allowing the system to scale. When more than one
- server is attached to the same directory they form a cluster.
- Each server in the cluster contains a copy of the data that the cluster is responsible for. They
- maintain consistency of this data by running the Raft \cite{raft} consensus protocol.
- When a new blocktree is created a server generates a key pair to serve as the root keys.
- It is imperative for the security of the system that the root private key is protected, and it
- is highly recommended that it be stored in a Trusted Platform Module (TPM) \cite{tpm} and that
- the TPM
- be configured to disallow unauthenticated use of this key. The server then generates its own key pair
- and uses the root private key to issue itself a writecap for the root of the tree. Once it has
- this writecap, it creates the root block and generates a block key for it. A readcap is added to
- this block for the root public key and the server's public key. Additional
- cryptographic operations are performed using the server's key pair, and only when a new writecap
- needs to be created for an addition root server is the root private key used.
- When a new server comes online and wishes to join the blocktree, it generates its own key pair.
- The public key of this
- server then needs to be transmitted to another server that's already part of the user's blocktree. The
- mechanism used will depend on the nature of the device on which the new server is running.
- For example, a phone could scan a QR code which contains
- the IP address of the user's root server, and then transmit its public key to that internet host.
- In order for the new server to be added to the user's blocktree, it needs to be issued a writecap
- and a readcap must be added to the directory where it will be attached.
- This could be accomplished
- by providing a user interface on the server which received the public key from the new server.
- This interface would show the requests that have been received from servers attempting
- to join the blocktree. The user can then choose to approve or deny the request, and can specify
- the path where the new server will attach. If the user chooses to approve the request, then the writecap
- is signed using the server's key and transmitted to then new server.
- The ability to cope with key compromise is an important design consideration in any real-world
- cryptosystem. In blocktree the compromise of a server key is handled by re-keying every block under
- the directory where the server was attached. Specifically, this means that a new block key is generated for
- each block, and the readcap for the compromised server is removed. This ensures that new writes to
- these blocks will not be visible to the holder of the compromised key. To ensure that writes
- will not be allowed, the root directory contains a revocation list containing the public keys
- which have been revoked by the tree. These only need to be maintained until their writecaps
- expire, after which time the list can be cleaned. Note that if the root private key is compromised or lost,
- then the blocktree must be abandoned, there is no recovery. This is real security, the artifact
- which grants control over the blocktree is the root private key which is why storing the root
- private key in multiple secure cryptographic co-processors is so important.
- servers in a blocktree communicate with one another by sending blocktree messages. These messages
- are used for implementing consensus and distributed locking,
- as well as notifying parent servers when a
- child has written new data. The later mechanism allows the parent to replicate the data stored in
- a child for redundancy. User code is also able to initiate the sending of messages. Messages are
- addressed using blocktree paths. When a server receives a message that is not addressed to it,
- but is addressed to its blocktree, it forwards it to the closest server to the recipient that it
- is connected to. In order to enable efficient low-latency message transfers, servers maintain open
- TCP connections to the other servers in their cluster, and the cluster leader maintains a connection to
- its parent. Diffie-Hellman key exchange is used to exchange a key for use in an AEAD cipher, and
- once this cipher context is established, the two servers mutually authenticate each other using their
- respective key pairs. When a server comes online, it uses the global blocktree (described later)
- to find the other servers in its cluster. If it is not part of a cluster, or this information is
- not stored in the global blocktree, then it instead looks up the
- IP address of a root server and connects to it. The root server may direct the server to connect to
- one of root's children, and this process repeats until the new server is connected to its parent.
- A concept that has proven to be very useful in the world of filesystems is the symbolic link.
- This is a short file that contains the path to another file, and is interpreted by most programs
- as being a "link" to that file. Blocktree supports a similar system, where a block can be
- marked as a symbolic link and a blocktree path placed in its body. This also provides us with
- a convenient way of storing readcaps for data that a server would otherwise not have access to.
- For instance a symbolic link could be created which points to a block in another user's blocktree.
- The other user only knows the public key of the owner of our blocktree, so they issue
- a readcap to it. But the root servers can open this readcap and extract
- the block key. This key can then be encapsulated using the public key of the server which
- requires access, and placed in the symbolic link. When the server needs to read the data
- in the block, it opens the readcap in the symbolic link, follows the link to the block (how
- that actually happens will be discussed below) and decrypts its contents.
- While the consistency of individual blocks can be maintained using Raft, a distributed locking
- mechanism is employed to enable transactions which span multiple blocks. This is
- accomplished by exploiting the hierarchical arrangement of servers in the tree. In order to describe
- this, its first helpful to define a new term. The \emph{servertree} of a blocktree is tree obtained
- from the blocktree by collapsing all the blocks that a server (or cluster of servers) is responsible
- for into a single logical block representing the server itself. Thus we can talk about a server having
- a parent, and by this we mean its parent in the servertree. In terms of the blocktree, the parent
- of a server is the first server encountered when the path back to the root is traversed.
- Now, distributed locking works as follows:
- \begin{itemize}
- \item A server sends a request to lock a block to the current consensus leader in its cluster.
- If the server is not part of a cluster, then it is the leader. This request contains a timestamp
- for when the lock expires.
- \item If the leader is responsible for the block then it moves on to the next step. Otherwise
- it contacts its parent and forwards the lock request and this step is repeated for the parent.
- \item The responsible server checks to see if there is already a lock for this block. If there is
- then the request fails. Otherwise the request succeeds and a lock is placed on the block. A
- message indicating the result is then passed back up the tree ending at the original server. This
- message includes the principal of the server enforcing the lock.
- \item Once the locking server is done making its updates it sends a message directly to the server
- enforcing the lock, causing it to be removed.
- \end{itemize}
- Locking a block locks the subtree rooted at that block. Thus no writes to any path contained in
- the path of the locked block will be allowed, unless they come from locking server. If the locking
- server does not send the message
- unlocking the block before the lock expires, then the modifications which had been performed by
- it are dropped and the block reverts to its prior state. Since the locking server is the leader
- of the consensus cluster that is responsible for the block, this guarantees that
- writes from other servers will not be accepted.
- \section{Connecting Blocktrees}
- In order to allow servers 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. Servers 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 \cite{bitcoin}. The server 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 an accounting mechanism for data.
- When a server writes data to a tree block, and it wishes this block to be globally accessible or
- replicated for redundancy,
- it produces what are called fragments. Fragments are the output symbols of the RaptorQ code
- \cite{raptorq}. This algorithm is an example of an Erasure Code, which is 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 servers that this server wishes to store a fragment and
- states the amount of blockcoin it will pay for each of the fragment's maintenance payments. When
- another servers wishes to accept the offer, it directly contacts the first server, which then sends
- it the fragment and publishes an event stating that the fragment is stored with the second
- server. 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 server which stored it.
- Thus any other server in the network can use the information contained in this event to
- determine the set of servers which contain the fragments of any given path.
- In order for the server which stored a fragment to receive its next payment, it has to pass
- a time-bound challenge-response protocol initiated by the server that owns the fragment.
- The owning server select a leaf in the Merkle tree of the fragment and sends the index of
- this leaf to the storing server. The storing server then walks the path from this leaf back to
- the root of the Merkle tree, and updates a hash value using the data in each node it traverses.
- It sends this result back to the owning server which verifies that this value matches its
- own computation. If it does, then the owning server signs a message indicating that the challenge
- passed and that the storing server should be paid. The storing server receives this message and uses
- it to construct an event, which it signs and publishes to the blocktree. This event causes
- the blockcoin amount specified to be transferred from the owning server's to the storing
- server's account.
- The fact that payments occur over time provides a simple incentive for servers to be honest and
- store the data they agree to. In banking terms, the storing server views the fragment as an
- asset, it is a loan of its disk space which provides a series of payments over time.
- On the other hand the owning server views the fragment as a liability, it requires payments to
- be made over time. In order for a blocktree owner to remain solvent, it must balance its
- liabilities with its assets, incentivizing it to store data for others so that its own data
- will be stored.
- In order for servers to be able to contact other servers, a mechanism is required for associating
- an internet protocol (IP) address with a principal. This is done by having servers 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 servers can
- then verify this signature to ensure that an attacker cannot bind the wrong
- IP address to a principal in order to receive messages meant for it.
- While this event ledger is useful for appending new
- events, and ensuring previous events
- cannot be changed, another data structure is required to enable efficient queries.
- In particular, it's important to be able to quickly perform the
- following queries:
- \begin{itemize}
- \item Find the set of servers storing the fragments for a given path.
- \item Find the IP address of a server or owner given a principal.
- \item Find the public key associated with a principal.
- \end{itemize}
- To enable these queries a special blocktree is maintained by each server in the network: the global
- blocktree. This tree does not support the usual writing and locking semantics of local blocktrees.
- In functional programming terms, it can be thought of as a left fold over all of the events in the
- blockchain starting from the empty state.
- The above queries are facilitated by the following blocks:
- \begin{itemize}
- \item \emph{/global/fragments}: this block contains a hashtable where the key is a path and the
- value is the list of servers storing the fragments for the block at that path.
- \item \emph{/global/principals}: contains a hashtable where the key is the a principal and the value
- is the tuple containing the public key of that principal, its current IP address, and its current
- blockcoin balance.
- \end{itemize}
- To compute the entries in these tree blocks, the servers in the network iterate over all the chain blocks, updating
- their local copy of each tree block appropriately. The reader may recognize this as an event
- sourced architecture. Currently only these two tree blocks are known to be needed, but if new events are
- added to the system it can be easily extended to enable queries that have yet to be envisioned.
- \section{Programming Environment}
- Enabling an excellent developer experience is one of the primary goals of this system (the others being security
- and performance). servers execute user code that has been compiled into WebAssembly modules \cite{wasm}. Such code
- running on a blocktree server is referred to as a process. A process
- executes in a sandbox that isolates it from other processes, as well as the security critical operations of the server
- itself. The sandbox provides the code with an extension of the WebAssembly System Interface (WASI),
- with extra functions to send and receive blocktree messages.
- The standard POSIX filesystem APIs are used to interact with the contents of blocktrees.
- For instance, a file descriptor for a block can be obtained by calling path\_open.
- Additional non-POSIX functionality is implemented by adding
- messages which are handled by the server. This functionality includes the following:
- \begin{itemize}
- \item Distributed Locking
- \item Messaging
- \item Supervision Trees
- \item Protocol Contracts (Session Types)
- \end{itemize}
- This additional functionality is described later in this section.
- % Package Publishing
- These modules are distributed in packages stored in a blocktree. A package contains one or more
- Wasm modules and a TOML manifest file which describes the package.
- This manifest defines the package's user-friendly name as well as the list
- of permissions it requires.
- This list of permissions is used to determine which APIs the package has access to.
- These artifacts are then
- placed in a zip file and stored in a blocktree file. This ensures the integrity of the code in the
- package, as all blocks in a blocktree are integrity protected.
- When a package is installed it's given a directory under which it can store data that is shared between all servers
- in a blocktree. The path of this block is formed by prefixing the path the package was published at
- with the string ``/apps". When a package is runs on a server, it is confined to a block contained
- in the server's directory. It is only allowed read and write blocks in this block, but to allow it to
- access shared data, a symbolic link is created to the package's shared directory in ``/apps".
- % Privacy Safe vs Unsafe
- Packages are broken into two categories: those that are privacy safe and those that are not.
- A package is privacy unsafe if it requests any permissions which allow it to send data
- outside of the blocktree it's part of. Thus requesting the ability to
- open a TCP socket would cause a package to be privacy unsafe. Similarly, the creation of a protocol
- handler for HTTP would also be privacy unsafe. Privacy unsafe packages can limit the scope of their
- unsafety by
- imposing limits on the unsafe APIs that they request. For instance a package which needs to send
- blocktree message back to the blocktree it was published in can request the messaging permission
- for a path in that tree. Similarly, a package which only wants to open a TCP socket listening on the
- local network, can limit the scope of its requested permission.
- % Protocol Contracts
- In order to make it easy to write packages which interface with existing systems, most notably
- those using HTTP, packages are able to define protocols using a contract language and then register
- call backs for these protocols. This works by providing a system call which the package can
- supply a protocol contract to. This contract is then compiled into a state machine by the server
- and a handle is returned to the package. This handle is then used to register callbacks for different
- parts of the protocol. This ensures that the protocol is handled by the server itself and that
- protocols can be shared between many different packages as a library. For instance, the HTTP protocol
- would be compiled to a particularly simply state machine, with only one state: the listening state.
- This state would expose a hook that where a callback can be registered to handle a request.
- This state also defines the record format used to pass the request information to the callback
- and the record format of the return value that is expected in order to produce the response.
- More complicated (stateful) protocols would have more states, each defining their own request and
- response records, as well as hooks. One nice thing about this setup is that it will enable
- optimizations where the state machine and the user callbacks can be compiled into a program
- which can be safely run in the server itself, or even in a SmartNIC. This would require that
- the callbacks only use an approved set of APIs, but could enable much higher performance.
- % Supervision Trees
- Processes can arrange themselves into supervision trees, in the same way that Erlang
- processes are arranged \cite{armstrong}. In this scheme, when a child package crashes, or the server its
- running on dies (which is detected by other servers), then the process receives a message.
- In the
- simplest case this can be used to implement a logging system, where crashes and server
- deaths are recorded. More interestingly, this can be used to integrate with a control
- plane. For instance, if a blocktree were running in AWS, when a message is received indicating
- that a server has died, a new EC2 instance could be started to replace it. The reliability of Erlang
- and other system employing the Actor Model have shown the robustness of this approach.
- Processes can form this relationship after they've started running, provided that both of the processes
- have permission to send messages to each other. Processes, with the appropriate permissions, can also
- spawn other processes on descendent servers. This can be used to implement map-reduce workloads, where
- a process spawns mapping jobs on descendent servers containing the data of interest, and it processes
- their messages to compute the final reduction. Due to the tiny size of most programs, this is a much
- more efficient approach than moving the data.
- \section{Potential Applications}
- In order to explore how blocktree can be used, the design of several hypothetical systems
- is discussed. It's important to note that blocktree does not try to force all computation
- to be local to a user's device, but it tries to enable this for applications where it
- is possible.
- \subsection{Contacts and Mail}
- The first application we'll consider is one which manages a user's contacts. This would expose
- the usual create, read, update and delete operations, allowing a user to input the name
- of a person they know and associate
- that name with their public key. Once the principal of a person is known, then their public
- key can be looked up in the global blocktree. This principal needs to be communicated to the
- user via some out-of-band method. They could receive it in an email, a text message, or embedded
- in a QR code. Of course this out-of-band communication needs to be authenticated, otherwise
- it would be easy to fool the user into associating an attacker's key for the person.
- The user now has a way of associating a blocktree with the name of this person. However, the
- root public key of this blocktree is not enough to establish secure communications, because
- the root private key is not available to every server in the person's blocktree. In particular
- it would be inadvisable for the root private key to be stored on a user's mobile device. To
- address this mailbox directories are created.
- For each contact two directories are created: the inbox and the outbox. The user creates a readcap
- for another user's root key and adds it to their outbox. The inbox for the other user is a symbolic
- link to the user's outbox in the blocktree of the other user. Thus each user
- can write messages into their own blocktree at a location where the other party knows how
- to find them. But, in order for a server to read these messages it requires a its own readcap.
- Only the root
- servers can issue this readcap as only they have access to the root key. Once permission has been
- granted to a server, a root server can use the root key to decrypt the readcap issued to it, and then
- encrypt it using the public key of the server. The resulting readcap is then stored in the metadata
- of the inbox.
- In addition to being able to check the inbox for mail, a blocktree message is sent to the receiving
- blocktree when mail is sent. This message may contain the entire contents of the mail, if the
- contents are short enough. But if the mail contains a lot of data, for instance a video, then
- the message just serves as a notification that new mail is available.
- \subsection{Social Network}
- Building a social network on top of the contacts app is fairly straight-forward. Once
- a contacts entry has been created for a person, most interactions between the user and that
- person can be implemented by sending mail. For example, when the
- user sends a direct message to a person mail is placed in their outbox
- and a blocktree message is sent to the root cluster of their blocktree. If the user wishes to
- send a message to a group of people, mail is sent to each one.
- This same mechanism can be used to implement status updates. When a user updates their status,
- they send mail to each of their "friends". The social networking app running on each of the contacts'
- devices will then display the latest status update from the user as their current status. This
- setup allows the user to "unfriend" anyone by simply omitting them from the list of recipients
- of these updates. To allow comments and likes on the status update to be visible to everyone
- that it was shared with, the block created in the outbox of each of the friends
- is a symbolic link to a single status update block. This symbolic link contains the
- readcap for the status update block.
- Comments and likes on status updates are implemented by sending mail to the user who posted the
- update. When one of the user's servers receives this mail, it then updates the block containing
- the status update with the new comment, or increments the like counter.
- It then sends mail to the people this status update was shared with, notifying them
- that the data has changed.
- \subsection{An e-commerce website.}
- The previous two examples show how to build decentralized versions of existing web applications,
- but blocktree also excels at building traditional web applications. Imagine an e-commerce website
- with multiple warehouses, all of whose inventory is to be visible to customers of the site. Part
- of the design consideration for the site is that the warehouses need to be able to update their
- inventory even when their internet service goes down, and that these updates need to be visible
- on the website once connectivity is restored.
- To accomplish this a designer could create a directory for each warehouse. This directory would have
- servers attached to it that are physically located at each warehouse. The inventory of the warehouse
- is then maintained in the warehouse's directory, satisfying the first requirement. Now, in order to
- enable efficient queries of the overall available inventory, the data from each of the warehouses
- needs to be merged. This is accomplished by creating another directory containing the merged data.
- In event sourcing terms this is called a read-model. This directory will have another cluster of
- servers attached which will act as web servers. These servers will subscribe to events published by the
- warehouse clusters, events indicating changing levels of inventory, and digest this information into
- a format that can be efficiently queried. These servers will also publish events to the warehouses
- when orders are placed, cancelled or amended.
- When a warehouse goes offline, its previous inventory counts are
- still recorded in the read-model, so queries can still be answered using the cluster's best
- knowledge of the warehouse. Once the warehouse comes back online, then the events that were recorded by the
- warehouse cluster while it was offline can be replayed to the web server cluster, and their read-model
- can be brought up to date.
- One of the advantages of this approach is that the cluster of web servers need not be physically
- close to each other. In fact they could be spread over several data centers, even in different
- cloud providers. This allows for greater fault tolerance and reliability. Of course, running a
- consensus cluster over a larger area means more latency and thus reduced performance, but if
- the workload is read-heavy, and writes can be handled mostly in the warehouse clusters, then this
- tradeoff may be worthwhile.
- I hope this example shows that having a standard format for data and the federation of servers,
- can provide designers with much greater flexibility, even if they do not care about decentralization
- or their user's privacy.
- \subsection{A Metaverse}
- As a final example I'd like to consider a platform for recording spacial information. The key insight
- that enables this is very general: blocktree enables the creation of distributed tree-like data structures.
- For instance, its straight forward to imagine creating a distributed hashtable implemented as a red-black tree.
- This impedance match between efficient query structures and the design of blocktree is one
- of the reasons why I believe it is so useful. The particular data structure germane to building the metaverse
- is the Binary Space Partition (BSP) tree.
- I don't see the metaverse as being one world, but rather many. Each world would be hosted by its own blocktree.
- The world will have a directory in the blocktree, that directory will be the root of a BSP. read
- access to the world is controlled by adding readcaps to this directory. If the world is to be
- publicly accessible, then then its block can be stored in plaintext.
- Thinking of worlds
- like ours (those that can be reasonably approximated as the surface of a sphere) we can impose the usual latitude
- and longitude coordinate system. We can then define parcels in the world by specifying the polygonal boundary as
- a set of these coordinates (more precisely, the parcel is the convex hull of this set of points). These parcels
- are then recorded as blocks in the world's directory, whose path is determined by its virtual location using
- the BSP algorithm. If a parcel
- is owned by the same user who owns the world, then the data contained in the parcel is stored in
- the same blocktree. However, if a parcel is to be owned by another user, then a symbolic link is created
- pointing to a block in the owner's blocktree. They can then write whatever data they want into this block, defining
- the contents of their parcel. Collaboration on a single parcel is accomplished by issuing a read and writecap to
- another user.
- It's easy to imagine that one world would be more important than the rest and that the creation of a metaverse
- representation of the Earth will be an important undertaking. The hierarchical nature of permissions in blocktree
- make such a shared world possible. National blocktrees could be given ownership of their virtual territory,
- this would then
- be delegated down to the state and municipal levels. Finally municipalities would delegate individual parcels
- to their actual owners. Owners could then use these as they see fit, including leasing them to third parties.
- The ending date of such a lease would be enforced technically by the writecap issued to the lessee; when it
- expires so too does the lease.
- \section{Conclusion}
- In this paper I have given the outline of a decentralized method of organizing information, computation,
- and trust in a way that I hope will be useful and easy to use. The use of cryptographic primitives for
- implementing access control were discussed, as well as methods of protecting private keys. A blockchain
- and corresponding cryptocurrency was proposed as a means of incentivizing the distribution of data.
- Erasure coding was used to ensure that distributed data is resilient to the loss of servers and can be
- reconstructed efficiently. A programming environment based on WASM and WASI was proposed as a way
- of providing an interface to this data. APIs for defining protocol contracts and efficient web servers
- were indicated. APIs for constructing supervision trees were mentioned as a means for building reliable
- systems.
- When Sir Tim Berners-Lee invented HTTP he could not have anticipated the applications
- that his inventions would bring about. It has been said that the key to the success of his system is
- that it made networking programming so easy that anyone could do it. I don't know what the future will
- bring, but I hope that this system, or one like it, will enable anyone to fearlessly build distributed
- systems.
- One thing is certain however, it is a moral imperative that we provide users with viable alternatives
- to online services which harvest their data and weaponize it against them. Only then will the web
- become the place it was meant to be.
- \printbibliography
- \end{document}
|