scorex.tex

\documentclass[]{report}   % list options between brackets

\usepackage{color}
\usepackage{graphicx}
%% The amssymb package provides various useful mathematical symbols
\usepackage{amssymb}
%% The amsthm package provides extended theorem environments
\usepackage{amsthm}
\usepackage{amsmath}

\usepackage{listings}


\newtheorem{axiom}{Axiom}

\newtheorem{proposition}{Proposition}
\newtheorem{definition}{Definition}

\def\shownotes{1}
\def\notesinmargins{0}

\ifnum\shownotes=1
\ifnum\notesinmargins=1
\newcommand{\authnote}[2]{\marginpar{\parbox{\marginparwidth}{\tiny %
  \textsf{#1 {\textcolor{blue}{notes: #2}}}}}%
  \textcolor{blue}{\textbf{\dag}}}
\else
\newcommand{\authnote}[2]{
  \textsf{#1 \textcolor{blue}{: #2}}}
\fi
\else
\newcommand{\authnote}[2]{}
\fi

\newcommand{\knote}[1]{{\authnote{\textcolor{green}{Alex notes}}{#1}}}
\newcommand{\anote}[1]{{\authnote{\textcolor{red}{asc9 notes}}{#1}}}

% type user-defined commands here
\usepackage[T1]{fontenc}

\usepackage{xcolor}

\definecolor{dkgreen}{rgb}{0,0.6,0}
\definecolor{gray}{rgb}{0.5,0.5,0.5}
\definecolor{mauve}{rgb}{0.58,0,0.82}
\lstdefinestyle{myScalastyle}{
  frame=tb,
  language=scala,
  aboveskip=3mm,
  belowskip=3mm,
  showstringspaces=false,
  columns=flexible,
  basicstyle={\small\ttfamily},
  numbers=none,
  numberstyle=\tiny\color{gray},
  keywordstyle=\color{blue},
  commentstyle=\color{dkgreen},
  stringstyle=\color{mauve},
  frame=single,
  breaklines=true,
  breakatwhitespace=true,
  tabsize=3,
}
\newtheorem{claim1}{Claim}
\newtheorem{dfn}{Definition}
\newtheorem{defn}{Definition}
\newcommand{\ma}{\mathcal{A}}
\newcommand{\mb}{\mathcal{B}}
\newcommand{\he}{\hat{e}}
\newcommand{\sr}{\stackrel}
\newcommand{\ra}{\rightarrow}
\newcommand{\la}{\leftarrow}

\newcommand{\ignore}[1]{} % may contain useful stuff (that needs more work)
\newcommand{\full}[1]{} % use only for full version
\newcommand{\notfull}[1]{#1}
\newcommand{\rand}{\stackrel{R}{\leftarrow}}
\newcommand{\haya}{blue}
\newcommand{\amitabh}{purple}
\newcommand{\questions}{blue}
\newcommand{\defined}{\stackrel{\mbox{\tiny{def}}}{=}}
\newcommand{\mc}{\mathcal}
\newcommand{\ms}{\mathsf}
\newcommand{\txs}{\textsf}
\newcommand{\lea}{\leftarrow}
\newcommand{\rea}{\rightarrow}
\newcommand{\adv}{{\cal A} }
\def\kg{{\sf{Gen}}}
\def\enc{{\sf{Enc}}}
\def\dec{{\sf{Dec}}}
\newcommand{\btc}{\includegraphics[height=8pt]{assets/btc.jpg}}

\begin{document}

\title{The Blockchain and the Scorex Tutorial}
\author{Alexander Chepurnoy and an anonymous contributor}         
\date{Jun-Dec, 2016}
\maketitle

\chapter{Executive Summary}

This paper describes the Scorex project and how it can be used to implement blockchain protocols~(such as Bitcoin). Scorex is a framework written in Scala with loosely coupled components. 
The intended audience is developers willing to create or experiment with such blockchain cores. Some basic knowledge of cryptography, data structures and cryptocurrencies is required. Some programming background is also required to understand the code-snippets. For good explanation of cryptography primitives and protocols please refer to the foundational book of~\cite{katz2014introduction}. 

In order to understand Scorex, it is helpful to consider Bitcoin, Namecoin and Ethereum as three distinct applications of the blockchain. Scorex gives the underlying framework for developing any of the three applications (and several others) by writing a thin layer of code. 

\begin{enumerate}
	\item {\em Bitcoin:} Decentralized currency~\cite{Nakamoto2008}.
	
		{\em Purpose:} Decentralization of money, easy to store and spend.		
	\item {\em Namecoin:} Decentralized DNS\footnote{http://namecoin.info/} (stores {\em key} $\rightarrow$ {\em value} mappings).
		{\em Purpose:} Decentralization of DNS, difficult to sensor or shut down.		
	\item {Ethereum:} Smart	contracts.	
	  {\em Purpose:} Enable trustless computing via decentralization.		
\end{enumerate}


\section{Organization}


This document is organized as follows. In Chapter~\ref{bitcoin-intro}, we give an introduction to Bitcoin. In Chapter~\ref{blockchain-intro}, we describe basic building blocks of a blockchain system. In Chapter~\ref{impl}, we describe how the blocks are implemented in the Scorex framework. We provide code snippets in Scala language. No prior knowledge of the Scala language is required.

\ignore{

\chapter{Introduction}

If you have heard of blockchain then you have indirectly heard of Bitcoin, the decentralized peer-to-peer currency network with some fancy features such as the ability to transfer real value over virtual channels. This is because Bitcoin is the first widespread use of the blockchain, which is essentially a {\em decentralized tamper-resistant append-only database} of transactions (sometimes also referred to as a {\em ledger}). Let us elaborate on this in more detail in the following sections. 
\section{Blockchain and Boxes}


Define $F$ to be the set of mappings $\mathbb{Z}\times\mathbb{Z}^{+} \mapsto \{-1, 0, 1\}$ over the integers. 
Each pair represents a `box' of type ((public-key, coinID), amount)\footnote{Each integer in the left of $\mathbb{Z}\times\mathbb{Z}^{+}$ is assumed to map to a unique pair of type (public-key, coinID), where coinID is some unique identifier for the coins. For now, it is sufficient to consider the left integer as some `ownership identifier' of the amount on the right.}. 

Each element from $F$ maps the pairs of such integers (i.e., all boxes) to one of three states: $-1, 0, 1$, indicating that the corresponding box is respectively {\em Unused} (never used), {\em Closed} (contains funds) and {\em Opened} (funds have been used).
A blockchain is an infinite sequence $f_0, f_1, f_2, \ldots \in F$ of functions from $F$ applied iteratively on $\mathbb{Z}$ such that: % each $f_i$ satisfies the following:
\begin{enumerate}
	\item $f_i \neq f_{i+1}$ (there must be at least one state change in the boxes).
	\item $\forall (x, y) : f_i(x, y) \leq f_{i+1}(x, y)$ (state cannot decrease).
	\item $\forall (x, y) : f_i(x, y)\cdot f_{i+1}(x, y) = 0$ (state cannot increase > 1).
\end{enumerate}

$f_0$ is called the {\em genesis mapping} or {\em genesis state}. Each mapping $f_i$ represents a snapshot of the system at iteration $i$, which indicates the state of each box. 
The set $m_i=\{(x, y)| f_i(x, y) = 0\}$ is called the {\em minimal state} at iteration $i$. 

A {\em block} $b_i$ gives the deltas between two successive states $(f_{i+1}, f_{i})$ and is essentially defines a set of boxes to open and close. Formally, $b_{i}$ is the set $\{(x, y)|f_{i+1}(x, y)\neq f_i(x, y)\}$. The transformation rules ensure that there is a unique block for each iteration. At any iteration $i$, a client needs only the current minimal state $m_i$ and the next block $b_i$ to compute the next minimal state. 
While this is enough to define a generic blockchain, Bitcoin has some additional rules:

\begin{enumerate}
	\item For any block $b_{i}$, $$\sum_{(x, y)\in b_{i}} y\cdot f_{i+1}(x, y) +\sum_{(x, y)\in b_{i}} y\cdot f_{i}(x, y) \leq  r(i),$$ for some {\em reward} function $r$.
	
	Note that $\sum_{(x, y)\in b_{i}} y\cdot f_{i}(x, y)$ is the negative of the sum of amount in all the boxes to be closed in this iteration and $\sum_{(x, y)\in b_{i}} y\cdot f_{i+1}(x, y)$ is the sum for the boxes to be opened. Thus, the LHS is the amount of bitcoins `created' in this block minus the amount bitcoins `destroyed'. The inequality says that the net amount of bitcoins created in a block cannot be more than the reward. 
	\item For each box $(x, y)\in b_i$, there is a {\em transaction} that acts as the {\em witness} of opening or	closing that box. A transaction acts like a proof that a particular state change was authorized via some public key, which will be discussed in detail in the next chapter. 
\end{enumerate}

At any iteration $i$ of the blockchain, older snapshots $(f_0, f_1, f_2, \ldots)$ are considered tamper-resistant while fresh copies ($\ldots, f_{i-2}, f_{i-1}, f_i$) may be susceptible to deletion or tampering, depending on the computational power of the attacker. However, after the snapshot becomes sufficiently old, it can be considered as tamper-proof for all practical purposes. The rules of the protocol ensure that if all honest nodes start with the same initial state $f_0$ and apply the same blocks successively then they will have the same snapshots $f_i$ at any iteration $i$. The task here is to ensure that the blocks are always applied in the right order. This is a consensus problem, and is solved in Bitcoin using a concept called {\em proof-of-work} -- the solution to a hard puzzle. The idea is that not everyone gets to choose which block to apply to reach the next valid snapshot, but only by someone who has invested a large amount of computing power and provides the proof on a first-come-first-serve basis. Snapshots are connected -- each block is linked to the previous one via a cryptographic hash so that if someone else provides a proof-of-work and the network accepts it, then all existing work for ``winning'' this block is invalidated and the contenders have to start again with the newly accepted block as the starting point. To incentivize nodes to expend work, each accepted snapshot comes with some reward in the form of tokens generated (additional states that benefit the node solving the puzzle). 

The rules encoding state changes are hardwired into the peer-to-peer nodes so that once a majority of them are running the code and act honestly, we can be ensured that block updates follow the correct rules. Blockchain can tolerate a high number of corrupt nodes (those controlled by an attacker) -- close to 40\%. 

\paragraph{Transactions:} Transactions can also be seen as state changes authorized via private keys and validated by the corresponding public keys. The transaction can encode information pertaining to funds transfer (as in Bitcoin) or have additional information pertaining to the external world such as attaching a key-value pairs to a public key (as in Namecoin -- a decentralized DNS).
While Bitcoin seems to be the primary use of blockchain right now, other intriguing use cases such as Namecoin have also been presented. The most powerful of being programmable-blockchains. The idea is simple -- while in Bitcoin, the rules encoding the state changes pertain only to spending of funds, nothing prevents us from coming up with more complex rule that can encode some business logic. One such example, already mentioned, is Namecoin, which additionally has rules for reserving doman names and for transferring them. In all cases, the rules will be written in a language that the node understands and accepts (the grammar is hardwired into the node). 

The newer applications of blockchain are all based on how these rules can be written and how expressive the language is. For instance, Ethereum, another blockchain based protocol boasts of a Turing complete language in contrast to the tiny one that Bitcoin provides. The following summarizes the main proposals.

%
\begin{enumerate}
	\item {\em Bitcoin:} Decentralized currency~\cite{Nakamoto2008,}.
	
		{\em Advantages:} Decentralization of money, easy to store and spend.
		
		{\em Challenges:} Too much storage, wild price fluctuations, too much energy consumed, limited bandwidth of blocks, not suitable for micro-transactions.
	\item {\em Namecoin:} Decentralized DNS (stores {\em key} $\rightarrow$ {\em value} mappings). 

		{\em Advantages:} Decentralization of DNS, difficult to sensor or shut down.
		
		{\em Challenges:} Similar in design to Bitcoin; some similar challenges, low computing power so less attack resistant.
	
	\item {Ethereum:} Smart	contracts.
	
	  {\em Advantages:} Enable trustless computing via decentralization.		
		
		{\em Challenges:} Turing completeness causes complexity, may have security issues -- example DAO attack.
	
\end{enumerate}
}

\chapter{Overview of Bitcoin}
\label{bitcoin-intro}
Here we attempt to give a high-level overview of Bitcoin. Some of the terms we will discuss are: {\em transaction}, {\em input}, {\em output}, {\em reference}, {\em block} and {\em confirmation}. We will revisit these terms in next chapters providing more abstract definitions.

In most cases of Bitcoin, funds are exchanged between {\em addresses} which are hashes of public keys. We will sometimes use the terms `address' and `public key' interchangeably. However, it should be remembered that addresses are one-way hashes of public keys. 
 
\section{Transaction} A transaction is a string sent over the peer-to-peer network that results in funds being transferred from one or more addresses to other addresses.
A transaction consists of \emph{inputs} (source of funds) and \emph{outputs} (destination of funds).
%Depending on the context, a symbol $A$ could refer to a public key or an address (the meaning will be clear from the usage).
The smallest unit of Bitcoin is Satoshi (1 Bitcoin $=10^8$ Satoshis), which is what we will use in our text.

Suppose an address $A$ owned by Alice has $x$ Satoshis. Alice wants to send $y \leq x$ Satoshis to address $B$ owned by Bob.
This can be done by creating a transaction with $A$ as the input and $B$ as one of the outputs.
The transaction additionally has information for other nodes to quickly validate that $A$ indeed has $x$ Satoshis to spend.
This is done by adding a reference to some previous transaction's output where $A$ actually received those $x$ Satoshis. Let us call this $ref_{A \leftarrow x}$.
The outputs are constructed as follows: The first output sends $y$ Satoshis to $B$. Alice then sets a transaction fee $t$ and adds a second output sending the remaining $z = x-y-t$ Satoshis to her {\em change address} $C$. The change address is simply any address owned by Alice and could also be $A$.

The message $\mbox{``{($ref_{A\leftarrow  x}$, take $x$ from $A$), (put $y$ in $B$), (put $z$ in $C$)}''}$ together with its signature under $A$ is considered a `transaction'.
%The above transaction assigns $\btc y$ from Alice's public key $A$ to Bob's public key $B$. 
%For the transaction to be valid, it must hold that $x \geq y+z$. (In general there can be several outputs as long as the sum of outputs is less than or equal to the input.) The transaction additionally has a verification condition which must pass for the funds to unlocked by $B$. Without loss of generality, we assume that the verification condition is ``Any funds leaving $B$ must be signed under $B$.'' More complex conditions can be inserted here. 

Let us define the following notation:
\begin{itemize}
	\item $ref_{X \leftarrow x}$ is the message ``($ref_{X \leftarrow x}$, take $x$ from $X$)''. This is an input.
\item
$X \leftarrow x$ is the message ``put $x$ in $X$''. This is an output.
\item
$\sigma_X(m)$ is signature on message $m$ with the private key corresponding to the public key $X$. %That is, public key $X$ is used to verify the signature.
\end{itemize}
Alice's transaction is then $(m, \sigma_A(m))$, where $m  =  (ref_{A \leftarrow x}, B \lea y, C \lea z)$.
 
A transaction can have several inputs and outputs. The only restriction is that the total amount of funds destroyed (via the inputs) must be greater than or equal to the total amount of funds created (via the outputs). Any difference is considered a {\em transaction fee}.\footnote{Transaction fee is collected by someone who confirms the transaction and is used both as an incentive for participation and a deterrent for spam attacks.} More formally:

\begin{definition}
Define $m$ to be the message
\[
M \defined (ref_{A_1\leftarrow x_1}, ref_{A_2\leftarrow x_2}, \ldots, ref_{A_n\leftarrow x_n}, B_1\la y_1,
B_2\la y_2, \ldots, B_l\la y_l), 
\] 
where $ref_{A_i\leftarrow x_i}$ are references to $n$ previous transaction outputs where $A_i$ received $x_i$ bitcoins, and $(B_i, y_i)$ are $l$ pairs of type (addresses, amount). 
%\paragraph{Inputs and outputs:} In message $M$ above, define inputs and outputs as follows:
%\[\mbox{Inputs }\defined A_i\sr{ref_i}{\ra} x_i~~~~~~~~(1\leq i \leq n)\] 
%\[\mbox{Outputs }\defined B_i \la y_i~~~~~~~~(1\leq i \leq l)\]
A valid transaction $tx$ is a tuple: 
\begin{equation}\label{tx0}tx\defined (M, \sigma_{A_1}(M), \sigma_{A_2}(M), \ldots, \sigma_{A_n}(M))\end{equation} such that each signature $\sigma_{A_i}(M)$ is correctly verified by the public key $A_i$ and the following holds:
\begin{enumerate}
	\item $\sum_{i=1}^{l}y_i \leq \sum_{i=1}^{n}x_i$ 
	\item Each $ref_{A_i \leftarrow x_i}$ for $1\leq i\leq n$ was never used in any prior transaction.
\end{enumerate}
\end{definition}

\paragraph{Referencing outputs:} In future, when spending the funds from any of the outputs (say $B_i \la y_i$) of the above transaction, a reference $ref_{B_i \leftarrow y_i}$ to that output needs to be provided. %This reference is computed as follows. 
Let $tx$ be the string of Eqn.~\ref{tx0}. Then: \[ref_{B_i \leftarrow y_i}\defined (Hash(tx), i)\]

The ordering of the signatures in $tx$ is determined from the ordering of messages inside $M$ (which is fixed due to the signatures). Thus each $i$ uniquely defines one output.

To prevent double spending, Bitcoin requires that a reference should be used in a transaction at most once. This is enforced as follows.
An unused reference is also called an unspent output (UTXO for short). Each client maintains a set of UTXOs.
Each output of every transaction is added to this set, and removed when it is used as a reference in another transaction.
A transaction with a reference not in this list is not processed.

\section{Validating Transactions}


A new transaction is valid if all the references are unused. If so, the transaction is accepted as {\em valid} but {\em unconfirmed}, and is relayed on the network. The clients add each such transaction to their (private) pool of unconfirmed transactions. Unconfirmed transactions can be double-spent. Here we describe the validation process in more detail.
Recall that a transaction is equivalent to 
$$tx\defined (M, \sigma_{A_1}(M), \sigma_{A_2}(M), \ldots, \sigma_{A_n}(M)),$$ 

where $M$ is of type:
\[
M \defined (ref_{A_1\leftarrow x_1}, ref_{A_2\leftarrow x_2}, \ldots, ref_{A_n\leftarrow x_n}, B_1\la y_1,
B_2\la y_2, \ldots, B_l\la y_l).
\] 

The values $A_i$ and $x_i$ are obtained from a {\em UTXO database} that every client must maintain.\footnote{The inputs additionally include the public key corresponding to address $A_i$. We can assume that this key is part of the signature.} 
This database is a key-value store of type $ref_{A_i \leftarrow x_i} \ra (A_i, x_i)$. Note that in order to validate transactions and participate in the protocol, maintaining this UTXO database is necessary. Once a node has bootstrapped and downloaded some length of the blockchain, it can quietly discard those downloaded blocks once its UTXO database resulting from those blocks has been generated (it could store a few recent blocks to handle rollbacks). It can keep updating this database as new blocks are received. Thus, even if a node is not storing blocks, it must still parse every new block to update its UTXO database. Observe that a node that does not store blocks cannot help new nodes to bootstrap.


It is helpful to consider each (unused) $ref_{A_i \lea x_i}$
%$A_1\sr{ref_1}{\ra}x_1$ 
above as a ``closed box'' with $x_i$ inside such that the box can only be opened via the private key corresponding to $A_i$. The act of using $ref_{A_i \lea x_i}$ in a transaction as ``opening the box'' and releasing $x_i$. A box can be opened at most once and the act of sending bitcoins to an address ($B_i\la y_i$) generates a new closed box, $ref_{B_i\lea y_i}$ with $y_i$ inside. 

The semantics of transactions are specified using some encoding and a DSL called {\em Script} (a stack-based language similar in design to Forth). 

The output of a transaction contains an {\em Output Script} which is equivalent to ``partial unlocking instructions'', a sequence of operations that when combined with another script will result in the Satoshis being unlocked. The remaining part of the unlocking instructions are provided when that output is later spent via a {\em different} 
transaction. This is called the {\em Input Script} because the output being spent becomes the input of the new transaction. 

The input script contains the signature and public key, while the output script contains instruction to verify the signature for the address holding the Satoshis. The (signature, public-key, address) triplet is considered valid if the combined script evaluates to non-zero (True).

%How to spend an output? In Bitcoin it contains a script in a stack-based language. Input also contains a script. Then an input could spend an output if a combined script made of inputs' and then outputs' could be executed and results in non-zero top stack item.
%
%[TODO: example]

A node validates a transaction by validating every input as follows:
%As a basic requirement, Script has the following instructions:

% verifying signature
% input script defines the steps to do (i.e., verify signature)
% output script defines how to create the new box

\begin{enumerate}
  \item	For each input $ref_{A_i\lea x_i}$ from $(ref_{A_1\leftarrow x_1}, ref_{A_2\leftarrow x_2}, \ldots, ref_{A_n\leftarrow x_n})$
	
	\begin{enumerate}
		\item Load signature $\sigma_i$ and public key corresponding to $A_i$ into stack (public key is in the signature). This is the Input Script.
		\item Using the key $ref_{A_i \lea x_i}$ find the value $(A_{i},  x_i)$ from the UTXO database. %This is the output of a transaction where $A_i$ received $x_i$ bitcoins. 
		\item The loaded box contains the amount to be released as well as the output-script (that verifies the above signature on $M$). The input-output script is evaluated and the box is opened if the result is True (non-zero), otherwise an error is thrown.
	\end{enumerate}
	\item If all boxes are opened, then we create new boxes $B_i\la y_i$ as defined by the outputs, provided that the total amount released from boxes is more than or equal to the total amount in the newly created boxes. 
\end{enumerate}

The opened and created boxes are not immediately committed to the UTXO database. Rather, every node must wait for the network to ``confirm'' the changes implied by any given transaction.  
Transactions are confirmed in batches such that all nodes quickly reach a consensus on which set of transactions to include in the next database update. 
To ensure consistency and fast consensus, only someone who has invested a large amount of CPU cycles gets to select which set of transactions to commit in the next batch. This node is called a {\em leader} or {\em miner} and is selected at each update. 
 
\section{Confirming Transactions}
\label{sec:verify}
Miners are nodes that propose a set of transactions to commit along with a proof that they have put in a certain minimum amount of work (in the form of CPU cycles) after the last update. The network selects the first solution. 

A miner confirms transactions as follows. First the miner constructs a block $b$ as a sequence of bytes containing the following data:
\begin{enumerate}
	\item A number of unconfirmed transactions along with one reward transaction %\footnote{The reward transaction has no inputs. It takes the fees and the block reward.} 
	(known as the \emph{coinbase transaction}).
	\item Hash value of the previous block $h_{pr}$  and a nonce. %(version, etc) %. , computed incremented from the last block and the SHA256 hash of the last block is added to the block.
	%\item A nonce is added to the block.
	%\item
\end{enumerate}

 Finally, $h =$ Hash($b$) is computed. If $h$ contains at least a specified number of leading zeros, the block $b$ is considered {\em mined} and broadcast to the network, otherwise the miner tries with different nonces until a mined block is found or another mined block containing $h_{pr}$ is received from elsewhere. All transactions in a mined block are considered {\em confirmed}.

\paragraph{Confirmations:} The number of confirmations of a transaction are the number of mined blocks that have been accepted by the network after the block that included that transaction. In other words, it is the {\em depth} of that transaction in the blockchain. The possibility of double-spending a transaction decreases exponentially with the number of confirmations. The default client requires 6 confirmations for normal transactions and 100 confirmations for reward transactions before they can be spent.  

\paragraph{Transaction pool management:} Each client maintains a pool of unverified (but valid) transactions. An element is removed from this pool when that transaction gets included in a mined block. This ensures that even if a transaction is not included in an immediate block, it is kept in the pool until it gets mined. If a transaction is not confirmed within 72 hours, then it is forgotten. 

\paragraph{Proof of Work:} Recall that we consider a block to be mined only if its hash value contained at least a `specified' number of leading zeros. Assuming that the hash function behaves like a random oracle, the probability of a random image of $k$ bits having $x$ leading zeros is about $2^{-x}$ and the only way to obtain such a value is to try hashing around $2^x$ different blocks.

This is called {\em Proof of Work} (PoW) because it is a witness that someone spent $2^x$ CPU cycles on average. The sole purpose of PoW is to secure the blockchain against tampering. 
Security in our sense implies the {\em persistence} of the blockchain, i.e., the inability to an attacker to fool a node into accepting a truncated or forked copy of the `true' blockchain (i.e., with different set of transactions that either don't include the real ones or double spend them). Bitcoin uses the following measure for difficulty: if the leading number of zeros are $x$ then {\em difficulty} $=2^{x}$ and {\em target} $=2^{k-x}$. 
If two competing blockchain are presented, honest nodes select the one with the highest {\em cumulative difficulty}~(i.e. the one where the summation of difficulties is the largest). 
%Define the function $zero(b)$ to output the number of leading zeros in block $b$. 
%Given two blockchains $B_1, B_2$, we first compute $s_1 = \sum_{b \in B_1} 2^{zeros(b)}$
%, the ratio of the maximum number of the image of the hash can represent and the highest number forms a valid hash.




%\begin{enumerate}
	%\item Prevent spam: Since PoW requires resources, the need to be compensated for in terms of transaction fees. A miner will select the transactions that give the maximum fee and SPAM transactions (that don't cost the sender much) will be rejected.
	%\item Secure the network: Security in our sense implies the {\em persistence} of the blockchain, the inability to an attacker to truncate or fork the blockchain with different set of transactions that either don't include the real ones or double spend them. 
%\end{enumerate}

\paragraph{Difficulty Adjustment:} We mentioned that the binary representation of the hash of a block must have at least a `specified' number $x$ of leading zeros. This is formalized as: Hash$(b)\leq $ target ($=2^{k-x}$). The current target changes in accordance with how fast or how slow the blocks are accepted by the network during a time frame of 2 weeks. At this rate, there should be exactly 2016 blocks generated in two weeks. If the average over 2 weeks is more or less than 1 block every 10 minutes, the protocol will adjust the current target and attempt to bring it back. However, if the hashing power of the network increases sub-exponentially (or faster), then difficulty may never catch up and the average block time will always be less than 10 minutes (as it was observed in Bitcoin during periods of exponential hashrate growth). 

\paragraph{Storage Requirements:} As discussed earlier, at the minimum each node must store the unopened boxes in a UTXO database to ensure that the spender actually holds those bitcoins. Additionally, each node may store the entire blockchain starting from the genesis block to help other clients to bootstrap. 

\section{Block Structure} 

A block consists of a variable-size {\em payload} containing the actual transactions and a fixed-size {\em header} describing the payload. 
Earlier we stated (for simplicity) that the PoW is computed as a hash of the entire block. This is not true. The PoW is computed only on the header and not the payload. This enables nodes to verify PoW using just header information, while the payload can be verified later via the root hash. 
The header is 80 bytes and contains: 
\begin{enumerate}
	\item The root hash of the Merkle tree\footnote{Merkle tree is a technique for authenticating small slices (few transactions) from a large chunk of data (entire payload) without having to authenticate the entire data (however, the entire data can be authenticated if needed).} of transactions in the payload.
	\item The current block index and the previous block-header hash.
	\item The nonce, the corresponding difficulty target and a timestamp.
\end{enumerate}


\paragraph{Example of header:} The following is an example of a block header\footnote{https://bitcoin.org/en/developer-reference\#block-headers}:\\
\texttt{\underline{02000000}b6ff0b1b1680a2862a30ca44d346d9e8910d334beb48ca0c00000000}\\
\texttt{00000000\underline{9d10aa52ee949386ca9385695f04ede270dda20810decd12bc9b048a}}\\
\texttt{\underline{aab31471}24d95a54\underline{30c31b18}fe9f0864}

The different sections are identified by alternating underlines:
\begin{enumerate}
	\item Block version: \texttt{02000000} (decodes to 2).
	\item Hash of previous block's header: \texttt{b6ff0b1 $\ldots$ 48ca0c0000000000000000}.
	\item Merkle root hash of payload: \texttt{9d10aa52 $\ldots$    decd12bc9b048aaab31471}.
	\item Unix timestamp: \texttt{24d95a54} (decodes to 1415239972).
	\item Difficulty target: \texttt{30c31b18} (decodes to $1bc330_{\texttt{hex}} \cdot 256^{18_{\texttt{hex}}-3}$).
	\item Nonce: \texttt{fe9f0864}.
\end{enumerate}
	
\paragraph{Computing the Merkle root:} The transactions are first arranged in some order that satisfies the consensus rules given below. Their transaction hashes (TXIDs) are considered as the last row (leaves) of the tree that will be constructed. Starting with the last row, each row is iteratively processed to get the previous (parent) row until the currently processing row has only one node, the Merkle root. 
If the currently processing row has two or more nodes, we first ensure that there are even number (say $n$) of them, by adding a null element if necessary. Then we pair the nodes to form $n/2$ pairs. Each pair $(L, R)$ is concatenated and its hash $\texttt{SHA256}(L||R)$ forms the parent for the next iteration. This process is repeated until the root is reached. 


\paragraph{Payload:} The first field of the payload defines the number of transactions. The rest of the payload contains the raw transactions concatenated in the same order as in the Merkle tree.


\paragraph{Consensus rules:} A client rejects block that do not follow the below rules:
\begin{enumerate}
	\item The coinbase transaction's TXID is always placed first.
	\item Any input within this block can spend an output which also appears in this block (assuming the spend is otherwise valid). However, the TXID corresponding to the output must be placed at some point before the TXID corresponding to the input. This ensures that any program parsing block chain transactions linearly will encounter each output before it is used as an input.
\item If a block only has a coinbase transaction, the coinbase TXID is used as the merkle root hash.
\end{enumerate}





\section{Security and Privacy} 
\label{btc-security}
At the heart of Bitcoin is the concept of the blockchain, a distributed global ledger of transactions that each node holds. The goal of the protocol is to ensure {\em eventual consistency}; if the network is completely synchronized then all nodes will have an identical copy of the blockchain. Thus, the primary goal of Bitcoin is to select the ``valid'' chain given more than one contenders. 


\paragraph{Selecting a unique chain:} It is conceivable that an attacker (or network failure) can cause two or more competing chains to be temporarily (a {\em soft-fork}) or permanently (a {\em hard-fork}) present in the system. The nodes should be able to quickly reject the ``invalid'' one. The protocol selects the chain with the highest cumulative difficulty, rather then the longest one. 

%\paragraph{Difficulty level adjustment:} Difficulty is a measure of the hardness of the puzzle and can be quantified by $x$, the maximum possible number representable with that many leading zeros. 
%A difficulty level of $d$ implies that $d = 2^{256}/x$. Thus, the smaller $x$ is, the larger the difficulty. The difficulty is adjusted every 2016 blocks based on the time it took to find the previous 2016 blocks. At the desired rate of one block each 10 minutes, 2016 blocks would take exactly two weeks to find. If the previous 2016 blocks took more than two weeks to find, the difficulty is reduced. If they took less than two weeks, the difficulty is increased. The change in difficulty is in proportion to the amount of time over or under two weeks the previous 2016 blocks took to find.




\paragraph{Security Requirements:} For security, we require the following: (1) The inability of an attacker to send bitcoins from addresses whose private key is not known, (2) The inability of an attacker to double-spend bitcoins or reverse a transaction, and (3) The inability of an attacker to prevent some valid transactions from confirming. The first requirement is satisfied if the underlying signature scheme is existentially unforgeable. The second and third requirements, formalized respectively as {\em persistence} and {\em liveness} in~\cite{Garay2015}, can be achieved if the underlying proof-of-work (PoW) based consensus system satisfies the following two properties~\cite{Garay2015}:
\begin{enumerate}
	\item {\em Common prefix:} If all honest participants remove the top (newer) $k$ blocks from their chains for a large enough $k$ then all of them will share a common prefix. In other words, the chains held by honest miners will either be identical or be contained in the others.
	\item {\em Chain quality:} There is some minimal integer $\lambda\geq 1$ such that, if the combined computing power of honest parties is $\lambda$ times that of the adversary, then a non-negligible amount of blocks generated by honest parties will make it into the chain. 
\end{enumerate}

If the difficulty level is sufficiently high and the network synchronization time (time between a new block being injected and reaching all participants) is short compared to average block generation period (10 minutes in Bitcoin) then the protocol offers high security. On the other hand, security is weakened if any of the following conditions hold~\cite{Garay2015}:
(1) overall computing power is low, (2) blocks are generated too fast, or (3) network takes long time to synchronize. 

\paragraph{Attacks on Implementation:} Following are attacks specific to Bitcoin:
\begin{enumerate}
	\item {\em Reused R-values:} The underlying signatures ECDSA can be broken if the same randomness is used in two different signatures~\cite{cryptoeprint:2013:734}. Thus, implementations must take additional care to use true randomness or message-specific one (computed as a hash of the message).
	%\item {\em Attack on cumulative difficulty:} Since the initial difficulty is small in the first two years of Bitcoin, a powerful attacker may be able to forge a chain longer than the current one  with higher cumulative difficulty. This attack becomes more difficult as the cumulative difficulty increases.
	\item {\em Centralization of mining:} If a majority of the mining power is concentrated in a few pools, then they can collude and attack Bitcoin. Part of the reason for this threat is the susceptibility to ASIC mining~\cite{Taylor:2013:BAB:2555729.2555745}.
	\item {\em Denial of service attacks:} Certain attacks are based on miners forcing other miners to skip block validation by generating large blocks or ones that require expensive verification. Thus, they could send wrong data that will result in other miners to later lose their work.
	\item {\em Malleability:} The signature encoding in Bitcoin is such that if certain bits of the signature are toggled, the result is still a valid signature (this is due to the underlying ECDSA scheme). This allows miners to mine a transaction whose is different from the original, while keeping everything else (i.e., inputs/outputs) same. If a bitcoin service uses the transaction hash to monitor funds being sent, then it could lose funds~\cite{decker2014bitcoin}.
\end{enumerate}

\paragraph{Privacy:} The addresses serve as pseudonyms and provide some anonymity. However, bitcoin does not provide true anonymity because the inputs are linked to the previous outputs via a reference.

\section{Further Reading}

The article ``How the Bitcoin protocol actually works'' by Michael Nielsen~\cite{nielsen} discusses various problems that led to the creation of Bitcoin. The original whitepaper by Satoshi Nakamoto~\cite{Nakamoto2008} provides a good description on the concepts and details can be found in the book ``Mastering Bitcoin''~\cite{antonopoulos2014mastering}. 



\chapter{A Blockchain System Design}             % chapter 2
\label{blockchain-intro}
\section{Introduction}     

We can define a blockchain as a {\em prefix-immutable append-log of non-conflicting authenticated-events in a decentralized peer-to-peer network}. Let us elaborate what this means.

Consider Bitcoin as an example, where a group of distrusting peers hold money in form of cryptographic tokens and can transfer them between themselves without any trusted mediator. The last part (``decentralized peer-to-peer network'') implies that these peers follow a protocol specified~(being effectively thrown away from the network otherwise) without any trusted arbiter. Peers issue ``authenticated events''~(signed messages of some semantics). For example, they can send out signed payments or they can register a \(name \rightarrow value\) pair in a shared database~(e.g. in order to register a domain). Bitcoin keeps records of transfers by building a blockchain, a type of {\em append-only database} (or ``append log''). If this append-log is ``prefix-immutable'' then all honest peers following the protocol will agree on an immutable prefix of events in the append log. That is, if we cut a suffix of some length from the log of every honest peer, then with overwhelming probability, the remaining entries in these logs will either be identical or be a proper sub-sequence of another honest node's log. ``Non conflicting'' implies that the log should not contain any sequence of events that violate protocol constraints.

Prefix immutability implies that older data in the append-log can be considered {\em tamper-resistant}. The immutability is achieved using a consensus method called {\em proof-of-work} (a solution to a exponentially hard puzzle that can be verified efficiently). The design of the protocol is such that the puzzle becomes harder as the data gets older. However, freshly added data (i.e., the last few versions of the log) are considered potentially unstable. 

Non-conflicting events in Bitcoin require that the same Satoshi cannot be spent twice (Satoshis are considered immutable; a transaction destroys old Satoshis and creates new ones). Thus, for example, if Alice has sent all her Satoshis to Bob, she can't send anything after that until she receives more of them from elsewhere.
Such double spends are prevented using the prefix-immutable database because the entire transfer history of every Satoshi (the smallest unit of Bitcoin) can be traced back to the time it was created. 


%
%\subsection{Security of Bitcoin}
%
%Like any multiparty protocol, Bitcoin needs {\em correctness} (`valid transactions' should go through) and {\em soundness} (`invalid transactions' must be blocked). Correctness is defined in terms of passive adversaries, who behave according to protocol and do not attempt deviate. Soundness is defined in terms of {\em chain quality} and {\em persistence} defined in Section~\ref{btc-security}.

%We will discuss how correctness 
%Correctness is trivially guaranteed because if all parties behave correctly, then the protocol indeed behaves as expected [...]. For soundness
\section{Cryptography}

\anote{will be improving this section as per Mario's comments}

Below are the cryptographic primitives needed to construct blockchain systems described in this chapter.
%At the minimum, Bitcoin requires the following cryptographic primitives:
\begin{enumerate}
	\item {\em One-Way Hash (OWH) functions:} A {\em One-Way Function} is easy to compute in the forward direction but difficult in the reverse. A {\em Hash Function} maps arbitrary sized strings to fixed size ones. Thus, a One-Way Hash (OWH) function efficiently maps arbitrary size strings to fixed sizes and is hard to reverse. Let there be an efficiently computable mapping $H:\{0,1\}^*\mapsto \{0,1\}^k$. 
	We say $H$ is a OWF if it is hard for any Poly-time attacker to compute two distinct values $x, y$ such that $H(x)=H(y)$. This property, {\em collision resistance}, also implies {\em pre-image resistance}, the inability of an attacker to compute any pre-image $x$ given $H(x)$.
	
	%We say that require the hash to be {\em collision resistance} (hard to find two arbitrary preimages with same hash) and {\em preimage resistance} (given hash, find any preimage)~\cite{schneier1996one}. For a good hash function there is no better way to break it than by brute force. By breaking, we imply finding a preimage satisfying certain predicate on the output.
	\item {\em Signature scheme:} A signature schemes consists of three algorithms:
	
	\begin{enumerate}
		\item  KEYGEN$(k)$: This takes as input a security parameter $k$ and outputs a (public-key, private-key) pair $(pk, sk)$. 
		\item  SIGH$(sk, m)$: This takes as input a private-key $sk$ and a message $m$. It outputs a signature $s$.
		\item  VERIFY$(pk, m, s)$: This takes as input a public-key $pk$, a message $m$ and a signature $s$. It outputs True or False.
	\end{enumerate}
	Correctness requires that for all $(pk, sk)$ pairs output from KEYGEN and for all $m$, it must hold that VERIFY$(pk, m, $ SIGN$(sk, m)) = $ True.
	
	%valid inputs the verification process outputs true.
	%A signature scheme is a type of public-key cryptography (i.e. based on two keys), where a private key is used to generate a {\em signature} on a message and the public key is used to {\em verify} the signature. 
	
	Security requires that this is the only way to generate valid signature. Formally, we define the security using a game where we give the attacker access to SIGN oracle for some private key $sk$ and require him to generate a valid signature (one that outputs True on VERIFY with $pk$) on a message that was never queried to this oracle.
	%should private key and the message allows creating a valid signature. The owner of a public key also cannot later deny having created the signature~\cite{schneier1996one}.
	%We require that the attacker cannot generate valid signatures on any arbitrary message even using the signing oracle on any other arbitrary messages. 
	This is called UF-CMA (unforgeability under adaptive chosen message attack)~\cite{schneier1996one}.
	
	We actually require a stronger property called {\em strong unforgeability} (SUF-CMA)~\cite{boneh2006strongly}. This requires that an attacker having access to a SIGN oracle for arbitrary messages cannot generate a {\em new} signature on a message whose signature has already been queried. Unfortunately, the signatures used in Bitcoin do not satisfy SUF-CMA (they do satisfy UF-CMA though). This has led to the {\em malleability} problem in Bitcoin.
	\item {\em Commitments:} Some proposals (such as ZeroCash~\cite{sasson2014zerocash}) use commitments, which allow a user, say Alice, to commit to a message $m$ without revealing  it. Instead she sends a commitment $c =$ COMM$(m, r)$, where $r$ is a random value. Later on, she can `open' her commitment by revealing $(m, r)$. A verifier then computes VERIFY$(c, m, r )$ and outputs either True or False. For correctness, we require that for all $(r, m)$, it must hold that VERIFY$($COMM$(m, r), m, r) =$ True.
	
	Commitments can be either: (1) {\em computationally binding}
	(so that Alice can cheat and present a different $m'$ if she has a large (but impractical) amount of computing power) and {\em perfectly hiding} (the commitment reveals no information about $m$ even to someone with infinite computing power), or: (2) {\em perfectly binding} (Alice cannot cheat even if she has infinite computing power) and {\em computationally hiding} (someone with very large but finite computing power can learn $m$) opening~\cite{damgaard1999commitment}. A commitment scheme cannot be both perfectly hiding and perfectly binding.
	
	\item {\em Non-Interactive Zero-Knowledge (NIZK) Proofs:} Let $N$ be an instance of any NP problem, such as finding the factors of a large integer. Let $P$ be a witness to this problem that Alice knows. 
	
	There are three requirements of NIZK proofs (of knowledge): (1) Given a \textbf{random} string $R$, Alice can construct a short proof $\pi=$ PROOF$(P, R)$ such that VERIFY$(\pi, R, N)=true$ iff Alice `really knows $P$'. The concept of `knowing' is captured as follows: (2) If Alice can be fooled into using a \textbf{maliciously crafted $R$}, then $\pi$ will reveal $P$ with a high probability. (3) Additionally, Alice can construct pairs $(\pi', R')$ such that VERIFY$(\pi', R', N) = true$ without knowing any witness $P$ as long as \textbf{she selects $R'$}. Thus, the generation of $R$ is of outmost importance because if the verifier selects $R$, the secret is leaked and if the prover selects $R$ then the proof is not convincing. If given the transcript of a proof, we cannot distinguish between the cases (1) and (3), then the protocol is zero knowledge, intuitively because given some $(\pi, R)$ pair, there is no way of knowing if it was generated using (1) or (3). An example of a NIZK proof is given in Appendix A.
\end{enumerate}

%Add commitments, etc


\section{Transactional Layer}

In this section we define a generalized view of transactional semantics of a blockchain system. %The two foundational concepts here are \textit{minimal state} and \textit{transaction}.

\subsection{Minimal State}
\label{min-state}
	Consider what a node does on receiving a transaction:

    \begin{enumerate}
		\item Checks whether the transaction is valid.
		\item Apply the transaction if it is so.
    \end{enumerate}

	Intuitively, a node does some stateless checks (e.g., whether a signature is valid or the amount is non-negative) and some stateful ones (if Alice indeed has enough funds to send to Bob or if a registered domain has not been taken yet). 

	Thus, a node needs to store {\em some} state in order to validate incoming transactions. Additionally, there is a unique \textit{minimal state} containing the smallest set of state elements a node must store to validate arbitrary transactions. All nodes store this (common) minimal state but a node could also store some additional information. %In Bitcoin, this minimal state is simply the UTXO set.

	After applying a transaction, the minimal state is modified such that is impossible to apply the same transaction again at a later time. 

	Almost all cryptocurrencies of today are packing transactions into \textit{blocks}, which we can think of as \textit{atomic batch state updates}. 

   We can state some axioms here.

	\begin{axiom}
	 There is some initial state hard-coded into each node. Further we name it \textit{genesis state}.
	\end{axiom}

    \begin{axiom} 
     Validation and application of a transaction (plus any metadata) is a deterministic process and all the honest nodes follow the same rules. 
    \end{axiom}

	\begin{proposition}\label{prop1} Two nodes applying the same sequence of blocks to the genesis state will obtain identical minimal states.
	\end{proposition}	
	%\begin{proof}Consider the nodes have the same minimal state and trying to apply the same block to it. By the Axiom 2, they will have the same minimal state as result, as verification and application procedures are deterministic. By the Axiom 1, genesis state is the same for all the nodes. By induction, result of sequential applying of the blocks results in the same minimal states for all the nodes.\end{proof}

We will use the terms ``minimal state'' and ``state'' interchangeably. 


%\subsection{Bitcoin}
\paragraph{Example:} In Bitcoin, a transaction contains multiple \textit{inputs} and \textit{outputs}. Inputs are essentially the outputs of an older transaction previously applied to a state. In order to be valid, these older outputs should not have appeared as the input of any other transaction. One inefficient way to validate this would be to check every transaction in the blockchain appearing after that older output. A more efficient way would be to store the set of unspent older outputs and remove from the set once they appear as the input in a transaction.
Thus, %an output can be spent as whole only and so 
we can consider the set of unspent outputs (UTXOs) as the minimal state.

%How to spend an output? In Bitcoin it contains a script in a stack-based language. Input also contains a script. Then an input could spend an output if a combined script made of inputs' and then outputs' could be executed and results in non-zero top stack item.
%
%[TODO: example]

\subsection{Boxes, Propositions and Proofs}

Abstracting the Bitcoin-like model, a minimal state could be represented as a set of \textit{closed boxes} of size \(n_S\). Each box has a value associated with it. Say, a transaction opens \(n_k\) boxes and also creates \(n_b\) new closed boxes, then the resulting state set has the size of \(n_S-n_k+n_b\) after applying the transaction. 

How can we open a box? 
We can use a Script-like language as in Bitcoin, or we simply have public-keys instead of addresses and signatures instead of scripts. To describe these approaches as well as many others, we say a box is protected by a \textit{proposition} of some kind, and in order to open it, a \textit{proof} of the same kind must be provided. %There are some tricky details we will discuss further.
Intuitively, a proposition is an NP statement and a proof, its witness.

A box can have some additional data inside. For example, it can contain a domain record or a certificate. The contents of closed boxes are relevant to every node. However, nodes can forget about boxes that have been opened.

\subsection{Namecoin}

Namecoin is a descendant of Bitcoin which in addition to token transfers, introduces \textit{name} $\rightarrow$ \textit{value} storage. In general, values could be arbitrary, but there are few  standard namespaces with predefined semantics for domains and identities.

Consider a transaction that contains a box with {\em name-register} command specifying a \textit{name} $\rightarrow$ \textit{value} correspondence. Such a box has zero value and is associated with a public key \(pk\). A fee may be required to insert a box into the minimal state. The box lives in the minimal state for some period of time after which it is considered expired and discarded. It is possible to renew or transfer ownership to a different public key by publishing a \textit{name-update} box, which replaces the original box in the minimal state.

This basic design has a critical flaw. If a miner processing a name-register box finds that particular name interesting or worth snatching, nothing prevents him from grabbing that name before it goes into the blockchain. The miner could simply refuse to include original box and put its own one for the same name. This is an example of a
\textit{frontrunning attack}, when an original transaction is suppressed by another one issued by an attacker. In order to avoid frontrunning attacks, Namecoin has \textit{name-new} command to announce the intention to register a name by first registering a cryptographic commitment to the name (without revealing the name). That way, a miner cannot know if the domain name intended to be registered is interesting or not. Later on the name-register command simply opens the commitment. The same attack cannot be applied because the public key of the name-register and name-new must match. An empirical analysis of Namecoin is given in~\cite{kalodner2015empirical}.


\subsection{Nxt and Ethereum}	

Bitcoin has the concept of immutable UTXOs and a Script-based structure for validating public-key and signatures. We can also conceive of a simpler model model where the ledger maps public keys to their balances and transactions to Satoshis transferred between the accounts. We can also have hard-wired semantics that validate public-key and signatures instead of Script code.

Nxt and Ethereum are two examples of such designs, which use the term {\em account} to refer to a public-key. A transaction transfers tokens from one account to another and needs to be signed by the sender. For such a system, the minimal state is a table holding a correspondence between accounts and their balances.

This simple explanation, however, has a critical flaw. Suppose Alice has 50 tokens at some time. She issues a signed transaction to pay 5 tokens to Bob. A node will find this valid, and therefore, applicable. After the application Alice has 45 tokens. However, Bob or anyone else can now {\em replay} the same transaction again and again till Alice's account is empty. Our minimal state representation seems to be flawed.

Ethereum solves the problem by modifying minimal state representation with a ``nonce'' value added to every account~(Nxt solution is different and not covered in this document). That is, the minimal state is no longer just a (public key $\rightarrow$ balance) correspondence, but a (public key $\rightarrow$ (nonce, balance)) one. Each transaction contains some nonce value \(txnonce\) describing which box to open. A transaction is valid only if \(txnonce = nonce + 1\). After applying the transaction the old box is destroyed and a new box with the incremented nonce and update balance is created. Thus, even Etherium has the idea of immutable boxes.

Unlike Bitcoin, Ethereum requires a strict order of transactions issued by an account. In Bitcoin, transactions could be applied in any order as long as they are spending non-overlapping sets of outputs and an input of one transaction does not spend the output of another. In Ethereum, the order is set by nonces. 



\subsection{Transactional Metadata}

Suppose we have a sequence $s$ of objects serializable to byte arrays and want to \textit{authenticate} their concatenated binary representation efficiently. That is, we want to calculate a fixed-sized value (the {\em root}) from $s$ such that even a single bit change in the representation always results in a change of the root. Furthermore, we require {\em collision-resistance}. That is, it must be computationally hard to generate different sequences resulting in the same root. Any data structure that supports this is called an {\em authenticated data structure}, an example of which is a Merkle tree.

Along with transactions, we could put some aggregated data about them. For example, in Bitcoin, the root hash of the Merkle tree of transactions of that block is also put into the block. That way it is possible for nodes to exchange only {\em block-headers} and not the full blocks. A \textit{block-header} is a block without its transactions. 
By including transaction root hash into the block-header it is possible to have it spread around a network and be sure that it is impossible to show transactions other than what were included when the root was computed. 


\subsection{Transactional Layer Generalization}

\knote{Sounds unfinished, we need to say this is just about transactions and state.}

Let us summarize the common features of various blockchains. At the core is a {\em minimal state} that encodes some shared information between nodes. The minimal state is modified via {\em transactions}, which contain instructions for modifying the minimal state. This idea is broken down into several components as follows:

\begin{enumerate}
\item{\textbf{A Proposition and A Proof.}}
In every imaginable blockchain we have objects to be protected by secret owners. The property of `being protected' is mapped to a proposition (an NP statement), and objects can be modified or destroyed only by presenting the corresponding proof of the proposition (a witness of the NP statement). There are several instantiations; Bitcoin scripts or digital signatures. 
\item{\textbf{Box Structure.}}
There is an atomic element in the minimal state which we call a \textit{box} and captures the objects of the above definition. A box is protected by a proposition. It is possible to modify it or destroy it by showing a proof satisfying the proposition. 
\item{\textbf{Minimal State.}}
Minimal state is a most compact structure giving an ability to verify a transaction. Minimal state is a set of closed boxes. 
\item{\textbf{Transaction And Transactional Language.}}
Transaction is the smallest possible atomic state modifier. A transaction will be verified against the minimal state in a deterministic fashion~(so given a state and a transaction, two nodes will always output the same result). If a transaction is valid against a state it could modify the state. Validation and application rules are blockchain specific~(Ethereum even brings quasi Turing completeness here).
\item{\textbf{Block.}}
Most blockchain systems don't update the minimal state arbitrarily. Rather they do it in batches by packing several transactions into a block and then applying the block. 
Most blocks also have some authenticating value for the transactions included therein. Thus, it is possible to use block-headers instead of full blocks in many scenarios. % in order to reduce load.
\end{enumerate}


%[TODO: wallet section?]

\section{Consensus}

We know (from proposition~\ref{prop1}) that if the same sequence of blocks is applied to the same genesis state by two nodes then they will arrive at the same minimal state. This is exactly what we want to achieve. So how we ensure that the same sequence of blocks are applied by each node? This is the consensus problem.

Firstly note that we can only hope to achieve this for nodes that follow the same protocol strictly. We refer to such nodes as \textit{honest} and the method to obtain consensus as the \textit{consensus protocol}. Nodes not following the protocol are called \textit{byzantine} nodes and could be doing so if they are corrupted by an attacker or due to software bugs, hardware crashes etc. 

Computer scientists have been studying consensus protocols extensively since early 1980s. A lot of interesting results were obtained. For example, it is impossible to achieve consensus using a deterministic procedure for a set of nodes if they are exchanging messages asynchronously and a single process could fail (Fischer-Lynch-Paterson theorem~\cite{fischer1985impossibility}). 
Randomized consensus in open networks with unknown number of participants is a hard problem. %pretty new and also a very hard question. 


For blockchain consensus protocols, we can state the following properties~\cite{Garay2015}:

\begin{enumerate}
\item{Consistency (or Prefix immutability)} - for two honest nodes the probability to have different prefixes after cutting last \(k\) blocks should go down exponentially with \(k\).
\item{Chain Quality} - a party having \(x\%\) of voting power should produce no more than \(\alpha x \%\) blocks in a long run, where \(\alpha\) $\geq 1$ is a function of \(x\).
\item{Chain Growth} - over time, the blockchain should always grow. Thus, as long there is an honest majority in the network (in terms of computing power, not number of nodes), a transaction sent by a honest node should eventually make it to the blockchain.
\end{enumerate}


\subsection{Proof-of-Work}

Proof-of-Work (PoW) as a consensus protocol was used for the first time in Bitcoin, as described in Nakamoto's seminal paper~\cite{Nakamoto2008}.
However, the concept of PoW came before bitcoin in the form of Hashcash~\cite{back2002hashcash}.
PoW forms the core of Bitcoin, Ethereum and many other cryptocurrencies. The basic idea here is to force miners to iterate over some function with a small probability of success per iteration. A successful result gives the right to generate a block. The probability is adjusted automatically via \textit{difficulty} parameter \(D\). 

In case of Bitcoin, the function is just a hash function. The input to the hash is a header comprising of a nonce, the current difficulty target, the root of the Merkle tree of transaction hashes (as an authenticator of the transactions included), and the hash of the previous block. This ensures that in order to replace a particular block the attacker has to replace all its descendants. As some amount of work is needed to generate each block, the amount of work needed to defeat an honest chain increases exponentially with depth.

With PoW, it is impossible to make a false claim of successful block generation. Such a claim is easily falsifiable, as calling the hash function is very cheap. Thus, PoW also offers protection against Sybil attacks where an attacker creates a large number of fake identities~\cite{douceur2002sybil}.

\subsection{Proof-of-Stake}

PoW has some disadvantages. Firstly, a lot of resources are needed to obtain a sufficient guarantee of security. Secondly, during early days, a PoW currency can be destroyed by an attacker possessing sufficient computing power. 

The question then is: can we have protection against Sybil attacks without spending computational resources? 
The simplest way to achieve this is to use cryptocurrency tokens themselves as anti-Sybil tools. 
That is, the probability to generate a block is proportional to the amount of cryptocurrency a node holds. This is called Proof-of-Stake (PoS)~\cite{kiayias2016provably,king2012ppcoin}.

\subsection{Proof-of-Burn}

{\em Proof-of-burn} is a method for distributed consensus and an alternative to PoW and PoS. It can also be used for bootstrapping one cryptocurrency off of another.
The idea is that miners should show proof that they destroyed some coins - that is, sent them to a verifiably unspendable address~\cite{stewart2012proof}. This is expensive from their individual point of view, just like proof of work; but it consumes no resources other than the burned underlying asset. However, to date, all proof of burn cryptocurrencies work by burning PoW-mined cryptocurrencies, so the underlying mechanism remains PoW.\footnote{https://en.bitcoin.it/wiki/Proof\_of\_burn}

\subsection{Transaction History}

Earlier we talked about a blockchain. However, in all the global networks, collisions are possible (i.e., two blocks referencing the same parent).\footnote{To prevent this, we would need to have a global lock or synchronous rounds and then some kind of leader election.} So in reality, it is a \text{blocktree} that exists.

%[TODO: a blocktree picture]

In most cases, the existence of blocktree is ignored and a node stores only one valid chain. For multiple contenders, each blockchain has some score (e.g., cumulative difficulty). If a chain with higher score is found, the older is discarded. In these cases, a node sees a blocktree only during switching from one branch of it to another. 

One might ask that instead of discarding the lower score chains, why don't we store them as additional PoW enhancing the persistence of some common ancestor from the main chain. There are some proposals that consider this and explicitly use a blocktree. For example, in GHOST scoring function~\cite{sompolinsky2015secure} a chain with heaviest tree wins. 


\subsection{Full Node View}
\label{fullnodeview}

A full node is a node which holds at least some state that is enough to check whether an arbitrary transaction is valid against it, and so applicable to it, or not. We have defined such a state,  \textit{minimal state}, above. Nodes also store the history from which the minimal states have been generated. In addition, a full node contains two more entities: (1) \textit{Memory pool} containing transactions not yet included into blocks~(and there is no guarantee of inclusion for them), and (2) \textit{Vault} containing some node-specific information from the log. For example, it could contain values encoded in some or all OP\_RETURN instructions, or all the transactions for specific addresses. The well-known example of vault is a \textit{wallet} which contains private keys as well as transaction associated with them.

With these four entities defined, we can explicitly state a node view type now: node-view $= \langle $history, minimal-state, vault, memory-pool$\rangle$.

The quadruple could be modified by applying an offchain transaction or a block coming from local code
%(user issuing a transaction to a local node, mining software generating a block) 
or from a remote peer. We can state some rules of node view  modification even for the most abstract definition given:

\begin{itemize}
\item An offchain transaction modifies vault and memory pool. Atomicity in this update is not critical.

\item For a persistent node view modifier, atomicity of updates is strictly needed. If history is producing rollback side-effect, other parts must handle it properly before applying an update. This sounds trivial, but in fact many years have been spent uncovering bugs related to inconsistency and read-when-update issues.
\end{itemize}


%[TODO: pseudocode? or Scala code in Scorex counter-part?]



\section{Complications and Alternative Designs}
\label{alternatives}
In addition to the systems described in this chapter as well as many other systems used around, there are many designs existing only on paper. In this section we quickly observe some proposals. The goal of Scorex is to help to get them from papers to prototype implementations. 


The various alternative designs are proposed to address some of the problems with Bitcoin explained below:
\begin{enumerate}
	\item Storage scalability: In Bitcoin, every node must store the entire blockchain (currently over 10 GB). This is a bottleneck as the blockchain becomes older. Proposals have been presented that allow pruning of the blockchain under certain assumptions. 
	\item Memory usage: The UTXO set is something that needs to be kept in memory for fast validation. This set is currently about 1.5GB.
	\item Rational behavior: If nodes behave rationally, they will not store the blockchain. Rather they will store only the current UTXO set (SPV nodes go even further and store only those UTXOs that they are interested in). In the long run, this could lead to {\em tragedy of the commons}, where no one has the complete blockchain. In fact, all rational nodes follow SPV.
	\item Privacy: While Bitcoin uses pseudo-random looking addresses for privacy, some information is inherently leaked. For instance, we can know all the addresses that a given satoshi has traveled to since its creation. Additionally, we can often infer that certain addresses belong to the same entity.
	\item Delay in confirmations: Bitcoin has an average confirmation time of 10 minutes. However, if the size of the unconfirmed transactions is higher than the maximum network throughput (1 MB/10 minutes), then a transaction can remain unconfirmed for tens of hours. Additionally, since PoW is a randomized process, there is no guarantee that a block will be mined soon, even if the transaction fee is very high.
	\item Transaction throughput: As mentioned in the previous point, the maximum block size is 1 MB. This roughly translates to about an average of 144 MB of data added to the blockchain per day if all blocks are full. Assuming a transaction size of the about 224 bytes (the minimum), we get a maximum of 28086 transactions/hour, which may become a bottleneck. %far less than centralized payment systems such as VISA.
	\item Validation-less Mining: Due to latency in network and the large size of blocks, many miners and mining pools do not validate headers. In other words, they start finding the solution using the Merkle root of transaction hashes without validating the batch of transaction themselves (which could be around 1 MB currently). Often this results in a split, where some clients create a Merkle root incorrectly (either deliberately or by accident) such as the softfork due to BIP66 in July 2015\footnote{https://en.bitcoin.it/wiki/Softfork\#2015\_BIP66\_Blockchain\_Fork}, where certain miners were creating invalid blocks and others were building a chain on top of those.
	\item Fully prunable outputs: In Bitcoin, certain outputs cannot be provably spent (such as those with value 0 -- those created using OP\_RETURN\footnote{https://en.bitcoin.it/wiki/OP\_RETURN}) or sent to an output that cannot be provably spent\footnote{Example: https://blockchain.info/address/1CounterpartyXXXXXXXXXXXXXXXUWLpVr}. Such unspent outputs serve no meaningful purpose to Bitcoin nodes and can be pruned from their UTXO sets. 
\end{enumerate}


%[TODO: ZCash]

%[TODO: fully prunable outputs]

\subsection{SPV}

SPV (Simple Payment Verification) was a protocol proposed in the original Bitcoin paper as an alternative to the full-node protocol~\cite{Nakamoto2008}. It is designed to enable lightweight clients that can sync in minutes instead of days and store only a fraction of the information (few MBs) compared to a full node (several GBs).
In this method, a node only verifies headers from the genesis block onwards and validates only the last few full blocks (enough for rollback). 
The key idea in SPV is that the unique blockchain is identified not by its height (the number of blocks before it since the genesis block) but rather its depth (the number of blocks mined since a client booted up). 

Implementations of SPV nodes use a protocol extension called {\em Bloom filters}, described in Bitcoin Improvement Proposal (BIP) \#37. They use headers for blocks prior to their wallet's birth timestamp, and request filtered blocks for the rest by sending a bloom filter to its peers. The peers then send the relevant transactions for blocks along with the Merkle paths.\footnote{http://bitcoin.stackexchange.com/a/11721/2075}

\subsection{Rollerchain}

Rollerchain~\cite{DBLP:journals/corr/ChepurnoyLO16} (RC) is a proposal aimed to (1) reduce storage and
(2) incentivizing nodes to store some number of last blocks and also state snapshots~(minimal states in a standard
representation). There are two main parameters of the scheme, $n$ and $k$. The parameter $n$ specifies number of blocks~(
and also state snapshots) a network aims to store collectively~(so a sufficiently large network stores last $n$ full
blocks and also state snapshots), while each miner is storing $k$ state snapshots. To create a successful PoW, nodes
must present proofs for the $k$ state snapshots determined via a hash of their public key and the current block index.
Since the index changes with each block, there is a {\em sliding window} of snapshots from which a node must store a few.
The index of stored snapshots also slides with the window and nodes must recompute this at every new block. Consequently,
nodes are implicitly forced to store all the blocks till the depth of their earliest snapshot.
In RC, the block header contains a Merkle root hash of the minimal state that will be obtained after the block is
applied. Additionally, the Merkle root hash of the transactions and a Proof of Storage of snapshots is also present
in the header.

\subsection{GHOST}

The GHOST (Greedy Heaviest-Observed Sub-Tree) protocol is designed for blockchains with very fast block times~\cite{cryptoeprint:2013:881}. As the network becomes less synchronized and blocks are generated fast, a significant amount of PoW will not make it into the main chain due to orphans. This leads to reduced security. The GHOST proposal makes use of the additional orphaned blocks to strengthen the network instead of rejecting them. Thus, two different branches will be compared not just by length but how `heavy' they are in terms of PoW. A GHOST protocol has various mechanisms for rewarding orphans. Etherium is one example that follows the GHOST strategy.

\subsection{Bitcoin-NG}

Bitcoin-NG~\cite{eyal2016bitcoin} (or simply NG) was proposed to solve two main issues in Bitcoin:
\begin{enumerate}
	\item {\em Reduce confirmation time:} Current Bitcoin transactions require an average of 10 minutes for the first confirmation. In NG, the first confirmation is very fast (within 30 seconds; roughly the time to cross the network). 
	\item {\em Increase transaction processing bandwidth:} Furthermore, much more transactions can be inserted into the blockchain between two successive PoWs. This is only limited by bandwidth and processing constraints of miners.
\end{enumerate}

While Bitcoin is retrospective based (i.e., the PoW captures transactions created {\em before} the PoW was formed), NG is forward-looking in that the PoW enables a miner (aka {\em leader} in NG) to confirm transactions in the future. 

The main idea in NG is to remove the link between transaction confirmations and the {\em leader selection}. A leader is essentially someone whose PoW is accepted. In NG, the leader is still selected based on PoW but the block selecting the leader (the {\em key-block}) does not contain transactions. Rather the currently selected leader (i.e., the public key) has the sole power to decide the transactions for the blockchain in several {\em micro-blocks} until the next leader is selected. The leader adds micro-blocks without much delay, ensuring that transactions get confirmed (with one PoW) very quickly. Furthermore, there is no limit to the number of micro-blocks that can be inserted, ensuring that the throughput of the network is high.
We summarize the main features of NG:
\begin{enumerate}
	\item Two types of blocks: {\em key blocks} that contain the PoW, a reference to the previous block and a coinbase (reward) transaction but no other transactions. The key block additionally gives the miner the ability to create several {\em micro-blocks} containing one or more transactions until the next PoW (i.e., key-block is found). Miners only compete for key-blocks.
	\item The fee is split into a 40-60 ratio, where 40\% goes to the owner of the current PoW and the rest to the next PoW. This is to dissuade attacks where miners try to fork the blockchain for stealing the previous block's transaction fee.
\end{enumerate}

\subsection{ByzCoin}

ByzCoin~\cite{kokorisposter} builds on the ideas of NG of separating the confirmations and leader selection. There are several differences from NG discussed below:
\begin{enumerate}
	\item Two separate blockchains: The key blocks and micro-blocks are part of two different chains. A key-block links to the previous key-block (the {\em main chain}) and the micro-blocks form a {\em secondary chain} and also link to the corresponding key-block in the main chain. 
	\item Different process for mining micro-blocks: While key-blocks are mined in a similar fashion to NG, the micro-blocks are mined using a Practical Byzantine Fault Tolerant (PBFT) protocol~\cite{castro1999practical} run by the leader. The group of members who participate (the {\em replicas}) are selected from a sliding window of miners who contributed a PoW in the last time-slice (say 24 hours). The amount of voting power held by a miner is proportional to the amount of blocks contributed in that window.
	\item Interactive consensus protocol: The replicas perform an interactive protocol using PBFT and combined signatures to obtain consensus on the micro-blocks to insert.
\end{enumerate}

The key difference with NG is that while a transaction is instantly confirmed in NG, it is not permanent in the case of dishonest miners because there is no control over how a miner generates micro-blocks. ByzCoin adds a level of consensus even for micro-blocks so the chance of those rolling back is negligible compared to NG.

\subsection{One-Way Aggregate Signatures}

One-Way Aggregate Signatures (OWAS), also called {\em composite signatures}, is an approach proposed in~\cite{saxena2014increasing} for enhancing anonymity. OWAS are based on another primitive called Aggregate Signatures~\cite{boneh2003aggregate}. In this, several individual signatures can be combined into one short object -- the aggregate signature -- that can be verified against all the (public-key, message) pairs of the individual signatures and the verification yields true if and only if all the individual (public-key, message, signature) triplets verified correctly before aggregation. This itself has the advantage of reducing the sizes of very large transactions by compacting the signature. 

Aggregate signatures, however, can be tweaked so that the aggregation process becomes one-way; given just the aggregate signature, it is very hard to extract the constituents. This gives someone the ability to aggregate two unrelated signatures so that no one can later separate them. OWAS use this idea to combine a signed input (which releases Satoshis from an address) with an unrelated output (which consumes those Satoshis) such that at the time of signing, the holder of the Satoshis may not even know who the recipient is. For instance, the sender could simply sign the input releasing the Satoshis and hand it over to some (possibly unknown) receiver over a private channel without specifying in the signature where the Satoshis should go. This is equivalent to handing out a ``blank cheque''. The receiver can then add an arbitrary signature sending those Satoshis to some address. This can be further combined with more such transactions over a private network before sending the large transaction to the public network. There can be various mechanisms of doing the private computation (such as sending it to an aggregator).


\section{ZeroCash}

ZeroCash (ZCash)~\cite{sasson2014zerocash} is a blockchain based protocol designed for privacy. Since the data in the Bitcoin blockchain is public, true anonymity is not present.
 ZCash can be considered an extension of ZeroCoin (ZCoin)~\cite{miers2013zerocoin}, an earlier proposal. In order to describe ZCash, we will first describe ZCoin.

Assume that all coins to be obfuscated are of a single denomination, say 1 BTC. ZCoin has its own currency (say Z), such that 1 Z = 1 BTC. There is a pool of obfuscated Z coins called {\em Zero-Pool}. Alice wants to anonymize her Bitcoin represented by serial number $c_A$. In order to do that, she begins by exchanging $c_A$ with an equivalent Z coin as follows. She generates a secret serial number $s_A$ and another secret $r_A$. Then she creates a commitment $z_A$ to $s_A$ using $r_A$ as randomness. That is, $z_A=$ COMM$_{r_A}(s_A)$, which is the Z coin Alice will use in exchange for $c_A$. All such exchanged coins are automatically added to the Zero-Pool. The commitment is computationally binding and perfectly hiding so no knowledge of $s_A$ or $r_A$ is leaked from $z_A$. Later on Alice will take back her $z_A$ using a transaction $t_A$, which is then automatically converted to 1 BTC. For anonymity, an adversary should not be able to link $t_A$ to $z_A$. This is achieved using Non-interactive Zero-Knowledge Proofs (NIZKs).

Alice creates a spend by revealing $s_A$ (but not $r_A$) and creates a NIZK proof of the NP statement ``I know $r$ such that $z=\text{COMM}_r(s_A)$ and $z \in \text{Zero-Pool}$''. The process of creating a commitment and revealing only one input (but never opening them completely) may seem counter-intuitive, but this in fact makes the statement provable by efficient NIZKs, because the circuit for computing the commitment can be efficiently coded into an NP language. The spend could have been done even without revealing $s_A$. However, this is needed for the next property -- security -- so that Alice should not be able to spend $z_A$ twice. This is achieved by keeping track of spent $s_A$s in a public ledger, kept by each client. 

ZCash is an extension of ZCoin with the following differences:
\begin{enumerate}
	\item In ZCash, the coins are minted in the protocol itself rather than exchanged with Bitcoins. This allows people to transact directly in ZCash rather than using it as an add-on to Bitcoin or another currency. In other words, the spent coins also generate Z coins.
	\item The statement  ``I know $r$ such that $z=\text{COMM}_r(s_A)$ and $z \in \text{Zero-Pool}$'' is replaced by the NP statement  ``I know $r$ such that $z =$ COMM$_r(s_A)$ and $z$ is a leaf node of a Merkle tree with root hash $M$'', where $M$ is the root hash of the Merkle tree of Z coins in the Zero-Pool. This makes the statements much shorter. The value $s_A$ is revealed in order to prevent double spends as in ZCoin.

	\item ZCash uses a variant of NIZKs called zkSNARKs (succinct non-interactive arguments of knowledge)~\cite{cryptoeprint:2013:879,ben2013snarks}. A zkSNARK is essentially a NIZK with the 
	proof size and verification-time O(1), and secure against only a computationally bound adversary. Note that the zkSNARKs used in the ZeroCash paper~\cite{sasson2014zerocash} require pre-computation. %We don't know efficient zkSNARKs without pre-computation.

	\item ZCash allows coins of arbitrary denominations instead of 1 BTC as in ZCoin. This is done by introducing a {\em pour} operation that uses a bunch of Z coins and creates new ones without revealing the amount in either the destroyed or created ones. The only thing revealed is that the sum of inputs is $\leq$ sum of outputs. This is done by appropriately modifying the Z coins and proving the corresponding NP statement using zkSNARKs. \end{enumerate}

\paragraph{Scalability:} We can see that both ZCoin and ZCash have two scalability issues: (1) The Zero-Pool always grows as we cannot determine which of the Z coins have been spent (for anonymity). (2) The spent set always grows as we need to keep track of double spends. Unlike Bitcoin, which uses spends only for bootstrapping and stores only unspent outputs, ZCoin must store both the spent and unspent outputs. The unspent outputs is simply the Zero-Pool.

%However, 
\section{Conclusion}

In this chapter we discussed various issues and concepts of a blockchain system such as Bitcoin. We also briefly described various Bitcoin-like systems that can be implemented with Scorex. We summarize this chapter below:

Scorex generalizes the concept of the UTXO Set in Bitcoin to a {\em Minimal State}, the minimum amount of information needed by any node to validate transactions. Each Bitcoin UTXO is equivalent to a locked {\em Box} that can be opened with a key. The lock can be considered a {\em proposition} and the key a {\em proof}. The proof in Bitcoin is simply the signature under the input public key and the proposition is a statement that validates the signature.

Some of the alternate blockchain designs we described were:

\begin{enumerate}
	\item {\em Consensus models:} Proof-of-Work, Proof-of-Stake, Proof-of-Burn.
	\item {\em Chain selection:} Longest chain, highest cumulative difficulty, heaviest branch of a blocktree (GHOST).
	\item {\em Application:} Currency (Bitcoin), Domain names (Namecoin), Smart contracts (Ethereum).
	\item {\em Fast confirmations and larger throughput:} Bitcoin-NG, ByzCoin.
	\item {\em Lightweight clients and reduced storage:} SVP clients, Rollerchain.
	\item {\em Anonymity:} ZeroCash, ZeroCoin, Composite Signatures.
\end{enumerate}




\chapter{Scorex}           
\label{impl}

\section{Introduction}     

Scorex is a modular blockchain core framework. It supports the definitions given in the previous chapter in the form of Scala code.
In order to build something using scorex, all a developer must do is provide concrete implementations for all the abstract
types, possibly reusing code previously written. Although Scorex is designed to build a full-node implementation, other security models such as SPV are possible.

\subsection{Scala Language}

Scala is functional, modular and also object-oriented language. There are several reasons to choose this language:
\begin{enumerate}
	\item Scala runs on the JVM which allows it to be cross-platform.
	\item Scala inter-operates seamlessly with Java.
	\item Scala is fully functional and consequently allows compact and more readable code.
	\item Scala has powerful constructs for concurrency.
	\item Scala has powerful type system. Scorex is using typing features of the language extensively.
\end{enumerate}

For a good introduction into the Scala language, please refer to~\cite{odersky2008programming}.

\section{A Node View And Its Modification}

The goal of a fullnode node is to compute the same \textit{minimal state}~(see Section~\ref{min-state}) as other honest nodes for some version $h$. It also holds local information derived from the history and state, which is specific to its user. To accomplish these goals, described in Section~\ref{fullnodeview}, the node has a local view of the world comprising of four entities:

\(node\_view = \langle history, minimal\_state, vault, memory\_pool \rangle \) \\

A \textit{node view holder} is a component that manages and updates this view when it receives either an offchain object (such as an offchain transaction), or an on-chain object~(such as a block (header), a key-block/micro-block in Bitcoin-NG, a blockheader/fullblock/state-snapshot in RollerChain). We refer to an object of the latter kind as \textit{persistent node view modifier}. Node view and its holder have following type signatures:

\begin{lstlisting}
trait NodeViewHolder[P <: Proposition, TX <: Transaction[P],
	PMOD <: PersistentNodeViewModifier[P, TX]] extends Actor {

  type SI <: SyncInfo
  type HIS <: History[P, TX, PMOD, SI, HIS]
  type MS <: MinimalState[P, _, TX, PMOD, MS]
  type VL <: Vault[P, TX, PMOD, VL]
  type MP <: MemoryPool[TX, MP]

  type NodeView = (HIS, MS, VL, MP)
\end{lstlisting}

In the snippet, the types and traits are modules possibly parametrized with other modules~(including themselves\footnote{
	This is called \textit{F-bounded polymorphism~\cite{f-bound}} and is widely used in Scorex.}). A concrete parameter has to be derived from an upper-bound abstract interface~(for example, concrete minimal state representation has to be derived from the \textit{MinimalState} trait).

\subsection{Node View Modifiers}

A node view can be modified by applying a \textit{node view modifier} to it. There are two kinds of node modifiers: 

\begin{enumerate}
	\item The first is an \textit{offchain transaction}, which is not part of any history log, and will be processed by using only a memory pool and a wallet. 
	\item The second type is a hierarchy of \textit{persistent node view modifiers}. In Bitcoin, for example, the hierarchy contains the Proof-of-Work blocks. In Rollerchain, we have three different kinds of objects in the hierarchy: a blockheader, a state snapshot and a fullblock; with different validation and application rules.

\end{enumerate}
All modifiers have identifiers of the same length~(to be set via \textit{application.conf} file with a default value of 32 bytes). We argue that this assumption is reasonable because usually the identifier is the output of a single hash function.  

A concrete implementation of a modifier must provide: (1) A type-identifer for the type of modifier, (2) An identifier for the modifier itself, and (3) A method giving a binary representation of the identifier:

\begin{lstlisting}
trait NodeViewModifier extends BytesSerializable with JsonSerializable {
  ...

  val modifierTypeId: ModifierTypeId

  def id: ModifierId

  lazy val bytes: Array[Byte] = ...
}
\end{lstlisting}

Log elements in the persistent node view modifiers hierarchy refer to a parent. A persistent modifier can also contain transactions~(but that is optional): 

\begin{lstlisting}
trait PersistentNodeViewModifier[P <: Proposition, 
         TX <: Transaction[P]] extends NodeViewModifier {

  def parentId: ModifierId

  // with Dotty it would be Seq[TX] | Nothing
  def transactions: Option[Seq[TX]]
}
\end{lstlisting}


\section{The State Design}

\subsection{A Minimal State}
A minimal state is a data structure which deterministically defines whether an arbitrary transaction is valid and so
applicable to it or not. See section~\ref{min-state} for details. The signature of a \textit{MinimalState} is

\begin{lstlisting}
trait MinimalState[
    P <: Proposition,
    BX <: Box[P],
    TX <: Transaction[P],
    M <: PersistentNodeViewModifier[P, TX],
    MS <: MinimalState[P, BX, TX, M, MS]
] extends NodeViewComponent{
  self: MS =>  
  ...
\end{lstlisting}

Per definition, we define methods to validate a transaction: 

\begin{lstlisting}
  def validate(transaction: TX): Try[Unit]

  def isValid(tx: TX): Boolean = validate(tx).isSuccess
\end{lstlisting}

The trait also has methods to get a closed box~(see section~\ref{sect_box}), to apply a persistent modifier, and to roll back to a previous version: 

\begin{lstlisting}
  def closedBox(boxId: Array[Byte]): Option[BX]
  def applyModifier(mod: M): Try[MS]
  def rollbackTo(version: VersionTag): Try[MS]
\end{lstlisting}


\subsection{Propositions and Proofs}

Blockchain can be thought as a mechanism to control access to some protected objects (such as transaction outputs). An object is protected by a {\em proposition} and a {\em proof} for that proposition is needed in order to modify the object.

A proposition is a very abstract concept. The only property we require from it is to be serialized into bytes. In form of Scala code it is described as: 	

\small{
\begin{lstlisting}
trait Proposition extends BytesSerializable
\end{lstlisting}
}
In most cases, a proposition requires a proof of knowledge of a secret to be provided in a non-interactive zero-knowledge form. For example, in most of popular signature schemes a digital signature is a non-interactive zero-knowledge proof of a private key knowledge. Scorex has a basic entity for that

\begin{lstlisting}
trait ProofOfKnowledgeProposition[S <: Secret] extends Proposition
\end{lstlisting}

A proof is an object which could satisfy a proposition given an additional input, namely a \textit{message}(e.g. transaction bytes). As well as a proposition, a proof could be serialized into bytes. 

\begin{lstlisting}
trait Proof[P <: Proposition] extends BytesSerializable {
  def isValid(proposition: P, message: Array[Byte]): Boolean
  ...
}
\end{lstlisting}

For a \textit{ProofOfKnowledgeProposition} corresponding abstract proof is provided:

\begin{lstlisting}
trait ProofOfKnowledge[S <: Secret, P <: ProofOfKnowledgeProposition[S]]
	extends Proof[P]
\end{lstlisting}

\subsection{Box}
\label{sect_box}

A box is a minimal state element. An unspent output in Bitcoin is a box. An account in certain state in Nxt or Ethereum is also a box. Basically, a box is about some amount of tokens associated with it and also some proposition which protects a box from being spent by anyone but a party~(or parties) knowing how to satisfy the proposition. Thus the basic abstraction is as follows:

\begin{lstlisting}
trait Box[P <: Proposition] extends BytesSerializable {
  type Amount = Long

  val value: Amount
  val proposition: P

  val id: Array[Byte]
}
\end{lstlisting}


\subsection{A History}

At the very basic level, Scorex does not have the notion of blockchain. This is done in order to support blocktrees and other non-linear structures. So Scorex has an abstract concept of \textit{history} defined by the trait \textit{History}.

\begin{lstlisting}
trait History[P <: Proposition,
	TX <: Transaction[P],
	PM <: PersistentNodeViewModifier[P, TX],
	SI <: SyncInfo,
	HT <: History[P, TX, PM, SI, HT]] extends NodeViewComponent {
		def isEmpty: Boolean	

	type ModifierIds = Seq[(ModifierTypeId, ModifierId)]	

  	def applicable(modifier: PM): Boolean = 
  		openSurfaceIds().exists(_ sameElements modifier.parentId)

  	def modifierById(modifierId: ModifierId): Option[PM]	

  	def append(modifier: PM): Try[(HT, Option[RollbackTo[PM]])]

  	def openSurfaceIds(): Seq[ModifierId]

  	def continuationIds(from: ModifierIds, size: Int): Option[ModifierIds]

  	def syncInfo(answer: Boolean): SI

  	def compare(other: SI): HistoryComparisonResult.Value	
  }
\end{lstlisting}

The trait contains no mention of block or blockchain. In principle, it supports non-linear structures and many object types to make the log. 

A node continuosly tries to get alternative~(and possibly better) histories from the network around and also feed nodes with less developed history with locally stored modifiers. To provide an information on how much local history is developed, there is an abstract type \textit{SyncInfo} mentioned in the type signature of the \textit{History} trait. We assume that \textit{SyncInfo} at least provides information about \textit{starting points}, persistent modifier identifiers a node sends in order to help other node to understand its synchronization status. Usually it is about last block identifiers. 

\begin{lstlisting}
trait SyncInfo extends BytesSerializable {
  def answer: Boolean
  def startingPoints: History.ModifierIds
}
\end{lstlisting}

Function \textit{compare} is checking a \textit{SyncInfo} instance got from another party and returns one of \textit{HistoryComparisonResult} values provided below: 

\begin{lstlisting}
object HistoryComparisonResult extends Enumeration {
  val Equal = Value(1)
  val Younger = Value(2)
  val Older = Value(3)
  val Nonsense = Value(4)
}
\end{lstlisting}

If another peer is holding the same history, then \textit{compare} should return \textit{Equal}. If other peer's history is more developed than local then \textit{compare} returns \textit{Older}, if less developed - \textit{Younger}. If from \textit{SyncInfo} it is not possible to get other peer's hystory status, \textit{compare} should return \textit{Nonsense}. 


Function \textit{openSurfaceIds} returns last block if a history is linear, otherwise it returns last blocks from a blocktree etc. That is why it is returning a sequence of modifier identifiers~(Seq[ModifierId]). The function \textit{continuationIds} returns modifiers after given. Again, if the history is linear, \textit{from} parameter is about just 1-element sequence~(we can not easily enforce that with the Scala type system, so an implementation should check that in runtime), otherwise, from could be about elements of different chains. The function returns modifiers after provided if found, otherwise \textit{None}. 

Function \textit{append} is trying to extend the history with a modifier given. No any attempt could be successful~(for example, if history does not contain modifier's parent, or modifier is not valid, append must aborts). There is an optional side-effect of an application to be passed to other components of the node. That is a rollback, which provides information about a last modifier id \textit{to} after the rollback~(and before the application), sequence of modifier thrown away and also a sequence of blocks to be applied~(after \textit{to}):

\begin{lstlisting}
case class RollbackTo[PM <: PersistentNodeViewModifier[_, _]]
	(to: ModifierId, thrown: Seq[PM], applied: Seq[PM])
\end{lstlisting}


\subsection{A Vault}

A \textit{vault} is a storage for node-specific information. Usually this is about wallet functionality. The information is to be obtained via scanning whether an offchain transaction or a persistent modifier. A rollback is surely possible. Thus the interface of a vault is as follows.  

\begin{lstlisting}
trait Vault[P <: Proposition, 
	TX <: Transaction[P],
    PMOD <: PersistentNodeViewModifier[P, TX], 
    V <: Vault[P, TX, PMOD, V]] extends NodeViewComponent {
  self: V =>

  type VersionTag = NodeViewModifier.ModifierId

  def scanOffchain(tx: TX): V

  def scanOffchain(txs: Seq[TX]): V

  def scanPersistent(modifier: PMOD): V

  def rollback(to: VersionTag): Try[V]
}
\end{lstlisting}

Scorex also contains \textit{Wallet} interface derived from the \textit{Vault}, parametrized with types of secrets and their public images also.

\begin{lstlisting}
trait Wallet[P <: Proposition, 
	TX <: Transaction[P], 
	PMOD <: PersistentNodeViewModifier[P,TX], 
	W <: Wallet[P, TX, PMOD, W]] extends Vault[P, TX, PMOD, W] {
  self: W =>

  type S <: Secret
  type PI <: ProofOfKnowledgeProposition[S]

  def generateNewSecret(): W

  def historyTransactions: Seq[WalletTransaction[P, TX]]

  def boxes(): Seq[WalletBox[P, _ <: Box[P]]]

  def publicKeys: Set[PI]

  def secrets: Set[S]

  def secretByPublicImage(publicImage: PI): Option[S]
}
\end{lstlisting}


\subsection{A Memory Pool}

A memory pool holds transactions not included into blocks yet and hence unconfirmed. We omit its functions here~(as they are pretty trivial) and provide only the type signature of the trait.  

\begin{lstlisting}
trait MemoryPool[TX <: Transaction[_], M <: MemoryPool[TX, M]]
\end{lstlisting}


\subsection{Block}

It is possible to develop block-less system, the only requirement is to have a history which contains instances of persistence node view modifiers. Nevertheless, the basic interface for a block is provided as it is needed for almost all imaginable applications. In addition to \textit{identifier} and \textit{parent identifier} fields inherited from \textit{PersistentNodeViewModifier}, a \textit{Block} generic interface contains also a version~(we assume block format could change with time) and timestamp.

\begin{lstlisting}
trait Block[P <: Proposition, TX <: Transaction[P]]
  extends PersistentNodeViewModifier[P, TX] with JsonSerializable {

  def version: Version

  def timestamp: Timestamp

  ...
}
\end{lstlisting}

\section{Network Layer}

Network layer in Scorex is simpler than in Bitcoin or Nxt. It provides some basic functionality~(a half-baked protocol with possibility to inject new methods) and also a lot of settings in the \textit{p2p} section of the \textit{settings.json} file~(we will further refer to a setting in this section as to \textit{p2p/setting}). This part of the Scorex is massively using Akka~\cite{} actors-based messaging framework. 

\subsection{Network Controller} 

\textit{NetworkController} class controls all the network interactions. It binds to the port given in the \textit{p2p/port} setting, obtains own external address other peers can connect to~(it s not always available), connects to a peer by a request and handles incoming connections. It also routes messages from peers to higher levels of the core and back.

\begin{lstlisting}
\end{lstlisting}

\subsection{Message Handler}

\begin{lstlisting}
\end{lstlisting}

\subsection{Peer Discovery}

\subsection{Broadcasting Strategies}

\subsection{Peer Connection Handler}

\subsection{Message Specification}

\subsection{Implementing }

\section{Examples}
There are few examples included into the distribution.

\subsection{Proof-of-Stake}
Proof-of-Stake module contains implementations of two Proof-of-Stake consensus algorithms. 

\subsection{Hybrid Proof-of-Work / Proof-of-Stake implementation}


\bibliographystyle{plain}
\bibliography{sources}
\appendix
\section*{A. NIZK Proofs}

This section gives an example of a {\em Non-Interactive Zero-Knowledge} (NIZK) proof (of knowledge). We illustrate this by first giving an example of an {\em Interactive Zero-Knowledge Proof} of Knowledge and then convert this to a non-interactive proof. 

\paragraph{An Interactive Proof:} Assume that $n$ is a public composite integer that is hard to factor.
Let $y\in \mathbb{Z}^*_n$ be a public value. In the following 3-step protocol, a prover $P$ proves to a verifier $V$, the {\em knowledge} of some secret $x$ such that $y\equiv x^2 \pmod{n}$.
Note that without the factors of $n$, not only is it hard to find any such $x$, but also it is hard to decide if $x$ even exists. In other words, it is hard to decide if $y$ is a {\em  quadratic residue} modulo $n$.\footnote{We could envision a different scenario where $P$ proves to $V$ that $y$ is indeed a quadratic residue modulo $n$ without necessarily proving that $P$ `knows' a square root of $y$. This is called a {\em proof of membership}. A proof of knowledge is stronger in that it additionally allows $V$ to extract the square root of $y$ if $P$'s state can be reset to use the same randomness.}


\begin{enumerate}
	\item $P$ generates $r\rand \mathbb{Z}^*_n$ and sends $s = r^2\bmod{n}$ to $V$.
	\item $V$ randomly selects a bit $b\rand \{0, 1\}$ and sends $b$ to $P$.
	\item $P$ sends $z=x^br \bmod{n}$ to $V$, who accepts if $z^2 \equiv y^bs\pmod{n}$
\end{enumerate}

In essense, depending on the bit $b$ the prover is required to either reveal a square root of $s$ or a square root of $sy$ (but never both, since that would reveal $x$). 
First observe that the protocol is a {\em proof of knowledge} because if $P$ can be ``reset'' (i.e., be forced to reuse randomness) then $V$ can extract $x$ by resetting $P$ and giving it a different $b$ in the second run of the protocol. 

To see that it is zero knowledge, first note that if $P$ indeed knows $x$ then $P$ can respond in the third step such that $V$ accepts 100\% of the time. On the other hand, if $P$ does not know any such $x$ than $P$ can attempt to guess $b$ and select $s$ differently (i.e., $s=r^2/y^b$) and still make $V$ accept in the third step (by setting $z=r$) as long as the guess was correct. 
Since the chance of correctly guessing $b$ is 50\%, therefore, a cheating $P$ can make $V$ accept only 50\% of the time. 
Given the protocol transcript where $V$ accepts, there is no way to decide if $P$ indeed knew $x$ because $P$ still has 50\% chance of cheating without knowing $x$. Hence the protocol is zero-knowledge.

We know that the probability of a cheating $P$ succeeding in one run of the protocol is $1/2$. This implies that for $m$ {\em parallel runs}, the probability of a cheating $P$ succeeding is $1/2^m$, which can be made arbitrarily small by increasing $m$. 

\paragraph{A Parallel Interactive Proof:} We give the $m$-parallel round protocol below.

\begin{enumerate}
	\item $P$ generates $r_1, r_2, \ldots, r_m\rand \mathbb{Z}^*_n$ and sends $s_i = r_i^2\bmod{n}$ to $V$ for $1\leq i\leq m$.
	\item $V$ randomly selects $m$ bits $b_i\rand \{0, 1\}$  for $1\leq i\leq m$ and sends all $b_i$s to $P$.
	\item $P$ computes $z_i=x^{b_i}r_i \bmod{n}$ and sends all $z_i$s to $V$ (for $1\leq i\leq m$). $V$ accepts if $z_i^2 \equiv y^{b_i}s_i\pmod{n}$  (for $1\leq i\leq m$).
\end{enumerate}

\paragraph{A Non-Interactive Proof:} We will use the Fiat-Shamir heurestic~\cite{fiat1986prove} to convert the above to a NIZK Proof. In this method, $V$'s challenge in the second step is obtained by applying a  one-way hash function to the value sent to $V$ in Step 1. This approach assumes that the hash function can be modeled using a random oracle.

$P$ generates $r_i$s and sets $s_i = r_i^2\bmod{n}$. $P$ then computes $h = H(r_1, r_2, \ldots, r_m)$ for a one-way hash function $H$ that outputs $m$ bits. $P$ then emulates Step 2 by setting $b_i$ as the $i^{th}$ bit of $h$. Finally $P$ emulates Step 3 and the entire transcript of the three emulated steps forms the NIZK proof.

\paragraph{NIZK proofs for NP:} The above proof is for a particular NP language, the set of quadratic residues modulo $n$. Since this is not believed to be NP-Complete, we cannot use this to construct NIZK proofs for arbitrary NP statements. However, similar techniques can be used for {\em circuit satisfiability} (SAT), a problem known to be NP-Complete. One construction based on pairings is given in~\cite{groth2006perfect}. We create a NIZK proof for an arbitrary NP statement $s$ by first reducing it to $t$, an instance of SAT. Then we give a NIZK proof of $t$, which is equivalent to a NIZK proof of $s$. Note that such reductions, although polynomial time, are inefficient in practice. Hence, we often use specialized NIZK proofs (such as the ones given above).
\end{document}