main.tex

\documentclass{llncs}

\pagestyle{headings}

%\usepackage{showkeys}
\usepackage{hyperref}
\usepackage{url}
\usepackage{relsize}
\usepackage{enumitem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage[T1]{fontenc}
\usepackage{listings, framed}
\usepackage{orcidlink}

\lstset{
  language=Java,
  showstringspaces=false,
  columns=flexible,
  basicstyle={\ttfamily},
  frame=l,
  numbers=left,
  numberstyle={\ttfamily},
%  breaklines=true,
  breakatwhitespace=true,
  tabsize=3,
  escapechar=|
}

% \|name| or \mathid{name} denotes identifiers and slots in formulas
\def\|#1|{\mathid{#1}}
\newcommand{\mathid}[1]{\ensuremath{\mathit{#1}}}
% \<name> or \codeid{name} denotes computer code identifiers
\def\codesize{\small}
\def\<#1>{\codeid{#1}}
\newcommand{\codeid}[1]{\ifmmode{\mbox{\codesize\ttfamily{#1}}}\else{\codesize\ttfamily #1}\fi}

\newcommand{\todo}[1]{{\color{red}\bfseries [[#1]]}}

\DeclareMathOperator*{\append}{\bowtie}

\newcommand{\fs}[1]{\todo{FS: #1}}
\newcommand*\xor{\oplus}

\newtheorem{alg}{Algorithm}

\newcommand{\wrt}{\textit{wrt.\ }}
\newcommand{\ie}{, \textit{ie.}, }

\newcommand{\numberofscoops}{{\#\mathit{scoops}}}
\newcommand{\noncesize}{{\mathit{nonce}_{\mathit{size}}}}
\newcommand{\byte}{{\mathit{byte}}}
\newcommand{\nonce}{{\mathit{nonce}}}
\newcommand{\nonces}{{\mathit{nonces}}}
\newcommand{\scoops}{{\mathit{scoops}}}
\newcommand{\plot}{{\mathit{plot}}}
\newcommand{\seed}{{\mathit{seed}}}
\newcommand{\deadline}{{\mathit{deadline}}}
\newcommand{\generation}{{\mathit{generation}}}
\newcommand{\size}{{\mathit{size}}}
\newcommand{\scoopnumber}{{\mathit{scoopNumber}}}
\newcommand{\data}{{\mathit{data}}}
\newcommand{\challenge}{{\mathit{challenge}}}
\newcommand{\mynext}{{\mathit{next}}}
\newcommand{\nextchallenge}{\challenge_\mynext}
\newcommand{\initialchallenge}{{\mathit{initialChallenge}}}
\newcommand{\height}{{\mathit{height}}}
\newcommand{\trunk}{{\mathit{trunk}}}
\newcommand{\block}{{\mathit{block}}}
\newcommand{\oblivion}{{\mathit{oblivion}}}
\newcommand{\now}{{\mathit{now}}}
\newcommand{\beat}{{\mathit{beat}}}
\newcommand{\weightedbeat}{\mathit{weightedBeat}}
\newcommand{\nextweightedbeat}{\weightedbeat_\mynext}
\newcommand{\power}{{\mathit{power}}}
\newcommand{\previousblockhash}{{\mathit{previousBlockHash}}}
\newcommand{\waitingtime}{{\mathit{waitingTime}}}
\newcommand{\nextwaitingtime}{\tau_\mynext}
\newcommand{\nextpower}{\power_\mynext}
\newcommand{\nextacceleration}{\alpha_\mynext}
\newcommand{\nextblock}{\block_\mynext}
\newcommand{\genesis}{{\mathit{genesis}}}
\newcommand{\consensus}{{\mathit{consensus}}}
\newcommand{\nattobe}{{\mathit{nat2be}}}
\newcommand{\betonat}{{\mathit{be2nat}}}
\newcommand{\finalhash}{{h_{\mathit{final}}}}
\newcommand{\chainidentifier}{{\mathit{chainIdentifier}}}
\newcommand{\publickeyofpeer}{{\mathit{publicKeyOfPeer}}}
\newcommand{\publickeyofminer}{{\mathit{publicKeyOfMiner}}}

\newcommand{\Prologs}{{\mathsf{Prologs}}}
\newcommand{\Plots}{{\mathsf{Plots}}}
\newcommand{\Challenges}{{\mathsf{Challenges}}}
\newcommand{\Scoops}{{\mathsf{Scoops}}}
\newcommand{\Nonces}{{\mathsf{Nonces}}}
\newcommand{\Trunks}{{\mathsf{Trunks}}}
\newcommand{\Blocks}{{\mathsf{Blocks}}}
\newcommand{\GenesisBlocks}{{\mathsf{GenesisBlocks}}}
\newcommand{\NonGenesisBlocks}{{\mathsf{NonGenesisBlocks}}}
\newcommand{\Deadlines}{{\mathsf{Deadlines}}}

\begin{document}

\begin{frontmatter}

  \title{A Formalization of Signum's Consensus}

  \author{Fausto Spoto\orcidlink{0000-0003-2973-0384}}
  \institute{Dipartimento di Informatica, Universit\`a di Verona, Italy\\
    \email{fausto.spoto@univr.it}}

%  \author{anonymous author}
%  \institute{anonymous institute\\
%    \email{anonymous email}}

  \maketitle

  \begin{abstract}
    Bitcoin's proof of work consensus consumes energy and requires
    dedicated, expensive hardware. Therefore, alternatives have been proposed,
    including proof of stake and proof of space. The latter mines with
    disk space instead of CPU power. Signum is the only implemented
    proof of space blockchain with smart contracts, and
    runs since ten years. But its relatively simple
    consensus algorithm lacks any formalization.
    This paper formalizes Signum's consensus and uses that formalization
    to show that Signum is free from block grinding attacks and is largely
    protected from challenge grinding attacks. Moreover, this paper proposes
    a new protection for Signum against newborn attacks.
  \end{abstract}

\end{frontmatter}

\pagenumbering{arabic}

\input{introduction}
\input{nonce_and_plot}
\input{challenge_and_deadline}
\input{blockchain_construction}
\input{prolog_and_attacks}
\input{related_work}
\input{conclusion}

\bibliographystyle{plain}
\bibliography{biblio}

\input{proofs}

\end{document}