I was under the impression that currently each chunk is stored as a file and the file system handles the actual storage.
I know. I’m wondering if that’s still sufficient with this PoS proposal. May well be.
Well you only have to prove that the vault software will actually store that amount of data in the claimed space. A cheater can always supply the space but at some stage just stop doing it. And that is what resource proof and punishing vaults that do not retrieve a requested chunk is about.
So I’d say that using the file system to store chunks as files is certainly good enough.
I was thinking more along the lines of efficiency. File systems have additional overhead and that’s why we have a single swap file and not thousands of tiny swap fragments for example. But, as I said, it may or may not be an issue.
2 Likes
Edit: Tl;Dr Below more complicated proof of storage ideas which also requires little bandwidth. Also extra efficient because less work for testers and is even more difficult to cheat.
I haven’t (yet) read everything concerning these ‘proofs’, but I don’t get it completely.
What I had in mind: use the group consensus characteristics to prove spare space.
Have at group/section level a list of seeds (i call it seed numbers below) derived from datachain or random numbers.
If a vault has 200 GB spare space: divide this in 200 parts of 1GB and couple each part on 1 such ‘group’ seed number. But prevent that 1 such seed number is used twice for 1 vault. This 1GB I choose here out of convenience: the point is it doesn’t have to match with the size of the 1MB of the chunks in the ‘used’ space. Whatever is the size that strikes the best balance between a time consuming ‘filling’-algorithm and having checking flexibility.
If a vault needs extra space to store new chunks: take 1 of these 200 GB parts, so that only 199 GB testable free space remains. That the free part of the 1GB isn’t tested is ok: it is not much in comparison with the 199 and it will soon decrease because of new chunks that are created.
What the testers (e.g. the elder nodes) have to know: the ‘part index-seed’-table of each vault to check.
When a new vault enters the section, the vault says to the group how much space it has and gets such a ‘part index - seed’-table back from the group.
Now the vault can start filling the spare space using the seed for each part. The algorithm to fill should take enough time so that later, during size check tests, it can’t be used to cheat by quickly creating a part a vault claims to have, because it takes too much time. And of course the resulting data on the spare disk space part after the filling algorithm is done, has to be always the same.
Maybe an extra ‘fill algorithm type’-field could be added to this table to mix different algorithms or for future, improved algorithms.
The group can make it so that the different vaults share parts with the same seed number: e.g. vault number 1 has seed number = x for part with index = 1, vault number 2 and 3 have also seed x for part 1 (or another part), but vault number 4 has no part with seed x.
Why all this trouble draw, you could ask yourself by now (if you are still reading this). Well this way a tester (e.g an elder node) could check multiple vaults at once, without having the data to check himself.
A tester could send a ‘check space’-command at a certain time to all/a lot of other, to be tested vaults of his section, so that they will calculate a hash for each (or at least a lot) of the spare space parts they have.
This command will also contains a random ‘salt’. Each tested vault has to calculate a separate hash for each spare part it has. To be clear no ‘linking’: not using the hash result of other parts to the hash calculation: only the ‘salt’ and the contents of the part.
When the tester gets the hash results back it can compare e.g. the hash of spare part with index = 1 and seed number = x of vault number 1,2 and 3. If this hash of this part is the same for vault 1 and 2, but for 3 it is different, then vault 3 has failed the spare space test. This way each part that is present at multiple vaults (because it has the same seed number) can be checked.
This is also scalable: the more free space a vault has, the more parts it has to provide a hash for in 1 reply to a ‘check space’-command, which also means only 1 round trip network message latency to take into account when calculating the maximum allowable time to respond…
You could make it so that the more spare parts a vault has to ‘proof’ this way, the more time a vault gets to respond to the ‘check space’-command.
If there are tested Vaults with unique free spare parts (with seed number that no other vault in the section has): no problem.
Make sure the tested Vault doesn’t know which parts will be checked and which will not.
Worst case (like in the example above if the hash of the part with the seed number x of the Vaults 1, 2 and 3 are all different) a tester can generate a to be tested part himself by generating it with the seeding algorithm and doing the hash check. Of course the tester gets the necessary time to generate the part to be tested.
Why the arrangement that not every vault’s spare space has exactly the same seed number for e.g. the part with index = 0 ? --> To prevent some cheating vaults in 1 section that could fake spare space by sharing 'proof ’ via a backchannel connection. If this a too unrealistic scenario, this part can be left out of course, to keep it as simple as possible.
My idea also has the advantage to cope with a constant in- and outflow (churn) of vaults.
I hope this has made a bit of sense 
2 Likes
As usual, thank you mav for presenting your ideas so succinctly and help us focus on important issues… lot’s of very interesting ideas here. However, I don’t think the timing of proofs are as appealing as the good old fashioned “sacrificial chunks” from yesteryear…
I don’t think so.
I think the notion of spare or “free space” in the network is something that should be shied away from, (just like the notion of free time ) In other words, a network with lot’s of free space is a network that is not maximizing its use of available resources. Instead, why not use this excess capacity by filling it up with many sacrificial chunks for maximum redundancy rather than special “proofs” or other objects whose only purpose is to check free space. When a vault joins the network, the vault managers can begin sending it sacrificial chunks until some stopping criteria is reached or an out of space condition occurs and the vault cannot store any more. This proves the the vault’s storage capacity to the network. Sourcing those sacrificial chunks will require older nodes to prove their own storage is valid. The number of sacrificial chunks serves as a distributed indicator of available network resources. Assuming that 33% of the nodes are corrupt, then the network will need a minimum of 12 copies of a chunk to ensure that 8 copies are valid. Giving a little extra margin, elders could just refuse to let new vaults join when there are 16 or 24 copies of all the primary chunks in a given section, which is an easy way to control the growth of the network and control GET rewards and PUT costs. When new PUTs are made to the section, some of the sacrificial chunks get overwritten, which would trigger the section to accept new vaults if the total number of copies for a chunk drops below the 16 chunk threshold. Sacrificial chunks have a lot going for them.
In my view, the network should never be idle. Section managers would continuously be requesting chunks from vaults to ensure the chunk is being properly stored/managed by the vault even if there were no human users doing so. The sacrificial chunks would continuously swirl and flow between nodes in a section, and I would presume that any vault/node who is unable to deliver would quickly be found out and removed via standard network error checking mechanisms already planned during the chunk retrieval process. I think this process should be transparent to the vaults and look no different than standard user puts or gets for data. Perhaps this automated verification rate would occur at some inverse multiple of human get/put requests in order to maximize the user experience while also maintaining maximum network load? Perhaps there was a reason that sacrificial chunks fell out of favor that I am unaware of?
7 Likes
That would be nice if bandwidth was unlimited. Once I dedeicated HDD (or part of it) to be a vault, I dont care what is there and how full it is, but with bandwidth it is diffrent. With most ISPs you will run in problems when you use your line 24/7 at 100% even the “unlimited” plans are often “not so unlimited”.
I think many vault hosts will run into problems with their ISPs even without this and as much i like the idea of increased redundancy, we should try to keep the bandwidth required to run a vault low. If running a vault will need too much bandwidth, it will lead to centralization to datacenter hosts, where the connection is cheap and close to unlimited.
2 Likes
I think the biggest issue with this is that it’s hard to generate and hard to validate afterwards. (bitcoin mining is hard to generate, as you need to brute force the block hash, but easy to validate as you only need to hash the block once.)
How would this work? Each section would have it’s own seed (thus all vaults in that group would at least start generating the same proof’s). And the tester would download/“request” a proof from the testee?
- Would that imply that only a node with more “free” space could test a node with less “free” space? resulting in not testable proofs. Or you could store the proofs in a decentralized manner but that would be just a reimplementation of the “normal” SAFE PUT/redundancy procedure and would generate the same amount of traffic, but store useless data instead.
- How would this prevent that the tested vault could ask another vault for that specific proof? That’s not an issue for GETs because of the timing, just the fastest vault gets the reward, thus there’s no time to proxy request data from another vault. I guess this could be mitigated by using a deterministic pseudo random source (eg. hash of the last block) to determine the testee and the needed proof, thus we could identify invalid requests.
For your 2 points: I tried to cover these in my previous (long) reply.
Yes, true. Reasonable limits could be imposed.
Perhaps new vaults could present a bandwidth capacity/rate statement to the section. The section would then throttle automated chunk interrogation to the vault based on the reported limits.
1 Like
I’m not sure we have a contradiction here. We can talk about these 3 different kinds of “content”:
- data that the section stores,
- data that the section is caching,
- proof of free space.
Caches are (or can take the place of) the sacrificial chunks, and they can count towards either of the free space or the stored data, depending on what we’re looking at. But I may be missing something so let me know.
No. Tests shouldn’t ask for entire proofs (that would be wasteful) only a few bytes from here and there. This also means that, after a vault first initialized its proof store, it could store away a number of samples from the high blocks so it could use them to test other vaults even when its own blocks are overwritten. In effect, a vault can test the free space in other vaults up to the total space of its own.
If the cache is stored on disk that is.
Well, yes. It depends on how much we cache and for how long. I now realize sacrificial chunks were more like an on-disk cache and “caching” was referring to a really short in-memory store.
It certainly makes sense to store away immutable data that is requested repeatedly, so that makes more sense for performance.
2 Likes
What happens when trying to cheat this algorithm?
The cheater proves 1 GB storage (1 MB proof size with 1024 proofs) but only really consumes half that.
Seed: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Proof Size: 1048576
Total proofs: 1024
Sign difficulty: 1
Hash difficulty: 1
Scavenge depth: 10
The cheating technique I used was to measure how many times each proof was scavenged, then discard 50% of the proofs starting with the least dependent proofs.
Not surprisingly, chunk 0 was the most heavily depended on, being used as a first-depth dependency 135 times.
The median dependency was 7 (half the proofs were reused less than 7 times, half were reused more than 7 times).
After discarding half the proofs, the cheater was asked to provide the data for a particular proof. The cheater might need to recreate some of the missing dependencies (possibly nested).
The most difficult proof to provide needed to recreate 236 missing proofs which took 4.1 seconds.
90% of proofs could be recreated in less than 1.15 seconds.
66% of proofs could be recreated in less than 0.12 seconds.
There’s a few intuitive observations (which the chart makes even clearer).
Proofs from the early portion of the chart are not as useful to test as later proofs since they take less effort to recreate (have less dependencies).
The degree of dependency on each proof is not equal, by nature of only looking backward for dependencies, not forward. Earlier proofs are more likely to be a dependency.
However this doesn’t mean tests should only come from the last x% of all proofs, since that would mean definitely the bottom 1-x% could be discarded!
My rough guess for how to tune this algorithm would be:
- depth should be
- high enough that it reduces the opportunity to discard and
- low enough that it doesn’t create significant computation overhead (that’s the job of the difficulty settings)
- difficulty should be
- high enough to make recreation longer than network transfer time and
- low enough to make initial creation simple and not restrict participation to only high performance vaults.
I think a better understanding of the relationship between depth and difficulty would be helpful.
7 Likes
My initial question is if the size was above 10GB, above 100GB, above 1TB. What then? How long to recreate.
My thought is to cheat with saying you have 1GB doesn’t seem worth it, does it. The cheat probably has more main memory free than the 1GB.
How long on a low end device that reasonably would only have 1GB of storage (assuming no USB mem stick or hard drive)
Also what happens if you implement my idea that any proof test should see the section requesting 3 spread out proofs per test. That way recalculations are increased and for a non-cheating vault the answer is given back almost as quick as asking for 1 proof, whereas for a cheat that recreates it likely will be 2 or 3 times.
2 Likes
1 GB
Took 22 seconds (0m22s) for initial (honest) creation.
Discard 50% of lowest dependency proofs.
Hardest proof to recreate: 236 missing dependencies, 4.1 seconds to recreate
90% of proofs had 66 or less missing dependencies, 1.15 seconds to recreate
66% of proofs had 4 or less missing depedencies, 0.12 seconds to recreate
10 GB
Took 183 seconds (3m3s) for initial (honest) creation.
Discard 50% of lowest dependency proofs.
Hardest proof to recreate: 788 missing dependencies, 13.7 seconds to recreate
90% of proofs had 84 or less missing dependencies, 1.48 seconds to recreate
66% of proofs had 5 or less missing depedencies, 0.086 seconds to recreate
100 GB
Took 2452 seconds (40m52s) for initial (honest) creation.
Discard 50% of lowest dependency proofs.
Hardest proof to recreate: 1802 missing dependencies, 35.5 seconds to recreate
90% of proofs had 78 or less missing dependencies, 1.5 seconds to recreate
66% of proofs had 5 or less missing depedencies, 0.093 seconds to recreate
Sure, I agree it’s not worth cheating 1 GB on face value, but the point is to get a sense of the algorithm characteristics. I’ve sorta assumed the magnitudes scale linearly (which in theory it should and the figures above indicate it does). So cheating 1 GB can be pretty accurately extrapolated to any size. I can see how that assumption is not at all obvious from the previous posts though.
I’ll see if I can crack out my raspberry pi or pine64 and do a test. Ideally it shouldn’t be too far away from a desktop computer, since it’s meant to test space rather than cpu, right?!
Good idea, it would need to be tested to know how much it improves things, but I imagine it serves a similar purpose to the ‘depth’ parameter. Except depth works at the test level rather than the generation level so the test idea is a good extra thing to have. I’ve mainly focused on the generation part of the algorithm rather than the testing part, but you make a good point that the test design can also be used to improve robustness against cheaters. Changing the test parameters is also a lot more flexible than changing the underlying algorithm (which would a full regeneration for every vault) so that’s another advantage.
I also came across Burst today which uses Proof-of-Capacity (prior thread). Some info about how they create proofs and how proofs are used for mining. There’s a fast POC miner written in rust called scavenger! Might have to try it out. They currently have about 250 PB on their network (source). Peak was almost 400 PB. Mining started in Sep 2014 at 5 TB and within two months grew to about 5 PB where it stayed for about 2 years. Hard to imagine that capacity staying with burst instead of SAFE.
I’d say POC in the current form is not a good algorithm for SAFE because it relies on shabal hash which would be a waste; the algo may as well use the crypto primitives needed for regular network activity so any hardware optimizations have multiple benefits. But I’m going to look at burst and POC in more detail because it’s out in the wild and seems to be proven to work. Might be easy to change the hash algo and keep the rest of the process if it’s robust.
5 Likes
It is indeed a good idea to first look thoroughly at what others have already done / ‘proven’ in this space 
2 Likes
Interesting that the real effect of size is on only the top hardest few percent of proofs to recreate, yet by the time you got down to 90% the times were close and at 66% they actually dropped in the simulation.
I guess a way to ensure a proof in the top 10% hardest each time would be good.
Also 0.093 seconds (93 milli seconds) cannot necessarily be distinguished from a vault long (digital or land) distance away.
3 Likes
Increasing the depth from 10 to 100 would mean ten times more previous proofs are required to generate each successive proof.
This change is intended to make it much harder to cheat but not much harder to generate the initial proofs.
1 GB
Took 80 seconds (1m20s) for initial (honest) creation (compared to 22s for depth 10)
Discard 50% of lowest dependency proofs.
Hardest proof to recreate: 493 missing dependencies, 39.0 seconds to recreate (compared to 236, 4.1s for depth 10)
90% of proofs had 386 or less missing dependencies, 30.9 seconds to recreate (compared to 66, 1.15s for depth 10)
66% of proofs had 156 or less missing dependencies, 12.2 seconds to recreate (compared to 4, 0.12s for depth 10)
10 GB
Took 521 seconds (8m41s) for initial (honest) creation (compared to 183s for depth 10)
Discard 50% of lowest dependency proofs.
Hardest proof to recreate: 4740 missing dependencies, 223 seconds to recreate (compared to 788, 13.7s for depth 10)
90% of proofs had 3645 or less missing dependencies, 171 seconds to recreate (compared to 84, 1.48s for depth 10)
66% of proofs had 1450 or less missing dependencies, 68 seconds to recreate (compared to 5, 0.086s for depth 10)
100 GB
Took 6895 seconds (1h54m55s) for initial (honest) creation (compared to 2452s for depth 10)
Discard 50% of lowest dependency proofs.
Hardest proof to recreate: 45791 missing dependencies, 3910 seconds to recreate (compared to 1802, 35.5s for depth 10)
90% of proofs had 34215 or less missing dependencies, 2470 seconds to recreate (compared to 78, 1.5s for depth 10)
66% of proofs had 13052 or less missing dependencies, 585 seconds to recreate (compared to 5, 0.093s for depth 10)
What does it mean?
Cheating has become much harder but initial proof creation only a little bit harder. That’s a nice characteristic.
Initial generation time is a bit slower, taking about 3x longer when depth was increased by 10x. This is a reasonably good result, since depth is only meant to control how many prior proofs must be retained to avoid cheaters, not how long it takes to initially create proofs. Ideally increasing depth shouldn’t add any time to the initial generation, but this is real life and increasing security comes at some cost.
Cheating becomes much harder, which is the intended purpose of increasing depth. The difficulty to recalculate missing proofs becomes exponentially harder as the total number of proofs increases. A 10x increase in depth created up to 1000x more work for a cheater (in this particular scenario).
In this case, the benefit of increasing depth from 10 to 100 is much greater than the cost, so overall it seems like a positive thing to do.
How should a value for depth be chosen? Increasing it more will eventually lead to almost no additional improvement to cheating. It’s a tradeoff, we want to keep depth low to avoid taking too long for initial generation but we want to keep depth high to make it very hard to cheat by discarding proofs.
What’s the point?
Zooming right out, recall why proof of storage is useful to SAFE.
Knowing how much spare space exists allows the network to manage stress better.
The proof of storage mechanism is like a sensor, providing additional knowledge to the network, which can be used to optimize the control mechanisms (such as safecoin creation, storage pricing and new vault disallow rules) and reduce stress on the network.
This prototype algorithm would be less cost (to both user and network) than the sacrificial chunks idea because it uses almost no bandwidth.
It’s good to consider whether the stress can be managed without the extra work required for proof of storage.
It’s hard to say whether the overall benefit of any proof of storage mechanism is greater than the overall cost.
The cost this particular algorithm imposes seems to be low enough that it could be considered usable for the problem (ie it’s not an impossible problem to solve).
I’m still undecided about proof of storage vs ‘let the farmers worry about it’.
Yeah the unluckiest proof is ‘extremely’ unlucky compared to merely ‘very’ unlucky worst 10%.
This is where increasing the difficulty to have more iterations of the signing operation or the hashing operation will allow the time-to-recreate-missing-proofs to be increased enough to be meaningful (along with a suitable depth value as explored in this post).
7 Likes