isovdf.tex

\documentclass{article}

\usepackage[american]{babel}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{tikz}
\usepackage{amsmath,amsthm,amsfonts}
\usepackage{unicode}
\usepackage{hyperref}
\hypersetup{
	unicode=true,
	colorlinks=true,
	citecolor=blue!70!black,
	filecolor=black,
	linkcolor=red!70!black,
	urlcolor=blue,
	pdfstartview={FitH},
}


\newtheorem*{rawnamedtheorem}{\therawnamedtheorem}
\newcommand{\therawnamedtheorem}{\error}
\newenvironment{namedtheorem}[1]{\renewcommand{\therawnamedtheorem}{#1}
   \begin{rawnamedtheorem}}
  {\end{rawnamedtheorem}}

\newcommand{\Z}{\mathbb{Z}}

\newcommand\mathperiod{.}
\newcommand\mathcomma{,}


\DeclareMathOperator{\Gen}{\mathsf{Gen}}
\DeclareMathOperator{\Eval}{\mathsf{Eval}}
\DeclareMathOperator{\Verif}{\mathsf{Verif}}
\DeclareMathOperator{\ek}{\mathsf{ek}}
\DeclareMathOperator{\vk}{\mathsf{vk}}
\DeclareMathOperator{\poly}{\mathsf{poly}}
\DeclareMathOperator{\polylog}{\mathsf{polylog}}

\title{Why VDFs from isogenies are so cool}
\author{Jeffrey Burdges, Luca de Feo}
\date{}

\begin{document}

\maketitle

\begin{abstract}
  Verfiable Delay Functions are a relatively new cryptographic
  construction, popular in the cryptocurrency space. Only a handful of
  constructions is known, and among those isogeny-based ones are the
  youngest.

  The aim of this document is to highlight some unique features of
  isogeny VDFs that may make them preferable over competitors, in some
  instances.

  We believe that both algorithmic and hardware optimisations for an
  isogeny VDF yield wide ranging benefits unachievable with RSA.
\end{abstract}


\section{Intro}

A Verifiable Delay Function (VDF) is a function $f: X → Y$ from some
space $X$ to some space $Y$ such that, given a random input $x ∈ X$,
it is ``slow'' to evaluate $f(x)$, whereas for any $(x,y) ∈ X×Y$
verifying that $f(x) = y$ can be done ``fast''.

At first blush\footnote{At least 50\% of the authors of this note have
  thought this on first seeing the definition.} this may look similar
to the definition of the NP complexity class, however an important
requirement for VDFs is that evaluation takes a set amount $T$ of
\emph{sequential} time, i.e., that with high probability computing
$f(x)$ takes $T$ ``elementary steps'', regardless of the amount of
parallel processors the evaluator has at its disposal.  This makes
designing good VDFs somewhat hard, and explains why only a handful of
constructions is known.

Formally, a VDF is a family of functions characterised by three
parameters:
a \emph{security parameter} $λ$, e.g., $λ=128$,
a \emph{delay time parameter} $T$, and
an \emph{adversary advantage bound} $A$. 
We expect $T$ and $A$ to be independent%
\footnote{Formally, it is required that $T\in o(2^λ)$ for the
security definitions to make sense. %
In practice, $T$ will be bounded by a value to be determined
through applied cryptanalysis, however this value will typically
be large enough that it is irrelevant in applications.} from $λ$,
but not from one another.

Our VDF is determined by three algorithms:
\begin{enumerate}
\item A \emph{parameter generation} scheme $\Gen(λ,T)→(\ek,\vk,A)$,
  that takes as inputs $λ$ and $T$, and returns a pair of
  \emph{public parameters} called the \emph{evaluation} and
  \emph{verification} key, and the bound on adversaries' advantage. 
  The keys define, among other things, the input and output sets
  $X,Y$.

  $\Gen$ runs in time $\poly(λ)$, but some
  authors~\cite{cryptoeprint:2019:166} relax this to
  $\poly(λ,T)$.  
  Also $\Gen$ can be a \emph{trusted setup} protocol that
  depends upon one of many parties being honest.  

\item An \emph{evaluation} routine $\Eval(\ek,x)→(y,π)$ that takes as
  input the evaluation key and the input $x ∈ X$, and outputs $y ∈ Y$
  and a (possibly empty) \emph{proof} $π$ for the verification routine.

  $\Eval$ should run in \emph{sequential time} bounded by $T$. 

  We assume adversaries have ``poor'' odds to find a valid $y$
  such that $(y,\cdot) = \Eval(\ek,x)$ in \emph{parallel time} less
  than $T/A$.
  We cannot formally ask that adversaries have only negligible odds
  here because residue number systems give an unbounded $A$ for an
  exponential increase in parallelism in somewhat plausible 
  computational models \cite{BernsteinSorenson07}.
  % https://twitter.com/hashbreaker/status/1131192651338829825

\item A \emph{verification} routine $\Verif(\vk,x,y,π)→\{0,1\}$ that
  takes as input the verification key, an input $x ∈ X$, an
  output $y ∈ Y$ and a (possibly empty) proof $π$, and outputs $1$
  if $(y,\cdot) = \Eval(\ek,x)$, except for odds negligible in $λ$.

  We require $\Verif(\vk,x,y',π) = 0$, except for odds negligible
  in $λ$, whenever $(y,\cdot) = \Eval(\ek,x)$ for some $y \ne y'$,
  which nearly requires $\Eval$ project to a function. 

  $\Verif$ must run in time $\poly(λ)$.
\end{enumerate}

We refer
to~\cite{Boneh,Wesolowski,Pietrzak,survey,cryptoeprint:2019:166} for
various formal security definitions. %
Here, we are chiefly interested in the practical aspects of VDFs, with
a view towards real-world deployments of isogeny-based VDFs.

\paragraph{Applications of VDFs}
To better understand the design choices and constraints of VDFs, 
it is useful to have a picture of what they may be used for. %

A basic example is a \emph{distributed lottery}, where a set of
mutually distrusting participants want to agree on a common random
winning ticket, in such a way that none of the participants can
influence the output in its favor. %
A solution involving a VDF is the following: 
in a \emph{ballot casting} phase, the participants submit
\emph{ballots} $a_1,\ldots,a_n$ of their own choice; 
when this first phase is complete, all the ballots are combined using
a hash function $H(a_1,\dots,a_n) = x ∈ X$, then the winning ticket
is determined by the value $y = \Eval(\ek,x)$ output by the VDF. %
The winning ticket can be computed by a single participant, who then
publishes it; once the winning ticket is known, everyone can then
verify it by running the VDF verification routine.

A malicious participant wishing to influence the lottery may wait
for all other participants to submit their ballots, say
$a_1,\dots,a_{n-1}$, then try many different values for $a_n$ until
he finds one that makes him win. %
The role of a VDF is to prevent this attack:  if our VDF is set up
so that $T/A$ exceeds the duration of the ballot casting phase,
then malicious participants do not have enough time to try multiple
values for its ballot $a_n$, and will therefore not be able to
influence the lottery outcome.

Realistically, the ballot casting phase could last one to several
minutes. %
It is clear that, in order to appropriately determine the VDF
parameters, one must have detailed figures for the speed of the
$\Eval$ procedure, not only in software, but also on dedicated
hardware. %
This where the \emph{sequentiality} requirement plays a role: by
postulating that $\Eval$ cannot be run more efficiently than by
executing $T$ \emph{elementary steps} in sequence, the security
analysis is reduced to evaluating the speed of the fastest design
achievable for one step (given assumptions on the limits of chip
manufacturing technology, and on the resources that the dishonest
participant is willing to spend). %
We will discuss sequentiality in depth in
Section~\ref{sec:performance}.

\paragraph{VDF candidates based on groups of unknown order}
Only a handful of candidate VDF constructions do exist. %
We briefly describe here the two most popular designs, based on
repeated squaring in groups of unknown
order~\cite{Wesolowski,Pietrzak}, as they represent the benchmark to
beat; for older proposals, see~\cite{Boneh}.

TODO

\paragraph{VDF candidate from isogenies of supersingular curves}
The latest candidate VDF is based on chained evaluations of degree $2$
isogenies of supersingular curves~\cite{cryptoeprint:2019:166}. %
The goal of this document is to compare it to previous VDF proposals,
and highlight the features that may give it an edge over its
competitors.

TODO



\section{Performance of $\Eval$ and sequentiality}
\label{sec:performance}

We start by discussing the sequentiality claims of the previously
mentioned VDFs. %

Informally, sequentiality states that $\Eval$ is composed of $T$
\emph{elementary steps} in sequence, and that realistic computer 
designs cannot compute the output faster than by computing $T/A$
steps in sequence. %

Formally, sequentiality requires fixing a computational model
(e.g., parallel Turing machines, Boolean circuits, \dots), but this
is problematic since different models can produce different answers. 
We stress that sequentiality is only a security assumption, like the
hardness of factoring or that of computing discrete logarithms, and
can only be trusted on the basis of repeated cryptanlytic efforts.

Pragmatically, the sequential character of a candidate is determined
through applied cryptanalysis: investing in hardware and software
design to produce the most efficient implementation of $\Eval$,
given current knowledge, and use the results as a basis for setting
parameters. %
The result can be expressed as the conjectural bound $A$, such that
if the fastest honest evaluator can evaluate the VDF in time $T$ then
no adversary can evaluate our VDF in time $T/A$.  We always have some
lower bound on $T/A$ in practice, so a smaller $A$ makes evaluating
the VDF cheaper.

We choose VDF designs to create a cost divide among performance
optimisations.  We want some reasonable optimisations to have
relatively inexpensive development and deployment costs, while
all other optimisations look cost prohibitive, even for well funded
adversaries.

As an example, we do tentatively want hardware optimisations for
any deployed VDF, probably an FPGA or maybe even an ASIC, while we
exclude exotic computation techniques like super-conducting computing.

At the same time, we require any VDF to track newly discovered
optimisations as well.  We should thus favor VDFs for which expected
optimisations interact well with research and other applications.
In this vein, we worry about the implications of optimisations that
benefit only the VDF use case, including ASICs.

\subsection{Hardware}

An isogeny VDF works by evaluating isogenies between elliptic curves
using Velu's formulas.  In these calculations, we work with elements
in a prime field $\Z/p\Z$ and some low degree field extensions. 
We need a prime $p$ roughly half the size of a 3072 but RSA composite
with a similar 128 bit security level, or about 3/4ths the size of the
current 2048 bit RSA VDF proposal with 112 bits of security.

At present, RSA based VDFs appear simplest to implement in hardware
because they only require a squaring operation. % TODO: True??
% Justin Drake https://ethresear.ch/t/minimal-vdf-randomness-beacon/3566 or maybe something else from https://vdfresearch.org
In the isogeny VDF, we need more involved computations with these
large field elements than merely the squarings required by RSA. 

Yet, there are wide ranging benefits to fast arithmetic in large
prime fields, or even full isogeny calculations.  We must target
FPGAs first anyways, so our development effort would therefore
benefit other important cryptographic protocols:
 
Recursive zkSNARKs need rather considerably smaller but still rather
large pairing friendly fields at the 128 bit security level. 
There remain diverse opinions on field sizes for pairning friendly
curves for use even with non-recursive zkSNARKs, with some growing
largish, but regardless prover and verifier time for zkSNARKs stand
to benefit even over conventionally sized fields.  

Isogenies-based key exchanges like CSIDH \cite{10.1007/978-3-030-03332-3_15}
need somewhat smaller fields.  CSIDH supports authentication and
long-term public keys better than lattice-based key exchanges. 
Also, there are low-latency circuit-based anonymity protocols like Tor,
for which lattice-based key exchange provide post-quantum security,
but such protocols are vulnerable to correlation attacks. 
Avoiding correlation attacks requires more asynchronous cryptography,
like in the Sphinx mixnet packet format, but CSIDH fits such protocols
much better than lattice schemes.  Improved CSIDH performance could
thus dramatically improve routing in future anonymity technologies.

Isogenies schemes like CSIDH remain an interesting long-term candidate
for small post-qauntum signatures and VRFs, although current schemes
like CSI-FiSh \cite{CSI-FiSh} has no advantages over say lattice-based
schemes like Dilithium \cite{Dilithium}
% https://www.esat.kuleuven.be/cosic/csi-fish-a-new-record-class-group-computation-and-fast-isogeny-based-signatures/
% https://pq-crystals.org/dilithium/index.shtml

We think arithmetic optimisations, including FPGA designs, that favour
all these use cases together would become more accessible to all users,
and thus better track technological advances.

We also note that RISC-V and ARM chips with FPGA coprosessors exist
now, which although questionable choices for VDF evaluation, sound
like excellent options for the above use cases.
% vaguely related: https://www.youtube.com/watch?v=4hq4yiVCopU#t=28m

Among likely hardware implementation options, 
we foresee no pressing need to favor ASICs over FPGAs because highly
optimised ASICs are only about 3-4 times faster than high speed FPGAs.
% to \cite  http://www.eecg.toronto.edu/~jayar/pubs/kuon/kuontcad06.pdf via https://www.quora.com/What-are-the-differences-between-ASIC-and-FPGA?share=1

These estimates might increase for non-parallelizable computations
because an FPGA can occupy 30-40 times as much space though, or
20 times when an FPGA coprosessor for field arithmetic.
As a rule, an ASICs largest savings over an FPGA actually come in
power consumption, like 14 times or 7 times for pure an coprosessor
designs, and per unit costs.  We do not care about either
because only a handful of nodes evaluate VDFs.  

As discussed below, arithmetic can and should be parallelized,
but attempts to do so using GPUs have mostly failed due to GPUs poor
performance for the few non-parallel parts of reductions.  
We do note such work focussed largely on RSA not fields of specially
crafted large prime order though.

\subsection{Memory}

We accelerate isogenies VDFs by using intermediate curve coefficients
precomputed during a previous slower run, which depends upon memory
latency.  We suggest however that memory latency provides a latency
target for the arithmetic parallelization discussed below.

TODO:  Memory bandwidth estimates?  Where?

In principle, an attacker might recompute these coefficients just in
time.  Yet, these precomputations have greater circuit depth, requiring
$O(T \log p)$ time as opposed to the $O(T)$ required for VDF evaluation
\cite[pp. 21]{cryptoeprint:2019:166}.  At present \cite[pp. 15]{cryptoeprint:2019:166} 
suggest $\log p \approx 1500$, but this can easily be increased.
An attacker must also do this computation in parallel, which further
increases their overhead.

Attackers who cannot keep these precomputations on the same chip remain
limited to the memory bus speed, and hence the speed of light. 
There remains a risk of attackers adding several independent busses to
different memory blocks, but this appears limited by space.

We consider this extremely promising because industrial applications
like machine learning also befit form FPGAs with high memory bandwidth.
Indeed FPGAs with memory bandwidth comparable to Intel Xeons have
existed since 2015, and 
% https://www.achronix.com/achronix-introduces-the-highest-fpga-memory-bandwidth-pcie-acceleration-board-for-data-center-applications/
modern designs incorporate arithmetic circuits directly.
% https://www.achronix.com/product/speedster7t/
% Intel has similar equipment, but not sure the links.
These are admittedly highly specialised machines, but they resemble
conventional computers far more closely than an ASICs.
We think their prevalence in industry should therefore increase
confidence in the VDF latency dramatically, especially against
exotic attackers, like super-conducting computing.

\subsection{Arithmetic}

There is an extensive literature about parallelizing modular powers
for RSA by representing numbers using the Chinese remainder theorem,
known as a residue number systems, like \cite{RNSonGPU07,Moss07,Araujo12}.
Among the strongest asymptotic results comes from \cite{BernsteinSorenson07}:

\begin{namedtheorem}{Theorem 8.1 of \cite{BernsteinSorenson07}}
There is an algorithm for the Common CRCW PRAM that, given the binary
representations of positive integers $x$, $e$, and $m$, of total bit
length $n$, computes the binary representation of $x^e \mod m$ in time
$O_\epsilon(n / \log \log n)$ using $O(n^{2+\epsilon})$ processors.
\end{namedtheorem}
% https://cr.yp.to/antiforgery/meecrt-20060914-ams.pdf


We know for example that addition modulo $N$ should have running-time
$O(\log \log \log N)$ with an optimal residue base, but only
running-time $O(\log \log N)$ with a more natural residue base of only
Mersenne primes \cite[\S4.6]{Parhami}.
There are explanation in \cite{RNSonGPU07} and \cite{Araujo12} of
doing Montgomery modular multiplication, and thus squarings, over
two distinct residue bases. 
% also https://pdfs.semanticscholar.org/0fef/478462c8f21e75364ca767b1835f3f05f267.pdf



We think these reduces confidence in any particular ASIC for RSA
squarings, especially if finding the optimal residue base for a
particular modulous proves interesting.  Also, residue number systems
require far more silicon, likely increasing ASIC costs.

In the isogenies VDF by comparison, we choose the prime field $\Z/p\Z$
of definition for our curves so that $p+1$ has a large prime factor
and a large power of two.  
We can therefore have more confidence that our arithmetic operations
provide relatively optimal performance \cite{????}.  In other words,
we know relatively optimal residue bases for working in $\Z/p\Z$ \cite{????}.

TODO: Is this correct Luca?  Explain further.  
TODO: Do Velu's formula's need anything that makes using RNS hard?

An isogenies-based VDF instead risks mathematical or algorithmic
advancements in evaluating Velu's formulas, which initially sound
much more significant than arithmetic optimisations.  We suspect
this risk might actually be lower however for several reasons:

We expect significant advancements would arise by academics improving
Velu's formulas for specialised field and curve paramaters.
Initially, the vulnerable paramaters would usually differ from the
paramaters used by our VDF, which translates into time to replace
the VDF paramaters, if appropriate.  

As above, we observe that CSIDH \cite{10.1007/978-3-030-03332-3_15} benefits enormously from
improving Velu's formulas, which translates into faster post-quantum
authentication and anonymous routing, and maybe post-quantum signatures.

\subsection{Quantum annoyance}

Any RSA scheme including an RSA based VDF is almost instantly broken
by a quantum computer. 

We say a signature scheme, VRF, or VDF is {\em quantum annoying} if
an adversary with a quantum computer can forge signatures, compute
outputs without the public key, or compute outputs very quickly
(respectively), but they must utilize the quantum computer for each
separate forgery or fast evaluation attack.
In other words, a quantum computer cannot break the public key or
paramaters once to provide information with which these attacks can
be run on a classical computer. 

As implemented, the class group VDF design appears quantum annoying
because each input yields a new class group with a different order.
There is currently no known algorithm for determining many unknown
group orders in a single batch computation or with an extensive
pre-compute, but such algorithms remain under explored.  We thus
have only a low confidence that the class group VDF is quantum annoying.

There is a VRF and signature scheme similar to our VDF in which the
isogeny $φ$ gets kept secret, and runs quickly, and the public key
is the curve $X$ and $φ G_1$.  Now our output $\sigma = φ* H_2(m)$
acts as signature and the verification equation is 
$$ e_X( φ G_1, H_2(m) ) = e_Y( G_1, \sigma ) \mathperiod $$
These schemes, and our VDF, are not post quantum because the
quantum computer can easily compute $u$ such that $u G_2 = H_2(m)$.

In principle, this VRF and signature scheme might be quantum annoying
because our quantum adversary cannot determine the isogeny itself
from merely $X$, $Y$, and many $\sigma$ however, only can find the
discrete log for each input point $H_2(m)$.

If so, there are handy properties of BLS signatures that carry over
to this VRF, like distinct message aggregation, but not other
aggregation strategies.  Also signatures are far smaller than any
known post-quantum signature scheme, while also providing competitive
verifier performance.  

There even remains a chance that quantum annoyance might hold for
our isogenies-based VDF construction.

We caution however that all these isogenies constructions using
pairings appear vulnerable to quantum pre-compute attacks, especially
in the vein of quantum analogs of batch number field sieve schemes.  
% Daniel J. Bernstein, Tanja Lange. "Batch NFS." Pages 38–58 in Selected areas in cryptography—SAC 2014—21st international conference, Montreal, QC, Canada, August 14–15, 2014, revised selected papers, edited by Antoine Joux, Amr M. Youssef. Lecture Notes in Computer Science 8781, Springer, 2014. ISBN 978-3-319-13050-7.  https://cr.yp.to/papers.html#batchnfs
% Find quantum analog of https://weakdh.org/imperfect-forward-secrecy.pdf

These precompute attacks would remain expensive in both quantum and
classical computation, like say reducing the classical security
paramater from 128 to 80 bits and making the algorithm parallel. 
In other words, we do not expect quantum annoyance for our preferred
classical paramater choices, but they do not make us a soft target
and they admit some quantum annoying paramater choices, 
unlike an RSA VDF.

We think quantum annoyance could provide a convenient stepping stone
while the threat from quantum computers increases.  In particular,
there are many consensus protocols in which VRFs or VDFs run frequently
and quickly, thus increasing the confidence derived from quantum annoyance.  

We note that deterministic hash-based signatures like Sphincs should
give fully post-quantum VRFs, but their extreme size makes them
unwieldy for consensus protocols.  We hope work on isogenies-based
signatures eventually yields more compact post-quantum VRFs too.
We do not know if lattice-based VRFs are even possible.


\section{Trusted setup}

There are several VDF designs currently under consideration, but
our two most serious candidates require a group $G$ of unknown order.
In $G$, these designs first repeatedly square some distinguished
element, while saving check point powers, and then produce a proof
that the squarings were done correctly, using the proof strategies
of either Pietrzak \cite{Pietrzak} or Wesolowski \cite{Wesolowski}.

In these proposals, the groups $G$ of unknown order has thus far been
either the class group of an imaginary quadratic order, or else an
RSA group $\Z/n\Z$ with $n = p q$ known but $p$ and $q$ unknown.

We do not require any trusted setup for the class group approach.
In fact, the group itself is normally constructed from the input,
thus avoiding precompute attacks and providing quantum annoyance.  

There is however a tricky highly synchronous MPC required to produce
an RSA modulus $n = p q$ with $p$ and $q$ unknown.  At minimum, such
a synchronous trusted setup limits participation and casts doubt on
the system's security.  

TODO: Comment on the RSA trusted setup proposed by Abhi Shelat at Ligero, as explained in ligeroRSA.pdf and  \url{https://www.youtube.com/watch?v=RwrJXO_ecRI&list=PLaM7G4Llrb7y075mVXGmSABDP9Nb_PsBq&index=7}

Isogenies VDFs require a trusted setup too because the distinguished
starting curve admits more optimisations when evaluating isogenies:
TODO: Luca please explain better.

In this trusted setup, we perform a random walks through curve $E_i$
around the specified isogeny volcano.  In sequence, each participants
producing a secret isogeny $φ_i : E_i \to E_{i+1}$ and publishes
$E_{i+1}$ along with curve points $U,V ∈ E_i$ and $X,Y ∈ E_{i+1}$
such that $e_{E_i}(U,V) = e_{E_{i+1}}(X,Y)$.  

Anyone can verify the whole trusted setup by checking all these
pairing equations.  We cannot aggregate these pairing computations
in verification, due to working on different curves.  Yet, verification
costs only two pairings per participant.

There is no synchronous MPC in this trusted setup, meaning participants
could join flexibly over an extended period of time.  We could even
resume the trusted setup anytime in the future, thereby expanding the
participant set.  After doing so, the VDF should be rerun to
regenerate its paramaters of course.

We further note that avoiding this trusted setup for isogeny starting
curves remains an active research area independent of VDFs. 
In particular, there is considerable interest in being able to hash to
{\it a} curve on an isogeny volcano.


\section{Proofs}

We foresee VDFs being applied primarily for collaborative randomness
in consensus protocols.  

\subsection{Proof ownership}

These consensus protocols commonly reward the VDF evaluator for the
CPU time, but this risks another node stealing the reward by claiming
it evaluated the VDF.  Any two evaluators produce the same VDF output
of course, but we can express ownership of the output by using
information from intermediate stages without touching the output itself.

As noted above, the VDF designs under consideration use a group $G$
of unknown order.  In $G$, these designs first repeatedly square
some distinguished element, while saving check point powers, and
then produce a proof that the squarings were done correctly, using
the proof strategies of
 either Pietrzak \cite{Pietrzak} or Wesolowski \cite{Wesolowski}.

In both designs, there is a Fiat-Shamir transform that hashes the
input $a$ and output $b = a^(2^T)$ together to select one or more
intermediate stages to reveal for the proof.  In both we simply
including the evaluator's public key into this hash to produce a
proof owned by that one evaluator.  Actually doing this requires
adjusting some security paramaters slightly, but doing so should not
harm performance. 

An isogeny VDF presents a minor challenge here because the proof
is only the output.  We therefore add a separate ownership proof
consisting of $x = o φ_{1/2} G_1$ and $y = o^{-1} φ_{1/2}* H_2(m)$
where $O = o G_1$ is the evaluator's public key and
$φ_{1/2} : Y \to Z$ and $φ_{1/2}* : X \to Z$ are isogenies to
some curve $Z$ part way along the path from $X$ to $Y$.
We may verify the public key's correctness by checking
$e_X(O, φ G_2) = e_Z(x, φ_{1/2} G_2)$ and verify the proof's correctness by
checking
$$ e_X( φ G_1, H_2(m) ) = e_Z( x, y ) = e_Y( G_1, φ* H_2(m) ) \mathperiod $$

An attacker could still produce a valid $y$ after evaluating only
$φ_{1/2}* H_2(m)$.  We not  if $Z$ could lie much further than
half way towards $Z$ so that the attackers fastest evaluation
becomes $y = φ_{1/2} φ_{1/2}* H_2(m)$.  In this, if $φ_{1/2}$ 
still delays the attackers enough then our honest evaluator wins.

\smallskip

In this vein, Justin Drake adapted Wesolowski VDF proof to provide
a ``blind'' proof \cite{}, % https://ethresear.ch/t/blinded-vdfs-and-timelocks/5494
that demonstrates having run the VDF without revealing the output.

An isogeny VDF supports blind proofs using the same trick as proof
ownership:  We set $x = o G_1$ and $y = o^{-1} φ* H_2(m)$
where $O = o G_1$ is either a blinding factor.
We verify the blind proof's correctness by checking
$$ e_X( φ G_1, H_2(m) ) = e_Y( x, y ) \mathperiod $$ %  = e_Y( G_1, φ* H_2(m) )
We could safely choose $O = o G_1$ to be the evaluator's public key,
in which case we verify $e_X(O, φ G_2) = e_Y(x, G_2)$ as well.

% Classical proof: (x₁, x₂, ...) = H(a,b)
% Ownership proof: (x₁, x₂, ...) = VRF_o(a,b) ?= H(a | b | oH'(a|b) )

\subsection{Proof composition}

We require at least one party evaluates the VDF and publishes the output, and proof if applicable.  Yet, we improve efficiency when as few parties as possible do so.  We thus want participants to know when they should spend resources on VDF evaluation.
% As a non-example, the caucus leader election protocol of fantômette \cite{fantomette} requires that every participant a run their VDF almost all the time. 

There are similar concerns that adversaries who reliably computes the VDF fastest can impact the protocol by revealing their output late.  We reduce the severity by not tuning the VDF delay automatically but instead manually tuning with experiments on known hardware.  Yet, adversaries increasing delays remains a significant threat.

We therefore propose that VDFs be evaluated in stages to provide live information about evaluation progress.  In this way, an adversary cannot delay beyond one stage without additional nodes taking over.  

We could chain evaluations with any VDF design, but we require separate proofs for stages won by different evaluators, if using either Pietrzak or Wesolowski's strategies.  We expect vagaries from block production and finality to randomize the VDF winners enough to make proof size linear in the number of stages.  We might produce proofs that combine several stages, except this makes proof productions far slower.

Isogenies VDFs provide a dramatic savings here because the proof is only the output.
$$ e_X( φ G_1, H_2(m) ) = e_{X_{1/2}}( φ_{1/2} G_1, φ_{1/2}* H_2(m) ) = e_Y( G_1, φ* H_2(m) ) \mathperiod $$


\section{Time-lock puzzles}

% https://people.seas.harvard.edu/~salil/research/timelock.pdf

There is a classical time-lock puzzle based on RSA \cite{TLP} that
amounts to running the RSA based VDF in an RSA group for which the
puzzle creator knows the trap door $p$ and $q$ of the RSA composite
$n = p q$.  

\subsection{Parallel time-locks}

There are seemingly insurmountable problems with deploying an RSA
time-lock puzzle protocol:
We need a puzzle of sufficient value to be worth solving to prevent
catastrophic denial of service attacks, but almost any realistic use
cases fail this test.  In particular, RSA time-lock puzzles are
useless for important applications like vicary auctions and voting. 
Also, if we incentivise puzzle solving then our puzzle's creator can
hijack the rewards.  

We expect some advanced RSA trusted setup MPC would permit multiple
parties to encrypt messages to an eventual decryption, but doing 
becomes extremely complex.

Isogenies VDFs solve this problem far more elegantly though:
We regard the VDF evaluation $φ* H_2(m)$ as an identity-based secret
key for an identity-based encryption scheme.  In this analogy, our
identity is the VDF's seed $m$, while our master public key is $φ G$,
and our master secret key is the isogeny $φ*$ itself.

In concrete terms, we have a party, normally a peer-to-peer network,
that agrees upon and publishes our seed $m$ and starts computing our
VDF evaluation $φ* H_2(m)$.  We trust thisparty cannot delay publishing
$m$, meaning one honest peer contribute to $m$ less than $T/A$ before
the VDF starts running in the peer-to-peer network case.
After this VDF run seeded by $m$ commences, any party Alice may create
an ephemeral secret scalar $u$, compute $s_u = e_X ( u φ G_1, H_2(m) )$,
and sends a ciphertext $(u G_1, E_{s_u}(\ldots))$ to any party Bob.
After an evaluator computes and publishes the VDF evaluation
$φ* H_2(m)$ then Bob can compute $s_u = e_Y ( u G_1, φ* H_2(m) )$ and
decrypt this ciphertext.

Importantly, our parties Alice and Bob have no involvement with
running the VDF, beyond monitoring the agreement process for $m$,
including the time when $m$ became known.  We expect the amortised
costs to Bob to be zero, either because maybe participants run one
puzzle together, or more likely because our peer-to-peer networks
evaluates the VDF for another reasons, like unbiased randomness.
Alice cannot therefore exploit the time-lock puzzles for such bad
denial of service attacks.

These free parallel time-lock puzzles have numerous applications in
distributed systems.  We obtain almsot trivial protocols for voting
and vicary auctions that provide far stronger security that existing
protocols, which mostly depend upon threshold secret sharing.
As above, all participants simply encrypt their bid or vote to our
eventual VDF evaluation $φ* H_2(m)$.  

In the auction case, we begin the auction when the VDF input $m$
becomes available, and end the auction before any VDF evaluator
computes $φ* H_2(m)$.  All bidders encrypt bids to $φ* H_2(m)$ as
above, so that all bids are revealed by the VDF evaluator computing
$φ* H_2(m)$.  Any logic may be applied to the decrypted bids,
which makes vicary auctions possible in particular.

We operate similarly in the voting case, except we achieve a secret
balot using relatively simple techniques like a reencryption mix net
or other mixing service.  We authenticate voters only when they submit
votes, which reduces or avoids zero-knowledge proof complexity.

We could support weighted votes privately using almost any techniques
adapted to the underlying ecosystem.  As an example, if vote valuations
are stored using homomorphic commitments, like in Zether or QuisQuis,
then we merely encrypt several votes values that sum to the commitment.

We might reduce the mixing service's importance if the underlying
ecosystem supports more advanced privacy features like zero-knowledge
proofs over Merkle trees, or blind signature constructions, like
rerandomizable certificates (Coconut \cite{Coconut}).
We do still benefit from simpler zero-knowledge circuits however.

% e_X ( u φ G_1, H_2(m) ) = s = e_Y ( u G_1, φ* H_2(m) )
% pk: uG
% ct: E_s(msg)

TODO: Show that game is better

\subsection{Sequential time-locks}

An RSA time-lock puzzle can ostensibly be given some extremely long
running time, like years or decades, while creating a slow isogneny
requires extensive precomputation.  An isogeny VDF can recapture the
classical time lock puzzle game easily enough, but only by sacrificing
its parallel users:

As before, Alice first selects an ephemeral secret scalar $u$ and
obtains the initial VDF seed $m_{0,u}$.  Yet, now she iteratively
computes $s_{i,u} = e_X ( u φ G_1, H_2(m_i) )$ and chooses subsequent
VDF seeds $m_{i+1,u} = H(s_{i,u})$, and finally sends the ciphertext
$(u G_1, E_{s_{k,u}}(\ldots))$ to Bob.
After Bob known $m_{i,u}$ evaluates $φ* H_2(m_{i,u})$ then he can
compute $s_{i,u} = e_Y ( u G_1, φ* H_2(m_i) )$, and find the subsequent
VDF seed $m_{i+1,u} = H(s_{i,u})$.

As $m_{i,u}$ depends upon $u$ for $i>0$, we no longer obtain parallel
time-lock puzzles from this construction, which makes it an extreme
denial of service target.  Alice can however choose $k$ as large as
she likes, subject to doing $k$ pairings herself.
We note $m_{0,u}$ may originate with some trusted source, which
prevents some attacks on RSA time-lock puzzles, like Alice stealing
rewards from an evaluator.

\subsection{Private VDF}

We believe the Caucus component of Fantomette \cite[\S5]{Fantomette}
to be only currently published scheme that uses private VDF evaluation.
We recommend against protocols like Fantomette because many concurrent
private VDF evaluations incurs environmental costs.  At the same time,
there are novel security properties obtainable through private VDF
evaluation, and they remain dramatically cheaper than proof-of-work.

We expect private VDF evaluations would run a VDF on a VRF output,
like in Fantomette.  If however the running VDF really needed to
be kept secret then the isogeny $φ*$ could be kept secret too.

As noted above, our VDF output $φ* H_2(m)$ amounts to a BLS signature,
with a secret isogeny $φ*$ replacing the secret scalar.  So our map
$m \mapsto φ* H_2(m)$ could simultaneously be both a private VDF as
well as a VRF.  

A priori, {\em verifiable delayed random function} (VDRF) or time-lock
VRF requires some heavy zkSNARK proving that $φ* : Y \to X$ incurs the
required delay by being generated correctly, and the correctness of
$X$, $Y$, $φ G_1$, and any intermediate curves revealed.  
As our zkSNARK encodes arithmetic in the base field $\Z/p\Z$,
it should operate in another pairing friendly curve whose group order
is divisible by $p$, which makes arithmetic mod $p$ relatively efficient.
We could obtain such curves using the Cocks-Pinch method, which appears
feasible thanks to the running time being polynomial in $\log p$ \cite{ordinary_cocks_pinch}.
% TODO:  Is this running time correct?  Find citation for supersingular case.


\section{Flexibility}

Isogeny VDFs inherit much of the extreme flexibility BLS signatures
possess, mostly through the various BLS aggregation strategies.

We caution that our isogeny being between supersingular elliptic
curves makes the paring not of type III, which breaks assumptions
like the Symmetric External Diffie-Hellman (SXDH) \cite{ordinary_cocks_pinch}.

\subsection{Aggregated evaluation}

We adapt the simple distinct message aggregation strategy for
BLS signatures:  If our messages $m_i$ are all distinct, then the
BLS signatures $\sigma_{i,j} = p_j H_2(m_i)$ may trivially be
aggregated as $\sigma = \sum_{i,j} \sigma_{i,j}$ and verified by
checking that $e(G_1,\sigma) = \Pi_j e(P_j, \sum_i H_2(m_i))$,
without any concerns about relationships among the public keys
$P_j = p_j G_1$.  

We rarely see distinct message aggregation of BLS signatures, due to
poor performance of multiplication in the target group.  
Yet, aggregating distinct messages yields a handy techniques for
isogeny VDFs.  We expect VDF messages to always be distinct of course,
but beyond this we may aggregate VDF evaluation itself whenever the
isogenies coinside.

As a simplified example,
we consider two isogenies $φ_0 : Y \to X_0$ and $φ_1 : X_0 \to X$
so that $φ_0*$ and $φ_0* φ_1*$ are evaluation isogenies for  % Use \circ ?/
two VDFs.  If we now start with two input messages $m_0$ and $m_1$,
then we need only evaluate $φ_0*$ to compute the aggregate evaluation
$$ \sigma = φ_0*( H_2(m_0) + φ_1* H_2(m_1) )$$
and the aggregate verification equation
$$ e(G_1,\sigma) = e(φ_0 G_1, H_2(m_0)) e(φ_1 φ_0 G_1, H_2(m_1)) \mathperiod $$
In practice, we expect $\sigma_1 = φ_1*(H_2(m_1)$ would always be
published early, so any verifiers who wished to trust the evaluation
of $φ_1*$ need only check 
$e(G_1,\sigma) = e(φ_0 G_1, H_2(m_0) + φ_1* H_2(m_1))$

In the VDF security model, our adversary has a significant advantage
$A$ in evaluate the VDF, meaning they can evaluate the VDF if time
$T/A$ where $T$ is the VDF running time.  As such, contributions to
$m_i$ only ensure security if released by contributors less than
$T/A$ before the VDF starts running.  We should therefore favor all
contributions arriving quickly in bursts

Yet, integrating a VDF with proof-of-stake block production schemes
like Ouroboros Praos naturally favours taking $m$ to be a hash of
all block production VRF outputs throughout an entire epoch. 
In this approach, only blocks released during the final $T/A$ of the
epoch secure the VDF against an adversary with advantage $A$.
As compensation, we might run roughy $A$ VDFs in parallel for $A$
epochs delay each, but $A = 128$ or even $1024$ sound plausible if
honest VDF evaluators do not possess specialised hardware.

In our simple aggregation example, we created two entry windows,
first $m_1$ and later $m_0$ with duration $T_{m_1}$ and $T_{m_0}$
respectively, into the one VDF evaluation $φ_0*$ with a long running
delay $T_{φ_0*}$.  We separate the earlier window $m_1$ from the later
window $m_0$ by another VDF evaluation $φ_1*$ with a possibly shorter
delay $T_{φ_1*}$.  Ideally, these two entry windows might halve our
required number of parallel evaluations, thus reducing our cost by a
factor of two. 

Yet, we encounter timing troubles when attempting aggregate the
evaluations of $φ_0* φ_1* H_2(m_1)$ into $φ_0* H_2(m_0)$ though:  
If an adversary has an advantage $A' < A$ against $φ_0*$, then they
could apply it to $φ_1*$ as well, in which case they again need only
control all slots in $m_0$ to bias the VDF output.  
If $2 T_{φ_1*} \leq T_{m_0}$ then this yields $2 A T_{m_1} \leq T_{m_0}$,
making $T_{m_1}$ extremely short for large $A$.  

We instead propose that different evaluation threads be aggregated
opportunistically.  Any evaluator learns one of $φ_1* H_2(m_1)$ or
$H_2(m_0)$ first, so they could begin computing say $φ_0* H_2(m_0)$
but apply delays to synchronise with $φ_0* φ_1* H_2(m_1)$ when 
$φ_1* H_2(m_1)$ arrives.  In principle, such synchronisation might
be enforced with incentives.  We acknowledge however that such a
system requires delicate tuning that takes into account the
security concerns.  

\subsection{Threshold evaluation}

In a similar vein, there exist threshold VDF constructions that
provide security so long as {\it either} the VDF security assumptions
hold, {\it or} some threshold security assumption holds. 

In an epoch, the $j$th contributor aka block producer encrypts
threshold verifiable secret shares \cite{Schoenmakers99asimple} % Stadler96publiclyverifiable
of some curve point $H_2(m_j)$ with designated VDF evaluators.
At the end of the epoch, the $i$th VDF evaluator begins computing
their share of the VDF  $φ* \sum_i \lambda_i H_2(m_i)$, where
$\lambda_i = \Pi_{j \neq i} {j \over j-i}$ are the Lagrange coefficients.

We dislike sharing secrets with distinguished parties for numerous
reasons.  Yet now, our either $j$th contributor could publish $H_2(m_j)$
somewhat early, or preferably our $i$th evaluator could reveal some
partial computation early, enabling aggregation.  In either case,
we improve liveness assurances over user threshold randomness designs.

We leave designing useful threshold VDFs for future work, but emphasise
that isogenies VDFs enable trade offs unavailable with other VDF designs. 

TODO: RandHound vs RandHerd

\bibliographystyle{alpha}
\bibliography{isovdf,isogenies_bib/isogenies}

\end{document}