{"id":"ec896957-e994-4568-9eba-ff44cac391c4","arxiv_id":"2607.16533","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"opOL is a Hoare-style logic with priv/leak outcome assertions and a Frame rule that stays sound under oblivious adversaries by treating adversarial schedule consumption as a separation-logic resource.","lead":"Randomized programs can be made harder to exploit by an adversary that cannot see the coin flips, but proving that is hard. This paper introduces opOL, a program logic that tracks how much of the adversary's fixed choice tape each run consumes, enabling compositional proofs of independence, correctness, and almost-sure termination.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"opOL's soundness is relative to a fixed tape with count-only observability; the equivalence to the informal oblivious adversary is unproved and is load-bearing for Frame/ND.","rationale":"The reader's weakest_assumption is exactly the modeling premise I find most load-bearing: the informal oblivious adversary is equated with a fixed tape whose only observable is scheduler consumption (the current index). I agree with that assessment. I considered the internal soundness argument carefully—the monad/DCPO structure, the Frame rule proof, the ND rule's use of count-stable preconditions, and the Bounded-Rank block-decay argument—and found no concrete internal contradiction within the stated semantics. The appendix proofs are detailed and the resource algebra is coherent. The unshipped Lean 4 artifact is a reproducibility gap rather than a mathematical objection. The modeling premise is the single most important concern because it is the bridge between the formal theorem and the intended adversary class: if the adversary has observables other than tape position—timing, loop-iteration counts, public memory, I/O—then the compositional guarantees and all three case studies do not follow from Theorem 5.2. The paper itself asserts in Section 4 that a source is leaked iff it may depend on the consumed scheduling bits, but it does not justify why this is the only leak channel. This supports the reader's CONDITIONAL verdict; I do not recommend moving it to ACCEPT or REJECT until the threat model is sharpened and, ideally, the Lean artifact is released.","tokens_in":81109,"tokens_out":16982,"duration_ms":198858,"concrete_test":"Analytical check: formalize a timing-aware oblivious adversary by extending the semantics to O_T(X)=Sched->N->D⊥(X×N×T), where T is a step counter incremented on every command (including loop iterations) and observable to the adversary, while sampled values remain hidden. Re-run the soundness proofs for Frame and NAssign under this semantics, and test the program C = x:≈Ber(1/2); z:=x; while x=1 do x:=0; y←[0,1]. If the existing proof rules still derive independence of z and y but T-validity gives P[z=y]=1, then the fixed-tape/count-only premise is essential and must be stated as an explicit threat-model restriction. Alternatively, ask the authors for a formal definition of the adversary's observable events and a proof that they are isomorphic to count observations; absent that, confine correctness claims to the fixed-tape model.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 5.2 proves soundness of opOL with respect to the denotational model O(X)=Sched->N->D⊥(X×N) (Section 3.2), where the adversary is an infinite tape s∈N->N and the only scheduling-observable is the current index n. The logic's distinctive rules—Frame (Figure 7), ND, NAssign, and the priv/leak distinction—all depend on this characterization: a random source is private exactly when the branch-dependent count marginal is independent of the sample (Section 4.3, Obs_priv), and the sound Frame rule works by keeping counts out of the frame. The paper never defines the informal adversary's observation interface or proves that 'cannot see random draws' is equivalent to 'reads a fixed tape and observes only n.' This is load-bearing: consider C = x:≈Ber(1/2); z:=x; while x=1 do x:=0; y←[0,1]. In O, the loop consumes zero scheduler entries (bits(while)={0}, Definition A.2), so z remains private and the Frame/NAssign rules permit a proof that z and y are independent. An adversary that can observe elapsed iterations—but not sample values directly—can see whether the original x was 1 and choose y=z, making P[z=y]=1. Thus Theorem 5.2 does not transfer to that adversary. This is not an internal inconsistency: the metatheory is coherent relative to O. But the advertised threat model, 'an oblivious adversary resolves nondeterminism without seeing the outcomes of random draws,' is broader than the fixed-tape model unless the observation interface is formally restricted. The case studies inherit this unstated restriction.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces Oblivious Probabilistic Outcome Logic (opOL), a Hoare-style logic for probabilistic programs whose nondeterminism is resolved by an oblivious adversary modeled as a fixed infinite schedule tape. The semantics is built on monad O(X) = Sched -> N -> D⊥(X×N), which records both the output memory and the number of schedule entries consumed. The logic tracks schedule consumption as a resource, distinguishes private from leaky random sources through probabilistic independence, and provides compositional rules including a restricted Frame rule, rules for nondeterministic choice, and a bounded-rank rule for almost-sure termination. The main metatheorem (Theorem 5.2) asserts soundness of all derivable triples with respect to this denotational model. The paper also sketches three case studies—Monty Hall, leader election, and randomized paging—and claims that the metatheory and case studies are mechanized in Lean 4.","tokens_in":81537,"tokens_out":5718,"duration_ms":71739,"significance":"If the results hold, opOL is a substantial advance over adaptive-adversary logics such as dOL and pcOL: it recovers a sound Frame rule for nondeterministic choice under an oblivious adversary and gives compositional, total-correctness-style reasoning for programs that are outside the reach of adaptive models. The paper's core contribution is carefully stated: the resource-based tracking of schedule consumption, the private/leaky distinction, and the direct soundness proofs against a denotational semantics are presented in detail in the appendices. The three case studies are nontrivial and provide concrete evidence of expressiveness. The claimed Lean mechanization, if accompanied by a verifiable artifact, would be a further significant strength; as submitted, that claim cannot yet be checked.","major_comments":[{"comment":"The paper equates 'oblivious adversary' with a fixed schedule tape whose only observable is the tape index n. The informal threat model ('does not see the outcomes of random draws') is broader: an adversary that could observe elapsed iterations, as in C = (x:≈Ber(1/2); z:=x; while x=1 do x:=0; y←[0,1]), would learn x even though bits(while)={0} makes z private in O. The soundness theorem is relative to the fixed-tape model, so this is not an internal inconsistency; however, the advertised scope is load-bearing for the Frame, ND, NAssign, and priv/leak rules. Please either formalize the adversary's observation interface and prove equivalence, or explicitly state that the logic is scoped to the fixed-tape model and that other side-channel observables are out of scope.","section":"Sections 2.1, 3.2, Definition 5.1"},{"comment":"The paper repeatedly claims 'The opOL metatheory and case studies are mechanized in Lean 4' and lists Lean mechanization as a contribution, but the submission contains no Lean artifact, no code listing, no link, and no machine-checkable proof. The visible appendix contains paper proofs, not Lean sources. This claim is therefore unverifiable as submitted. Either provide the artifact (and instructions for checking it) or remove/qualify the mechanization claim.","section":"Abstract, Section 1, Section 5"},{"comment":"Theorem 3.1 states that the oblivious semantics refines the adaptive convex powerdomain semantics, and the text says 'To show that result formally'—but no proof appears, and the statement is not accompanied by a specific proof reference. This theorem is used to argue that adaptive proof rules are sound in the oblivious setting. Although Theorem 5.2 is proved directly in Appendices E/F, the missing proof of Theorem 3.1 is still a gap in a stated contribution. Provide a proof or a precise citation to an accessible proof.","section":"Theorem 3.1 (Section 3.4)"}],"minor_comments":[{"comment":"Typo: 'Conseqence' should be 'Consequence'.","section":"Figure 7"},{"comment":"The rule label 'SAMP' is inconsistent with the text's 'Samp'; use one style consistently.","section":"Figure 6"},{"comment":"The phrase 'adversarial choice is an observable effect' is potentially misleading outside the formal model. Consider saying 'observable effect in the model' to emphasize that the model tracks only the schedule index, not timing or other side channels.","section":"Section 2.3"},{"comment":"bits(while e do C end) is an infinite union; it may be worth noting that this is a syntactic over-approximation and that the fixed-point semantics is what the soundness proof actually uses.","section":"Definition A.2"}],"recommendation":"major_revision","confidential_remarks":"This is a strong and carefully written paper: the resource algebra, the direct soundness proofs in Appendices E/F, and the case studies are convincing evidence that the logic works for the fixed-tape oblivious model. My main reservations are the unverifiable Lean claim, the unproved Theorem 3.1, and the mismatch between the informal threat-model phrasing and the formal count-only observation model. None of these strike me as unfixable; they require either additional content or clearer scoping. I therefore recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: opOL is a real step forward for reasoning about probabilistic programs with non-adaptive schedulers. The tape-of-choices monad, the priv/leak distinction, and the Frame rule built on schedule consumption are genuinely new relative to dOL, pcOL, and Fan et al. The paper is careful: the denotational semantics is worked out in detail, the soundness proofs for the sequential and structural rules in the appendix look substantive, and the case studies are small but well-chosen to show where the adaptive adversary is too strong. The Lean mechanization claim is nice but currently unverifiable: no artifact ships, so for now it is an assertion, not evidence.\n\nThe soft spot is the modeling premise. The informal adversary is one that “cannot see random draws.” The formal adversary is a fixed tape with only the current tape index observable. These are not the same. The stress-test loop example is the right one: a loop whose body consumes no schedule entries but whose iteration count depends on a coin. In the tape model the coin is private and the Frame/ND rules apply; an adversary that can count iterations learns the coin and can correlate its next choice. Since the distinctive rules all lean on count-only observability, this is a load-bearing assumption, not a cosmetic one. The paper never defines the adversary’s observation interface, and it should.\n\nEverything else holds up. The heavy self-citation is to the authors’ own Outcome Logic line, but the cited results are relevant and the novelty claim against Fan et al. is backed by actual differences. I found no internal inconsistency in the visible material. Theorem 3.1’s proof is mostly deferred to prior work; that is acceptable if the full argument is in the appendix, but a referee should check that the refinement direction is stated correctly.\n\nWho is this for: PL researchers working on probabilistic program logics, scheduler models, or compositional reasoning about oblivious adversaries. It deserves a serious referee. A revision that sharpens the threat model and ships the Lean artifact would make it considerably stronger; I would send it to review.","headline":"A substantial, well-engineered program logic for fixed-tape oblivious schedulers, but the advertised threat model is broader than the formal model unless the observation interface is pinned down.","tokens_in":82013,"tokens_out":3566,"would_cite":true,"duration_ms":46298,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q60","03B70"],"pacs":[],"model":"deepseek-v4-flash","headline":"opOL is a proof system whose derivable triples are valid for every oblivious-adversary schedule, with frame preservation and zero nontermination probability.","keywords":["probabilistic program logic","oblivious adversary","separation logic","probabilistic independence","scheduler consumption","almost-sure termination","randomized algorithms","total correctness"],"falsifier":"Construct a program whose random branch and schedule count are independent, but where an adversary with a fixed tape can still correlate its later choice with the random draw through an observable not represented in the denotation, such as execution time or memory access pattern; in opOL's model such a leak is invisible, so a derivable triple could fail against that stronger adversary.","tokens_in":81027,"feed_emoji":"🎲","tokens_out":5554,"duration_ms":63854,"temperature":0.7,"pith_summary":"The paper aims to make correctness proofs for randomized programs with an oblivious adversary compositional. Its central claim is a soundness theorem: any triple derived in opOL is valid against every fixed schedule, preserves framed resources, and implies almost-sure termination. The key move is to model the adversary as an infinite tape of choices and to track how many tape entries each branch consumes; a random outcome is private exactly when it is independent of that count. This lets the logic keep a frame rule for nondeterministic choice, which prior adaptive-adversary logics could not. The paper tests the logic on paging, leader election, and Monty Hall, where the obliviousness assumption is essential.","feed_headline":"Counting the adversary's moves verifies randomized programs","feed_subtitle":"The logic tracks how many schedule entries random branches consume, keeping private randomness safe for later proofs.","key_machinery":"The oblivious monad O(X)=Sched→N→D⊥(X×N), a probability monad layered over a reader for the immutable schedule and a state for the current index. The count of consumed tape entries is the only channel by which control flow can leak random outcomes to the fixed schedule; assertions are resources over probability spaces with memory and count observations, and the priv/leak modes attach to probabilistic outcome conjunctions. The Frame rule and ND rule are sound precisely because stability and privacy conditions control this count channel.","core_discovery":"The central claim is that obliviousness can be made compositional by encoding schedule consumption as a resource. The denotation O(X)=Sched→N→D⊥(X×N) represents a program as a function from a fixed schedule and current index to a distribution over outputs and updated indices. Random branches that consume different numbers of schedule entries can leak entropy to the adversary; assertions carry a priv/leak mode that records whether a sampled variable is independent of the count. Soundness shows every derivable triple holds for all schedules and, since validity quantifies over resources without nontermination, implies total correctness. The logic recovers adaptive reasoning as a special case an","pith_inferences":["If the tape-index channel is the only leakage, the logic's guarantees suggest a quantitative measure: the probability that the adversary can guess a random source is governed by the marginal of the count conditioned on that source.","The model is a template for other resource-aware logics: any observable consumption channel, such as time or memory access pattern, could be wrapped as a resource and tracked with the same independence discipline.","The paging proof could plausibly be extended from bounds on the probability of many misses to expected competitive ratios, since the invariant already bounds the miss distribution.","Concurrency is the stated next step; the tape model assumes adversarial choices occur only at explicit nondeterministic commands, so the resource bookkeeping would need extension if scheduling occurs at every interleaving step."],"forward_implications":["Every derivable opOL triple is valid for all schedules: postconditions hold, frames are preserved, and nontermination probability is zero.","Adaptive-adversary proof rules remain sound in the oblivious model because the oblivious semantics is a refinement of the adaptive powerdomain semantics.","Private random sources can be framed across later nondeterministic choices, so independence facts survive globally rather than being destroyed by each adversarial step.","The Bounded-Rank rule yields almost-sure termination proofs by giving a uniformly positive probability of rank decrease per block of iterations.","Case studies on paging, leader election, and Monty Hall show the logic can express guarantees that adaptive logics cannot."],"fun_headline_variants":["Logic verifies programs against adversaries blind to random draws","opOL: New logic ensures random draws stay hidden from adversary","Scheduling-aware logic keeps random outcomes private from foes","Verifying probabilistic programs when adversaries can't see randomness","Compositional logic makes obliviousness verifiable for randomized programs"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The guarantees rest on the modeling premise that an oblivious adversary's only power is a fixed tape of choices read in order, so that a random outcome is hidden exactly when it is independent of the tape position; if the real adversary could observe timing or partial outputs, the logic's compositionality would not transfer.","fun_headline_variants_meta":{"raw":{"variants":["Logic verifies programs against adversaries blind to random draws","opOL: New logic ensures random draws stay hidden from adversary","Scheduling-aware logic keeps random outcomes private from foes","Verifying probabilistic programs when adversaries can't see randomness","Compositional logic makes obliviousness verifiable for randomized programs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001117,"raw_usage":{"total_tokens":4483,"prompt_tokens":739,"completion_tokens":3744,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":483,"completion_tokens_details":{"reasoning_tokens":3664}},"tokens_in":483,"tokens_out":3744,"duration_ms":25411,"temperature":1.0,"reasoning_tokens":3664,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T20:41:42.561833+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a program whose random branch and schedule count are independent, but where an adversary with a fixed tape can still correlate its later choice with the random draw through an observable not represented in the denotation, such as execution time or memory access pattern; in opOL's model such a leak is invisible, so a derivable triple could fail against that stronger adversary.","supporting_citations":[],"review_version":1}