Incompatibility using nightly Rust (1.69.0-nightly)

[teor2345]

We're seeing what we think is a miscompilation using nightly Rust (roughly 2023-02-15 onwards).

Using stable Rust, our halo2 test vectors pass. Using nightly Rust, they fail with a ConstraintSystemFailure:

---- primitives::halo2::tests::verify_generated_halo2_proofs stdout ---- Message: assertion failed: verify_orchard_halo2_proofs(&mut verifier, shielded_data).await.is_ok() Location: zebra-consensus/src/primitives/halo2/tests.rs:164

https://github.com/ZcashFoundation/zebra/actions/runs/4251106918/jobs/7393038170#step:14:1940 https://github.com/ZcashFoundation/zebra/actions/runs/4251106918/jobs/7393038041#step:14:11875

I have only tested on Linux so far.

Here's the first instance we saw on 15 February: https://github.com/ZcashFoundation/zebra/pull/6163#issuecomment-1430688218

[ebfull]

Thanks for the report. Coincidentally, we were investigating a related issue on the orchard crate where tests failed on 32-bit platforms. It turns out that both issues stem from the same bug: the V1 floor planner in halo2_proofs incorrectly depends on an unstable sort algorithm that is not guaranteed by the Rust developers to produce identical results between versions of Rust. (Recent changes/optimizations to the sorting algorithm have landed on nightly.) It also behaves differently depending on whether the target architecture is 32-bit or 64-bit, explaining the orchard test failures we saw on 32-bit platforms.

We need the orchard crate to enforce that halo2_proofs uses the original pattern-defeating quicksort algorithm from libcore 1.56.1 to maintain consensus compatibility for Zcash between architectures and versions of the Rust compiler. Thus, we're planning on deploying a crate (https://github.com/zcash/halo2_legacy_pdqsort) which extracts this algorithm from libcore and unifies its behavior between 32-bit and 64-bit architectures. Then, we'll add a feature flag to halo2_proofs which uses this sorting algorithm for compatibility purposes, but otherwise defaults to the (correct) usage of a stable sort algorithm to avoid this problem in the future for other users. orchard will be updated to set this feature flag to maintain consensus compatibility.

[teor2345]

@ebfull just a note about cargo's non-standard semver implementation:

• if you release the fixed orchard version as 0.3.1, cargo will upgrade all the existing dependencies to 0.3.1 as soon as a single dependency upgrades
• if you make it 0.4.0, every dependency will need to upgrade, and until they have, both 0.3.0 and 0.4.0 will be compiled into the same binary (and their types will be considered incompatible, even if they have the same names)

This happens because cargo treats 0.3.0 as 3.0.0 when resolving dependencies. So 0.3.0 and 0.4.0 are not compatible, and they will both be compiled into the binary: https://doc.rust-lang.org/cargo/reference/resolver.html#semver-compatibility

[str4d]

This will be fixed as 0.4.0, because the fix involves changing the default external behaviour of floor_planner::V1 (the existing behaviour will only be preserved - for 64-bit targets - via a default-off feature flag). It isn't possible to fix this without changing some external behaviour for some target and/or Rust version, so better to fix it uniformly.

[daira]

Fixed by #739. (We normally close tickets when the fix is merged to main, even though this isn't in a release or used by the orchard crate yet.)