zk bootcamp from encoda
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
- Montgomery 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
-
zkSNARKS = Succint Non interactive ARgument of Knowledge
-
C(Circit?): generate a proving key(pk) and a verification key(vk) by taking a secret parameters lambda
-
P(Prover): generate proof (pr=P(pk,x,w)) with public input(x) and private witness(w)
-
V(Verifier): V(vk,x,pr) rerutns teue uf hte proof(pr) is correct
-
→C(x,w)=true
-
Math
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で、b
public 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
比較
- snark : small proof size, but need to have trusted setupte
- stark : large proof size, but no trusted setup
- crypto assumption, post-quantum, trusted setup あたりで違いが出る
- Sigma protocol
use cases
- An Efficient Design and Implementation of a Secure Neural Network Verification System Using zkSNARKs
- ZKR
- process
- L3回りの話もう一回聞く(tendermint使ってる?)
- Filecoin
- ストレージの存在証明の仕組み
- Proof of Replication : マイナーがデータと公開鍵を保存する、一番最初のみ
- Proof of Spacetime : 指定の期間にデータか保存されていたかの確認
- 10のsnaarkをもとに定期的にオンチェーンで検証される
- (◯)https://research.protocol.ai/sites/snarks/
- ストレージの存在証明の仕組み
- tornado cash
- secretとともにdpositして、そのsecretと持っているproofを作成してwithdraw
- Zero Knowledge Lottery based on Tornado Cash
- dark forest
- 侵略ゲーム
- 移動する際に位置情報のハッシュ値をオンチェーンに登録
- ただ、ハッシュ値が不正な可能性がある(存在しない位置のハッシュ値など)ためproofを作成して検証し、移動を確定させている
- ING : KYC
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>
- Variable
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に慣れる
実行はrustのplaygroundを使うのが楽
Day 5 : Cairo
StarkNet orverview
- StarkNet’s Architecture Review
- Transaction types
- Block structure
Recursive STARKS
- https://medium.com/starkware/recursive-starks-78f8dd401025
- SHARP (The shared prover)では、ある程度txが溜まってからproofを作成していた
- Recursive proofでは、並列でproofを生成し、proofのペアからさらにproofを生成する
- 早く、安くなる
Rust intro 2
-
- 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
- zkSnarks,
-
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
- 実際に見てみると面白い
- https://zcashblockexplorer.com/
-
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
- c = Commit(m, r) / m = given a message, r = randomness
- nulifier
- note
- transaction
- この辺はあまり理解できなかったので要復習
- nulifierを追加することにより、匿名を担保している
- UTXO
-
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
- note has two public info
-
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 {}
- if
- Noir Library
- いろんなCryptographic functions
- Field function
- ACIR (Abstruct Circuit Intermediate Representation)
- Noir compiler
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()
- use
-
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
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から選ばれた人
- block producer
- Consensus
- Ouroboros PoS
- stakeに応じてランダムで選ばれる
- Ouroboros PoS
- 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の生成
- Proof of Efficiency
- 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
-
- Lagrange Interplation
Polynomial Commitment
**SNARK Process **
参考資料
-
Shielded Transactions
https://docs.google.com/presentation/d/1qsOtMLiBVhVMbeB_R0heTSMRsKnhuOKfhACFiXKM-J0/edit?usp=sharing -
Ethworks Reports : Zero-Knowledge Blockchain Scalability
https://ethworks.io/assets/download/zero-knowledge-blockchain-scaling-ethworks.pdf
Discussion