Scriptless Bitcoin Lotteries from Oblivious Transfer
Lloyd Fournier
lloyd.fourn@gmail.com

September 10, 2019

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 20191 / 23

What’s a Lottery?

Imagine a trusted party Lloyd who conducts lotteries between Alice andBob:
Alice and Bob send 1 BTC to Lloyd’s Address
Lloyd chooses a winner randomly and sends them 2 BTC
The goal of a lottery protocol is achieve the same result without a trusted
third party.

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 20192 / 23What’s Scriptless?

Bitcoin has a way of specifying the spending rules on coins with alanguage called “Script”. A scriptless protocol doesn’t use it. Instead it
realises the spending rules off-chain through some cryptographic protocol.
For example:
You can replace OP CHECKMULTISIG with a threshold
mutli-signature scheme.
You can replace HTLC by using “adaptor” signatures

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 20193 / 23

Why Scriptless?

1

Scriptless protocols are more efficient and more private (no validation
rules appear on the blockchain).

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 20194 / 23

Why Scriptless?

1

Scriptless protocols are more efficient and more private (no validation
rules appear on the blockchain).

2

To know what can and can’t be done without script

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 20194 / 23

Why Scriptless?

1

Scriptless protocols are more efficient and more private (no validation
rules appear on the blockchain).

2

To know what can and can’t be done without script

https://bitcointalk.org/index.php?topic=355174.0...I think the multi-party lottery scheme still rates as the mostadvanced usage of script yet found in the wild
— Mike Hearn

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 20194 / 23

How to do a lottery without a trusted third party?

Need to fairly generate randomness (no OP RANDOM)The randomness choose the winner
Enforce the outcome on the blockchain
All previous lotteries used hash commitment “coin tossing” to generate
the randomness

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 20195 / 23

Coin tossing

Idea introduced in by Manuel Blum in 1981: Coin Flipping By Telephone:
A protocol for solving impossible problems
Alice and Bob want to flip a coin by telephone. (They have justdivorced, live in different cities, want to decide who gets the car.)

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 20196 / 23

Coin tossing

Idea introduced in by Manuel Blum in 1981: Coin Flipping By Telephone:
A protocol for solving impossible problems
Alice and Bob want to flip a coin by telephone. (They have justdivorced, live in different cities, want to decide who gets the car.)basic idea:
1

Alice sends a “commitment” to her coin toss2

Bob sends his coin toss3

Alice reveals her coin toss

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 20196 / 23

Hash-Commitment Coin tossing

Aliceb1 ←$ {0, 1}
r ←$ {0, 1}lt ← H(b1 , r)Bobt−−−−−−−−−→b2←−−−−−−−−−b2 ←$ {0, 1}⇐ b1 ⊕ b2
b01 , r0−−−−−−−−−→?

H(b01 , r0 ) = t
b01 ⊕ b2 ⇒Note: It’s unfair
Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 20197 / 23

Lottery Protocols – First Attempt

Iddo - fair coin toss with no extortion and no need to trust a third party
https://bitcointalk.org/index.php?topic=277048.0 (2013)...there seemed to be an interest in implemented a gambling
system that doesn’t involve a 3rd-party like SatoshiDice, so we
can eliminate the house edge

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 20198 / 23

Lottery Protocols – First Attempt

Iddo - fair coin toss with no extortion and no need to trust a third party
https://bitcointalk.org/index.php?topic=277048.0 (2013)...there seemed to be an interest in implemented a gambling
system that doesn’t involve a 3rd-party like SatoshiDice, so we
can eliminate the house edge
Two Ideas:
Iddo Bentov: We can use collateral to force both parties to reveal
pre-images.
Adam Back: If a party doesn’t reveal their pre-image we should justmake them lose by default.

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 20198 / 23

Miller-Bentov 2016

Zero-Collateral Lotteries in Bitcoin and Ethereum

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 20199 / 23

Scriptless Lottery
How do we get our lottery to look like this?

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201910 / 23

Oblivious transfer

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201911 / 23

Oblivious transfer

1

Manuel Blum to the rescue (again)! He made another discovery in1981: you can generate a random outcome with oblivious transfer.

2

University of Berkeley technical report: Three applications ofoblivious transfer: 1. Coin flipping by telephone, 2. How to exchange
secrets, 3. How to send certified electronic mail.

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201911 / 23

Oblivious transfer

1

Manuel Blum to the rescue (again)! He made another discovery in
1981: you can generate a random outcome with oblivious transfer.

2

University of Berkeley technical report: Three applications ofoblivious transfer: 1. Coin flipping by telephone, 2. How to exchange
secrets, 3. How to send certified electronic mail.

Rough Definition:
1

Alice transmits one of n message to Bob of Bob’s choosing (But Alice
doesn’t learn which message).

2

receiver security Sender doesn’t know which message was sent

3

sender security Receiver only gets one message

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201911 / 23

AliceBob

m0 , m1 ←$ {0, 1}kb2 ←$ {0, 1}
 OT((b2 ), (m0 , m1 )) b1 ←$ {0, 1}

b1−−−−−−−−−→m0←−−−−−−−−−learns mb2⇒ b1 ⊕ b2
 0 m0 = m01 m0 = m1b02 :=⊥ otherwise⇐ b1 ⊕ b02

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201912 / 23

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201913 / 23

1

Choose keys securely

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201913 / 23

1

Choose keys securely

2

Sign the transaction scaffold

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201913 / 23

1

Choose keys securely

2

Sign the transaction scaffold

Lloyd Fournier (Scaling Bitcoin 2019)

3Scriptless Lotteries

Alice obliviously signs BobWin

September 10, 201913 / 23

1

Choose keys securely

3

Alice obliviously signs BobWin

2Sign the transaction scaffold

4Sign and broadcast Fund

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201913 / 23

How to realise Oblivious Signing?

We want Bob to have a signature on BobWin0 OR BobWin1 but without
Alice knowing which one.

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201914 / 23

How to realise Oblivious Signing?

We want Bob to have a signature on BobWin0 OR BobWin1 but without
Alice knowing which one.
Approach: Use adaptor signatures where Bob only knows the completionfor one of them.

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201914 / 23

Adaptor Signatures (Poelstra 2017)

Adaptor signatures enable the signer to create a simple access structure toa particular signature on a particular message.

args
s=validSchnorr
sk, mr + H(g r ||pk||m)sk(s, g r )Lloyd Fournier (Scaling Bitcoin 2019)

Adaptorsk, m, Y = g yr + H(g r Y ||pk||m)sk(s + y, g r Y )Scriptless Lotteries

September 10, 201915 / 23Adaptor Signatures (Poelstra 2017)

Adaptor signatures enable the signer to create a simple access structure toa particular signature on a particular message.

args
s=validSchnorrsk, mr + H(g r ||pk||m)sk(s, g r )Adaptorsk, m, Y = g y
r + H(g r Y ||pk||m)sk(s + y, g r Y )Important feature: The signer learns y if they see the completedsignature.

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201915 / 23

Oblivious Signing

Approach: Alice to give Bob adaptor signatures where Bob only knows
the completion for one of them.

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201916 / 23

Oblivious Signing

Approach: Alice to give Bob adaptor signatures where Bob only knows
the completion for one of them.
A Pedersen commitment for x is in the form T = g x hc .
It’s impossible to decommit to more than one value without knowing
the DLOGg (h)Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201916 / 23

Oblivious Signing

Approach: Alice to give Bob adaptor signatures where Bob only knows
the completion for one of them.
A Pedersen commitment for x is in the form T = g x hc .
It’s impossible to decommit to more than one value without knowing
the DLOGg (h)Fix c ∈ {0, 1}, committer can only know discrete log of T OR T h−1
c = 0 −→ T = g x (knows DLOG(T ))c = 1 −→ T = g x h (knows DLOG(T h−1 ))Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless LotteriesSeptember 10, 201916 / 23

Oblivious Signing

Alice(sk)(m0 , m1 , h)Bob(pk, c ∈ {0, 1})y ←$ Zq

T = g y hc←−−−−−−−−−(s0 , R0 ) = σ(sk, m0 , T )−1(s1 , R1 ) = σ(sk, m1 , T h )(s0 , R0 ), (s1 , R1 )−−−−−−−−−→
verify both
(sc + y, Rc · g y ) ⇒Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201917 / 23

Secure?

1security for sender (Alice): If Bob can complete both adaptor
signatures then he can solve DLOG(h) (from the completion of both
adaptor signatures we learn DLOG of T, T h−1 ).

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201918 / 23

Secure?

1

security for sender (Alice): If Bob can complete both adaptor
signatures then he can solve DLOG(h) (from the completion of bothadaptor signatures we learn DLOG of T, T h−1 ).

2security for receiver (Bob): It’s information theoretically impossible
for Alice to learn which choice Bob made (until he reveals it).

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201918 / 23

Secure?

1

security for sender (Alice): If Bob can complete both adaptor
signatures then he can solve DLOG(h) (from the completion of bothadaptor signatures we learn DLOG of T, T h−1 ).

2security for receiver (Bob): It’s information theoretically impossible
for Alice to learn which choice Bob made (until he reveals it).

3

Original protocol due to: Tso R., Okamoto T., Okamoto E. (2008)
1-out-of-n Oblivious Signatures. In: Chen L., Mu Y., Susilo W. (eds)
Information Security Practice and Experience. ISPEC 2008. Lecture
Notes in Computer Science, vol 4991. Springer, Berlin, Heidelberg

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201918 / 23

Not so fast! Our transactions outputs are locked by joint public keys!

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201919 / 23

Two-party oblivious signing

One party knows which of two messages they are both signing but theother doesn’t. Make a few changes:
1

They first choose joint nonces RBobWin0 , RBobWin1 (we did this already).

2Along with T Bob sends half adaptor signatures for m0 (BobWin0 )and m1 (BobWin1 ) under B0 and B1

3

Alice calculates the full adaptor signatures and sends them back toBob

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201920 / 23

Ok Done!

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201921 / 23

Summary
Summary:
Lotteries were previously an example of something that could only bedone with non-trivial script.

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201922 / 23

Summary
Summary:
Lotteries were previously an example of something that could only bedone with non-trivial script.
They can be (and are actually more efficient on-chain)

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201922 / 23

Summary
Summary:
Lotteries were previously an example of something that could only bedone with non-trivial script.
They can be (and are actually more efficient on-chain)
Oblivious signing with Schnorr signatures is secure and efficient (atleast as it is used here).

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless LotteriesSeptember 10, 201922 / 23

Summary
Summary:
Lotteries were previously an example of something that could only bedone with non-trivial script.
They can be (and are actually more efficient on-chain)
Oblivious signing with Schnorr signatures is secure and efficient (atleast as it is used here).
Unsubstantiated claims:
You can do lotteries with different odds by doing 1/N oblivious
signing rather than 1/2.
You can cooperatively complete the lottery in two on-chaintransactions.
You can execute cooperative protocol in a payment channel (and evendo it ”multi-hop” I think).
Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201922 / 23

The End

Lloyd Fournier (Scaling Bitcoin 2019)

Scriptless Lotteries

September 10, 201923 / 23