Validate Poseidon `hash_pair` input

[tzerrell]

Our Poseidon/Poseidon2 hash_pair functionality is intended to work with Digests generated by Poseidon hashing. However, prior to this PR, it does not perform checking to ensure that its input Digests are in this format. This means a developer unaware of this nuance might accidentally write code that expects these hash_pair functions to work as hash functions on general Digests with values outside those possible from Poseidon hashing, which could create a vulnerability depending on the use case.

This PR adds an assert that validates all inputs are in the required format by adding the ability to test that words in a Digest are elements of the underlying field in reduced form. Thus, any developer misusing hash_pair in the above way would hit this assert instead of running to completion and producing a "hash" that does not have all the security properties such a developer might expect.

[vercel[bot]]

The latest updates on your projects. Learn more about Vercel for Git ↗︎

Name	Status	Preview	Comments	Updated (UTC)
docs-website	✅ Ready (Inspect)	Visit Preview		Apr 24, 2024 7:02am
reports	❌ Failed (Inspect)			Apr 24, 2024 7:02am
reports-and-benchmarks	✅ Ready (Inspect)	Visit Preview		Apr 24, 2024 7:02am
website	✅ Ready (Inspect)	Visit Preview	💬 Add feedback	Apr 24, 2024 7:02am

[nategraf]

This is very helpful, and looks good to me 👍

Removed my approval just pending any bench-marking we can do. I know you ran it locally, but we should think a bit on what more we might want to do. For example, we should confirm the same lack of performance diff occurs on a CUDA machine.

[flaub]

I've been thinking about this and wondering if we could change the structure of a Digest so that it prevents misuse by leveraging the type system more.

[tzerrell]

Summarizing what I understood from our in-person discussion:

• We have not seen perf impacts in my CPU testing, and we expect to not see perf impacts (because running 16 u32 < ops is small compared to the whole of Poseidon)
• This doesn't change CUDA/Metal code because this is on the verification side, which isn't GPU accelerated
• The proof system should not be using this hash_pair on values >= P. Also, the hash_pair code is not a very sensible thing to use outside the proof system, although at the moment it is public in a way that outside developers in principle could use & misuse it without warnings. Adding this assert has negligible performance impact and prevents misuse by us or others from causing security defects.
• There may be deeper changes that are unnecessary for this specific problem but make it harder to create similar sharp edges in the future. E.g. @flaub's comment "change the structure of a Digest so that it prevents misuse by leveraging the type system more," and I know @nategraf has been thinking about this as well. These can be handled in other PRs.

[tzerrell]

Checking in on this PR, because GitHub is flagging this as "approved", but the only approval (from @nategraf) has been removed (https://github.com/risc0/risc0/pull/1372#issuecomment-1906998538) -- are we ready to land this?

[nategraf]

In aba887d I pushed a change to fix the benchmarks in the benchmarks directory. These were broken because they expected to a CompositeReceipt back from the prove method, but this was changed in https://github.com/risc0/risc0/pull/1325 and updating this location was missed.

[tzerrell]

In aba887d I pushed a change to fix the benchmarks in the benchmarks directory. These were broken because they expected to a CompositeReceipt back from the prove method, but this was changed in #1325 and updating this location was missed.

These changes look fine to me; were you then able to run benchmarks?

[tzerrell]

Fascinating! Yay for empiricism, because I didn't think these asserts were in code used by the GPUs -- but with this data I double-checked, and they are indeed run even on GPU.

Given that and the noticeable performance slowdown, I think we should pause this until we see what comes of your type cleanup work.

[flaub]

We now have better benchmark comparisons and I'm not seeing any perf regression here: https://github.com/risc0/risc0/actions/runs/8811852210?pr=1372