OEP: native contract for elliptic curve arithmetic, pairing check and zk-SNARKs

[kunxian-xia]

  OEP: 
  Title: Native contract for elliptic curve arithmetic and SNARK verification
  Author: Kunxian Xia
  Type: Standard
  Status: Draft

==Abstract==

This proposal aims to add native contracts for elliptic curve arithmetic, i.e. point addition and scalar multiplication, on a specific pairing-friendly elliptic curve. Besides, this proposal also outlines a native contract for zk-SNARKs verification.

The contracts in this proposal will make it possible to write a privacy-preserving smart contract on Ontology.

==Motivation==

==Specification==

We propose to have the following methods in a native contract:

• ECAdd
• ECMul
• TwistECAdd
• TwistECMul
• PairingCheck
• PHGR13Verify

The first two methods(i.e. ECAdd and ECMul) are used to do elliptic curve arithmetic on the base curve E.
The second two methods(i.e. TwistECAdd and TwistECMul) are used to do elliptic curve arithmetic on the twisted curve E'.

The fifth method is used to check a relation between an array of points on the base curve E and points on the twisted curve E'.

The last method is used to check if a zk-SNARKs proof is valid. And the concrete protocol we use is the well-known PHGR13 scheme.

===Curve===

We only support one pairing-friendly curve, namely, the alt_bn128 curve which is used in several projects such as ZCash and Ethereum.

The base curve E is defined by

y^2 = x^3 + 3 over the field F_p where p is a prime and
p = 21888242871839275222246405745257275088696311157297823662689037894645226208583

The base curve E' is defined by

y^2 = x^3 + 3/(i+9) over the field F_p^2 = F_p[i] / (i^2 + 1) 

===Encoding===

The elements from field F_p are encoded as 32 byte big-endian numbers. The elements from field F_p^2 are of the form x + y*i with x, y are elements from F_p.

Scalars are encoded as big-endian numbers.

The points on the base curve E are encoded as a pair (x, y) with the point at infinity is encoded as (0, 0).

The points on the twisted curve E' are encoded as a pair (x, y) with the point at infinity is encoded as (0, 0).

===ECAdd and ECMul===

The signature of ECAdd method is

Method name: "ECAdd"
Input: two points P, Q on E
Output: P + Q

The signature of ECMul method is

Method name: "ECMul"
Input: point P on E, and scalar k
Output: k*P

===TwistECAdd and TwistECMul===

The signature of TwistECAdd method is

Method name: "TwistECAdd"
Input: two points P, Q on E'
Output: P + Q

The signature of TwistECMul method is

Method name: "TwistECMul"
Input: point P on E', and scalar k
Output: k * P

===PairingCheck===

The signature of PairingCheck method is

Method name: "PairingCheck"
Input: (a1, b1, ..., ak, bk) where ai are elements in E and bi are elements in E'
Output: e(a1, b1) * ... * e(ak, bk) == 1 

==Rationale==

==Backwards Compatibility==

==Test Cases==

==Implementation==