CRDT에 대해서

Overview

CRDT (Conflict free Replicated Data Types)는 중앙 서버의 개입 없이, 유저 간 컨센서스, 동기화 과정을 거치지 않고도 동일한 상태를 가질 수 있도록 하는 기술입니다.

기존에는 OT (Operational Transformation) 방식을 사용했습니다. 중앙 서버가 유저들의 작업 내용을 모두 받아 이를 적절하게 보정하여 모든 유저들의 상태를 동일하게 하였습니다. 하지만 유저 간 통신으로 동기화가 불가능 하기 때문에 중앙 서버에 과부하가 올 수 있다는 문제점이 있었습니다.

CRDT (Conflict free Replicated Data Types)

CRDT는 두 가지 방식이 존재합니다. State based CRDT(상태 기반 CRDT)와 Operation based CRDT(작업 기반 CRDT) 입니다.

Eventual Consistency

CRDT를 다루기 전에 먼저 Eventual Consistency에 대한 설명이 필요합니다.

Eventual Consistency란 모든 복제본들에 대해서 새로운 상태 업데이트가 발생하지 않을때 동일한 값으로 수렴하는 것이 가능하다는 것입니다.

Eventual Consistency를 만족하기 위해서 아래 3가지 조건이 필요합니다

• Eventual Delivery: 어떤 복제본에 특정 method가 실행 되었다면 다른 복제본에서도 동일한 method가 실행 될 수 있습니다.

• Convergence: 어떤 두 복제본이 동일한 method set을 가지고 수행되었다면 그 두 복제본은 같을 수 있습니다.

• Termination: 모든 method는 정상적으로 실행 되어야 합니다.

Eventual Consistency를 만족하면 CRDT를 만족할 수 있느냐 라고 한다면 그렇지 않을 수 있습니다.

Eventual Consistency 만으로는 동일한 상태를 만들 수 있다는 가능성만을 나타낼 뿐 이를 확실할 순 없습니다.

Strong Eventual Consistency

그래서 조금 더 강력한 조건이 필요합니다. 이를 Strong Eventual Consistency라고 합니다.

Strong Eventual Consistency는 Eventual Consistency에서 업데이트가 다른 순서대로 오더라도 동일한 상태가 된다는 내용입니다.

이를 만족하기 위해서 Eventual Consistency를 만족하면서 아래 조건을 추가로 만족해야 합니다.

• Strong Convergence: 어떤 두 복제본이 동일한 method set을 가지고 수행되었다면 그 두 복제본은 같은 상태를 가집니다.

그래서 CRDT를 달성한다는 것은 SEC를 만족한다는 것과 같은 말이라고 할 수 있습니다.

State based CRDT

State based CRDT는 복제본 간에 상태를 전달하여 모든 복제본의 상태를 일치시키는 방법입니다.

State based CRDT에서 각 복제본은 아래의 튜플을 구성합니다.

$(S, S^0, q, u, m)$

$ S = State, S^0 = Initial \ State$

$ q=Query, u=Update, m=Merge $

Merge function

State의 순서에 상관없이 모든 복제본이 동일한 상태로 수렴하게 하려면 Merge function이 매우 중요합니다.

그러기 위해서 Merge function은 아래의 조건을 만족해야 합니다.

• 교환법칙: 두 상태를 결합할 때 순서를 바꾸더라도 결과 값은 동일하다

• 멱등법칙: 동일한 두 상태를 결합할 때 결합한 상태와 같은 값이 나와야 한다.

• 결합법칙: 3개 이상의 상태에 대해서 결합을 하고자 할 때, 어떤 2개의 상태를 먼저 결합을 하더라도 결과 값은 동일하다.

위의 3가지 조건을 만족하는 Merge function을 구성한다면 State based CRDT를 만족할 수 있게 됩니다.

Operation based CRDT

Operation based CRDT는 복제본 간에 수행된 작업을 전달하여 모든 복제본의 상태를 일치시키는 방법입니다.

State based CRDT에서 각 복제본은 아래의 튜플을 구성합니다.

$(S, S^0, q, u, t m)$

$ S = State, S^0 = Initial \ State$

$ q=Query, t= prepare-update, u=effect-update, m=Merge $

State based CRDT에서 있던 Merge 가 사라지고 Update가 $(u,t)$ 쌍으로 구분 되었습니다.

Commutativity

Operation based CRDT에서도 State based CRDT와 마찬가지로 순서에 상관없이 동일한 상태로 수렴할 수 있어야 합니다.

그러기 위해서 Update 연산에 대해서 순서를 바꾸더라도 동일한 결과값을 획득할 수 있어야 합니다.

위 사진에 보이는것 처럼 $\alpha$, $\beta$ 업데이트를 한다고 했을 때 순서를 바꿔서 업데이트를 수행하더라도 동일한 결과를 얻을 수 있어야 합니다.

이를 만족하는 Update method를 구성한다면 Operation based CRDT를 만족할 수 있게 됩니다.

Sidetree?

이전 포스팅에서 Sidetree protocol에 대해서 다루었는데 Sidetree protocol에서 Sidetree node간 상태를 일치시키는데 CRDT를 사용하고 있습니다.

그러면 Sidetree에서는 State based CRDT를 사용할까요? Operation based CRDT를 사용할까요?

Delta based CRDT

State based CRDT는 모든 복제본에 상태값을 전달하게 되는데 상태값 전체를 전달하게 되면 전송하는 데이터의 사이즈가 굉장히 커질 수 있습니다.

이를 보완하고자 변경 된 상태에 대해서만 다른 복제본으로 전달하는 Delta based CRDT가 파생 되었습니다.

각 복제본은 전체 상태를 다른 복제본으로 전달하지 않고 변경된 상태에 대해서만 다른 복제본으로 전달하게 되고 그 이후 과정은 State based CRDT와 동일하게 수행됩니다.

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)