Guidance on `-M` (`--preserve-mem-order`) for large ORAM: correctness vs. efficiency

[roostab]

Hi Marcel,

I'm using MP-SPDZ (0.4.2) to benchmark OptimalPackedORAM at scale, and I'd
really value your guidance on whether to compile with -M
(--preserve-mem-order). The efficiency-vs-correctness trade-off lands right
where it changes the numbers I report, and I can't tell from the docs how real
the correctness hazard is in practice.

Setup

replicated-ring-party.x (semi-honest, -R 64), OptimalPackedORAM accessed at
secret indices. I run it across a range: up to ~1M items, and with
entry widths from a few cells up to tens of thousands of cells (8- and 32-bit
values). Compile flags -M -E ring -R 64 -Y -Z 3 (no --budget / -l).

Measured effect of -M

compile-only, a wide-entry config (~900 items, each ~23k cells):

	-M	no -M
VM rounds	33,468	18,572 (−44%)
peak compile RAM	16.0 GB	9.6 GB (−40%)
memory-order warning	—	fires (below)

So -M costs ~44% more rounds and ~40% more compile RAM. At the largest sizes
it becomes decisive: with -M the compile OOMs (peak ~392 GB on a 376 GB host,
~34M instructions); without -M it looks like it would fit (~235 GB,
extrapolated from the 0.6× ratio). But the number is only useful if correct.
Without -M, on the wide entries:

WARNING: Order of memory instructions not preserved due to long vector, errors possible

i.e. the allocator.py path where dependency tracking is capped at budget, so
some dependencies on the large vectors aren't added.

What I've checked

A small OptimalPackedORAM — 8 items × 3 cells: populate with known values, read
at secret indices (including a read-after-write at a secret index), reveal the
total squared error — gives 0 error with both -M and no -M. But 3-cell
entries stay under budget, so they never take the "long vector" branch —
exactly the case the warning is about.

Scaling this check up to the sizes that matter is awkward on two fronts: a
thorough check means many more reveals, and even then it's hard to know how
many reveals are enough to catch a bug; if the reordering does bite it may be
sparse and data-dependent, so a passing spot-check doesn't rule one out. That's
really why I'm asking rather than just brute-forcing it.

Questions

1. For an ORAM up to ~1M items, would you compile with -M, or not? How do
   you usually handle this for ORAM in your own benchmarks?
2. When the "long vector, order not preserved" warning fires on secret-indexed
   ORAM access, how real is the correctness risk — a genuine hazard, or usually
   benign because the ORAM's data dependencies end up captured anyway?
3. Is the correctness risk driven by the number of items, or by the entry width
   (cells / bytes per item)? i.e. which regime is riskier — many small items,
   or few wide items?
4. -M has a real efficiency cost; for research numbers, is dropping it safe for
   ORAM in practice, or is protect_memory(...) around the accesses the intended
   middle ground (strict order only there, default optimization elsewhere)?
5. If dropping -M were the only way to fit the largest size, would a passing
   reveal-based correctness check at a smaller-but-still-long-vector size be
   sufficient evidence, or is the reordering too data-dependent to extrapolate?

Thanks a lot — and thanks for MP-SPDZ!

[mkskeller]

I never use -M because there are other ways to fix the issue should it arise, like protect_memory. For integrated functionality, it should not be necessary to use either because the functionality has been tested for correctness. The reason for the warning is that it would be expensive for the compiler to keep track of memory accesses, so the warning serves as a reminder. Deciding when to warn would be just as expensive, so the only other option here would be keeping quiet and hoping for the best. A minimal example of how the error appears is the following:

n = 100000
a = sint.Array(n)
a[:] = regint.inc(n) * sint(1) * sint(1)
x = a[n - 1]
x * sint(1)
print_ln('%s', x.reveal())

The second multiplication should clearly happen after the first, but that requires keeping track of all memory cells being accessed, which becomes very expensive as n grows.