FStarLang / FStarLang/FStar

`FStar.Bytes` is inconsistent: `repr_bytes` / `repr_bytes_size` prove `False`

Open
#4,476 0 comments 0 reactions 0 assignees View on GitHub
kind/unsoundness
Dominant language
F*
Stars
3.1k
Forks
267
Avg merge
10h 45m
Merged PRs (30d)
54

Description

## Summary

`FStar.Bytes` ships two mutually contradictory axioms. Any program that
opens `FStar.Bytes` can prove `False` — and hence anything at all — in one
line, with no `assume`, no `admit`, no tactic, no `--ext` flag and no
option changes. The resulting module verifies *and* extracts.

Because the offending lemma carries an `SMTPat`, no explicit lemma call is
even required: merely mentioning `fits_in_k_bytes 0 0` in a proof context
is enough. Ordinary `FStar.Bytes` clients can therefore hit this by
accident.

`FStar.Bytes` is an interface-only module: there is no `ulib/FStar.Bytes.fst`
and no OCaml realization under `ulib/ml/`. Every `val` in it is an unproven
axiom that F* trusts unconditionally.

## Repro

```fstar
module BytesReprBytes
module B = FStar.Bytes
let bad () : Lemma False = B.repr_bytes_size 0 0
```

```
$ fstar.exe BytesReprBytes.fst
Verified module: BytesReprBytes
All verification conditions discharged successfully
```

Everything follows:

```fstar
let one_is_two () : Lemma (1 == 2) = bad ()
let anything (a: Type) : Tot a = bad (); false_elim ()
let boom : int = anything int
```

This also extracts cleanly:

```
$ fstar.exe --codegen OCaml --odir out BytesReprBytes.fst
$ cat out/BytesReprBytes.ml
open Prims
let anything (uu___ : unit) : 'a= FStar_Pervasives.false_elim ()
let boom : Prims.int= anything ()
```

### No lemma call needed (`SMTPat`)

```fstar
module BytesReprBytesAuto
module B = FStar.Bytes
let bad () : Lemma False = assert (B.fits_in_k_bytes 0 0)
```

Also verifies.

## Root cause

`ulib/FStar.Bytes.fsti`:

```fstar
let fits_in_k_bytes (n:nat) (k:nat) = FStar.UInt.size n (8 * k)
type uint_k (k:nat) = n:nat{fits_in_k_bytes n k}

(** repr_bytes n: The number of bytes needed to represent a nat **)
val repr_bytes:
n:nat
-> k:pos{fits_in_k_bytes n k} // <-- result is a `pos`, i.e. >= 1

val repr_bytes_size:
k:nat // <-- `nat`, so `k = 0` is allowed
-> n:uint_k k
-> Lemma (ensures (repr_bytes n <= k))
[SMTPat (fits_in_k_bytes n k)]
```

- `repr_bytes`'s declared result type is `k:pos{...}`, so
`repr_bytes 0 >= 1`.
- `uint_k 0 = n:nat{FStar.UInt.size n 0} = n:nat{0 <= n /\ n < pow2 0}`,
which is inhabited exactly by `0`. So `repr_bytes_size 0 0` is a
well-typed application, and it yields `repr_bytes 0 <= 0`.

`1 <= repr_bytes 0 <= 0` is `False`.

The `k` argument of `repr_bytes_size` is the only place where `0` slips
through: the intended reading is "if `n` fits in `k` bytes then `k` bytes
are enough", but `k = 0` bytes trivially "fit" `n = 0` under
`UInt.size n 0`, while `repr_bytes` is specified never to return `0`.

## The interface is only well-typed because of the inconsistency

```fstar
val bytes_of_int:
k:nat
-> n:nat{repr_bytes n <= k /\ k < pow2 32}
-> lbytes k

val bytes_of_int_of_bytes:
b:bytes{length b <= 32}
-> Lemma (ensures (bytes_of_int (length b) (int_of_bytes b) == b))
[SMTPat (int_of_bytes b)]
```

Instantiating `bytes_of_int_of_bytes` at `empty_bytes` (`length = 0`)
mentions `bytes_of_int 0 (int_of_bytes empty_bytes)`. Since
`int_of_bytes empty_bytes : uint_k 0` is necessarily `0`, that application
requires `repr_bytes 0 <= 0` — precisely the false fact above. F* accepts
it, discharging the obligation with the `repr_bytes_size` `SMTPat`. So
`FStar.Bytes`'s own `ensures` clause is well-typed only *because* the
axiom set is inconsistent:

```fstar
module BytesIllTyped
module B = FStar.Bytes
let derived ()
: Lemma (B.bytes_of_int 0 (B.int_of_bytes B.empty_bytes) == B.empty_bytes) =
B.bytes_of_int_of_bytes B.empty_bytes
```

verifies.

## Suggested fixes

Any one of these removes the contradiction; the first is the smallest and
matches the intended meaning:

1. Strengthen `repr_bytes_size`'s first argument to `k:pos`.
2. Weaken `repr_bytes`'s result type from `k:pos{...}` to `k:nat{...}`, and
change `lemma_repr_bytes_values` so that `repr_bytes 0 == 0`. (This
changes the meaning of `repr_bytes 0` and will affect clients.)
3. Require `n:pos` in `repr_bytes_size`.
4. More broadly: `FStar.Bytes` is a sizeable axiom set with no
implementation and no realization, so nothing checks it for consistency.
Consider giving it a model (even a `Seq byte`-based one behind the
interface) so that these `val`s are discharged rather than trusted, or
at minimum adding a consistency smoke test.

## Prior art checked

Searched the FStarLang/FStar tracker (open and closed) for `repr_bytes`,
`repr_bytes_size`, `FStar.Bytes inconsistent`, and `Bytes unsound`. The
only `repr_bytes` hit is #86 (extraction of `Prims.int`), which is
unrelated. #2072 ("A soundness issue?") is about zero-size vectors in
HACL*'s Merkle trees, also unrelated. No issue reports this.

## Environment

- F* v2026.08.23, commit `f3dd580cd58cdc5ccc0a64e4697c8cdad5a9e208`
(latest release at time of writing).
- `ulib/FStar.Bytes.fsti` is byte-identical between that release and
current `FStarLang/FStar` `master`; the file has not been touched by any
recent change to this area.
- No flags, no `#set-options`, no `#push-options`, no tactics.

Contributor guide

Open the contributing guide

Research direction

Start with ulib/FStar.Bytes.fsti and reproduce the contradiction using the BytesReprBytes example from the issue. Inspect the repr_bytes and repr_bytes_size refinements, then evaluate the suggested smallest fix of requiring a positive byte count. Done means the reproducer no longer verifies False and a regression check covers the zero-byte case.

Written by the indexing model from the issue text.

Assessment

Domain
compilers
Issue type
Bug
Difficulty
3/5
Estimated time
1-2 days
Activity status
Active
Clarity
Clearly specified
Newbie friendliness
65/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.