# Rescue vs Poseidon

## Hash speed

- Rescue: 169.60 µs
- Poseidon: 8.7461 µs

Rescue is ~20ish times slower than Poseidon. This is consistent with [the paper](https://eprint.iacr.org/2019/458).

## Circuit size

| |Trivial Gate| Parallel Gate|
|---|---|---|
|Rescue | 24a + 72e | 24a + 24e|
|Poseidon | 74a + 90e | 74a + 74e  |
|improvement| 1~3x | 3x|

- a: cost for a `affine transform` gate
- e: cost for an `exponentiation` gate

# Detailed analysis

### Algorithms
Let $w$ be the width of hash function. The state of the hash is denoted by a vector $\left<h_1,\dots, h_w\right>$. Let $\alpha$ be the S-box parameter. I.e., for BN254 and BLS12-381 we have $\alpha= 5$ and for BLS12-377 we have $\alpha = 11$.

#### Poseidon's round iteration:
1. add round constant
    - add a round key to current vector
2. S-box
    - for a full round, compute $\left<h_1^\alpha, h_2^\alpha,\dots, h_w^\alpha\right>$
    - for a partial round, compute $\left<h_1^\alpha, h_2,\dots, h_w\right>$
3. linear transformation
    - multiply current state by a MSD matrix

**Note**: step 1 and step 3 can be merged into a single step as `affine transform`

Our poseidon uses 8 full rounds and 66 partial rounds. So that is
- 74 `affine transforms`
- 8$w$ + 66 `exponentiations` (can be done more efficiently with a high degree custom gate)

#### Rescue's round iteration:
1. add round constant
    - add a round key to current vector
2. S-box
    - for a foward round, compute $\left<h_1^\alpha, h_2^\alpha,\dots, h_w^\alpha\right>$
    - for a backword round, compute $\left<h_1^{1/\alpha}, h_2^{1/\alpha},\dots, h_w^{1/\alpha}\right>$
3. linear transformation
    - multiply current state by a MSD matrix

**Note**:
- step 1 and step 3 are identical to Poseidons.
- forward round and backward round have the same circuit complexity.

A 128 bits secure Rescue uses 12 forward rounds and 12 backward rounds. So that is
- 24 `affine transforms`
- 24$w$ `exponentiations` (can be done more efficiently with a high degree custom gate)

### Rescue vs Poseidon

We instantiate it with $w = 3$. This is a typical setup for a binary tree.

#### Parallel gate

$$q_1 w_1 + q_2 w_2 + q_3 w_3 + q_{h} w_1^5 + q_c=0$$

Rescue uses $72$ exp gates while Poseiden uses $90$ exp gates.

#### Customized Gate

$$q_1 w_1 + q_2 w_2 + q_3 w_3 + q_{h1} w_1^5 + q_{h2} w_3^5 + q_{h3} w_3^5 + q_c=0$$

Rescue uses $24$ exp gates while Poseiden uses $74$ exp gates.