mining.tex

\section{Consensus and Governance}

\subsection{Mining the blockchain}
\label{sect:mining}

Traditionally blocks in a blockchain contain an ordered list of transactions
combined with a cryptographic hash ---Blake2b \cite{aumasson2013blake2} in our
case--- of the previous block \cite{whatisablockchain,raikwar2019sok} and mining
is the act of creating such blocks. Transactions are only added with the
creation of a new block which. In \cite{Eyal:2016:BSB:2930611.2930615}
Ittay et al. propose to decouple the leader election from inclusion of
transactions in blocks for scalability purposes. Their scheme dubbed
\enquote{Bitcoin-NG} is what we adopted using Cuckoo Cycle for proof-of-work.

% Chaining of hashes prevents that blocks can be tampered with. If a block
%changes with even one bit, the hash of the block will change.
%The changed block's successor will then contain the hash of a non-existing
%block. Thus, an attacker modifying a transaction in a block will also have to
%modify all consecutive blocks. Since the hashes also have to satisfy a
%difficulty requirement, which requires a non-trivial amount of work, rewriting
%a block in the history of the chain is assumed to require more computational
%resources than available to an attacker.


\subsubsection{Cuckoo Cycle PoW}

\textit{Cuckoo Cycle} \cite{Tromp2015CuckooCA}, a graph-theoretic problem of
finding cycles in a graph, is used for proof-of-work puzzles. Finding solutions
to this problem is memory bound, meaning that runtime is constrained by memory
latency of accessing nodes of the graph. Cuckoo cycle was chosen because memory
latency is believed to not allow as big performance gains from specialised
integrated circuits (ASICs) versus general purpose hardware. Verifying the
validity of a solution is also trivial, meaning that validating a block has
less overhead.

Solving a cuckoo cycle instance requires finding a fixed length cycle in a
bipartite graph of $2^N$ edges and $2^M$ nodes. The ratio of $\frac{M}{N}$,
$\frac{1}{2}$ by default, is one of the parameters to control the hardness of
the problem. Edges are represented as $N$ bit strings.
As of December 2019, \aet\ requires cycles of length 42 and 30 bit edges.

\subsubsection{Difficulty}

Adaptable difficulty allows us to control the expected time it takes to find
a solution and thus a new valid block. To allow more fine-grained control over
the difficulty of the proof-of-work, the final step after a solution to the
graph problem has been found is to hash it.
The hash is then compared to a difficulty target, which is adjusted with
each new block. If output of the hash function and the difficulty target are
interpreted as numbers, then in order to have a valid proof-of-work solution,
the hash needs to be smaller than the target difficulty.

The difficulty for each block is deterministically computed based on timestamps
of the last 17 blocks. This timestamp is unreliable, since the nodes have no
synchronized clocks. However, the timestamp may not precede the timestamp of a
previous block. A block submitted with difficulty not meeting the target
specified in the previous block will be ignored by honest nodes.
Likewise, if a miner presents the wrong target difficulty for the next block,
this block will be discarded.

\subsubsection{Forks}

Whenever there are two or more blocks produced with the same parent block, we
speak of a \textit{fork}. This can happen for a variety of reasons, accidental
or intended. Forks can last for multiple blocks with miners working on separate
branches.
A defining feature of every blockchain is the \textit{fork choice rule}. It
tells honest nodes which branch to choose in case of a fork. For \aet nodes,
the rule is to prefer the longest branch use work committed to it, as measured
via the difficulty, as tiebreaker.

A different kind of fork can be caused whenever nodes run different software
and disagree about the rules of what constitutes a valid block. In this case
manual intervention by node operators might be required.

%\subsubsection{Finality}

%The most important metric for a majority of blockchain users is the latency
%between submitting a transaction and the time by which there is enough
%certainty to consider this transaction confirmed, i.e. final. How to
%quantify this metric is still an understudied topic but beyond the scope of
%this paper.
%The most widely used metric nowadays, although certainly not the best, is the
%number of blocks following the block which included the transaction in
%question.
%This metric is used with the assumption that with each successive block the
%probability of a previously unknown, but longer, branch with more work
%committed, showing up, gets lower. Such an unknown branch could be problematic
%since it might include different transaction and invalidate a previously
%thought to be valid transaction.
%The logic for this follows from the above fork choice rule and the lack of a
%way of assessing the actual mining power available to all network
%participants.
%(finality as a function of the transacted value and PoW amount (time))

\subsection{Next Generation Nakamoto Consensus}

Where in Bitcoin or Ethereum each block filled with transactions requires
a proof-of-work solution, a miner in \aet\ has to find one proof-of-work
solution and can then create multiple blocks with transactions until the next
miner finds an admissible proof-of-work solution. This scheme was proposed by
Ittay et al. \cite{Eyal:2016:BSB:2930611.2930615} under the name
\enquote{Bitcoin-NG}.

\subsubsection{Key- and micro-blocks}

Bitcoin-NG requires two different kinds of blocks. One kind, called
\textit{key-block}, to elect the miner, or \textit{leader}, who is allowed to
include transactions on chain, and \textit{micro-blocks} containing
transactions. Every new key-block starts a new epoch---or \textit{generation}
in the \aet\ context.

The key-blocks contain the hash of a previous micro-block as well as the hash
of the previous key-block.
Micro-blocks are created in rapid succession making it likely that any
given new key-block does not include the hash of the latest micro-block
produced by the previous round leader.
This is called a micro-fork. (cf.\ red micro-block in Fig.\
\ref{ng-mining}). The transactions of the discarded micro-blocks are put back
in the transaction pool and taken care of by the next leader. Since they have
been seen in a micro-block before, they will very likely be valid in
future micro-block as well.

In practice, miners are allowed to publish a micro-block every three seconds
and the computational complexity---associated with every transaction and
measured in gas---is limited per block. These limits are put in place to avoid
miners flooding the network.

To give miners an incentive to work on top of the newest micro-block,
transaction fees are divided by giving 40\% to the leader producing a
micro-block and 60\% to the miner of next key-block after that
micro-block\footnote{Note that if miners
  were to only mine key-blocks, there would be no transactions on the
  chain at all.}.

\begin{figure}
   \includegraphics[scale=0.3]{keymicro.jpg}
   \caption{Next generation consensus}
   \label{ng-mining}
\end{figure}

\subsubsection{Fraudulent leaders}

There is only one leader per generation creating micro-blocks. Each key-block
includes the public key of the new leader and consecutive micro-blocks are
only valid if signed with the associated private key. This protects
against third parties trying to post micro-blocks.

A malicious leader, however, could construct forks either by forking directly
from the key-block, or by forking on a micro-block. This could be done to
disrupt the network or to perform double spend attacks. A malicious miner could
also try to produce more micro-blocks than entitled to by fiddling with the
micro-block creation timestamp.

In order to mitigate the risk of a leader forking its own sequence,
there is a mechanism in place to detect and report this by submitting
a Proof-of-Fraud. This is submitted in the next
generation. The leader is punished by not receiving a block reward and
in order to make that possible, block rewards are not immediately paid out but
kept for the duration of 180 blocks.

\subsubsection{Divide and conquer}

Each transaction is a binary of a certain size. Internally both size
and computation are expressed in gas and there is a maximum amount of
gas per micro-block that allows for maximally 300 KB per micro-block.
Thus, an additional advantage of the introduction of micro-blocks is that
instead of a huge block with 180,000 transactions in 3 minutes, we can create
60
reasonably sized micro-blocks of maximally 300 KB  in the same 3
minutes. This has several advantages for network latency and
smaller blocks are easier and faster to gossip through the
network. Moreover, if it takes longer to compute the next key-block we
are not bound to a maximum block size, because we generate new
micro-blocks as long as no key-block has been found.

\subsection{Weighted delegated coin-voting}

A major problem in all decentralized systems is that of coordination between
the different participants, especially because they might not share common
goals with regards to the utility and development of the system.

Giving all these different participants a way to signal their preferences is
important to make decision processes legitimate and also collect as much
information as possible.

The previous section outlined the coordination game played by miners, where
they vote with they computational power to signal which fork they support and
thus decide the \enquote{main chain}. Coordination here is facilitated by the
fork choice rule described above but miners do not have to follow it.

Another group to consider are owners of the native \aet\ coin---although by no
means can we assume that that group is homogeneous in their objectives. The
signalling mechanism used for them is based on delegative
 or liquid democracy \cite{ford2002delegative} and shareholder voting. This
means in practice that any owner of coins can delegate their voting power to
any other blockchain account. The voting power is based on the amount of coins
owned. This means that opposed to \enquote{one person one vote}, it is
\enquote{one coin one vote.}
These two voting schemes were chosen because allowing the delegation of voting
power allows people without enough expertise but a lot of stake to
delegate their voting power to someone with the expertise but maybe lacking
voting power. In theory this should lead to better decisions to be made. Making
the voting power proportional to coins owned follows the logic that a bigger
share of the value of the network implies more \enquote{skin in the game}.

This scheme could then be used to prioritze future development efforts or in
the case of a contentious fork signal which side might get support from most
coin owners, which could then inform the behaviour of miners when choosing a
fork to mine on.


\begin{figure}[h!]
   \includegraphics[scale=0.31]{ae-inflation_110_years.png}
   \caption{Inflation and total coins (source: aeknow.org)}
   \label{fig:coins}
\end{figure}



\subsection{Economics}
During the initial token sale in April to June 2017 82\% of the initial AE tokens got sold via a public token sale (contribution campaign). The rest was reserved for the founding team, the founding company and for the foundation to do future airdrops. 99\% of the initial tokens were created as an ERC20 smart contract on Ethereum with a total supply of 273,685,830.1643299 AE. After the mainnet launch, the ERC20 token contract became obsolete and after its expiry all AE have been migrated to \aet\ blockchain. 


Further, mining started with the mainnet launch. Through the process of mining new coins get created with every new key-block as a block-reward. Similarly to Bitcoin, \aet\ is programmed to have a finite supply, reaching its maximum in about one hundred years. \aet\'s new coin supply curve is hereby similarly decreasing like Bitcoins or Ethereums, although Ethereum has infinite supply programmed into its code base. 
Figure \ref{fig:coins} shows the yearly "inflation" rate and the total coins in existence.