# Efficient Pedersen Hash Construction in PLONK

Author: Shumo Chu and Tom Shen
(Thanks comments from Luke Pearson and Zhenfei Zhang)

Despite looks "simple", construct Pedersen Hash naively can result in a lot of constraint count. Now, we show how can we optimize the number of constraints of Pedersen Hash both in R1CS and using PLONK gates.

## Pedersen Hash

Let $M$ be a bit sequence.The *Pedersen hash* function of $M$ on a group formed by a set ellitpic curve points $\mathbb{G}$ can be defined as follows:

* Let $P_0, P_1, \ldots, P_l$ be $l+1$ **indedependently** and **randombly** sampled generators from $\mathbb{G}$
* Split $M$ into $200$ bits (assuming $|\mathbb{G}|\approx2^{256}$) blocks ($M_0, M_1, \ldots M_l$) and each block into chunks of $4$ bits ($m_0, m_1, \ldots m_k$):
$$M = M_0 || M_1 || \ldots || M_l$$
where:
$$M_i = m_0 || m_1 || \ldots || m_{49}$$
Each $m_j$ term is a chuck of $4$ bits $[b_0\;b_1\;b_2\;b_3]$. We define:
$$enc(m_j) = (2 b_3 - 1 ) \cdot (1 + b_0 + 2b_1 + 4b_2)$$

and let:
$$\langle M \rangle = \sum_{j=0}^{49}enc(m_j)\cdot 2^{5j} $$

Now we can define Pedersen hash of $M$ as:
$$ H(M) = \sum_{i=0}^{l} \langle M_i \rangle \cdot P_i$$

Note that the expression above is a linear combination of elements of $\mathbb{G}$, thus itself is also an element of $\mathbb{G}$, i.e. a point in the elliptic curve.

## Efficient Construction of Pedersen Hash in Constraint Systems

### Baseline: Construct Pedersen Hash using Lookup Tables

How can we construct Pedersen Hash using less number of constraints? A basic technique is for each 4 bit chunk, we can build a look up table for the first 3 bits ($[b_0\;b_1\;b_2]$) $f(b_0, b_1, b_2) = (1 + b_0 + 2b_1 + 4b_2) \cdot 2^{5j} \cdot P_i$ and view the last bit $b_3$ as the conditional select bit. Below is the look up table (let $c_i = (i+ 1) \cdot 2^{5j} \cdot P_i(x)$):

| $b_2$ | $b_1$ | $b_0$ | $f(b_0, b_1, b_2)$ |
|-------|-------|-------|---------------------|
| 0 |0 | 0 | $c_0$ |
| 0 |0 | 1 | $c_1$ |
| 0 |1 | 0 | $c_2$ |
| 0 |1 | 1 | $c_3$ |
| 1 |0 | 0 | $c_4$ |
| 1 |0 | 1 | $c_5$ |
| 1 |1 | 0 | $c_6$ |
| 1 |1 | 1 | $c_7$ |

We can get a similar lookup table on $y$-axis, i.e. let $d_i = (i+ 1) \cdot 2^{5j} \cdot P_i(y)$ and replace $c_i$ with $d_i$.

### Arithmization in R1CS

Now, we want to embed this lookup table into the constraint system. It would be actually expensive to actually build a function with a big "switch" statement in the constraint systems. Now, we use a "arithmization" technique to convert the the look up table into constraints system as follows (assuming we are using R1CS in zkSNARK schemes like Groth16):

* $b_{10} = b_0 \cdot b_1$
*
$$
\begin{align}
out_x = & [(c_7 − c_6 − c_5 + c_4 − c_3 + c_2 + c_1 − c_0) \cdot b_{10} + (c_6 − c_4 − c_2 + c_0) \cdot b_1 \\
& + (c_5 − c_4 − c_1 + c_0) \cdot b_0 + (c_4 − c_0)] b_2 + (c_3 − c_2 − c_1 + c_0) \cdot b_{10} + (c_2 − c_0) \cdot b_1 \\
& + (c_1 − c_0) \cdot b_0 + c_0
\end{align}
$$
*
$$
\begin{align}
out_y = & [(d_7 − d_6 − d_5 + d_4 − d_3 + d_2 + d_1 − d_0) \cdot b_{10} + (d_6 − d_4 − d_2 + d_0) \cdot b_1 \\
& + (d_5 − d_4 − d_1 + d_0) \cdot b_0 + (d_4 − d_0)] b_2 + (d_3 − d_2 − d_1 + d_0) \cdot b_{10} + (d_2 − d_0) \cdot b_1 \\
& + (d_1 − d_0) \cdot b_0 + d_0
\end{align}
$$

TODO: show an example.

### Arithmization in PLONK

Now, how can we do this efficiently on Plonk? On one hand, the second and third R1CS constraints can not be easily expressed as a single gate in PLONK. On the other hand, PLONK provides us the opportunities with more powerful customized gates. For example, we can construct a **big_poly** gate as the following in PLONK:

$$ q_m \cdot (a \cdot b) + q_l \cdot a + q_r \cdot b + q_4 \cdot d + q_c + PI = c $$

where $q_i$ are constant, $a, b, c, d$ are variables, $PI$ is public input.

By purely using **big_poly**, we can express the constraints on $x$ axis as following:

*
$$
\begin{align}
out_1 = & (c_7 − c_6 − c_5 + c_4 − c_3 + c_2 + c_1 − c_0) \cdot (b_0 \cdot b_1) + (c_6 − c_4 − c_2 + c_0) \cdot b_1 \\
& + (c_5 − c_4 − c_1 + c_0) \cdot b_0 + (c_4 − c_0)
\end{align}
$$

* $$
out_2 = (c_3 − c_2 − c_1 + c_0) \cdot {b_1 \cdot b_0} + (c_2 − c_0) \cdot b_1 + (c_1 − c_0) \cdot b_0 + c_0
$$

* $$ out_x = out_1 \cdot b_2 + out_2 $$

Now we can derive $out_y$ similarly, and $b_3$ is used to conditionally negate the point. In details,
$$
\begin{split}
\text{neg_out}_x &= -1*out_x \\
\text{final_out}_x &= \text{cond_select}(b_3, neg\_out_x, out_x)\\
\text{final_out}_y &= out_y
\end{split}
$$

where generating $\text{neg_out}_x$ requires 1 constraint and $\text{cond_select}$ takes 1 constraint.

And $out_y$ can be computed in a similar manner.

For a $4$-bit chunk, the total constraint counts is: $8=3\cdot2+2(\text{used in conditional select})$

## Furthur Optimization with Width 5 Poly_Gate

If we have **big_poly** with width 5, i.e:

$$ q_m \cdot (a \cdot b) + q_l \cdot c + q_r \cdot d + q_4 \cdot e + q_c + PI = c $$
we can further improve the constraint count as follows:

* $b_{10} = b_0 \cdot b_1$
* $$
\begin{align}
out_1 = & (c_7 − c_6 − c_5 + c_4 − c_3 + c_2 + c_1 − c_0) \cdot b_{10} + (c_6 − c_4 − c_2 + c_0) \cdot b_1 \\
& + (c_5 − c_4 − c_1 + c_0) \cdot b_0 + (c_4 − c_0)
\end{align}
$$
* $$
\begin{align}
out_x = & out_1 \cdot b_2 + (c_3 − c_2 − c_1 + c_0) \cdot b_{10} + (c_2 − c_0) \cdot b_1 \\
& + (c_1 − c_0) \cdot b_0 + c_0
\end{align}$$

Since $b_{10}$ will be reused on both axis. We get $6=1 + 2\cdot2 + 1$ constraint per 4 bits.

## References
1. [Iden3 Pederden Hash Docuemnt](https://iden3-docs.readthedocs.io/en/latest/_downloads/4b929e0f96aef77b75bb5cfc0f832151/Pedersen-Hash.pdf)