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  # Roots of unity
 39  # ---------------------------------------------------------
 40  
 41  def gen_pow2_roots_of_unity(field, num_powers):
 42    """
 43    Generate the 2^i'th roots of unity
 44    with i in [0, num_powers)
 45    """
 46  
 47    # Find a primitive root of the finite field of modulus q
 48    # i.e. root^k != 1 for all k < q-1 so powers of root generate the field.
 49    # https://crypto.stanford.edu/pbc/notes/numbertheory/gen.html
 50    #
 51    # Usage, see ω usagefor polynomials in evaluation form:
 52    # https://dankradfeist.de/ethereum/2021/06/18/pcs-multiproofs.html
 53    primitive_root = field.multiplicative_generator()
 54  
 55    assert primitive_root == 7, (
 56      'The ref implementation c-kzg-4844 uses 7.'
 57      + ' Any primitive root is correct but the order of coefficients '
 58      + ' won\'t be the same which makes debugging harder.'
 59    )
 60  
 61    return [primitive_root^((field.characteristic()-1)//(1 << i)) for i in range(num_powers)]
 62  
 63  # Dump
 64  # ---------------------------------------------------------
 65  
 66  def dumpConst(name, inner):
 67    result = f'const {name}* = (\n'
 68    result += inner
 69    result += ')\n'
 70  
 71    return result
 72  
 73  def dumpRoots(vec):
 74    result = f'  # primitive_root⁽ᵐᵒᵈᵘˡᵘˢ⁻¹⁾/⁽²^ⁱ⁾ for i in [0, {len(vec)})\n'
 75    lastRow = len(vec) - 1
 76  
 77    for rowID, val in enumerate(vec):
 78      result += '  '
 79      result += f'BigInt[{max(1, int(val).bit_length())}].fromHex"0x{Integer(int(val)).hex()}"'
 80      result += ',\n' if rowID != lastRow else '\n'
 81  
 82    return result
 83  
 84  # CLI
 85  # ---------------------------------------------------------
 86  
 87  if __name__ == "__main__":
 88  
 89    with open(f'ethereum_kzg_constants.nim', 'w') as f:
 90  
 91      f.write(copyright())
 92      f.write('\n\n')
 93      f.write(inspect.cleandoc(f"""
 94        import
 95          ../config/curves,
 96          ../io/io_bigints
 97  
 98        # Roots of unity
 99        # ------------------------------------------------------------
100      """))
101      f.write('\n\n')
102  
103      r = Curves['BLS12_381']['field']['order']
104      Fr = GF(r)
105      f.write(dumpConst(
106        'ctt_eth_kzg_bls12_381_fr_pow2_roots_of_unity',
107        dumpRoots(gen_pow2_roots_of_unity(Fr, 32))
108      ))
109      f.write('\n\n')