Four Proof Algorithms

PPIO employs 4 different storage proofs, namely Proof of Replication (PoRep), Proof of Download (PoD), Proof of Spacetime and Light Proof of Capacity (LPoC). These proofs guarantee that the storage provider (miner) correctly replicates the data, and consistently stores the data within the agreed time period. They also ensure that user can successfully download the data any time during the agreed time period. These proofs maintain the integrity and reliability of PPIO's storage system. They will be discussed in details in this section.

Definition of terms in the section:

  • CRH: Collision-resistant Hashing, a hash function h with which it is difficult to find two different inputs xxxx', and generate the same output h(x)==h(x)h(x) == h(x').
  • MerkleCRH: The root hash of a Merkle tree built from collision resistant hashing. Merkle tree can be used as an efficient way to validate if the content of a data block matches the original data.
  • Seal: An encryption method to ensure that each copy of the data has a unique and independent representation. The encryption process should take substantially longer time than decryption, to prevent Generation Attacks. AES-256 is a viable option for its implementation.
  • Cipher: A lightweight encryption method with symmetric keys, used in Proof-of-Download. XOR Cipher is a viable option for its implementation.

Proof-of-Replication (PoRep)

Proof of Replication (PoRep) provides a way to verify that miner LL correctly replicates Data DD from User UU and stores it in its storage. The process also provides an indirect proof of the bandwidth available to LL. The procedure of PoRep is described below.

Proof-of-Replication

Proof-of-Replication

Proof-of-Replication

  1. User UU generates a Seal key PKSealPK_{Seal},applies it to encrypt Data DD, and generates a unique copy R=Seal(D,PKSeal)R=Seal(D, PK_{Seal}). It also builds a Merkle Tree on top of RR, calculates the root hash of the tree RT=MerkleCRH(R)RT=MerkleCRH(R),and sends RTRT to Verifier VV.
  2. UU transmits RR and PKSealPK_{Seal} to miner LL.
  3. LL requests PoRep challenge from VV, VV accepts the request and sends a random challenge cc to LL, i.e. it challenges the storage of the ccth data block of RR.
  4. LL retrieves RcR_{c} which is the ccth block of RR, and calculates PathRCRTPath_{RC-RT} which contains the hash values of all the Merkle tree nodes between RcR_{c} and the root node. LL returns the following to VV:
    • RcR_{c}
    • PathRCRTPath_{RC-RT}
  5. From received RcR_{c} and PathRCRTPath_{RC-RT}, VV generates the Merkle tree root hash RTRT', if RTRT' matches the original root hash received from UU, i.e. RT==RTRT' == RT, the proof has succeeded, otherwise the proof has failed.

Proof-of-Download (PoD)

Proof-of-Download (PoD) provides a way to verify that Data DD has been correctly downloaded from miner LL to User UU. The procedure of PoD is described below.

Proof-of-Download

Proof-of-Download

Proof of Download

  1. For Data DD to be downloaded, User UU sends the root hash of its Merkle tree DTU=MerkleCRH(D)DT_{U}=MerkleCRH(D) to Verifier VV.
  2. Miner LL decrypts its stored copy RR and obtains data DD. It then calculates the root hash of its Merkle tree DTL=MerkleCRH(D)DT_{L}=MerkleCRH(D).
  3. LL creates a Cipher Key PKCipherPK_{Cipher}, applies it to Data DD, and generates a ciphered copy R=Cipher(D,PKCipher)R'=Cipher(D, PK_{Cipher}). It then calculates the root hash RT=MerkleCRH(R)R'T=MerkleCRH(R'), and sends the following to VV:
    • DTLDT_{L}
    • PKCipherPK_{Cipher}
    • RTR'T
  4. VV checks whether DTUDT_{U} is identical to DTLDT_{L}. If not, the proof has failed.
  5. VV sends a random challenge cc to LL, i.e. the storage challenge of the ccth block of DD and RR'.
  6. LL retrieves DcD_{c} which is the ccth block of DD and calculates PathDCDTPath_{DC-DT} which contains the hash values of all the Merkle tree nodes between DcD_{c} and the root node. LL also retrieves RcR'{c} which is the ccth block of RR' and calculates PathRCRTPath{R'C-R'T} which contains the hash values of all the Merkle tree nodes between RcR'_{c} and the root node. It then returns the following to VV:
    • DcD_{c}
    • PathDCDTPath_{DC-DT}
    • PathRCRTPath_{R'C-R'T}
  7. From received DcD_{c} and PathDCDTPath_{DC-DT}, VV generates the Merkle tree root hash DTLDT'{L}, and verifies that DTLDT'{L} matches the root hash DTLDT_{L} previously received from LL, i.e. DTL==DTLDT'{L} == DT{L}. If not, the proof has failed.
  8. From received DcD_{c} and PKCipher)PK_{Cipher}), VV generates ciphered data block Rc=Cipher(Dc,PKCipher)R'{c}=Cipher(D{c}, PK_{Cipher}), and calculates the root hash RTR'T' using RcR'{c} and received PathRCRTPath{R'C-R'T}, and verifies that RTR'T' matches the root hash previously received RTR'T from LL, i.e. RT==RTR'T' == R'T. If not, the proof has failed.
  9. UU downloads data RR' from LL.
  10. UU requests proof of download from VV
  11. VV sends a random challenge cc to UU, i.e. the storage challenge of the ccth block of RR'.
  12. UU retrieves $R'{c} which is the ${c}th block of content on RR', and calculates $Path{R'C-R'T}, which contains the hash values of all the Merkle tree nodes between RcR'_{c} and the root node, and sends following to VV:
    • RcR'_{c}
    • PathRCRTPath_{R'C-R'T}
  13. From received RcR'{c} and PathRCRTPath{R'C-R'T}, VV generates the Merkle tree root hash RT"R'T", if RT"R'T" matches the root hash RTR'T previously received from LL, i.e. RT"==RTR'T" == R'T, the proof has succeeded, and VV sends the Cipher key PKCipherPK_{Cipher} to UU, so that UU can decipher RR' to recover data DD successfully.

Proof-of-Spacetime (PoSt)

Proof of Spacetime (PoSt) provides a way to verify that miner LL has stored Data DD for a given period of time. The process also provides an indirect proof of the storage capacity of LL. The procedure of PoSt is described below.

Proof-of-Spacetime

Proof-of-Spacetime

Proof of Spacetime

  1. As described in PoRep procedures, data DD is encrypted to obtain a unique copy RR, RR is stored on LL, its Merkle tree root hash is RT=MerkleCRH(R)RT=MerkleCRH(R).
  2. VV also stores RTRT.
  3. At a given time TT, LL requests proof of storage challenge from VV.
  4. VV sends a random challenge cc to LL, i.e. the storage challenge on ccth block of RR.
  5. LL retrieves RcR_{c} which is the ccth block of RR, and calculates PathRCRTPath_{RC-RT} which contains the hash values of all the Merkle tree nodes between RcR_{c} and the root node, and sends the following to VV:
    • RcR_{c}
    • PathRCRTPath_{RC-RT}
  6. From received RcR_{c} and PathRCRTPath_{RC-RT}, VV generates the Merkle tree root hash RTRT', and verifies that RTRT' matches the original root hash stored RTRT, i.e. RT==RTRT' == RT. If not, the proof has failed.
  7. Repeat steps 3 to 6 at given time intervals.
  8. The series of repeated successful challenges and proofs between LL and VV generates the successful proof of spacetime.

Light-Proof-of-Capacity (LPoC)

Light Proof of Capacity (LPoC) provides a way to verify the available storage capacity of miner LL. The available capacity does not include the storage space already used for existing data. PPIO's lightweight proof reduces the amount of resources wasted in conducting complicated proofs. The procedure of LPoC is broken into two phases, which are described below.

Initialization Phase

Initialization Phase of Light-Proof-of-Capacity

Initialization Phase of Light-Proof-of-Capacity

  1. VV generates a unique Directed Acyclic Graph (DAG) G=(N,E)G=(N, E) for a specific miner LL, in which N is the set of nodes in G, and E is the set of edges that connect different nodes in G.
  2. Let π(n)=n:(n,n)EnN,nN\pi(n)={n':(n',n)\in E|n'\in N, n\in N} be the set of predecessors of node n in G.
  3. Let LIDL_{ID} be the identifier of LL, let n|n| be the identifier of node nn.
  4. Let w(n)=CRH(LID,n,w(π(n))w(n)=CRH(L_{ID}, |n|, w(\pi(n)) be the hash value of node nn, in which w(π(n))=(w(n1),...,w(nM))w(\pi(n))=(w(n_{1}),...,w(n_{M})) and n1,...nMπ(n)n_{1},...n_{M} \in \pi(n)
  5. LL calculates the hash value w(n)w(n) for all the nodes in GG, and stores the values in its available storage, to prepare for challenges from VV.

Verification Phase

Verification Phase of Light-Proof-of-Capacity

Verification Phase of Light-Proof-of-Capacity

  1. At a given time TT, LL requests PoLC challenge from VV.
  2. VV choose a random node nNn \in N, and sends n|n| to LL.
  3. Based on received n|n|, LL sends its stored hash values w(π(n))w(\pi(n)) of all the nodes in π(n)\pi(n) and stored w(n)w(n) to VV
  4. From received w(π(n))w(\pi(n)), VV calculates w(n)w'(n) by the formula w(n)=CHR(LID,andn,w(π(n))w'(n)=CHR(L_{ID}, and |n|, w(\pi(n)), and verifies that w(n)w'(n) is identical to previously received w(n)w(n) from LL. If not, the proof has failed.
  5. VV randomly chooses one of the predecessors of nn, repeats steps 2 to 4, until these is no more predecessors to try in any of the predecessor sets.
  6. Repeat the procedure from step 1 at given time intervals.
  7. The series of repeated successful challenges and proofs between LL and VV generates the successful proof of capacity for LL.
last modified: 12/21/2018, 1:35:01 PM