How does Chia verify a plot is k32 and not e.g. a k32 plot with 10% of it deleted or a k31 plot with zero bits added to the x values?

I’ve read https://www.chia.net/assets/proof_of_space.pdf and am probably missing something obvious… Is it that it is rejected/looses out because of lower quality?

3 Likes

Great question! I was battling with similar questions until I figured it out. About the 10% deletion: All bits in a plot contribute to at least one proof and most bits contribute to multiple proofs. So a 10% deletion will usually cause a more-than-10% proof deletions. It is however sometimes suggested that lossy compression by removing information that contributes to only one solution would be slightly beneficial.

How does Chia verify a proof comes from a k32 plot and not from a k31 plot? If you create a plot for k=31, that number 31 is used indirectly* as input to hash-functions. When the network validates your proof claim, it will use 32 as input to those hash functions and the proof validation will fail.

So you say, what happens if we adjust the k31 plotting software to pass 32 as input to the hash functions? Then we have to be careful about when we reach the point where we’re just creating a k32 plot. What we could do is create a k32 plot but with only using numbers x_i that are smaller than 2^31. In that case the size of the plot will indeed be that of a k31 one, but since each of the 64 x_i’s of potential proofs will have half of their possible values disappeared, the expected number of proofs of such a plot will be a factor 2^64 lower, meaning that such a plot will in virtually every case have no proofs.

On page 4 it says under f functions:

`f_t: ...... -> 2^(k+...)`

The input (the first dots) also contains k’s but that’s no issue in our attack; we could just claim that our inputs happen to be smaller than 2^31. However the size of the output is dependent on k, which becomes important when that output is used as input for f_t in the next table.

The k that is shown in the above line is therefore very important. It also makes sure that a plot of k33 doesn’t have a gazillion more proofs than a plot of k32: because of this k here two inputs to M are twice as unlikely to match in a k33 plot than in a k32 plot.

6 Likes

Than you for reading through this carefully.

It seems to me that even a slight amount of deletions would be beneficial for cheating pools.

I noticed occasional Hpool disk activity similar to checking plots with a small number of challenges. However for such a small number of checks deviations in excess of 10% are expected. Larger number of checks eventually converge, but slowly. Order of magnitude increase of N is needed while time to complete grows linearly, bound by disk random seek speed.

Great topic! How do you *prove* you have all that space. Central to the concept of Chia.

1 Like

A Chia challenge asks for a certain x so that the “Chia hash” of x is equal to the given Challenge. Such an x is called the “preimage” (or “proof” in Chia) of the Challenge and the Challenge is the “hash” of x. For a given x, it’s easy (for a computer) to find the hash. However the reverse is opposite: for a given hash (Challenge), it’s almost impossible for a computer to find the preimage x, unless it has precomputed a table where it can lookup the preimage of the given hash. That’s how Chia works: By showing the preimage of a Challenge (hash), the farmer proves that he has a whole lookup table on his disk. This proof is of a statistical nature. In theory the farmer could have stored only one hash with its preimage in a couple of bytes on disk and be lucky that the next Challenge is exactly that hash. So in Chia, proofs that one has all that space are of a statistical nature.

It’s easy to construct a lookup table. You simply compute the hash of many different x’s and you store each hash with the corresponding x. When a Challenge comes in, you lookup if one of your hashes is equal to it and there you’ll find the x you stored with it. A Chia plot is simply such a lookup table, just stored in a smarter / more efficient way using the specifics of how a Chia hash works.

The above story is of course a summary and makes a lot of simplifications. In reality, the majority of all farmers have a preimage of the current Challenge and that’s where the quality string kicks in to break ties. In the long run, farmes with more disk space will have more quality strings and so have a greater chance of winning the ties.

The x in the above story is in Chia actually x_1…x_64. The “Chia hash” is the multiline function on page 3 of OP’s document under “Proof format”. It differs from hash functions in general in the sense that most x_1…x_64 don’t even produce an output (hash), namely in the cases where at least one of the M-functions outputs False.

2 Likes