# 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 computer scientist Andrew Yao: two millionaires, Alice and Bob, are interested in knowing which of them is richer without revealing their actual wealth.
```
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
```
+----------------------+ +----------------------+
| +-------+ +-------+ | | +-------+ +-------+ |
----->| Prev. | | Nonce | |----->| Prev. | | Nonce | |
| | Hash | | (PoW) | | | | Hash | | (PoW) | |
| +-------+ +-------+ | | +-------+ +-------+ |
| +----+ +----+ +----+ | | +----+ +----+ +----+ |
| | Tx | | Tx | | ...| | | | Tx | | Tx | | ...| |
| +----+ +----+ +----+ | | +----+ +----+ +----+ |
+----------------------+ +----------------------+
```
Courtesy of Satoshi Nakamoto (2008)
---
### Blockchain intro: consensus
- Consensus: all processes have a value and they must agree on only one $\rightarrow$ agreement, validity, termination.
- Fault models: crash, omission, byzantine.
- Network models: synchronous, asynchronous.
Note:
Fault models:
- Crash
- Omission
- Arbitrary or byzantine
Consensus requirements:
- Agreement: every non-faulty process outputs the same value.
- Validity: if all non-faulty processes suggest the same value, that value must be the output value.
- Termination: every non-faulty process eventually outputs a value.
Communication models:
- Synchronous: we know how fast each process is, and how long a message takes to arrive.
- Asynchronous: we do not know either.
---
### Blockahin intro: theoretical results
Under the byzantine fault model:
| | Property | Network model | Result |
|----------------------------|-----------|---------------|---------------|
| Byzantine generals problem | Consensus | Syncronous | $<1/3$ faults |
| FLP-impossibility | Agreement | Asynchronous | Impossible |
Note:
- Byzantine generals problem shows that in order to reach **consensus** in a **syncronous network** a number of **byzantine failures** $< 1/3$ is tolerated at most.
- FLP-impossibility states that it is impossible to reach **byzantine agreement** over an **asynchronous network** in a deterministic number of rounds.
---
### Blockchain intro: eventual consensus
- Blockchain protocols, that assume an **asynchronous network** and **byzantine failures**, guarantee **eventual consensus** only $\rightarrow$ **no guaranteed termination**, **eventual agreement**, **eventual validity**.
Note: It means that at some point all nodes agree on the same old state and that if all non-faulty nodes suggest the same state then they will eventually agree on that state.
---
### Blockchain intro: GKL model
- Blockchain protocol properties in the GKL model:
- Chain Growth
- Chain Quality
- Common Prefix
- Assumption for proving security: the adversary **can control $< 1/2$ of the computational power invested in solving the PoW puzzle**.
Note:
- Chain Growth: the chain will grow with at least constant speed (a constant number of new blocks is added to the chain after a constant number of rounds).
- Chain Quality: given $k$ blocks in a blockchain, at least $c \cdot k$ blocks were generated by honest parties for a constant $c$ with overwhelming probability.
- Common Prefix: the probability that two honest parties see different chains after removing the $k$ last blocks from a chain is negligible in $k$.
---
### 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 $P_i$ with $i \in {1,...,n}$.
- Bid $b_i = b_{i1}|...|b_{il}$ with $b_{ir} \in \{0,1\}$.
```
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$.
---
- 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.
---
#### Secret deposits (novel technique)
- In order to make rational parties do not cheat, **the greater are the bids and the greater the deposits have to be**.
- However, the **privacy of the bids has to be preserved**.
- Secret deposits are adopted (e.g., using **confidential transactions**).
---
#### 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:
```
in_i c_i, work
-----> P_in ------------> F_{sm}
---
| com(change_i)
<--
?
c_i*com(change_i) = com(in_i - work)
<=>
b_i + change_i = in_i - work
```
---
- 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\}$
```
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)
```
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.
```
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.
```
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 $b_{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 $b_{ik} = 0$ for $k = r+1,...,l$" is followed by the parties?
- Non interactive zero knowledge proofs guarantee that $b_{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.
---
#### 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**.
---
#### Security proof sketch $\Pi_{FPA}$
A simulator $\mathcal{S}$ has to perform an ideal execution with $\mathcal{F}_{AUC}$, $\mathcal{F}_{SC}$, a random oracle and an internal copy of the adversary $\mathcal{A}$ indicated with $\mathcal{A}'$ and:
- Generate a view for $\mathcal{A}'$ that is indistinguishable from the view for $\mathcal{A}$ (NIZKs, commitments, veto inputs have to be indistinguishable from the ones in the real world);
---
- Extract the inputs used by $\mathcal{A}$ (the input of $\mathcal{A}$ has to be extracted by $\mathcal{S}$ using NIZKs knowledge extractor);
- Make the simulated view be consistent with the output that is based on the input of $\mathcal{A}$ (NIZKs have to be coherent with the winning bid $b_w$ in the real world);
---
#### Future work
- Can the technique of secret deposits be generalized?
- In which other applications can it be used?
---
#### Time for questions!
:fast_forward:
https://eprint.iacr.org/2021/264
Bernardo David
**Lorenzo Gentile**
Mohsen Pourpouneh
lorg@itu.dk
{"metaMigratedAt":"2023-06-15T15:21:15.954Z","metaMigratedFrom":"YAML","title":"FAST","breaks":true,"description":"View the slide with \"Slide Mode\".","contributors":"[{\"id\":\"d80064c0-9b1a-4455-a2b0-11618ed627cd\",\"add\":27823,\"del\":15100}]"}