CIRCOMLIB / OPTIMIZED-CIRCOM BASELINE ROW COUNTS -- FETCHED FROM SOURCE
Fetched 2026-09-01 from raw.githubusercontent.com (branch master).

--- iden3/circomlib circuits/sha256/xor3.circom (template Xor3(n)) ---
  signal mid[n];
  for (var k=0; k<n; k++) {
    mid[k] <== b[k]*c[k];
    out[k] <== a[k] * (1 -2*b[k] -2*c[k] +4*mid[k]) + b[k] + c[k] -2*mid[k];
  }
  => PER BIT: 2 R1CS constraints (both assignments are genuinely quadratic:
     mid = b*c, and out = a*(linear in b,c,mid) + linear) and
     1 auxiliary signal allocation (mid).
  CORRIDOR'S QUOTED BASELINE (from memory): "2 rows + 1 allocation". CORRECT.

--- iden3/circomlib circuits/sha256/maj.circom (template Maj_t(n)) ---
  signal mid[n];
  for (var k=0; k<n; k++) {
    mid[k] <== b[k]*c[k];
    out[k] <== a[k] * (b[k]+c[k]-2*mid[k]) + mid[k];
  }
  => PER BIT: 2 R1CS constraints + 1 auxiliary signal (mid).
  CORRIDOR'S QUOTED BASELINE: "2 rows + 1 allocation". CORRECT.

Caveat: these are the constraint counts AS WRITTEN. circom's --O1/--O2 passes
do linear substitution/simplification; a compiled .r1cs count for a whole
SHA-256 may differ. No compile receipt was produced. But neither assignment is
linear, so neither can be removed by linear substitution. Confidence high.

--- bkomuves/hash-circuits circuits/sha2/sha2_common.circom
    (a leading hand-optimized circom SHA-2 library) ---
  template Bits2()   : lo,hi booleanity (2 constraints) + xy === 2*hi+lo
                       (linear, free) => 2 constraints, 2 allocations.
  template XOR3_v1() : out <- Bits2(x+y+z).lo   => 2 constraints.
  template XOR3_v2() : the circomlib form       => 2 constraints.

  VERBATIM COMMENT between the two templates:
    "// same number of constraints (that is, 2), in the general case
     // however circom can optimize y=0 or z=0, unlike with the above
     // and hopefully also x=0."

  SIGNIFICANCE FOR ZK-C-03: an author who deliberately implemented and
  compared TWO independent XOR3 constructions, in a library whose entire
  purpose is minimizing SHA-2 constraint count, concluded that 2 is the
  general-case cost. Strong (not conclusive) negative evidence that the
  1-row form (2s - t)*t = 3s - 2t is not circulating circom folklore.

--- INDEPENDENT RE-CHECK OF THE CORRIDOR'S 1-ROW GADGETS (done by hand here,
    not taken on trust) ---
  XOR3: t = a+b+c, claim (2s - t)*t = 3s - 2t.
    t=0,s=0: 0 = 0. t=1,s=1: (2-1)*1 = 1 ; 3-2 = 1. t=2,s=0: (0-2)*2 = -4 ;
    0-4 = -4. t=3,s=1: (2-3)*3 = -3 ; 3-6 = -3. All hold.
    Rearranged: s*(2t-3) = t^2 - 2t. Coefficient 2t-3 in {-3,-1,1,3} for
    t in {0,1,2,3}, nonzero in any field of char != 2,3 => s is uniquely
    determined. Sound and complete, 1 row, 0 allocations. CONFIRMED.
  MAJ3: claim (4y - t)*t = 6y - t.
    t=0,y=0: 0 = 0. t=1,y=0: (0-1)*1 = -1 ; 0-1 = -1. t=2,y=1: (4-2)*2 = 4 ;
    6-2 = 4. t=3,y=1: (4-3)*3 = 3 ; 6-3 = 3. All hold.
    Rearranged: y*(4t-6) = t^2 - t. Coefficient 4t-6 in {-6,-2,2,6}, nonzero
    for char != 2,3 => y unique. CONFIRMED.
  So the claimed 2x reduction against the deployed circomlib baseline is real
  arithmetic, verified independently of the corridor's own receipts.
