Thread by @Hyunxukee

@Sin7Y_Labs 아티클로 알아보는 #zkEVM 연구 트렌드
#Plonk #Halo #Lookup_table #Custom_gate #Recursive_Proof

https://twitter.com/Hyunxukee/status/1549318624485462016

👇디테일은 스레드에서 확인!

[Lookup table]
- 증명자가 table에 witness value가 존재한다고 주장할 수 있도록 미리 만들어 놓은 값. zkEVM에서 증명을 만들때 이 table에서 값을 가져와 연산의 정확성을 증명함
- 대표적인 솔루션: Plookup, Halo2 Lookup table
- Halo2를 사용하면 Plookup보다 universality가 높음

[Lookup table 참고 자료 @Sin7Y_Labs]
1) sin7y.org/plookup-an-alg…
2) hackmd.io/@sin7y/ByHDJPf…
3) hackmd.io/@sin7y/ryDJ-Yx…
4) hackmd.io/@sin7y/HysLzbU…

[Custom gate]
- circuit의 gate 수를 줄이고 설계의 유연성을 높이는 방법
- 일반 계산을 TinyRam에만 구현하는 것은 어렵기 때문에 계산의 간소화를 위해 custom gate를 채택
대표적인 솔루션
- turboPlonk: custom gate + Plonk
- UltraPlink: custom gate + Plonk + Lookup table

[Custom gate 참고자료 @Sin7Y_Labs]
hackmd.io/@sin7y/HkGORu6…

[Combined selector]
- zkEVM circuit을 설계할 때는 많은 custom gate를 정의해야하기 때문에 binary selector가 많이 도입됨
- Selector가 불필요하게 많이 있으면 증명 생성과 검증에 비용이 많이 발생하기 때문에, combined selector로 selector polynomial을 최적화시키는 방법을 고안해야함

[Combined selector 참고자료 @Sin7Y_Labs]
hackmd.io/@sin7y/H10EO2Z…

[Recursive Proof]
- zkp에서 recursion이란, Relation (circuit) 안에서 이전에 생성된 proof를 verify하는 코드를 포함하는 것을 의미
- 10개의 트랜잭션을 검증하기 위해서는 10개의 증명 생성과 10번의 검증이 필요
- recursive는 10개의 증명을 한 개로 압축하기에, 한 번의 검증만 필요함

[Recursive Proof in Halo2]
- Halo는 circuit안에서 verify code를 효율적으로 수행할 수 있도록 설계된 알고리즘
- Halo는 recursion의 모든 step에서 verify code를 매번 실행하지 않고, 마지막 step에서 한 번만 실행
- 이를 위해 모든 step에서 원래 검증해야했던 이전 proof를 accumulate함

[Recursive Proof in Halo2 참고자료 @Sin7Y_Labs]
hackmd.io/@sin7y/SJQpj9F…

[Others @Sin7Y_Labs]
Plonk
- hackmd.io/@sin7y/ByYZfpn…
- hackmd.io/@sin7y/rkbZn9d…
STARK
- hackmd.io/@sin7y/Hktwgoe…
- hackmd.io/@sin7y/HkIELMU…
- hackmd.io/@sin7y/r1r0IE4…
- hackmd.io/@sin7y/ry377Vp…