A - Building Blocks: PoSpace, VDFs and Signatures
In this section we sketch the main building blocks used in the blockchain: unique digital signatures, proofs of space [DFKP15; AAC+17] and verifiable delay functions [Pie19b; BBBF18; Wes20]. The definitions are not fully general, but instead tailored to the particular constructions of PoSpace from [AAC+17] and the VDFs [Pie19b; BBBF18; Wes20] based on sequential squaring.
A.1 (Unique) Digital Signatures
A digital signature scheme is specified by three algorithms; a (probabilistic) key-generation algorithm , a signing algorithm and a verification algorithm . We assume the standard security notion (unforgeability under chosen message attacks) and perfect completeness, that is, a correctly generated signature will always verify:
uses signatures in the foliage (to chain foliage blocks and to bind them to the trunk) and also in the trunk (so only the farmer can compute the challenge). To avoid grinding attacks, the signatures used in the trunk must be unique, that is for every (this includes maliciously generated public keys) and message there can be at most one accepting signature
A.2 (Unique) Proofs Of Space
A.2.1 Algorithms for PoSpace
A proof of space is specified by the four algorithms given below
on input a space parameter (where is some set of valid parameters) and a unique identifier (we use to denote the identifier as in it will be the public key of a signature scheme) outputs1
Here is the large file of size the prover needs to store. We also keep as part of as it will be convenient.
on input and a challenge outputs a proof
Here is the actual proof, the other entries in are just convenient to keep around.
on input a proof outputs or
We assume perfect completeness
A.2.2 Security of PoSpace
We will not give the formal security definition for PoSpace here, but informally it states that an adversary who stores a file of size significantly less than bits should not be able to produce a valid proof for a random challenge unless he invests a significant amount of computation (ideally close to what it costs to run the full initialization ). Moreover it must be impossible to amortize space, that is, initializing space for different identities must require times as much space.
To prevent grinding attacks, we need our PoSpace to be unique as defined below.
A.2.3 Unique PoSpace
A PoSpace is unique if for any identity and any challenge there is exactly one proof, i.e.,
We call a PoSpace weakly unique if the expected number of proofs is close to , i.e.,
For weakly unique PoSpace we assume that whenever there is more than one proof for a given challenge which passes verification, outputs all of them.
The [AAC+17] PoSpace used in is only weakly unique. To be able to focus on the main challenges, we will nonetheless assume a unique PoSpace when analyzing but our analysis can be extended without major difficulties to handle weakly unique PoSpace, things just get a bit more messy.
A.2.4 The [AAC+17] PoSpace
We give a very high level outline of the PoSpace from [AAC+17]. The space parameter is given implicitly by a value , the actual space required is approximately bits (e.g. for that's terabytes). Let denote the set of bit strings. Below we denote with the bit prefix of a string .
The identity together with a hash function defines two functions as
Note that if we model as a random function, then are also random functions. On a challenge the prover must answer with a tuple
if it exists. In this construction, for roughly a fraction of the challenges there will be at least one proof, and the expected number of proofs is (so it is a weakly unique PoSpace).
The prover will generate and store two tables so they can efficiently generate proofs. They first compute and store a table with the values sorted by the 2nd entry. With this table, the prover can now efficiently enumerate all tuples where and to generate a table containing all triples ; the expected number of such triples is . This table is then sorted by the thrid value. Now given a challenge one can efficiently look up proofs in the second table as it is sorted by the values. Storing the second table requires bits, and this can be brought down to bits by encoding it in a more clever way.
is based on this PoSpace, but to further minimize the effect of time/space trade-offs (where a malicious farmer tries to save on space at the cost of doing more computations), a nested version of this construction is used. We omit the details in this writeup.
A.3 Verifiable Delay Functions
The definition of verifiable delay functions (VDFs) given below is not completely general, but makes some additional properties of VDF we'll need in explicit. In particular, we want a VDF where the sequential computation can start before we know the number of sequential steps for which it will run, while still being able to output proofs reasonably fast at any point during the sequential computation. This similar to the functionality provided by continuous VDFs [@Ephraim2020], which require that one can provide proofs for intermediate values almost immediately. We can allow some slack, and thus can use "normal" practical VDF constructions. We'll use the following notation to an (ongoing or finished) VDF computation
the challenge (usually one or more unpredictable values) used for this VDF
total number of sequential steps performed
For we let denote the state of the VDF after sequential steps, and
denotes the value after steps.
is a proof certifying that is correctly computed.
We'll denote the value and proof for the last value as
The functions defining a VDF are
on input a challenge samples the initial value and outputs a partial VDF value
the function doing one step of the sequential computation
on input a challenge and time parameter outputs a proof
and runs in (not much more than) sequential steps (what a step is depends on the particular VDF). Here is the output and is a proof that has been correctly computed. For convenience we also keep as part of .
We have perfect completeness
The two security properties we require are
uniqueness: It is hard to come up with any statement and an accepting proof for a wrong output. More precisely, it is computationally difficult to find any where for we have
Note that we only need (but not ) to be unique, i.e., the proof showing that is the correct value can be malleable. This seems sufficient for all applications of VDFs, but let us mention that in the [Pie19b; Wes20] VDFs discussed below also is unique.
sequentiality: Informally, sequentiality states that for any , an adversary who makes less than sequential steps will not find an accepting proof on a random challenge. I.e., for some tiny
Let us stress that is only bounded by the number of sequential steps, but they can use high parallelism. Thus the VDF output cannot be computed faster by adding parallelism beyond what can be used to speed up a single step of the VDF computation.
A.3.1 The [Pie19b, Wes20] VDFs
The VDFs proposed in [Pie19b; Wes20] (see [BBBF18a] for an overview of those constructions) are both based on squaring in a group of unknown order, for concreteness let the group be where is the product of two large primes . On input one would first map the challenge on a group element, say as , and the output is with . This can be computed by squaring sequentially times , and it is conjectured that there is no shortcut to this computation if one doesn't know the factorization of .
The VDFs from [Pie19b; Wes20] differ in how the proof that certifies that is defined. The proof in [Pie19b] is shorter ( vs. elements), but soundness of the proof requires an additional assumption (that taking random roots is hard).
If one uses an RSA group as above, a trusted setup or a multiparty computation is needed to sample the modulus in a way that nobody learns its factorization. As this sampling is expensive, one would then think of as a public parameter to be used indefinitely.
Wesolowski [Wes20] suggests using the class group of an imaginary quadratic field as the underlying group of unknown order. These groups can be obliviously sampled -- this means given random bits one can sample a group without learning its order -- and thus there is no need for a trusted setup. On the other hand, it's somewhat tricky to obliviously sample random group elements in class groups (here obliviously means in a way that does not reveal the discrete log of the element). Thus in the class group setting we can let sample a fresh group using the challenge , and then exponentiate a fixed easy to find group element (concretely the element (a=2, b=1)). This is the approach taken in .
- The first constructions of PoSpace from [DFKP15] were based on depth-robust graphs. The initialization phase in these PoSpace was not just a function as it is here, but an interactive protocol. The definition we give here captures the [AAC+17] PoSpace (which was developed for ) where the initialization phase is non-interactive, this makes its use in a blockchain design much simpler. The Spacemint [PKF+18] proposal is using graph-based PoSpace and because of that must bootstrap the blockchain itself to make initialization non-interactive: farmers must post a commitment to their space to the blockchain via a special type of transaction before it can be used for farming. Without this, Spacemint would succumb to grinding attacks (on the message send to the verifier during the initialization phase).↩