[Tech Debt] - Update VID recovery threshold

[rob-maron]

What is this task and why do we need to work on it?

Update the VID chunk size recovery threshold to not use the "previous power of two" algorithm after we have univariate KZG in evaluation form (https://github.com/EspressoSystems/jellyfish/issues/339)

What work will need to be done to complete this task?

No response

Are there any other details to include?

No response

What are the acceptance criteria to close this issue?

• [ ] chunk size recovery threshold calculation does not deal with powers of two

Branch work will be merged to (if not the default branch)

No response

[ggutoski]

See https://github.com/EspressoSystems/HotShot/pull/2149#discussion_r1412615187

We need to ensure that chunk_size recovery_threshold is sufficiently smaller than num_storage_nodes so that our security assumption (f-fraction malicious nodes) implies that there is a sufficiently large number of honest storage nodes to recover the payload. Typically this ratio should be like 2x or 4x.

[mrain]

Current VID parameter setting is UNSAFE! https://github.com/EspressoSystems/HotShot/blob/39127341371bac1d747ca905e5fd822890d28b2b/crates/types/src/vid.rs#L56

When num_storage_nodes is near a power of two, for example 17. recovery_threshold is set to 16 so we only have 1 redundancy. In this case, recoverability cannot be guaranteed if we have 1/3 corrupted party.