-
Minimizing Foreign Arithmetic in ZKP Circuits
https://eprint.iacr.org/2024/265.pdf 논문에 대해 다룹니다. 소개 ZKP를 사용하는 과정에서 가장 핵심적인 부분은 결국 $\mathbb{F}_p$ 위의 기본적인 연산들을 통해서 프로젝트 스펙에서 필요로 하는 constraint들을 표현하는 것에 있습니다. 하지만 $\mathbb{F}_p$ 위에서 모든 것을 표현하는 것이 쉽지만은 않습니다. 대표적인 사례는 바로 foreign field arithmetic인데, 이는 $\mathbb{F}_p$를 표현할 수 있는 ZKP system 위에서 $\mathbb{F}_q$의 연산을 증명하는 것을 의미합니다. 예를 들어, BN254 위의 PLONK를 하고 있다고 치면 BN254의 scalar field가 ZKP 상으로 native 하게 지원되지만, 여기서 SECP256K1 ECDSA verification을 하고 싶다면...
-
Suffix Automaton으로 Suffix Array 문제들을 풀어보자 1
최근 공부 중에 Suffix Automaton이라는 자료 구조를 새로 알게 되어, Suffix Array 태그가 붙은 문제들을 전부 Suffix Automaton으로 풀어보려 시도했습니다. 그리고 꽤 많은 문제들이 Suffix Automaton을 사용할 때 훨씬 편리하게 풀린다는 것을 발견했습니다. 그 과정에서 알게 된 여러 테크닉들을 정리하고자 합니다. 이 글에서는 Suffix Automaton 자체에 대한 상세한 설명보다는 문제 풀이에 필요한 개념 위주로 간략하게 설명합니다. 아래에 Suffix Automaton에 대해 자세히 설명된 글이 있으니, 참고하시면 좋을 것 같습니다. https://koosaga.com/314 https://cp-algorithms.com/string/suffix-automaton.html Suffix Automaton이란? Suffix Automaton을 간단히...
-
Insights from and on Taxonomy of ZKP Vulnerabilities
올해 4월 초, ZKP 관련 최대 컨퍼런스 중 하나인 zkSummit11에서 ZKP 보안과 관련된 발표를 진행할 수 있었습니다. 이번 글에서는 발표 내용에 대한 간략한 설명을 합니다. ZKP 보안에 대한 업계의 이해도는 2022년부터 꾸준히 증가해왔지만, 아직도 ZKP 보안 판에는 여러 문제가 있습니다. 가장 큰 문제 중 하나는 사람이 부족하다는 것인데, 이에 대한 해답으로는 크게 두 가지를 생각할 수 있습니다. 암호를 잘 하는 사람에게 보안의 컨텍스트를 가르쳐 ZKP 보안을 소개하는 것 블록체인 보안을 하는 사람에게 암호의 컨텍스트를 가르쳐...
-
IMO 조합 문제를 DP로 풀어보자
저번 글에 이어 이번에도 IMO(국제 수학 올림피아드)와 관련된 주제를 가져왔습니다. 오늘은 아마도 이 글을 읽는 분들이 가장 익숙하실 조합 문제들을 다뤄보려고 합니다. 최근 들어 PS에서 다루는 다양한 알고리즘적 사고를 요구하는 문제들이 수학 올림피아드에도 출제되고 있습니다. 특히 DP(점화식)를 이용하는 문제가 최근 2년 연속 IMO에 출제되며 큰 관심을 끌었습니다. 이번 글에서는 이 두 문제의 풀이를 간단히 소개해보려 합니다. IMO 2022 P6 양의 정수 $n$이 있다. 노르딕 사각형이란 $n\times n$ 모양의 판으로 각 칸에 $1$부터 $n^2$까지의 수가 하나씩...
-
Polya's Enumeration Theorem을 이용한 카운팅 문제 해결
개요 Polya’s Enumeration Theorem(포여 열거 정리)는 어떤 작용에 대한 equivalence class의 개수를 구할 때 사용됩니다. 대표적인 예시로 돌리거나 뒤집어서 같은 것을 하나로 볼 때, 서로 다른 목걸이의 개수를 구하는 문제가 있습니다. 이 글에서는 Burnside Lemma와 그것의 일반화인 Polya’s Enumeration Theorem을 소개한 후 이를 적용하여 문제를 해결하는 과정을 서술하겠습니다. 관련 문제는 백준 문제집 또는 알고리즘 분류에서 찾아볼 수 있습니다. 해당 태그를 가진 문제가 9문제에 불과한 만큼 CP에서 자주 등장하는 주제는 아닙니다. 그렇지만 특정 형태의 카운팅 문제를...