---
# System prepended metadata

title: Efficient Pedersen Hash Construction in PLONK

---

# 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)