Proof of Resource formal specification


#1

Hi,

I was wondering if there is any formal specification for Proof of Resource used in MaidSAFE? Particularly, how are the proofs generated, validated and how MaidSAFE ensures there is no way to fake a proof?

Thanks,
Yurii.


#2

Hi Yurii,

I’m very glad you are interested in the SAFE project because the synergy that your decentralized Github project has with SAFE is remarkable (For anyone not familiar with Yurii’s project check out Gitchain on kickstarter)

Regarding your question - I know you are asking for formal specs but a good place to start is this blog post and the comment section below.

Another interesting resource is the System docs

But for a detailed and formal spec you are going to have to wait for the paper to come out (I think it should come out very soon but I’m in no way sure about this) or better yet you could ask @dirvine himself…

If he doesn’t respond here make sure to post on the dev mailing list

Also you should check out @chadrickm 's project Builder Hub since your projects also go perfectly hand in hand.


#3

Hi Marin,

Thank you for the links. The first one doesn’t seem to be revealing any details on actual proofs (“Ignore how the mine attempt and proof works for now”) and I can’t quite locate any specific part of the System documentation about this.

That said, any description of the proof of resource algorithm will suffice for my purposes, even just a piece of code (I mean, paper is nice to have, but I can take a variety of input types :smile:). Would love to hear from @dirvine if he has a minute to address this issue.

I find the proof-of-storage a particularly interesting, but somewhat challenging topic. I’ve been recently entertaining an adaptation of Permacoin’s ideas for Gitchain as it feels like a right fit. That said, a lot of people have approached me telling me about MaidSAFE and I’m always curious to learn.

Yurii.


#4

Yes there are bits of info everywhere at the moment. The proof of resource is based on a similar notion of proof of retrievable data. So if you check the code in vaults you will see there is an integrity check code:
https://github.com/maidsafe/MaidSafe-Vault/blob/master/src/maidsafe/vault/data_manager/service.h#L662 and also here https://github.com/maidsafe/MaidSafe-Vault/blob/master/src/maidsafe/vault/data_manager/integrity_check_data.cc.

In essence what happens is that:

  1. A client does a Get request (ignore repeats, bots etc. otherwise subject gets huge, it is covered though)
  2. The Data Manager group(s) then issue Integrity checks, which are
  3. Create nonce
  4. Send nonce to holder of data with id of chunk to check
  5. holder appends nonce, hashes and responds with answer
  6. Data Managers check returns from all holders (it’s all encrypted end to end so no cheating)
  7. If any fail they get de-ranked and no mining attempt allowed
  8. As the rank fails further mining attempts reduced
  9. On successful gets and pass of IC then a mine attempt may happen (it’s based on a modulo arithmetic count of several factors (message_id, pmid manager addresses, node address), The rate is calculated on a function of the node rank so something like ((mine_attempt %X) == 0) Where X is a function of rank (still being discussed) so it will be close to safecoin_reward * NetWorkAverage / (stored/lost)

This proves data is retrievable and not only that, but the data has not been tampered with or otherwise corrupted.

Some say an attack is nodes do not actually hold the data and get it elsewhere, we do not care about this as the node is asked to give us data and if they do then cool. If they did this attack there are many reasons for failure as they do extra work, but essentially we do not care how nodes do what we ask them to as long as it’s done correctly and in a time that does not de-rank them.

Hope this helps a little.


#5

I’ve recently found this project and became curious about the Proof of Resource thing. The described method lacks the details about checking the returned result. How exactly the Data Manager does this? As I understand, to verify the correctness of the returned hash it should have that chunk to add the nounce and hash them together, verifying then against the miner provided hash. But then it requires Data Manager to have all the chunks which isn’t practical and makes it a SPoF supposedly. Or is it so DM doesn’t know anything about the valid value and just forms a consensus using the Byzantine generals problem (there was a mention of it somewhere here)?


#6

That part is pretty simple, there are a minimum of 2 and up to 20 copies actually online, ask them all the same encrypted question and weed out the wrong answers. no need to keep any copies! Can you please help with docs and point out where this is not described with Proof of Retrievability or Integrity checks. It will help others if we update it.


#7

It is described here, it’s a lot to take in and I would describe it as ultra advanced stuff;

http://maidsafe.net/SystemDocs/detail/Vault.html

I found and have read some of the following paper and I think it will help with understanding the concept of Proof of Resource; It is helping for me.

http://www.arijuels.com/wp-content/uploads/2013/09/JK07.pdf

Abstract. In this paper, we define and explore proofs of retrievability (PORs). A POR scheme
enables an archive or back-up service (prover) to produce a concise proof that a user (verifier)
can retrieve a target file F, that is, that the archive retains and reliably transmits file data
sufficient for the user to recover F in its entirety.
A POR may be viewed as a kind of cryptographic proof of knowledge (POK), but one specially
designed to handle a large file (or bitstring) F. We explore POR protocols here in which the
communication costs, number of memory accesses for the prover, and storage requirements of
the user (verifier) are small parameters essentially independent of the length of F. In addition
to proposing new, practical POR constructions, we explore implementation considerations and
optimizations that bear on previously explored, related schemes.
In a POR, unlike a POK, neither the prover nor the verifier need actually have knowledge
of F. PORs give rise to a new and unusual security definition whose formulation is another
contribution of our work.
We view PORs as an important tool for semi-trusted online archives. Existing cryptographic
techniques help users ensure the privacy and integrity of files they retrieve. It is also natural,
however, for users to want to verify that archives do not delete or modify files prior to retrieval.
The goal of a POR is to accomplish these checks without users having to download the files
themselves. A POR can also provide quality-of-service guarantees, i.e., show that a file is
retrievable within a certain time bound.


#8

Thanks, now I understand. These docs don’t pop up when I searched for “proof of resource” in Google and this thread was one of the top.


#9

How does the data manager know what are wrong answers without keeping the data?


#10

Several ways really I think this may help


Also


#11

I’m sorry but it does not. I must be missing something since i always end up with a question mark at this point in the process:

(4) The result is collected at the checking group and compared

compared to what? You cannot compare it to the other received answers since they can be corrupt. You cannot compare it to an expected answer since the expected answer can only be known if data is known (data+nonce hashed).


#12

If everyone is corrupt there really is a problem :wink: Majority rule is not bad in this situation. Plus and importantly the hash of the content == name, so mathematically self validating data.


#13

So if all answers differ and only one is not corrupt, then you need to transmit the actual data and check for which instance the data hashes to the name correctly to know which one was not corrupt.

I was thrown off track by being fixated on the idea that data is never transmitted and it could still work :smiley:


#14

Yes, this is where c++ is really good, the data will not deserialise/parse into a type, so it won’t exist and therefore will be less likely to corrupt anything. It will fail in the construction of that type and not be able to infiltrate as rouge data at that point.