Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

sha256 with variable length disagree with sha256 with constant length of the same length #5761

Closed
TomAFrench opened this issue Aug 19, 2024 · 0 comments · Fixed by #5760 or #5779
Closed

sha256 with variable length disagree with sha256 with constant length of the same length #5761

TomAFrench opened this issue Aug 19, 2024 · 0 comments · Fixed by #5760 or #5779
Labels
bug Something isn't working

Comments

@TomAFrench
Copy link
Member

Consider the program

fn main(input: [u8; 2], toggle: bool) {
    let size: Field = 1 + toggle as Field;
    assert(!toggle);

    let variable_sha = std::sha256::sha256_var(input, size as u64);
    let constant_sha = std::sha256::sha256_var(input, 1);

    assert_eq(variable_sha, constant_sha);

}

We should expect that this program passes for the inputs below:

input = [0, 0]
toggle = false

This is as size == 1 in this case and so the lengths being passed to the sha256_var calls are the same (and so the hashes are the same).

However this program fails as the two hashes produced are different.
@TomAFrench TomAFrench added the bug Something isn't working label Aug 19, 2024
@TomAFrench TomAFrench mentioned this issue Aug 19, 2024
Merged
5 tasks
@guipublic guipublic mentioned this issue Aug 22, 2024
Merged
5 tasks
github-merge-queue bot pushed a commit that referenced this issue Aug 22, 2024
@guipublic
fix: do not use predicate for index in array operation, when the inde…
9d8f2bd 
…x is safe (#5779)

# Description

## Problem\*

Resolves #5761

## Summary\*

For array operation, we keep the index when it is safe, instead of using
the predicate.


## Additional Context



## Documentation\*

Check one:
- [X] No documentation needed.
- [ ] Documentation included in this PR.
- [ ] **[For Experimental Features]** Documentation to be submitted in a
separate PR.

# PR Checklist\*

- [X] I have tested the changes locally.
- [X] I have formatted the changes with [Prettier](https://prettier.io/)
and/or `cargo fmt` on default settings.
github-merge-queue bot pushed a commit that referenced this issue Aug 27, 2024
@vezenovm
fix(sha256): Perform compression per block and utilize ROM instead of…
c52dc1c 
… RAM when setting up the message block (#5760)

# Description

## Problem\*

Resolves #5761 

Resolution to performance blow-up found with sha256_var.

## Summary\*

### Issue

The crux of the blow-up was the result of calling `sha256_compression`
inside of the same loop where we build the message block. In the current
`sha256_var` algorithm we are looping over the entire message and
conditionally checking a msg byte pointer (the pointer into the msg
block) to determine whether we have filled up a msg block and should run
the sha compression. However, in a circuit this leads to us calling the
compression opcode `N` times where `N` is the size of the message.

We also were utilize RAM to build our message block when we do not have
to do so. We can instead construct our block outside of the circuit and
verify that the block has been constructed as we expect with assertion
that just require ROM.

### Improvements

This PR produces a ~16x improvement in ACIR opcodes a >13x improvement
in backend constraints for the following circuit:
```rust
fn main(foo: [u8; 95], toggle: bool) {
    let size: Field = 93 + toggle as Field * 2;
    let hash = std::sha256::sha256_var(foo, size as u64);
    println(f"{hash}");
}  
```
#### master
nargo info:
```
+---------+----------------------------+----------------------+--------------+-----------------+
| Package | Function                   | Expression Width     | ACIR Opcodes | Brillig Opcodes |
+---------+----------------------------+----------------------+--------------+-----------------+
| sha256  | main                       | Bounded { width: 4 } | 125852       | 243             |
+---------+----------------------------+----------------------+--------------+-----------------+
| sha256  | print_unconstrained        | N/A                  | N/A          | 230             |
+---------+----------------------------+----------------------+--------------+-----------------+
| sha256  | directive_integer_quotient | N/A                  | N/A          | 6               |
+---------+----------------------------+----------------------+--------------+-----------------+
| sha256  | directive_invert           | N/A                  | N/A          | 7               |
+---------+----------------------------+----------------------+--------------+-----------------+
```
bb gates:
```
{"functions": [
  {
        "acir_opcodes": 125852,
        "circuit_size": 597646,
```

#### This PR

Output of nargo info:
```
+----------------------------+----------------------------+----------------------+--------------+-----------------+
| Package                    | Function                   | Expression Width     | ACIR Opcodes | Brillig Opcodes |
+----------------------------+----------------------------+----------------------+--------------+-----------------+
| sha256_var_size_regression | main                       | Bounded { width: 4 } | 7768         | 1041            |
+----------------------------+----------------------------+----------------------+--------------+-----------------+
| sha256_var_size_regression | build_msg_block_iter       | N/A                  | N/A          | 299             |
+----------------------------+----------------------------+----------------------+--------------+-----------------+
| sha256_var_size_regression | pad_msg_block              | N/A                  | N/A          | 201             |
+----------------------------+----------------------------+----------------------+--------------+-----------------+
| sha256_var_size_regression | attach_len_to_msg_block    | N/A                  | N/A          | 298             |
+----------------------------+----------------------------+----------------------+--------------+-----------------+
| sha256_var_size_regression | print_unconstrained        | N/A                  | N/A          | 230             |
+----------------------------+----------------------------+----------------------+--------------+-----------------+
| sha256_var_size_regression | directive_integer_quotient | N/A                  | N/A          | 6               |
+----------------------------+----------------------------+----------------------+--------------+-----------------+
| sha256_var_size_regression | directive_invert           | N/A                  | N/A          | 7               |
+----------------------------+----------------------------+----------------------+--------------+-----------------+
```
bb gates output:
```
{"functions": [
  {
        "acir_opcodes": 7768,
        "circuit_size": 44663,
```

## Additional Context



## Documentation\*

Check one:
- [ ] No documentation needed.
- [ ] Documentation included in this PR.
- [ ] **[For Experimental Features]** Documentation to be submitted in a
separate PR.

# PR Checklist\*

- [ ] I have tested the changes locally.
- [ ] I have formatted the changes with [Prettier](https://prettier.io/)
and/or `cargo fmt` on default settings.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
bug Something isn't working
Projects
Noir
Status: ✅ Done
Milestone
No milestone
1 participant
@TomAFrench