ZK rollup - 1. 목적/library

2023. 6. 15. 10:25ㆍBlockchain/Roll up

728x90
반응형

※ 원글 작성 : 23년 3월 13일

Roll up Series

[Blockchain/Roll up] - Rollup의 개념과 특성
[Blockchain/Roll up] - ZK rollup - 1. 목적/library
[Blockchain/Roll up] - ZK rollup - 2. ZKP
[Blockchain/Roll up] - ZK rollup - 3. zkEVM 프로젝트
[Blockchain/Roll up] - ZK rollup - 4. zk-SNARK의 Circuit & QAP

ZK rollup에 대한 간략한 분석과 zk-SNARK를 구현한 go library gnark를 보면서 어떻게 구성되어 있나 확인해본다. 기본적인 rollup에 관한 설명은 이전 게시글에서도 확인할 수 있다.

Rollup 시의 ZKP 사용목적

일반적인 ZKP(Zero-Knowledge Proof)의 경우 내가 어떠한 정보를 알고 있다는 것을 verifier에게 직접 전달하지 않고도 verifier는 내가 그 정보를 알고 있다는 것을 검증하는 알고리즘이다. 이때 zk rollup에서는 어떠한 목적으로 ZKP를 사용하는것인가. 바로 사이드체인 정보를 보여주지 않는것이 목적이다. 사이드체인의 상태 변화 정보를 직접 제시하지 않고 메인체인이 그것을 검증함으로써 사이드 체인은 전체 정보를 메인 체인에 노출하지 않고, 메인 체인도 사이드체인의 상태 정보를 알 필요가 없다. 여러가지 정보를 직접 전달하지 않음으로써 생기는 이점 때문에 ZKP를 적용하는 것이다.

생성된 zk proof를 보고 메인체인은 올바르게 상태 변화가 이루어진것을 확인한다. 이때의 검증 과정은 proof가 유효한지 확인함으로써 이루어진다. Proof는 암호학적으로 안전한 서명, 랜덤값으로 구성되어 있기 때문에 이 요소들이 올바르게 포함되었는지, proof 자체가 유효한지를 확인한다. 또한 proof 내에 포함되어 있는 merkle root를 확인한다. 이전 state와 새로운 state의 차이를 나타네는 데이터를 포함하기 때문에 메인 체인은 저장되어 있는 이전 state merkle tree root hash를 가져와서 proof로 부터 얻은 데이터를 추가하여 새로운 merkle root hash를 생성 가능하다. 새로운 root hash와 계산한 root hash의 consistency를 확인해여 검증을 진행한다.

ZKP protocol

ZKP의 protocol 중 gnark에서 사용되는 Groth16과 Plonk의 비교분석 자료를 게시한다.

구분 Groth16 Plonk
trusted setup circuit specific universal
proof length very good normal
prover work good normal
verifier work good normal

Groth16은 동일한 circuit(single logic computatio)에 대해 많은 증명을 생성하고, 성능이 중요한 경우에 사용되며, Plonk는 많은 circuit(different arbirary business logic)을 처리할 때 사용한다.

각각의 특징은 아래와 같다.

Groth16

  • 많은 블록체인 프로젝트에서 사용됨
  • Circuit-specific함
  • Proof의 크기가 일정하며 검증시간이 빠름
  • General-purpose를 위해서는 circuit 별로 신뢰할 수 있는 설정(trusted setup)이 필요함
  • ZCash, Loopring, Hermez, Celo, Filecoin 등

Plonk

  • Universal함
  • Update 가능한 pre-processing 단계가 존재하며, 검증시간이 짧고 일정
  • Groth16에 비해 proof 크기가 더 크고 생성 속도가 느림
  • Aztec, ZKSync, Dusk 등

gnark

앞서 언급한 golang의 zk-SNARK 라이브러리인 gnark를 확인해본다.

Circuit 구조

gnark의 circuit은 frontend/Circuit에서 interface로 구현되어 있다. 각 circuit은 Define function 내에서 연산을 위한 알고리즘을 구현해야 한다.

type Circuit interface {
    // Define declares the circuit's Constraints
    Define(api API) error
}

Circuit structure는 frontend.Variable을 통해 각 변수의 public/secret input을 정의한다.

type MyCircuit struct {
    C myComponent
    Y frontend.Variable `gnark:",public"`
}

type myComponent struct {
    X frontend.Variable
}

func (circuit *MyCircuit) Define(api frontend.API) error {
    // ... see Circuit API section
}

Struct 내의 var들은 gnark:",public"을 명시적으로 표현함으로서 해당 variable이 public인지 secret인지 구분짔는다. 또한 Compile 시에 frontend.Compil(...)은 frontend.constraintSystem을 build하기 위해 frontend.Variable을 포함하는 struct field를 재귀적으로 parsing한다.

Circuit APIs & conditionals/loops

Circuit struct내의 func Define(api frontend.API) error 상에서 연산이 수행되는 것을 지원하기 위해 gnark에서 연산 function을 지원한다. 지원되는 API는 frontend.API에서 확인 가능하다. 예를 들어 아래와 같은 cubic equation을 증명할 때에 gnark 라이브러리를 통한 구현 코드이다.

x3 := api.Mul(circuit.X, circuit.X, circuit.X)
api.AssertIsEqual(circuit.Y, api.Add(x3, circuit.X, 5))

loop는 일반 golang의 for를 사용하고, conditional은 if else 대신 사용할 수 있는 Select 함수를 따로 제공한다.

// Select if b is true, yields i1 else yields i2
func (cs *ConstraintSystem) Select(b Variable, i1, i2 interface{}) Variable {
    ...
}

gnark standard library

gnark에서는 hash 및 signature 검증, proof verify 등의 기능을 제공한다.

  • MiMC hash
func (circuit *mimcCircuit) Define(api frontend.API) error { 
  // ... 
  hFunc, _ := mimc.NewMiMC(api.Curve()) 
  computedHash := hFunc.Hash(cs, circuit.Data) 
  // ... 
}
  • EdDSA signature verification
type eddsaCircuit struct { 
  PublicKey eddsa.PublicKey `gnark:",public"` 
  Signature eddsa.Signature `gnark:",public"` 
  Message frontend.Variable `gnark:",public"` 
}
func (circuit \*eddsaCircuit) Define(api frontend.API) error {  
  edCurve, \_ := twistededwards.NewEdCurve(api.Curve())  
  circuit.PublicKey.Curve = edCurve eddsa.Verify(cs, circuit.Signature, circuit.Message, circuit.PublicKey)

  return nil  
}
  • Merkle proof verification
type merkleCircuit struct {  
  RootHash frontend.Variable `gnark:",public"`  
  Path, Helper \[\]frontend.Variable  
}  
func (circuit \*merkleCircuit) Define(api frontend.API) error {  
  hFunc, \_ := mimc.NewMiMC(api.Curve())  
  merkle.VerifyProof(cs, hFunc, circuit.RootHash, circuit.Path, circuit.Helper)

  return nil  
}
  • zk-SNARK verifier
type verifierCircuit struct { 
  InnerProof Proof 
  InnerVk VerifyingKey
  Hash frontend.Variable 
} 
func (circuit *verifierCircuit) Define(api frontend.API) error { 
  groth16.Verify(api, circuit.InnerVk, circuit.InnerProof, []frontend.Variable{circuit.Hash}) 

  return nil 
}

Compiler hint

Circuit 내에서 값을 계산하는 대신 circuit 외부에서 계산하고, circuit은 계산의 정확성만 확인 할 수 있도록 hint를 제공한다. Prover 입장에서 hint는 user가 아닌 hint 함수가 제공하는 입력 variable이다. 예를 들어, int를 a 비트로 분해할 경우, 정수의 binary 표현을 보고 비트를 추출하는 것이 아닌 gnark 제공하는 hint.IthBit 비트를 변수로 제공할 수 있다.

var b \[\]frontend.Variable  
var Σbi frontend.Variable  
base := 1  
for i := 0; i < nBits; i++ {  
  b\[i\] = cs.NewHint(hint.IthBit, a, i)  
  cs.AssertIsBoolean(b\[i\])  
  Σbi = api.Add(Σbi, api.Mul(b\[i\], base))  
  base = base << 1  
}  
cs.AssertIsEqual(Σbi, a)

Compiler circuit

frontend.Compile 함수를 통해 알고리즘 연산을 통한 variable 추출이 가능하다. Circuit이 컴파일되면 backend의 3가지 알고리즘(setup/prove/verify)이 실행 가능하다.

  • Groth16
// 1. one time setup 
pk, vk, err := groth16.Setup(cs) 
// 2. proof creation 
proof, err := groth16.Prove(cs, pk, witness) 
// 3. proof verification 
err := groth16.Verify(proof, vk, publicWitness)
  • Plonk (development version)
// 1. one time setup 
publicData, _ := plonk.Setup(cs, ...) 
// WIP 
// 2. Proof creation 
proof, err := plonk.Prove(r1cs, publicData, witness) 
// 3. Proof verification 
err := plonk.Verify(proof, publicData, publicWitness)

또한, go process 내에서 circuit data 구조를 재사용하여 witness를 구성할 수 있다.

type Circuit struct {  
    X frontend.Variable  
    Y frontend.Variable `gnark:",public"`  
}

assignment := &Circuit {  
    X: 3,  
    Y: 35,  
}

witness, \_ := frontend.NewWitness(assignment, ecc.BN254)

// use the witness directly in zk-SNARK backend APIs  
groth16.Prove(cs, pk, witness)

// test file --> assert.ProverSucceeded(cs, &witness)

이더리움에서 사용 가능하도록 solidity를 export하는 기능도 제공하고 있는데 사용 방법은 아래와 같으며, 여기에서 이더리움 사용 예제가 있다.

// 1. Compile (Groth16 + BN254)  
cs, err := frontend.Compile(ecc.BN254, r1cs.NewBuilder, &myCircuit)

// 2. Setup  
pk, vk, err := groth16.Setup(cs)

// 3. Write solidity smart contract into a file  
err = vk.ExportSolidity(f)

Compression

타원 곡선 point들(ProvingKey, VerifyingKey or Proof object)은 오직 X coordinate에서만 저장함으로써 압축(compression)될 수 있다. 이렇게 하면 object를 나타내는 필수 항목이 2개로 나뉘지만 deserialization 측면에서 상당한 CPU 비용이 발생한다.

provingKey.WriteRawTo(&buf) // alternatively, provingKey.WriteTo(&buf)  
...

pk := groth16.NewProvingKey(ecc.BN254)  
pk.ReadFrom(&buf) // reader will detect if points are compressed or not

Deserialization 시 speed > storage cost 일 때 WriteRawTo를 사용하고, 다른 경우에는 point compression과 함께 WriteTo를 사용한다.

Witness

Prove 또는 verify 함수에 대한 input으로 사용되는 witness는 위에서 언급한 것처럼 witness를 구성할 수도 있고 non-Go codebase인 gnark 밖에서도 구성될 수 있다. Witness는 Full witness와 Public witness로 존재할 수 있으며, full witness는 public과 secret 입력을 포함하여, Prove가 필요한 input이며, public witness는 public input만 들어가서 Verify가 필요한 input이다. Witness가 커질 수도 있기 때문에 성능적인 측면에서 witness는 binary protocol을 사용하여 encoding이 되어야 한다.(gnark는 JSON encoding을 제공)

  • Binary protocol
    gnark는 표준이 없을 동안 다른 zk-SNARK 라이브러리의 패턴을 따라한다.
    • nbElement == len(publicVariables) + len(secretVariables)
    • 각 변수는 big endian byte array로 인코딩 된다. len(bytes(variable)) == len(bytes(modulus))
    • // Full witness -> [uint32(nbElements) | publicVariables | secretVariables] // Public witness -> [uint32(nbElements) | publicVariables ]
  • Ordering
    Ordering sequence는 publicVariable이 첫번째이고, secretVariables가 다음이다. 각 subset은 circuit structure에 있는 order의 정의로부터 ordering 된다. 예를 들어 [uint32(3) | bytes(Y) | bytes(X) | bytes(Z)이며, Y=35, X=3, Z=2일때의 Hex 표현은 00000003000000000000000000000000000000000000000000000000000000000000002300000000000000000000000000000000000000000000000000000000000000030000000000000000000000000000000000000000000000000000000000000002 이다.
  • Full witness example
// witness 
var assignment cubic.Circuit 

assignment.X = 3 
assignment.Y = 35 
witness, _ := frontend.NewWitness(&assignment, ecc.BN254) 

// Binary marshalling 
data, err := witness.MarshalBinary() 

// JSON marshalling 
json, err := witness.MarshalJSON() 
... 
// recreate a witness 
witness, err := witness.New(ecc.BN254, ccs.GetSchema()) 
// note that schema is optional for binary encoding 
// Binary unmarshalling 
err := witness.UnmarshalBinary(data) 

// JSON unmarshalling 
err := witness.UnmarshalJSON(json) 
// extract the public part only 
publicWitness, _ := witness.Public()

Profile circuits

zk를 구현할 때 퍼포먼스 측면에서 constraints의 수를 최소화 시키는데, gnark/profile은 profiling files와 호환되는 pprof를 생성한다. 한번 .pprof 파일이 생성되면 이것은 go tool pprof를 통해서 visualizing 가능하다. Profile은 circuit 내에 포함된 constraint의 수도 측정 가능하다.

  • Usage
type Circuit struct {
    A frontend.Variable 
} 

func (circuit *Circuit) Define(api frontend.API) error {
    api.AssertIsEqual(api.Mul(circuit.A, circuit.A), circuit.A) 

    return nil 
} 

func Example() { 
    // default options generate gnark.pprof in current dir 
    // use pprof as usual (go tool pprof -http=:8080 gnark.pprof) to read the profile file 
    // overlapping profiles are allowed (define profiles inside Define or subfunction to profile 
    // part of the circuit only) 

    p := profile.Start() 
    _, _ = frontend.Compile(ecc.BN254.ScalarField(), r1cs.NewBuilder, &Circuit{}) 
    p.Stop() 

    fmt.Println(p.NbConstraints()) fmt.Println(p.Top()) 

    // Output: 
    // 2 
    // Showing nodes accounting for 2, 100% of 2 total 
    // flat flat% sum% cum cum% 
    // 1 50.00% 50.00% 2 100% profile_test.(*Circuit).Define profile/profile_test.go:17 
    // 1 50.00% 100% 1 50.00% r1cs.(*r1cs).AssertIsEqual frontend/cs/r1cs/api_assertions.go:37 
}

Validity of proof

ZK rollup을 실제로 gnark를 통해 적용되는 과정을 sequencial하게 확인해본다. 우선 예시의 circuit을 기준으로 확인한다.

type Circuit struct {  
  // SECRET INPUTS
  // ---------------------------------------------------------------------------------------------
  // list of accounts involved before update and their public keys  
  SenderAccountsBefore \[BatchSizeCircuit\]AccountConstraints  
  ReceiverAccountsBefore \[BatchSizeCircuit\]AccountConstraints  
  PublicKeysSender \[BatchSizeCircuit\]eddsa.PublicKey

  // list of accounts involved after update and their public keys  
  SenderAccountsAfter \[BatchSizeCircuit\]AccountConstraints  
  ReceiverAccountsAfter \[BatchSizeCircuit\]AccountConstraints  
  PublicKeysReceiver \[BatchSizeCircuit\]eddsa.PublicKey

  // list of transactions  
  Transfers \[BatchSizeCircuit\]TransferConstraints

  // list of proofs corresponding to sender and receiver accounts  
  MerkleProofReceiverBefore \[BatchSizeCircuit\]merkle.MerkleProof  
  MerkleProofReceiverAfter \[BatchSizeCircuit\]merkle.MerkleProof  
  MerkleProofSenderBefore \[BatchSizeCircuit\]merkle.MerkleProof  
  MerkleProofSenderAfter \[BatchSizeCircuit\]merkle.MerkleProof  
  LeafReceiver \[BatchSizeCircuit\]frontend.Variable  
  LeafSender \[BatchSizeCircuit\]frontend.Variable

  // ---------------------------------------------------------------------------------------------  
  // PUBLIC INPUTS

  // list of root hashes  
  RootHashesBefore \[BatchSizeCircuit\]frontend.Variable `gnark:",public"`  
  RootHashesAfter \[BatchSizeCircuit\]frontend.Variable `gnark:",public"`
}

해당 Circuit을 처리하기 위해 정의된 define 함수는 아래와 같다.

func (circuit \*Circuit) Define(api frontend.API) error {

  if err := circuit.postInit(api); err != nil {  
      return err      
  }

  // hash function for the merkle proof and the eddsa signature  
  hFunc, err := mimc.NewMiMC(api)  
  if err != nil {  
      return err  
  }

  // verifications of:  
  // - Merkle proofs of the accounts  
  // - the signatures  
  // - accounts' balance consistency  
  for i := 0; i < BatchSizeCircuit; i++ {

    // the root hashes of the Merkle path must match the public ones given in the circuit
    api.AssertIsEqual(circuit.RootHashesBefore[i], circuit.MerkleProofReceiverBefore[i].RootHash)
    api.AssertIsEqual(circuit.RootHashesBefore[i], circuit.MerkleProofSenderBefore[i].RootHash)
    api.AssertIsEqual(circuit.RootHashesAfter[i], circuit.MerkleProofReceiverAfter[i].RootHash)
    api.AssertIsEqual(circuit.RootHashesAfter[i], circuit.MerkleProofSenderAfter[i].RootHash)

    // the leafs of the Merkle proofs must match the index of the accounts
    api.AssertIsEqual(circuit.ReceiverAccountsBefore[i].Index, circuit.LeafReceiver[i])
    api.AssertIsEqual(circuit.ReceiverAccountsAfter[i].Index, circuit.LeafReceiver[i])
    api.AssertIsEqual(circuit.SenderAccountsBefore[i].Index, circuit.LeafSender[i])
    api.AssertIsEqual(circuit.SenderAccountsAfter[i].Index, circuit.LeafSender[i])

    // verify the inclusion proofs
    circuit.MerkleProofReceiverBefore[i].VerifyProof(api, &hFunc, circuit.LeafReceiver[i])
    circuit.MerkleProofSenderBefore[i].VerifyProof(api, &hFunc, circuit.LeafSender[i])
    circuit.MerkleProofReceiverAfter[i].VerifyProof(api, &hFunc, circuit.LeafReceiver[i])
    circuit.MerkleProofSenderAfter[i].VerifyProof(api, &hFunc, circuit.LeafSender[i])

    // verify the transaction transfer
    err := verifyTransferSignature(api, circuit.Transfers[i], hFunc)
    if err != nil {
        return err
    }

    // update the accounts
    verifyAccountUpdated(api, circuit.SenderAccountsBefore[i], circuit.ReceiverAccountsBefore[i],     circuit.SenderAccountsAfter[i], circuit.ReceiverAccountsAfter[i], circuit.Transfers[i].Amount)

  }

return nil
}

위에서 라이브러리 상에 존재하지 않고 선언된 struct인 AccountConstraints와 TransferConstraints는 아래와 같다.

// AccountConstraints accounts encoded as constraints  
type AccountConstraints struct {  
  Index frontend.Variable // index in the tree  
  Nonce frontend.Variable // nb transactions done so far from this account  
  Balance frontend.Variable  
  PubKey eddsa.PublicKey `gnark:"-"`  
}

// TransferConstraints transfer encoded as constraints  
type TransferConstraints struct {  
  Amount frontend.Variable  
  Nonce frontend.Variable `gnark:"-"`  
  SenderPubKey eddsa.PublicKey `gnark:"-"`  
  ReceiverPubKey eddsa.PublicKey `gnark:"-"`  
  Signature eddsa.Signature  
}

이 예제를 통해 zk rollup에 필요한 proof가 포함해야하는 data가 어떠한 형식으로 포함이 되어있는지 확인한다.

Proof creation

ZK rollup node에 충분한 tx가 있으면 batch로 모으고, circuit에 대한 입력을 compile하여 zk proof를 생성한다. 이 때 proof에 포함되어야 하는 데이터는 아래와 같다.

1. 배치의 모든 tx를 구성하는 merkle tree
2. tx들이 배치안에 포함되어 있다는 것을 증명하는 merkle proof
3. account들이 rollup state tree의 일부분이라는 것을 증명하기 위해 tx의 sender-receiver pair에 대한 merkle proof
4. 각 tx가 state update를 적용한 후 state root update에서 파생된 중간 root set(=sender의 balance 감소 및 receiver의 balance 증가)

이 값들이 어떻게 circuit내에서 표현될 수 있는지 확인해본다.

  • check 1.
    Batch에 첫번째로 포함된 transaction을 예로 보자. Sender의 tree index를 0으로 설정하고 recevier의 tree index를 1로 설정한다 가정한다. 이 때 Circuit내의 LeafSender, LearReceiver의 index를 각각 0과 1로 입력해야 한다.

MerkleProofReceiverBefore를 예로 보자. gnark의 경우 merkle.MerkleProof struct가 존재한다.

// MerkleProof stores the path, the root hash and an helper for the Merkle proof.  
type MerkleProof struct {

  // RootHash root of the Merkle tree  
  RootHash frontend.Variable

  // Path path of the Merkle proof  
  Path \[\]frontend.Variable
}

이 MerkleProof.Path에 tree의 path를 설정가능하다. 아래와 같이 path의 크기를 이진 tree의 depth로 make한다. 예를 들어, batch로 모인 tx들에 16 account의 sender/receiver가 존재한다면(8개의 transaction) 이진 merkle tree의 depth는 4(log_2 16)이다.

depth := 5 // 4 + 1

circuit.MerkleProofReceiverBefore\[i\].Path = make(\[\]frontend.Variable, depth)

gnark-crypto의 BuildReaderProof 함수에서 생성되는 proofSet으로 proof를 생성한 뒤 위 path에 적용하여 witness를 생성할 수 있다.

  func BuildReaderProof(r io.Reader, h hash.Hash, segmentSize int, index uint64) (root \[\]byte, proofSet \[\]\[\]byte, numLeaves uint64, err error) {  
  tree := New(h)  
  err = tree.SetIndex(index)  
  if err != nil {  
  // This code should be unreachable - SetIndex will only return an error  
  // if the tree is not empty, and yet the tree should be empty at this  
  // point.  
      panic(err)  
  }  
  err = tree.ReadAll(r, segmentSize)  
  if err != nil {  
      return  
  }  
  root, proofSet, \_, numLeaves = tree.Prove()  
  if len(proofSet) == 0 {  
  err = errors.New("index was not reached while creating proof")  
      return  
  }  
  return  
}
  • check 2.
    Circuit내의 Transfers와 실제 send-receive 과정 시 발생한 state 변화값이 circuit내에 등록됨으로써 tx가 batch내에 포함되어 있다는 것을 증명한다.
  • check 3.
    Sender, receiver pair에 대한 merkle proof는 Circuit struct 내에서 before와 after로 구분되어 있으며, 명시적으로 확인할 수 있다.
  • check 4.
    Circuit 내의 이전 root hash, 현재 root hash가 포함이 되어 있고, 이 파라미터들은 gnark:",public"으로, verifier가 실제로 확인할 수 있는 데이터이다.

Conclusion

다수의 블록체인 플랫폼이 go로 구현되어 있어서, go 라이브러리인 gnark가 zk rollup을 구현할 시에 편리할 것이라 판단되어, 실제로 gnark를 이용해 간단한 zk rollup 기능을 구현해 보고자 분석한 글이었다. ZKP를 이해 했어도, 이것을 실제로 roll up 형태를 구현하는 것은 또다른 문제인 것 같다. 다음글에서는 조금 더 세부적인 gnark 라이브러리 분석과 proof creation에 이어 proof verification을 진행 할 시 gnark에서 어떻게 처리하는지 확인해보도록 할것이다.

참고
https://ethereum.org/en/developers/docs/scaling/zk-rollups/
https://github.com/ConsenSys/gnark
https://docs.gnark.consensys.net/

728x90
반응형
저작자표시

'Blockchain > Roll up' 카테고리의 다른 글

ZK rollup - 4. zk-SNARK의 Circuit & QAP  (0) 2023.09.21
ZK rollup - 3. zkEVM 프로젝트  (0) 2023.09.21
ZK rollup - 2. ZKP  (0) 2023.06.15
Rollup의 개념과 특성  (0) 2023.06.14

티스토리툴바