Compress y.

[fchirica]

Compress y form from 100 bytes to 33 bytes and adds python bindings for compression/verification. Note that this modifies chiavdf n-wesolowski verification as well, by factoring out the common parts in the verifiers.

[almogdepaz]

i really think we should sort out the names to match between the repo's and the paper
for example having a method called CheckProofOfTimeNWesolowskiYCompressed where there is no Y in the method itself doesn't make much sense to me

[rostislav]

I agree with the above suggestion by Almog that we should keep the naming consistent. The "compressed y" value is actually named B in the paper and elsewhere in the code, so I'd suggest to name the new functions accordingly, e.g. CheckProofOfTimeNWesolowskiWithB.

Secondly, the compress_y_from_n_wesolowski function is performing extra computational work (re-verifying the proof and deriving B) that can be avoided. What we could do instead is to introduce a new prove function named e.g. prove_get_B or modify the existing prove function to return B instead of (or in addition to) y.

Alternatively, if it is desired to have a function to compress y in existing proofs, we may add a Python binding for GetB, which derives B from x and y. Derivation of B is less computationally expensive than verifying the proof.

[fchirica]

I'll rename y_compressed into B.

The goal is to turn a proof y, proof, [iters1, B1, proof1], [iters2, B2, proof2], ... into B, proof, [iters1, B1, proof1], [iters2, B2, proof2], ..., so we send B instead of y to save space. The B must refer to the first segment only, not to the whole proof. So in order to create it, we need to "redo" the work verifier does (i.e. get out_y from x, B and proof for all segments but the first, then do x = out_y to prepare for the next segment).

Indeed, we can save this unnecessary check B == GetB(D, x, out_y) ? 0 : -1 in creating B, since we know it's true. But unless I'm missing something, is there any other way to get the first segment x from an existing proof other than duplicating VerifyWesoSegment operations?

[rostislav]

I understand now that for N-weso we have to verify the segments before the last one in order to find x for the last segment. Getting B from 0-weso doesn't require verification work, which is good.
I suggested some minor fixes in inline comments.

[rostislav]

In this and two other functions disc_size_bits argument is unused and could be removed.

[fchirica]

I left it for CheckProofOfTimeNWesolowski and verify_n_wesolowski, since those functions are already heavily used both in chiavdf and in chia-blockchain. I removed the field for the 2 new functions.

[fchirica]

actually I've tracked and removed it from CheckProofOfTimeNWesolowski, but I'll still keep it in python bindings function (verify_n_wesolowski)

[rostislav]

lgtm

[almogdepaz]

tested my new wp code with latest changes from this pr, looks good