Introduction.tex

In the original Bitcoin whitepaper \cite{Bitcoin}, \citeauthor{Bitcoin} proposed a simple method to verify the presence of a transaction within a Proof of Work (PoW) blockchain called Simplified Payment Verification (SPV). While this method significantly reduces the amount of data a peer has to store to verify such a thing, it is not scalable. Indeed, as of June 2020, using this method to verify the presence of a transaction within the Ethereum blockchain requires storing approximately \num{10000000} headers \cite{Etherscan}, each of which requires \SI{508}{\byte} of storage \cite{\FCCite}. Hence, this method would require approximately \SI{4.73}{\gibi\byte} of storage, and grows linearly with the size of the main chain. Furthermore, the existence of multi-currency wallets worsens the problem, a \textit{client} having by definition low storage and memory capacities.
    
In order to overcome this problem, two approaches, so-called \textit{superlight} blockchain clients or \textit{sublinear} light clients, have been proposed: Superblock NiPoPows \cite{\NipoCite} and \FC\ \cite{\FCCite}. Since the former does not take into account the variable difficulty of the Bitcoin protocol, the latter uses a different approach to handle this problem.
    
However, both these protocols require the addition in the header of a block of a new data field: the MMR root \cite{\FCCite} for \FC\ and the previous \textit{superblocks} level for Superblock. In order to implement these, it is thus necessary to fork the current protocol to add this data field if it is not present. A convenient way to do this, considered by the authors of \FC, is to deploy it as a velvet fork \cite{Velvet}. While they claim the security of the \FC\ protocol when deployed as such, a new type of attack called the \cs\ attacks, discovered by the authors of the Superblock protocol, allows an adversary to perform a double-spend transaction with non-overwhelming probability of failure.
    
In this thesis, we aim to describe formally a \cs\ attack on the \FC\ protocol when deployed as a velvet fork, to improve this protocol to make it resistant to this kind of attacks and finally to implement it as a chain relay, similarly to BTC-Relay \cite{BTCRelay}.

\paragraph{Blockchains and Simplified Payment Verification clients.} A \textit{block} is a data structure composed of two parts: the body and the header. The body contains transactions, which are actually arrays of inputs and outputs that can be hashed using SHA-256 \cite{SoK}. A block header contains metadata, including but not limited to the block version, the previous block header hash, the Merkle Tree root and a nonce \cite{BitcoinHeader}. That said, a \textit{blockchain} is the data structure linking blocks together, using the PoW deduced from the block header.
    
Simplified Payment Verification (SPV) has been introduced in the original Bitcoin whitepaper \cite{Bitcoin} as a protocol to verify the inclusion of a transaction within the main chain efficiently. The argument back then was that a Bitcoin block header is \SI{80}{\byte} big, while the total block size is in average \SI{1.284}{\mega\byte} as of July 2, 2020 and shows a general increase throughout the years \cite{BitcoinSize}. The SPV protocol requires to store every block header in the chain, or at least their nonce, reference to the previous block header and Merkle Tree root. These information gathered, the size of the proof of the inclusion of a transaction is logarithmic in the number of transactions included within the block which contains the transaction we're interested in. However, if the client does not have a copy of the chain, it has to download and store every block header present in the chain, making the size of the proof growing linearly with the length of the blockchain.

Two types of nodes are to be considered, according to \cite{SoKDistributed}: full nodes, who owns a local copy of the blockchain, and clients. Not only clients does not have a local copy of the blockchain, but they are generally also limited in memory and storage.
    
\paragraph{\textit{Superlight} clients.} In the light of the need of more efficient protocol providing proofs of inclusion of transaction within a chain, two methods were proposed: Superblock, also called Non-Interactive Proofs of Proof-of-Work (NIPoPoWs) \cite{\NipoCite} and \FC\ \cite{\FCCite}. Both these protocols aim to provide such proofs whose size grows logarithmically with the total length of the chain, while SPV provides proofs whose size grows linearly with this length.
    
The idea behind the Superblock protocol is to use \textit{superblocks}, that are blocks that appear less frequently than \enquote{normal} blocks. \textit{Superblocks} can be categorized in several levels: \textit{superblocks} of level 1 are twice less frequent than \enquote{normal} blocks, that are \textit{superblocks} of level 0. More generally there is in average a factor \(2^i\) between the number of \textit{superblocks} of level \(i\) and the number of \enquote{normal} blocks. The Superblock method samples mostly \textit{superblocks}, which allows for proofs growing polylogarithmically with the size of the chain. However, an interlink data referencing superblocks must be used for the protocol to run. Furthermore, as the \FC\ authors highlighted: \blockquote{It isn’t clear how to modify the super-block based protocols to handle the variable difficulties} \cite{\FCCite}.
    
\FC\ uses a different approach. The principle is to make the prover commits on its chain before the protocol, using Merkle Mountain Range \cite{\FCCite}. Then, \citeauthor{\FCCite} determined an optimized sampling strategy which samples a fake block if the adversary created one with overwhelming probability. The committing they was forced to make prevents them from providing a valid block in lieu of a fake block. The number of blocks sampled by a prover using the \FC\ protocol grows logarithmically with the size of the chain. \FC\ uses this sampling to verify that the adversary effectively owns a copy of the main chain. Once this is determined, it asks for a proof of inclusion of the block containing the transaction it is interested in, along with a Merkle Proof, as used in the SPV protocol. Just like the Superblock protocol, \FC\ also requires the presence of an additional interlink data, which is the Merkle Mountain Range root, often used throughout the protocol. However, unlike Superblock, \FC\ has been designed to work on a chain with variable difficulty.
    
\paragraph{Velvet forks.} Changing a protocol rules, like adding the interlink data for instance, traditionally requires either a hard fork or a soft fork. In the case of a hard fork, adding this interlink data would mean changing every block already mined to add the interlink data to them. In the case of a soft fork, the interlink data would be added only to the most recent blocks. In both cases, it assumes that a majority of nodes in the network has adopted the new protocol.
    
However, a more novel fork strategy may be more convenient for this case: the velvet fork, that has been described in \cite{Velvet}. The principle is that upgraded nodes mine blocks according to the new protocol but which are still valid regarding to the old protocol. By doing so, there is no need for a majority to adopt the new protocol, as long as \FC\ can be adapted to run with blocks mined by non-upgraded nodes, which the \FC\ authors have done in \cite{\FCCite}. However, this incurs an increase in the size of the proofs, although they are still growing logarithmically with the size of the chain. Furthermore, contrarily to a soft or a hard fork where the interlink data has to be valid to be accepted by the consensus, nothing prevents an adversary from putting arbitrary data in the interlink data field when \FC\ is deployed as a velvet fork, since the block would still be considered valid by the old protocol. It thus gives the adversary a potential way to fool the client.
    
\paragraph{Our contribution.} We summarise our contributions by the following:
    
\begin{description}
    \item[\CS\ attacks.] We formalise the concept of \cs\ attack on \FC\ when deployed as a velvet fork on an existing blockchain. We show how it is possible for an attacker to perform a double-spent transaction or to create coins by spending from an invalid UTXO even if the attacker has low hashrate. We compute the probability of success of the attack if the \FC\ protocol is implemented as described in \cite{\FCCite} and show that no matter the computational power the attacker has access to, they can have this probability to be as high as they desire. We compute the cost that the attacker has to pay in order to set up the attack and show what is the optimal strategy according which the attacker must behave to minimise this cost. 
    \item[\FC\ improvement.] We design an interactive version of the \FC\ protocol to make it resistant to \cs\ attacks while keeping its efficiency in terms of blocks. We show that our mitigated version is completely resistant to \cs\ attacks, which means such an attacks has a nil probability of success, and is as secure as the original \FC\ protocol concerning the other use cases.
    \item[\FC\ implementation.] We implement \FC\ as a chain relay on the Ethereum blockchain using Solidity \cite{Solidity}, mimicking the BTC-relay \cite{BTCRelay} chain relay and compute the gas needed to verify a transaction. The code is available on GitHub \cite{OwnRepo}. We show that we can verify a block header using \FC\ using a similar amount of gas used to verify a block header on BTC-Relay, which ensures the improvement upon BTC-Relay, since \FC\ only samples a logarithmic number of block headers, while BTC-Relay, as an SPV, samples a linear number of those.
\end{description}