-
Run Enumerate로 문제를 풀어보자
이 포스트는 Run Enumerate의 구현 및 활용에 대해 다루며, koosaga님의 포스트를 기반으로 쓰여졌습니다. 이 글에서는 Run Enumerate를 문제 풀이에 활용하는 방법을 위주로 다루며, 증명이나 기타 자세한 내용에 대해서는 다루지 않으므로 다른 글을 참고하시길 부탁드립니다. Run Enumerate란? Run Enumerate는 문자열 내부에 연속하여 존재하는 모든 반복 또는 반복의 일부를 찾고 싶을 때 쓰는 알고리즘입니다. 예를 들어, $\rm{mississippi}$라는 문자열을 생각해봅시다. 이 문자열에는 어떤 반복이 존재할까요? 한번 나열해 봅시다. $[2, 4)$ 구간과 $[5,7)$ 구간에 해당하는 부분 문자열은 $\rm{ss}$로, 길이...
-
Kotlin 변성
이 포스트에서는 코틀린 제네릭의 주요 개념 중 하나인 변성에 대해 알아보겠습니다. 변성이란 List<String>와 List<Any>와 같이 기저 타입이 같고 타입 인자가 다른 여러 타입이 서로 어떤 관계가 있는지 설명하는 개념입니다. List<Any> 타입의 파라미터를 받는 함수에 List<String>을 넘기면 안전한지에 대한 질문을 생각해봅시다. 결론부터 말하면 안전합니다. 예를 들어 다음과 같은 코드는 정상적으로 컴파일됩니다, fun print(list: List<Any>){ println(list.joinToString()) } print(listOf("a","b","c")) 그러나 MutbleList의 경우는 그렇지 않습니다. fun add(list: MutableList<Any>) { list.add(42) } val strings = mutableListOf("a","b","c") add(strings) println(strings.maxBy{it.length}) 만약 이...
-
Anatomy of a zkVM: Looking at SP1
소개 최근 Succinct Labs의 zkVM인 SP1을 자세히 볼 기회가 생겼습니다. zkVM은 ZKP를 통해서 하나의 프로그램 자체의 execution을 통째로 증명하는 것을 목표로 하고 있습니다. SP1의 경우에서는 RISC-V 프로그램을 대상으로 하고 있어, Rust을 구현한 후 컴파일하면 SP1이 바로 증명을 할 수 있게 됩니다. 이를 통해서, 복잡한 ZKP 서킷을 직접 작성하는 대신 Rust로 코드를 짜고, 이를 SP1으로 덮어서 ZKP를 사용할 수 있게 됩니다. 즉, zkEVM을 구현하기 위해서 EVM의 Rust 구현체를 가져다 쓰기만 하면 됩니다. 이 글에서는 SP1의 구조에...
-
Suffix Automaton으로 Suffix Array 문제들을 풀어보자 2
이 포스트에서는 이전 글인 Suffix Automaton으로 Suffix Array 문제들을 풀어보자 1에 이어서, Suffix Automaton과 함께 사용할 수 있는 여러 테크닉들에 대해 설명합니다. Suffix Automaton이 무엇인지에 대해서는 제 이전 글을 참고하셔도 좋고, 아래 글을 읽어보셔도 좋습니다. https://koosaga.com/314 https://cp-algorithms.com/string/suffix-automaton.html DAG + Small to Large Suffix Automaton의 DAG에서 DP를 진행할 수도 있지만, 관리해야 하는 것이 어떤 값이 아닌 목록인 경우 Small to Large 테크닉을 활용할 수 있습니다. DAG에서 Small to Large를 활용하게 되는 대표적인 경우는, $n$개의 문자열 $S_1,...
-
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을 하고 싶다면...