It is not very intuitive to me right now why we have to audit all sectors. IIRC there are some attacks that would be possible if we skip sectors according to some criteria, however wouldn’t that also cause issues for Chia? I don’t recall what those reasons are if they are even documened somewhere, so maybe this thread would be that place initially.
How is Subspace different that it can’t benefit from the same optimization?
Specifically Chia according to documentation seems to skip 511/512 plots, so 99.8% after quick check. It’d be awesome if we could do something similar.
Another way to look at the benefit of this attack: If the attacker can create a plot that always passes the filter, it will be the equivalent of storing 512 plots locally.
and
The downside of the plot filter constant is that it provides a multiplier of replotting benefit to an attacker, so it must not be set too high.
Similar analysis to what they give applies also in Subspace. There’s just a tradeoff between how much you filter and how much storage an on-demand attacker emulate in a single on-the-fly plot.
I recall reading that with latest GPU plotting improvements they are looking to decrease the filtering some to maintain security, I believe it was on their blog.
All good points, Barak! On the other hand, if the filter depends on the sector content, then we are OK. However, such a filter should have two properties: (1) It admits fast verification; (2) It is robust to compression attacks.
One thing to note is the following. A good strategy for on-the-fly plotting is not to create-audit-delete the on-demand plots per challenge, but instead to keep them and audit against all challenges in between the last created block and the next created block to come. So on average we expect each on-demand plot to serve for 6 (subsequent) challenges.
However, if we deterministically reduce the amounts of audits per sector to be a 1/6 of the chunks, then the on-the-fly attacker loses this advantage.
To be concrete, suppose that per block challenge, we only audit the indices j satisfying j \equiv slot\_number \pmod{6}. In this case, the attacker can create only a sixth of a sector while simulating a full sector, so they amplify their weight by 6. On the other hand, unlike the explanation above, they can no longer use this for 6 consecutive challenges, hence reducing their weight by 6.
Comments:
Keeping on-demand plots for future challenges is not straightforward as it requires some infrastructure.
Yet, one can easily audit newly on-demand plots against previous challenges. So in this case, the expected number of challenges that an on-demand plot is audited against it 3.5, and it should serve as a lower bound.
This strategy can be combined with nothing at stake, using newly created plots even for challenges that are previous to the newly created blocks, basically extending the amount of challenges that each on-demand plot is checked against. Hence, the upper bound can be greater than 6.
Here’s my proposal.
For each challenge, for each (sub-)chunk, the farmer does the following:
xor 8 bits of challenge with the chunk
convert to a number 0 \leq j \leq 255
go to j-th bit, b, of the chunk
if b=0 continue, otherwise reject
This filters half of the chunks on average, and we can repeat (by shifting the bits) to amplify the filtering.
This filter depends on the chunk’s content and admits fast verification. Additionally, it seems not to be compressible, given that the challenge is drawn uniformly at random: since the 8 chosen bits are equally likely to take any value in their range, also j is chosen uniformly at random in its range.
Note that there may not be a real need to xor the challenge in (1) above.
I really like this idea proposed by @Barak! Three quick comments:
We can view this filter as part of the definition of winning chunks. More specifically, we can state the winning conditions as follows. Given a chunk and a challenge (256 bits for each), we say the chunk is a winning chunk if it satisfies the following conditions: 1) one or more random positions of this chunk are all zero; 2) hash(chunk, challenge) is within the solution range.
This filter seems to be incompressible, given that the chunk is drawn uniformly at random and the challenge is drawn uniformly at random (independent of the chunk). To see this, imagine a chunk with only a few positions = 0. Then, we just need to “record” these positions.
Under the above assumptions, we can even get rid of the hash operation in the definition of winning chunks and then use some difficulty adjustment algorithm to adjust the required number of random positions.
To sum up, I suggest using this as part of our winning definition and introducing a parameter corresponding to the number of random positions. The first 8 bits of the challenge give us Position 1, the second 8 bits give us Position 2, and so on. Do we need to modify our difficulty adjustment for the solution range? I don’t think so.
For 2, indeed I assumed that 0 and 1 bits of the chunks are equally likely. Even without compression, we should assume that averaging on records, the chunks bits are equally likely. Otherwise a farmer may decide to discard that record. So to be on the safe side, I suggest the j-th bit is taken from (chunk \ XOR \ challenge) as well.
For 3, I was thinking in this direction as well, but I see some obstacles. First, if we don’t mix the 8 bits, then per challenge there are at most 32 (256/8) positions we can choose. As you point out, as the space alleged to the network grows, the number of required positions will grow as well. If more than 32 positions are needed, we may hash the challenge and use that hash output bits in the same manner – this means we only hash once (or a few times in general, if we need more than 64 positions) per challenge, instead of hashing each chunk per challenge.
Additionally, as more and more positions are selected, it may be computationally less efficient to follow this procedure rather than taking a single hash of the chunk (after ‘partial’ filtering). As pointed above, if we don’t hash, then farmers will have an even stronger incentive to discard non-favourable records (even after the work spent on creating the masked records), so I emphasize my suggestion to xor the chunk for the challenge for the purpose of checking the random position bit value.