(Potential) Mismatch with Poseidon Hash paper

[BoyuanFeng]

Thanks for the wonderful work!

It seems there are a few (potential) mismatches between round_numbers.rs and the Poseidon Hash paper. Is there any reason for this mismatch? More specifically,

1. In Line 82, we are using let rf_interp = 0.43 * m + t.log2() - rp;. In Poseidon Hash paper, Eq (3) requires
   

For BLS12-381 with , M=128, and , we should add something like log_5(t) instead of t.log2().

2. Line 82 ~ 83 is also different from Eq (5) in Poseidon hash paper.

[porcuquine]

Since @DrPeterVanNostrand wrote this code, I will restrict my initial comments to surface impressions from comparison with the reference implementation. All else aside, I believe we have tests establishing that the code here generates the same values as the reference code for width up to 125.

That said, it would obviously be beneficial to clear up any imprecision or discrepancies. I'd like to hear @DrPeterVanNostrand's opinion on the issue (problem, best fix) before digging in further myself.

The line you quote seems to be an almost direct port from the original reference implementation.

For clarity, are you suggesting that implementation is also wrong?

It does look like line 83 assumes min(n, M) to be n — whereas it was previously taken to be M (and given the hard-coded constants, M seems to be correct).

The same comment applies to line 84.

[BoyuanFeng]

Thanks for the quick reply!

1. I do not have a strong opinion or proof on whether the implementation is wrong. I am just wondering why the implementation is (slightly) different from the paper, as detailed earlier. Would this difference lead to any security concerns?
2. The hardcoded results are actually (slightly) different from the paper (Table 2). For example, Line 104 hardcoded r_p = 55 when t = 3 and M=128 for BLS12-381. However, in Table 2, with BLS12-381 and M=128, r_p is specified as 57 when t=3. Similar difference also shows for t = 5. Is there any reason behind this difference?

[porcuquine]

Hi, @BoyuanFeng. It seems @DrPeterVanNostrand has not had time to look into the main details you raised yet. With regards to 2. above, I'm not sure why the Table 2 you linked has those numbers. The version of the paper that was current when neptune was audited doesn't have that table. If you look at the relevant table there, it seems to agree with the round numbers in the neptune source (also tested against the reference script): https://eprint.iacr.org/archive/2019/458/1580899304.pdf.

[porcuquine]

Looking a little more closely, this particular discrepancy (number 2 above) seems likely to stem from the introduction of a 'security margin' (section 5.4), arbitrarily chosen to be 7.5% for the numbers used in Table 2. This seems to be analogous to the Strength::Strengthened option we included in the initial implementation. There we used the margin of 25%, suggested as something which would almost certainly be safe, even in the case of a newly-discovered attack. We had considered performing a trusted setup using the strengthened hash in case we needed to switch suddenly. In the end, we decided not to do so preemptively.