Elliptic curve arithmetic in script

A computer-implemented method for performing elliptic curve arithmetic using blockchain transactions, wherein the method is performed by a script engine and comprises:

• obtaining a first blockchain transaction, wherein the first blockchain transaction comprises a first script, wherein the first script comprises a modular inversion script, and wherein the modular inversion script is configured to, when executed, by a script engine:
• obtain a target integer (x) and a modulus value (p), wherein the target integer and the modulus value are co-prime and the modulus value is a prime number,
• obtain a pair of indices (si, ti) for a component (ai) of an addition chain for a reduced modulus value (p−2), the reduced modulus value have a value two less than the modulus value, the indices identifying a pair of pervious components of the addition chain which, when summed, equal the component of the addition chain, wherein the addition chain has a length l, and
• output a modular inverse (y) of the target integer, wherein the modular inverse is generated by:
• computing a sequence of l multiplier values, wherein a first multiplier value of the sequence of multiplier values is equal to the target integer, a second multiplier value of the sequence of multiplier values is computed, and for each component of the addition chain for 3≤i≤l, a respective multiplier value of the sequence of multiplier values is iteratively computed, each respective multiplier value being the target integer (x) exponentiated by the component of the addition chain, each respective multiplier value being calculated by:
• selecting from a stack the multiplier values associated with the pair of previous components of the addition chain;
• multiplying the selected multiplier values to generate the respective multiplier value for the component;
• and
• pushing the generated multiplier value to the stack;
• and
• for i=l, computing a modulus of the multiplier value with respect to the modulus value (p), wherein the modulus of the multiplier value with respect to the modulus value (p) is output as the modular inverse (y);
• and
• obtaining a second blockchain transaction, wherein the second blockchain transaction comprises a second script, wherein the second script comprises the target integer (x) and the modulus value (p);
• and executing the first script together with the second script to generate the modular inverse of the target integer.

Computer equipment, comprising:

• memory comprising one or more memory units;
• and
• processing apparatus comprising one or more processing units, wherein the memory stores code arranged to run on the processing apparatus, the code being configured so as when run on the processing apparatus, the processing apparatus performs a method for enabling elliptic curve arithmetic to be performed using blockchain transactions, wherein the method is performed by a script generator and comprises:
• generating a first script of a first blockchain transaction, wherein the first script comprises a modular inversion script, and wherein the modular inversion script is configured to, when executed, by a script engine:
• obtain a target integer (x) and a modulus value (p), wherein the target integer and the modulus value are co-prime and the modulus value is a prime number,
• obtain a pair of indices (si, ti) for a component (ai) of an addition chain for a reduced modulus value (p−2), the reduced modulus value have a value two less than the modulus value, the indices identifying a pair of pervious components of the addition chain which, when summed, equal the component of the addition chain, wherein the addition chain has a length l, and
• output a modular inverse (y) of the target integer, wherein the modular inverse is generated by computing the exponentiation of x to the reduced modulus (p−2) using an addition chain by:
• computing a sequence of l multiplier values, wherein a first multiplier value of the sequence of multiplier values is equal to the target integer, a second multiplier value of the sequence of multiplier values is computed, and for each component of the addition chain for 3≤i≤1, a respective multiplier value of the sequence of multiplier values is iteratively computed, each respective multiplier value being the target integer (x) exponentiated by the component of the addition chain, each respective multiplier value being calculated by:
• selecting from a stack the multiplier values associated with the pair of previous components of the addition chain;
• multiplying the selected multiplier values to generate the respective multiplier value for the component;
• and
• pushing the generated multiplier value to the stack;
• and
• for i=l, computing a remainder of the multiplier value with respect to the modulus value (p), wherein the modulus of the multiplier value with respect to the modulus value (p) is output as the modular inverse (y);
• and
• outputting the first script for inclusion in the first blockchain transaction.

A computer program embodied on non-transitory computer-readable storage media and configured so as, when run on one or more processors, the one or more processors perform a method for enabling elliptic curve arithmetic to be performed using blockchain transactions, wherein the method is performed by a script generator and comprises:

• generating a first script of a first blockchain transaction, wherein the first script comprises a modular inversion script, and wherein the modular inversion script is configured to, when executed, by a script engine:
• obtain a target integer (x) and a modulus value (p), wherein the target integer and the modulus value are co-prime and the modulus value is a prime number,
• obtain a pair of indices (si, ti) for a component (ai) of an addition chain for a reduced modulus value (p−2), the reduced modulus value have a value two less than the modulus value, the indices identifying a pair of pervious components of the addition chain which, when summed, equal the component of the addition chain, wherein the addition chain has a length l, and
• output a modular inverse (y) of the target integer, wherein the modular inverse is generated by computing the exponentiation of x to the reduced modulus (p−2) using an addition chain by:
• computing a sequence of l multiplier values, wherein a first multiplier value of the sequence of multiplier values is equal to the target integer, a second multiplier value of the sequence of multiplier values is computed, and for each component of the addition chain for 3≤i≤1, a respective multiplier value of the sequence of multiplier values is iteratively computed, each respective multiplier value being the target integer (x) exponentiated by the component of the addition chain, each respective multiplier value being calculated by:
• selecting from a stack the multiplier values associated with the pair of previous components of the addition chain;
• multiplying the selected multiplier values to generate the respective multiplier value for the component;
• and
• pushing the generated multiplier value to the stack;
• and
• for i=l, computing a remainder of the multiplier value with respect to the modulus value (p), wherein the modulus of the multiplier value with respect to the modulus value (p) is output as the modular inverse (y);
• and
• outputting the first script for inclusion in the first blockchain transaction.