search

kroma-network / tachyon

Modular ZK(Zero Knowledge) backend accelerated by GPU
MIT License
7.78k stars 226 forks source link

feat: implement LogUp scheme #420

Closed Insun35 closed 1 month ago

Insun35 commented 2 months ago

Implement logarithmic derivative lookup scheme. Logarithmic derivatives translate products of linear factors into sums of their reciprocals, turning zeroes into simple poles of same multiplicity. It reduces computation cost using grand sum argument instead of grand product argument. See Paper 2022/1530

Referenced Scroll Halo2 implementation. We named Logup not MVLookup because this implementation uses univariate polynomial commitment scheme.

chokobole commented 1 month ago

Please remove this statement from the commit body of feat(zk): add constraint_system lookup logic for LookupsMap

Also add kInvalid type to avoid using Lookup() and LookupAny() without setting a lookup type.

chokobole commented 1 month ago

Please add links to the rust reference code to every single commit!

chokobole commented 1 month ago

You need to add license of Geometry Research. Does Scroll take this code from here, right?

chokobole commented 1 month ago

Please change the type of fix(zk): fix wrong iterator access, feat(zk): add circuit test flags for LogUp and feat(zk): implement MultiLookupCircuit to test

TomTaehoonKim commented 1 month ago

@Insun35 Could you fix typo in 98aa037's commit body? "Constraint system select" -> "Constraint system selects"

Insun35 commented 1 month ago

You need to add license of Geometry Research. Does Scroll take this code from here, right?

Yep, but Geometry didn't explicit their license so I'll add the Scrolls license.