Zero Knowledge Seoul 2022.9.17 내용 끄적이기

쌍제이(JJVoiture)·2022년 9월 17일
blockchain
0

Overview of zkEVM & zkRollup

블록체인 트릴레마 중 Ehtereum scaling problem을 해결하기 위함.
** 확장성 문제: 자원을 더 투입해도 TPS가 증가하지 않는 문제.

Layer 2 scalability solutions

Rollup

사용자들의 트랜잭션을 모아 off chain에서 연산을 수행하고, 결과의 batch를 업데이트하는 방식.

종류

  • Optimistic Rollup
    : 데이터가 옳다고 가정하고 기록, 사기 증명을 통해 데이터 관리(?)

  • zk Rollup

zkRollup의 영지식 증명 활용 방식

Secret: 전송 데이터

Prover: Relayers

Verifier: Ethereum Smart Contract

Validity proof

영지식 증명을 활용하여, state가 항상 옳다는 것을 증명하는 방식.

optimistic vs zkRollup

사기 증명 - zk validity proof
인출시 대기 기간 필요 - 즉시 인출 가능

등등

zkRollup 프로젝트 종류

dydx

Immutable X

nft 거래에 특화된 zkRollup 기반 프로젝트.
즉각적으로 거래 확인 가능, 가스 수수료가 거의 없음.

zkEVM

Problem

EVM은 zk-circuit을 실행할 수 있도록 디자인 되어 있지 않음.

Ethereum compatibility

언어: 솔리디티
인터페이스: 이더리움 JSON-RPC 클라이언트 API
토큰 스탠다드: ERC20/ERC721 등의 토큰 표준
라이브러리: ether.js

언어 단계: EVM 친화적 언어를 영지식 친화적 언어로 바꾸는 단계.

바이트코드 단계: evm 바이트코드를 번역하여 zk 친화적인 evm에서 코드가 실행되는 단계.
여기에 도달해야 zkEVM이라 할 수 있다.

consensus 단계: 컨센서스 단계에서도 호환성을 달성하는 단계.

zkEVM의 실행 과정

  1. evm exevutor에서 트랜잭션을 실행하여 posr_state를 얻는다.
  2. pre_state, tx, post_state를 zkEVM에 입력하면...
    (못 적었다...)

Bus mapping

상태 증명: 일관성과 정확성을 담당하는 증명.
EVM 증명: EVM 연산 코드의 올바른 실행을 담당한는 증명.

zkEVM 생태계

  • 스타크넷
    : language level에 해당하는 솔루션. Cairo로 실행.
  • zkSync:
  • polygon Hermez
    : opcode-level에서 zkEVM을 만들고 있음.
  • Scroll
    : EVM execution tract 자페를 증명하여 모든 EVM opcode를 circuit에서 바로 실행할 수 있는 zkEVM 개발이 최종 목표이다.

Introduction to zk-SNARK theory

  • Interactive ZKP
    증명자와 검증자 사이의 상호작용.
  • Non-interactive ZKP
    증명자 혼자서 증거를 생성.

zk-SNARK(Succint, Non-Interactive, ARguments of Knowledge)

zk-SNARK = flattening + ECC

무엇을 ZKP할 것인가?
f = MIMC hash function, EVM operations, 등

ex) f(x) = x^3 + x + 5
private input: x = 3
public output: out = 35

prover: x=3을 알지만 전달 안해.
verifier: x=3을 모르지만 prover가 input을 제대로 알고 있다는 것을 알아.

개발자가 해야 하는 건 circom을 잘 작성하는 거....

ZKP process

arithmetic circuit(gates)

산술회로화
gate는 곱셈과 덧셈만 지원

gate1: 		  x * x = v1
gate2: 		 v1 * x = v2
gate3: (v2 + x) * 1 = v3
gate4: (v3 + 5) * 1 = v4

solution vector

S = [1, x, out, v1, v2, v3]

산술회로를 분해하는 과정에서 생성되는 모든 중간 변수와 상수항을 포함.

witness vector

S = [1, 3, o35, 9, 27, 30]
solution vector(x=3) == witness vector

R1CS(Rank 1 Constraint System)

circuit의 각 게이트가 a x b = c꼴로 전부 분해된 형태
개별 gate의 A, B, C 열을 각각

		1	x	out	  v1	v2	  v3
gate1  	0	1	0	  0		0	  0	
gate2	0	0	0	  1		0	  0	
gate3	0	1	0	  0		1	  0
gate4	5	0	0	  0		0	  1

꼴의 행렬로 나타내...

A * B = C 꼴의 행렬 곱으로 나타낼 수 있는가??? NO!!!!
차원이 안맞아서 불가능.
다항식의 특성을 활용해서 R1CS를 QAP로 변환하자.

QAP: Quadratic Arithmetic System

규칙

R1CS의 A행렬의 1열 벡터를 취해서 각 요소를 y좌표로 하고, gate 넘버를 t좌표로 하는 점 4개를 추출한다.
Lagrangian interpolation을 이용하여
(1, 0), (2, 0), (3, 0), (4, 5)를 지나는 3차 함수를 구해.
이를 계수 벡터로 표현.

y = -5 + 55/6 * t - 5 * t^2 + 5/6 * t^3

이 식으로 R1CS를 QAP로 변환.

--> (gate 수) x (solution vector 차원) 행렬을 (solution vector 차원) x (gate 수)로 변환하기 때문에 행렬 곱이 가능해진다.

  • Lagrangian interpolation으로 얻어진 다항식들은 t = 1, t = 2, t = 3, t = 4일 때 빼고는 의미가 없다.

t = 1을 넣으면 R1CS[1] == QAP A(1)[]가 나온다....

왜 이런 짓을 하는가?

  • succint해진다.
  • 회로의 여러 constraints를 한 번에 검증하고 싶어서.

gate1: (A(1)[].S) x (B(1)[].S) - (C(1)[].S) = 0

let
(. : 내적)

  • alpha(t) = (A(t)[].S)
  • beta(t) = (B(t)[].S)
  • gamma(t) = (C(t)[].S)

alpha(t) x beta(t) - gamma(t) = 0

t = 1, 2, 3, t일 때 성립
alpha(t) x beta(t) - gamma(t) = H(t) x (t-1)(t-2)(t-3)(t-4)
(t-1)(t-2)(t-3)(t-4) = z(t)라고 하면,

alpha(t) x beta(t) - gamma(t) = H(t) x z(t)
QAP의 형태로 표현된 경우 단 한 번의 나눗셈만으로 모든 gate를 통과함을 검증할 수 있다.

실제 응용 사례에서 gate의 수는 1억 개 이상.

여기까지는 암호화가 안 되어 있음(zk 특성이 없음)
검증의 간소화를 위해 식의 구조를 바꾸었을 뿐
QAP의 등식을 구성하는 다항식을 타원 곡선에 올려 암호화할 것.

enc(alpha(t) x beta(t) - gamma(t)) = enc(H(t) x z(t))
연산 관계가 보존하는 암호화 함수가 있다면 가능하지 않을까?

ECC / ECDLP

ECC: 타원 곡선 암호화
ECDLP: 타원 곡선 이산대수문제
d*P = Q
덧셈, 곱섬 점 연산에 대하여 공개 좌표 P, Q로부터 d를 유추하는 게 매우 어려움....
P, Q를 공개키, d를 개인키로 활용.

Trusted Setup

QAP의 다항식들에 타원곡선 암호화를 적용하기 위해서, QAP의 다항식들을 타원곡선 위로 올린다.

alpha(t) x beta(t) - gamma(t) = H(t) x z(t)
에 랜덤한 숫자 t = r 대입

enc(alpha(r) x beta(r) - gamma(r)) = enc(H(r) x z(r))

QAP: [alpha, beta, gamma, H, z]
 * G
타원 곡선: [P, Q, R, S, T}

Bilinear Pairing

ECC의 복호화 없이 타원 곡선 상의 점들 간의 연산만으로 QAP의 constraint 식이 성립하는지 검증할 수 있다.

ex) e(cX, dZ) = e(X, Z)^cd

e(3, x1) = e(1, 33)
2^(3 x 11) 11대신 2^11을 공개

alpha(r) x beta(r) - gamma(r) = H(r) x z(r)
P x Q - R = S x T
연산 관계가 보존된다.

마무리...

zk-friendly hash function과 이에 대한 analysis도 했는데 일단 마무리한다...

profile
쌍제이(JJVoiture)
안녕하세요. 중구난방 개발자 쌍제이입니다.
이전 포스트

마스터링 이더리움 12장: DApp

다음 포스트

query, mutation, fragment

0개의 댓글