# Poseidon in Filecoin
**Review by ADBK Consulting**
*Mikhail Vladimirov and Dmitry Khovratovich*
## Notation
Let $\mathbb{F}$ be the scalar field of the BN254 curve prime subgroup. Let $x_{i:j}$ denote a $(j-i+1)$-element vector $(x_i,x_{i+1},\ldots,x_j)$.
The Poseidon [paper](https://eprint.iacr.org/2019/458.pdf) defines (for various $\mathbb{F}$) a certain bijective transformation from $\mathbb{F}^n$ to $\mathbb{F}^n$ called the *Poseidon permutation*, which we denote by $\mathcal{P}_n$. Let us denote by $\mathcal{P}_n[2]$ the second element of the $\mathcal{P}_n$ output. Based on that, several hash functions have been defined in the paper.
## Poseidon Hash Functions in Filecoin
The Filecoin protocol makes use of several hash functions based on the Poseidon permutation $\mathcal{P}_n$ with different $n$.
### Poseidon Permutation
The permutations $\mathcal{P}_n$ are implemented correctly in Filecoin, which we checked thoroughly. In particular, optimized versions of $\mathcal{P}_n$ with sparser matrices in linear transformations are implemented, and we have verified that all the optimizations are correct and follow the strategy outlined in the original paper. We also checked that the nonlinear transformation and the constant addition are implemented correctly. The constant generation is implemented differently from the reference implementation, since the original paper is ambiguous about the endianness of constant bits.
### Poseidon Hash Functions
Filecoin implementation creates several hash functions, which we name according to the code:
1. The long-input function $H_{MD}(x_{1:t})$ which operates as follows:
a. Pad the input with zero $\mathbb{F}$ elements until $t=1\pmod{35}$.
b. Return
$$
\mathcal{P}_{37}[2](36,\ldots(36, \mathcal{P}_{37}[2](36,\mathcal{P}_{37}[2](36,x_{1:36}),x_{37:71}),\ldots),x_{(t-34):t}).
$$
2. Fixed-input hash functions $H_t$
$$
H_t(x_{1:t}) = \mathcal{P}_{t+1}[2](t,x_{1:t})
$$
## Issues in Poseidon-Based Hash Function Design
We have identified the following design issues:
1. The $H_{MD}$ function has **length extension problem**. Concretely, given $h = H_{MD}(x)$, where length of $x$ is $1 \pmod{35}$, it is possible to compute $H_{MD}(x,y)$ for any $y$ even when $x$ is unknown. This is a security issue when $x$ contains some secret information and a user is not supposed to be able to compute the hash if he does not know it. This might not be a problem if all messages have the same length by the protocol, but this is not enforced and might not be true in future versions of the code or protocol.
It is possible to fix this by reusing the first output element of $\mathcal{P}$ instead of setting it to 36, but we recommend a different scenario (see below).
2. The $H_{MD}$ function is **not collision resistant**. Indeed, for any $x$ longer than 36 elements we have
$$
H_{MD}(x_{1:36}x_{37:\ldots}) = H_{MD}(wx_{37:\ldots}),
$$
where $w=H_{MD}(x_{1:36})$. The same fix as above would apply here.
## Issues in Poseidon-based Hash Function Usage
We have identified the following usage issues:
1. The $H_{MD}$ function is too wide. This results in big memory usage and increasing computation time, as well as a lot of round constants and matrix elements in the code. We suggest a generic $\mathcal{H}$ construction (see below).
2. The data sent to $H_{MD}$ is padded twice, first in the [caller code](https://github.com/filecoin-project/rust-fil-proofs/blob/tnet2/storage-proofs/post/src/election/vanilla.rs#L204) and then in the [Poseidon internals](https://github.com/filecoin-project/rust-fil-proofs/blob/tnet2/storage-proofs/core/src/hasher/poseidon.rs#L269). Probably the first padding is redundant.
3. An instance $H_{11}$ of Poseidon of width 12, used for column hashing, is also too wide. We recommend implementing via $H_{MD}$ as above, which would require only 3 calls to $\mathcal{P}_5$ of width 5.
4. Merkle trees of arity greater than 4 are used, in particular the arity 8. We guess this is not optimal in terms of performance due to large width of transformation $\mathcal{P}$. We advise using a tree of the same arity everywhere, for instance 2 or 4. Note that a leaf can be a hash of an arbitrarily long object, for which the $\mathcal{H}$ hash can be used (or the fixed $H_{MD}$.
## Optimal Variable- and Fixed-Length Poseidon Hash
In order to process an arbitrary long string $\mathbf{x}$ of $\mathbb{F}$ elements, the following function $\mathcal{H}$ can be used:
1. Use permutation $\mathcal{P}_5$.
2. Let $l$ be the length of $\mathbf{x}$.
3. Pad the resulting string with zero elements up to the multiple of 4, then split it into chunks $\mathbf{w}_1,\mathbf{w}_2,\ldots,\mathbf{w}_k$ of 4 elements each.
4. Compute iteratively:
$$
(h^1_1,h^2_1,h^3_1,h^4_1,h^5_1) = \mathcal{P}_5(2^{64}+l,\mathbf{w}_1)$$
$$
(h_i^1,h_i^2,h_i^3,h_i^4,h_i^5) = \mathcal{P}_5(h_{i-1}^1,h_{i-1}^2+w_i^1,h_{i-1}^3+w_i^2,h_{i-1}^4+w_i^3,h_{i-1}^5+w_i^4)
$$
where $\mathbf{w}_i=(w_i^1,w_i^2,w_i^3,w_i^4)$ and addition is in the field. Note that we set the `arity tag` field into $2^{64}+l$. This guarantees that messages of different length have different input to the first $\mathcal{P}_5$ call.
5. Output $\mathcal{H}(\mathbf{x})=h_{last}[2]$.
This construction has several advantages:
1. It works well for messages of all lengths, including short messages, where the overhead is minimal. It is thus possible to have a single constant set for the entire code.
2. One may hash the first chunks of a long message before the last ones are available.
## Other Issues
1. The [`new_with_preimage`](https://github.com/filecoin-project/neptune/blob/v0.5.4/src/poseidon.rs#L158) method does not se the `pos` field properly.
2. The code contains three alternative implementations of Poseidon hash function. One one of these implementations is actually used, but all three are reachable. Probably unused implementation should be removed or moved to tests, to make code simpler and easier to read.

1. Notation Group elements (curve points) are capitals $K,R,P,\ldots$ Scalars (field elements) are lowercase $s,k,\ldots$ Scalar multiplication in the group is $[k]P$. Vectors are bold: $\mathbf{D}$. Tuples: $\mathcal{C}$ 2. Components 2.1 Cryptographic Primitives Curve $\mathbf{E}$ defined over field $\mathbb{F}_q$ (supposedly BN254) with group of prime order $\mathbb{F}_r$;

5/26/20231. Problem $f\in \mathbb{F}^d[X]$; $(a_1,a_2,\ldots,a_d)\in \mathbb{F}$ $(c_1,c_2,\ldots,c_d)\in \mathbb{F}$ $c(X)$ such that $c(\omega^i) = a_i$ and $c(\omega^{d + i}) = c_i$ Prove that $f( c(w^i))=c_i$ for all $1 \leq i \leq d$. 2. Warmup: Proof of Division

11/20/2022Dmitry Khovratovich Problem: whenever we implement an algorithm that works over $Z_{N}$, with $N=2^{16}$ or $N=2^{32}$, we need to reduce all computations modulo $N$ and range-check all variables against $N$. These operations are expensive. We suggest a new scheme that implements the mod-$N$ arithmetic without range checks. 1. State of the art: Simplified Plonk Notation: $N =2^n$. First recall (and simplify) how Plonk arranges its witness.

11/18/20221. Notation $n$ -- ring degree (512 or 1024) $q$ -- modulus $=12289 = 3\cdot 2^{12}+1$ $\widehat{\beta} = \lfloor\beta^2\rfloor$ -- max norm (34 034 726 or 70 265 242) $\phi=X^n+1$ 2. Single Signature Verification Inputs:

9/7/2022
Published on ** HackMD**