---
title: Private Blockchain Bridges
tags: Templates, Talk
description: Retreat Italy 2022 - Anoma - PBB
type: slide

---

# Private Blockchain Bridge

## Iraklis Leontiadis
https://leontiad.github.io/

Anoma Summer Retreat 2022

---

# Walkthrough
1. Bridges
2. Private bridge
3. How MPC is used in secret computing
5. MPC and Private Bridges
6. Challenges

---

# Blockchain Bridges


---

## What is a Bridge

1. Facilitates interopability/communication between two or more blockchains
2. Enable cross chain transactions
3. From siloed to a more connected ecosystem
4. Users can exchange data betweeen two blockchains

---

## Bridge Types

1. Chain specific (Avalanche, Polygon)
2. Asset specific (wBTC)
3. Agnostic/Generalized (IBC)
4. Trusted/Non-trusted

---

## Cross-chain Bridge Flow (lock&mint)
Alice wants to transact from A(token) to B(token) chains:
1. Initiates a local transaction with $a$ tokens at the source chain A in a specific address.
2. Relayers/Validators/Smart contract lock those $a$ tokens.
3. Equivalent $b$ token of type B are minted at the destination chain B.
4. Alice wallet contains $b$ tokens of type B.

---

## Backward leftovers
Alice wants transfer the leftovers from B(token) to A(token) chains:
1. Leftovers are burnt on B
2. Relayers/Validators/Smart contract mint equivalent A tokens in chain A

---

# Private Blockchain Bridges (PBB)

---

## Private Bridge

* Perform cross-chain transactions without inspecting data
* Total amount remain private both ways:
A->B, B->A

---

# Generic MPC

---

## Arithmetic Secret Sharing (ASS)
How to compute on encrypted data?
* Split data input x in shares [.] such that $\sum{[.]}=x$ and give each party one share.
* Addition/subtraction comes for free

---

## Example ASS

* 2 computing parties A and B.
* 2 input parties U1 and U2 with $v1=5, v2=4$
* U1 secret shares $v1$: $[v1]_A=3$, $[v1]_B=2$
* U2 secret shares $v2$: $[v2]_A=1$, $[v2]_B=3$
* Addition: A: $x=[v1]_A+[v2]_A = 4$
* Addition: B: $y=[v1]_B+[v2]_B = 5$
* $x+y = v1+v2 = 9$

---

## Multiplication
\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.
$q2,q3$ ?

---

## Beaver triplets
* 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$.

---

## Beaver triplets

\begin{align*}
& 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{align*}

---

## MPC Security

* Privacy holds as long as colluding assumptions are respected (full thresold or variations thereof)
* Information/Statistical security. ($[r],[x-r]$ for random $r$)
* Good randomness during secret sharing

---

## Comparison circuit:

* $4$ bits register
* $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}

---

## Comparison algorithm
1. Find 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$

---

## Bitwise Arithmetics

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.

---

3. 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. Inner product of $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$

---

## From numbers to bits
* Instead addition secret sharing perform xoring
* $[x1]xor[x2] = x$
* XOR comes for free (Additions in the ring)
* NOT comes for free (flip bits)
* AND needs beaver triplets (multiplication)

---

## BitDecomposition

Input: Each $CP_i$ holds a share $[x]_M$ of $x$
Output: Each $CP_i$ holds a share $[x]_2$ of bit $x$
$[a]_i^j$: secret share of the $i$th bit of $x$ held by party $j$

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^j]2^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}]$

---

## MPC and PBBs
Building Blocks
* The chain of computations in a PBB:
* Counting->Comparing
* Secure Addition
* Secure Multiplication
* BitDecomposition
* Secure comparison

---

# Challenges

1. If all validators collude they can reveal all the private information which is secret shared.
2. Validators might collude under the table.
3. Can we enforce/incentivize correct behavior, otherwise slashed?

---

# Future Work

#### Engineering:

* Evaluate the vanilla protocol with passive security, full threshold and a trusted dealer.
* Compare it with the subtraction protocol
#### Research:
* Validate user input
* What stops a malicious user adding gibberish but welformed data to the counter?
* How validators prove correct MPC execution (MPC ZKP: How to prove correct execution of a value being shared among parties? )