# Private Asset Bridges

## Setup

- Chain A with native asset of type T
- Chain B with a bridged-version of asset T, that is only minted when T assets are moved to a special account (representing Chain B) on Chain A
- Asset bridge from Chain A to B: move assets from A to B as well as B to A
- Chain A and B both assumed to have DKG setups, e.g. Ferveo. Chains have public keys $pk_A$ and $pk_B$ respectively.
- Chain A use ZCash-like system to keep track of T assets, where values are committed to homomorphically (e.g. Pedersen).
- Core restriction: Chain B cannot run a client of Chain A directly, i.e. chain B cannot maintain an account on Chain A natively. Therefore, Chain A maintains a special account for outgoing funds to Chain B.
- Core problem: make sure T assets of chain A does not inflate even if Chain B fail to balance.

## Sketch of a private bridge

(Wei: this is my interpretation of the construction proposed by @cwgoes during Crypto retreat)

- Construction hides transfer amount, but not asset type (for now)
- Fix an homomorphic encryption scheme, say modified ElGamal, where $Enc_{pk}(m; r) := (g^r, pk^r \cdot g^m)$. (This could be any additive homomorphic encryption scheme.)
- Chain A keeps track of encrypted balance of outstanding T-assets that is transferred to chain B, $Bal_T = Enc_{pk_A}(bal)$, which is initialized to $Enc_{pk_A}(0)$.
- A private bridge transfer from A to B of amount k need to: (1) spend a note (revealing a value commitment of the form $C_1 = (g^r, h^rg^k)$), (2) add a ciphertext $C_2 = Enc_{pk_A}(k)$ to the encrypted counter $Bal_T$ homomorphically, and (3) prove that the value commitment $C_1$ and the ciphertext $C_2$ encode the same value.
- A private bridge transfer from B to A of amount k: chain B tells chain A to (1) create a new note of type T with value commitment $C_1$, (2) substract $Bal_T$ with some ciphertext $C_2$, and (3) proves that $C_1$ and $C_2$ encode the same value. However, during this step, chain A needs to be convinced that chain B is not creating more asset T, i.e. the encrypted balance is always positive. Chain A runs some protocol $RangeTest(Bal_T, q)$ to verify that the encrypted balance $bal_T$ is in some range $[0, q]$.

## Open question 1: RangeTest protocol

Given an ElGamal ciphertext, $C = (g^r, pk^r \cdot g^m)$, where a set of n validators hold the threshold key shares $s_1, \ldots, s_n$ for public key $pk$. We need a protocol between the validators to decide whether $m$ is in some range $[0, q]$ for some public input q, without revealing $m$ itself. Call this protocol $RangeTest(C, q)$. Validators needs to run $RangeTest(C, q)$ everytime Chain B sends T asset to Chain A.

Related works:
[1] [A Novel Range Test](https://eprints.qut.edu.au/24581/8/A_Novel_Range_Test.pdf)
[2] [An Efficient and Verifiable Solution to the Millionaire Problem](https://eprints.qut.edu.au/24573/1/An_Efficient_and_Verifiable_Solution_to_the_Millionaire_Problem.pdf)
[3] [Efficient Zero-Knowledge Argument for Correctness of a Shuffle](https://link.springer.com/content/pdf/10.1007/978-3-642-29011-4_17.pdf)
[4] [Mix-nets from homomorphic signatures](https://eprint.iacr.org/2019/547.pdf)
[4] [MPC "bit decomposition"](https://www.iacr.org/archive/tcc2006/38760286/38760286.pdf)

### Range Test from [1]

Peng et al. proposed a range test, which *does not* actually work!

### Sketch of protocol (adapted from [1]):
We fix an additive homomorphic encryption scheme. Encryption is denoted $Enc(m)$ where $m \in Z_p$. Every encryption is assumed to use independent randomness. The set of validators together has the ability to decrypt, which is denoted as $Dec(C)$ for a ciphertext $C$. Multiplication of ciphertext is denoted by $C \cdot C'$ (which for ElGamal is done component-wise). Additive homomorphism of the scheme requires that
$$Dec(C \cdot C') = Dec(C) + Dec(C') \mod p \; .$$

We first consider a zero test protocol.

// A protocol between the set of validators
ZeroTest(Z): // test whether Dec(Z) is 0 without revealing the exact message
    Step 1. Samples r from Z_p^* and set Z = Z^r, broadcast new Z
    Step 2. Repeat step 1 for at least threshold number of times
    Step 3. Return true iff Dec(Z) is 0

Step 1 above might require some proof of correctness from validators, but this could simply be an EQDL proof.

**TODO**: Design a more efficient protocol to achieve the same functionality in less rounds.

Next, consider a function `GenC1E1`, parameterized by a distribution D over Z_p, that samples two ciphertexts. Looking ahead, we would want an MPC that simulates `GenC1E1` without revealing the internal values of m1 and encryption randomness.

// GenC1E1 is a function that returns two ciphertexts
// Parameter D is a distribution over Z_p,
GenC1E1():
    Sample m1 from distribution D
    Set C1 = Enc(m1), E1 = Enc(m1 % q)
    Return C1, E1

Finally, we can now consider the RangeTest protocol.

// A protocol between the set of validators
RangeTest(C, q): // test whether Dec(C) ∈ [0, q]
    Run "Threshold MPC" to simulate GenC1E1(D) to obtain C1, E1
    Set C2 = C / C1
    Threshold decrypt m2 = Dec(C2)
    Compute E2 = Enc(m2 % q)
    Compute Z1 = E1 * E2 / (C1 * C2)
    Compute Z2 = E1 * E2 / (C1 * C2 * Enc(q))
    Return ZeroTest(Z1) or ZeroTest(Z2)

**Claim**: the above protocol always return `True` when $Dec(C) \in [-1, q-1]$. Moreover, if the above protocol return `True` then $Dec(C) \in [-q, 2q-2]$.

#### On distribution D
If we are using Paillier encryption, then we can pick D to be uniform over $Z_p$. However, we cannot do this in case of ElGamal. The reason is that computation of Dec(C2) could be hard in case of ElGamal. To make this feasible, we need to restrict the distribution D so that decryption of C2 can be bruteforced. The consequence is that $m2 = m - m1 \mod p$ leaks information about $m$. We would need to pick distribution D carefully so that (1) decryption of C2 is not too hard and (2) information leakage of $m$ is minimized. When brutefoce decryption of `C2` fails, the protocol should return `False` denoting that the encrypted value is not in range.

## Open question 2: Dealing with key updates

Ferveo periodically updates the chain public key. This means that encrypted balances need to be updated every time the chain public key is changed. This re-encryption should be done without decryption. Suppose the master secret $sk$ is updated to $sk'$, then an encrypted balance $Bal = (C_0, C_1)$ needs to be updated to $(C_0, C_1')$ where $C_1' = C_1 \cdot (C_0)^{sk^{-1} \cdot sk'}$. Note that the imtermediate value $C_0^{sk^{-1}}$ cannot be revealed. This should be feasible with existing MPC techniques.

## Open question 3: Hiding Asset Type

The above sketch requires revealing the asset type being transferred, as the validators needs to access the encrypted balance associated with a particular type of asset. Can we design a protocol that also hide which asset type is being transferred?

Potential approach: each transfer modify all encrypted balances for all assets. The transfer initiator needs to prove that all modifications are trivial besides the one corresponding to the note being burnt.