ZKFixedPointChip

ZK Fixed Point Arithmetic with its Application in Machine Learning based on Halo2 & Axiom's Halo2-base.

Features

• FixedPointChip: Fixed point arithmetic and math library
  • Support different kinds of precisions (from 32.32 to 63.63) with automatically generated polynomial using Remez algorithm
  • Support negative number arithmetics with quantization
  • Support functions: add, sub, mul, div, mod, sign, clip, polynomial, bit_xor, sum, neg, exp, log, pow, sqrt, max, sin, cos, tan, sinh, cosh, etc.
• ZK-LR: LinearRegressionChip/LogisticRegressionChip
  • Support inference with vector multiplication and sigmoid (based on exp) using FixedPointChip
  • Support training with gradient descent algorithm
• ZK-DT: DecisionTreeChip
  • Support inference with tree traversal over the decision tree
  • Support training by building the decision tree recursively with the calculated Gini Impurity in each node

Setup

Install rust:

curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

Clone this repo:

git clone https://github.com/DCMMC/ZKFixedPointChip.git
cd ZKFixedPointChip

Build & Run Examples

Fixed Point Arithmetic (exp2, log2, sin):

cargo run --example fixed_point

Linear Regression (Inference & Training):

cargo run --example linear_regression

Logistic Regression (Inference & Training):

cargo run --example logistic_regression

Decision Tree (Inference & Training):

cargo run --example decision_tree

For visualizing, you should install graphviz and the generated svg file is located in ./figure/dt.svg.

Benchmark

The complexity of decision tree training is proportional to $2^d$ where $d$ is the tree depth.

Decision Tree Visualization