Phase C: Spot-check hash oracle for MPT membership

[hoddukzoa12]

목표

Full keccak AIR 없이도 MPT membership (receiptHash ∈ receiptsRoot)의 신뢰도를 올리는 방향. 해커톤에서는 로드맵으로 제시.

현재 갭

Phase A+B 이후에도 공격자가 가짜 receiptHash를 제출할 수 있음. 실제로 해당 receipt이 블록의 receiptsRoot에 포함되는지는 미검증.

해결 방향: Hash Oracle

Full keccak-f[1600] AIR를 구현하지 않고, hash oracle + probabilistic spot-check 방식으로 MPT membership을 검증.

아키텍처

Prover (off-chain):
  1. MPT walk 실행, 모든 keccak(input, output) pair 기록
  2. Hash table을 Merkle commit → hash_table_root
  3. STARK trace에서 hash output을 참조하여 MPT walk 수행
  4. hash_table_root를 public input에 포함

Verifier (on-chain):
  1. STARK proof 검증 (Sharpe + event decode + MPT walk logic)
  2. hash_table에서 K개 랜덤 항목 추출 (Fiat-Shamir)
  3. 각 항목에 대해 keccak precompile로 hash(input) == output 검증
  4. K=20이면 ~80-bit security

Calldata 비교

방식	Calldata
현재 (full MPT on-chain)	~97KB
Phase A (commitment only)	~3KB
Phase C (hash oracle, K=20)	~3KB + ~2KB (spot-check data) = ~5KB
Full keccak AIR (이론적)	~3KB (proof만)

대안: Limited Membership

Hash oracle 대신, MPT proof의 마지막 몇 단계만 on-chain으로 검증하는 방식:

1. receiptHash가 leaf에 있다는 것은 client가 검증
2. leaf → parent branch의 keccak hash만 on-chain 검증 (1개 hash)
3. 나머지 경로는 STARK witness

이 방식은 구현이 더 간단하지만 보안 수준이 낮음.

변경 파일 (Hash Oracle 방식)

파일	변경
prover/src/hash_oracle.rs	신규: keccak hash table builder + Merkle commit
prover/src/mpt_trace.rs	신규: MPT walk trace generator (hash oracle 참조)
prover/src/lib.rs	hash oracle + MPT trace 통합
prover/src/sharpe_trace.rs	MPT columns 추가
contracts/stylus/src/lib.rs	spot-check 로직 (Fiat-Shamir로 인덱스 선택)
contracts/stylus/src/mpt.rs	hash table 디코딩 + spot-check 검증

장기 로드맵: Full Keccak AIR

Hash oracle의 확률적 보안을 완전한 soundness로 올리려면:

• Keccak-f[1600] AIR: 1600 binary columns × ~120 rows per hash
• 구현 복잡도: Polygon Miden / StarkWare 급 팀이 수개월 투자
• Trace 크기: 현재 6 cols × 16 rows → 1600+ cols × 수만 rows
• 실용성: 해커톤 범위 밖, 프로덕션 단계에서 고려

보안 모델

항목	Phase A	Phase B	Phase C (Oracle)	Full Keccak
Sharpe 산술	✓	✓	✓	✓
Commitment 바인딩	✓	✓	✓	✓
return_bps 출처	✗	✓	✓	✓
MPT membership	✗	✗	~80-bit	Full soundness

예상 소요: 34주 (Hash Oracle), 812주 (Full Keccak)

선행 작업: Phase A (#68), Phase B (#69)