Line data Source code
1 : #include "./fd_poseidon.h"
2 : #include "fd_poseidon_params.c"
3 :
4 : /* Poseidon internals */
5 :
6 : static inline void
7 : fd_poseidon_apply_ark( fd_bn254_scalar_t state[],
8 : ulong const width,
9 943 : fd_bn254_scalar_t const * ark ) {
10 8020 : for( ulong i=0; i<width; i++ ) {
11 7077 : fd_bn254_scalar_add( &state[i], &state[i], &ark[i] );
12 7077 : }
13 943 : }
14 :
15 : static inline void
16 : fd_poseidon_apply_sbox_full( fd_bn254_scalar_t state[],
17 7821 : ulong const width ) {
18 : /* Compute s[i]^5 */
19 21541 : for( ulong i=0; i<width; i++ ) {
20 13720 : fd_bn254_scalar_t t[1];
21 13720 : fd_bn254_scalar_sqr( t, &state[i] ); /* t = s^2 */
22 13720 : fd_bn254_scalar_sqr( t, t ); /* t = s^4 */
23 13720 : fd_bn254_scalar_mul( &state[i], &state[i], t ); /* s = s^5 */
24 13720 : }
25 7821 : }
26 :
27 : static inline void
28 7092 : fd_poseidon_apply_sbox_partial( fd_bn254_scalar_t state[] ) {
29 : /* Compute s[0]^5 */
30 7092 : fd_poseidon_apply_sbox_full( state, 1 );
31 7092 : }
32 :
33 : static inline void
34 : fd_poseidon_apply_mds( fd_bn254_scalar_t state[],
35 : ulong const width,
36 825 : fd_bn254_scalar_t const * mds ) {
37 825 : fd_bn254_scalar_t x[FD_POSEIDON_MAX_WIDTH+1] = { 0 };
38 : /* Vector-matrix multiplication (state vector times mds matrix) */
39 6976 : for( ulong i=0; i<width; i++ ) {
40 59766 : for( ulong j=0; j<width; j++ ) {
41 53615 : fd_bn254_scalar_t t[1];
42 53615 : fd_bn254_scalar_mul( t, &state[j], &mds[ i * width + j ] );
43 53615 : fd_bn254_scalar_add( &x[i], &x[i], t );
44 53615 : }
45 6151 : }
46 7063 : for( ulong i=0; i<width; i++ ) {
47 6238 : state[i] = x[i];
48 6238 : }
49 825 : }
50 :
51 : static inline void
52 : fd_poseidon_apply_sparse_mds( fd_bn254_scalar_t state[],
53 : ulong const width,
54 : fd_bn254_scalar_t const * row,
55 7071 : fd_bn254_scalar_t const * col ) {
56 7071 : fd_bn254_scalar_t old_s0 = state[0];
57 7071 : fd_bn254_scalar_t new_s0[1] = { 0 };
58 :
59 57801 : for( ulong j=0; j<width; j++ ) {
60 50730 : fd_bn254_scalar_t t[1];
61 50730 : fd_bn254_scalar_mul( t, &state[j], &row[j] );
62 50730 : fd_bn254_scalar_add( new_s0, new_s0, t );
63 50730 : }
64 :
65 52469 : for( ulong i=1; i<width; i++ ) {
66 45398 : fd_bn254_scalar_t t[1];
67 45398 : fd_bn254_scalar_mul( t, &old_s0, &col[i-1] );
68 45398 : fd_bn254_scalar_add( &state[i], &state[i], t );
69 45398 : }
70 :
71 7071 : state[0] = new_s0[0];
72 7071 : }
73 :
74 : static inline void
75 : fd_poseidon_apply_mds_row0( fd_bn254_scalar_t state[],
76 : ulong const width,
77 118 : fd_bn254_scalar_t const * mds ) {
78 118 : fd_bn254_scalar_t new_s0[1] = { 0 };
79 :
80 1010 : for( ulong j=0; j<width; j++ ) {
81 892 : fd_bn254_scalar_t t[1];
82 892 : fd_bn254_scalar_mul( t, &state[j], &mds[j] );
83 892 : fd_bn254_scalar_add( new_s0, new_s0, t );
84 892 : }
85 :
86 118 : state[0] = new_s0[0];
87 118 : }
88 :
89 : static inline __attribute__((always_inline)) void
90 : fd_poseidon_permute( fd_bn254_scalar_t state[],
91 : ulong const width,
92 : fd_poseidon_par_t const * params,
93 118 : ulong const partial_rounds ) {
94 118 : const ulong half_rounds = 4UL;
95 :
96 118 : fd_poseidon_apply_ark ( state, width, params->ark_start );
97 118 : fd_poseidon_apply_sbox_full ( state, width );
98 :
99 472 : for( ulong round=1; round<half_rounds; round++ ) {
100 354 : fd_poseidon_apply_ark ( state, width, params->ark_start + round*width );
101 354 : fd_poseidon_apply_mds ( state, width, params->mds );
102 354 : fd_poseidon_apply_sbox_full ( state, width );
103 354 : }
104 :
105 118 : fd_poseidon_apply_ark ( state, width, params->ark_start + half_rounds*width );
106 118 : fd_poseidon_apply_mds ( state, width, params->pre_sparse_mds );
107 :
108 7212 : for( ulong round=0; round<partial_rounds; round++ ) {
109 7094 : fd_poseidon_apply_sbox_partial( state );
110 7094 : fd_bn254_scalar_add( &state[0], &state[0], ¶ms->ark_partial[ round ] );
111 7094 : fd_poseidon_apply_sparse_mds( state,
112 7094 : width,
113 7094 : params->sparse_mds_row + round*width,
114 7094 : params->sparse_mds_col + round*(width-1UL) );
115 7094 : }
116 :
117 118 : fd_poseidon_apply_sbox_full( state, width );
118 471 : for( ulong round=0; round<half_rounds-1UL; round++ ) {
119 353 : fd_poseidon_apply_ark ( state, width, params->ark_end + round*width );
120 353 : fd_poseidon_apply_mds ( state, width, params->mds );
121 353 : fd_poseidon_apply_sbox_full ( state, width );
122 353 : }
123 118 : fd_poseidon_apply_mds_row0( state, width, params->mds );
124 118 : }
125 :
126 : static inline void
127 : fd_poseidon_get_params( fd_poseidon_par_t * params,
128 118 : ulong const width ) {
129 118 : #define FD_POSEIDON_GET_PARAMS(w) case (w): \
130 118 : params->ark = fd_poseidon_ark_## w; \
131 118 : params->mds = fd_poseidon_mds_## w; \
132 118 : params->ark_start = fd_poseidon_ark_start_## w; \
133 118 : params->ark_partial = fd_poseidon_ark_partial_## w; \
134 118 : params->ark_end = fd_poseidon_ark_end_## w; \
135 118 : params->pre_sparse_mds = fd_poseidon_pre_sparse_mds_## w; \
136 118 : params->sparse_mds_row = fd_poseidon_sparse_mds_row_## w; \
137 118 : params->sparse_mds_col = fd_poseidon_sparse_mds_col_## w; \
138 118 : break
139 :
140 118 : switch( width ) {
141 12 : FD_POSEIDON_GET_PARAMS(2);
142 11 : FD_POSEIDON_GET_PARAMS(3);
143 10 : FD_POSEIDON_GET_PARAMS(4);
144 9 : FD_POSEIDON_GET_PARAMS(5);
145 10 : FD_POSEIDON_GET_PARAMS(6);
146 7 : FD_POSEIDON_GET_PARAMS(7);
147 5 : FD_POSEIDON_GET_PARAMS(8);
148 10 : FD_POSEIDON_GET_PARAMS(9);
149 8 : FD_POSEIDON_GET_PARAMS(10);
150 13 : FD_POSEIDON_GET_PARAMS(11);
151 11 : FD_POSEIDON_GET_PARAMS(12);
152 118 : FD_POSEIDON_GET_PARAMS(13);
153 118 : }
154 118 : #undef FD_POSEIDON_GET_PARAMS
155 118 : }
156 :
157 : /* Poseidon interface */
158 :
159 : fd_poseidon_t *
160 : fd_poseidon_init( fd_poseidon_t * pos,
161 229 : int const big_endian ) {
162 229 : if( FD_UNLIKELY( pos==NULL ) ) {
163 0 : return NULL;
164 0 : }
165 229 : pos->big_endian = big_endian;
166 229 : pos->cnt = 0UL;
167 229 : fd_memset( pos->state, 0, sizeof(pos->state) );
168 229 : return pos;
169 229 : }
170 :
171 : fd_poseidon_t *
172 : fd_poseidon_append( fd_poseidon_t * pos,
173 : uchar const * data,
174 949 : ulong sz ) {
175 949 : if( FD_UNLIKELY( pos==NULL ) ) {
176 0 : return NULL;
177 0 : }
178 949 : if( FD_UNLIKELY( pos->cnt >= FD_POSEIDON_MAX_WIDTH ) ) {
179 0 : return NULL;
180 0 : }
181 949 : if( FD_UNLIKELY( sz!=32UL ) ) {
182 78 : return NULL;
183 78 : }
184 :
185 : /* Handle endianness */
186 871 : fd_bn254_scalar_t cur[1] = { 0 };
187 871 : fd_memcpy( cur->buf, data, 32UL );
188 871 : if( pos->big_endian ) {
189 463 : fd_uint256_bswap( cur, cur );
190 463 : }
191 :
192 871 : if( FD_UNLIKELY( !fd_bn254_scalar_validate( cur ) ) ) {
193 33 : return NULL;
194 33 : }
195 838 : pos->cnt++;
196 838 : fd_bn254_scalar_to_mont( &pos->state[ pos->cnt ], cur );
197 :
198 838 : return pos;
199 871 : }
200 :
201 : uchar *
202 : fd_poseidon_fini( fd_poseidon_t * pos,
203 118 : uchar hash[ FD_POSEIDON_HASH_SZ ] ) {
204 118 : if( FD_UNLIKELY( pos==NULL ) ) {
205 0 : return NULL;
206 0 : }
207 118 : if( FD_UNLIKELY( !pos->cnt ) ) {
208 0 : return NULL;
209 0 : }
210 118 : const ulong width = pos->cnt+1;
211 118 : fd_poseidon_par_t params[1] = { 0 };
212 118 : fd_poseidon_get_params( params, width );
213 118 : if( FD_UNLIKELY( !params->ark ||
214 118 : !params->mds ||
215 118 : !params->ark_start ||
216 118 : !params->ark_partial ||
217 118 : !params->ark_end ||
218 118 : !params->pre_sparse_mds ||
219 118 : !params->sparse_mds_row ||
220 118 : !params->sparse_mds_col ) ) {
221 0 : return NULL;
222 0 : }
223 :
224 118 : #define FD_POSEIDON_PERMUTE_CASE(w,p) case (w): fd_poseidon_permute( pos->state, (w), params, (p) ); break
225 118 : switch( width ) {
226 12 : FD_POSEIDON_PERMUTE_CASE( 2UL, 56UL );
227 11 : FD_POSEIDON_PERMUTE_CASE( 3UL, 57UL );
228 10 : FD_POSEIDON_PERMUTE_CASE( 4UL, 56UL );
229 9 : FD_POSEIDON_PERMUTE_CASE( 5UL, 60UL );
230 10 : FD_POSEIDON_PERMUTE_CASE( 6UL, 60UL );
231 7 : FD_POSEIDON_PERMUTE_CASE( 7UL, 63UL );
232 5 : FD_POSEIDON_PERMUTE_CASE( 8UL, 64UL );
233 10 : FD_POSEIDON_PERMUTE_CASE( 9UL, 63UL );
234 8 : FD_POSEIDON_PERMUTE_CASE( 10UL, 60UL );
235 13 : FD_POSEIDON_PERMUTE_CASE( 11UL, 66UL );
236 11 : FD_POSEIDON_PERMUTE_CASE( 12UL, 60UL );
237 12 : FD_POSEIDON_PERMUTE_CASE( 13UL, 65UL );
238 0 : default: return NULL;
239 118 : }
240 118 : #undef FD_POSEIDON_PERMUTE_CASE
241 :
242 : /* Convert through a local scalar: hash only needs to be byte aligned. */
243 118 : fd_bn254_scalar_t scalar_hash[1];
244 118 : fd_bn254_scalar_from_mont( scalar_hash, &pos->state[0] );
245 118 : if( pos->big_endian ) {
246 61 : fd_uint256_bswap( scalar_hash, scalar_hash );
247 61 : }
248 118 : fd_memcpy( hash, scalar_hash, 32 );
249 118 : return hash;
250 118 : }
|
