TumbleBit:
An Untrusted Bitcoin-Compatible Anonymous
Payment Hub
Ethan Heilman, Leen AlShenibr, Foteini Baldimtsi,
Alessandra Scafuro, Sharon Goldberg

Scaling Bitcoin Milan 20161

Introduction
TumbleBit is:
1.
2.
3.
4.

Private: Unlinkable Bitcoin payments and k-anonymous mixing,
Untrusted: No one including Tumbler can steal or link payments.
Scalable (payment hub): scales transaction velocity and volume.
Compatible: Works with today's Bitcoin protocol.
Why is compatibility hard?
Our protocol must work with highly constrained Bitcoin scripts
which provide two very limited cryptographic operations.

Two ways to use TumbleBit:
TumbleBit can be used as a classic Bitcoin tumbler:● k-anonymity within a mix,
● 4 transactions confirmed in 2 blocks (~20mins)
When TumbleBit is used as a payment hub:
● Unlinkability within the payment phase,● Payments confirmed in seconds,● Payments are off-blockchain,... don’t take up space on the blockchain.

2

Introduction
TumbleBit is:
1.
2.
3.
4.

Private: Unlinkable Bitcoin payments and k-anonymous mixing,
Untrusted: No one including Tumbler can steal or link payments.
Scalable (payment hub): scales transaction velocity and volume.
Compatible: Works with today's Bitcoin protocol.
Why is compatibility hard?
Our protocol must work with highly constrained Bitcoin scripts
which provide two very limited cryptographic operations.

Two ways to use TumbleBit:
When usedcan
as abepaymenthub,
TumbleBit
helpstumbler:
scale
TumbleBit
used asa classic
Bitcointransaction
velocity● Bitcoin’s
k-anonymity
withina mix,(faster payments),
and 4transaction
volume(higher maximum
payments).
●
transactions
confirmed
in 2 blocks(~20mins)

When TumbleBit is used as a payment hub:
● Unlinkability within the payment phase,● Payments confirmed in seconds,● Payments are off-blockchain,... don’t take up space on the blockchain.

3

Background: Payment Hub
A payment hub: routes payment channels.
Unidirectional Payment Channel
Alice → Payment Hub

Unidirectional Payment Channel
Payment Hub → Bob

Transaction: Escrow1
Output Script: 2-of-2 multisig
Must be signed by Alice and Payment Hub
Refunded to Alice: after 1 month

Transaction: Escrow2
Output Script: 2-of-2 multisig
Must be signed by Payment Hub and Bob
Refunded to Payment Hub: after 1 month

Payment
Hub

Transaction
Escrow1

Alice
σ1

Transaction
Claim1σ1

Alice signs Claim1

Transaction
Escrow2

σ2

Transaction
Claim2Bob
σ2Payment Hub signs Claim2

Payment Hub and Bob could sign and post both claim transactions,paying 1 Bitcoin from Alice to Bob via the Payment Hub.
4

Background: Payment Hub
A payment hub: routes payment channels.
Unidirectional Payment Channel
Alice → Payment Hub

Unidirectional Payment Channel
Payment Hub → Bob

Transaction: Escrow1
Output Script: 2-of-2 multisig
Must be signed by Alice and Payment Hub
Refunded to Alice: after 1 month

Transaction: Escrow2
Output Script: 2-of-2 multisig
Must be signed by Payment Hub and Bob
Refunded to Payment Hub: after 1 month

Payment
Hub

Transaction
Escrow1

Alice
σ1

Transaction
Claim1σ1Transaction
Escrow2

σ2

Transaction
Claim2Bob
σ2malicious,
Hub signs Claim2
Alice signs ...But
Claim1 what if the hub is Payment
and takes Alice’s bitcoin and doesn’t pay Bob?
Payment Hub and Bob could sign and post both claim transactions,paying 1 Bitcoin from Alice to Bob via the Payment Hub.
5

Background: Payment Hub
A payment hub: routes payment channels.
Unidirectional Payment Channel
Alice → Payment Hub

Unidirectional Payment Channel
Payment Hub → Bob

Transaction: Escrow1
Output Script: 2-of-2 multisig
Must be signed by Alice and Payment Hub
Refunded to Alice: after 1 month

Transaction: Escrow2
Output Script: 2-of-2 multisig
Must be signed by Payment Hub and Bob
Refunded to Payment Hub: after 1 month

Payment
Hub

Transaction
Escrow1

Alice
σ1

Transaction
Claim1σ1Transaction
Escrow2

σ2

Transaction
Claim2Bob
σ2malicious,
Hub signs Claim2
Alice signs ...But
Claim1 what if the hub is Payment
and takes Alice’s bitcoin and doesn’t pay Bob?
Atomicity: If Claim1 and Claim2 happen atomically then theft is prevented.
Payment Hub and Bob could sign and post both claim transactions,paying 1 Bitcoin from Alice to Bob via the Payment Hub.

Hash locks provide this property.

6Background: Payment Hub
A payment hub: routes payment channels.
Unidirectional Payment Channel
Alice → Payment Hub

Unidirectional Payment Channel
Payment Hub → Bob

Transaction: Escrow1
Output Script: 2-of-2 multisig
Must be signed by Alice and Payment Hub
Refunded to Alice: after 1 month

Transaction: Escrow2
Output Script: 2-of-2 multisig
Must be signed by Payment Hub and Bob
Refunded toI Payment
Hub:x,
after
1 month
don’t know
so…

I can’t spend Claim2.
Alice, learn x to pay me.

Bob, the value of x is....

Payment
Hub

Transaction
Escrow1

Alice
σ1

Transaction
Claim1
H(X) = Y?

σ1 ,XTransaction
Escrow2

σ2

Transaction
Claim2Bob
σ2 ,X

H(X) = Y?

malicious,
Hub signs Claim2
Alice signs ...But
Claim1 what if the hub is Payment
and takes Alice’s bitcoin and doesn’t pay Bob?
Atomicity:
If Claim1andClaim2 happen
atomicallythen hubtheftcanis prevented.
Thus,using hashlockedtransactions
or HTLCsa payment
prevent theft,
Payment Hub and Bob could sign and post both claim transactions,paying1 Bitcoin fromto Bob
via the Payment
Hub.
however thisis provides
noAliceprivacyagainstthe payment
hub.
Hash locks provide this property.
7Payers

Alice1

Alice
Alice
2

Alice3Background: HTLC Privacy
Transaction
Escrow

Transaction
Escrow
Transaction
Claim
H(x2) = Y?

No privacy
from payment hub.

Transaction
Claim
H(x1) = Y?

Transaction
Escrow

Payment
Hub

Transaction
Escrow

Transaction
Claim
H(x1) = Y?

Transaction
Claim
H(x2) = Y?

Transaction
Escrow

Transaction
Escrow

Transaction
Claim
H(x3) = Y?

Transaction
Claim
H(x3) = Y?

Payees

Bob1

Bob
Bob2

Bob3

8

Payers

Alice1

Alice
Alice
2

Alice3Background: HTLC Privacy
Transaction
Escrow

Transaction
Escrow

Transaction
Claim
H(x2) = Y?

Transaction
Claim
H(x1)
= Y?
?????

Transaction
Escrow

Payment
Hub

Transaction
Escrow

Transaction
Claim
H(x1) = Y?

Transaction
Claim
H(x2)
= Y?
?????

Transaction
Escrow

Transaction
Escrow

Transaction
Claim
H(x3) = Y?

Transaction
Claim
H(x3)
= Y?
?????

The main idea behind TumbleBit is a protocol which
provides atomicity but is also unlinkable (i.e. private).
Think of it like Unlinkable or Private HTLCs.

Payees

Bob1

Bob
Bob2

Bob3

9

Background: RSA Puzzles● An RSA Puzzle is just a “textbook RSA encryption” of some value ϵ:RSA(PK, ϵ) = z● Only the party that knows SK can solve RSA puzzles:
RSA-1(SK, z) = RSA-1(SK, RSA(PK, ϵ)) = ϵ

RSA blinding can be used to blind RSA puzzles
z1
Tumbler

Bob1

z2

Bob2

z*

z* = Blind(z2)ϵ*ϵ2 = Unblind(ϵ*)-1RSA (SK,z*) = ϵ*Bob2 learns the solution ϵ2 to the puzzle z2
Tumbler can not link the blinded RSA puzzle it solves z*
to any of the RSA puzzles it issued (z1, z2).

TumbleBit: Protocol Overview
Alice, I’ll sell a solution to an RSA
puzzle of your choice for 1 Bitcoin.

Bob, the solution ϵ to RSA puzzle z
allows you to claim 1 Bitcoin.

Transaction
Escrow1

Alice

Tumblerz = RSA(PK, ϵ)c = Enc(ϵ,σ)
PuzzleSolver Protocolz*Y, qFair exchange:for ϵ*

Dec(X, q)

Transaction
Escrow2

Bob

Puzzle Promise
Protocol(z, c)

Blind(z)z*ϵ* = RSA-1(SK,z*)q = Enc(X, ϵ*)Y = H(X)
Learn ϵ get

Transaction offer
H(X) = Y for

X

Transaction fulfill
X

Unblind(ϵ*)ϵ*
Transaction

σ for .

σ

Dec(ϵ, c)TumbleBit: Protocol Overview
Alice, If
I’llTumbler
sell a solution
to an RSA
to RSA or
puzzlez
corruptsz, c, X,or Bob,
q it thecansolution
cheatϵ AliceBob!
puzzle of your choice for 1 Bitcoin.
allows you to claim 1 Bitcoin.
Transaction
Escrow1

Alice

Tumblerz = RSA(PK, ϵ)c = Enc(ϵ,σ)
PuzzleSolver Protocolz*Y, qFair exchange:for ϵ*

Dec(X, q)

Transaction
Escrow2

Bob

Puzzle Promise
Protocol(z, c)

Blind(z)z*ϵ* = RSA-1(SK,z*)q = Enc(X, ϵ*)Y = H(X)
Learn ϵ get

Transaction offer
H(X) = Y for

X

Transaction fulfill
X

Unblind(ϵ*)ϵ*
Transaction

σ for .

σ

Dec(ϵ, c)TumbleBit: Protocol Overview
Alice, If
I’llTumbler
sell a solution
to an RSA
to RSA or
puzzlez
corruptsz, c, X,or Bob,
q it thecansolution
cheatϵ AliceBob!
puzzle of your choice for 1 Bitcoin.
allows you to claim 1 Bitcoin.
Transaction
Escrow1

Alice

Tumblerz = RSA(PK, ϵ)c = Enc(ϵ,σ)
PuzzleSolver Protocolz*Y, qFair exchange:for ϵ*

Dec(X, q)

Transaction
Escrow2

Bob

Puzzle Promise
Protocol(z, c)

Blind(z)z*ϵ* = RSA-1(SK,z*)q = Enc(X, ϵ*)Y = H(X)
Learn ϵ get

Transaction offer
H(X) = Y for

X

Transaction fulfill
X

TumbleBit prevents this
via two protocols:ϵ*Puzzle-Solver-Protocol:
Tumbler convinces Alice the preimage X
where Hash(X) = Y will allow her to learn ϵ*.

Unblind(ϵ*)

Puzzle-Promise-Protocol:
Tumbler convinces Bob that the solution to RSA
Transaction
Dec(ϵ,σ him learn
puzzle z is a value ϵ which allows
σ. c)

σ for .

TumbleBit: Protocol Overview
Alice, I’ll sell a solution to an RSA
puzzle of your choice for 1 Bitcoin.

Bob, the solution ϵ to RSA puzzle z
allows you to claim 1 Bitcoin.

Transaction
Escrow1

Alice

Tumblerz = RSA(PK, ϵ)c = Enc(ϵ,σ)
PuzzleSolver Protocolz*Y, qFair exchange:for ϵ*

Dec(X, q)

Transaction
Escrow2

Bob

Puzzle Promise
Protocol(z, c)

Blind(z)z*ϵ* = RSA-1(SK,z*)q = Enc(X, ϵ*)Y = H(X)
Learn ϵ get

Transaction offer
H(X) = Y for

X

Transaction fulfill
X

Unblind(ϵ*)ϵ*
Transaction

σ for .

σ

Dec(ϵ, c)TumbleBit: Phases
1.
2.
3.

Escrow Phase: All payment channels setup.
Payments Phase (~1 month): Payers make payments.
Cashout Phase: Payers and payees close their payment channels.
PayeesPayersAlice1

Payment Channel
A1:10, T:0

Payment Channel
T:10, B1:0

Bob1(c,z),(c,z),(c,z),...(c,z)

Alice2

Payment Channel
A2:10, T:0

Payment Channel
T:10, B2:0

Bob2(c,z),(c,z),(c,z),...(c,z)

Alice3

Payment Channel
A3:10, T:0

Payment Channel
T:10, B3:0

Bob3(c,z),(c,z),(c,z),...(c,z)

TumbleBit: Phases
1.
2.
3.

Escrow Phase: All payment channels setup.
Payments Phase (~1 month): Payers make payments.
Cashout Phase: Payers and payees close their payment channels.
PayeesPayersAlice1
Pay
1
BTC
Pay
2
BTC
Pay
3
BTC
Pay
4
Pay 5 BTC
BTC

Alice2
Pay
1 BTC
Pay
Pay 2
3 BTC
BTC

Alice3
Pay
1
BTC
Pay
2
BTC
Pay
3
BTC
Pay
4
BTC
Pay
5
BTC
Pay
6
Pay 7 BTC
BTC

Payment Channel
A1:10, T:0

Payment Channel
T:10, B1:0

Close channel
T:5, B1:5

Payment Channel
A2:10, T:0(c,z),(c,z),(c,z),...(c,z)σ σPayment Channel
T:10, B2:0

Close channel
T:3, B2:7
Payment Channel
A3:10, T:0

Bob1

Bob2
(c,z),(c,z),(c,z),...(c,z)σ σ σPayment Channel
T:10, B3:0σBob3(c,z),(c,z),(c,z),...(c,z)σ σ σTumbleBit: Phases
1.
2.
3.

Escrow Phase: All payment channels setup.
Payments Phase (~1 month): Payers make payments.
Cashout Phase: Payers and payees close their payment channels.
PayeesPayersPayment Channel
A1:10, T:0

Payment Channel
T:10, B1:0

Close channel
T:5, B1:5

Close channel
T:8, B1:2

Payment Channel
A2:10, T:0

Payment Channel
T:10, B2:0

Close channel
T:3, B2:7

Close channel
T:0, B2:10

Alice3

Payment Channel
A3:10, T:0

Payment Channel
T:10, B3:0

Pay
1
BTC
Pay
2
BTC
Pay
3
BTC
Pay
4
BTC
Pay
5
BTC
Pay
6
Pay 7 BTC
BTC

Close channel
T:7, B3:3

Close channel
T:7, B3:3

Alice1
Pay
1
BTC
Pay
2
BTC
Pay
3
BTC
Pay
4
Pay 5 BTC
BTC

Alice2
Pay
1 BTC
Pay
Pay 2
3 BTC
BTC

Bob1
(c,z),(c,z),(c,z),...(c,z)

σ σ
Bob2
(c,z),(c,z),(c,z),...(c,z)

σ σ σ

σ

Bob3
(c,z),(c,z),(c,z),...(c,z)σ σ σTumbleBit: Phases
1.
2.
3.

Escrow Phase: All payment channels setup.
Payments Phase (~1 month): Payers make payments.
Cashout Phase: Payers and payees close their payment channels.
PayeesPayersPrivacyoffered the TumbleBit
Payment Hub
Payment Channel
Payment Channel
A1:10, T:0
T:10, B1:0
Alice1
Tumbler’s view:Close channel
Close channel
Pay
1
BTC
Pay
2 BTC
T:5, B1:5 (2) # of payments each payee
T:8,received.
B1:2(1) payerof each payment,
Pay
Pay 3
4 BTC
BTC

Bob1
(c,z),(c,z),(c,z),...(c,z)σ σPay 5 BTC

Unlinkability def:
Payment Channel
Payment Channel
AllAliceinteraction
graphscompatiblewiththetumblers
view
areBequally
likely.
A :10, T:0
T:10,
:0
2
2

Pay
1 BTC
Pay
Pay 2
3 BTC
BTC

Alice3
Pay
1
BTC
Pay
2
BTC
Pay
3
BTC
Pay
4
BTC
Pay
5
BTC
Pay
6
Pay 7 BTC
BTC

Close channel# Sent T:3, B2:7
(5)
Payment Channel(3) A3:10, T:0
Close channel(7) T:7, B3:3

2

Bob2

Close channel(c,z),(c,z),(c,z),...(c,z)
T:0, B2:10 # Received(2)
Payment Channel
T:10, B3:0
(10)
Close channel
T:7, B3:3

(3)

σ σ σ

σ

Bob3
(c,z),(c,z),(c,z),...(c,z)σ σ σTumbleBit: Classic Tumbler
TumbleBit can also be a classic tumbler:
Allows users to privately move bitcoins to an unlinked fresh address.

Old Addr 1

Fresh Addr 1

Old Addr 2

Fresh Addr 2

Old Addr 3

Fresh Addr 3This is also sometimes known as a mixing service or mix.

19

TumbleBit: Classic Tumbler

Payers

To run TumbleBit as a Classic Bitcoin Tumbler:● Each payer just makes one payment.
● Each payee accepts only one payment.
● # of payers = # of payees.
● payer and payee pairs are the same user
Payment Channel
A1:1, T:0

Payment Channel
T:1, B1:0

Pay 1 BTC

Close channel
T:1, B1:0

Close channel
T:0, B1:1

Alice2

Payment Channel
A2:1, T:0

Payment Channel
T:1, B2:0

Close channel
T:0, B2:1

Close channel
T:0, B2:1

Alice3

Payment Channel
A3:1, T:0

Payment Channel
T:1, B3:0

Pay 1 BTC

Close channel
T:1, B3:0

Close channel
T:0, B3:1

Alice1

Pay 1 BTC

Provides k-anonymity:
Where k = # of payers = # of payee.

Payees

Bob1

Bob2

Bob3

Compared to other Tumblers
Vulnerable to DoS &Sybil Attacks

Bitcoin-Compatible
Schemes(aka “Mixing Services”)

Vulnerable to bitcoin theft
Limited Anonymity

TumbleBit

Mixing takes
hours

Xim

Intermediarybreaksanonymity
21

TumbleBit: Implementation
We wrote a proof-of-concept implementation of the Classic
Tumbler:● We are working on improving it and making it user friendly.
● Sourcecode and a development roadmap are available on
Github.
We “tumbled”
800 payments:● We are working
to improve it to make it user ready.
You can see the transactions on the mainnet blockchain.
TXIDs avaliable in our paper.

Our implementation is Performant (per TumbleBit payment):● 326 KB of Bandwidth,● Puzzle-Solver takes ~0.4 seconds to compute● Total time depends on network latency:
No latency ~0.6 seconds.
Boston to Tokyo ~6 seconds (clear) and ~11 seconds...(both parties use TOR)

22

Conclusion
TumbleBit provides,
private untrusted scalable payments via today’s Bitcoin
1. Private: Unlinkable or k-anonymous payments
2. Trustless: Tumbler can not steal or link payments.
3. Scalable (payment hub): scales Bitcoin’s transaction velocity and volume.

We have running code (for TumbleBit classic tumbler):● Our code runs on Bitcoin’s mainnet blockchain.
● We have published our code on github.
● ...and we working to improve it and make TumbleBit easy and safe to use.

We are hiring a full time engineer (Boston),email me if interested.
23

Questions?
Source code + roadmap: https://github.com/BUSEC/TumbleBit
Paper: https://eprint.iacr.org/2016/575.pdf

Ask questions on twitter: @Ethan_Heilman

24

TumbleBit: Puzzle-Solver-Protocol

I can’t tell which B’s
are real or fake.

z*

Alice

Fair exchange/contingent payment for an RSA puzzle solution to z*:
1. Alice pays Tumbler if and only if Tumbler solves RSA puzzle z*
2. Tumbler reveals ϵ* if and only if Alice pays.

Tumbler
1. Makes m real puzzles:
for i in m: Di = Blind(z*, Ri)...and n fake puzzles:
for j in n: Fi = RSA(PK, Pi)
3. Reveals fake puzzles
by sending solutions.

Shuffle(D1,D2 …, Dm, F1, F2, …, Fn)= (B1,B2,B3, … Bn+m)(q1,Y1),(q2,Y2),(q3,Y3),...
(P1, P2, … Pn)

5. Checks fake puzzles
values “H(X) = Y”
correctly computed.

(X2, X5, X11, …)

6. A proves all real puzzles
unblind to same puzzle z*

7. decrypts q’slearns ϵ*(X1, X3, X4, …)

2. Solves/ encrypts:
for i in m+n:ϵi = RSA-1(SK, Bi)
qi = Enc(Xi, Si)
Yi = H(Xi)

4. Reveals Xi
of fake puzzles.

(R1, R2, … Rm)
Transaction offer
H(X1) = Y1 AND H(X3) AND H(X4) … forTransaction fulfill
X1, X3, X4, ...

If Tumbler computes any (qi,ϵi,Yi) of the real puzzles correctly Alice learns ϵ*,25thus to cheat Alice, Tumbler must corrupt all the real and none of the fake puzzles.

TumbleBit: Puzzle-Solver-Protocol

I can’t tell which B’s
are real or fake.

z*

Alice

Fair exchange/contingent payment for an RSA puzzle solution to z*:
1. Alice pays Tumbler if and only if Tumbler solves RSA puzzle z*
2. Tumbler reveals ϵ* if and only if Alice pays.

Tumbler
1. Makes m real puzzles:
for i in m: Di = Blind(z*, Ri)...and n fake puzzles:
for j in n: Fi = RSA(PK, Pi)
3. Reveals fake puzzles
by sending solutions.

Shuffle(D1,D2 …, Dm, F1, F2, …, Fn)= (B1,B2,B3, … Bn+m)(q1,Y1),(q2,Y2),(q3,Y3),...

2. Solves/ encrypts:
for i in m+n:ϵi = RSA-1(SK, Bi)
qi = Enc(Xi, Si)
Yi = H(Xi)

Probability(Tumbler successfully cheats) = (m+n choose m) = ~1/(280)(P1, P2, … Pn)
4. Reveals Xi
m = # of real puzzles = 15
5. Checks fake puzzlesof fake puzzles.
(X2, X5, X11, …)
n = # of fake puzzles= 285
values “H(X) = Y”
correctly computed.
6. A proves all real puzzles
unblind to same puzzle z*

7. decrypts q’slearns ϵ*(X1, X3, X4, …)(R1, R2, … Rm)
Transaction offer
H(X1) = Y1 AND H(X3) AND H(X4) … forTransaction fulfill
X1, X3, X4, ...

If Tumbler computes any (qi,ϵi,Yi) of the real puzzles correctly Alice learns ϵ*,26thus to cheat Alice, Tumbler must corrupt all the real and none of the fake puzzles.

TumbleBit: Puzzle-Promise-Protocol
At the end of this protocol: Bob should be convinced that for a (z, c):
1. The ciphertext c decrypts to σ under a key ϵ i.e Dec(ϵ,c) = σ
2. AND the key ϵ is the solution to the RSA-puzzle z.
The protocol should never: allow Bob to learn a valid σ (without paying).
Bob

TumblerThis is why the protocol is hard,
otherwise Tumbler could convince Bob
by just sending (c,z,ϵ,σ) and let Bob check.

27

TumbleBit: Puzzle-Promise-Protocol
At the end of this protocol: Bob should be convinced that for a (z, c):
1. The ciphertext c decrypts to σ under a key ϵ i.e Dec(ϵ,c) = σ
2. AND the key ϵ is the solution to the RSA-puzzle z.
The protocol should never: allow Bob to learn a valid σ (without paying).

Tumbler

1. B sends: a mix of hashes of valid and invalid claim transactions.

Bob

B = H(T1),H(T2),H(T3),H(T4),H(T5),H(T6)
2. T Signs & Encrypts σ:
for Bi in B:
σi = Sign(Bi)zi = RSA-1(SK,ϵi), ci = Enc(ϵi,σi)This is why the protocol is hard,(z1,c1),(z2,c2),(z3,c3),(z4,c4),(z5,c5),(z6,c6)
otherwise Tumbler could convince Bob
by just sending (c,z,ϵ,σ) and let Bob check.
T1,T2,T3,T4,T5,T6

4. T Reveals: ϵi forinvalid transactions.

ϵ2,ϵ3,ϵ5

3. B: reveals
transactions.
5. B checks: invalidtransactions σi arecorrectly computed.

6. Bob and Tumbler run “quotient protocol” ensuring that:
if Bob learns ϵ1, Bob can use that knowledge to learn ϵ4,ϵ6.
(ϵ4/ϵ1 mod N, ϵ6/ϵ4 mod N)

If Tumbler computes any (ϵi,σi) of the valid transactions correctly Bob learns a σ/gets paid,
28
thus to cheat Bob, Tumbler must all corrupt all the valid and none of the invalid transactions.

TumbleBit: Puzzle-Promise-Protocol
At the end of this protocol: Bob should be convinced that for a (z, c):
1. The ciphertext c decrypts to σ under a key ϵ i.e Dec(ϵ,c) = σ
2. AND the key ϵ is the solution to the RSA-puzzle z.
The protocol should never: allow Bob to learn a valid σ (without paying).
1. B sends: a mix of hashes of valid and invalid claim transactions.

TumblerBob

B = H(T1),H(T2),H(T3),H(T4),H(T5),H(T6)
2. T Signs & Encrypts σ:
for Bi in B:
σi = Sign(Bi)zi = RSA-1(SK,ϵi), ci = Enc(ϵi,σi)This is why the protocol is hard,(z1,c1),(z2,c2),(z3,c3),(z4,c4),(z5,c5),(z6,c6)
otherwise Tumbler could convince Bob
by just sending (c,z,ϵ,σ) and let Bob check.

Probability(Tumbler successfully cheats) = (m+n choose m) = ~1/(280)
3. B: reveals
T1,T2,T3,T4,T5,T6
m = # of validtransactions = 42transactions.
n = # of invalid transactions = 42

4. T Reveals: ϵi forinvalid transactions.

ϵ2,ϵ3,ϵ55. B checks: invalidtransactions σi arecorrectly computed.

6. Bob and Tumbler run “quotient protocol” ensuring that:
if Bob learns ϵ1, Bob can use that knowledge to learn ϵ4,ϵ6.
(ϵ4/ϵ1 mod N, ϵ6/ϵ4 mod N)

If Tumbler computes any (ϵi,σi) of the valid transactions correctly Bob learns a σ/gets paid,
29
thus to cheat Bob, Tumbler must all corrupt all the valid and none of the invalid transactions.