GHSA-c873-wfhp-wx5m: 
Rust vulnerability analysis and mitigation

A high-severity vulnerability was discovered in SP1's STARK verifier affecting versions prior to 4.0.0. The vulnerability encompasses three main issues: missing validation checks in chipordering for preprocessed columns, underconstraint of the iscomplete boolean flag in the recursive verifier, and incorrect implementation of polynomial evaluation claims verification in the FRI-based polynomial commitment scheme. The vulnerability was identified through collaborative efforts from multiple teams including Succinct, Aligned, LambdaClass, 3MI Labs, and individual researchers Lev Soukhanov and Onur Kilic (GitHub Advisory).

The vulnerability consists of three technical issues: First, the prover-provided chipordering lacked proper validation for preprocessed column indexes. Second, the iscomplete boolean flag in the recursive verifier was underconstrained, particularly in the first layer of recursion. Third, in the FRI-based polynomial commitment scheme implementation, evaluation claims were not properly observed into the challenger before sampling coefficients for random linear combinations. These issues were present in the STARK verifier implementation and its integration with the Plonky3 dependency (GitHub Advisory).

The vulnerability affects the soundness of both the Rust SDK for verifying compressed proofs and the on-chain verifier for deferred proofs. While the recursive verifier and on-chain verifier were protected from the chip_ordering vulnerability due to pre-generation and merkle proof verification of verifier programs, other components remained vulnerable (GitHub Advisory).

The vulnerabilities were addressed in version 4.0.0 through multiple fixes: adding validation checks for chipordering by comparing indexed chip names with stored verifying key information, implementing proper assertcomplete function calls to constrain the is_complete flag, and correctly observing evaluation claims into the challenger in the Plonky3 integration. All previous versions have been deprecated and their verifiers frozen to prevent production use of vulnerable versions (GitHub Advisory).