Privacy

Elliptic Curves

An elliptic curve over a finite field \(F\), \(E(F)\), is defined as the set of solutions \((x,y) \in F^2\) of an equation of the form \(y^2 + (a_1 x + a_3) y = x^3 + a_2 x^2 + a_4 x + a_6\), also known as a Weierstrass equation in its long form.

Given a random integer \(k \in F\), we can construct a point \(Q = kP\) from another point in the elliptic curve \(P\). The reversed process, i.e. finding \(k\) given \(P\) and \(Q\), is a problem that is not computable in sub-exponential time. This problem is called the elliptic curve discrete logarithm problem (ECDLP). Elliptic curve cryptography (ECC) is a modern standard for constructing key pairs based on the intractability of the ECDLP.

The curves used in Uplink’s cryptographic protocols are Secp256k1, Curve25519 and BN128.

Pairings

Elliptic curves with a special map called a pairing or bilinear map allow cryptographic primitives to achieve functions or efficiency which cannot be realized otherwise. ZSS signature and broadcast encryption (BE) are examples of such primitives.

The Barreto-Naehrig (BN) family of curves achieve high security and efficiency with pairings due to an optimum embedding degree.

We have implemented the optimal Ate pairing over the BN128 curve, i.e. we define \(q\) and \(r\) as

  • \(q = 36t^4 + 36t^3 + 24t^2 + 6t + 1\)
  • \(r = 36t^4 + 36t^3 + 18t^2 + 6t + 1\)
  • \(t = 4965661367192848881\)

An extension of a field \(F_{q^k}\) can be constructed by successively towering up intermediate fields \(F_{q^a}\) and \(F_{q^b}\) such that \(k = a^i b^j\), achieving significant performance in computation. The tower of finite fields we work with is defined as follows:

  • \(F_{q^2} := F_q[u]/u^2 + 1\)
  • \(F_{q^6} := F_{q^2}[v]/v^3 - (9 + u)\)
  • \(F_{q^{12}} := F_{q^6}[w]/w^2 - v\)

The groups’ definitions are:

  • \(G_1 := E(F_q)\), with equation \(y^2 = x^3 + 3\)
  • \(G_2 := E'(F_{q^2})\), with equation \(y^2 = x^3 + 3 / (9 + u)\)
  • \(G_T := \mu_r\), i.e. the r-th roots of unity subgroup of the multiplicative group of \(F_{q^{12}}\)

Verifiable Computations

A zero-knowledge proof is an encryption scheme by which one party can prove to another party that she knows a private value \(x\) without exposing any information of \(x\)

A verifiable computation in zero knowledge scheme allows a party to outsource to a worker the evaluation of a function and verify that the computation is performed correctly without having to repeat the entire computational process. It doesn’t reveal any detail of the computation either.

Any program can be represented by an arithmetic circuit and verifying the correctness of the computation is equivalent to checking circuit satisfiability on given input and output.

Arithmetic Circuits and QAPs

Arithmetic circuits can be represented as directed acyclic graphs with wires as edges and addition and multiplication gates as vertices. The idea behind the zero-knowledge succint non-interactive arguments of knowledge (zk-SNARK) protocol is to translate a valid circuit assignment into an algebraic property of polynomials, using quadratic arithmetic programs (QAPs).

Let \(C:F^n \times F^h \rightarrow F^l\) be an arithmetic circuit. A valid assignment is a tuple \((a_1, ..., a_N) \in F^N\) such that \(C(a_1, ..., a_{n+h}) = (a_{n+h+1}, ..., a_N)\), where \(N = (n + h) + l\). The role of a Quadratic Arithmetic Program (QAP) in zk-SNARK is to provide the prover with tools to construct the proof \(\pi\) for the claim that he knows a valid assignment \((a_1, ..., a_N) \in F^N\) for a circuit \(C\).

A \(QAP(C) := (\vec{A}, \vec{B}, \vec{C}, Z)\) provides three sets of polynomials \(\vec{A} = (A_0(z), ..., A_m(z))\), \(\vec{B} = (B_0(z), ..., B_m(z))\) and \(\vec{C} = (C_0(z), ..., C_m(z))\), and a target polynomial \(Z(z)\) that divides the polynomial \(P(z)\):

\[P(z) := (A_0(z) + \sum_{i=1}^m a_iA_i(z)) (B_0(z) + \sum_{i=1}^m a_iB_i(z)) - (C_0(z) + \sum_{i=1}^m a_iC_i(z))\]

An assignment \((a_1, ..., a_N)\) is considered valid for a circuit \(C\) if and only if \(Z(z)\) divides \(P(z)\).

zk-SNARK protocol

A worker aims to evaluate a function and prove that he knows an assignment \((\vec{x}, \vec{y})\) with output \(0\) for a certain arithmetic circuit \(C\). The protocol consists on three algorithms usually named as key generation, prover and verifier.

  • Key generation:

    • The QAP must be constructed by a trusted third party from an arithmetic circuit \(C\).

    • A Proving Key \(pk := (pk_A, pk_B, pk_C, pk_H)\) and a Verification Key \(vk := (vk_{IC}, vk_Z)\) are generated from the QAP and some random values \(\tau\), \(\rho_A\), \(\rho_B\):

      \(pk_A := (A_0(\tau)\rho_AP_1, ..., A_m(\tau)\rho_AP_1)\)

      \(pk_B := (B_0(\tau)\rho_BP_1, ..., B_m(\tau)\rho_BP_1)\)

      \(pk_C := (C_0(\tau)\rho_CP_1, ..., C_m(\tau)\rho_CP_1)\)

      \(pk_H := (\tau^0P_1, ..., \tau^dP1)\)

      \(vk_{IC} := (A_0(\tau)\rho_AP_1, ..., A_n(\tau)\rho_AP_1)\)

      \(vk_Z := Z(\tau)\rho_CP_2\)

  • Prover:

    • Construct the QAP \((\vec{A}, \vec{B}, \vec{C}, Z)\) of \(C\), together with \(P(z) := {A(z)B(z) - C(z)}\)

    • Compute a valid distribution \((a_1, ..., a_m)\) from the prover’s valid assignments \((\vec{x}, \vec{w})\)

    • Determine the coefficients \(\{h_0, ..., h_d\}\) of the polynomial \(H(z) = P(z) / Z(z)\)

    • The prover constructs the proof \(\pi := (\pi_A, \pi_B, \pi_C, \pi_H)\). This proof states that the prover knows that \(\vec{x} \in F^n\) is a valid input.

      \(\pi_A := a_{n+1}pk_{A,n+1} + ... + a_mpk_{A,m}\)

      \(\pi_B := pk_{B,0} + (a_1pk_{B,1} + ... + a_mpk_{B,m})\)

      \(\pi_C := pk_{C,0} + (a_1pk_{C,1} + ... + a_mpk_{C,m})\)

      \(\pi_H := pk_{H,0} + (h_1pk_{H,1} + ... + h_dpk_{H,d})\)

  • Verifier:

    • Calculate \(vk_{\vec{x}}=vk_{IC,0} + (x_1vk_{IC, 1} + ... + x_nvk_{IC, n})\)

    • Check QAP divisibility: \(e(vk_{\vec{x}} + \pi_A, \pi_B) = e(\pi_H, vk_Z) e(\pi_C, P_2)\).

      As \(vk_{\vec{x}} + \pi_A = A(\tau)\rho_aP_1\), the pairing equation above is equivalent to \(e(P_1, P_2)^{\rho_A\rho_BA(\tau)B(\tau)} = e(P_1, P_2)^{\rho_cH(\tau)Z(\tau)} e(P_1, P_2)^{\rho_CC(\tau)}\). The non-degeneracy of the pairing \(e\) implies that this equation holds true if and only if \(P(\tau) = H(\tau) Z(\tau)\).

In Uplink we use a practical zk-SNARK compiler that allows a prover to perform efficiently public verifiable computations while relying only on cryptographic assumptions. It allows computationally weak parties to oursource computation to more powerful untrusted workers and verify the results returned. These untrusted workers produce signatures of computation to accompany the result without revealing any information about the input.

The asymptotics are optimal for our use-cases: the key generation and prover step in the protocol require cryptographic effort linear in the size of the original computation, while the verifier step requires time linear in the size of the inputs and outputs. Circuits can also be precompiled to elmininate the cost associated with Lagrange interpolation during construction.

The output proof (\(\pi\)) is 288 bytes, regardless of the size of the computation and the proofs can be verified efficiently, typically in tens of milliseconds.