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
4. MPC and Private Bridges
5. 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.
4. 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\)
5. 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)\):

First step:

Second step:

Third step:

Fourth step:

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}\)
2. Parties compute \([x]-\sum_{i=0}^{l-1}{\sum_{j=0}^{n-1}{[r_i^j]2^i}}\in \mathbb{Z}_M\)
3. CP's open \(c=x-r\in \mathbb{Z}_M\)
4. 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? )