-
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을 하고 싶다면...
-
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을 간단히...