Allow odd full rounds
Closed this issue · 5 comments
Currently, neptune expects that the number of full rounds R_F is an even number, as evidenced by the number of full rounds in the first and second halves being the same R_f = floor(R_F / 2).
All three Poseidon implementations (static, correct, and dynamic) use R_f as the number of first and second half full rounds, which is correct only when R_F is even (currently R_F = 8 for all Filecoin applications). However, when R_F is odd, the number of second half full rounds should be R_F - R_f (so you don't lose the last full round of the second half).
Required Changes
- In all three Poseidon implementations, change the number of second half full rounds to
self.constants.full_rounds - self.constants.half_full_rounds. - Remove this
unimplemented!panic.
I think Poseidon is required to have an even total number of full rounds (R_F)— because the same number of full rounds (R_f) is specified to occur both before and after the partial rounds. This is from page 6 of the current version of the paper:
What makes you think an odd number of full rounds is permissible?
This requirement also appears to be encoded in the way the full round numbers are calculated. The implementation of calc_round_numbers appears to only ever return values for rf which are multiples of 2. (Candidates begin from two and are only ever incremented by 2.)
Ok, that makes sense, I forgot about the step_by(2). I was going from the security inequalities in the paper which never require an even R_F, just that the tuple (R_F, R_P) minimizes the number of S-boxes. Also the paper uses the the symbol R_F/2 which is ambiguous, but I assumed to be integer division.
So I'll close this issue now that you pointed out the step_by(2), I hadn't looked at that piece of code in a while because it's not actually in the paper.
Sounds good. I think it makes sense to keep the panic!, but maybe change the text and remove the comment suggesting that anything needs to change. This is a code path that shouldn't be possible to hit, so panicking if we do is appropriate and documents that invariant.