# Privacy¶

## Upperlink¶

**Overview**

Upperlink provides strong transaction privacy for participants, public verifiability and privacy-preserving auditing capabilities. It hides amounts, participants and links between transactions while allows any party to receive reliable answers to its queries. Only the time of transactions and the type of asset being transferred are public. All participants in Upperlink can still verify transactions are maintaining financial invariants.

In our setting, a participant does not broadcast details of a transaction in the clear. Instead, they post Pedersen commitments to the overlay ledger, which are additively homomorphic. (See Pedersen commitments). They allow Upperlink support a useful set of auditing primitives including sums, moving averages, variance, standard deviation, and ratios. Pedersen commitments are also perfectly hiding and computationally binding, i.e. a commitment doesn’t reveal anything about the committed value and an adversary can only use another value to open a commitment if she breaks the discrete logarithm problem.

Every participant can confirm that any transaction maintains overall integrity via the following invariants:

- Proof of balance: Transfer transactions cannot create or destroy assets
- Proof of assets: Assets are only transferred with the spending participant’s authority and the spending network must own enough of the particular asset to execute the transaction.
- Proof of range: Commitment values are in an elliptic curve group and rely on modulus. Range proofs are used to show that values are within a range.

Upperlink relies on non-interactive zero-knowledge proofs to make privacy-preserving assertions about the ledger. Specifically, we use the Schnorr NIZK and the Bulletproof protocols for our zero-knowledge proofs of knowledge of a value and a range, respectively.

Each private transfer transaction contains:

- A Pedersen commitment to the transferred value.
- A publicly verifiable audit token that enables a participant to show that the asset total is correct without actually needing to know the random input used to create the commitment.
- A proof of consistency: The same random input was used to generate the value commitment and the tokens.
- A proof of balance: A zero-knowledge proof asserting that the committed values satisfy \(sum_{k=1}^n v_k = 0\)
- A proof of assets: A new commitment and a zero-knowledge proof asserting that the committed value transferred is in an acceptable range and the spending participant owns enough of the asset transferred.

Transfer transactions may contain additional metadata in plaintext or encrypted.

## 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)\):

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.