跳到主要内容

A - Building Blocks: PoSpace, VDFs and Signatures

In this section we sketch the main building blocks used in the Chia\textsf{Chia} 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 Sig.keygen{{\sf Sig.keygen}}, a signing algorithm μSig.sign(sk,m)\mu\gets {{\sf Sig.sign}}(sk,m) and a verification algorithm Sig.verify{{\sf Sig.verify}}. We assume the standard security notion (unforgeability under chosen message attacks) and perfect completeness, that is, a correctly generated signature will always verify:

m,Pr[Sig.verify(pk,m,μ)=accept]=1where(pk,sk)Sig.keygen ; μSig.sign(sk,m) .\begin{aligned} \forall m,&& \Pr[{{\sf Sig.verify}}(pk,m,\mu)={\sf accept}]=1\\ \textrm{where}&&(pk,sk)\gets{{\sf Sig.keygen}}\ ;\ \mu\gets{{\sf Sig.sign}}(sk,m)~. \end{aligned}

Chia\textsf{Chia} 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 pkpk (this includes maliciously generated public keys) and message mm there can be at most one accepting signature

pk,m, (Sig.verify(pk,m,μ)=accept)(Sig.verify(pk,m,μ)=accept)(μ=μ) .\forall pk,m,\ ({{\sf Sig.verify}}(pk,m,\mu)={\sf accept})\wedge ({{\sf Sig.verify}}(pk,m,\mu')={\sf accept})\Rightarrow (\mu=\mu')~.

A.2 (Unique) Proofs Of Space

A.2.1 Algorithms for PoSpace

A proof of space is specified by the four algorithms given below

PoSpace.init\textsf{PoSpace.init}

on input a space parameter NNN\in{\cal N} (where NZ+{\cal N}\subset \mathbb{Z}^+ is some set of valid parameters) and a unique identifier pkpk (we use pkpk to denote the identifier as in Chia\textsf{Chia} it will be the public key of a signature scheme) outputs1

S=( S.Λ , S.N=N , S.pk=pk)PoSpace.init(N,pk)S=(\ S.\Lambda\ ,\ S.N=N\ ,\ S.pk=pk)\gets {\sf PoSpace.init}(N,pk)

Here S.ΛS.\Lambda is the large file of size S.Λ N\lvert S.\Lambda\ \rvert \approx N the prover needs to store. We also keep N,pkN,pk as part of SS as it will be convenient.

PoSpace.prove\textsf{PoSpace.prove}

on input SS and a challenge c{0,1}wc\in \{0,1\}^w outputs a proof

σ=( σ.π ,σ = σ.N=S.N , σ.pk=S.pk , σ.c=c ) PoSpace.prove(S,c)\sigma=(\ \sigma.\pi\ , \sigma\ = \ \sigma.N=S.N\ ,\ \sigma.pk=S.pk\ ,\ \sigma.c=c\ )\ \gets {\sf PoSpace.prove}(S,c)

Here σ.π\sigma.\pi is the actual proof, the other entries in σ\sigma are just convenient to keep around.

PoSpace.verify\textsf{PoSpace.verify}

on input a proof σ\sigma outputs accept{\sf accept} or reject{\sf reject}

PoSpace.verify(σ){reject,accept} .{\sf PoSpace.verify}(\sigma)\in \{{\sf reject},{\sf accept}\}\ .

We assume perfect completeness

NN,c{0,1}w, Pr[PoSpace.verify(σ)=accept]=1 where SPoSpace.init(N,pk) and σPoSpace.prove(S,c)\begin{aligned}&&\forall N\in{\cal N},c\in\{0,1\}^w, \ \Pr[{{\sf PoSpace.verify}}(\sigma)={\sf accept}]=1\textrm{ where }\\&&S\gets{\sf PoSpace.init}(N,pk) \textrm{ and } \sigma\gets{{\sf PoSpace.prove}}(S,c)\end{aligned}

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 NN 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 PoSpace.init(N,pk){\sf PoSpace.init}(N,pk)). Moreover it must be impossible to amortize space, that is, initializing space for m>1m>1 different identities must require mm 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 pkpk and any challenge cc there is exactly one proof, i.e.,

N,pk,c,{σ : (PoSpace.verify(σ)=accept)((σ.N,σ.pk,σ.c)=(N,pk,c))}=1\begin{aligned} &\forall N,pk,c,\\ &\left|\{\sigma\ :\ \left({{\sf PoSpace.verify}}(\sigma)={\sf accept}\right)\wedge \left( (\sigma.N,\sigma.pk,\sigma.c)=(N,pk,c)\right)\}\right|= 1 \end{aligned}

We call a PoSpace weakly unique if the expected number of proofs is close to 11, i.e.,

N,pk,c,Ec{0,1}w[{σ:(PoSpace.verify(σ)=accept})((σ.N,σ.pk,σ.c)=(N,pk,c))]1\begin{aligned} &\forall N,pk,c,\\ &{\mathrm E}_{c\gets \{0,1\}^w}\left[|\{\sigma : \left({{\sf PoSpace.verify}}(\sigma)={\sf accept}\} \right) \wedge \left((\sigma.N,\sigma.pk,\sigma.c)=(N,pk,c)\right) |\right]\\ &\approx 1 \end{aligned}

For weakly unique PoSpace we assume that whenever there is more than one proof for a given challenge which passes verification, PoSpace.prove(S,c){\sf PoSpace.prove}(S,c) outputs all of them.

The [AAC+17] PoSpace used in Chia\textsf{Chia} is only weakly unique. To be able to focus on the main challenges, we will nonetheless assume a unique PoSpace when analyzing Chia\textsf{Chia} 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 Z+\ell\in\mathbb{Z}^+, the actual space required is approximately N22N\approx \ell\cdot 2\cdot 2^{\ell} bits (e.g. for =40\ell=40 that's 1010 terabytes). Let L:={0,1}L:=\{0,1\}^\ell denote the set of \ell bit strings. Below we denote with XX_{|\ell} the \ell bit prefix of a string XX.

The identity id:=pkid:=pk together with a hash function H{\sf H} defines two functions f:LL,g:L×LLf: L\rightarrow L, g:L\times L\rightarrow L as

f(x)=H(id,x)andg(x,x)=H(id,x,x) .f(x)={\sf H}(id,x)_{|\ell}\quad\textrm{and}\quad g(x,x')={\sf H}(id,x,x')_{|\ell} \ .

Note that if we model H{\sf H} as a random function, then f,gf,g are also random functions. On a challenge yLy\in L the prover must answer with a tuple

id,(x,x) where xx,f(x)=f(x),g(x,x)=yid,(x,x')\qquad\textrm{ where }\qquad x\neq x', f(x)=f(x'), g(x,x')=y

if it exists. In this construction, for roughly a (11/e)0.632(1-1/e)\approx 0.632 fraction of the challenges yLy\in L there will be at least one proof, and the expected number of proofs is 11 (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 (x,f(x))(x,f(x)) sorted by the 2nd entry. With this table, the prover can now efficiently enumerate all tuples (x,x)(x,x') where xxx\neq x' and f(x)=f(x)f(x)=f(x') to generate a table containing all triples (x,x,y=g(x,x))(x,x',y=g(x,x')); the expected number of such triples is L=2|L|=2^\ell. This table is then sorted by the thrid value. Now given a challenge yy one can efficiently look up proofs in the second table as it is sorted by the yy values. Storing the second table requires 3Llog(L)=2+1\approx 3|L|\log(|L|)=2^{\ell+1}\ell bits, and this can be brought down to 2Llog(L)\approx 2|L|\log(|L|) bits by encoding it in a more clever way.

Chia\textsf{Chia} 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 Chia\textsf{Chia} 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 τ\tau

τ.c{0,1} ⁣:\tau.c \in \{0,1\}^* \colon the challenge (usually one or more unpredictable values) used for this VDF

τ.tN ⁣:\tau.t \in \N \colon total number of sequential steps performed

For i : 0 iτ.ti\ :\ 0\ \le i \le \tau.t we let τ[i]\tau[i] denote the state of the VDF after ii sequential steps, and

τ[i].xX ⁣:\tau[i].x\in {\cal X}\colon denotes the value after ii steps.

τ[i].π ⁣:\tau[i].\pi \colon is a proof certifying that τ[i].x\tau[i].x is correctly computed.

We'll denote the value and proof for the last value as

τ.y=defτ[τ.t].xτ.π=defτ[τ.t].π\tau.y \stackrel{\scriptsize \sf def}{=}\tau[\tau.t].x\qquad \tau.\pi\stackrel{\scriptsize \sf def}{=}\tau[\tau.t].\pi

The functions defining a VDF are

VDF.sample\textsf{VDF.sample}

on input a challenge c{0,1}c\in\{0,1\}^* samples the initial value xx and outputs a partial VDF value

τ.t:=0 , τ[0].x:=x , τ.c:=c\tau.{\sf t}:=0\ ,\ \tau[0].{\sf x}:=x\ ,\ \tau.{\sf c}:=c

VDF.next\textsf{VDF.next}

XX{\cal X}\rightarrow {\cal X} the function doing one step of the sequential computation

VDF.solve\textsf{VDF.solve}

on input a challenge c{0,1}c\in\{0,1\}^* and time parameter tZ+t\in\mathbb{Z}^+ outputs a proof

τ=( τ.y , τ.π , τ.x , τ.c=c , τ.t=t )VDF.solve(c,t)\tau=(\ \tau.y\ ,\ \tau.\pi\ ,\ \tau.x\ ,\ \tau.c=c\ ,\ \tau.t=t\ )\gets {\sf VDF.solve}(c,t)

and runs in (not much more than) tt sequential steps (what a step is depends on the particular VDF). Here τ.y\tau.y is the output and τ.π\tau.\pi is a proof that τ.y\tau.y has been correctly computed. For convenience we also keep (c,t)(c,t) as part of τ\tau.

VDF.verify\textsf{VDF.verify}

on input τ\tau outputs accept{\sf accept} or reject{\sf reject}.

VDF.verify(τ){reject,accept}{\sf VDF.verify}(\tau)\in \{{\sf reject},{\sf accept}\}

Verifying must be possible in t\ll t steps, for existing VDFs verification just takes log(t)\log(t) [Pie19b] or even constant [Wes20] time.

We have perfect completeness

t,c : VDF.verify(VDF.solve(c,t))=accept\forall t,c\ :\ {{\sf VDF.verify}}({{\sf VDF.solve}}(c,t))={\sf accept}

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 τ\tau' where for τVDF.solve(τ.c,τ.t)\tau\gets {\sf VDF.solve}(\tau'.c,\tau'.t) we have

VDF.verify(τ)=accept and τ.yτ.y .{\sf VDF.verify}(\tau')={\sf accept}\quad\textrm{ and }\quad\tau.y\neq \tau'.y\ .

Note that we only need τ.y\tau.y (but not τ.π\tau.\pi) to be unique, i.e., the proof τ.π\tau.\pi showing that τ.y\tau.y 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 τ.π\tau.\pi is unique.

sequentiality: Informally, sequentiality states that for any tt, an adversary A{\cal A} who makes less than tt sequential steps will not find an accepting proof on a random challenge. I.e., for some tiny ϵ\epsilon

Pr[VDF.verify(τ)=accept  τ.c=c  τ.t=t : crand{0,1}w,τA(c,t)]ϵ\hspace{-1cm} \Pr[{\sf VDF.verify}(\tau)={\sf accept}\ \wedge \ \tau.c=c\ \wedge\ \tau.t=t \ :\ c\stackrel{rand}{\gets}\{0,1\}^w,\tau\gets{\cal A}(c,t)]\le \epsilon

Let us stress that A{\cal A} 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 ZN\mathbb{Z}_N^* where N=pqN=pq is the product of two large primes p,qp,q. On input VDF.solve(c,t){\sf VDF.solve}(c,t) one would first map the challenge cc on a group element, say as xc:=hash(c)modNx_c:= hash(c)\bmod N, and the output is (y,π)(y,\pi) with y=xc2tmodNy=x_c^{2^t}\bmod N. This yy can be computed by squaring xcx_c sequentially tt times xcxc2xc22xc2tx_c\rightarrow x_c^2\rightarrow x_c^{2^2}\rightarrow \cdots \rightarrow x_c^{2^t}, and it is conjectured that there is no shortcut to this computation if one doesn't know the factorization of NN.

The VDFs from [Pie19b; Wes20] differ in how the proof π\pi that certifies that y=xc2tmodNy=x_c^{2^t}\bmod N is defined. The proof in [Pie19b] is shorter (11 vs. log(T)\log(T) 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 NN in a way that nobody learns its factorization. As this sampling is expensive, one would then think of NN 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 VDF(c,t){\sf VDF}(c,t) sample a fresh group using the challenge cc, and then exponentiate a fixed easy to find group element (concretely the element (a=2, b=1)). This is the approach taken in Chia\textsf{Chia}.

Footnotes

  1. 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 Chia\textsf{Chia}) 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).