# ZKP Fuzzing

**Fuzzing**이란, 시스템이 암묵적으로 가정한 의미적 불변식을 깨기 위해 입력·상태·연산을 의도적으로 변형하며 반례를 탐색하는 동적 분석 기법이다.

### 어떤 취약점에 활용할 수 있는가? 

ZKFUZZ는 TCCT(Trace-Constraint Consistency Test)라는 새로운 이론적 모델을 기반으로, 크게 두 가지 범주의 심각한 취약점을 탐지한다.

1.  Under-Constrained Circuits (Soundness 위반) 회로의 제약 조건이 너무 느슨하여, 악의적인 증명자(Prover)가 거짓된 증명을 생성할 수 있는 경우이다.

* 계산 중단(Computation Aborts) 버그: 입력값에 대해 증인 생성 프로그램은 충돌(crash)하거나 중단되지만, 회로 제약 조건은 이를 만족하는 경우이다. 이는 기존 도구들이 놓치는 주요 취약점으로, 전체 버그의 약 50%를 차지한다.
* 결과 불일치: 프로그램이 생성한 결과와 다른 결과를 회로가 수용하는 경우이다.

2. Over-Constrained Circuits (Completeness 위반) 회로의 제약 조건이 너무 엄격하여, 정직한 증명자가 올바른 증명을 생성했음에도 검증을 통과하지 못하는 경우이다.

* 유효한 실행 거부: 프로그램 로직상으로는 올바른 실행 경로(Execution Trace)이지만, 제약 조건이 이를 거부하여 서비스 거부(DoS) 상태를 유발한다.

3. 세부 패턴 버그

* Zero-Division (0으로 나누기): 분모가 0일 때 제약 조건이 무력화되는 패턴.
* Hash-Check 누락: 해시 검증이 제대로 이루어지지 않아 임의의 데이터를 유효한 것으로 속이는 패턴.
* 배열 인덱스 오류: 잘못된 배열 접근으로 인한 버그.

### ZK Fuzz 어떻게 하는가? 

1. ZK 프로그램(Circom 코드)을 입력받아 계산 로직(P)과 회로 제약 조건(C)으로 분리
2. 2가지 차원에서 변이를 일으킴 

   a. 입력 데이터 변이 (Input Fuzzing)

   * 큰 소수 필드(Large Prime Fields)에서 0, 1, 혹은 모듈러 연산의 경계값(q-1) 등 버그가 발생하기 쉬운 "Skewed Distribution(편향된 분포)"을 사용하여 입력을 생성한다.
   * 정적 분석을 통해 '0으로 나누기' 등 취약한 지점을 미리 파악하여 입력을 유도한다.

   b. 프로그램 로직 변경(Program Mutation)

   * 증인 생성 프로그램(P)의 연산자나 상수를 임의로 변경하여 변이된 프로그램(P')을 만든다.
   * 예를 들어, 덧셈을 뺄셈으로 바꾸거나 할당 값을 변경한다.
3. 실행 및 추적 (Execution & Tracing)
   * 원본 프로그램(P)과 변이된 프로그램(P')을 생성된 입력값으로 실행하여 실행 추적(Trace)을 얻는다.
   * 실행 추적에는 입력, 출력뿐만 아니라 중간 계산값(Intermediate values)도 포함된다.
4. TCCT 기반 결함 탐지 (Detection via TCCT)
   * Over-Constrained 탐지:원본 프로그램(P)이 정상적으로 실행되어 결과(Trace)를 내놓았는데, 이 Trace가 제약 조건(C)을 만족하지 못하면(False) Over-constrained이다.
   * Under-Constrained 탐지:변이된 프로그램(P')이 원본과 다른 출력값을 생성했는데, 이 잘못된 Trace가 여전히 제약 조건(C)을 만족한다면(True) Under-constrained이다. 즉, 로직이 바뀌어 엉뚱한 값이 나왔는데도 회로가 이를 "맞다"고 통과시켜버리는 것이다.
5. 진화 알고리즘 (Evolutionary Fuzzing)
   * 제약 조건 위반 정도를 점수화(Error-based Fitness Score)하여, 버그를 찾을 확률이 높은 변이(Mutant)를 선택하고 다음 세대에 유전시킨다.

### Reference

* H. Takahashi, J. Kim, S. Jana, and J. Yang, "[zkFuzz: Foundation and Framework for Effective Fuzzing of Zero-Knowledge Circuits](https://arxiv.org/abs/2504.11961)," in Proceedings of the 2024 ACM SIGSAC Conference on Computer and Communications Security (CCS '24), 2024.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://upsidezkp.gitbook.io/upside-zkp-docs/step-5/zkp/zkp-fuzzing.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.