Zenn
🏕️

zk bootcamp from encoda

2023/04/29に公開
Rust
#
zk
#
snark
#
stark
#
cairo
tech

Day1 : Math & Cryptography

zkpを理解する上で必要な数学的知識

  • Modular Arithmetic （合同算術）
  • Group Theory （群論）
    • inverse / Equivalence classes
    • Fields （体）
    • group homomorphisms （群準同型）
  • Polynomial Arithmetic （多項式）
    • roots

Cryptographyの基礎知識

  • Hash functions
  • Symmetric / Asymmetric Encryption
  • Elliptic Curves
    • Montgomery Curves
      • Diffie–Hellman (ECDH) key agreement scheme
    • Edwards Curves
  • Verifiable Random Functions

ZKPの概要をさらっと

Day2 : zkSNARK

  • (Fully) Homomorphic Encryption : 完全準同型暗号
    • Bitcoin split-key vanity mining
    • 例えばAliceが (a: provate key, A: public key)とBobが(b,B)を持っていたら、privateKey(a + b) から public key (A + B)を使える
  • Big O notation
    • describe complexity

zkSNARKS

Trusted stup and Toxic waste

  • the secret parameter lambda を知っている人は、V(vk,x,pr)がtrueになる虚偽のproofを生成することが可能
    • fake proofを作成できるだけで、private inputはわからない
  • the secret parameter lambdaはtrusted setupと呼ばれ、この問題のことをtoxic wasteという
  • 解決としてMPCなどがある
    • 例) ZCash
    • Hola2はtrusted setupはいらない（Minaで使われてる）

Zokrates
toolbox for zkSNARKs
zokratesを利用したprivate inputの証明は下記手順で行えます。実際やるとより理解が深まります。

  • RemixのpluginからZokratesをインストール
  • main.zokでファイルを作成
  • 下記コードをコピペ
    • aがprivate inputで、bpublic inputになります
def main(private field a, field b) {
    assert(a * a == b);
    return;
}
  • Compile
  • Compute: a * a = bが成り立つように引数を入れてください
  • Setup : ここでtrusted setupしています
  • Generate proof : 作成後verifier inputsをコピー
  • Export verifier : ここでproof検証用のsolidityのコードが生成されます
  • 上記で生成されたverifier.solをdeploy
  • verifyTx()にコピーしたproofをペーストして実行
  • proofが正しければ成功！

Day3 : ZKP Use cases

比較

use cases

Day 4 : Starknet and rust

StarkNet

  • Starknet
    • StarknetCore, FactRegistry depolyed on L1
    • Sequencer send state diff to StraknetCore, and Prover send proof to FactRegstry contract throught Verifier
  • Cairo 1 (from starknet v0.11.0)
    • Caito1 → Sierra → CASM
    • Cairo program vs Cairo cotract

rust

  • core

    • Memory safety
    • Concurrency

  • rustを書く際に注意した方がいいもの

    • Variable
      • let x = 1; let mut x = 1; (mut means mutable)
    • Data type : https://doc.rust-lang.org/book/ch03-02-data-types.html
      • integers
      • u8, i32, u64
    • （◯）char
    • （◯）usize
    • Compound Types
      • Tuple
      • Struct
      • Collection
    • String vs str
    • Control flow
      • numericをboolに自動変換できない
    • Option
      • 返り値がわからない場合
      • Option<T>
      • enum Result<T, E>
enum Result<T, E> {
	Ok(T),
	Err(E),
}

- match

 enum Coin {
    Penny,
    Nickel,
    Dime,
    Quarter,
}
fn value_in_cents(coin: Coin) -> u8 {
    match coin {
        Coin::Penny => 1,
        Coin::Nickel => 5,
        Coin::Dime => 10,
        Coin::Quarter => 25,
    }
}

Cargo

  • package manager
  • compile and build

hoework
このリポジトリのコードを修正してrustに慣れる
https://github.com/ExtropyIO/ZeroKnowledgeBootcamp/tree/main/rust/homeworks/homework4

実行はrustのplaygroundを使うのが楽
https://play.rust-lang.org/?version=stable&mode=debug&edition=2021

Day 5 : Cairo

StarkNet orverview

Recursive STARKS

Rust intro 2

  • Ownership

    • Copying
    • Move
let a = vec![1,2,3];
let b = a;
let c = a; // ownershipがbに移動してるので、aからcに移動させることできない
  • References
  • Traits

** Differences between Cairo and Rust**

  • Loops
loop {
	counter += 1
	if (counter == 5){}
}
  • Collections
  • Shadowing
let x = 5;
{
	let x = x *2;
}
  • Data types
  • Type conversion
let origin = 5;
let a: u8 = origin.try_into().unswap();
let b: felt252 = a.into();

Tools

  • Protostar

Day 6 : ZCash & Aztec

ZCash

  • Decentralized Anonymous Payment schema

    • zkSnarks, Equihash memory-hard proof-of-work algorithm

  • Tx type : publicとprivateのvalue、どちらも使うことができる

    • Public : sender & receiver が public
    • Shielding : senderはpublic, receiverはprivate
    • De-shielding : senderはprivate, receiverはpublic
    • Private : sender & receiver が private

  • explorer

  • Address type

    • start with "t": public address
    • start with "z" "zc" "zs": private address

  • History

    • Using MPC to solve the toxic waste problem
    • Ceremony happend in 2012, 2018
    • Security Problem in 2018

  • ZCash design

    • UTXO
      • Alice has note1 : (ska) → Note1
      • Alice to Bob: (ska) cancel Note1 →　(skb) Note1
      • add a random value r as an Id to Note
      • store a hash of value, not sorting
    • commitment
      • c = Commit(m, r) / m = given a message, r = randomness
        • binding and hiding
    • nulifier
    • note
    • transaction
      • この辺はあまり理解できなかったので要復習
      • nulifierを追加することにより、匿名を担保している

  • Cryptography

    • Vesta for proof system, and Pallas for the application circut

Bulletproofs

  • short proof, no trusted setup
  • use case
    • range proof, Mercle proofs, Proof of Sollvency

Monero

  • 仕組み後で調べる

TornadoCash

  • 概要理解できてるので割愛

Aztec

  • Privacy: all aspects of transaction remain hidden from the public or third party

  • Confidentiality: the inputs and outputs of a transaction are hidden from the public but the transaction parties remain public

  • Anonymity: the input and output of a transaction are public but the transaction graph is obscured from one transaction to the next, preventing the identification of the transaction parties.

  • note

    • note has two public info
      • AZTEC commitment: an encrypted representation of how much value the note holder
      • an ethereum address of note's owner
    • private info
      • the value of note
      • the note's viewing key

  • Anonymity, Accounts, Account Registration, Account Alias, Data structure

    • 後ほど復習

zk.money

Aztec connect

Day 7 : Noir, Cairo

Noir

  • domain specific language for creating and verifying proof.

Language

  • Private & Public
fun main(x: field, y: pub Field) {}
  • Mutation
let mut y = 2;
  • Primitive type
    • Field
    • Integer
    • Boolean
    • String: str<N> fixed size / constrain / std::pintIn()
fn main(x: Field) {}
fn main() { let t = true; }
  • Conpound type
let arr: [Field: 2] = [x, y] //array
let tup: (u8, Field) = (1,2) //tuple
struct Animal {hand: Field, head: Field};
  • Comptime value
let a: comptime Field = 5;
let a  = 5;
  • Global variable
global N: Field = 10;
let x = N;
  • function
fn foo(x: Field) -> Field { x }
  • loops
for i in 0..10 {}

Day 8 : Cairo

  • default stateless,
#[contract]
mod StarknetContract {
	struct {
		balance: felt,
	}
	
	#[external]
	fn increase_balance(amoount: felt) {
		balance::write(balance::read() + amount);
	}
	
	#[view]
	fn get_balance() ->  felt {
		balance::read()
	}
}

Decorators

  • #[contract]

  • #[event]

  • function

    • #[external]
    • #[view]
    • #[constructor]

  • Storing data

    • use Storage struct
      • storage::read(), storage::write()

  • importing another contract

    • use starknet::get_caller_address;

  • contract class

    • we need to deploy contract interface to make third party call the depolyed contract

AA

Starknet JS

// install

// Provider get-starknetを使うと良い
const provider = new starknet.Provider({
	sequencer: { network: 'mainnet-alpha' }
})

// deploy contract
provider.deployContract(payload [ , abi ]) => _Promise
	
// call contract
provider.callContract(call [, blockIdentifier]) => _Promise
 - call object : call.contractAddress, call.entrypoint, call.calldata

// wait for tx
provider.waitForTransaction(txHash [ , retryInterval]) => Promise < void >

// signer api
const privateKey = stark.randomAddress();
const starkKeyPair = ec.genKeyPair(privateKey);
const starkKeyPub = ec.getStarkKey(starkKeyPair);

// accout methods
const account  = new starknet.Account(Provider, address, starkKeyPair)
account.getNonce() => Promise
account.estimateFee(calls [ , options ]) => _Promise
account.execute(calls [ , abi , transactionsDetail ]) => _Promise
account.signMessage(typedData) => _Promise
account.hashMessage(typedData) => _Promise
account.verifyMessageHash(hash, signature) => _Promise
account.verifyMessage(typedData, signature) => _Promise

// contract
new starknet.Contract(abi, address, providerOrAccount)
contract.attach(address)` _for changing the address of the connected contract_
contract.connect(providerOrAccount)` _for changing the provider or account_
// view
contract.METHOS_NAME(...args [ , overrides ]) => Promise<Result>
	overrides.blockIdentifier
// write
contract.METHOS_NAME(...args [ , overrides ]) => Promise<AddTransactionResponse>	
// almost same as ethers.js or web3.js

Example
https://github.com/0xs34n/starknet.js-workshop
https://medium.com/@darlingtonnnam/an-in-depth-guide-to-getting-started-with-starknet-js-a55c04d0ccb7

WARP

  • transpile Solidity contract into Cairo

Day 9 : Mina

overview

  • Mina blockchain
    • succinct blockchain
    • about 22kb, fixed size
  • roles
    • block producer
      • snark producerを選べる
    • snark producer
      • sell profs to block producer
    • professional producer
      • poolから選ばれた人
  • Consensus
    • Ouroboros PoS
      • stakeに応じてランダムで選ばれる
  • recursive
    • proofのproofを作成する
    • 最新のproofと過去のblockのproofがあれば良い

zkApps

  • pass state update + proof to validator
  • varidator vefiry proof and update state on-chain

zkApp use case

  • Privcy enabled app
  • Power enterprise interoperability
  • Minimise transaction fee
  • Power secure & fait finance servises
  • Enable private & auditable election
  • Access money from anywhere in the world

zkBridge

  • MinaのstateをETHで検証

How Mina create proof

  • Pickles
    • core zk-SNARK, developer toolkit
  • Kimuchi
    • create proof without trusted setup

SnarkyJS
SnarkyJS is a TS library for writing smart contracts for the Mina Protocol.

Day 10 : zkEVM

zkEVM solition

  • AppliedZKP zkEVM
    • State Proof : used to check the state transaction
    • EVM proof : used to check the opecode correctness.
  • design challanges
    • EVM is stack based, not register bases
    • EVM has a 256 bit
    • EVM storage ises keccak and MPT (not zkp friendly)

zkEVM types

  • Compatibility x Performance

zkSync

  • 3 unique
    • AA
    • LLVm compiler
    • Future Proof
  • Hyperscaling
    • Base chain (zkSync Era) = settlement layer for hyperchais(L3)
  • DA
    • zkSync common state root contains zkRollup root and zkPorter root
    • same as shared sequencer??
    • zkPorter : off-chain DA / secured by the supermajority of validators' stake
  • infrastructure
    • full node
    • Prover
    • Interactor
    • Paranoid Monitor

Polygon

  • polygon zero
    • recrusive proofs to solve generating proof problems (Plonky2)
    • generate proofs simultaneously for every tx and aggregate into a single proof
  • Polygon Hermez
    • Proof of Efficiency
      • Sequenrer : blockの生成、maticをaggregatorに送る
      • Aggregator : proofの生成
  • Polygon Miden
    • STARK-based ZK rollup with EVM compatibility
    • 5,000 txs in single block, block produced every 5 sec = 1000tps
  • Polygon Nightfall
    • EY
    • OR for scalability & ZK for provacy
  • Polygon zkEVM
    • ごく単純な説明

Polynomial Identity Language

Scroll

  • Components
    • Sequencer : provide RPC, accept tx and generate block
    • Coordinator :
    • Roller :

Day 11 : Risc Zero / Plonk

Risc zero

  • zkVM

Bonsai

  • flexible zkVM
  • seamlessly connects to any smart contract or chain
  • universal rollup

ZKSnark process

  • transformaion
    • Computation
    • Algebraic Circuit
    • P1CS

Plonkish Prtocol

  • Plookup
    • range proof

Plonky2

Day 12 : Circom / SNARK theory

  • Signal??
  • Template and components :

Circom -> Cairo

Polynomial Introduction

  • polynomial can contain unbounded amount and info
  • add, multiply and divide
  • root
    • P(r) = 0 / A = BC

  • Schwartz - Zoppel Lemma

  • Lagrange Interplation

Polynomial Commitment

**SNARK Process **

参考資料

Discussion