Fall 2024

Blockchains, Cryptocurrencies and

Smart Contracts

Lecture 6

Ahmed Kosba

Department of Computer and Systems Engineering

Faculty of Engineering
Alexandria University
Outline
• Bitcoin limitations
• Payment channels
• Using Bitcoin for more complex applications
• Fairness in Cryptographic Protocols
• Introduction to smart contracts

2
Bitcoin Limitations
• Scalability
• Maximum transaction throughput in Bitcoin: ~7 txs/sec.
• Existing centralized financial systems process much higher rate of transactions.
• Transactions are not instantaneous
• Cannot accept a transaction immediately. Have to wait for confirmations.
• Privacy
• Transaction graph could be analyzed.
• Proof-of-work puzzles
• Waste of energy. The puzzle itself is meaningless.
• Limited functionality
• ..
3
Improving Bitcoin
• Increasing transaction throughput
• Faster block generation
• Off-chain payments
• More functionality
• What else can we do with Bitcoin?
• Smart contracts and Ethereum
• Discourage mining centralization
• Use different kind of puzzles/proofs
• Increase privacy
• How can we hide the transaction graph?
4
 The higher the block size, the more time needed for a block
to be propagated to the network.

Scalability
• Naïve Solutions to scalability issues:
• Increase block size?
• Reduce time between blocks?
Both solutions could lead to:

Percentage represents network reachability

Data by Decker and Wattenhofer
[Sompolinsky and Zohar ‘2013]
Most of the miners' efforts are wasted. 5
This can be exploited in attacks.
Accelerated block generation
• Fast money grows on trees [Sompolinsky and Zohar ‘2013]
• Greedy Heaviest Observed Sub-tree (GHOST) protocol
• Rule:
• Pick the heaviest subtree when conflicts occur (instead of the longest chain)

6
Block DAGs
• Instead of a single chain, consider a graph
B F J

C
M
Genesis
H K
D

E L
I

Challenge: How to maintain consistency in this case?

7
Off-chain payments
• Changing the underlying blockchain in a major way might not always
be an option. An alternative is to find compatible solutions.
• Payment Channels
• Handles the majority of transactions off-chain
• Avoids the fees of posting every transaction to the blockchain

• Lightning Network: routes payments through a network of

bidirectional payment channels

• We will cover unidirectional payment channels in this lecture only.

8
 Unidirectional Payment Channels
• Building blocks:
• Multi-signature Address (An output cannot be spent without getting
signatures from multiple parties. Check the link for other features.)
• Time-locked transactions (A transaction cannot be accepted before a certain
time)

50 BTC [Alice, Bob], 50 BTC

TXsetup

Alice Bob

TXrefund [Alice], 50 BTC

Both Alice and Bob’s signatures are
required to spend this UTXO T > 1 month
9
Alice cannot use this to take her money back before a prespecified amount of time passes.
 Unidirectional Payment Channels
• Building blocks:
• Multi-signature Address (An output cannot be spent without getting
signatures from multiple parties. Check the link for other features.)
• Time-locked transactions (A transaction cannot be accepted before a certain
time)
[Alice], 49 BTC
50 BTC [Alice, Bob], 50 BTC
TXsetup TXspend [Bob], 1 BTC

Alice Bob

TXrefund [Alice], 50 BTC

Both Alice and Bob’s signatures are
required to spend this UTXO T > 1 month
10
Alice cannot use this to take her money back before a prespecified amount of time passes.
 Unidirectional Payment Channels Bob will publish the final
transaction at the end of
the interaction and before
the time lock expires.
• Building blocks:
• Multi-signature Address (An output cannot be spent without getting
signatures from multiple parties. Check the link for other features.)
• Time-locked transactions (A transaction cannot be accepted before a certain
time)
[Alice], 48 BTC
50 BTC [Alice, Bob], 50 BTC
TXsetup TXspend [Bob], 2 BTC

Alice Bob

TXrefund [Alice], 50 BTC

Both Alice and Bob’s signatures are
required to spend this UTXO T > 1 month
11
Alice cannot use this to take her money back before a prespecified amount of time passes.
Unidirectional Payment Channels
• Protocol outline (simplified) [1/2]:
• Setup: Alice creates and signs the TXsetup transaction.
• The output of TXsetup can only be spent using Alice's and Bob's signatures.
• Alice should not publish the setup transaction yet (why?).

• Refund: Alice creates the time-locked TXrefund transaction. The transaction

should use the output of TXsetup . Alice sends TXrefund to Bob. (Note: TXsetup is
not sent to Bob)
• Bob signs TXrefund and sends the signed version back to Alice.

• Alice can publish the TXsetup transaction now.

• Alice keeps TXrefund as insurance.
12
Unidirectional Payment Channels
• Protocol outline (simplified) [2/2]:
• Payments (off-chain): When Alice buys something from Bob before the
deadline, she creates and signs TXspend, and sends it to Bob.
• This operation is repeated. Each time, TXspend updates Alice's balance and
Bob's balance.

• Finalization: When the interaction ends, Bob can sign the last TXspend received
from Alice and publish it before the time lock expires.
• If Bob does not publish the final transaction within the specified time, Alice can sign
TXrefund and publish it.

13
Limited functionality of Bitcoin
• We showed how Bitcoin can be used to support decentralized
financial transactions.
• Can we build other decentralized applications using Bitcoin?
• While some applications could be made possible, there are limitations.
• Next, we will discuss
• What else can we do with Bitcoin?
• Limitations

14
Remote Coin Flipping - Revisited
• Coin flipping in a remote setting

H( r1 ‖ bA)
bA
bB
bB
Alice Bob Alice r1 , bA Bob

Insecure.
Does not achieve input
independence. 15
Remote Coin Flipping - Revisited
• Is there a problem that we did not address before?
• Alice could choose not to reveal her input after knowing that she would lose.
• This way, only Alice learned about the output. Bob did not.
• This violated a property called: fairness.

- In case of two parties, if Alice does not reveal her input, then Bob is
likely the winner.

- What if we would like to implement a multi-party protocol?

16
Addressing the fairness problem
• Can we rely on Reputation?
• Relying on reputation means that the participants who have a good history could
participate.
• Problem?
• What else can we do to address fairness?
• Find a way to incentivize the participants to complete the protocol till the end.
• The following paper showed how to build a lottery protocol using Bitcoin.

IEEE S&P 2014 17

Fairness Challenges in Multiparty Protocols
Randomly select a winner
Deposit

The index
of the winner

. .
. .
. .

- How to implement this securely?

- What could go wrong here?
19
Winner Selection
• Random winner selection should happen in an unbiased way.
• How can a group of n participants select a random index?
A simple approach:
• Assume the parties are labeled 0, 1, …, n – 1
• Each party i will select a random number xi between 0 and n – 1
• The winner index will be calculated as σ 𝑥𝑖 𝑚𝑜𝑑 𝑛

• Note that if at least one of the participants is honest, i.e., selecting

her xi uniformly at random, all participants will have an equal
probability to win.
20
Winner Selection
• When implementing the previous protocol, what would be the
problem if each party sends xi to the other participants directly?
• The last party to participate will be able to provide a value that will change
the outcome to a value of his choice.

• Input independence need to be guaranteed, i.e., each party needs to

select xi independently from other participants.
• Solution: use commitment schemes as we learned in the first lecture.

• Remaining problem: Fairness

• The last party to reveal input might choose to abort and not reveal his input if
the outcome is not in his favor.
21
Addressing Fairness
• How to incentivize each party to reveal his/her input?

• In a nutshell,
Build a protocol that works as follows:
• Each party will commit to a private input as we studied before.
• Each party will lock a configurable amount of money as a security deposit.
• Note: the deposit in our context here is different from the deposit in the previous slide.
The deposit in the previous slide was for the application itself.
• The security deposit will only be returned if the party reveals the private
input before a certain deadline.
• If not, the deposit will go to other participants.
What can be used to build this on top of Bitcoin?
22
How to implement the previous protocol on
Bitcoin?
• To implement the previous mechanism on top of Bitcoin, we will need to
rely on two features
• Multi-signature addresses and time-locked transactions.
• The protocol in the previous paper requires a commitment phase before
starting the protocol.
• Each party C sets up a timed commitment scheme with each other party Pi in the
system.
• This will address fairness as we will see shortly.
• Then, the main protocol itself runs after the commitment phase ends.
• If all participants reveal their inputs, the winner will proceed and take the reward.
• If any part C aborts, the deposits locked by C in the commitment phase will be
collected by the other participants.
23
Timed Commitment Scheme on Bitcoin
• Given a party C who would like to commit to some secret value x, and
another party Pi who would like to have insurance that C will reveal x
before a certain time.
• Flow:
• C will commit to some secret x and lock some deposit.
• To get the deposit back, C must disclose x (open the commitment) before a
certain deadline.
• If C does not reveal the secret on time, the deposit will go to the party Pi.

• In the setup, both commit and insurance (PayDeposit) transactions

need to be prepared. The details are shown next.
24
 Timed Commitment Scheme on Bitcoin
Commiti
value d Input Script:
UTXO that Signature by C to prove ownership of
belongs to prev UTXO
address C
Output Script Specification:
Tx output
The output of this transaction can only
be spent in any of these cases. of value d
• A value x is provided such that
hash(x) = h and the spending
transaction is signed by C
• The output is spent by a transaction
signed by both C and Pi

This tx output can be spent if one of these conditions holds

- The committer reveals the private input x (which hashes to h)
(1) The party C creates this Commiti transaction and - There is a valid transaction signed by both the committer and the
sends it to the ledger. party Pi

25
 Timed Commitment Scheme on Bitcoin
Commiti
This transaction will be used only if C does
value d Input Script: not reveal the secret x on time (before T).
UTXO that Signature by C to prove ownership of Pi must get this transaction from C (with a
belongs to prev UTXO signature) at the beginning of the protocol,
address C
and keeps it as insurance.
Output Script Specification:
Tx output If C does not reveal x before T, then Pi can
The output of this transaction can only
be spent in any of these cases. of value d sign it and get deposit.
• A value x is provided such that
hash(x) = h and the spending
transaction is signed by C PayDepositi
• The output is spent by a transaction
signed by both C and Pi
Input Script: Tx output of
Signatures by C and Pi value d
Output Script Specification:
(2) The party C creates the PayDepositi transaction, The output of this transaction can only
be spent with a transaction signed by Pi
signs it and sends to Pi. This will be the insurance
that Pi has. Timelock: T

26
 Timed Commitment Scheme on Bitcoin
Commiti
This transaction will be used only if C does
value d Input Script: not reveal the secret x on time (before T).
UTXO that Signature by C to prove ownership of Pi must get this transaction from C (with a
belongs to prev UTXO signature) at the beginning of the protocol,
address C
and keeps it as insurance.
Output Script Specification:
Tx output If C does not reveal x before T, then Pi can
The output of this transaction can only
be spent in any of these cases. of value d sign it and get deposit.
• A value x is provided such that
hash(x) = h and the spending
transaction is signed by C PayDepositi
• The output is spent by a transaction
signed by both C and Pi
Input Script: Tx output of
Signatures by C and Pi value d
Output Script Specification:
(2) The party C creates the PayDepositi transaction, The output of this transaction can only
be spent with a transaction signed by Pi
signs it and sends to Pi. This will be the insurance
that Pi has. Timelock: T

The initial setup is complete now.

Note that the party C needs to run the above with each other party at the beginning of the protocol.
27
In total, all parties will run this protocol with each other. This will lead to O(n2) transactions.
 Timed Commitment Scheme on Bitcoin
This happens later during the protocol.

Commiti Openi
Tx output of
value d Input Script: Input Script: value d
UTXO that Signature by C to prove ownership of Signature by C and the secret input x
belongs to prev UTXO
address C Output Script Specification:
Output Script Specification: The output of this transaction can only
The output of this transaction can only be spent with a transaction signed by C
Tx output
be spent in any of these cases.
• A value x is provided such that
of value d
hash(x) = h and the spending
transaction is signed by C PayDepositi
• The output is spent by a transaction
signed by both C and Pi
Input Script: Tx output of
Signatures by C and Pi value d
Output Script Specification:
The output of this transaction can only
In order for C to get the deposit back, C will send the open transaction at the appropriate be spent with a transaction signed by Pi
time. Timelock: T
Assuming the protocol goes as expected, when shall C reveal input x?
- After all parties commit to their inputs and the compute transaction shown next is
published. This means that the protocol is ready for the next step and winner selection.
- Obviously, all of this must happen be before T. 28
The Execution Phase
• After all parties commit to their inputs, and the PayDeposit insurance
transactions are received, they are now ready to proceed with the next
phase (Execution Phase).

• The parties should not proceed with the execution phase unless everything
is in place.
• For example, if any party does not receive the expected PayDeposit transaction, they
should abort and not complete the protocol.
• In this case, they should also retrieve their deposits back.

• In the following, assume that the n parties have already committed to their
inputs x1, x2 …, xn. Denote the commitments by h1, h2, …, hn
• Each xi will have the secret input and the randomness needed for hiding.
29
 The Execution Phase
All parties sign this transaction
UTXO that Value 1 ComputeWinner
belongs to
address P1
Input Scripts:
1: Signature by P1
UTXO that Value 1 2: Signature by P2
belongs to .
.
address P2 n: Signature by Pn Value n
.
Output Script Specification:
.
The output of this transaction can only be spent if all the
. following hold
- Values x1, x2 …, xn are provided such that
UTXO that Value 1 h(x1) = h1 and h(x2) = h2 and …. and h(xn) = hn
belongs to
address Pn
- The spending transaction is signed by Pwinner where
winner = f (x1, x2, …., xn)

The input to this transaction are n UTXOs of equal value

(say 1 Bitcoin), each belongs to one of the parties.
The output can only be spent by the winner. The winner index is
30
computed by the function f specified in the script.
 The Execution Phase In order for this
All parties sign this transaction
output to be spent by
UTXO that Value 1 ComputeWinner the winner, all parties
belongs to
need to reveal their
address P1
Input Scripts: inputs xi's.
1: Signature by P1
UTXO that Value 1 2: Signature by P2 When this happens,
belongs to . the winner can be
.
address P2 n: Signature by Pn Value n identified, and the
winner can claim the
.
Output Script Specification: money accordingly.
.
The output of this transaction can only be spent if all the
. following hold If not, this output will
- Values x1, x2 …, xn are provided such that not be spent, but the
UTXO that Value 1 h(x1) = h1 and h(x2) = h2 and …. and h(xn) = hn honest participants
belongs to will take the
address Pn
- The spending transaction is signed by Pwinner where
winner = f (x1, x2, …., xn) insurance deposits.

The input to this transaction are n UTXOs of equal value

(say 1 Bitcoin), each belongs to one of the parties.
The output can only be spent by the winner. The winner index is
31
computed by the function f specified in the script.
 The Execution Phase
UTXO that Value 1 ComputeWinner Signed by the winner
belongs to
address P1 ClaimMoney
Input Scripts:
1: Signature by P1
2: Signature by P2 Input Script:
UTXO that Value 1
. x1, x2, …., xn
belongs to
address P2
. Signature by Pwinner
n: Signature by Pn Value n
.
Output Script Specification:
. Output Script Specification:
The output of this transaction can only be spent if all the
. The output of this
following hold
transaction can only be spent
- Values x1, x2 …, xn are provided such that
UTXO that Value 1 with a transaction signed by
h(x1) = h1 and h(x2) = h2 and …. and h(xn) = hn
belongs to Pwinner (or whatever Pwinner
- The spending transaction is signed by Pwinner where
address Pn sets)
winner = f (x1, x2, …., xn)

32
 The Execution Phase
UTXO that Value 1 ComputeWinner Signed by the winner
belongs to
address P1 ClaimMoney
Input Scripts:
1: Signature by P1
2: Signature by P2 Input Script:
UTXO that Value 1
. x1, x2, …., xn
belongs to
address P2
. Signature by Pwinner
n: Signature by Pn Value n
.
Output Script Specification:
. Output Script Specification:
The output of this transaction can only be spent if all the
. The output of this
following hold
transaction can only be spent
- Values x1, x2 …, xn are provided such that
UTXO that Value 1 with a transaction signed by
h(x1) = h1 and h(x2) = h2 and …. and h(xn) = hn
belongs to Pwinner (or whatever Pwinner
- The spending transaction is signed by Pwinner where
address Pn sets)
winner = f (x1, x2, …., xn)
The winner can obtain the xi information
from the open transactions, that the
parties will send to get their deposits
back.
33
Considerations
• Before signing computeWinner, the parties should check that the
commitments h1 to hn are distinct.
• Think about what could go wrong in a two-party protocol if one player used
the same commitment of the other party.

• How to set the security deposit d value?

• The value of d should be N in order to make the expected payoff non-
negative, according to the paper.
• This means that the total security deposits locked by each party at the
beginning of the protocol will have to be N(N-1).
• This motivated research later on how to reduce the security deposit value.

34
Drawbacks of the previous protocol
• The previous protocol description has high overhead: O(n2) transactions in
the setup and communication.
• Note: in the setup, the timed commitment transactions of each party C made to all
other parties can be grouped into one multi-output transaction. However, the total
size of the transactions on-chain will still be quadratic.
• The total number of paydeposit (exchanged off-chain at the beginning) is quadratic.
• High security deposit.
• While there are other papers which tried to improve this on top of Bitcoin,
there was still overhead, and more flexibility was still needed in the
specification of the application on Bitcoin.

Next, we will learn about smart contracts, which can make implementing the
previous protocol easier and more efficient.
35