gistfile1.txt

Miner has a public key pK, and private key sK.

When storing, the storer does:
* OP_STORE, 2^24 * 24 bits
* partition chunk of 48MB into words, 24bit each called D. you get ~ 2^24 of such words
* Hash the words via merkle, top hash is OP_STORE merkle hash
* Publish the OP_STORE with hash, along with your ip for p2p transfer

When storing for later mining, the miner does:
* Sees OP_STORE, decides to store this chunk
* Contacts publisher P2P, classic bittorrent
* Fetches the chunk, partitions into words  24bit each, verifies merkle etc
* for each word of chunk D, find a number E, such that MAP(pK,E) = D. MAP is bilinear
  mapping function and pK is your public key. Reversing the mapping is
  computationally difficult even with pK publicly known (DLP or other).
* store Es on disk
* tag in database this stored chunk with 'round indice' RI, last 16bits of merkle top hash

When mining:
* You get a 256bit NUMS number from oracle (previous block hash, or from a PoW chain
  separate from this one, this is subject to NaS problem)
* Last 32bits of this number is round indice RI, look up all your previously stored chunks
  which are tagged with it. Yes, it will be 1/(2^16) of your total storage.
* For each chunk you find, scan the Es in there, such as:
  for i in 0 ... 2^22
     if H(NUMS, E[i*4] || E[i*4+1] || E[I*4+2] || E[i*4+3]) < difficulty you win
     (ie hashing 96 bits each step)
* Sign block with your 'sK'
* Construct proof. "decrypt" the chunk by doing:
  for i in 0 ... 2^24
    D[i] = MAP(pK,E[i])
* Construct merkle tree for the chunk (divide and conquer, same as bittorrent
  merkle).
* Publish your block, with pK, merkle path and winning E's:
                                    TOP (found in OP_STORE)
                                    / \
                                   o   D
                                  / \
                                 o   D
                                / \
                               o   D
                              / \
                             o   o
                            / \ / \
                           E  E E  E <- H() over these were found to match difficulty

Others verify your proof:
* Check that round indice RI matches mined OP_STORE hash
* They take the 4 Es you published, check difficulty H(NUMS, E1 || E2...)
* decrypt E's via D = MAP(your_pK,E)
* This completes the merkle tree, the top hash now matches that of the original
  in OP_STORE

Why is this difficult? Why can't I just PRNG, publish OP_STORE for that, and
save nothing?

Inverting MAP() is very difficult, as the search space must be bruteforced.
You do it once, when storing chunk, but further lookups are cheap (as you
stored the inverted mapping). This is why you can't compute it on spot as
needed.

Because its infeasible to scan all chunks you have each round, this is why
things are partitioned according to "round indice" - each round, 1/2^16 is
scanned.

There's another problem with incentives. You can selfishly store your
own data, still get mining reward, and contribute nothing. Miners like
that are expected to be widespread. This needs to be addressed in economy
protocol incentives and is outside of the scope of actual PoStorage algo as such.