LeoIf we use a symmetric PoRep and a layered graph, no matter what parameters we achieve in terms of space gap, or cost ratio, or latency, etc., the cost of unsealing one node is equal to the (number of layers) x (number of hash inputs at each node). The width of the PoRep does not matter, because the cost is per bottom node. It’s the height that matters.
In this note, I argue that this simple arithmetic presents a hard bottleneck for the cost of unsealing, regardless of whether we are in the cost model or in the latency model. All the currently known techniques for reasonable PoS constructions have this problem. In order to reduce this bottleneck, we have to either go to asymmetric PoReps, or compute less for every PoS byte sealed, which requires a drastically different PoS.
The number of hash inputs is fixed at 37.
The minimum number of layers in the current graph is 8. With fewer layers we have absolutely no guarantees. With 8 layers, we have a latency and a cost guarantee of 0.2 (for a 20% spacegap cheating adversary). We can say that the unsealing cost of this guarantee is 8x37.
We can improve this guarantee in the cost model to 2.24 if we have 11 layers. Then the unsealing cost of we pay for this improved guarantee is 11x37. Thus, by paying 11/8 = 1.375 more for unsealing, we get a guarantee that is 11 times better. We can have 12 layers, improving the guarantee to 3.17, or 13 layers, improving the guarantee to 4.1, or 14 layers, improving the guarantee to 5.03, and so on.
We can also change the graph. We can change the expander degree to 31 from 8 (and still have enough room in the 37 hash inputs, because the depth-robust graph in-degree is 6). Even though this will be a much better expander, it will change the analysis only slightly, getting us to 0.2 by 6 layers instead of 8, and, in general shaving off 2-3 layers from the numbers above. We can also reduce delta, potentially shaving off a bit more. However, this will not reduce the cost of unsealing dramatically — we still need at least 6 layers, which is more than half of the current 11 layers, so we can’t even cut the cost of unsealing in half. Further increasing the expander degree will not change much, either, even if we ignore the degree effect on the cost of unsealing. The current analysis techniques seem to require 5-6 (depending on how small we can drive delta) graph layers no matter what.
What about latency? Again, the current graph demands a cost of 8x37 for latency of 0.2. I have proposed improved analysis techniques that allow for stringing of multiple paths to get one long path. These techniques work better if expansion is better, so let us increase the expander degree to 31. Even so, these techniques will probably get us no more than 0.05-0.08 in additional latency for every graph layer added unless we dramatically increase the graph degree (which increases cost). [This is a rough, back of the envelope calculation, because I haven’t yet managed to carry out the analysis; if anything, it’s a bit too optimistic.] In other words, you pay the unsealing cost of 6x37 upfront for the bare-bones latency of 0.2, and then 1x37 for each additional 0.05-0.08 increase in latency.
Note that with the current analysis techniques, the cost of latency is much higher than the cost of cost. That is, if I want latency of X hashes, I pay as much in unsealing time as I would for cost of 10X-15X hashes. I don’t see a way to fix it by messing with the expander. We need either much stronger depth-robustness guarantees or some totally different constructions.