construction.tex

\section{Velvet NIPoPoWs}\label{sec:construction}
In order to eliminate the Chainsewing Attack we propose an update to the velvet NIPoPoW protocol. The core problem is that, in her suffix proof, the adversary was able to claim not only blocks of shorter forked chains, but also arbitrarily long parts of the chain generated by an honest party. Since thorny blocks are accepted as valid, the verifier cannot distinguish blocks that actually belong in a chain from blocks that only \emph{seem} to belong in the same chain because they are pointed to from a thorny block.

The idea for a secure protocol is to distinguish the smooth from the thorny blocks, so that smooth blocks can never point to thorny blocks. In this way we can make sure that thorny blocks acting as passing points to fork chains, as block $a'$ does in Figure~\ref{fig:attack}, cannot be pointed to by honestly generated blocks. Therefore, the adversary cannot utilize honest mining power to construct a stronger suffix proof for her fork chain. Our velvet construction mandates that honest miners create blocks that contain interlink pointers pointing only to previous smooth blocks. As such, newly created smooth blocks can only point to previously created smooth blocks and not thorny blocks. Following the terminology of Section~\ref{sec:velvet}, the smoothness of a block in this new construction is a stricter notion than smoothness in the na\"ive construction.

In order to formally describe the suggested protocol patch, we define smooth blocks in our patched protocol recursively by introducing the notion of a smooth interlink pointer.

\begin{definition}[Smooth Pointer]
  A \emph{smooth pointer} of a block $b$ for a specific level $\mu$ is the interlink pointer to the most recent $\mu$-level smooth ancestor of $b$.
	\label{defn:smooth_pointer}
\end{definition}

We describe a protocol patch that operates as follows. The superblock NIPoPoW protocol works as usual but each honest miner constructs smooth blocks whose interlink contains only smooth pointers; thus it is constructed excluding thorny blocks. In this way, although thorny blocks are accepted in the chain, they are not taken into consideration when updating the interlink structure for the next block to be mined. No honest block could now point to a thorny superblock that may act as a passage to the fork chain in an adversarial suffix proof. Thus, after this protocol update, the adversary is only able to inject \emph{adversarially} generated blocks from an honestly adopted chain to her own fork.
At the same time, thorny blocks cannot participate in an honestly generated suffix proof except for some blocks in the proof's suffix $(\chi)$. Consequently, as far as the blocks included in a suffix proof are concerned, we can think of thorny blocks as belonging in the adversary's fork chain for the $\pi$ part of the proof,  which is the critical part for proof comparison.
Figure~\ref{fig:injection} illustrates this remark. The velvet NIPoPoW verifier is also modified to only follow interlink pointers, and never previd pointers (which could be pointing to thorny blocks, even if honestly generated).

\begin{figure*}[h!]
	\begin{center}
		\iftwocolumn
			\includegraphics[width=0.6 \textwidth]{figures/injection.pdf}
		\else
			\includegraphics[width=0.8 \textwidth]{figures/injection.pdf}
		\fi
	\end{center}
	\caption{Adversarial fork chain $\chain_\mathcal{A}$ and chain $\chain_B$ of an honest party. Thorny blocks are colored black. Dashed arrows represent interlink pointers. After the protocol update when an adversarially generated block is sewed from $\chain_B$ into the adversary's suffix proof the verifier perceives $\chain_\mathcal{A}$ as longer and $\chain_B$ as shorter. \textbf{I:} The real picture of the chains. \textbf{II:} Equivalent picture from the verifier's perspective considering the suffix proof for each chain.}
	\label{fig:injection}
\end{figure*}

\import{./}{algorithms/alg.smooth-chain-suffix}

With this protocol patch we conclude that the adversary cannot usurp honest mining power for use in her fork chain. This change has an undesired side effect: the honest prover cannot utilize thorny blocks belonging in the honest chain. Thus, contrary to the na\"ive protocol, the honest prover can only depend on \emph{honestly} mined blocks in the honestly adopted chain. Due to this fact, to ensure security in the velvet model, we introduce the assumption that the adversary is bound by $1/3$ of the honest \emph{upgraded} mining power.

\begin{definition}[Velvet Honest Majority]
	Let $n_h$ be the number of upgraded honest miners. Then $t$ out of total $n$ parties are corrupted such that $\dfrac{t}{n_h} < \dfrac{1 - \delta_v}{3}$, for some $\delta_v > 0$.
	\label{defn:velvet_honest_majority}
\end{definition}

\import{./}{algorithms/alg.update-interlink}
\import{./}{algorithms/alg.velvet-suffix-prover}

The following Lemmas come as immediate results from the suggested protocol
update.

\begin{lemma}
	A velvet suffix proof constructed by an honest party cannot contain any thorny block.
	\label{lemm:smooth_honest_suffix}
\end{lemma}
%\begin{proof}
%	The statement holds by construction.
%\end{proof}

The following lemma discusses the structure of valid adversarial proofs, i.e., adversarial proofs that pass the honest verifier validation process. The structure is illustrated in Figure~\ref{fig:adversarial_velvet_proof}.

\begin{figure}
	\begin{center}
		\iftwocolumn
			\includegraphics[width=0.8\columnwidth]{figures/adversarial_velvet_proof.pdf}
		\else
			\includegraphics[width=0.5\columnwidth]{figures/adversarial_velvet_proof.pdf}
		\fi
	\end{center}
	\caption{After the protocol update the adversarial velvet suffix proof consists of an initial part of smooth blocks possibly followed by thorny blocks.}
	\label{fig:adversarial_velvet_proof}
\end{figure}

\begin{lemma}
	Any valid adversarial proof $\mathcal{P_A} = (\pi_\mathcal{A}, \chi_\mathcal{A})$ containing both smooth and thorny blocks consists of a prefix smooth subchain followed by a suffix thorny subchain.
	\label{lem:adversarial_proof_scheme}
\end{lemma}
\begin{proof}
	Suppose for contradiction that there was a thorny block immediately preceding a smooth block. Then the smooth block would contain a pointer to a thorny block, contradicting the definition of smoothness.
	\Qed
\end{proof}

We now describe the algorithms needed by the upgraded miner, prover and verifier. In order to construct an interlink containing only the smooth blocks, the miner keeps a copy of the ``smooth chain'' ($\chain_S$) which consists of the smooth blocks in his adopted chain $\chain$. The algorithm for extracting the smooth chain out of $\chain$ is given in Algorithm~\ref{alg:smooth_chain_suffix}. Function \emph{isSmoothBlock($B$)} checks whether a block $B$ is smooth by calling \textit{isSmoothPointer($B,p$)} for every pointer $p$ in $B$'s interlink. Function \emph{isSmoothPointer($B,p$)} returns \emph{true} if $p$ is a valid pointer, i.e., a pointer to the most recent smooth block for the level denoted by the pointer itself. The \emph{updateInterlink} algorithm is given in Algorithm~\ref{alg:updateInterlink}. It is the same as in the case of a soft fork, but works on the smooth chain $\chain_S$ instead of $\chain$.

The construction of the velvet suffix prover is given in Algorithm~\ref{alg:velvet_suffix_prover}. Again it deviates from the soft fork case by working on the smooth chain $\chain_S$ instead of $\chain$.
Lastly, the Verify algorithm for the NIPoPoW suffix protocol remains the same as in the case of a hard or soft fork, keeping in mind that no \emph{previd} links can be followed when verifying the ancestry of the chain to avoid hitting any thorny blocks.

%We provide an in-depth analysis and formal proof of our construction's security in Appendix~\ref{sec:analysis}.