# Private bridging
[TOC]

## Plaintext bridge (relay) flow (Outdated)
> Here, I am unwrapping more the logic without privacy as digested from IBC relayers for my own understanding of the workflow.
1. Blockchain A with tokens a,b,c
2. Blockchain B with tokens d,e,f
3. User U from blockchain A with N tokens of type **a** wants to exhange n **a**'s for m **d**'s within a transaction object, $td$.
4. A sends a message to B
5. B opens the message and sends back an ack
6. A burns n tokens and sends a proof(what is that proof?) that those tokens have been actually burnt. Certificate of transaction is sent.
7. B validates the proof and creates a voucher which authorizes the creation of m **d**'s to bc B and are equivalent to n **d**'s of bc A.

> Q:How those messages are sent actually since those are two different blockchains with different Consensus and state machines rules ? Who is transporting the packages/messages?

> A: The relayers are responisble to act as the transporters of packages messages between A and B. Those relayers are light-clients who perform validations and orchestrate the networking between A and B. They are not full nodes in the sense that they do not need to download the entire state but they can still validate/verify

> A has each own light-client LC-A and B has each own LC-B
> All LCs constitute the relayer/bridge logic

> Seems like those relayers are centralized components who hold logic for cross chain transactions.

> IBC world: client, connections, channels, ports, and packets:
* https://github.com/informalsystems/ibc-rs
* https://github.com/informalsystems/hermes-hackatom-demo
* https://github.com/informalsystems/hermes-ibc-workshop
* https://hermes.informal.systems/

Chain A <--------------------> **LC-A<->LC-B**<------------------>Chain B
Client

create_client(type b on chain A and type a on chain B)
update_client
https://github.com/informalsystems/hermes-ibc-workshop/blob/main/docs/clients.md

## Bridges (Functionality goal: Transfer tokens from bc A to bc B, with privacy)
1. Blockchain A with tokens a,b,c
2. Blockchain B with tokens d,e,f
3. User U from blockchain A with N tokens of type **a** wants to exhange n **a**'s for m **d**'s within a transaction object, $td$. That is:
4. Blockchain A keeps balance sheet for total amount (total outstanding balance) of transactions that happen from A to B for all tokens of A: a,b,c. Lets call those balance sheets **BSa**, **BSb** and **BSc**. Those BS's are encrypted with the public key of the blockchain(Q:since anyone can encrypt and send encrypted balances, how the system preserves malicious entities be it users, or the blockchain itself just sending incorrect balances from transactions that do not exist?)
5. U encrypts transaction data: *token type:tt* ,*token amount: ta* with the public key of the blockchain A **pkA**: $E_{pkA}(td) = C_{td}$. The bridge module in blockchain A, updates the state of **BSa** with $C_{td}$ in a private way such that the BS keeps the correct encrypted amount.
6. U publishes note commitment to blockchain A that includes `(d, amount, recipientAddress)` marked as to-be-sent (cross-chain transaction) to blockchain B, and U provides a proof that `amount == ta` from the encrypted amount in the previous step.
7. Blockchain B is informed by the relayer (who copies the note commitment and light client proofs) that the transaction on Blockchain A happened (blockchain B can check the light client proofs) and now that user needs to mint in total m tokens of type **c**.(Q: where the information that user U owns those c tokens is recorded? in bridge A, bridge B or both?)

On the way back, if U sends token `d` back to blockchain A, where token `d` on blockchain B corresponds to token `a` on blockchain A, blockchain A, when it receives a new note commitment from blockchain B over the bridge which contains `a` tokens, will decrement the **BSa** encrypted counter and check that it is non-negative (thus preventing blockchain B from sending more token `a` back than it was originally sent by blockchain A).

---

## Private Counters

### MPC Approach:
1. Each user additively secret shares the value $tv$ inside a $\mathsf{tx}_{cross}$ transaction with validators responsible to act as *watchdogs* for the counter.
2. For $i=0..n-2$, where $n=$ #validators, U picks random numbers $r_i$ and distributes one $r_i$ to each validator $v_i$. Finally it computes $$r_{n-1} = tv - \sum_{i=0}^{n-2}{r}_i$$ and distributes it to the last validator $v_{n-1}$
Observe that the sum of all shares $r_i, 0 \le i \le n-1$ equals the total value $tv$. There is full threshold security here: All validators need to collude to reveal $tv$.
3. Correctness of shares: We assume at the first version that secret shares are computed correctly (does that sound very powerful assumption? If user U secret shares gibberish data what can go wrong?Is that captured at a later stage? Can we force user to produce proofs that secret share equal the $tv$ that has been part of the commitment? We need a protocol as follows: User(prover) secret shares $r_i, 0 \le i \le n-1$ sum to $tv$ without revealing $tv$ and $tv$ is input to a note where a commitment has been put on the MT. )
4. For additive properties (accumulating the total balance) additive secret sharing over a group is fine but for comparison we need to transform additive shares to boolean (edaBits/daBits: https://eprint.iacr.org/2021/119.pdf, https://mkskeller.github.io/files/programming.pdf). The general idea is: to check whether $x<y$ we check whether $x-y<0$. If subtraction result is negative it is equivalent to $x<y$ otherwise when $x>y$ the subtraction is a positive number. It suffices to check only the sign of the subtraction which can be done by extracting the MSB of $x-y$ and check in two complement's notation.
5. Having additively secret shares of two numbers in $Z_N: [x]_{Z_N}$ and $[y]_{Z_N}$ perform:
* perform subtraction and publish $[z] = [x-y]$
* run $\mathsf{bitDecompose}$ to $[z]$ such that $z$ is been shared with boolean shares in $Z_2$
* run $\mathsf{MSBExtract}([z]_{Z_2})$ )

#### Plaintext example:

Assume we are in a $4$ digits register computer for simplicity and $a = 0010(2)$ and $b = 0100(4)$. $b[i]$ denotes the ith bit of $b$ starting rightmost from position $0$, i.e:$b[0]=1, b[1] = 0$ , etc. We want to compute the function:

\begin{equation}
f_{<}(a,b) =
\begin{cases}
0 & \text{if a>=b }\\
1 & \text{otherwise}\\
\end{cases}
\end{equation}

In their bit decomposition thinking in big-endian machines(most significant bit is leftmost) we are looking to extract the the first leftmost bit where two numbers first differ. Obviously whichever's number bit is 0 at that position is less than the other one. So the task of comparing two numbers in their bit decomposition is reduced into:
1. finding the first position $p$ where the numbers start to differ starting from the most significant part (leftmost part)
2. Extract from both numbers their bit at position $p$
3. if $b[p]==0$ then $a<b$

In bitwise arithmetics the above algorithm is translated as follows:
1. Compute bitwise XOR of $a$ and $b$ and store it to $c$. That will result in a bit vector where at $0$ positions $a$ and $b$ are equal and at $1$ positions they differ.
2. Compute the OR of each bit of $c$ starting from the leftmost bit and store it to $d$.
$d[l-1]=c[l-1],\\
d[l-2]= d[l-1] \lor c[l-2]$,...
That results in a bit vector of $0$'s followed with $1$'s starting at the position where $a$ and $b$ started to differ from leftmost.
1. Perform component wise subtraction at vector $d$ starting leftmost as in the previous step and store it in $e$. That will result in a bit vector with only a single $1$ at the position where $a$ and $b$ started to differ from leftmost.
2. Sum all individual bits of the value $b$ with $e$. $e$ is a one bit vector so that operation extracts the bit value of $b$ in that positions where $e[i]=1$
3. Finally\begin{equation}
\sum{b\cdot e} =
\begin{cases}
0 & \text{if a>=b }\\
1 & \text{if a<b}\\
\end{cases}
\end{equation}

**Running example$f_<(a=2,b=4)$**:

| position | 3 | 2 | 1 | 0|
| -- | - | - | - | - |
| $a$ | 0 | 0 | 1 | 0|
| $b$ | 0 | 1 | 0 | 0|

First step:
| $a$ xor $b$ | 3 | 2 | 1 | 0|
| -- | - | - | - | - |
| $c$ | 0 | 1 | 1 | 0|

Second step:

| or $c$ | 3 | 2 | 1 | 0|
| -- | - | - | - | - |
| $d$ | 0 | 1 | 1 | 1|

Third step:

| subtruct d | 3 | 2 | 1 | 0|
| -- | - | - | - | - |
| $e$ | 0 | 1 | 0 | 0|

Fourth step:
| $b\cdot e$ | 3 | 2 | 1 | 0|
| -- | - | - | - | - |
| $f$ | 0 | 1 | 0 | 0|

Fifth step:
$r= \sum{f[i]} =1$ so output 1, meaning $a<b$, which is true: $2<4$

**Multiplicative shares**
* OR and AND gates require multiplication circuit which cannot be computed separately by the existing additive shares parties hold.
* E.g: Two computing parties $A$ and $B$ and two users $U1$ and $U2$ with two values $v1=5, v2=4$, respectively. $U1$ secret shares $v1$ with $A$ and $B$ giving $A$ $[v1]_A=3$ and to $B$ $[v1]_B=2$. $U2$ respectively secret shares $v2$ giving $A$ $[v2]_A=1$ and to $B$: $[v2]_B=3$ Notice that without colluding $A$ and $B$ know nothing about the values $v1$ and $v2$. $A$ and $B$ can do any computation requires addition/subtraction locally: meaning without the need of extra secret from additional parties or extra communication:
$$v1+v2=[v1]_A+[v1]_B+[v2]_A+[v2]_B$$

* A computes $[v1]_A+[v2]_A$ and reveals it, $B$ accordingly computes $[v1]_B+[v2]_B$ and reveals it and now anyone can compute $v1+v2$.
* multiplition only from additive shares does not work:
\begin{equation}
\begin{split}
([v1]_A+[v1]_B)\cdot([v2]_A+[v2]_B) & = [v1]_A\cdot[v2]_A\\&+[v1]_A\cdot[v2]_B\\&+[v1]_B\cdot [v2]_A\\&+[v1]_B\cdot [v2]_B
\end{split}
\end{equation}
Setting :
$q1=[v1]_A\cdot[v2]_A$
$q2=[v1]_A\cdot[[v2]_B$
$q3=[v1]_B\cdot [v2]_A$
$q4=[v1]_B\cdot [v2]_B$

$q1$ and $q4$ can be computed locally by $A$ and $B$ respectively but $q2$ and $q3$ not because parties hold additive shares and sharing any of the shares from A to B and vice versa is not allowed as it will reveal parties' values in cleartext.

Here is beaver trick:
* Imagine an imaginary party choosing uniformly at random $a, b$ and $c$ such that $a\cdot b = c$ and additively secret shares all values $[a],[b]$ and $[c]$ with $A$ and $B$.
* A and B compute locally: $d=[v1]-[a]$ and $e=[v2]-[b]$ and reveal $e$ and $d$ which are perfectly hiding $v1$ and $v2$.
* Both compute:

\begin{equation}
\begin{split}
d\cdot[v2]+e\cdot[v1]+[c]-e\cdot d& =\\
(v1-a)\cdot[v2]+(v2-b)\cdot[v1]+[c]- (v1-a)\cdot(v2-b) &= \\
[v1\cdot v2]-[a]\cdot[v2] +[v1\cdot v2]-[b]\cdot [v1] +[a]\cdot[b]-[v1\cdot v2]+[b]\cdot[v1]+[a]\cdot[v2]-[a]\cdot[b]&= \\
[v1\cdot v2]
\end{split}
\end{equation}

## Full protocol with passive security and honest users
### Architecture
* A lot of users: $\mathsf{U}$'s wishing to perform cross chain transactions from A to B blockchains.
* Some validators being deployed by anoma, running anoma software: $\mathsf{V}$.
* A smart contract controlled by the target blockchain B: $\mathsf{SC}$
* A subset of validators called MPC computing parties ($\mathsf{CP}$'s) responsible for the bridging protocol act as MPC computing parties receiving the secret shared data inputs by the user.
* A locking account on issue blockchain A acting as a vault: $\mathsf{Vault}$

### Phases
* Issue():
* Redeem():

### Asssumptions
* A trusted dealer distributing correlated randomness and not communicating with CPs during online phase (when data are secret shared among CPs which also hold the correlated randomness)
* Fixed set of $n$ CP's which are available at the beginning of a computation period. We assume parties are fixed within a computation period and

### Description

#### Building Blocks
* $[x] \leftarrow \mathsf{SShare}$($x$,n): holding private data input $x$. Run my the user U hTakes as input the integer number$x$ than needs to be protected and the number of CP's n and returns secret shares of $x$, $[x]$, such that $\sum_{i=0}^{n-1}{[x_i]_M}=x$.
For $i=0..n-2$, where $n=$ #CP, U picks random numbers $r_i$ and distributes one $r_i$ to each CP $v_i$. Finally it computes $$r_{n-1} = x - \sum_{i=0}^{n-2}{r}_i$$ and distributes it to the last CP $v_{n-1}$

* $[x+y]_M \leftarrow \mathsf{SAdd}$($[x]_M,[y]_M$): Non interactive protocol where CP's locally add their share for $[x]$ and $[y]$ and every one publishes $[x+y]$. Finally an aggregator add all shares and reveals $x+y$.

* $[x*y]_M \leftarrow \mathsf{SMul}$($[x]_M,[y]_M$):Beaver

* $[x]_2 \leftarrow \mathsf{bitDecompose}$($[x]_M$): Parties hold arithmetic secret shares of $x$ which is an $l$-bit number, denoted as [x] in its secret shared form and they wish without revealing x to secret share each bit of $x:a_{l-1},a_{l-2},...,a_0$ with secret shares of the bit vector [a] in $Z_2$ such that $x=\sum{a_i2^i}$. We denote with $[a]_i^j$ the secret share of the $i$th bit of $x$ held by party $j$, $0\le j \le n-1$, $0 \le i \le l-1$

:::info
Input: Each $CP_i$ holds a share $[x]_M$ of $x$
Output: Each $CP_i$ holds a share $[x]_2$ of bit $x$

---
1. Each CP secret shares a $l$ random bit $r_i$ with all other parties such that no one knows $r=\sum{r_i2^i}$
1. Parties compute $[x]-\sum_{i=0}^{l-1}{\sum_{j=0}^{n-1}{r_i^j2^i}}\in \mathbb{Z}_M$
1. CP's open $c=x-r\in \mathbb{Z}_M$
1. CP's bitwise compute $[x_{l-1}],...,[x_0] = c_{l-1}+ [r_{l-1}],...,c_{0}+ [r_{0}]$
:::

* $\mathsf{MSBExtract}([z]_{Z_2})$

### Analysis
#### Security
#### Efficiency

**Disadvantages**: Threshold assumptions might be a bit wavy: If all validators collude they can reveal all the private information which is secret shared. Can we make assumptions on that as in research papers that all parties cannot collude? Validators might collude under the table. Can we enforce/incentivize correct behavior, otherwise slashed?

**Challenges**:
1. How input is validated from users being potentially malicious? What stops a malicious user adding gibberish but welformed data to the counter? https://www.usenix.org/system/files/conference/nsdi17/nsdi17-corrigan-gibbs.pdf
1. How validators prove correct MPC execution
* https://www.usenix.org/system/files/sec22fall_ozdemir.pdf
* https://arxiv.org/pdf/2107.04248.pdf

**To study:**
1. https://eprint.iacr.org/2019/017.pdf
1. https://eprint.iacr.org/2019/188.pdf

## Transaction Execution a la Zerocash

A transaction Tx:=snd,rcv,ic,oc, where ic equals the input coins and oc the output coins.

Zcast checks in private way:
1. Check that ic is active
2. Check that Tx sender is authorized
3. Check that value at ocj is preserved: ocj.amount=ici.amount

With a ZKP:
Sender sends commitments cm1 corresponding to ic and cm2,cm3,... corresponding to output coins and computes a zkp:
1. Open commitment cm1
1. Show that cm1 $\in$ CMTree
1. sn1 $\in$ to non spent Tree
1. cm2+cm3+...+cm3 underlying values correspond to cm1
1. Check that signature of Tx is by sender.pk


:::warning

**Create_Address():**
>Each address comes with a public and secret key computed as follows:

1. secret address key $a_{sk}$ is chosen at random by user $U$
2. public key of the adress is $a_{pk}=PRF_{a_{sk}}(0)$
3. $U$ also choses public secret keys for public key encryption scheme $E$, which is key private(looking ciphertexts cannot tell the the public key under which have been encrypted): $\mathsf{pk}_{enc},\mathsf{sk}_{enc}$

>Now somebody knowing $a_{sk}$ can assign a coin $c$ of value $v$ to that address or can use $a_{pk}$ as target for payments.

:::

:::info
**Create_Coin(v,$a_{sk}$)->c,cm:**
>To mint a token $\mathbf{c}$ of value $v$, U proceeds as follows:
1. Choose $\rho$ at random
2. Compute $\mathsf{sn}=PRF_{a_{sk}}(\rho)$
3. Commit to ($a_{pk},v,\rho$) in two phases to hide public key:
i. $k = \mathsf{COMM}_r(a_{pk},\rho)$, for a hiding/binding commitment $\mathsf{COMM}$ with randomness $r$.
ii.$\mathsf{cm} = \mathsf{COMM}_s(k,v)$
1. Coin is defined as $\mathbf{c} = (a_{pk},r,\rho,v,s,\mathsf{cm})$
e. transaction for that minting is $\mathsf{tx}_{mint} = (\mathsf{cm},v,k,s)$. Anyone can verify that $\mathsf{cm}$ contains a coin of value $v$ as long as $U$ deposited coins of value $v$. \mathsf{cm} is added to the merklee tree with root rt.

>The nested commitment preserves anonymity of the the user since its public key is not explicitely part of the transaction but still anyone can verify that this was part of a valid pk unwrapping membership proofs. Transaction is also untrackable since serial number is hidden insiden $k$ - as such when $U$ sends that coin it cannot track it.
>
:::
:::success

**Spend/Pour_Coin(c,$a_{sk}$):**
>Owner of $a_{sk}$ who has minted coin $\mathbf{c} = (a_{pk},r,\rho,v,s,\mathsf{cm})$ wishes to spend/send it to a new address:
1. $U$ proceeds with rerunning Create_Coin(v,$a_{sk}$) twice for $v1$ and $v2$ such that $v=v1+v2$ creating two new coins:
* $\mathbf{c1} = (a_{pk1},r1,\rho_1,v1,s1,\mathsf{cm1})$
* $\mathbf{c2} = (a_{pk2},r2,\rho_2,v2,s2,\mathsf{cm2})$
and the corresponing commitments:
* $k1 = \mathsf{COMM}_r1(a_{pk1},\rho1)$
* $k2 = \mathsf{COMM}_r2(a_{pk2},\rho2)$
* $\mathsf{cm1} = \mathsf{COMM}_s1(k1,v1)$
* $\mathsf{cm2} = \mathsf{COMM}_s2(k2,v2)$

1. $U$ proves in ZK with $\pi_{pour}$ proof the followings:
1. $\mathsf{cm}$ was part of the rt
2. $v=v1+v2$
3. $\mathsf{sn}$ was created correctly in $\mathsf{sn}=PRF_{a_{sk}}(\rho)$
4. $a_{pk}$ was created correctly in $a_{pk}=PRF_{a_{sk}}(0)$
5. commitments for c: k, cm were correct by opening them
6. $\mathsf{cm1}$ and $\mathsf{cm2}$ are correct

Finally pour transaction is created as follows:
$\mathsf{tx}_{pour} = (rt,\mathsf{sn},\mathsf{cm1},\mathsf{cm2},\pi_{pour})$

:::
:::danger

**Send($r,\rho,v,s,\mathsf{pk}_{enc},a_{pk}$):**
> Owner of $(r,\rho,v,s)$ coin who has pured it running the Spend/Pour_Coin wishes to send his coin to the address defined by $a_{pk}$ in a private manner without exposing the values of the coin that identify its value or old owner.

1. Compute ciphertext $C = E_{\mathsf{pk}_{enc}}(r,\rho,v,s)$
2. Put it on the ledger as part of the $\mathsf{tx}_{pour}$ transaction

:::

The above works for one token type and is different from Zcash (need to digest the differences)