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