DID Sidetree 프로토콜

Overview

Sidetree 프로토콜은 탈중앙화 시스템 위에서 DID를 구현할 수 있게 해주는 Layer 2 프로토콜 입니다.

현재 여러 블록체인 위에서 동작하는 많은 DID 시스템이 있지만, 트랜잭션 수수료 및 처리량에 대한 한계가 있기 때문에 그러한 문제점을 해소할 수 있는 방안으로 제시된 프로토콜 입니다.

Network Topology

Sidetree의 네트워크는 크게

• Content Addressable Storage (CAS) (eg. IPFS)
• Sidetree Node
• Decentralized Ledger System (eg. Bitcoin, Ethereum)

의 3가지로 구분될 수 있습니다.

Sidetree Node는 사용자로 부터 특정 요청을 받아 이를 처리합니다. 사용자로부터 받을 수 있는 요청은 DID resolve, 혹은 Create, Update, Recover, Deactivate 등의 동작이 될 수 있습니다.

DID State에 대한 변경이 필요하다면 변경 사항을 Decentralized Ledger System과 CAS에 저장하고 DID State에 대한 조회가 필요하다면 Decentralized Ledger System과 CAS로 부터 필요한 데이터를 불러와 사용자에게 전달 할 것입니다.

DID URI Composition

Sidetree 기반의 DID는 Short-Form, Long-form 2가지로 나뉘어 집니다. Short-form DID는 did:{METHOD}:{DID-SUFFIX} 의 형식으로 이루어져 있으며 Long-form DID는 did:{METHOD}:{DID-SUFFIX}:{LONG-FORM-SUFFIX-DATA} 로 이루어져 있습니다.

Long-Form Suffix Data는 위 사진에 나온 Long-form DID Data를 Base64URL 형식으로 인코딩한 값입니다. 해당 값을 구성하는 필드를 어떻게 생성하는 지는 DID Operation의 Create에서 자세히 설명 할 것입니다.

DID Operation

Sidetree 프로토콜에서 수행할 수 있는 DID Operation은 크게 Create, Update, Recover, Deactivate의 4가지 입니다.

Create

Create Operation은 DID를 생성하는 기능을 수행하며 이후 동작에 사용할 Update Key Pair와 Recovery Key Pair를 생성하는 과정을 포함하고 있습니다.

이 과정에서 Long form DID Data를 구성하는 데이터들을 생성하게 되고 여기서 생성한 값들을 Long-form DID를 구성하는데 사용합니다.

Update

Update Operation은 해당 DID에 대한 attribute를 수정하는 기능을 수행합니다. (eg. add/remove keys, add/remove services, …)

Create Operation 혹은 이전 Update Operation 과정을 수행하면서 만든 Update key를 필요로 하며 동일한 키를 계속 사용하는것이 아닌 새로운 Update key Pair인 Next Update Key Pair를 생성하여 다음 Operation에 사용할 수 있도록 합니다.

Recover

Recover Operation은 해당 DID에 대한 attribute를 복구하는 기능을 수행합니다.

기존에 생성한 Update key, Recovery Key 모두를 필요로 하며 Update와 마찬가지로 이후 Operation에서는 동일한 키를 계속 사용하는것이 아닌 새로운 Update key Pair인 Next Update Key Pair, 새로운 Recovery key Pair인 Next Recovery Key Pair를 생성하여 다음 Operation에 사용할 수 있도록 합니다.

Deactivate

Deactivate는 해당 DID를 비활성화 하는 기능을 수행합니다.

Patches

DID Operation를 수행하면서 Delta Object를 생성하는 과정에서 Patches 라는 필드가 Array로 포함되는데 이 필드에 실제 어떤 기능을 하는지에 대한 내용이 포함됩니다.

Sidetree 프로토콜에서 제공하는 Patches에 대한 종류는 아래 사진과 같습니다.

자세한 내용은 DID State Patches 링크를 참조하세요

Reference

Sidetree DIF spec

ION github

Nestjs에 SWC 컴파일러 적용하기

본 문서는 Nestjs 공식문서 를 참조하여 작성 되었습니다.

Overview

Nestjs v10부터 swc 를 사용할 수 있게 되었습니다. 사실 v9때도 불가능 했던 것은 아니지만 공식 문서에서도

SWC isn't compatible with NestJS CLI plugins.

이라고 안내를 했었던 만큼 v10에서 공식적인 지원이 되었다 라고 봐도 괜찮을 것 같습니다.

본 문서에서는 제가 사용하고 있는 boilerplate에 어떤 방법으로 swc를 적용하였는지에 대하여 작성하였습니다.

Installation

시작을 위하여 아래 명령어를 이용하여 패키지를 설치 해 주었습니다.

yarn add -D @swc/cli @swc/core

Getting Started

위 패키지를 설치하고 nest-cli에 -b 옵션을 통해서 swc를 적용할 수 있습니다.

nest start -b swc

위 명령어처럼 -b 옵션을 주는것으로 실행이 가능 하지만 nest-cli.json에 아래 내용을 추가하는 것으로 builder로 swc를 사용하게 끔 설정할 수 있습니다.

{
  "compilerOptions": {
    "builder": "swc"
  }
}

아니면 아래와 같이 추가적인 옵션을 설정하는 것도 가능합니다.

"compilerOptions": {
  "builder": {
    "type": "swc",
    "options": {
      "swcrcPath": "infrastructure/.swcrc"
    }
  }
}

제가 실제 사용하고 있는 nest-cli.json 내용은 아래와 같습니다.

{
    "language": "ts",
    "collection": "@nestjs/schematics",
    "sourceRoot": "src",
    "compilerOptions": {
        "builder": {
          "type": "swc",
          "options": {
            "swcrcPath": ".swcrc"
          }
        }
      }      
}

위 파일에서 .swcrc 파일을 사용하고 있는데 swc에 대한 옵션을 구성하는 파일입니다.

기본적으로 루트 디렉토리에 두어야 하지만, 다른곳에 두더라도 nest-cli.json 에서 .swcrc 파일 위치를 지정할 수 있습니다.

.swcrc 파일에 대한 예시는 아래와 같습니다.

{
    "sourceMaps": true,
    "module": {
        "type": "commonjs",
        "strict": true
    },
    "jsc": {
        "target": "es2020",
        "parser": {
            "syntax": "typescript",
            "decorators": true
        },
        "transform": {
            "legacyDecorator": true,
            "decoratorMetadata": true
        },
        "keepClassNames": true
    }
}

여기까지 진행 했다면 nest start 혹은 nest build 등 기존 명령어를 그대로 수행하더라도 swc가 적용되어 실행 되는 모습을 확인할 수 있습니다.

TypeORM

만약 TypeORM을 사용하고 있는 경우 relation을 사용하는 경우 아래와 같은 오류를 볼 수 있습니다.

@Entity("role", { schema: "public" })
export class Role {

    // ---- snip ----
    
    @OneToMany(() => UserRole, userRole => userRole.role)
    userRoles: UserRole[];

// ---- snip ----

위 처럼 relation을 사용하는 경우 아래와 같이 처리를 해 주어야 합니다.

@Entity("role", { schema: "public" })
export class Role {

    // ---- snip ----
    
    @OneToMany(() => UserRole, userRole => userRole.role)
    userRoles: Relation<UserRole[]>;

// ---- snip ----

위와 같은 방법으로 Nestjs에 swc를 적용 해 보았습니다. 실제로 사용 해 보면서 확실히 빌드 속도가 빨라졌다 라는 것이 느껴질 정도로 속도에 변화가 있었습니다.

Nestjs를 사용하고 있다면 한번쯤 swc를 사용 해 보는것도 좋은 선택인 것 같습니다.

본 문서에서 사용된 모든 코드는 boilerplate 에 포함되어 있습니다.

ZK Whiteboard Sessions - Module Three 정리

본 문서는 ZK Whiteboard Sessions - Module Three를 보고 정리한 문서입니다. zk에 대한 이해가 완벽하지 않아서 잘못 이해하고 작성한 부분이 있을 수 있습니다.

youtube

Google Slide

Goal: Construct a poly-IOP called a “Plonk”

• Plonk + PCS ⇒ SNARK (and also a zk-SNARK)

Useful observation

• for \(0 \neq f \in \mathbb{F}_p^{(\leq d)}[X]\)
  for \(r \leftarrow \mathbb{F}_p\): \(Pr[f(r) =0] \leq d/p\) (*)
  최대 d차를 갖는 다항식 f에 대하여 f(r)=0 일 확률은 d/p보다 낮다.
  ⇒ \(p \approx 2^{256}\) 이고 \(d \leq 2^{40}\) 이라고 가정했을 때 \(d/p\)는 무시할만큼 낮다.
  ⇒ 임의의 \(r \leftarrow \mathbb{F}_p\): 에 대하여 \(f(r)=0\) 이라면 \(f\)는 높은 확률로 zero라고 추정할 수 있다.
  ⇒ polynomial commitment에 대한 간단한 zero 테스트
  
  • SZDL lemma: multivariate polynomial에 대해서도 (*) 부분의 식이 성립함
    • (\(d\) 는 \(f\)의 차수의 합)
  • SNARK에서 주로 사용하는 테크닉

Related observation

• \(p \approx 2^{256}\) 이고 \(d \leq 2^{40}\) 이라고 가정했을 때 \(d/p\)는 무시할만큼 낮다.
  • Let \(f,g \in \mathbb{F}_p^{(\leq d)}[X]\)
    임의의 \(r \leftarrow \mathbb{F}_p\)에 대해서 \(f(r)=g(r)\) 이라고 하면 \(f=g\) 라고 높은 확률로 추정할 수 있다.
    → \(f(r)-g(r)=0\) ⇒ \(f-g=0\)
    ⇒ polynomial commitment에 대한 간단한 equal 테스트

Useful proof gadgets

• Let \(\omega \in \mathbb{F}_p\) be a primitive \(k\)-th root of unity (\(\omega^k=1\))
  Set \(H := \{1, \omega, \omega^2 ,...,\omega^{k-1}\} \subseteq \mathbb{F}_p\)
  Let \(f \in \mathbb{F}_p^{\leq d}[X]\) and \(b,c \in \mathbb{F}_p\). (\(d \geq k)\)
  There are efficient poly-IOPs for the following tasks
  • Zero-test: prove that \(f\) is identically zero on \(H\)
  • Sum-check: prove that \(\Sigma_{a \in H}f(a) =b\) (verifier has \(\fbox{f},b\))
  • Prod-check: prove that \(\Pi_{a\in H}f(a)=c\) (verifier has \(\fbox{f},c\))
    box씌운 f는 f에대한 commitment입니다.
    

Zero test on \(H\)

• Prover P(\(f,\bot\))
• Verifier V(\(\fbox{f}\))

• Lemma: \(f\) is zero on \(H\) if and only if \(f(X)\) is divisible by \(X^k-1\)

• Prover는 \(q(X) \leftarrow f(X)/(X^k-1)\) 를 계산하고 \(q \in \mathbb{F}_p^{(\leq d)}[X]\) 에 대한 commitment를 Verifier에게 전달한다
• Verifier는 \(r \leftarrow \mathbb{F}_p\) 를 랜덤하게 선택한다.
• Verifier는 \(r\) 에 대해서 \(q(X), f(X)\) 를 Prover에게 질의한다. 이 과정에서 \(q(r), f(r)\)을 획득
• Verifier는 \(f,q\)에 대한 commitment를 가지고 있기 때문에 이를 검증할 수 있다.

• Verifier는 \(f(r)=q(r)(r^k-1)\) 임을 확인한다.

  • (implies that \(f(X)=q(X)(X^k-1)\))
  • 이를 만족한다면 Lemma에 의해 \(f\)는 \(H\)에서 zero
• Thm: this protocol is complete and sound, assuming \(d/p\) is negligible
• proof size: one commitment(\(\fbox{q}\)) + two open proof(\(q(X), f(X)\))

• Verifier time: \(O(logk)\) and two eval verify (but can be done in one)

• Prover가 \(q\)에 대한 commitment를 생성하기 전에 \(r\)을 알아버린다면 prover는 실제로 \(f\)가 조건을 만족하지 않아도 point \(r\)에 대해서 조건을 만족하는 \(q\)를 생성해 버릴 수 있다.
  ⇒ commitment를 생성한 이후에 \(r\)을 생성하는것이 매우 중요함

Plonk step 1

Step 1: compile circuit to a computation trace (gate fan-in = 2)

• we’ll want to do is prove that the computation trace is valid and that output actually is zero because we’d like to prove that \(C(x,w)=0\)

Computation Trace as Polynomial – Intro

\(\|C\| :=\) total number of gates in \(C\)

\(\|I\| := \|I_x\| + \|I_w\| =\) number inputs to \(C\)
I_x: statement input, I_w: witness input

let \(d := 3\|C\|+\|I\|\) (in example, \(d=12\)) and \(H := (1, \omega, \omega^2,...,\omega^{d-1})\)

The plan: prover interpolates a polynomial \(P \in \mathbb{F}_p^{(\leq d)}[X]\) that encodes the entire trace

Computation Trace as Polynomial – Constraints

The plan: prover interpolates \(P \in \mathbb{F}_p^{(\leq d)}[X]\) such that

1. \(P\) encodes all inputs: P(\(\omega^{-j}\)) = input number \(j\) for \(j = 1,..., \|I\|\)
2. \(P\) encodes all wires: \(\forall l=0,...,\|C\|-1\)
   • P(\(\omega^{3l}\)): left input to gate #\(l\)
   • P(\(\omega^{3l+1}\)): right input to gate #\(l\)
   • P(\(\omega^{3l+2}\)): output to gate #\(l\)

In out example, Prover interpolates \(P(X)\) such that:

Inputs: \(P(\omega^{-1})=5\), \(P(\omega^{-2})=6\), \(P(\omega^{-3})=1\)

gate 0: \(P(\omega^{0})=5\), \(P(\omega^{1})=6\), \(P(\omega^{2})=11\)

gate 1: \(P(\omega^{3})=6\), \(P(\omega^{4})=1\), \(P(\omega^{5})=7\)

gate 2: \(P(\omega^{6})=11\), \(P(\omega^{7})=7\), \(P(\omega^{8})=77\)

degree(\(P\)) = 11

Prover uses FFT to compute the coefficients of \(P\) in time \(dlogd\)

Plonk Step 2

Step 2: Prove P is valid computation trace

• Prover P(\(S_p,x,w\))

• Verifier V(\(S_v,x)\)

• Prover는 \(P(X) \in \mathbb{F}_p^{(\leq d)}[X]\) 를 만들고 \(P\)의 commitment를 Verifier에게 보낸다
  • Prover는 \(P\)가 올바른 computation trace임을 증명해야 한다.
    1. \(P\) encodes the correct inputs
    2. every gate is evaluated correctly
    3. the wiring is implemented correctly
    4. the output of last gate is 0

Prove Trace

Both prover and verifier interpolate a polynomial \(v(X) \in \mathbb{F}_p^{(\leq\|l_x\|)}[X]\) that encodes the \(x\)-inputs to the circuit:

for \(j=1,...,\|l_x\|\): \(v(\omega^{-j})\) = input #\(j\)

In out example: \(v(\omega^{-1})=5\), \(v(\omega^{-2})=6\), \(v(\omega^{-3})=1\). (\(v\) is quadratic)

constructing \(v(X)\) takes time proportional to the size of input \(x\)

⇒ verifier has time do this

Let \(H_{inp} := \{\omega^{-1}, \omega^{-2},...,\omega^{-\|l_x\|}\} \subseteq H\) (points encoding the input)

Prover proves (1) by using zero-test on \(H_{inp}\)to prove that

⇒ \(P(y)-v(y) = 0\). \(\forall y \in H_{inp}\)

Idea: encode gate types using a selector polynimial \(S(X)\)

define \(S(X) \in \mathbb{F}_p^{(\leq d)}[X]\) such that \(\forall l=0,...,\|C\|-1\):

\(S(\omega^{3l})=1\) if gate #\(l\) is an addition gate

\(S(\omega^{3l})=0\) if gate #\(l\) is an multiplication gate

Observe that, \(\forall y \in H_{gates}:= \{1, \omega^3, \omega^6,...,\omega^{3(\|C\|-1)}\}\):

\(P(y)\) = left input

\(P(\omega y)\) = right input

\(P(\omega^2y)\) = output

\(Setup(C) \rightarrow S_p:=S\) and \(S_v:=(\fbox{S})\)

Prover uses zero-test on the set \(H_{gates}\) to prove that \(\forall y \in H_{gates}\)

encode the wires of \(C\):

Define a polynomial \(W : H \rightarrow H\) that implements a rotation

Lemma : \(\forall y \in H: P(y) = P(W(y))\) ⇒ wire constraints are satisfied

Problem : the constraint \(P(y)=P(W(y))\) has degree \(d^2\)

⇒ prover would need to manipulate polynomials of degree \(d^2\)

⇒ quadratic time prover (goal: linear time prover)

Lemma : \(P(y) = P(W(y))\) for all \(y \in H\) if and only if \(L(Y,Z) \equiv 1,\)

where \(L(Y,Z) := \Pi_{x \in H}(P(x)+Y*W(x)+Z)/P(x)+Y*x+Z\)

To prove that \(L(Y,Z) \equiv 1\) do:

1. verifier chooses random \(y,z \in \mathbb{F}_p\)
2. prover builds \(:L_1(X)\) such that \(L_1(X)=(P(x)+Y*W(x)+Z)/P(x)+Y*x+Z\) for all \(x \in H\)
3. run prod check to prove \(\Pi_{x \in H}L_1(x) = 1\)

4. validate \(L_1\): run zero test on \(H\) to prove \(L_2(x)=0\) for all \(x \in H\),

   where \(L_2(x)=(P(x)+y*x+z)L_1(x) - P(x)+y*W(x)+z)\)

The Final Plonk poly-IOP

ZK Whiteboard Sessions - Module Two 정리

본 문서는 ZK Whiteboard Sessions - Module Two를 보고 정리한 문서입니다. zk에 대한 이해가 완벽하지 않아서 잘못 이해하고 작성한 부분이 있을 수 있습니다.

youtube

Google Slide

Building an efficient SNARK

1. A functional commitment scheme ⇒ cryptographic object
2. A suitable interactive oracle proof (IOP) ⇒ information theoretic object

(1) + (2) ⇒ (zk)SNARK for general circuits

Commitment

Cryptographic commitment: emulates an envelope

Algorithms:

• \(commit(m,r) \rightarrow com\) (\(r\) choose at random)
• \(verify(m,com,r) \rightarrow\) accept / reject

Properties:

• binding: commitment에 대해서 2가지의 유효한 *opening이 존재하지 않는다.
• hiding: commitment는 data에 대해서 아무런 정보도 공개하지 않음

Committing to a Value

Fix a hash function \(H: M\times R \rightarrow C\)

• \[commit(m,r): com:= H(m,r)\]
• \(verify(m,com,r):\) accept if \(com=H(m,r)\)

Committing to a Function

Choose a family of functions \(F = \{ f: X \rightarrow Y \}\)

Prover가 Function family에 속하는 \(f\)에 대해서 commit 하려고 한다면 이를 \(com_f\)를 사용하여 commit 할 수 있고 Verifier는 \(com_f\)를 저장한다.

나중에 Verifier가 \(x\)에 대해서 \(f(x)\)값을 요구할때 Prover는 \(y\)와 함께 Proof \(\pi\)값을 주어 Verifier가 이를 검증할 수 있도록 한다.

Proof \(\pi\)는 \(f(x)=y\) and \(f \in F\) 임을 검증한다.

Committing to a Function: Syntax

A functional commitment scheme for \(F\):

• \(setup(\lambda) \rightarrow pp\) (outputs public parameters \(pp)\)
• \[commit(pp, f,r) \rightarrow com_f\]
  • commitment to \(f \in F\) with \(r \in R\) a binding (and *optionally hiding) commitment scheme for \(F\)
  optionally hiding: ZK일 경우 hiding까지 만족 해야함

• \(eval\)(Prover P, verifier V): 주어진 \(com_f\) 와 \(x \in X,\) \(y \in Y\)에 대해서:

  P(\(pp, f,x,y,r) \rightarrow\) short proof \(\pi\)

  V(\(pp, com_f, x,y, \pi) \rightarrow\) accept/reject

• a SNARK for the relation: \(f(x) =y\) and \(f \in F\) and \(commit(pp,f,r)= com_f\)

Examples of Functional Commitments

Polynomial commitments:

• Committing to a univariate polynomial \(f(x)\) in \(\mathbb{F}_p^{(\leq d)}[X]\)
  • univariate polynomials of degree at most \(d\)

Multilinear commitments:

• Commiting to a multilinear polynomial in \(\mathbb{F}_p^{(\leq 1)}[X_1,...,X_k]\)

Linear commitments:

• Committing to a linear function \(f_{\overrightarrow{v}} (\overrightarrow{u})=<\overrightarrow{u},\overrightarrow{v}> = \Sigma^n_{i=i}u_iv_i\)

Polynomial Commitment Schemes (PCS)

A PCS is a functional commitment for the family \(F = \mathbb{F}_p^{(\leq d)}[X]\)

⇒ prover 는 단일 미지수 방정식 \(f\) in \(\mathbb{F}_p^{(\leq d)}[X]\) 를 commit할 수 있고, 이후에 public \(u,v \in \mathbb{F}_p\)에 대한 \(v = f(u)\) 를 검증할 수 있다.

KZG PCS Setup & Commitment

KZG (Kate-Zaverucha-Goldberg’2010)

Group \(\mathbb{G} := \{0,G, 2*G,...,(p-1)*G \}\) of order \(p\)

\(setup(\lambda) \rightarrow pp\):

• Sample random \(\alpha \in \mathbb{F}p\)
• \[pp=(H_0=G, H_1=\alpha*G, ..., H_d=\alpha^d*G)\in \mathbb{G}^{d+1}\]

• *delete \(\alpha\) (trusted setup)

  α를 지우지 않으면 유츌 되었을 때 이를 알고있는 다른 사람들이 가짜 proof를 생성할 수 있음

\(commit(pp,f) \rightarrow com_f\) where \(com_f := f(\alpha)*G \in \mathbb{G}\)

• \[f(X) = f_0+f_1X+...+f_dX^d \rightarrow com_f = f_0*H_0+...+f_d*H_d\]
• \[= f_0*G+f_1\alpha*G+...=f(\alpha)*G\]

=> α 없이 public parameter만 가지고 commitment를 검증할 수 있음

KZG PCS Evaluation

\(eval\):

Prover(\(pp,f,u,v)\)

Verifier(\(pp,com_f,u,v)\)

Goal: prove \(f(u)=v\)

\(f(u)=v \Leftrightarrow u\) is a root of \(\hat{f} = f-v \Leftrightarrow (X-u)\) divides \(\hat{f}\)

\(\Leftrightarrow\) exists \(q \in \mathbb{F}_p[X]\) such that \(q(X)*(X-u) = f(X)-v\)

compute \(q(X)\) and \(com_q\) → send \(\pi := com_q \in \mathbb{G}\) to verifier

accept if \((\alpha-u)*com_q = com_f-v*G\)

=> Verifier는 α를 알지 못하는데 어떻게 이를 계산하여 검증할까? => pairing을 사용하여 계산할 수 있음

KZG PCS Generalizations

Generalizations:

• KZG for committing to k-variate polynomials, buy eval proof size is k group elements
• Batch proofs
  • suppose verifier has commitments .\(com_{f1}, ... com_{f_n}\)
  • prover wants to prove \(f_i(u_{i,j})=v_{i,j}\) for \(i \in [n], j \in [m]\) ⇒ batch proof \(\pi\) is one or two group elements

Dory PCS

Difficulties with KZG: trusted setup for \(pp\), and \(pp\) size is linear in \(d\)

Dory:

• transparent setup: no secret randomness in setup
• \(com_f\) is a single group element (independent of degree \(d)\)
• evel proof size for \(f \in \mathbb{f}_p^{(\leq d)}[X]\) is \(O(logd)\) group elementes
• eval verify time is \(O(logd)\)
• Prover time: \(O(d)\)

Polynomial IOP Setup

Let \(C(x,w)\) be some arithmetic circuit.

Let \(x \in \mathbb{F}_p^n\)

Poly-IOP: a proof system that proves \(\exists w:C(x,w) =0\) as follows:

• \(setup(C) \rightarrow\) public parameters \(S_p\) and \(S_v =(f_0, f_{-1},...,f_{-s})\)

Polynomial IOP Evaluation

Polynomial IOP Properties

• Complete: if \(\exists w:C(x,w)=0\) thet verifier always accepts

• Knowledge sound: (informal) Let \(x \in \mathbb{F}_p^n\) for every \(P^*\) that convince the verifier with prob. \(\geq 1/10^6\) there is an efficient extractor \(E\) such that \(Pr[E(x,f_1,r_1,...r_{t-1},f_t) \rightarrow w]\) such that \(C(x,w)=0] \geq 1/10^e -\epsilon\)

• Optional: zero-knowledge

The Resulting SNARK

\((t,q)\) Poly-IOP: \(t:=\) number of polys. committed,

\(q :=\) number of eval queries in verify ( usually \(t,q \leq 3\) )

The SNARK:

• Prover sends t poly commitments
• During poly-IOP verify: run PCS evel protocol q times

• Use flat-Shamir transform to make the proof system non-interactive

• Length of SNARK proof: t poly-commits + q evel proofs
• Verifier time: q * time(evel verify) + time(IOP-verify)
• Prover time: t * time(commit) + q * time(prove) + time(IOP-prover)

ZK Whiteboard Sessions - Module One 정리

본 문서는 ZK Whiteboard Sessions - Module One을 보고 정리한 문서입니다. zk에 대한 이해가 완벽하지 않아서 잘못 이해하고 작성한 부분이 있을 수 있습니다.

youtube

Google Slide

Definition: SNARK

SNARK: 어떤 명제가 참임을 간결하게 증명 하는 것

zk-SNARK: 어떤 명제가 참인것에 대해 정보를 공개하지 않고 간결하게 증명할 수 있는 것

Applications of SNARKs

• Private Transaction on Public Blockchain
  • Tornado cash, Zash …
• Private Dapps
  • Aleo
• Scalability: 유효성을 갖춘 Rollup 시스템

Arithmetic circuits

• Fix a finite field F = {0, … p-1} for some prime p > 2
• Arithmetic circuit
  • Circuit \(C: F^n \rightarrow F\)
  • 그래프에서 노드가 +, -, x 이며 입력이 1, \(x_1\),…,\(x_n\) 인 directed acyclic graph (DAG)
  • 이는 n차 다항식을 정의 합니다.
  • $|C|=$ number of gates in \(C\)
• Example
  • $C_{hash}(h,m)$: Output 0 if SHA256(\(m\)) = \(h\), and \(\neq 0\) otherwise
  • $C_{hash}(h,m)=$ (\(h\) - SHA256(\(m\))), \(\|C_{hash}\| =\) 20K gates

Argument Systems

• Public arithmetic circuit: \(C:(x,w) \rightarrow F\)
  • $x$: public statement in \(F^n\)
  • $w$: secret witness in \(F^m\)

Non-interactive Preprocessing Argument Systems

• Preprocessing(setup): \(S(c)\) → public parameters \((S_p, S_v)\)

Preprocessing Argument System

• A preprocessing argument system is a triple \((S,P, V)\)
• $S(C)$ → public parameters\((S_p, S_v)\) for prover and verifier
• $P(S_p,x,w)$ → proof \(\pi\)
• $V(S_{v} ,x, \pi)$ → Accept or Reject

Argument System Requirements

Complete: 모든 \(C(x,w) = 0\)을 만족 시키는 \(x,w\)에 대하여 \(V(S_v,x, P(S_p,x,w))\) = accept 일 확률은 1이다.

Knowledge Sound: Verifier가 Proof를 Accepts 했다면 Prover는 \(C(x,w) = 0\) 을 만족시키는 \(w\)을 알고 있다고 할 수 있다.

→ \(P\)가 \(w\)를 모를 때 $V(S_v, x, \pi$)$ = Accept 일 확률은 무시할만큼 낮다

Optional: Zero Knowledge: \((C, S_p, S_v, x, \pi)\) 는 \(w\)에 대한 어떠한 정보도 노출하지 않는다.

Succintness

• SNARK: a Succinct ARgument of Knowledge a succint preprocessing argument system is a triple \((S, P, V)\)
• $S(C)$ → public parameters \((S_p, S_v)\) for prover and verifier
• $P(S_p, x,w)$ → short proof $\pi; |\pi|=0(log(|C|,\lambda)$
• $V(S_v, x, \pi)$ → **fast to verify : $time(V) =0(|x|, log(|C|), \lambda)$

SNARK: \((S, P, V)\) is complete, knowledge sound, succint

zk-SNARK: \((S, P, V)\) is a SNARK and is zero knowledge

Not a SNARK: Trivial Argument System

• Prover sends w to verifier
• Verifier checks if \(C(x,w) = 0\) and accpets if so

Problems with this

• $w$ might be secret: prover는 \(w\)를 공개하길 원하지 않음
• $w$ might be long: 간결한 proof를 원함
• computing \(C(x,w)\) may be hard: 빠르게 검증하기를 원함

Motivating Question: how is \(O(log n)\) Possible?

Types of Setup

$S(C;r)$ → public parameters \((S_p, S_v)\)

$r$: random bits

Types of setup

trusted setup per circuit.: $S(C;r)$ random $r$ must be kept secret from prover

prover learns $r$ → 잘못된 statement에 대해서도 검증 할 수 있게 됨

trusted but universal (updatable) setup: secret \(r\) is independent of \(C\)

transparent setup : \(S(C)\) does not use secret data ( trusted setup 없음 )

SNARK Landscape

SNARK Software Ecosystem

Definition of Knowledge Sound

Goal: If \(V\) accepts then \(P\) knows \(w\) s.t. \(C(x,w) = 0\)

$w$를 안다는것이 무슨 의미일까

Formally: $(S, P, V)$ is knowledge sound for a circuit $C$ if

for event poly. time adversary $A = (A_0, A_1)$ such that

\[ S(C) \rightarrow (S_p, S_v), \] \[ (x,state) \leftarrow A_1(S_p), \] \[ pi \leftarrow A_1(S_p, x, state) : \] \[ Pr[V(S_v,x,\pi) = accept] > 1 / 10^6 (non-negligible) \]

there is an efficient extractor \(E\) (that uses \(A_1\) as a block box) s.t.

\[ S(C) \rightarrow (S_p, S_v), \] \[ (x,state) \leftarrow A_0(S_p), \] \[ w \leftarrow E^{A_1}(S_p,x,state)(S_p, x) : \] \[ Pr[C(x,w)=0] > 1 / 10^6 - \epsilon \] (for a negligible \(\epsilon\))

⇒ Poly. time adversary \(A\)가 정상적으로 state로 부터 proof \(\pi\)를 생성할 수 있다면 \(C(x,w) = 0\)을 만들 수 있는 유효한 witness를 추출할 수 있는 extractor를 갖고 있다고 할 수 있다.

Definition of Zero Knowledge

$(S, P, V)$ is zero knowledge if for every \(x \in F^n\), proof \(\pi\) reveals nothing about \(w\), other than its existence

$(S, P, V)$ is zero knowledge if there is an efficient alg, Sim such that $(S_p, S_v, \pi) ← Sim(C,x)$ look like the real $S_p, S_v$ and $\pi$

Formally: \((S, P, V)\) is zero knowledge for a circuit \(C\)

if there is an efficient simulator Sim such that for all \(x \in F^n\) s.t \(∃ w: C(x,w) =0\) the distribution :

$(C, S_p, S_v, x, \pi):$ where \((S_p, S_v) ← S(C)\), \(\pi ← P(S_p, x, w)\)

is indistinguishable form the distribution :

$(C, S_p, S_v, x, \pi):$ where \((S_p, S_v, \pi) ← Sim(C,x)\)