Remove erasure coding from v2.3 plotting

I have a proposal to remove erasure coding from v2.3 consensus (plotting). I know @dariolina will not like it, but I think there are more positive aspects to it than negative.

Erasure coding was added due to the fact that proof of space quality/proof can be found with probability ~2/3, so by expanding record chunks 2x we increase probability that each chunk of the record used in the plot will be encoded (from our empirical tests ~99% of records will use all encoded records).

This is great, but there are a few negative side effects:

  1. During proving and reading not just decoding using XOR, but also erasure-decoding is necessary, which for 2^16 chunks is a non-trivial amount of work
  2. ^ also means that we need a lot more RAM during operation (if written plot is 1.3G, then at peak we need at least 3x+ of that amount of memory allocated).
  3. S-buckets become variable in size, which in turn requires even more work during proving and reading (or prohibitive amounts of RAM)

As the result proving and reading of pieces from the plot are unnecessarily expensive operations, likely costing on my machine (24C/32T 13900K) ~0.5s out of 1s budget. It would be very nice to get rid of it.

If we do remove erasure coding, we’ll have ~1/3 of chunks unencoded and not eligible for farming, but fundamentally that is not much different from tweaking sectors_to_audit in the spec, making 1/3 of sectors not eligible for solutions.

Erasure coding there seems to cause more issues than it solves, maybe we should remove it in the end?

The final plot format that you are proposing then would be (assuming max_pieces_in_sector pieces):

  1. max_pieces_in_sector bitfields of size NUM_CHUNKS each that indicate whether that chunk index has a PoS proof
  2. NUM_CHUNKS s-buckets of size max_pieces_in_sector each where ~37% of chunks are unencoded
  3. KZG commitments + witnesses

The audit now becomes slightly larger, so we may want to reduce number of pieces to stay under 32 KiB. However, we save on metadata with bucket sizes and know exactly where each bucket starts.
During audits a farmer reads a bucket, and scans: if a chunk isn’t encoded skips, if encoded checks if within solution range.
On winning chunk generates PoS, decodes encoded chunks, computes KZG witness. So we save time in reading parent record chunks from disk and erasure code recovery. That does sound good.
Let’s see what @Chen_Feng_2023 has to say on whether there are security implications I did not consider.

Short answer: An adversary can “amplify” its advantage by only storing pre-images and a single copy of certain records.

Long answer: Consider the following attack. An adversary picks a particular record and generates as many farmer IDs as possible that contain this record. Then, the adversary finds the pre-images for this particular record across the farmer IDs it controls. The adversary only stores these pre-images together with a single copy of the record.

@Chen_Feng_2023 could you please elaborate on how erasure coding each record prevents that? It seems like the attack you are describing is still the case with the original design. Erasure coding the record is quite fast (~2 FFTs) compared to PoS computation that we do in this design Nazar proposed same as originally

Sure @dariolina ! In the previous construction, the storage of pre-images is about 2/3 of the total storage requirement. In other words, the overhead is as large as 1/3. (Such a large overhead incentives cheating.) With erasure coding, this overhead can be made close to 0.

Is there another way we can get around this? Considering how easy it is to derive PoSpace quality, could we wrap around and use (2^15)x+s_bucket’s quality, where x = 0... Then with enough attempts we should be able to encode all chunks, not just 2/3.

There are already multiple qualities per s_bucket and no way to prove which one we picked, so picking quality from completely different index should be fine as well as long as it is verifiable.

How would you verify the wrap-around? Also, is (2^15)x+s_bucket’s quality incompressible? I guess I don’t quite understand this new approach.

You can verify that it is a value at the offset that is multiple of 2^15 relatively to s-bucket by attaching the offset (or multiplication coefficient) itself.

If I understand this strategy correctly, then one does not need to store the pre-images (I actually don’t see the benefit in doing so). It just exploits the fact that 37% of the space that is taken in the honest farming protocol can be compressed into a single record.