4a0b48588c
Aere Network public source. Everything here can be checked against the live chain (chain id 2800, https://rpc.aere.network). Scope note, stated up front rather than buried: consensus on chain 2800 is classical secp256k1 ECDSA QBFT. The post-quantum work in this repository is at the signature, precompile, account and transport layers. Nothing here makes the consensus post-quantum, and no document in it should be read as claiming so.
207 lines
8.5 KiB
Java
207 lines
8.5 KiB
Java
/*
|
|
* Copyright contributors to the AERE Network.
|
|
* SPDX-License-Identifier: Apache-2.0
|
|
*
|
|
* Standalone self-test for the FriQueryIndex helper that is embedded in
|
|
* pqc-fork/precompiles/Sp1StarkVerifierPrecompiledContract.java (the PQ STARK-verify precompile
|
|
* 0x0AE8). The logic below is a VERBATIM copy of that helper's arithmetic, extracted so it can be
|
|
* compiled and run WITHOUT the Besu classpath (plain `javac` + `java`), giving a genuinely-running
|
|
* Java validation of the exact code that ships in the precompile.
|
|
*
|
|
* HONEST SCOPE. This tests ONE constant-free slice of FRI component (d): the query-index derivation
|
|
* (sample_bits) and the per-layer folding-index walk. It verifies NOTHING about a real STARK proof,
|
|
* and the top-level 0x0AE8 verifier stays fail-closed. It asserts hand-computed golden vectors and
|
|
* structural invariants; cross-language agreement with the Python and Node references is checked by
|
|
* test_fri_query_index.py. Conformance to a real SP1 v6.1.0 trace is [MEASURE] (port spec 8).
|
|
*
|
|
* Run: javac FriQueryIndexSelfTest.java && java FriQueryIndexSelfTest
|
|
* Emits JSON on stdout (the shared vector set) when invoked as: java FriQueryIndexSelfTest --emit
|
|
*/
|
|
public final class FriQueryIndexSelfTest {
|
|
|
|
static final long BABYBEAR_P = 2013265921L; // 2^31 - 2^27 + 1
|
|
|
|
// ==== helper logic (identical to Sp1StarkVerifierPrecompiledContract.FriQueryIndex) ============
|
|
|
|
/** Low `bits` bits of a canonical BabyBear representative. [VERIFY] LSB vs MSB vs p3-challenger. */
|
|
static int sampleBits(final long canonicalU32, final int bits) {
|
|
if (bits < 0 || bits >= 31) {
|
|
throw new IllegalArgumentException("bits must be in [0,31): one BabyBear sample carries ~31 bits");
|
|
}
|
|
if (canonicalU32 < 0 || canonicalU32 >= BABYBEAR_P) {
|
|
throw new IllegalArgumentException("canonicalU32 must be canonical in [0, p)");
|
|
}
|
|
return (int) (canonicalU32 & ((1L << bits) - 1L));
|
|
}
|
|
|
|
/** One FRI folding-index step: [index, sibling, index_pair, parity]. */
|
|
static int[] foldStep(final int index) {
|
|
return new int[] {index, index ^ 1, index >> 1, index & 1};
|
|
}
|
|
|
|
/** Full per-query folding-index walk; row r = {layer, index, sibling, index_pair, parity}. */
|
|
static int[][] walk(final int index, final int logMaxHeight, final int logFinalPolyLen) {
|
|
if (logMaxHeight < 0 || logFinalPolyLen < 0 || logFinalPolyLen > logMaxHeight) {
|
|
throw new IllegalArgumentException("bad log heights");
|
|
}
|
|
if (index < 0 || index >= (1 << logMaxHeight)) {
|
|
throw new IllegalArgumentException("index out of range for log_max_height");
|
|
}
|
|
final int rounds = logMaxHeight - logFinalPolyLen;
|
|
final int[][] out = new int[rounds][5];
|
|
int cur = index;
|
|
for (int layer = 0; layer < rounds; layer++) {
|
|
final int[] s = foldStep(cur);
|
|
out[layer][0] = layer;
|
|
out[layer][1] = s[0];
|
|
out[layer][2] = s[1];
|
|
out[layer][3] = s[2];
|
|
out[layer][4] = s[3];
|
|
cur = cur >> 1;
|
|
}
|
|
return out;
|
|
}
|
|
|
|
static int finalIndex(final int index, final int logMaxHeight, final int logFinalPolyLen) {
|
|
return index >> (logMaxHeight - logFinalPolyLen);
|
|
}
|
|
|
|
// ==== tests ====================================================================================
|
|
|
|
static int pass = 0, fail = 0;
|
|
|
|
static void check(final String name, final boolean cond) {
|
|
if (cond) {
|
|
pass++;
|
|
} else {
|
|
fail++;
|
|
System.out.println("FAIL " + name);
|
|
}
|
|
}
|
|
|
|
public static void main(final String[] args) {
|
|
if (args.length > 0 && args[0].equals("--emit")) {
|
|
System.out.print(emitSharedVectorsJson());
|
|
return;
|
|
}
|
|
|
|
// 1. Hand-computed golden walk: index=11 (0b1011), log_max_height=4, final poly len 0.
|
|
// round0: 11 -> sib 10, pair 5, par 1
|
|
// round1: 5 -> sib 4, pair 2, par 1
|
|
// round2: 2 -> sib 3, pair 1, par 0
|
|
// round3: 1 -> sib 0, pair 0, par 1 ; final index 11>>4 = 0.
|
|
int[][] g = walk(11, 4, 0);
|
|
int[][] expect = {
|
|
{0, 11, 10, 5, 1},
|
|
{1, 5, 4, 2, 1},
|
|
{2, 2, 3, 1, 0},
|
|
{3, 1, 0, 0, 1},
|
|
};
|
|
check("golden.walk.len", g.length == 4);
|
|
for (int i = 0; i < expect.length; i++) {
|
|
check("golden.walk.row" + i, java.util.Arrays.equals(g[i], expect[i]));
|
|
}
|
|
check("golden.walk.final", finalIndex(11, 4, 0) == 0);
|
|
|
|
// 2. Hand-computed golden with a non-trivial final poly: index=22, lmh=5, lfp=1 -> 4 rounds,
|
|
// final index 22>>4 = 1 (in [0,2)).
|
|
int[][] g2 = walk(22, 5, 1);
|
|
int[][] expect2 = {
|
|
{0, 22, 23, 11, 0},
|
|
{1, 11, 10, 5, 1},
|
|
{2, 5, 4, 2, 1},
|
|
{3, 2, 3, 1, 0},
|
|
};
|
|
check("golden.walk2.len", g2.length == 4);
|
|
for (int i = 0; i < expect2.length; i++) {
|
|
check("golden.walk2.row" + i, java.util.Arrays.equals(g2[i], expect2[i]));
|
|
}
|
|
check("golden.walk2.final", finalIndex(22, 5, 1) == 1);
|
|
|
|
// 3. sample_bits hand goldens: 20 = 0b10100.
|
|
check("golden.samplebits.20_2", sampleBits(20, 2) == 0); // low 2 bits: 00
|
|
check("golden.samplebits.20_3", sampleBits(20, 3) == 4); // low 3 bits: 100
|
|
check("golden.samplebits.20_4", sampleBits(20, 4) == 4); // low 4 bits: 0100
|
|
check("golden.samplebits.20_5", sampleBits(20, 5) == 20); // low 5 bits: 10100
|
|
check("golden.samplebits.mixed", sampleBits(0x6ae81234L, 5) == 0x14);
|
|
|
|
// 4. Invariants over many random cases.
|
|
java.util.Random rnd = new java.util.Random(0xAE8);
|
|
for (int t = 0; t < 20000; t++) {
|
|
int lmh = 1 + rnd.nextInt(27); // 1..27, single-sample safe
|
|
int lfp = rnd.nextInt(lmh + 1); // 0..lmh
|
|
int idx = rnd.nextInt(1 << lmh);
|
|
int[][] w = walk(idx, lmh, lfp);
|
|
check("inv.rounds", w.length == lmh - lfp);
|
|
int cur = idx;
|
|
boolean ok = true;
|
|
for (int[] row : w) {
|
|
ok &= (row[1] == cur); // index tracks the running fold
|
|
ok &= (row[2] == (cur ^ 1)); // sibling differs in exactly bit 0
|
|
ok &= (Integer.bitCount(row[1] ^ row[2]) == 1);
|
|
ok &= (row[3] == (cur >> 1)); // index_pair halves
|
|
ok &= (row[4] == (cur & 1)); // parity
|
|
cur >>= 1;
|
|
}
|
|
ok &= (finalIndex(idx, lmh, lfp) == cur);
|
|
ok &= (cur < (1 << lfp)); // collapses into final-poly domain
|
|
check("inv.walk", ok);
|
|
|
|
int bits = rnd.nextInt(30);
|
|
long v = (long) (rnd.nextDouble() * BABYBEAR_P) % BABYBEAR_P;
|
|
int sb = sampleBits(v, bits);
|
|
check("inv.samplebits.range", sb >= 0 && sb < (1 << bits));
|
|
check("inv.samplebits.lowbits", sb == (int) (v & ((1L << bits) - 1L)));
|
|
}
|
|
// full-width sample_bits is identity for canonical reps that fit
|
|
check("inv.samplebits.identity", sampleBits(0x0abcdefL, 28) == 0x0abcdef);
|
|
|
|
System.out.printf("Java FriQueryIndexSelfTest: PASS=%d FAIL=%d%n", pass, fail);
|
|
if (fail != 0) {
|
|
System.exit(1);
|
|
}
|
|
}
|
|
|
|
// Emit the exact shared vector set (same cases as the Node/Python references) as JSON, so the
|
|
// harness can diff all three languages byte-for-byte.
|
|
static String emitSharedVectorsJson() {
|
|
int[][] walkCases = {
|
|
{11, 4, 0}, {22, 5, 1}, {0, 6, 0}, {63, 6, 0}, {12345, 20, 3}, {1, 1, 0},
|
|
};
|
|
long[][] sampleCases = {
|
|
{20, 2}, {20, 3}, {20, 5}, {0x6ae81234L, 5}, {0x6ae81234L, 20}, {BABYBEAR_P - 1, 10},
|
|
};
|
|
StringBuilder sb = new StringBuilder();
|
|
sb.append("{\"walks\":[");
|
|
for (int c = 0; c < walkCases.length; c++) {
|
|
int idx = walkCases[c][0], lmh = walkCases[c][1], lfp = walkCases[c][2];
|
|
int[][] w = walk(idx, lmh, lfp);
|
|
if (c > 0) sb.append(",");
|
|
sb.append("{\"index\":").append(idx)
|
|
.append(",\"logMaxHeight\":").append(lmh)
|
|
.append(",\"logFinalPolyLen\":").append(lfp)
|
|
.append(",\"final_index\":").append(finalIndex(idx, lmh, lfp))
|
|
.append(",\"steps\":[");
|
|
for (int i = 0; i < w.length; i++) {
|
|
if (i > 0) sb.append(",");
|
|
sb.append("{\"layer\":").append(w[i][0])
|
|
.append(",\"index\":").append(w[i][1])
|
|
.append(",\"sibling\":").append(w[i][2])
|
|
.append(",\"index_pair\":").append(w[i][3])
|
|
.append(",\"parity\":").append(w[i][4]).append("}");
|
|
}
|
|
sb.append("]}");
|
|
}
|
|
sb.append("],\"samples\":[");
|
|
for (int c = 0; c < sampleCases.length; c++) {
|
|
long v = sampleCases[c][0];
|
|
int bits = (int) sampleCases[c][1];
|
|
if (c > 0) sb.append(",");
|
|
sb.append("{\"v\":").append(v).append(",\"bits\":").append(bits)
|
|
.append(",\"out\":").append(sampleBits(v, bits)).append("}");
|
|
}
|
|
sb.append("]}");
|
|
return sb.toString();
|
|
}
|
|
}
|