---
# System prepended metadata

title: Functional commitments on top of arkworks

---

---
title: 'Functional commitments on top of arkworks'
disqus: hackmd
---

Functional commitments on top of arkworks
===

We implemented set of libraries: AC2tFT compiler, Proof of functional relation and index private marlin on top of arkworks. We also used ark-marlin as our baseline and introduced necessary changes in order to derive index private version of it. 

Before we publish the library with accompanying blogposts and some ideas of potential applications we would like to note a few slight changes regarding specific ark-marlin implementation and potentially a small mistake we found in the paper. 

We'll keep this as short as possible, but we are more than happy to have more in depth conversations if needed. 

### ark-marlin changes 

#### Strictly upper triangular matrices
Fractal introduced matrix transposition for reducing one round in the protocol. We use the same optimization in our implementation and thus we prove that matrices $A$ and $B$ are strictly upper triangular instead of strictly lower triangular. This is in relation to claim 6.7 in the Fractal paper.

#### Remove joint arithmetization

Joint arith $row$ and $col$ polynomials can't be used anymore. We have $(row_i, col_i, val_i)$ for each matrix for which we can prove functional relation.

#### No reindexing
In the paper low degree extension of instance polynomial, $\hat{x}(X)$, is defined over first $|x|$ roots of unity, $H[\leq|x|]$. In order to use power of FFTs ark-marlin implementation introduces domain "reindexing" and smooth $domain\_x$ for handling public inputs. 
Reindexing affects: 1. [$w$ poly calculation](https://github.com/arkworks-rs/marlin/blob/026b73c20638f4f86cbae0946045934c865d5a30/src/ahp/prover.rs#L340), 2. [$t$ poly calculation](https://github.com/arkworks-rs/marlin/blob/026b73c20638f4f86cbae0946045934c865d5a30/src/ahp/prover.rs#L422) and the most important part: 3. [matrix artithmetization](https://github.com/arkworks-rs/marlin/blob/026b73c20638f4f86cbae0946045934c865d5a30/src/ahp/constraint_systems.rs#L180). This is indeed useful trick but reindexing in matrix arithmetization violates the diagonality and lower triangularity properties we need for proof of functional relation, that's why we simply do not use reindexing, and we instead compute the polynomial on the $H[\leq|x|]$ without using FFTs.

#### No witness shifting 
Although there is no reindexing we still need to commit to shifted witness polynomial which verifier uses for querying $\hat{z}(X)$. Since we must introduce one more Zero over K check for testing outputs we recommend using directly $\hat{z}(X)$ in Marlin and then proving its well formation ($(x, w, y)$) in batched Zero over K check which will be explained in more details in the coming section. 


### Updated zero over K

For the assignment $z = (x, (w, y))$ and its low degree extension $\hat{z}(X)$ we have to check that first $|x|$ evals match public inputs and that last $|y|$ evals match outputs. 

Given that, we check Zero over K for: 

$$(\overline{z} - \hat{x})v_H[>|x|] + \alpha * (\overline{z} - \hat{y})v_H[\leq|H| - |y|]$$

- $\alpha$ is random challenge 
- $\overline{z}$ is blinded $\hat{z}$

#### Note for checking outputs
Unless we are making huge mistake, check $\overline{w} *v_H[\leq|H| - |y|] - \hat{y}$ from the paper should be $(\overline{w} - \hat{y})v_H[\leq|H| - |y|]$


$$A=\{(r,c): (r,c)\in\mathbb{N}\times\mathbb{N}\text{in A}\}$$
$$B=\{(r,c): (r,c)\in\mathbb{N}\times\mathbb{N}\}\text{in B}$$
$$S=A\cup B$$
$$A\setminus B$$