Sage script for constants calculation for banderwagon and bandersnatch

[rupam-04]

Addresses #359 .

Implemented the sqrtPrecomp_PrimitiveDyadicRoots in Sage. However I would need some help on defining the ret array in sage as I didn't come across any helpful SageMath docs.

[mratsim]

However I would need some help on defining the ret array in sage as I didn't come across any helpful SageMath docs.

For arrays, you can get inspiration from my lattice pretty printer here: https://github.com/mratsim/constantine/blob/976c8bb215a3f0b21ce3d05f894eb506072a6285/sage/derive_endomorphisms.sage#L45-L51

which generates this:

https://github.com/mratsim/constantine/blob/976c8bb215a3f0b21ce3d05f894eb506072a6285/constantine/math/constants/bls12_381_endomorphisms.nim#L21-L27

or my Frobenius constants generator

https://github.com/mratsim/constantine/blob/976c8bb215a3f0b21ce3d05f894eb506072a6285/sage/derive_frobenius.sage#L139-L149

which generates this

https://github.com/mratsim/constantine/blob/976c8bb215a3f0b21ce3d05f894eb506072a6285/constantine/math/constants/bls12_381_frobenius.nim#L51-L129

After the Dyadic roots, we also need: the Precomputed Blocks and the table:

https://github.com/mratsim/constantine/blob/976c8bb215a3f0b21ce3d05f894eb506072a6285/constantine/math/constants/banderwagon_sqrt.nim#L210-L1507

[rupam-04]

However I would need some help on defining the ret array in sage as I didn't come across any helpful SageMath docs.

For arrays, you can get inspiration from my lattice pretty printer here:

https://github.com/mratsim/constantine/blob/976c8bb215a3f0b21ce3d05f894eb506072a6285/sage/derive_endomorphisms.sage#L45-L51

which generates this:

https://github.com/mratsim/constantine/blob/976c8bb215a3f0b21ce3d05f894eb506072a6285/constantine/math/constants/bls12_381_endomorphisms.nim#L21-L27

or my Frobenius constants generator

https://github.com/mratsim/constantine/blob/976c8bb215a3f0b21ce3d05f894eb506072a6285/sage/derive_frobenius.sage#L139-L149

which generates this

https://github.com/mratsim/constantine/blob/976c8bb215a3f0b21ce3d05f894eb506072a6285/constantine/math/constants/bls12_381_frobenius.nim#L51-L129

After the Dyadic roots, we also need: the Precomputed Blocks and the table:

https://github.com/mratsim/constantine/blob/976c8bb215a3f0b21ce3d05f894eb506072a6285/constantine/math/constants/banderwagon_sqrt.nim#L210-L1507

I tried using a dictionary instead of an array. That shouldn't be a problem right?

[mratsim]

I tried using a dictionary instead of an array. That shouldn't be a problem right?

Using a table is fine at the moment for proof-of-concept purposes. However, they cannot be constant-time and so will need to be changed later: https://github.com/mratsim/constantine/issues/358

[rupam-04]

I tried using a dictionary instead of an array. That shouldn't be a problem right?

Using a table is fine at the moment for proof-of-concept purposes. However, they cannot be constant-time and so will need to be changed later: #358

I thought the sage script is just for generating the constants. So is it necessary to convert the sage code to constant time?

[mratsim]

I tried using a dictionary instead of an array. That shouldn't be a problem right?

Using a table is fine at the moment for proof-of-concept purposes. However, they cannot be constant-time and so will need to be changed later: #358

I thought the sage script is just for generating the constants. So is it necessary to convert the sage code to constant time?

Not yet, but it will need to be refactored for #358.

Should this be modularised such that constants for other curves can also be generated by plugging in the curve params ? @mratsim

Yes, this can be done in a subsequent PR, if this one is too big, atm it's only 47 lines but missing all the code that format things correctly so that we can just copy-paste the constants into the Nim codebase.

One thing though that I think is important is this:

• https://github.com/pornin/modsqrt/blob/0a9c69a0ce8b4a031e7f4a728a3bd93870088ecf/modsqrt.sage#L133-L138
• https://github.com/pornin/modsqrt/blob/0a9c69a0ce8b4a031e7f4a728a3bd93870088ecf/modsqrt.sage#L232-L236

#  - When lb is small enough, this is a matter of recognizing the value z
#    among the known 2^lb-th roots of 1, with a "reverse lookup". This can
#    be done by using only a small number of bits from the value (see the
#    minhc() function in the code below, to find a minimal-sized bit
#    pattern that is enough to distinguish all roots). We can thus stop
#    the recursion before reaching lb == 1.

and the function minhc: https://github.com/pornin/modsqrt/blob/0a9c69a0ce8b4a031e7f4a728a3bd93870088ecf/modsqrt.sage#L535-L559

Ergo, we are using a LUT of window 8 (see also https://hackmd.io/@jsign/bandersnatch-optimized-sqrt-notes#Detailed-comparison): https://github.com/mratsim/constantine/blob/d7871d74852b360aba456cee710389b7858cc5ac/constantine/math/constants/banderwagon_sqrt.nim#L167-L172

but we're lucky because 8-bit patterns can uniquely identify the root-of-unity we need.

For constant-time implementation because we can't use branches, we have to scan through a whole array that maps bit pattern to root of unities, i.e. no sparse hash-table. And the mapping size grows exponentially with the number of bits, so we likely would want to use 6-bit windows for example if the pattern is small enough to uniquely identify the root of unity we need, that would be 4x less memory consumption.

This means we need to check the absence of pattern collisions in our precomputed small windows.

[rupam-04]

@mratsim things are pretty much completed it seems to me. Are we ready to merge this then?