Greentea's Blog

Introduction안녕하세요, 지난시간까지 저희는 2D convolution을 새롭게 제안하는 sumcheck protocol을 통해 증명할 수 있는 방법에 대하여 알아보았습니다. 이번 시간에는, 2D convolution에서 그치지 않고, 실제 CNN 에 대한 증명으로 확장하기 위해 필요한 몇가지 테크닉들에 대하여 알아보도록 하겠습니다.  1.  Generalized addition and multiplication gates.기존의 GKR에서 제안되는 arithmetic gate의 경우는 두 가지 input wire를 받게 됩니다. 하지만 CNN의 경우 구조에 따라 이보다 더 많은 input을 받아야 하는 경우가 생기게 됩니다. 따라서 GKR 식을 좀 변형하여 multiple input을 받을 수..

Introduction안녕하세요, 저번 시간부터 저희는 prover와 verifier가 CNN model weight 을 공유하지 않고도 실제로 input에 대하여 올바른 연산을 진행하였음을 증명할 수 있는 ZK-CNN protocol에 대하여 알아보기 시작했습니다. 좀 더 구체적으로, 지난 시간 우리는 Fast Fourier Transform (FFT) 에 대한 새로운 Sumcheck Protocol에 대하여 알아보았습니다. 지난 시간 일련의 과정은 CNN 과는 어느정도 거리가 있는 내용으로 느껴지셨을 수 있는데요, 이번 시간에는 지난번에 알아본 FFT 에 대한 Sumcheck protocol 을 가지고, 어떻게 2D convolution을 증명할 수 있는지 알아보도록 하겠습니다.Proving 2D ..

안녕하세요, 오늘부터는 ZK-CNN 논문에 대하여 살펴보도록 하겠습니다. ZK-CNN은 영지식증명을 통해 기계학습의 결과를 증명하는 Zero-Knowledge Machine Learning (ZKML) 분야의 논문입니다. 해당 논문에서는 영지식증명을 활용해 비전 분야에서 많이 활용되는 Convolutional Neural Network (CNN) 을 증명하는 방법을 제안하고 있습니다. 저에게도 도전적인 논문인데요, 같이 한번 살펴보고 질문이나 잘못이해한 부분 있다면 같이 이야기해보면 좋을 것 같습니다.  Introduction우선 본격적으로 protocol에 대하여 알아보기 전에, ZK-CNN 이 왜 필요한지, 어떤식으로 작동하는 protocol인지에 대하여 먼저 살펴보도록 하겠습니다. Prover가 이..

Introduction 안녕하세요, 오늘은 영지식증명 과정에서 유용하게 사용되는 lookup argument에 대하여 알아보려고 합니다. Lookup argument는 영지식증명을 통해 증명하기 까다로운 연산들을, 이름에서처럼 미리 table 형식으로 지정해두고 (public table), 까다로운 연산들을 증명하는 대신, 해당 연산 결과값을 테이블에서 참조했음을 증명함으로써 까다로운 연산에 시간이 많이 소요되는 것을 방지할 수 있습니다. 예를 들어 영지식증명을 통해 non-linear 함수를 증명하는 것은 까다로운데요, lookup argument를 사용하면 미리 nonlinear한 연산의 증명은 테이블 참조 증명으로 대체함으로 영지식증명의 영역을 넓혀주는 역할을 하는데 굉장히 중요합니다. Lookup..

안녕하세요, 지난시간에 저희는 GKR protocol 에 대하여 살펴보았습니다. 이번 시간에는, GKR 구현체 코드에 대하여 살펴보며, 어떻게 실제로 GKR protocol을 구현할 수 있는지 살펴보도록 하겠습니다. 흥미롭게도 한국인 이더리움 개발자께서 만들어 두셨네요. 오늘 글에서는 모든 소스 코드를 살펴보기보다, 핵심 파일인 gkr.py 를 위주로 살펴보며, 해당 레포지토리에 코드가 있지만 설명이 필요한 경우는 글을 통해 설명하며 글을 진행해 보도록 하겠습니다. 본격적으로 들어가기에 앞서, 해당 구현은 지난 시간 살펴본 구현보다 조금의 테크닉이 더 가미되어 있습니다. 좀 더 정확히는, 링크의 65 페이지를 참조하면 되는데요, 코드를 살펴보며 해당 부분이 나오면 언급드리며 살펴보도록 하겠습니다. 증명 ..

안녕하세요, 오늘은 지난번 Sum-Check protocol에 이어 GKR protocol에 대하여 알아보도록 하겠습니다. 이번 글은 Thaler 교수님의 A Note on the GKR Protocol을 바탕으로 작성되었습니다. Sum-Check Protocol 복습 GKR protocol은 Sum-Check protocol을 활용해 주어진 circuit을 증명해내는 방법입니다. 따라서 우선 Sum-Check Protocol에 대하여 다시 한번 복습해 봅시다. 우선 우리에게 finite field $\mathbf{F}$ 에서 $v$ variate polynomial $g(\cdot)$ 이 주어졌다고 가정해 봅시다. Sum-Check protocol의 목적은 아래 식을 verifier에게 증명하는 것입니..

Introduction 안녕하세요, 지난 시간에는 영지식 증명 방법론 중 하나인 Sum-Check Protocol에 대하여 알아보았습니다. 이번 시간에는 sum-check protocol의 강력함을 경험하기 위해, 아주 유용한 사용 예제를 하나 가져와 보았습니다. 지난 시간과 마찬가지로 Justin Thaler 교수님의 렉쳐노트를 참조해 글을 작성했습니다. Main Protocol 행렬곱 증명의 목표는, prover가 verifier에게 어떠한 두 행렬 $A, B$의 곱은 $C$라는 claim을 증명하는 것입니다. 두개의 인풋 행렬 $A, B \in \mathbf{R}^{n \times n}$이 있을 때, 각각의 행렬은 $\{0, 1\}^{logn} \times \{0, 1\}^{logn}$ 에서 fin..

Introduction 안녕하세요, 오늘은 영지식증명의 다양한 분야에서 사용되고 있는 Sum-Check Protocol에 대하여 알아보는 시간을 가지려고 합니다. 이번 블로그 포스트는 Justin Thaler 교수님의 Sum-check Protocol 강의 자료를 참조하여 만들었습니다. Sum-Check Protocol Sum-Check Protocol 에서 증명하고자 하는 바는 다음과 같습니다: 우리가 어떤 finite field $\mathbf{F}$에서 $v$개의 변수를 같는 다항식 $g$를 가지고 있다고 가정하겠습니다. sum-check protocol의 prover는 아래 값을 verifier에게 증명하는 것이 목표입니다. $H := \sum_{b_1 \in \{0, 1\}} \sum_{b_2 ..

안녕하세요, 이전 시간에는 영지식 회로 (zero-knowledge circuit)을 만들 수 있는 프로그래밍 언어 Circom 의 사용 방법에 대하여 알아보았습니다. 이번 시간에는 PLONK 기반의 영지식 회로를 만들 수 있는 Halo2 언어에 대하여 살펴보도록 하겠습니다. 체감상 Halo2는 Circom 보다 진입장벽이 더 높은 것 같습니다. 이번 블로그 글의 목표는 코드에 사용되는 모든 component의 동작을 이해하는 것보다는 high level 에서 동작을 이해하는 것을 목표로 하겠습니다. halo2는 Rust언어를 기반으로 작동하기 때문에, 해당 코드 작성 전 Rust 설치가 우선시되어야 합니다. 조금 더 구체적으로, 이번 시간에는 Halo2 를 통해 피보나치 수열의 계산을 증명하는 방법에 ..

Introduction 안녕하세요, 지난 시간까지는 영지식 증명 방법 중 하나인 PLONK에 대하여 알아보았습니다. 지난 시간까지 조금 이론적인 내용을 다루었다면, 이번 시간에는 영지식 증명을 위한 회로를 짜는 방법에 대하여 알아보도록 하겠습니다. Alice가 영지식 증명을 통해 어떤 주장을 증명하고 싶어합니다. Alice는 앞서 배운 PLONK를 직접 구현할 수도 있겠지만, 이러한 과정은 시간이 굉장히 많이 소요됩니다. 다행히도, 개발자들이 이미 쉽게 영지식 증명을 위한 회로를 짤 수 있는 방법을 마련해 두었습니다. Circom, Halo2, Noir 등이 이러한 예시입니다. 이번 시간에는 Circom 을 사용하는 방법에 대하여 알아보도록 하겠습니다. Installing Circom 자세한 circom..