derive_pairing.sage
1 #!/usr/bin/sage 2 # vim: syntax=python 3 # vim: set ts=2 sw=2 et: 4 5 # Constantine 6 # Copyright (c) 2018-2019 Status Research & Development GmbH 7 # Copyright (c) 2020-Present Mamy André-Ratsimbazafy 8 # Licensed and distributed under either of 9 # * MIT license (license terms in the root directory or at http://opensource.org/licenses/MIT). 10 # * Apache v2 license (license terms in the root directory or at http://www.apache.org/licenses/LICENSE-2.0). 11 # at your option. This file may not be copied, modified, or distributed except according to those terms. 12 13 # ############################################################ 14 # 15 # Pairing constants 16 # 17 # ############################################################ 18 19 # Imports 20 # --------------------------------------------------------- 21 22 import os 23 import inspect, textwrap 24 25 # Working directory 26 # --------------------------------------------------------- 27 28 os.chdir(os.path.dirname(__file__)) 29 30 # Sage imports 31 # --------------------------------------------------------- 32 # Accelerate arithmetic by accepting probabilistic proofs 33 from sage.structure.proof.all import arithmetic 34 arithmetic(False) 35 36 load('curves.sage') 37 38 # Utilities 39 # --------------------------------------------------------- 40 41 # Code generators 42 # --------------------------------------------------------- 43 44 def genAteParam(curve_name, curve_config): 45 u = curve_config[curve_name]['field']['param'] 46 family = curve_config[curve_name]['field']['family'] 47 if family == 'BLS12': 48 ate_param = u 49 ate_comment = ' # BLS12 Miller loop is parametrized by u\n' 50 elif family == 'BN': 51 ate_param = 6*u+2 52 ate_comment = ' # BN Miller loop is parametrized by 6u+2\n' 53 elif family == 'BW6': 54 result = genAteParam_BW6_unoptimized(curve_name, curve_config) 55 result += '\n\n' 56 result += genAteParam_BW6_opt(curve_name, curve_config) 57 return result 58 else: 59 raise ValueError(f'family: {family} is not implemented') 60 61 buf = '# The bit count must be exact for the Miller loop\n' 62 buf += f'const {curve_name}_pairing_ate_param* = block:\n' 63 buf += ate_comment 64 65 ate_bits = int(ate_param).bit_length() 66 buf += f' BigInt[{ate_bits}].fromHex"0x{Integer(abs(ate_param)).hex()}"\n\n' 67 68 buf += f'const {curve_name}_pairing_ate_param_isNeg* = {"true" if ate_param < 0 else "false"}' 69 70 return buf 71 72 def genAteParam_BW6_unoptimized(curve_name, curve_config): 73 u = curve_config[curve_name]['field']['param'] 74 family = curve_config[curve_name]['field']['family'] 75 assert family == 'BW6' 76 77 # Algorithm 5 - https://eprint.iacr.org/2020/351.pdf 78 ate_param = u+1 79 ate_param_2 = u*(u^2 - u - 1) 80 81 ate_comment = ' # BW6-761 unoptimized Miller loop first part is parametrized by u+1\n' 82 ate_comment_2 = ' # BW6 unoptimized Miller loop second part is parametrized by u*(u²-u-1)\n' 83 84 # Note we can use the fact that 85 # f_{u+1,Q}(P) = f_{u,Q}(P) . l_{[u]Q,Q}(P) 86 # f_{u³-u²-u,Q}(P) = f_{u (u²-u-1),Q}(P) 87 # = (f_{u,Q}(P))^(u²-u-1) * f_{v,[u]Q}(P) 88 # 89 # to have a common computation f_{u,Q}(P) 90 # but this require a scalar mul [u]Q 91 # and then its inversion to plug it back in the second Miller loop 92 93 # f_{u+1,Q}(P) 94 # --------------------------------------------------------- 95 buf = '# 1st part: f_{u+1,Q}(P)\n' 96 buf += f'const {curve_name}_pairing_ate_param_1_unopt* = block:\n' 97 buf += ate_comment 98 99 ate_bits = int(ate_param).bit_length() 100 naf_bits = int(3*ate_param).bit_length() - ate_bits 101 102 buf += f' # +{naf_bits} to bitlength so that we can mul by 3 for NAF encoding\n' 103 buf += f' BigInt[{ate_bits}+{naf_bits}].fromHex"0x{Integer(abs(ate_param)).hex()}"\n\n' 104 105 buf += f'const {curve_name}_pairing_ate_param_1_unopt_isNeg* = {"true" if ate_param < 0 else "false"}' 106 107 # frobenius(f_{u*(u²-u-1),Q}(P)) 108 # --------------------------------------------------------- 109 110 buf += '\n\n\n' 111 buf += '# 2nd part: f_{u*(u²-u-1),Q}(P) followed by Frobenius application\n' 112 buf += f'const {curve_name}_pairing_ate_param_2_unopt* = block:\n' 113 buf += ate_comment_2 114 115 ate_2_bits = int(ate_param_2).bit_length() 116 naf_2_bits = int(3*ate_param_2).bit_length() - ate_2_bits 117 118 buf += f' # +{naf_2_bits} to bitlength so that we can mul by 3 for NAF encoding\n' 119 buf += f' BigInt[{ate_2_bits}+{naf_2_bits}].fromHex"0x{Integer(abs(ate_param_2)).hex()}"\n\n' 120 121 buf += f'const {curve_name}_pairing_ate_param_2_unopt_isNeg* = {"true" if ate_param_2 < 0 else "false"}' 122 123 buf += '\n' 124 return buf 125 126 def genAteParam_BW6_opt(curve_name, curve_config): 127 u = curve_config[curve_name]['field']['param'] 128 family = curve_config[curve_name]['field']['family'] 129 assert family == 'BW6' 130 131 # Algorithm 5 - https://eprint.iacr.org/2020/351.pdf 132 ate_param = u 133 ate_param_2 = u^2 - u - 1 134 135 ate_comment = ' # BW6 Miller loop first part is parametrized by u\n' 136 ate_comment_2 = ' # BW6 Miller loop second part is parametrized by u²-u-1\n' 137 138 # Note we can use the fact that 139 # f_{u+1,Q}(P) = f_{u,Q}(P) . l_{[u]Q,Q}(P) 140 # f_{u³-u²-u,Q}(P) = f_{u (u²-u-1),Q}(P) 141 # = (f_{u,Q}(P))^(u²-u-1) * f_{v,[u]Q}(P) 142 # 143 # to have a common computation f_{u,Q}(P) 144 # but this require a scalar mul [u]Q 145 # and then its inversion to plug it back in the second Miller loop 146 147 # f_{u,Q}(P) 148 # --------------------------------------------------------- 149 buf = '# 1st part: f_{u,Q}(P)\n' 150 buf += f'const {curve_name}_pairing_ate_param_1_opt* = block:\n' 151 buf += ate_comment 152 153 ate_bits = int(ate_param).bit_length() 154 naf_bits = 0 # int(3*ate_param).bit_length() - ate_bits 155 156 buf += f' # no NAF for the optimized first Miller loop\n' 157 buf += f' BigInt[{ate_bits}].fromHex"0x{Integer(abs(ate_param)).hex()}"\n\n' 158 159 buf += f'const {curve_name}_pairing_ate_param_1_opt_isNeg* = {"true" if ate_param < 0 else "false"}' 160 161 # frobenius(f_{u²-u-1,Q}(P)) 162 # --------------------------------------------------------- 163 164 buf += '\n\n\n' 165 buf += '# 2nd part: f_{u²-u-1,Q}(P) followed by Frobenius application\n' 166 buf += f'const {curve_name}_pairing_ate_param_2_opt* = block:\n' 167 buf += ate_comment_2 168 169 ate_2_bits = int(ate_param_2).bit_length() 170 naf_2_bits = int(3*ate_param_2).bit_length() - ate_2_bits 171 172 buf += f' # +{naf_2_bits} to bitlength so that we can mul by 3 for NAF encoding\n' 173 buf += f' BigInt[{ate_2_bits}+{naf_2_bits}].fromHex"0x{Integer(abs(ate_param_2)).hex()}"\n\n' 174 175 buf += f'const {curve_name}_pairing_ate_param_2_opt_isNeg* = {"true" if ate_param_2 < 0 else "false"}' 176 177 buf += '\n' 178 return buf 179 180 def genFinalExp(curve_name, curve_config): 181 p = curve_config[curve_name]['field']['modulus'] 182 r = curve_config[curve_name]['field']['order'] 183 k = curve_config[curve_name]['tower']['embedding_degree'] 184 family = curve_config[curve_name]['field']['family'] 185 186 # For BLS12 and BW6, 3*hard part has a better expression 187 # in the q basis with LLL algorithm 188 scale = 1 189 scaleDesc = '' 190 if family == 'BLS12': 191 scale = 3 192 scaleDesc = ' * 3' 193 if family == 'BW6': 194 u = curve_config[curve_name]['field']['param'] 195 scale = 3*(u^3-u^2+1) 196 scaleDesc = ' * 3*(u^3-u^2+1)' 197 198 fexp = (p^k - 1)//r 199 fexp *= scale 200 201 buf = f'const {curve_name}_pairing_finalexponent* = block:\n' 202 buf += f' # (p^{k} - 1) / r' + scaleDesc 203 buf += '\n' 204 buf += f' BigInt[{int(fexp).bit_length()}].fromHex"0x{Integer(fexp).hex()}"' 205 206 return buf 207 208 # CLI 209 # --------------------------------------------------------- 210 211 if __name__ == "__main__": 212 # Usage 213 # BLS12-381 214 # sage sage/derive_pairing.sage BLS12_381 215 216 from argparse import ArgumentParser 217 218 parser = ArgumentParser() 219 parser.add_argument("curve",nargs="+") 220 args = parser.parse_args() 221 222 curve = args.curve[0] 223 224 if curve not in Curves: 225 raise ValueError( 226 curve + 227 ' is not one of the available curves: ' + 228 str(Curves.keys()) 229 ) 230 else: 231 ate = genAteParam(curve, Curves) 232 fexp = genFinalExp(curve, Curves) 233 234 with open(f'{curve.lower()}_pairing.nim', 'w') as f: 235 f.write(copyright()) 236 f.write('\n\n') 237 f.write(inspect.cleandoc(""" 238 import 239 ../config/curves, 240 ../io/io_bigints 241 242 # Slow generic implementation 243 # ------------------------------------------------------------ 244 """)) 245 f.write('\n\n') 246 f.write(ate) 247 f.write('\n\n') 248 f.write(fexp) 249 f.write('\n\n') 250 f.write(inspect.cleandoc(""" 251 # Addition chain 252 # ------------------------------------------------------------ 253 """)) 254 255 print(f'Successfully created {curve}_pairing.nim')