# FAST
FAST: **F**air **A**uctions via **S**ecret **T**ransactions
:fast_forward:
https://eprint.iacr.org/2021/264
Bernardo David
**Lorenzo Gentile**
Mohsen Pourpouneh
lorg@itu.dk
---
#### MPC intro: Yao's Millionaires' problem
- Introduced in 1982 by Yao: two millionaires, Alice and Bob, are interested in knowing which of them is richer without revealing their actual wealth.
```plaintext
a +--------+
Alice ---> | YAO | f(a,b) = 1 if a > b else 0
b | | --->
Bob ---> | |
+--------+
```
- Compute $f(a, b)$ while preserving the privacy of $a$ and $b$.
- Theoretical result shows that any function can be evaluated on private inputs.
---
### Blokchain intro: Bitcoin
```plaintext
+----------------------+ +----------------------+
| +-------+ +-------+ | | +-------+ +-------+ |
----->| Prev. | | Nonce | |----->| Prev. | | Nonce | |
| | Hash | | (PoW) | | | | Hash | | (PoW) | |
| +-------+ +-------+ | | +-------+ +-------+ |
| +----+ +----+ +----+ | | +----+ +----+ +----+ |
| | Tx | | Tx | | ...| | | | Tx | | Tx | | ...| |
| +----+ +----+ +----+ | | +----+ +----+ +----+ |
+----------------------+ +----------------------+
```
Courtesy of Satoshi Nakamoto (2008)
---
### Blockchain intro: smart contracts
- Smart Contracts allow to describe **arbitrarily complex conditions** under which transactions might take place among the parties.
- FAST adopts a **public** blockchain and smart contracts to achieve **eventual immutability** and **automatically enforce** part of the protocol.
---
#### FAST protocol
- Parties $\mathcal{P}_{i}$ with $i \in {1,...,n}$.
- Bid $b_i = b_{i1}|...|b_{il}$ with $b_{ir} \in \{0,1\}$.
```plaintext
b_1 +--------+
---> | FAST | b_w = max(b_1,...,b_n)
... | | --->
b_n | | P_w sends b_w to the auctioneer
---> | |
+--------+
```
- Compute $max(b_1,...,b_n)$ while preserving the privacy of $b_1,...,b_n$ (similarly for second price).
---
#### Motivation
- It may be **not feasible** or **expensive** to find a trusted third party.
- A third party may cheat, without being detected, to **increase profit** (e.g., increase second price).
---
#### FAST in a nutshell
- Parties send **secret deposits** to a **smart contract**.
- Cheating parties **lost their deposits**.
- **Rational parties do not cheat**.
- **Fairness** is achieved.
---
#### Building blocks
- Secret deposits.
- Anonymous veto protocol.
- Non interactive zero knowledge proofs (NIZKs).
- Cheating detection.
- Recovery committee.
---
#### Secret deposits (novel technique)
- In order to make rational parties do not cheat, **the deposits have to be equal to the bids plus work**.
- However, the **privacy of the bids has to be preserved**.
- Secret deposits are adopted (e.g., using **confidential transactions** by Greg Maxwell).
---
#### Confidential transactions (details)
- Parties $P_i$ with $i \in {1,...,n}$.
- Bid $b_i = b_{i1}|...|b_{il}$ with $b_{ir} \in \{0,1\}$.
- $\mathcal{P}_{i}$ computes the bit commitments as $c_{ir} = g^{b_{ir}}h^{r_{ir}}$ to each bit $b_{ir}$ of $b_{i}$ (used in NIZKs later), and the bid commitment as $c_{i} = \prod_{{r} = 1}^{l} c_{ir}^{2^{l-{r}}} = g^{b_{i}}h^{\sum_{{r}=1}^{l}2^{l-{r}}r_{ir}}$.
---
- $\mathcal{P}_{i}$ send a confidential transacation to the smart contract:
```plaintext
in_i c_i, work
-----> P_i ------------> F_{sm}
---
| com(change_i)
<--
?
c_i*com(change_i) = com(in_i - work)
<=>
in_i = b_i + work + change_i
```
---
- The smart contract verifies the validity of the confidential transaction (**inputs equal to outputs** and **range proofs**).
- $\mathcal{P}_{i}$ verifies for each other party $\mathcal{P}_j$ that $c_j = \prod_{k = 1}^{l} c_{jk}^{2^{l-k}}$ for $j \in \{1,\ldots,n\}\setminus {i}$.
---
#### Anonymous veto protocol
- Parties $P_i$ with $i \in {1,...,n}$.
- Bit $b_i \in \{0,1\}$.
```plaintext
b_1 +--------+
---> | AVP | v = b_1 or ... or b_n
... | | --->
b_n | | if v = 0 no veto
---> | | if v = 1 veto
+--------+
```
- Compute $b_1$ or $...$ or $b_n$ while preserving the privacy of $b_1,...,b_n$.
---
#### Anonymous veto protocol (examples)
```plaintext
0 +--------+
---> | AVP |
0 | | v = 1
---> | | --->
1 | | veto
---> | |
+--------+
0 +--------+
---> | AVP |
0 | | v = 0
---> | | --->
0 | | no veto
---> | |
+--------+
```
---
#### Anonymous veto protocol (details)
- **Round 1.** $\mathcal{P}_{i}$ chooses $x_{i} \stackrel{u}{\leftarrow} \mathbb{Z}_q$ (uniformly at random), computes $X_{i}=g^{x_{i}}$ and broadcasts $X_{i}$.
---
- **Round 2.** Upon receiving $X_j$ from all other parties $\mathcal{P}_j,\mathcal{P}_{i}$ computes
$Y_{i} = \prod_{k = 1}^{{i}- 1} X_{k} / \prod_{k = {i} + 1}^{n} X_{k} = g^{(\sum_{k=1}^{{i} - 1}x_{k} - \sum_{k={i} + 1}^{n}x_{k})}$
and then broadcasts the following message:
$$v_{i} = \left\{\begin{array}{lr} Y_{i}^{x_{i}}, & \text{if $b_{i}=0$} \\ r \stackrel{u}{\leftarrow} \mathbb{Z}_q,g^r, & \text{if $b_{i}=1$} \end{array}\right.$$
---
- **Output.** All parties compute $V=\prod_{{i} = 1}^{n}v_{i}$ after receiving all the $v_{i}$'s from the other parties. Notice that if $b_{i}=0$ for all ${i} \in \{1,\ldots,n\}$ then $V=1$ (no veto), and if $b_{i}=1$ for at least one ${i} \in \{1,\ldots,n\}$ then $V\neq 1$ (at least one veto).
---
#### Anonymous veto protocol (detailed example)
- $n = 3$
- $X_1 = g^{x_1}, X_2 = g^{x_2}, X_3 = g^{x_3}$
- $Y_1 = g^{-x_2-x_3}, Y_2 = g^{x_1-x_3}, Y_3 = g^{x_1+x_2}$
If we assume that $b_{i}=0$ for all ${i} \in \{1,2,3\}$, then:
$V = v_1 \cdot v_2 \cdot v_3 = Y_1^{x_1} \cdot Y_2^{x_2} \cdot Y_3^{x_3} \\ = g^{-x_1(x_2+x_3)} \cdot g^{x_2(x_1-x_3)} \cdot g^{x_3(x_1+x_2)}\\ = g^0 = 1 \Rightarrow \text{no veto}$
---
#### Anonymous first price auction protocol
- (idea) Use bit-by-bit AVP.
```plaintext
b_1 = 1 1 0 1 0
b_2 = 1 1 0 0 1
b_3 = 1 0 1 1 1
---------
v = 1 1 1 1 1 != max(b_1,b_2,b_3)
```
---
#### Anonymous first price auction protocol
- (idea) Modify input bits according to previous inputs and outputs.
```plaintext
b_1 = 1 1 0 1 0
b_2 = 1 1 0 0 0*
b_3 = 1 0 0* 0* 0*
--------------
v = 1 1 0 1 0 = max(b_1,b_2,b_3)
```
- If $v_r = 1$ but $b_{ir} = 0$ then $d_{ik} = 0$ for $k = r+1,...,l$.
---
#### NIZK proofs
- How can we guarantee that the rule "if $v_r = 1$ but $b_{ir} = 0$ then $d_{ik} = 0$ for $k = r+1,...,l$" is followed by the parties?
- Non interactive zero knowledge proofs guarantee that $d_{ir}$ are correctly computed according to the inputs and outputs of the previous rounds.
---
#### NIZK proofs - Before First Veto (details)
$$v_{ir} =
\begin{cases}
Y_{ir}^{x_{ir}} ,& \text{if } b_{ir}= 0 \\
g^{\bar{r}_{ir}} ,& \text{if } b_{ir}= 1
\end{cases}$$
Logical condition to prove:
$(b_{ir}=0 \wedge d_{ir}=0) \vee (b_{ir}=1 \wedge d_{ir}=1)$
---
$$\begin{gathered}
BV_{ir} \leftarrow BV \{ b_{ir},r_{ir}, x_{ir}, \bar{r}_{ir} \mid \\ (\frac{c_{ir}}{g^{b_{ir}}}=c_{ir}=h^{r_{ir}} \wedge v_{ir}= Y_{ir}^{x_{ir}} \wedge X_{ir}=g^{x_{ir}} )
\vee \\
( \frac{c_{ir}}{g^{b_{ir}}}=\frac{c_{ir}}{g}=h^{r_{ir}} \wedge v_{ir}= g^{\bar{r}_{ir}} ) \}\end{gathered}$$
---
#### NIZK proofs - After First Veto (details)
$$v_{ir} =
\begin{cases}
Y_{ir}^{x_{ir}} ,& \text{if } b_{ir}=0\\
g^{r_{ir}} ,& \text{if } d_{i\widehat{r}}= 1 \wedge b_{ir}= 1\\
Y_{ir}^{x_{ir}} ,& \text{if } d_{i\widehat{r}}= 0 \wedge b_{ir}= 1
\end{cases}$$
Logical condition to prove:
$(b_{ir}=0 \wedge d_{ir}=0) \vee (b_{ir}=1\wedge d_{i\widehat{r}}=1 \wedge d_{ir}=1)\vee \\ (b_{ir}=1 \wedge d_{i\widehat{r}}=0 \wedge d_{ir}=0)$
---
$$\begin{gathered}
AV_{ir} \leftarrow AV \{ b_{ir},r_{ir},x_{ir},\bar{r}_{i\widehat{r}}, \bar{r}_{ir},x_{i\widehat{r}} \mid \\
(\frac{c_{ir}}{g^{b_{ir}}}=c_{ir}=h^{r_{ir}} \wedge v_{ir}= Y_{ir}^{x_{ir}} \wedge X_{ir}=g^{x_{ir}})
\vee \\
(\frac{c_{ir}}{g^{b_{ir}}}=\frac{c_{ir}}{g}=h^{r_{ir}} \wedge d_{i\widehat{r}}= g^{\bar{r}_{i\widehat{r}}} \wedge v_{ir} = g^{\bar{r}_{ir}})
\vee \\
(\frac{c_{ir}}{g^{b_{ir}}}=\frac{c_{ir}}{g}=h^{r_{ir}} \wedge \ d_{i\widehat{r}}= Y_{i\widehat{r}}^{x_{i\widehat{r}}} \wedge X_{i\widehat{r}}= g^{x_{i\widehat{r}}} \\ \wedge v_{ir}= Y_{ir}^{x_{ir}} \wedge X_{ir}= g^{x_{ir}}) \}\end{gathered}$$
---
#### Cheating detection
- How can we detect cheating parties?
- NIZK are publicly verifiable.
- Signed messages allow to prove inconsistencies.
- If cheating is detected, a **recovery stage** is executed.
---
#### Recovery committee
- The opening of the confidential transaction
($c_{i} = g^{b_{i}}h^{\sum_{{r}=1}^{l}2^{l-{r}}r_{ir}}$) commited amount is **secret shared** with a committee using **PVSS**.
- In the recovery stage the opening is reconstructed and the **confidential transaction is spent**.
---
#### Extension to second price auction
- (idea) Execute again the protocol without the winning party.
- (better idea) Once the winning party $\mathcal{P}_w$ is identified, conclude the execution to compute the second price without $\mathcal{P}_w$.
- From a game theory perspective, bidding truthfully is a **dominant strategy**.
---
#### Time for questions!
:fast_forward:
https://eprint.iacr.org/2021/264
Bernardo David
**Lorenzo Gentile**
Mohsen Pourpouneh
lorg@itu.dk
{"metaMigratedAt":"2023-06-17T02:53:24.413Z","metaMigratedFrom":"YAML","title":"FAST (shortened)","breaks":true,"description":"View the slide with \"Slide Mode\".","contributors":"[{\"id\":\"d80064c0-9b1a-4455-a2b0-11618ed627cd\",\"add\":11141,\"del\":1308}]"}