definition.tex

\section{Defining Proof-of-Burn}

We now formally define what a proof-of-burn protocol is. Let $\kappa$ be the security parameter. The protocol consists of two functions $\GenBurnAddr$ and $\BurnVerify$ and works as follows. Alice first generates an address $\burnAddr$ to which she sends some cryptocurrency. The address is generated by invoking $\GenBurnAddr(1^\kappa, t)$ and encodes information contained in a tag $t$, a string of Alice's choice. When the transaction is completed, she gives the transaction and tag to Bob who invokes $\BurnVerify(1^\kappa, t, \burnAddr)$ to verify she irrevocably destroyed the cryptocurrency while committing to the provided tag.

\begin{definition}[Burn protocol]
  A \emph{burn} protocol $\Pi$ consists of two functions $\GenBurnAddr(1^\kappa, t)$ and $\BurnVerify(1^\kappa, t, \burnAddr)$ which work as follows:

  \begin{itemize}
    \item $\GenBurnAddr(1^\kappa, t)$: Given a tag $t \in \{0,1\}^*$, generate a \emph{burn address}.

    \item $\BurnVerify(1^\kappa, t, \burnAddr)$: Given a tag $t \in \{0,1\}^*$ and an address $\burnAddr$, return $\sf{true}$ if and only if $\burnAddr$ is a burn address and correctly encodes $t$.
  \end{itemize}
\end{definition}

We require that the burn scheme is \emph{correct}.

\begin{definition}[Correctness]
  A burn protocol $\Pi$ is \emph{correct} if for all $t \in \{0,1\}^*$ and for all $\kappa \in \mathbb{N}$ it holds that
  $\BurnVerify(1^\kappa, t, \GenBurnAddr(1^\kappa, t)) = \true$.
\end{definition}

With foresight, we remark that the implementation of $\GenBurnAddr$ and $\BurnVerify$ will typically be deterministic, which alleviates the need for a probabilistic correctness definition.

Naturally, for $\GenBurnAddr$ to generate addresses that ``look'' valid but are unspendable according to the blockchain protocol requires that the burn protocol respects its format. We abstract the address generation and spending verification of the given system into a \emph{blockchain address protocol}:

\begin{definition}[Blockchain address protocol]
  A \emph{blockchain address protocol} $\Pi_\alpha$ consists of two functions $\GenAddr$ and $\sf{SpendVerify}$:

  \begin{itemize}
    \item $\GenAddr(1^\kappa)$: Returns a tuple $(\sf{pk}, \sf{sk})$, denoting the cryptocurrency address $\sf{pk}$ (a public key) used to receive money and its respective secret key $\sf{sk}$ which allows spending from that address.

    \item $\sf{SpendVerify}(m, \sigma, pk)$: Returns $\sf{true}$ if the transaction $m$ spending from receiving address $pk$ has been authorized by the signature $\sigma$ (by being signed by the respective private key).
  \end{itemize}
\end{definition}

We note that, while the blockchain address protocol is not part of the burn protocol, the \emph{security} properties of a burn protocol $\Pi$ will be defined \emph{with respect to} a blockchain address protocol $\Pi_\alpha$.

These two functionalities are typically implemented using a public key signature scheme and accompanied by a respective signing algorithm. The signing algorithm is irrelevant for our burn purposes, as burning entails the inability to spend. As the format of $m$ is cryptocurrency-specific, we intentionally leave it undefined. In both Bitcoin and Ethereum, $m$ corresponds to transaction data. When a new candidate transaction is received from the network, the blockchain node calls $\textsf{SpendVerify}$, passing the public key $pk$, which is the address spending money incoming to the new transaction $m$, together with a signature $\sigma$, which signs $m$ and should be produced using the respective secret key.

To state that the protocol generates addresses which cannot be spent from, we introduce a game-based security definition. The unspendability game $\spendattack$ is illustrated in Algorithm~\ref{alg.spend-game}.

\import{./}{algorithms/alg.spend-game.tex}

\begin{definition}[Unspendability]
  A burn protocol $\Pi$ is \emph{unspendable} with respect to a blockchain address protocol $\Pi_\alpha$ if
  for all probabilistic polynomial-time adversaries $\mathcal{A}$ there exists a negligible function $\negl$ such that
  $
    \Pr[\spendattack_{\mathcal{A}, \Pi}(\kappa) = \textsf{true}] \leq \negl
  $.
\end{definition}

\import{./}{algorithms/alg.bind-game.tex}

It is desired that a burn address encodes one and only one tag. Concretely, given a burn address $\burnAddr$, $\BurnVerify(1^\kappa, t, \burnAddr)$ should only evaluate to $\true$ for a single tag $t$. The game $\bindattack$ in Algorithm~\ref{alg.bind-game} captures this property.

\begin{definition}[Binding]
  A burn protocol $\Pi$ is \emph{binding} if
  for all probabilistic polynomial-time adversaries $\mathcal{A}$ there is a
  negligible function $\negl$ such that
  $\Pr[\bindattack_{\mathcal{A},\Pi}(\kappa)] \leq \negl$.
\end{definition}

We note here that the correctness and binding properties of a burn protocol are irrespective of the blockchain address protocol it was designed for.

We are now ready to define what constitutes a \emph{secure proof-of-burn protocol}.

\begin{definition}[Security]
  Let $\Pi$ be a correct burn protocol. We say $\Pi$ is \emph{secure} with respect to a blockchain address protocol $\Pi_\alpha$ if it is \emph{unspendable} and \emph{binding} with respect to $\Pi_\alpha$.
\end{definition}

The aforementioned properties form a good basis for a burn protocol. We observe that it may be possible to detect whether an address is a burn address. While this is desirable in certain circumstances, it allows miners to censor burn transactions. To mitigate this, we propose \emph{uncensorability}, a property which mandates that a burn address is indistinguishable from a regular address if its tag is not known. During the execution of protocols which satisfy this property, when the burn transaction appears on the network, only the user who performed the burn knows that it constitutes a burn transaction prior to revealing the tag. Naturally, as soon as the tag is revealed, \emph{correctness} mandates that the burn transaction becomes verifiable.

\begin{definition}[Uncensorability]
  Let $\mathcal{T}$ be a distribution of tags.
  A burn protocol $\Pi$ is \emph{uncensorable} if
  the distribution ensembles $\{(pk, sk) \gets \GenAddr(1^\kappa); pk\}_\kappa$ and
  $\{t \gets \mathcal{T}; pk \gets \GenBurnAddr(1^\kappa, t); pk\}_\kappa$ are computationally indistinguishable.
\end{definition}