WorksComputer Science
A counterexample to the soundness of the Flowering IOPP for codes on graphs
Abstract
The Flowering protocol of Delavenne, Medevielle and Roussel (ISIT 2025, arXiv:2501.14337) and its generalization by Delavenne and Lallemand (CANS 2025, arXiv:2508.10510) are Interactive Oracle Proofs of Proximity (IOPPs) for codes on graphs with Reed-Solomon local codes. Similarly to FRI for Reed-Solomon codes, the graph is recursively cut into isomorphic subgraphs and the word is folded along the cuts. We show that the soundness claims of both papers are false. The commit soundness proofs identify the vertex distance of a word to the code with the fraction of its unsatisfied local constraints, while only one inequality holds, in the wrong direction. We furthermore give an explicit counterexample.
Introduction
IOPPs like the FRI protocol [1] successively reduce a claim of the form for , and to a claim with , and is the folding of by some public coin randomness from the Verifier. The soundness analysis of these protocols then rely on the fact that with high probability on the public coin of the Verifier, the folding of a vector -far from the code is -far from .
In [3] the authors propose an analogous IOPP called Flowering, for codes on graphs [5, 4] whose coordinates are the edges of a regular graph and whose local views must lie in a Reed-Solomon code. The vertices of the graph are cut into two subsets of vertices, and the subvectors on the induced subgraphs are combined linearly. This construction is extended in [2] to collections of non-disjoint cuts. Both papers claim a soundness error smaller than that of FRI, valid up to the covering radius. However these soundness claims are false.
In Section 3, we locate the flaw in the proofs of commit soundness [3 Proposition 3] and [2 Proposition 4], we show that folding along a flowering cut does not preserve the Hamming distance, and we give a word on which a cheating Prover contradicts the soundness theorems of both papers.
Definitions and claim
We follow the definitions and notations of [3].
Definition 1 (-RIM). For , an -regular indexed multigraph (-RIM) is given by a map such that for all and , .
We say that is a petal if . A word on is a map such that for all and , . Denote the set of words on .
For and , denote the local view of at .
Definition 2 (Code ). Let and let be a Reed-Solomon code of length and dimension . The code on is defined by
Denote the relative Hamming distance, i.e. for , is the fraction of edges on which and differ. For and , .
Definition 3 (Cut-graph). For , the cut-graph is defined by if and otherwise. The edges leaving become petals.
Definition 4 (Flowering cut). A flowering cut is a partition together with a bijection that is an index-preserving isomorphism from to .
Denote for the map equal to the identity on and to on .
Definition 5 (Folding). For , the folding of is the word given for and by
Definition 6 (Blossoming sequence). A blossoming sequence is a sequence of -RIMs such that has a single vertex and each is the cut-graph of a flowering cut of .
For a blossoming sequence, denote and ; when applied to a word on , denotes the folding along .
We present the Flowering protocol of [3 Protocol 1] with parameter .
Definition 7 (Flowering protocol [3 Protocol 1]). Let and . The Flowering protocol is the following interactive protocol between a Prover and a Verifier where the Prover has access to and the Verifier has oracle access to .
Commit phase. For , the Verifier sends a uniformly random , and the Prover answers with oracle access to some .
Query phase, repeated independently times. The Verifier picks a uniformly random , and sets for . It checks that for all , and that .
The main result of [3, 2] is the soundness of the Flowering protocol [2 Theorem 2], which generalizes [3 Theorem 2] to collections of non-disjoint cuts. A flowering cut as above is a flowering cut collection of order 2 in the sense of [2 Definition 7]. For such collections, the protocol of [2 Definition 10] is the one above, where the Verifier reads whole local views ( in [2]). With rounds and repetitions, [2 Theorem 2] then reads as follows.
Flawed claim 8 ([2 Theorem 2]). Let , let be a blossoming sequence and let . For every Prover, the Verifier of the Flowering protocol accepts with probability at most
We give a counterexample to Flawed claim 8 in § 3.2.
Counterexamples
For , let be its set of unsatisfied vertices. Both papers prove Flawed claim 8 through a commit-soundness statement [3 Proposition 3], [2 Proposition 4] in the vertex distance . Its proof sets and , and uses (just before [3 Equation (3)], just after [2 Equation (6)]). Only holds: a codeword differs from at every unsatisfied vertex, and possibly at many others (§ 3.2).
Folding does not preserve the Hamming distance
We first show that folding may drastically decrease the Hamming distance, which rules out a proof similar to that of FRI.
Proposition 9. Let , , , and let have two vertices sharing the edge of index 1, each with petals (Figure 1). With and , the word given by and satisfies, for every ,
Proof. Since is the set of constant vectors and share an edge, is the set of constant words. The word equals 1 on the petals of and 0 on the other edges. Hence is at distance from the zero word, from the all-one word, and from the other constant words, and .
Moreover,
which differs from on a single edge out of .
Figure 1. Proposition 9 for . The common edge becomes the red petal, the only edge where differs from the codeword .
This does not contradict Flawed claim 8: for , the folding is not a codeword and the Verifier reads the whole local view of the single vertex of . We now hide the error at one vertex among many.
The claim is false
Fix , , , , so that has minimum distance . Fix a field of odd characteristic with . Let with , that is . Then is the complete graph . Let be the blossoming sequence of [3 Definition 10]: and , with the -th unit vector. Write , , . Every vertex of has a petal at each index of . This is illustrated in Figure 2.

Figure 2. First cut for and . The gray edges cross the cut and become petals of . The only unsatisfied vertex of is , and becomes a codeword after changing the red petal.
We first show in Lemma 10 that for every vertex , there are words on whose only unsatisfied vertex is .
Lemma 10. For every and , there is with for and .
Proof. Denote the dual code of . It is an MDS code of dimension , hence of minimum distance .
We first show that the local parity checks are linearly independent. Let such that for all ,
Since the value of on the edge appears in both and , this is equivalent to
For , denote and . Multiplying (1) by , summing over and using , we obtain
Since the characteristic of is odd, $1+\chi_b(s_\ell)=2\ne0$ whenever , and then . If , this holds for all , so . If , this holds for the indices such that , so has weight at most , and . Since is invertible in , the Fourier inversion formula gives for all $v\in V_0
Therefore the local parity checks are linearly independent.
Now let be the space of words whose local views at all lie in , and consider
Its kernel is , and by independence of the local parity checks, . Hence is surjective, which proves the lemma. □
We then show in Lemma 11 that such words are far from the code.
Lemma 11. If , then .
Proof. For , denote its Hamming weight. Let , and denote and
Since and , we have . Remark that if , then , so . In particular .
Let . Since , is a nonzero codeword of , so . As has no multiple edges, these nonzero coordinates lead to distinct vertices of , hence .
Each edge on which is nonzero is counted twice in . Therefore is nonzero on at least half of
edges, out of the edges of . Thus . Finally, since , and since for . □
We finally show in Proposition 12 that a cheating Prover makes the Verifier accept such a word with high probability.
Proposition 12. Let , , , and given by Lemma 10 with . For every , a Prover makes the Verifier accept with probability at least , whereas the bound of Flawed claim 8 tends to at most as . Hence Flawed claim 8 and [3 Theorem 2] are false.
Proof. Since has weight , we have , hence .
We first describe the Prover. Let be the first challenge of the Verifier, and let be the word equal to except at , where
Since , is a petal of , so . Let . If , then neither nor is , hence
If , then by Lemma 10,
Thus . The Prover sends , and then for . Since each local view of a folding is a linear combination of local views, for all . We now bound the acceptance probability. The checks of rounds pass by construction, and the final check passes since . Since and differ at most at , the check of round 1 fails only if . As is two-to-one from onto , this happens with probability . The repetitions being independent, the Verifier accepts with probability at least .
Finally, taking in Flawed claim 8 and using Lemma 11, the bound of Flawed claim 8 is at most
which is smaller than since . The bound of [3 Theorem 2] multiplies by a constant that equals 1 when has no petals [3 Proposition 1], so it is the same here.
For instance, let and . Since Hamming weights are integers, Lemma 11 shows that is at distance at least 9 of the 28 edges of from . The Prover is accepted with probability at least , while Flawed claim 8 with gives at most for . For larger , the Prover is accepted with probability at least , while the bound of Flawed claim 8 tends to at most .
References
- [1][BBHR18] E. Ben-Sasson, I. Bentov, Y. Horesh, and M. Riabzev. Fast Reed–Solomon interactive oracle proofs of proximity. In ICALP 2018, volume 107 of LIPIcs, pages 14:1–14:17, 2018.
- [2][DL25] H. Delavenne and L. Lallemand. Codes on any Cayley graph have an interactive oracle proof of proximity. In CANS 2025, volume 16351 of LNCS, pages 335–357. Springer, 2026. arXiv:2508.10510.arxiv.org/abs/2508.10510
- [3][DMR25] H. Delavenne, T. Medevielle, and É. Roussel. Interactive oracle proofs of proximity to codes on graphs. In IEEE International Symposium on Information Theory (ISIT), 2025. arXiv:2501.14337.arxiv.org/abs/2501.14337
- [4][SS96] M. Sipser and D. A. Spielman. Expander codes. IEEE Transactions on Information Theory, 42(6):1710–1722, 1996.
- [5][Tan81] R. M. Tanner. A recursive approach to low complexity codes. IEEE Transactions on Information Theory, 27(5):533–547, 1981.DOI
