A - Building Blocks: PoSpace, VDFs and Signatures
In this section we sketch the main building blocks used in the 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, a signing algorithm μ←Sig.sign(sk,m) and a verification algorithm 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,wherePr[Sig.verify(pk,m,μ)=accept]=1(pk,sk)←Sig.keygen ; μ←Sig.sign(sk,m) .
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 pk (this includes maliciously generated public keys) and message m there can be at most one accepting signature
∀pk,m, (Sig.verify(pk,m,μ)=accept)∧(Sig.verify(pk,m,μ′)=accept)⇒(μ=μ′) .
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
on input a space parameter N∈N (where N⊂Z+ is some set of valid parameters) and a unique identifier pk (we use pk to denote the identifier as in Chia it will be the public key of a signature scheme) outputs1
S=( S.Λ , S.N=N , S.pk=pk)←PoSpace.init(N,pk)
Here S.Λ is the large file of size ∣S.Λ ∣≈N the prover needs to store. We also keep N,pk as part of S as it will be convenient.
PoSpace.prove
on input S and a challenge c∈{0,1}w outputs a proof
σ=( σ.π ,σ = σ.N=S.N , σ.pk=S.pk , σ.c=c ) ←PoSpace.prove(S,c)
Here σ.π is the actual proof, the other entries in σ are just convenient to keep around.
PoSpace.verify
on input a proof σ outputs accept or reject
PoSpace.verify(σ)∈{reject,accept} .
We assume perfect completeness
∀N∈N,c∈{0,1}w, Pr[PoSpace.verify(σ)=accept]=1 where S←PoSpace.init(N,pk) and σ