standard.tex

\section{Relaxing the Random Oracle assumption}\label{sec:standard}

The construction presented above works for P2PKH and achieves its unspendability and uncensorability in the Random Oracle model. In this section, we discuss alternative constructions which work without requiring the Random Oracle model.

The simplest blockchain address protocol is the Pay to Public Key (P2PK) protocol which, in contrast to P2PKH does not hash the public key to generate an address. Instead, the address is literally the public key and spending verification simply checks the validity of a signature. This protocol is illustrated in Algorithm~\ref{alg.p2pk}.

\import{./}{algorithms/alg.p2pk.tex}

Without the Random Oracle model, our construction must be tailored to the signature scheme in order to ensure uncensorability, as our addresses must look similar to public keys generated by the scheme. We describe a burn scheme which can work for (EC)DSA signatures, as used in most cryptocurrencies today. Our scheme is unconditionally correct and binding in the standard model. We provide evidence of uncensorability in the Common Random String model, assuming the DLOG problem is hard and a collision resistant hash function exists. Additionally, we provide evidence that our scheme is unspendable in the Common Random String model and that no generic unspendable construction is possible in the standard model.

Initially, a $\kappa$-order multiplicative group $\mathbb{G}$ of order $q$ and a generator $g$ are selected and let the Common Random String be a random group element $h = g^y$ for some $y \in [q]$. Due to the self-reducibility of the DLOG problem, if DLOG is difficult in the group, an adversary will not be able to find the logarithm $y$ of the random group element, except with negligible probability.

Our scheme is illustrated in Algorithm~\ref{alg.construction-crs}. $\GenBurnAddr$ hashes the tag $t$ and treats $H(t)$ as the exponent, calculates the public key $g^{H(t)}$ and blinds it using the factor $h$. As before, $\BurnVerify$ regenerates the burn address from $t$ and ensures it has been calculated correctly.

\import{./}{algorithms/alg.construction-crs.tex}

Correctness holds unconditionally.

\begin{theorem}[Correctness]
  The proof-of-burn protocol $\Pi$ of Algorithm~\ref{alg.construction-crs} is \emph{correct}.
\end{theorem}
\begin{proof}
  Based on Algorithm~\ref{alg.construction-crs}, $\BurnVerify(1^\kappa, t, \GenBurnAddr(1^\kappa, t)) = \textsf{true}$ if and only if $\GenBurnAddr(1^\kappa, t) = \GenBurnAddr(1^\kappa, t)$, which always holds as $\GenBurnAddr$ is deterministic.
\end{proof}

As evidence towards unspendability, we now remark that it is difficult for an adversary to obtain the secret key corresponding to the public key $h g^{H(t)}$ needed to produce signatures. We therefore conjecture that our scheme is unspendable.

\import{./}{algorithms/alg.secret-key-adversary.tex}

\begin{lem}[Logarithm ignorance]
  If $h$ is a \emph{Common Random String} and assuming the DLOG problem is hard, no probabilistic polynomial-time adversary can produce $(t, z)$ such that $g^z = h g^{H(t)}$, except with negligible probability in $\kappa$.
\end{lem}
\begin{proof}
  Suppose $\mathcal{A}$ is a probabilistic polynomial-time adversary which produces $(t, z)$ with probability of success $p = \Pr[g^z = h g^{H(t)}]$.
  We construct the adversary $\mathcal{A}^*$ which invokes $\mathcal{A}$
  illustrated in Algorithm~\ref{alg.secret-key-adversary} and finds the
  logarithm of $h$.
  Conditioned on the event that $\mathcal{A}$ is successful,
  we have that
  $g^z = h g^{H(t)} \Rightarrow g^z = g^{y + H(t)} \Rightarrow y \equiv z - H(t) \Modulo{q}$, so $\mathcal{A}^*$ is successful.
  Therefore $\Pr[\mathcal{A}^*(h) = y] = p$.
  But $\Pr[\mathcal{A}^*(h) = y]$ is negligible.
\end{proof}

This observation illustrates the useful fact that, if a single group element with unknown logarithm is provided, an arbitrary number of such group elements can be found and logarithm ignorance can be proven.

\noindent\textbf{Proofs-of-ignorance.}
There are other constructions which can give similar results. In fact, recent
work on \emph{proofs-of-ignorance}~\cite{deshpande2018proofs} has shown that any
$\NP$ language can support proofs-of-ignorance, which are a prerequisite for our
need of unspendability (as inability to produce signatures mandates ignorance of
the private key). Therefore, we conjecture that such constructions
are possible using any secure signature scheme in which the secret key
constitutes a witness for the fact that the public key is an element of an $\NP$
language. Additionally, they argue that such constructions are not possible in
the standard model given non-uniform probabilistic polynomial-time adversaries,
supporting our construction in the Common Random String model. Whether burn
constructions in the Standard Model exist against uniform probabilistic
polynomial-time adversaries remains a question for future work.

\import{./}{algorithms/alg.collision-adversary-crs.tex}

\begin{theorem}[Binding]
  If the hash function $H$ is collision resistant and its range lies in $[q]$ where $q$ denotes the group order of $\mathbb{G}$, then the proof-of-burn protocol $\Pi$ of Algorithm~\ref{alg.construction-crs} is \emph{binding}.
\end{theorem}
\begin{proof}
  Let $\mathcal{A}$ be a probabilistic polynomial-time binding adversary against the protocol $\Pi$. We construct the probabilistic polynomial-time collision adversary $\mathcal{A}^*$ against the hash function $H$. The adversary $\mathcal{A}^*$ is illustrated in Algorithm~\ref{alg.collision-adversary-crs} and works as follows. It invokes $\mathcal{A}$ which returns a triplet $(t, t', \burnAddr)$, then returns the collision $(t, t')$. Let $p$ denote the probability that $\mathcal{A}$ is successful.

  Conditioned on the event that $\mathcal{A}$ is successful, it holds that
  $h g^{H(t)} = h g^{H(t')}$ and $t \neq t'$. This implies that $g^{H(t)} = g^{H(t')}$, which in turns yields $H(t) \equiv H(t') \Modulo{q}$. Since the range of $H$ lies in $[q]$, this constitutes a collision and $\mathcal{A}^*$ is successful.

  We thus conclude that $\mathcal{A^*}$ is successful in the $\collisionattack$ game if and only if $\mathcal{A}$ is successful in the $\bindattack$ game.

  \[
    \Pr[\bindattack_{\mathcal{A},\Pi} = \true]
    =
    \Pr[\collisionattack_{\mathcal{A}^*,H} = \true]
  \]

  From the collision resistance of $H$ it follows that $\Pr[\collisionattack_{\mathcal{A}^*,H} = 1] < \negl$. Therefore,
  $\Pr[\bindattack_{\mathcal{A},\Pi} = \true] < \negl$, so
  the protocol $\Pi$ is binding.
\end{proof}

We now give some evidence towards the uncensorability of our scheme.
The following lemma expands on the results of Lemma~\ref{lem:ro-unpredictability} without making use of the Random Oracle model.

\import{./}{algorithms/alg.collision-adversary-unpred-crs.tex}

\newcommand{\collstar}{\textsc{Coll}_{h^*}}

\begin{lem}[Collision resistant unpredictability]
  Let $H$ be a collision resistant hash function and $\{\mathcal{T}\}_{\kappa\in\mathbb{N}}$ be an
  efficiently samplable unpredictable distribution ensemble. Then the
  distribution ensemble $X_\kappa = \{ t \gets \mathcal{T}; H(t) \}$ is unpredictable.
\end{lem}
\begin{proof}
  Consider the collision adversary $\mathcal{A}$ against the hash function $H$ illustrated in Algorithm~\ref{alg.collision-adversary-unpred-crs} which samples $t_1$ and $t_2$ independently from $\mathcal{T}_\kappa$ and hopes for a collision. Let $\collstar$ denote the event that $H(t_1) = H(t_2) = h^*$.
  Applying total probability
  \begin{align*}
  \max_{h^* \in [X_\kappa]}\Pr[\collstar]&
  \\=
  \max_{h^* \in [X_\kappa]}(\Pr[\collstar|t_1 = t_2]\Pr[t_1 = t_2]
   + \Pr[\collstar|t_1 \neq t_2]\Pr[t_1 \neq t_2])&
  \\\leq
  \max_{h^* \in [X_\kappa]}\Pr[\collstar|t_1 = t_2]\Pr[t_1 = t_2]&
  \\ + \max_{h^* \in [X_\kappa]}\Pr[\collstar|t_1 \neq t_2]\Pr[t_1 \neq t_2]&
  \\\leq
  \max_{h^* \in [X_\kappa]}\Pr[t_1 = t_2]
  + \max_{h^* \in [X_\kappa]}\Pr[\collstar|t_1 \neq t_2]\Pr[t_1 \neq t_2]&
  \\=
  \Pr[t_1 = t_2]
  + \max_{h^* \in [X_\kappa]}\Pr[\collstar \land t_1 \neq t_2]&
  \,.
  \end{align*}
  Therefore $\max_{h^* \in [X_\kappa]}\Pr[\collstar \land t_1 \neq t_2] \geq \max_{h^* \in [X_\kappa]}\Pr[\collstar] - \Pr[t_1 = t_2]$.
  We have that
  \begin{align*}
    \Pr[\collisionattack_{\mathcal{A}}(\kappa) = \true] &=
    \sum_{h^* \in [X_\kappa]} \Pr[\collstar \land t_1 \neq t_2]\\\geq
    \max_{h^* \in [X_\kappa]} \Pr[\collstar \land t_1 \neq t_2]
    &\geq
    \max_{h^* \in [X_\kappa]}\Pr[\collstar] - \Pr[t_1 = t_2]\,.
  \end{align*}
  Since $\Pr[\collisionattack_{\mathcal{A}}(\kappa) = \true] \leq \negl$
  and $\Pr[t_1 = t_2] \leq \negl$, therefore $\max_{h^* \in [X_\kappa]} \Pr[\collstar] \leq \negl$.
  Because $H(t_1)$ and $H(t_2)$ are chosen independently,
  \[
  \max_{h^* \in [X_\kappa]}\Pr_{x \gets X_\kappa}[x = h^*] = \sqrt{\max_{h^* \in [X_\kappa]} \Pr[\collstar]} \leq \negl\,.
  \]
  Applying Lemma~\ref{lem:negl-unpred}, we deduce that the distribution ensemble $X_\kappa$ is unpredictable.
\end{proof}

Unfortunately, a merely unpredictable distribution on the exponent does not allow us to prove uncensorability. However, we can prove uncensorability if we assume the hash function maps the tag distribution to the uniform distribution $\uniform([q])$ of the exponents of $\mathbb{G}$, which is an assumption closely related to the Random Oracle. We leave the relaxation of this additional assumption for future work.

\begin{theorem}[Uncensorability]
  Let $\mathcal{T}$ be an efficiently samplable unpredictable tag distribution and $H$ be a hash function such that $\{t \gets \mathcal{T}_\kappa; H(t)\} \cind \uniform([q])$ where $q$ denotes the order of the group $\mathbb{G}$. Then the proof-of-burn protocol $\Pi$ of Algorithm~\ref{alg.construction-crs} is \emph{uncensorable} with respect to blockchain address protocol $\Pi_\alpha$ of Algorithm~\ref{alg.p2pk}.
\end{theorem}
\begin{proof}
  Apply Lemma~\ref{lem:ind-pres} to the computationally indistinguishable distribution ensembles $X = \{t \gets \mathcal{T}_\kappa; H(t)\}$ and $Y = \uniform([q])$ mapped through the function $f(x) = g^x$. The resulting distributions, $g^X$ and $g^Y$ are
  indistinguishable. The distribution $g^Y$ is the distribution of public keys
  generated by $\GenAddr$. As multiplication by $h$ constitutes a permutation
  of the group, the distribution $g^Y$ is identical to the distribution $h g^Y$.
  Hence $g^X$ and $h g^Y$ are indistinguishable.
\end{proof}

\noindent
\textbf{Trusted setup.}
We remark here that we \emph{do not} require a trusted setup. In particular, for the selection of the protocol parameters, we do not generate a Common Reference String $g^y$ by selecting a random $y$ and computing $g^y$, as this would require ensuring $y$ is destroyed. Instead, we select a random group element $h$ directly, which is possible in many finite groups. As an example of such a construction in practice, a point can be selected on the secp256k1 elliptic curve by starting with an $X$ coordinate corresponding to a well-known number such as $X = \SHA($``Whereof one cannot speak, thereof one must be silent''$)$ and incremented until a solution of the elliptic curve equation exists for $Y$, then taking the positive such $Y$ and using the point $h = (X, Y)$.

\noindent
\textbf{Perturbation of group element labels.}
Yet another scheme that can potentially realize the above properties is the burn
address generation by evaluating $(g^{H(t)}) + 1$, where the $+1$ does not pertain to
the group operation, but operates on the label of the group element. For
example, in the primed order group $\mathbb{Z}_p^*$, the $+1$ operation can be taken to be literally
the next integer. Such a scheme is clearly correct and binding. Its
uncensorability is comparable to our above scheme. Lastly, its unspendability,
given appropriate restrictions ($t \neq 0$) seems to intuitively hold: It is
hard to know the logarithm of both a group element and its next. Whether this is
provable in the Generic Group Model or using appropriate hardness assumptions is
left for future work.