feat: add blake2b compression precompile

[0xkanekiken]

The implementation is based on reference #180 and partially addresses issue #231. In the Blake2b hash function, the state and message elements are represented as u64 values, whereas the sp1 standard supports u32 words. As a result, each u64 is implemented using two u32 limbs, with appropriate handling for this format.

Furthermore, two operations for u64 data types have been introduced:

• Fixed right shift for u64.
• Addition for u64.

The XOR operation for u64 can be derived from the XOR operations of individual u32 limbs.

To-Do:

• [x] Add tests.
• [x] Integrate with sp1.

[0xkanekiken]

encountered the following verification error and need to figure out how to resolve it

[kevjue]

@0xkanekiken - I see that your PR is modeled off of the Blake3 precompile. I recently fixed a bug in that precompile which I believe also affects this PR.

[0xkanekiken]

@kevjue- thank you. I had the same question when I was taking a look at the constraints of blake3. However, I noticed that the round_index was updated to ROUND_COUNT, which seemed to make the constraint valid. In fact, the tests for blake3 were also passing.

https://github.com/succinctlabs/sp1/blob/4cf63779809d0da483822b897073d3c4bb13dcfe/core/src/syscall/precompiles/blake3/compress/trace.rs#L108-L116

I attempted to incorporate the fix you introduced, but I am still encountering the NonZeroCumulativeSum error. Is there a more systematic approach to evaluating all the AIR and determining whether it satisfies the constraints or not?

[kevjue]

@0xkanekiken - Ya, the fix PR removed the need for setting round_index. That was there to deal with the very last real row of blake3 where it expected the next (which would be a padded row) row to have a value of round_index + 1, which would be ROUND_COUNT.

Regarding the NonZeroCumulativeSum issue, that means that something is inconsistent with your interactions (a term we use for communication between chips).

You can try adding this function (https://github.com/succinctlabs/sp1/blob/049410580e3945f1f90767f740ed6c7696baefdf/core/src/lookup/debug.rs#L112) in your test case which will output any inconsistencies. Here is an example of how to use it: https://github.com/succinctlabs/sp1/blob/049410580e3945f1f90767f740ed6c7696baefdf/core/src/memory/global.rs#L200.

I actually suspect that all your constraints in your blake2b air related to the blake logic are fine. You normally encounter the NonZeroCumulativeSum after the constraints for the AIR are checked. You may want to check your memory constraints as that uses interactions.

[0xkanekiken]

Thank you for all the guidance and support! Indeed, the problem stemmed from how I defined the memory access AIR constraints. I've addressed this issue in https://github.com/succinctlabs/sp1/pull/321/commits/54a416ec651e9ae8e586035dce7147d5e0dfb032. Consequently, the tests are passing, and I'm able to generate the proof. It's ready for a review now.

[kevjue]

Thanks for the PR @0xkanekiken ! In general, it looks great! But we'll take a closer look at it soon.

[puma314]

At some point, we should merge a PR like this for the blake2b precompile if there is further demand, but for now it's not high priority and this PR is quite out of date so closing for now.