STARK 검사 200회→148회 가능성…수학 과제 3개 공개
제목 연관성·주요 수치·시장 영향·향후 전망을 기준으로 핵심 문장을 선별한 요약 브리핑입니다.
핵심 포인트
- 공개 과제는 리드·솔로몬 근접성 검사의 예외값 상한을 다루는 세 목표로 구성됐다.
- 특정 조건에서 검사 횟수가 200회에서 148회로 줄 수 있다는 계산 예가 제시됐지만, 세 목표는 모두 미해결 상태다.
- STARK 증명의 검사 횟수를 줄이기 위한 수학 과제 세 개가 공개됐다.
본문
공개 과제는 리드·솔로몬 근접성 검사의 예외값 상한을 다루는 세 목표로 구성됐다. 특정 조건에서 검사 횟수가 200회에서 148회로 줄 수 있다는 계산 예가 제시됐지만, 세 목표는 모두 미해결 상태다. STARK 증명의 검사 횟수를 줄이기 위한 수학 과제 세 개가 공개됐다. 과제 페이지는 특정 조건에서 100비트 보안에 필요한 검사 횟수가 200회에서 148회로 줄 수 있다는 계산 예도 제시했지만, 이는 목표 증명과 전체 보안성 분석을 전제로 한 수치다. provably.fast의 공식 과제 페이지에는 세 목표가 제시돼 있다. 각 명제는 수학 정리 증명 도구인 Lean에 고정돼 있으며, 독립적인 검토를 거친 증명만 해결로 인정된다. 과제는 이 검사 과정에서 잘못된 데이터가 정상적인 코드처럼 보이게 할 수 있는 ‘나쁜 도전값’의 수를 제한하는 데 초점을 맞췄다.
과제 페이지는 동의율 5/8, 비율 1/2인 첫 사례에서 기존 구성의 나쁜 도전값 수가 114n/16까지 이르는 조건에 대해 16n 상한을 증명하도록 제시했다.
페이지가 든 검사 횟수 예시는 FRI 방식, 비율 1/2, n=2²⁰, 124비트 필드 등 특정 조건을 전제로 한다. 페이지는 이 수치가 검사 횟수 계산에 한정되며, 실제 적용에는 전체 보안성 분석이 필요하다고 설명했다. 꽝 다오(Quang Dao), 스콧 듀크 코미너스(Scott Duke Kominers), 저스틴 탈러(Justin Thaler)가 9월 17일 등록한 프리프린트는 같은 보안 목표에서 ProveKit 여권 증명을 79.4KB(11.1%), ZisK 압축 최종 증명을 13.2KB(4.63%), LambdaVM CPU 하위 증명을 59.8KB(4.85%) 줄였다고 보고했다. 세 공개 과제가 해결됐거나 실제 STARK 구현의 증명 크기가 추가로 줄었다는 결과는 아직 나오지 않았다.