Ashlar: an AO hash from a squaring degree engine, and a request for cryptanalysis

Cryptography
1

TL;DR. I have a new arithmetization-oriented hash, Ashlar, built around a different degree engine: a Feistel chain of field squarings instead of a power map. Under the accounting metric that the FreeLunch-era attacks make natural — bits of CICO ideal degree per R1CS constraint — squaring buys 1.0 and I prove 1.0 is a ceiling. The width-3 BN254 hash costs 191 measured R1CS constraints against derived counts of 243 for Poseidon and 240 for Poseidon2, and 14,232 EVM gas against Poseidon’s measured 18,229. It also loses in places, and I say where below.

I am posting this to get it attacked. It is new, it has had no external analysis, and there is a specific list of things I could not settle at the end of this post. Please do not use it for anything.

Artifact and Paper: GitHub - aryaethn/ashlar: Ashlar: an arithmetization-oriented hash from an R1CS-optimal squaring degree engine — paper, artifact manifest, and validation campaign · GitHub (tag v1.0-eprint), archived at Zenodo
Ashlar.pdf (779.2 KB)

The question

FreeLunch, the improved resultant attacks, and the follow-up multi-output work showed that for those algebraic pipelines, estimated S-box degree can exceed the degree that actually governs the change of monomial order — and several designs fell at or near full rounds in CICO-1. That does not give a general lower bound on solving cost, but it does suggest a conservative accounting

question:

How many bits of CICO ideal degree does a design buy per R1CS constraint?

An S-box of degree d costing C rank-1 constraints gives at most log2(d)/C bits per constraint in the coarse model. So:

S-box constraints bits/constraint
x^5 3 0.774
x^7 4 0.702
x^2 1 1.000

Squaring is the extreme point, and it is the extreme point for a structural reason rather than a numerical accident: a rank-1 constraint has total degree at most 2, so a zero-dimensional CICO ideal presented by C of them has quotient dimension at most 2^C by the affine Bézout bound. One bit per constraint is a ceiling no design can beat.
Attaining it is not automatic. The surviving presentation has to be square, genuinely quadratic, and have no solutions at infinity — so I measure attainment rather than infer it. The engine attains 1.0000 at six reduced points (S = 8, 12, 14, 16, 18, 20, all the way to D = 1,048,576 at S=20). Poseidon’s partial section also attains its own coarse S-box product at 0.7740, which is a different and weaker notion of attainment; Rescue-Prime and a mixed Poseidon configuration measurably fail their own Bézout products (625→125, 390625→15625). Those negative rows are in the paper because they are the evidence that the check is not vacuous.

The design

Squaring is not a permutation over an odd prime field and gives no backward degree, so it can only appear in Feistel position, and it needs surrounding. Ashlar is a HADES-style frame:

  • Engine: S squarings in Feistel position, chunked — the internal matrix is applied once per k squarings rather than every squaring. Chunking leaves R1CS cost and structural degree unchanged while cutting native matrix applications from S to S/k (147 → 21 at width 3).
  • Bracket: 4 BricksF rounds + 4 full x^α rounds + 2·n_pp partial-power rounds, wrapped around the engine. The x^α blocks are what carry the active-S-box bounds; BricksF is cheaper and adds nonlinearity I do not count. The bracket is not free and I want to be blunt about it: it is 44 of Ashlar-3-P’s 191 constraints and 244 of Ashlar-12-P’s 412. The engine is R1CS-optimal; the complete hash is not, and I claim no global optimality.

Normative instances (S = structural degree exponent, R1CS = constraints per call):

instance field t α S R1CS
Ashlar-3-P BN254 / BLS12-381 3 5 147 191
Ashlar-8-P Goldilocks 8 7 159 323
Ashlar-12-P Goldilocks 12 7 168 412

Numbers, with provenance

Everything below is same-machine, same-session (Apple M2, pinned toolchain). Every row maps to a driver command and a hash-pinned raw output in the artifact’s MANIFEST.csv; check_manifest.py re-verifies the whole table.

R1CS — Ashlar rows are measured in ark-relations; Poseidon rows are derived from published schedules using the same per-operation costs. The headline ratio therefore compares a measured numerator with a derived denominator, which I flag rather than hide.

design t constraints vs Ashlar
Ashlar-3-P (BN254) 3 191 —
Poseidon 3 243 1.272×
Poseidon2 3 240 1.257×

Poseidon2 is listed separately because its published schedule has 56 rather than 57 partial rounds. Its linear-layer rewrite is genuinely free in R1CS, so it cannot follow here — the gain comes from the degree engine, not the linear layer.

EVM gas, 2-to-1, all contracts gated on-chain against frozen vectors first:

optimizer_runs Ashlar Poseidon t=3 Poseidon2 t=4
200 18,552 30,485 26,813
5,000 14,232 30,485 26,807
≥10,000 14,232 18,229 19,639

I report the sweep because optimizer saturation changes the ranking — at 200 runs the gap looks like 1.64×, at saturation it is 1.28×. Quoting only the first would be dishonest. The arithmetic floor is 326 mulmod + 395 addmod + 2 mod = 5,778 gas, so 14,232 is a 2.46× overhead.

Where it loses:

  • Goldilocks native: Ashlar-12-P is 3.956 µs against Poseidon2’s 0.968 µs — 4.09× slower. Many cheap rounds are expensive when you price linear layers rather than multiplications. It is ahead of RPO (4.789 µs) with non-overlapping intervals, which is a much weaker consolation.
  • BN254 native: 6.488 µs vs Poseidon2’s 5.855 µs — within 11%, so a loss.
  • Plonkish: with a fold-2 chunk gate, 83 rows against Poseidon’s 66 — a 1.26× loss. A fold-3 gate reaches 58 rows without enlarging the coset domain (degree 9 → quotient degree 8 → 8×, same as degree 6), but it consumes the entire degree-9 headroom, so any other gate in the ambient circuit that would push past 9 doubles the blowup for everything. That is a trade, not a win.
  • AIR: not measured, not ranked, claims nothing.
  • Coverage: R1CS coverage is Poseidon and Poseidon2 only. Rescue, Griffin, Reinforced Concrete and Monolith ship in the same zkhash harness I used and were not measured — I did not record a reason at the time and I am not inventing one now. They are untested, not unavailable.

What is proven, what is assumed, what is open

This is the part I most want read carefully.

Proven:

  • The 2^C ceiling (affine Bézout).
  • Any nonzero differential trail, and any nontrivial linear trail with nonzero correlation, activates at least 2(t+1) x^α S-boxes.
  • The bare engine’s CICO-(1,1) ideal is zero-dimensional, in shape position, with quotient dimension exactly 2^S — under an explicit nonvanishing condition on the transition and output coefficients.

Assumed, and flagged as such:

  • Round independence (average-key / Markov-cipher) to multiply single-S-box bounds across rounds. Not implied by the active-S-box count for a fixed unkeyed permutation with public constants.
  • The trail bounds are single-trail, not hull bounds.
  • Square-freeness of the eliminant at normative S. It holds in exact experiments through S=27; it is neither proved nor measured at S=147/168.
  • A generic-search heuristic behind the side condition n_O·log2(p) ≥ S.

Explicitly not claimed:

  • No lower bound on the cost of solving CICO. A quotient dimension is not a solving-cost bound. The Ω(2^S) figure holds only in a stated dense-representation model. Over Goldilocks, straight-line evaluation over the whole base field already defeats the one-output engine problem at ~2^71.4 operations, far below the formal degree 2^168.
  • Algebraic security of the deployed mode is an assumption, not a theorem. A negative result against my own design: on the bare engine, each additional output constraint removes roughly one whole chunk from the ideal degree. In 42 structural probes at normative parameters the tested linear cancellation is

absent — minimum surviving degree 99 over BN254 and 1353 over Goldilocks width 12, rather than 0 — so the bracket appears to block it. But that is one mechanism excluded, not the problem solved.

What I would like attacked

Concretely, in rough order of how much it would change the paper:

  1. The multi-output CICO ideal degree of the normative permutation. Open. I have no full both-sides ideal-degree measurement, no Gröbner results beyond two outputs, and no exclusion of nonlinear or resultant reductions.

  2. The 0 ∈ I branch of the degree formula. Never run — it needs projective degree computations for I = {0,1}, not a flag on the existing affine driver. The normative width-3 rate set uses exactly that branch, so I quote no margin from it.

  3. Compact eliminant representations. My Ω(2^S) assumes dense materialisation. If the eliminant admits a compact straight-line representation that can be evaluated or factored without materialising it, the argument weakens considerably. I think this is the most likely place a real attack comes from.

  4. The Goldilocks circulant external matrix. It is more structured than a Cauchy matrix: it preserves the all-ones line and has many invariant subspaces. My acceptance and subspace gates exclude the inactive trails my own arguments use, but that is not a general invariant- or affine-subspace analysis, and I say so in the paper rather than hiding behind the speed measurement it bought.

  5. Square-freeness at normative S, per above.

  6. Whether the 2(t+1) count is tight, and whether a hull argument changes the
    picture.

If it would help, I am happy to publish reduced-round CICO challenge instances at a range of S so people can calibrate solvers against something concrete rather than reimplementing from the appendix.

Reproducing

The artifact carries the reference implementation, the Rust crates and Solidity contracts the numbers were measured from, the conformance vectors, all raw outputs including the runs I abandoned at a budget (9 of 110 Gröbner runs, and a bracket measurement that exhausted every budget I tried), and the negative results that refuted my own earlier claims.

git clone https://github.com/aryaethn/ashlar && cd ashlar
python3 artifact/check_manifest.py # audits every claim's provenance; exits 0
validation/ashlar-final/run_all.sh # gates, R1CS, native, EVM, Plonkish
validation/ashlar-gb/run_all.sh # Gröbner campaign, calibration gate first

The Gröbner harness reproduces a published Anemoi result as a calibration gate before it computes any Ashlar number, because I had a substitute solver silently take leading monomials in the wrong order once and return plausible values everywhere else.

Happy to answer anything, and more than happy to be shown wrong.