[Cryptography] Poseidon Hash Optimization (feat. Filecoin)

wooju·2023년 10월 25일
FilecoinPoseidon Hash Optimization

Poseidon Hash

목록 보기
4/4

Intro.

0. Notation & Background

Notation

  • MM는 3×33\times 3 mds 행렬
  • M−1M^{-1}는 행렬 MM의 역행렬
  • f:Fp3→Fp3f:\mathbb{F}_p^3\rightarrow \mathbb{F}_p^3 는 full 라운드의 비선형 연산을 나타내는 함수
  • g:Fp3→Fp3g:\mathbb{F}_p^3\rightarrow \mathbb{F}_p^3 는 partial 라운드의 비선형 연산을 나타내는 함수
  • s⃗i∈Fp3\vec{s}_i\in \mathbb{F}_p^3: ii 라운드의 state들의 행벡터
  • r⃗i∈Fp3\vec{r}_i\in \mathbb{F}_p^3: ii 라운드의 라운드 상수들의 행벡터
  • ARC,sARC, s-box,MDSbox, MDS: Poseidon permutation을 구성하는 각 함수들로, 순서대로 라운드 상수 덧셈, 비선형 연산, mds 행렬곱을 의미

Background

  • Sparse Matrix Factorization
    partial 라운드의 연산 최적화 과정에서 사용되며, 어떤 정방행렬을 sparse 한 행렬(원소의 대부분이 0으로 이루어진 행렬)의 곱으로 factorization하는 방법이다. 함수 D:Fp3×3→Fp3×3×Fp3×3D:\mathbb{F}_{p}^{3 \times 3} \rightarrow \mathbb{F}_{p}^{3 \times 3}\times \mathbb{F}_{p}^{3 \times 3} 를 정의해서 3×33\times 3 행렬 MM을 입력으로 해서 m′⋅m′′=Mm'\cdot m''= M을 만족하는 두 행렬을 반환하는 함수 m′,m′′←D(M)m', m''\leftarrow D(M) 를 정의하자. 구체적으로, 함수의 동작은 다음 00~66과정으로 이루어진다.
    \quad
    0. input M=[m00m01m02m10m11m12m20m21m22]1. m^=[m11m12m21m22],n^=[n11n12n21n22] such that n^=m^−12. m′=[1000m11m120m21m22]3. w⃗=[m10m20]4. w^⃗=n^⋅w⃗5. m′′=[m00m01m02w^[0]10w^[1]01]6.  return m′,m′′\begin{array}{l} \quad 0.\ \text{input } M= \left[\begin{array}{ccc} m_{00} & m_{01} & m_{02} \\ m_{10} & m_{11} & m_{12} \\ m_{20} & m_{21} & m_{22} \end{array}\right]\\ \quad \\ \quad 1.\ \hat{m}= \left[\begin{array}{cc} m_{11} & m_{12} \\ m_{21} & m_{22} \end{array}\right], \hat{n}= \left[\begin{array}{cc} n_{11} & n_{12} \\ n_{21} & n_{22} \end{array}\right] \text{ such that }\hat{n}=\hat{m}^{-1}\\ \quad \\ \quad 2.\ m^{\prime}= \left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & m_{11} & m_{12} \\ 0 & m_{21} & m_{22} \end{array}\right]\\ \quad \\ \quad 3.\ \vec{w}= \left[\begin{array}{c} m_{10} \\ m_{20} \end{array}\right]\\ \quad \\ \quad 4.\ \vec{\hat{w}}= \hat{n}\cdot \vec{w}\\ \quad \\ \quad 5.\ m^{\prime \prime}= \left[\begin{array}{ccc} m_{00} & m_{01} & m_{02} \\ \hat{w}[0] & 1 & 0 \\ \hat{w}[1] & 0 & 1 \end{array}\right]\\ \quad \\ \quad 6.\ \text{ return } m^{\prime}, m^{\prime \prime} \end{array}\\ \quad \\
    위와 같이 정의된 함수 DD는 3×33\times 3 행렬 MM을 입력으로 받아서 M=m′⋅m′′M = m'\cdot m''을 만족하는 두개의 3×33\times 3 행렬 m′,m′′m', m''을 출력한다. 이부분은 다음과 같이 어렵지 않게 확인 가능하다.
    m′⋅m′′=[1000m11m120m21m22]⋅[m00m01m02w^[0]10w^[1]01]=[m00m01m02m11⋅w^[0]+ m12⋅w^[1]m11m12m21⋅w^[0]+ m22⋅w^[1]m21m22]\begin{array}{l} m'\cdot m''&=& \left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & m_{11} & m_{12} \\ 0 & m_{21} & m_{22} \end{array}\right]\cdot \left[\begin{array}{ccc} m_{00} & m_{01} & m_{02} \\ \hat{w}[0] & 1 & 0 \\ \hat{w}[1] & 0 & 1 \end{array}\right]\\ \quad \\ &=& \left[\begin{array}{ccc} m_{00} & m_{01} & m_{02} \\ m_{11}\cdot \hat{w}[0]+\ m_{12} \cdot \hat{w}[1]& m_{11} & m_{12} \\ m_{21}\cdot \hat{w}[0]+\ m_{22} \cdot \hat{w}[1] & m_{21} & m_{22} \end{array}\right]\\ \quad \\ \end{array}\\ \quad \\
    다음 아래의 등식이 성립함을 통해서 M=m′⋅m′′M = m'\cdot m''임을 확인할 수 있다.
    [m11⋅w^[0]+ m12⋅w^[1]m21⋅w^[0]+ m22⋅w^[1]]=[m11 m12m21 m22]⋅[w^[0]w^[1]]=m^⋅w^⃗=m^⋅n^⋅w⃗=w⃗\begin{array}{l} \left[\begin{array}{c} m_{11}\cdot \hat{w}[0]+\ m_{12} \cdot \hat{w}[1]\\ m_{21}\cdot \hat{w}[0]+\ m_{22} \cdot \hat{w}[1] \\ \end{array}\right]&=& \left[\begin{array}{c} m_{11}\ & m_{12}\\ m_{21}\ & m_{22}\\ \end{array}\right]\cdot \left[\begin{array}{c} \hat{w}[0]\\ \hat{w}[1] \\ \end{array}\right]\\ \quad \\ &=& \hat{m}\cdot \vec{\hat{w}}\\ \quad \\ &=& \hat{m}\cdot \hat{n}\cdot \vec{w}\\ \quad \\ &=& \vec{w} \end{array}\\ \quad \\
    이 함수에서 중요한 부분은 m′m'과 m′′m'' 이 단위행렬의 일부를 포함한 형태라는 것이다. 단위행렬의 경우 행렬곱 연산의 결과에 영향을 주지 않는데, 이러한 성질을 이용해서 partial 라운드의 연산을 더 적은 constraint들로 표현하는 것이 가능하다. 연산 결과에 영향을 주지 않는다는 것을 예를 들면, 다음과 같이 어떤 벡터에 행렬을 곱했을때 결과 벡터의 원소가 다시 자기자신이 되는 상황이다.
    [x⋯⋯]⋅[1000⋱⋮0⋯]=[x⋮⋮]\begin{array}{l} \left[\begin{array}{ccc} x & \cdots &\cdots\\ \end{array}\right]\cdot \left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & \ddots & \vdots \\ 0 & \cdots & \end{array}\right]= \left[\begin{array}{c} x \\ \vdots \\ \vdots \\ \end{array}\right] \end{array}
    \quad
    \quad

Optimization

1. full round

하나의 full 라운드는 ARC>sARC > s-box>MDSbox > MDS 연산 순서로 구성된다. 이를 notation의 정의를 이용해서 표현하면 다음과 같다.

f(s⃗i+r⃗i)⋅M=s⃗i+1f(\vec{s}_i+\vec{r}_i)\cdot M = \vec{s}_{i+1}

그러면 s⃗i+r⃗i,s⃗i+1+r⃗i+1\vec{s}_i+\vec{r}_i, \vec{s}_{i+1}+\vec{r}_{i+1}의 관계식은 다음과 같다.

f(s⃗i+r⃗i)⋅M+r⃗i+1=s⃗i+1+r⃗i+1f(\vec{s}_i+\vec{r}_i)\cdot M +\vec{r}_{i+1}= \vec{s}_{i+1}+\vec{r}_{i+1}

위 식은 ii 라운드의 state s⃗i\vec{s}_i에 ARCARC, ss-boxbox, MDSMDS 연산을 수행한 뒤 i+1i+1 라운드의 state s⃗i+1\vec{s}_{i+1}에 대한 ARCARC 연산까지를 포함하는 제약식을 나타낸다. 식을 다시 정리하면 다음과 같다.

(f(s⃗i+r⃗i)+r⃗i+1⋅M−1)⋅M=s⃗i+1+r⃗i+1(f(\vec{s}_i+\vec{r}_i) +\vec{r}_{i+1}\cdot M^{-1})\cdot M = \vec{s}_{i+1}+\vec{r}_{i+1}

s⃗i+r⃗i\vec{s}_i+\vec{r}_i는 i−1i-1의 full 라운드의 출력이라는 가정하에, ii 라운드의 제약식은 s⃗i+r⃗i\vec{s}_i+\vec{r}_i와 r⃗i+1⋅M−1\vec{r}_{i+1}\cdot M^{-1}를 입력으로 하여 출력 값 s⃗i+1+r⃗i+1\vec{s}_{i+1}+\vec{r}_{i+1} 에 대한 연산 관계를 정의한다. mds행렬 MM과 라운드 상수는 연산을 수행하기 전에 미리 결정되는 값들로 r′⃗i+1=r⃗i+1⋅M−1\vec{r'}_{i+1}=\vec{r}_{i+1}\cdot M^{-1}을 미리 계산해 놓을 수 있다. 따라서, full 라운드의 연산은 위의 식의 반복으로 표현될 수 있다.
\quad
\quad

2. full -> partial round

s⃗i+r⃗i\vec{s}_i+\vec{r}_i 가 처음 절반의 full 라운드의 출력값이라 하자. 이 출력에 이어서 다시 full 라운드를 진행하는 경우에는 다음과 같이 mds행렬 MM을 이용해서 출력 값을 나타낼 수 있다.

(f(s⃗i−1+r⃗i−1)+r⃗i⋅M−1)⋅M=s⃗i+1+r⃗i+1\begin{array}{l} (f(\vec{s}_{i-1}+\vec{r}_{i-1})+\vec{r}_{i}\cdot M^{-1})\cdot M = \vec{s}_{i+1}+\vec{r}_{i+1} \\ \end{array}

하지만 filecoin의 최적화 방법에서는 partial 라운드에서 비선형 연산을 첫번째 state만 적용하고 있다는 이점을 활용하기 위해서 마지막 full 라운드에 다소 테크닉컬한 방법을 사용한다.이해를 돕기 위해 두번의 partial 라운드에 대해서만 생각해보자. partial 라운드의 최적화 과정을 크게 MDS행렬 곱의 최적화와 라운드 상수의 최적화 두가지단계로 나눠서 볼것이다.

1. partial 라운드에서 보이는 sparse mds행렬 연산과정)

m0′,m0′′←D(M)m'_0,m''_0\leftarrow D(M)라고 하고, m1′,m1′′←D(M⋅m0′)m'_1,m''_1\leftarrow D(M\cdot m'_0) 이라하자.

마지막 full 라운드에서 partial 라운드의 입력을 위한 제약식을 다음과 같이 설정할 수 있다.

(f(s⃗i−1+r⃗i−1)+r⃗i⋅M−1)⋅M⋅m1′=(s⃗i+r⃗i)⋅m1′\begin{array}{l} (f(\vec{s}_{i-1}+\vec{r}_{i-1})+\vec{r}_{i}\cdot M^{-1})\cdot M\cdot m'_1 &=& (\vec{s}_{i}+\vec{r}_{i})\cdot {m'_1} \\ \end{array}

위 식에는 각 partial 라운드에서 필요한 연산 ARC > s-box > MDS에서 필요한 ARC연산 및 MDS의 일부 연산이 미리 적용되어 있다고 이해할 수 있다.

mi′=[1000⋱⋮0⋯]\begin{array}{l} m_i'= \left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & \ddots & \vdots \\ 0 & \cdots & \end{array}\right] \end{array}와 같은 형태로 정의되며, g\textcolor{red}g는 첫번째 성분에만 적용되는 연산이므로 다음 등식이 성립함을 알 수 있다.

(g(s⃗i+r⃗i))⋅m1′=g((s⃗i+r⃗i)⋅m1′)\begin{array}{l} (\textcolor{red}{g(}\vec{s}_{i}+\textcolor{green}{\vec{r}_{i}}\textcolor{red}{)})\cdot {m'_1}=\textcolor{red}{g(}(\vec{s}_{i}+\textcolor{green}{\vec{r}_{i}})\cdot {m'_1}\textcolor{red}{)} \\ \end{array}

양변에 m1′′m''_1 를 곱하면 다음과 같은 식을 얻는다.

(g(s⃗i+r⃗i))⋅m1′⋅m1′′=(g(s⃗i+r⃗i))⋅M⋅m0′=s⃗i+1⋅m0′\begin{array}{l} (\textcolor{red}{g(}\vec{s}_{i}+\textcolor{green}{\vec{r}_{i}}\textcolor{red}{)})\cdot {m'_1}\cdot {m''_1}&=&(\textcolor{red}{g(}\vec{s}_{i}+\textcolor{green}{\vec{r}_{i}}\textcolor{red}{)})\cdot \textcolor{blue}M\cdot {m'_0} \\ \quad \\&=&\vec{s}_{i+1}\cdot {m'_0} \end{array}

계산 결과로 s⃗i+1+r⃗i+1\vec{s}_{i+1}+\vec{r}_{i+1}꼴을 얻기위해

라운드 상수를 다음과 같이 수정할 수 있다.

(g(s⃗i+r⃗i)+r⃗i+1⋅M−1)⋅m1′⋅m1′′=(g(s⃗i+r⃗i)+r⃗i+1⋅M−1)⋅M⋅m0′=(s⃗i+1+r⃗i+1)⋅m0′\begin{array}{l} (\textcolor{red}{g(}\vec{s}_{i}+\textcolor{green}{\vec{r}_{i}}\textcolor{red}{)}+\textcolor{green}{\vec{r}_{i+1}\cdot{M^{-1}}})\cdot {m'_1}\cdot {m''_1}&=&(\textcolor{red}{g(}\vec{s}_{i}+\textcolor{green}{\vec{r}_{i}}\textcolor{red}{)}+\textcolor{green}{\vec{r}_{i+1}\cdot{M^{-1}}})\cdot \textcolor{blue}M\cdot {m'_0} \\ \quad \\&=&(\vec{s}_{i+1}+\vec{r}_{i+1})\cdot {m'_0} \end{array}

위와 동일한 과정으로 양변에 비선형 연산을 적용하고 m0′′m''_0 를 곱하면 다음과 같은 식을 얻는다.

(g(s⃗i+1+r⃗i+1))⋅m0′⋅m0′′=(g(s⃗i+1+r⃗i+1))⋅M=s⃗i+2\begin{array}{l} (\textcolor{red}{g(}\vec{s}_{i+1}+\textcolor{green}{\vec{r}_{i+1}}\textcolor{red}{)})\cdot {m'_0}\cdot {m''_0}&=&(\textcolor{red}{g(}\vec{s}_{i+1}+\textcolor{green}{\vec{r}_{i+1}}\textcolor{red}{)})\cdot \textcolor{blue}M \\ \quad \\&=&\vec{s}_{i+2} \end{array}

역시 위와 동일하게 계산 결과로 s⃗i+2+r⃗i+2\vec{s}_{i+2}+\vec{r}_{i+2}꼴을 얻기위해

라운드 상수를 다음과 같이 수정할 수 있다.

(g(s⃗i+1+r⃗i+1)+r⃗i+2⋅M−1)⋅M=s⃗i+2+r⃗i+2\begin{array}{l} (\textcolor{red}{g(}\vec{s}_{i+1}+\textcolor{green}{\vec{r}_{i+1}}\textcolor{red}{)}+\textcolor{green}{\vec{r}_{i+2}\cdot{M^{-1}}})\cdot \textcolor{blue}M &=&\vec{s}_{i+2}+\vec{r}_{i+2} \end{array}

2. 라운드 상수

이를 한번에 적으면 다음을 확인할 수 있다.

s⃗i+2+r⃗i+2=(g(s⃗i+1+r⃗i+1)+r⃗i+2⋅M−1)⋅M=g((s⃗i+1+r⃗i+1)⋅m0′)⋅m0′′+r⃗i+2=g((g(s⃗i+r⃗i)+r⃗i+1⋅M−1)⋅m1′⋅m1′′)⋅m0′′+r⃗i+2\begin{array}{l} \vec{s}_{i+2}+\vec{r}_{i+2}&=&(\textcolor{red}{g(}\vec{s}_{i+1}+\textcolor{green}{\vec{r}_{i+1}}\textcolor{red}{)}+\textcolor{green}{\vec{r}_{i+2}\cdot{M^{-1}}})\cdot M \\ \quad \\ &=&\textcolor{red}{g(}(\vec{s}_{i+1}+\textcolor{green}{\vec{r}_{i+1}})\cdot m'_0\textcolor{red}{)}\cdot m''_0+\textcolor{green}{\vec{r}_{i+2}} \\ \quad \\ &=&\textcolor{red}{g(}(\textcolor{red}{g(}\vec{s}_{i}+\textcolor{green}{\vec{r}_{i}}\textcolor{red}{)}+\textcolor{green}{\vec{r}_{i+1}\cdot{M^{-1}}})\cdot {m'_1}\cdot {m''_1}\textcolor{red}{)}\cdot m''_0+\textcolor{green}{\vec{r}_{i+2}} \end{array}

i+2i+2 의 라운드 상수는 다음과 같이 다시 적을 수 있으므로

r⃗i+2=((r⃗i+2⋅(m0′′)−1(m1′⋅m1′′)−1)⋅m1′⋅m1′′)⋅m0′′=((r⃗i+2⋅(m0′′)−1(M⋅m0′)−1)⋅m1′⋅m1′′)⋅m0′′=((r⃗i+2⋅(M−1)2)⋅m1′⋅m1′′)⋅m0′′\begin{array}{l}\textcolor{green}{\vec{r}_{i+2}} &=& ((\textcolor{green}{\vec{r}_{i+2}}\cdot {(m''_0)}^{-1}{(m'_1\cdot m''_1)}^{-1})\cdot m'_1\cdot m''_1)\cdot m''_0\\ \quad \\ &=& ((\textcolor{green}{\vec{r}_{i+2}}\cdot {(m''_0)}^{-1}{(M\cdot m'_0)}^{-1})\cdot m'_1\cdot m''_1)\cdot m''_0 \\ \quad \\ &=& ((\textcolor{green}{\vec{r}_{i+2}}\cdot ({M}^{-1})^2)\cdot m'_1\cdot m''_1)\cdot m''_0\end{array}

다음 식이 성립한다.

s⃗i+2+r⃗i+2=g((g(s⃗i+r⃗i)+r⃗i+1⋅M−1+r⃗i+2⋅M−2)⋅m1′⋅m1′′)⋅m0′′\begin{array}{l} \vec{s}_{i+2}+\vec{r}_{i+2}&=&\textcolor{red}{g(}(\textcolor{red}{g(}\vec{s}_{i}+\textcolor{green}{\vec{r}_{i}}\textcolor{red}{)}+\textcolor{green}{\vec{r}_{i+1}\cdot{M^{-1}}}+\textcolor{green}{\vec{r}_{i+2}\cdot M^{-2}})\cdot {m'_1}\cdot {m''_1}\textcolor{red}{)}\cdot m''_0 \end{array}

또한, g\textcolor{red}g는 첫번째 성분에만 적용되는 연산이므로 위의 라운드 상수와 MDS 의 역행렬을 곱해서 얻어지는 초록색 상수부분을 partial라운드를 시작하기 이전에 precompute해서 라운드 상수를 새롭게 정의하면 partial라운드를 수행하면서 더해지는 상수부분을 비선형 연산이 적용되는 첫번째 성분에 대해서만 적용하면 충분하다. 즉, r⃗i+1′=r⃗i+1⋅M−1,r⃗i+2′′=r⃗i+2⋅M−2{\vec{r}'_{i+1}}={\vec{r}_{i+1}\cdot{M^{-1}}},\vec{r}''_{i+2}={\vec{r}_{i+2}\cdot M^{-2}} 라 정의하고 라운드 상수를 다음과 같이 다시 정의한다

ci⃗=ri⃗+[0ri+1′[1]ri+1′[2]]+[0ri+2′′[1]ri+2′′[2]]\begin{array}{l} \vec{c_i}&=&\vec{r_i}+ \left[\begin{array}{c} 0 \\ r'_{i+1}[1] \\ r'_{i+1}[2] \end{array}\right]+ \left[\begin{array}{c} 0 \\ r''_{i+2}[1] \\ r''_{i+2}[2] \end{array}\right] \end{array}\\ \quad \\

위의 최적화 내용을 정리하자면, 마지막 full 라운드에서 partial 라운드의 입력을 위한 제약식을 다음과 같이 쓸 수 있다.

(f(s⃗i−1+r⃗i−1)+c⃗i⋅M−1)⋅M⋅m1′=(s⃗i+c⃗i)⋅m1′\begin{array}{l} (f(\vec{s}_{i-1}+\vec{r}_{i-1})+\vec{c}_{i}\cdot M^{-1})\cdot M\cdot m'_1 &=& (\vec{s}_{i}+\vec{c}_{i})\cdot {m'_1} \\ \end{array}

이후 이어지는 partial 라운드에서는 두번째, 세번째 state 에 대한 추가적인 라운드 상수의 덧셈을 고려하지 않아도 되며 sparse행렬의 곱과 첫번째 state에 대한 라운드 상수덧셈 및 비선형연산을 고려하면 된다.

단, 첫번째 state에는 라운드 상수를 더하는 연산과 비선형연산이 섞여있으므로 c⃗i\vec{c}_i를 계산하면서 얻게되는 첫번째 성분에 더해지는 라운드 상수들을 partial 라운드 횟수만큼 따로 저장해 놓고 사용해야한다.

considerations:

  • mds행렬 MM대신 M⋅m1′M\cdot m_1'을 사용하는 것은 partial 라운드 두번을 수행하는 경우를 고려한 경우이며, 라운드 횟수에 따라서 라운드 상수 및 full라운드 마지막에 곱할 행렬에 대한 추가적인 계산이 필요하다. 하지만 연산을 수행하기전 미리 precompute 할 수 있다.
  • 라운드 상수의 최적화로, 저장하고 있어야할 라운드 상수의 갯수와 라운드 상수 연산의 횟수가 줄어든다.
  • scroll's optimization에서는 7번의 partial 라운드를 8번에 거쳐서 제약식을 표현하는데, 각 8번에서 위와 같은 방식으로 유도하여 사용하는 mds행렬로 부터 유도된 값들은 동일하게 표현될 것으로 예상할 수 있다.
  • 위와 같은 테크닉에서 사용되는 m′,m′′m', m''는 state 벡터의 첫번째 성분과 두번째, 세번째 성분의 연산을 나눠서 적용하기 위해 도입되었다고 볼 수 있다.
  • 일반화된 알고리즘은 filecoin의 최적화 문서에서 찾아볼 수 있다.
    \quad
    \quad

3. partial round

full 라운드에서 partial 라운드로의 출력 값은 (s⃗i+r⃗i)⋅m′(\vec{s}_{i}+\vec{r}_{i})\cdot {m'} 에서 시작한다. 행렬 m′{m'}은 정의에 의해서 state 벡터 값에 행렬곱 연산 적용시 첫번째 성분의 값을 변경시키지 않으며, gg는 첫번째 성분에만 적용되는 비선형 연산임을 기억하자. 비선형 연산을 적용하고 행렬 m′′{m''}을 곱하면 다음과 같다.

g((s⃗i+r⃗i)⋅m′)⋅m′′=s⃗i+1g((\vec{s}_i+\vec{r}_i)\cdot m')\cdot m'' = \vec{s}_{i+1}

m′⋅m′′=M{m'}\cdot m'' = M이라는 사실을 이용하면, full 라운드에서와 마찬가지로 s⃗i+r⃗i,s⃗i+1,r⃗i+1\vec{s}_i+\vec{r}_i, \vec{s}_{i+1}, \vec{r}_{i+1}들에 대한 다음 관계식을 생각할 수 있다.

(g(s⃗i+r⃗i)+r⃗i+1⋅M−1)⋅M=s⃗i+1+r⃗i+1(g(\vec{s}_i+\vec{r}_i)+\vec{r}_{i+1}\cdot M^{-1})\cdot M= \vec{s}_{i+1}+\vec{r}_{i+1}

위 과정을 통해 한번의 partial 라운드에 대한 연산을 바르게 수행했는지 여부를 확인할 수 있으며, partial 라운드가 두번이상인 경우에는 '2. full -> partial round' 과정에서 사용했던 M⋅m′M\cdot m' 행렬을 다시 함수 DD의 입력으로하여 라운드의 횟수만큼 수행하고 이때 m′′m''에 해당하는 행렬값들만 따로 저장하여 partial 라운드 진행시 적용하여 확장할 수 있다.
\quad

Reference

Filecoin's poseidon_spec.pdf

: 위 내용은 포세이돈 해시 함수의 최적화 기법 이해를 위해 레퍼런스의 Filecoin poseidon_spec 문서를 기반으로 작성되었으며, 자세한 내용 및 일반화된 알고리즘들은 해당 문서에 더욱 자세히 기술되어 있다.

profile
wooju
이전 포스트

[Halo2-Dev] Optimized Poseidon Hash Circuit

0개의 댓글