Catena: Efficient Non-equivocation via Bitcoin
Wednesday, December 13th, 2017
Alin Tomescu
alinush@mit.edu
Srinivas Devadas
devadas@mit.edu
Cambridge Blockchain Meetup,
Cambridge, MA
Acknowledgements
Neha Narula, MIT DCI
Albert Kwon
Ilia Lebedev
Ling Ren
Chris Fletcher
Charles Herder
Overview
Overview
The equivocation problem
The equivocation problem
Non-equivocation: "Saying the same thing to everybody."
The equivocation problem
Non-equivocation: "Saying the same thing to everybody."
Malicious service
Bob
Alice
The equivocation problem
Non-equivocation: "Saying the same thing to everybody."
Malicious service
Bob
Alice
S1
The equivocation problem
Non-equivocation: "Saying the same thing to everybody."
Malicious service
Bob
Alice
S1
S2
The equivocation problem
Non-equivocation: "Saying the same thing to everybody."
Malicious service
Bob
Alice
S1
S2
S3
The equivocation problem
Non-equivocation: "Saying the same thing to everybody."
Malicious service
Bob
Alice
S1
S2
S3
Might be false, but everybody sees it.
The equivocation problem
Equivocation: "Saying different things to different people."
Malicious service
Bob
Alice
S1
S2
S3
S4
S'4
The equivocation problem
Equivocation: "Saying different things to different people."
Jimmy
Dad
Mom
S1
S2
S3
S4
S'4
The equivocation problem
Equivocation: "Saying different things to different people."
Jimmy
Dad
Mom
S1
S2
S3
S4
S'4
"Mom said I can go outside…"
The equivocation problem
Equivocation: "Saying different things to different people."
Jimmy
Dad
Mom
S1
S2
S3
S4
S'4
"Mom said I can go outside…"
"Dad said I can go outside…"
Catena prevents equivocation!
Catena prevents equivocation!
Malicious service with Catena
Bob
Alice
S1
S2
S3
Damn.
Catena prevents equivocation!
Malicious service with Catena
Bob
Alice
S1
S2
S3
I gotta show Alice and Bob the same S4...
S4
So what?
So what?
Secure software update
So what?
Secure software update
So what?
Secure software update
Secure messaging
So what?
Secure software update
Secure messaging
"Blockchain" for X
Contributions
Contributions
Contributions
Contributions
Contributions
Contributions
Contributions
Overview
Bitcoin blockchain
Block n
Block i
Block j
Bitcoin blockchain
Block n
Block i
Block j
Bitcoin blockchain
Block n
Block i
Block j
Bitcoin blockchain
Block n
Block i
Block j
Bitcoin blockchain
Block n
Block i
Block j
Bitcoin blockchain
Block n
Block i
Block j
txa
Bitcoin blockchain
Block n
Block i
Block j
txa
PKA minted 4Ƀ
Bitcoin blockchain
Block n
Block i
Block j
txa
PKA minted 4Ƀ
txb
PKB has 3Ƀ
Bitcoin blockchain
Block n
Block i
Block j
txb
txa
PKA minted 4Ƀ
from SKA
PKB has 3Ƀ
Bitcoin blockchain
Block n
Block i
Block j
txb
txa
PKA minted 4Ƀ
from SKA
PKB has 3Ƀ
txb "spends" txa's first output
Bitcoin blockchain
Block n
Block i
Block j
txb
txa
s1
PKA minted 4Ƀ
from SKA
Arbitrary statement s1
PKB has 3Ƀ
Data can be embedded in TXNs.
Bitcoin blockchain
Block n
Block i
Block j
txb
txa
PKA minted 4Ƀ
from SKA
PKB has 3Ƀ
Alice gives Bob 3Ƀ,
Bitcoin miners collected 1Ƀ as a fee.
s1
Bitcoin blockchain
Block n
Block i
Block j
txb
txc
s1
PKB has 3Ƀ
from SKB
PKC has 2Ƀ
Bob gives Carol 2Ƀ,
Bitcoin miners collected another Ƀ as a fee.
Bitcoin blockchain
Block i
Block j
Block n
s1
txb
txc
txc'
No double-spent coins: A TXN output can only be referred to by a single TXN input.
Moral of the story
Proof-of-work (PoW) consensus ⇒ No double spends
Either TX2 or TX2' but not both!
TX1
TX2'
TX2
Moral of the story
Proof-of-work (PoW) consensus ⇒ No double spends
Either s2 or s2'
but not both!
TX1
TX2'
TX2
s1
s2
s'2
Overview
Previous work
Block i
Block j
Block n
s1
s2
TX
TX
TX
s3
Previous work
Block i
Block j
Block n
Need to download
full blocks to find inconsistent s'3
s1
s2
TX
TX
TX
s3
TX
s'3
Previous work
Block i
Block j
Block n
...or trust majority of nodes to not hide statements.
s1
s2
TX
TX
TX
s3
TX
s'3
Our work
Block i
Block j
Block n
s1
s2
TX
TX
TX
s3
TX
s'3
No inconsistent s'3 as it would require a double-spend!
Previous work
Block i
Block j
Block n
s1
s2
TX
TX
TX
s3
TX
s'3
Our work
Block i
Block j
Block n
s1
s2
TX
TX
TX
s3
TX
s'3
Overview
Starting a Catena log
Catena
log server
Server's funds
Starting a Catena log
GTX
Block i
Genesis TXN
Catena
log server
Appending to a Catena log
s1
GTX
Block i
Block j
Catena
log server
TX1
Appending to a Catena log
s1
GTX
TX1
Block i
Block j
s2
TX2
Block n
Catena
log server
Appending to a Catena log
s1
GTX
Block i
Block j
Catena
log server
s2
Block n
Next, unique s3
TX1
TX2
Appending to a Catena log
Advantages:
(1) Hard to fork
(2) Efficient to verify
s1
GTX
Block i
Block j
Catena
log server
s2
Block n
Next, unique s3
TX1
TX2
Appending to a Catena log
Advantages:
(1) Hard to fork
(2) Efficient to verify
Disadvantages:
(1) 6-block confirmation delay
s1
GTX
Block i
Block j
Catena
log server
s2
Block n
TX1
TX2
Next, unique s3
Appending to a Catena log
Advantages:
(1) Hard to fork
(2) Efficient to verify
Disadvantages:
(1) 6-block confirmation delay
(2) 1 statement every 10 minutes
s1
GTX
Block i
Block j
Catena
log server
s2
Block n
TX1
TX2
Next, unique s3
Appending to a Catena log
Advantages:
(1) Hard to fork
(2) Efficient to verify
Disadvantages:
(1) 6-block confirmation delay
(2) 1 statement every 10 minutes
(3) Must pay Bitcoin TXN fees
s1
GTX
Block i
Block j
Catena
log server
s2
Block n
TX1
TX2
Next, unique s3
Appending to a Catena log
Advantages:
(1) Hard to fork
(2) Efficient to verify
Disadvantages:
(1) 6-block confirmation delay
(2) 1 statement every 10 minutes
(3) Must pay Bitcoin TXN fees
(4) No freshness guarantee
s1
GTX
Block i
Block j
Catena
log server
s2
Block n
TX1
TX2
Next, unique s3
Overview
Efficient auditing
Efficient auditing
Catena
log server
Catena
client
Efficient auditing
Catena
log server
Catena
client
Bitcoin P2P
(11,500 nodes)
Efficient auditing
Catena
log server
Catena
client
Header i
GTX
Bitcoin P2P
(11,500 nodes)
Efficient auditing
Catena
log server
Catena
client
Header i
GTX
Bitcoin P2P
(11,500 nodes)
Q: Next block header(s)?
Efficient auditing
Catena
log server
Catena
client
Header i
GTX
Bitcoin P2P
(11,500 nodes)
Header i+1
Header j
80 bytes each
Efficient auditing
Catena
log server
Catena
client
Header i
Header j
GTX
Bitcoin P2P
(11,500 nodes)
Efficient auditing
Catena
log server
Catena
client
Header i
Header j
GTX
Bitcoin P2P
(11,500 nodes)
Q: What is s1 in the log?
Efficient auditing
Catena
log server
Catena
client
Header i
Header j
GTX
Bitcoin P2P
(11,500 nodes)
TX1
s1
600 bytes
Efficient auditing
Catena
log server
Catena
client
Header i
Header j
TX1
s1
GTX
Bitcoin P2P
(11,500 nodes)
Efficient auditing
Catena
log server
Catena
client
Header i
Header j
TX1
s1
GTX
Q: Next block header(s)?
Bitcoin P2P
(11,500 nodes)
Efficient auditing
Catena
log server
Catena
client
Header i
Header j
TX1
s1
GTX
Header j+1
Header n
Bitcoin P2P
(11,500 nodes)
Efficient auditing
Catena
log server
Catena
client
Header i
Header j
Header n
TX1
s1
GTX
Bitcoin P2P
(11,500 nodes)
Efficient auditing
Catena
log server
Catena
client
Header i
Header j
Header n
TX1
s1
GTX
Q: What is s2 in the log?
Bitcoin P2P
(11,500 nodes)
Efficient auditing
Catena
log server
Catena
client
Header i
Header j
Header n
TX1
s1
GTX
TX2
s2
Bitcoin P2P
(11,500 nodes)
Efficient auditing
Catena
log server
Catena
client
Header i
Header j
Header n
TX1
s1
GTX
TX2
s2
Bitcoin P2P
(11,500 nodes)
Auditing bandwidth
e.g., 500K block headers + 10K statements = ~46 MB
(80 bytes each)
(around 600 bytes each)
Overview
Catena scalability
Catena client 2
Catena client 1
Catena client 200,000?
...
P2P
>11,500 full nodes
Supports up to ~1,345,500 incoming connections
Source: https://bitnodes.earn.com/
Catena scalability
Catena client 2
Catena client 1
Catena client 200,000?
Q: Next block header(s)?
...
Q: Next block header(s)?
Q: Next block header(s)?
P2P
>11,500 full nodes
Supports up to ~1,345,500 incoming connections
Source: https://bitnodes.earn.com/
Catena scalability
Q: Next block header(s)?
Catena client 2
Catena client 1
Catena client 200,000?
Q: Next block header(s)?
Q: Next block header(s)?
...
200,000 Catena clients ⇒ "Accidental" DDoS attack on Bitcoin.
P2P
>11,500 full nodes
Supports up to ~1,345,500 incoming connections
Source: https://bitnodes.earn.com/
Catena scalability
Header Relay Network (HRN)
Volunteer nodes
Blockchain explorers
Facebook, Twitter, GitHub, etc.
...
P2P
Header 1
Header n
Catena client 2
Catena client 1
Catena client 200,000
Catena scalability
Header Relay Network (HRN)
Volunteer nodes
Blockchain explorers
Facebook, Twitter, GitHub, etc.
Q: Next block header(s)?
...
P2P
Header 1
Header n
Catena client 2
Catena client 1
Catena client 200,000
Q: Next block header(s)?
Q: Next block header(s)?
Catena scalability
Q: Next block header(s)?
Q: Next block header(s)?
Q: Next block header(s)?
Header Relay Network (HRN)
Volunteer nodes
Blockchain explorers
Facebook, Twitter, GitHub, etc.
...
P2P
Header 1
Header n
Catena client 2
Catena client 1
Catena client 200,000
The cost of a statement
The cost of a statement
To append a statement, must issue TXN and pay fee.
The cost of a statement
To append a statement, must issue TXN and pay fee.
TXN size: 235-byte
The cost of a statement
To append a statement, must issue TXN and pay fee.
TXN size: 235-byte
Fee (as of Dec 13th, 2017): $16.24 (10 mins)
Latest fees: https://bitcoinfees.info/
The cost of a statement
To append a statement, must issue TXN and pay fee.
TXN size: 235-byte
Fee (as of Dec 13th, 2017): $16.24 (10 mins)
PS: Statements can be "batched" using Merkle trees.
Latest fees: https://bitcoinfees.info/
Overview
Secure software update
Secure software update
Example attack:
(1) Compromise bitcoin.org (or the network)
Secure software update
Example attack:
(1) Compromise bitcoin.org (or the network)
(2) Change the Bitcoin binary to your malicious binary
Secure software update
Example attack:
(1) Compromise bitcoin.org (or the network)
(2) Change the Bitcoin binary to your malicious binary
(3) Wait for people to install your malicious Bitcoin binary
Secure software update
Example attack:
(1) Compromise bitcoin.org (or the network)
(2) Change the Bitcoin binary to your malicious binary
(3) Wait for people to install your malicious Bitcoin binary
(4) Steal their coins, steal their data, etc.
Secure software update
Example attack:
(1) Compromise bitcoin.org (or the network)
(2) Change the Bitcoin binary to your malicious binary
(3) Wait for people to install your malicious Bitcoin binary
(4) Steal their coins, steal their data, etc.
Example: bitcoin.org, "0.13.0 Binary Safety Warning," August 17th, 2016
Secure software update
Example attack:
(1) Compromise bitcoin.org (or the network)
(2) Change the Bitcoin binary to your malicious binary
(3) Wait for people to install your malicious Bitcoin binary
(4) Steal their coins, steal their data, etc.
Example: bitcoin.org, "0.13.0 Binary Safety Warning," August 17th, 2016
Typical defense: Sign your binaries with SK and protect SK.
Secure software update
Example attack:
(1) Compromise bitcoin.org (or the network)
(2) Change the Bitcoin binary to your malicious binary
(3) Wait for people to install your malicious Bitcoin binary
(4) Steal their coins, steal their data, etc.
Example: bitcoin.org, "0.13.0 Binary Safety Warning," August 17th, 2016
Typical defense: Sign your binaries with SK and protect SK.
Problem: (1) Not everyone checks sig. (2) Hard to detect stolen SK.
Secure software update
Example attack:
(1) Compromise bitcoin.org (or the network)
(2) Change the Bitcoin binary to your malicious binary
(3) Wait for people to install your malicious Bitcoin binary
(4) Steal their coins, steal their data, etc.
Example: bitcoin.org, "0.13.0 Binary Safety Warning," August 17th, 2016
Typical defense: Sign your binaries with SK and protect SK.
Problem: (1) Not everyone checks sig. (2) Hard to detect stolen SK.
Solution: Publish signatures in a Catena log ⇒ Can at least detect.
Software transparency to the rescue
h1
GTX
Block i
Block j
Catena log for Bitcoin binaries
h1 = SHA256(bitcoin-0.0.1.tar.gz)
Software transparency to the rescue
h1
GTX
Block i
Block j
h2'
Block n
h1 = SHA256(bitcoin-0.0.1.tar.gz)
h2' = SHA256(evilcoin-0.0.2.tar.gz)
Catena log for Bitcoin binaries
Software transparency to the rescue
h1
GTX
Block i
Block j
h2'
Block n
Catena log for Bitcoin binaries
h1 = SHA256(bitcoin-0.0.1.tar.gz)
h2' = SHA256(evilcoin-0.0.2.tar.gz)
h2 = SHA256(bitcoin-0.0.2.tar.gz)
h2
Software transparency to the rescue
h1
GTX
Block i
Block j
h2'
Block n
Catena log for Bitcoin binaries
h1 = SHA256(bitcoin-0.0.1.tar.gz)
h2' = SHA256(evilcoin-0.0.2.tar.gz)
h2 = SHA256(bitcoin-0.0.2.tar.gz)
h2
Must double-spend to equivocate!
Overview
KeyChat: Secure messaging via Bitcoin
Keybase.io + Bitcoin + Catena.
KeyChat: Secure messaging via Bitcoin
Keybase.io + Bitcoin + Catena.
Impersonation attack as hard as forking Bitcoin.
KeyChat: Secure messaging via Bitcoin
Keybase.io + Bitcoin + Catena.
Impersonation attack as hard as forking Bitcoin.
MIT PRIMES high schoolers:
Yiming Zheng, John Kuszmaul, Robert Chen
Public-key distribution
Public-key distribution
PKM, SKM
PKA, SKA
PKB, SKB
Public-key distribution
PKA
PKM, SKM
PKA, SKA
PKB, SKB
Public-key distribution
PKA
PKM
PKM, SKM
Alice's PKM
PKA, SKA
PKB, SKB
Public-key distribution
PKB
PKM, SKM
Alice's PKM
PKA, SKA
PKB, SKB
Public-key distribution
PKM
PKB
PKM, SKM
Alice's PKM
Bob's PKM
PKA, SKA
PKB, SKB
Public-key distribution
PKM, SKM
Alice's PKM
Bob's PKM
PKA, SKA
PKB, SKB
Public-key distribution
EncM(msg)
PKM, SKM
Alice's PKM
Bob's PKM
PKA, SKA
PKB, SKB
Public-key distribution
EncM(msg)
Alice's PKM
Bob's PKM
PKA, SKA
PKB, SKB
PKM, SKM
I know their message 'msg'!
Public-key distribution
EncM(msg)
EncB(msg)
Alice's PKM
Bob's PKM
PKA, SKA
PKB, SKB
PKM, SKM
Public-key distribution
EncA(msg')
EncM(msg')
PKM, SKM
Alice's PKM
Bob's PKM
PKA, SKA
PKB, SKB
Ha! Another message 'msg'!
Public-key distribution
Using Certificate Authorities (CAs) does not help much: Mallory compromises or coerces CA instead.
PKM, SKM
Alice's PKM
Bob's PKM
EncA(msg')
EncM(msg')
PKA, SKA
PKB, SKB
Public-key distribution
A = {Alice, PKA}, SKA
B = {Bob, PKB}, SKB
B
A
t1
Public-key distribution
A = {Alice, PKA}, SKA
B = {Bob, PKB}, SKB
C
B
E
D
A
B
A
t1
t2
Public-key distribution
A = {Alice, PKA}, SKA
B = {Bob, PKB}, SKB
C
B
E
D
A
B
A
t1
t2
Public-key distribution
A = {Alice, PKA}, SKA
B = {Bob, PKB}, SKB
C
B
E
D
A
B
A
t1
A' = {Alice, PKM}, SKM
B' = {Bob, PKM}, SKM
t2
Public-key distribution
A = {Alice, PKA}, SKA
B = {Bob, PKB}, SKB
C
B
E
D
A
B
A
t1
A' = {Alice, PKM}, SKM
B' = {Bob, PKM}, SKM
t2
B'
A'
t3
Public-key distribution
A = {Alice, PKA}, SKA
B = {Bob, PKB}, SKB
C
B
E
D
A
B
A
t1
A' = {Alice, PKM}, SKM
B' = {Bob, PKM}, SKM
t2
B'
A'
t3
I've been impersonated!
Public-key distribution
A = {Alice, PKA}, SKA
B = {Bob, PKB}, SKB
C
B
E
D
A
B
A
t1
A' = {Alice, PKM}, SKM
B' = {Bob, PKM}, SKM
t2
B'
A'
t3
I've been impersonated!
I've been impersonated!
Public-key distribution
A = {Alice, PKA}, SKA
B = {Bob, PKB}, SKB
C
B
E
D
A
B
A
t1
A' = {Alice, PKM}, SKM
B' = {Bob, PKM}, SKM
B'
A
t3
t2
I'm not impersonated.
Public-key distribution
A = {Alice, PKA}, SKA
B = {Bob, PKB}, SKB
C
B
E
D
A
B
A
t1
A' = {Alice, PKM}, SKM
B' = {Bob, PKM}, SKM
B'
A
t3
B
A'
t3'
t2
I'm not impersonated.
I'm not impersonated.
Public-key distribution
EncA'(msg)
A = {Alice, PKA}, SKA
B = {Bob, PKB}, SKB
C
B
E
D
A
B
A
t1
A' = {Alice, PKM}, SKM
B' = {Bob, PKM}, SKM
B'
A
t3
B
A'
t3'
t2
Great, gotta say something to Alice...
Public-key distribution
EncA'(msg)
A = {Alice, PKA}, SKA
B = {Bob, PKB}, SKB
C
B
E
D
A
B
A
t1
A' = {Alice, PKM}, SKM
B' = {Bob, PKM}, SKM
B'
A
t3
B
A'
t3'
t2
Great, gotta say something to Alice...
KeyChat
Idea: Store t1, t2, ..., tn in a Catena log.
KeyChat
Idea: Store t1, t2, ..., tn in a Catena log.
C
B
E
D
A
B
A
t1
B'
A
t3
B
A'
t3'
t2
KeyChat
Idea: Store t1, t2, ..., tn in a Catena log.
C
B
E
D
A
B
A
t1
B'
A
t3
B
A'
t3'
t2
Block i
Block j
Block n
t1
t2
t3
t'3
Publishing t'3 and t3 would require a double-spend!
Overview
I need a "blockchain" for ...
I need a "blockchain" for ...
IoT? Self-driving cars? Digital identity? Issue diplomas? Health care? Voting?
I need a "blockchain" for ...
IoT? Self-driving cars? Digital identity? Issue diplomas? Health care? Voting?
"Blockchain" = Byzantine State Machine Replication (SMR)
I need a "blockchain" for ...
IoT? Self-driving cars? Digital identity? Issue diplomas? Health care? Voting?
"Blockchain" = Byzantine State Machine Replication (SMR) =
= Agree on log of ops + Execute ops
I need a "blockchain" for ...
IoT? Self-driving cars? Digital identity? Issue diplomas? Health care? Voting?
"Blockchain" = Byzantine State Machine Replication (SMR) =
= Agree on log of ops + Execute ops = Agree on final state.
I need a "blockchain" for ...
IoT? Self-driving cars? Digital identity? Issue diplomas? Health care? Voting?
"Blockchain" = Byzantine State Machine Replication (SMR) =
= Agree on log of ops + Execute ops = Agree on final state.
I need a "blockchain" for ...
IoT? Self-driving cars? Digital identity? Issue diplomas? Health care? Voting?
"Blockchain" = Byzantine State Machine Replication (SMR) =
= Agree on log of ops + Execute ops = Agree on final state.
Permissioned "blockchain:"
I need a "blockchain" for ...
IoT? Self-driving cars? Digital identity? Issue diplomas? Health care? Voting?
"Blockchain" = Byzantine State Machine Replication (SMR) =
= Agree on log of ops + Execute ops = Agree on final state.
Permissioned "blockchain:"
I need a "blockchain" for ...
IoT? Self-driving cars? Digital identity? Issue diplomas? Health care? Voting?
"Blockchain" = Byzantine State Machine Replication (SMR) =
= Agree on log of ops + Execute ops = Agree on final state.
Permissioned "blockchain:"
I need a "blockchain" for ...
IoT? Self-driving cars? Digital identity? Issue diplomas? Health care? Voting?
"Blockchain" = Byzantine State Machine Replication (SMR) =
= Agree on log of ops + Execute ops = Agree on final state.
Permissioned "blockchain:"
I need a "blockchain" for ...
IoT? Self-driving cars? Digital identity? Issue diplomas? Health care? Voting?
"Blockchain" = Byzantine State Machine Replication (SMR) =
= Agree on log of ops + Execute ops = Agree on final state.
Permissioned "blockchain:"
Permissionless "blockchain:" Roll your own. But proceed with caution?
Conclusions
Conclusions
What we did:
Conclusions
What we did:
Why it matters:
For more, read our paper!
Ask me questions!
Block j
Block n
s1
s2
s'3
Block i
Block j
Block n
s1
s2
s3
s'3
s3
Block i
No inconsistent s'3 as it would require a double-spend!
Need to download
full blocks to find inconsistent s'3
Previous work
Catena
Extra slides
What is non-equivocation?
Public-key directory
What is non-equivocation?
Public-key directory
What is non-equivocation?
Public-key directory
PKA
PKB
t1
Bob
Alice
s1 = SHA256(t1)
What is non-equivocation?
Public-key directory
Bob
Alice
t2
PKA
PKB
t1
PKA
PKB
s1 = SHA256(t1)
s2 = SHA256(t2)
What is non-equivocation?
Public-key directory
Bob
Alice
t2
PKA
PKB
t1
PKA
PKB
s1 = SHA256(t1)
s2 = SHA256(t2)
What is non-equivocation?
Public-key directory
Bob
Alice
t2
PKA
PKB
t1
PKA
PKB
s1 = SHA256(t1)
s2 = SHA256(t2)
What is non-equivocation?
Bob
Alice
t2
PKA
PKB
t1
PKA
PKB
PKA'
s1 = SHA256(t1)
s2 = SHA256(t2)
Public-key directory
What is non-equivocation?
Bob
Alice
t2
PKA
PKB
t1
PKA
PKB
PKA'
s1 = SHA256(t1)
s2 = SHA256(t2)
Public-key directory
What is non-equivocation?
Good: "Stating the same thing to all people."
Bob
Alice
t2
PKA
PKB
t1
PKA
PKB
PKA'
s1 = SHA256(t1)
s2 = SHA256(t2)
Public-key directory
What is non-equivocation?
Good: "Stating the same thing to all people."
Bob
Alice
t2
s1 = SHA256(t1)
s2 = SHA256(t2)
PKA
PKB
t1
PKA
PKB
PKA'
Including statements that are
incorrect at the application-layer
Public-key directory
What is equivocation?
S1
PKA
PKB
t1
Public-key directory
What is equivocation?
Alice
t2
PKA
PKB
PKB'
PKA
PKB
t1
Public-key directory
S1
S2
What is equivocation?
Bob
Alice
t2'
PKA
PKB
PKA'
t2
PKA
PKB
PKB'
PKA
PKB
t1
Public-key directory
S1
S2
S2'
What is equivocation?
Bob
Alice
t2'
PKA
PKB
PKA'
t2
PKA
PKB
PKB'
PKA
PKB
t1
Public-key directory
S1
S2
S2'
What is equivocation?
Bob
Alice
t2'
PKA
PKB
PKA'
t2
PKA
PKB
PKB'
PKA
PKB
t1
Public-key directory
S1
S2
S2'
What is equivocation?
MITM
Bob
Alice
t2'
PKA
PKB
PKA'
t2
PKA
PKB
PKB'
PKA
PKB
t1
Public-key directory
S1
S2
S2'
What is equivocation?
Bad: "Stating different things to different people.'"
MITM
Bob
Alice
t2'
PKA
PKB
PKA'
t2
PKA
PKB
PKB'
PKA
PKB
t1
Public-key directory
S1
S2
S2'
Bitcoin: The full picture
Payment TXs
blocki
A ➝ ,
95K
A ➝ ,
95K
B ➝ A, $100K
Peer-to-peer network
Miners
A
Customers
Merchants
Payment verification
A ➝ , $95K
blockj
A ➝ , $95K
Catena transaction format
A single spendable output ⇒ No forks
txi
"Change" coins back to server
(public key)
Unspendable OP_RETURN output with arbitrary data
Coins from server for paying TX fees
(digital signature)
txj
txi
txk
<data>
BKD: A Bitcoin-backed PKD
Catena: Hard-to-fork, append-only log (Bitcoin-backed)
BKD: Hard-to-fork public-key directory (Catena-backed)
A
B
A'
B'
E
D
A"
B"
D'
C
TX
TX
TX
t1
t3
t2
Bitcoin blockchain
Block n'
Block i
Block j
Blockchain forks ⇔ Double-spent coins
Block n
s1
txb
txc
txc'
Previous work
"Liar, liar, coins on fire!" (CCS '15)
Previous work
tx1
"Liar, liar, coins on fire!" (CCS '15)
tx1[0] = (2Ƀ, PK)
SK, PK
Previous work
tx1
"Liar, liar, coins on fire!" (CCS '15)
tx1[0] = (2Ƀ, PK)
SK, PK
signSK(i, s)
signSK(i, s')
Previous work
tx1
"Liar, liar, coins on fire!" (CCS '15)
SK, PK
signSK(i, s)
signSK(i, s')
extractSK()
secret key SK
Previous work
tx2
tx1
"Liar, liar, coins on fire!" (CCS '15)
SIGSK(tx1[0], tx2)
tx2[0] = (2Ƀ, PK')
SK, PK
extractSK()
secret key SK
signSK(i, s)
signSK(i, s')
Previous work
tx2
tx1
"Liar, liar, coins on fire!" (CCS '15)
SK, PK
Disincentivizes equivocation by locking Bitcoin funds under SK.
Does not prevent equivocation by malicious outsiders!
tx2[0] = (2Ƀ, PK')
SIGSK(tx1[0], tx2)