Applying Private Information Retrieval
to Lightweight Bitcoin Clients
Kaihua Qin, Henryk Hadass, Arthur Gervais and Joel Reardon

Bitcoin SPV Clients2

Simple Payment Verification (SPV) Clients

Blockchain Block3

Simple Payment Verification (SPV) Clients

HeaderBlockchain Block3

Simple Payment Verification (SPV) Clients

HeaderTransactions

Blockchain Block3

Simple Payment Verification (SPV) Clients

HeaderTransactions

Blockchain Block3

Simple Payment Verification (SPV) Clients

HeaderTransactions

Blockchain BlockHashHashHashHash

Transaction Transaction Transaction Transaction
3

Simple Payment Verification (SPV) Clients

HeaderTransactions

Hash

Hash

Blockchain Block
Hash

Hash

Hash

Hash

Transaction Transaction Transaction Transaction
3

Simple Payment Verification (SPV) Clients

HeaderHashTransactions
Merkle Root
Hash

Hash

Blockchain Block
Hash

Hash

Hash

Hash

Transaction Transaction Transaction Transaction
3

Simple Payment Verification (SPV) Clients

SPV client

Full Bitcoin
node4Simple Payment Verification (SPV) Clients

SPV client
Did I receive new coins?

Full Bitcoin
node4Simple Payment Verification (SPV) Clients

SPV client
Did I receive new coins?

Full Bitcoin
nodeRelevant transactions

4

Simple Payment Verification (SPV) Clients

SPV client
Did I receive new coins?

Full Bitcoin
nodeRelevant transactions

Privacy!

4

Bloom Filter

Bloom filter

00000005

Bloom Filter

Insertion

Bloom filter{ @1, @2, @3 }00000005

Bloom Filter

Insertion

Bloom filter{ @1, @2, @3 }0010001005

Bloom Filter

Insertion

Bloom filter{ @1, @2, @3 }00100010105

Bloom Filter

Insertion

Bloom filter{ @1, @2, @3 }00100010105

Bloom Filter

Insertion

Bloom filter

Membership test

{ @1, @2, @3 }0010001010{ @1, @4, @5 }5Bloom Filter

Insertion

Bloom filter

Membership test

{ @1, @2, @3 }0010001010{ @1, @4, @5 }5Bloom Filter

Insertion

Bloom filter

Membership test

{ @1, @2, @3 }00
10001010{ @1, @4, @5 }5Bloom Filter

Insertion

Bloom filter

Membership test!

@4 False positive{ @1, @2, @3 }0010001010{ @1, @4, @5 }target False Positive Rate (FPR)

5

Bloom Filter

Insertion

Bloom filter

Membership test!

@4 False positive{ @1, @2, @3 }0010001010{ @1, @4, @5 }target False Positive Rate (FPR)

5

Bloom Filter

Insertion

Bloom filter

Membership test!

@4 False positive{ @1, @2, @3 }0010001010{ @1, @4, @5 }target False Positive Rate (FPR)@5 True negative
5

BIP-37 (Bloom Filters)

SPV client

Full Bitcoin
node

Full Bitcoinnode6

BIP-37 (Bloom Filters)

Full Bitcoinnode

SPV client@1@2@30100110

Full Bitcoin
nodeBloom filter

6BIP-37 (Bloom Filters)

Full Bitcoinnode

SPV client
Connection
Bloom filter@1@2@301001100100

110

Full Bitcoin
nodeBloom filter

6BIP-37 (Bloom Filters)

Full Bitcoinnode

SPV client
Connection
Bloom filter

0100110transactions

Is transaction relevantfor Bloom filter?

@1@2@30100110

Full Bitcoin
nodeBloom filter

6BIP-37 (Bloom Filters)

Full Bitcoinnode

SPV client
Connection
Bloom filter

0100110

Relevant transactions

Is transaction relevantfor Bloom filter?

@1@2@3010transactions

0110

Full Bitcoin
nodeBloom filter

6BIP-37 (Bloom Filters)

Full Bitcoinnode

SPV client
Connection
Bloom filter

0100110

Relevant transactions

Is transaction relevantfor Bloom filter?

@1@2@3010

transactions

0110

Full Bitcoin
nodeBloom filter

6BIP-37 (Bloom Filters)

Full Bitcoinnode

SPV client
Connection
Bloom filter0100110Relevant transactions

Is transaction relevantfor Bloom filter?

@1@2@3010transactions

0110Bloom filter

Promise:33 mio addresses in the Blockchain
target FPR: 0.1 %Full Bitcoinnode"User addresses hidden amongst
33 000" false positives
6Model and Privacy measure

Blockchain

SPV client7Model and Privacy measure

Blockchain

SPV client

Adversary7Model and Privacy measure

Blockchain+ parameters(seed, FPR)
0100110Bloom filter

SPV client

Adversary7Model and Privacy measure

Blockchain+ parameters(seed, FPR)
010011

All addressesof the Blockchain

0

Bloom filter

SPV client

Adversary7Model and Privacy measure

Blockchain+ parameters(seed, FPR)
010011

All addressesof the Blockchain

0@@@

Bloom filter

SPV client

Total positives

Positive
Positive
Positive

Adversary7Model and Privacy measure

Blockchain+ parameters(seed, FPR)
010011

All addressesof the Blockchain

0@@@

Bloom filter

SPV client

Total positives

Positive
Positive
Positive

Adversary@@@

Positive
Positive
Positive

True positives
7Model and Privacy measure

Blockchain+ parameters(seed, FPR)
010011

All addressesof the Blockchain0@@@

Bloom filter

SPV client

Total positives

Positive
Positive
Positive

Measureprivacy

Adversary@@@

Positive
Positive
Positive

True positives
7Model and Privacy measure

Blockchain+ parameters(seed, FPR)+@

010011

All addressesof the Blockchain

0@@@

Bloom filter

SPV client

Total positives

Positive
Positive
Positive

Measureprivacy

Adversary@@@

Positive
Positive
Positive

True positives
7Model and Privacy measure

Blockchain+ parameters(seed, FPR)+@

010011All addressesof the Blockchain0@@@

Bloom filter
010011

Total positives

Positive
Positive
Positive

0Measure
privacy

Bloom filter 2
SPV client

Adversary@@@

Positive
Positive
Positive

True positives
7

SPV + Bloom Filter

1. Given one Bloom filter, Bitcoin addresses partially linkable- Addresses linkable if < 20 addresses in wallet

2. Given multiple Bloom filter, addresses nearly always linkable

Bloom filter

0100110Gervais et al., On the privacy provisions of bloom filters in lightweight bitcoin clients, ACSAC'148Proposed solution@101@102@. 103..
@200@1@2@3..
.
@1000

1001

10Bloom filter 10100

11Bloom filter 10100

1

10

Bloom filter 20

100

1

100

Bloom filter 2Pre-generate Bitcoin addresses and insert into filter
Keep state about outsourced Bloom filter
Overhead: For 100 addresses, < 1 kb

9Private Information Retrieval

Query the Database
without learning anything
about the query

Blockchain10

Private Information Retrieval

Query the Database
without learning anything
about the query

Blockchain

Solution: Download the entire DB!

10

PIR Versions

PIR

11

PIR Versions
IT-PIRPIR

11

PIR Versions
IT-PIR

PIR

C-PIR

11

PIR Versions
IT-PIR

PIR

C-PIR

11

PIR Versions
IT-PIR

Q1

Q2
Q3

PIR

C-PIR

11

PIR Versions
IT-PIR

Q1

Q2
Q3

Information Theoretic security, assuming
no collision up to a certain degree

PIR

C-PIR

11

PIR Versions
IT-PIR

Q1

Q2
Q3

Information Theoretic security, assuming
no collision up to a certain degree

PIR

C-PIR

Computational PIR, query privacy
via cryptographic means

11

IT-PIR vs. C-PIR

IT-PIRC-PIR

Communication costs

Smaller

BiggerComputation costs

Smaller

BiggerRisk of Collusion

Server can mount sybil attack

Non existent

Robust to missing or incorrect
server response

RobustNon-robust

12The best of both worlds: Hybrid PIR

combines the IT-PIR protocols with the C-PIR protocols
queries are operated in a recursive way
maintains partial privacy of client query information if
the assumptions made by one of the inner protocols is broken
open-source Percy++ library

Devet, C. and Goldberg, I., The best of both worlds: Combining information-theoretic and computational PIR for communication efficiency. PETS’14
13

System Overview(a) PIR servers download the blockchain, constructs PIRdatabases. For each database, the PIR server creates a
description file called manifest file.

Blockchain(a)(b) The user collect all available block headers from e.g.,full node peers.

PIR servers(c)(c) The user fetch the manifest files from the PIR servers tolater efficiently query the PIR database.
(d) The user executes the PIR-SPV protocol, decodes thePIR responses for servers and then performs SPV validation

(b)
(d)

SPV client

Devet, C. and Goldberg, I., The best of both worlds: Combining information-theoretic and computational PIR for communication efficiency. PETS’14
14

Database structure

Manifest files

PIR databases
row/column

Address PIR Manifest

start/end

Merkle Tree PIR Manifest

Transaction PIR Manifest

15

Temporal Division

16

PIR Protocol - Pre-requisites

1) Download Manifest files
Address PIR Manifest
Merkle Tree PIR Manifest
Transaction PIR Manifest

2) Download all Block Header
HTr17

PIR Protocol

18

PIR Protocol

Choose @18

PIR Protocol

Address PIR Manifest

Choose @Merkle Tree PIR Manifest

Transaction PIR Manifest
18

PIR Protocol

Choose @Choose @Row indices

Address PIR Manifest

Merkle Tree PIR Manifest

Transaction PIR Manifest
18

PIR Protocol

Row indices
Block height
Choose @Choose @Row indices

Address PIR Manifest

Merkle Tree PIR Manifest

Transaction PIR Manifest
18

PIR Protocol

Row indices
Block height
Choose @Choose @Row indices
Block Height

Address PIR Manifest

Merkle Tree PIR Manifest

Row indicesTransaction PIR Manifest
18

PIR Protocol

Row indices

TXIDs

Row indices
Block height
Choose @Choose @Row indices
Block Height

Address PIR Manifest

Merkle Tree PIR Manifest

Row indicesTransaction PIR Manifest
18

PIR Protocol

Row indices

TXIDs

Row indices
Block height
Choose @Choose @Row indices
Block Height
Row indices
TXIDs

Address PIR Manifest

Merkle Tree PIR Manifest

Transaction PIR Manifest

Row indices18

PIR Protocol

Row indices

TXIDs

Row indices

Row indices

Block heightTransactions
Choose @Choose @Row indices
Block Height
Row indices
TXIDs

Address PIR Manifest

Merkle Tree PIR Manifest

Transaction PIR Manifest

Row indices18

PIR Protocol

19

PIR Protocol

We have:- Transaction IDs- Block Headers- Our raw transactions

19

PIR Protocol

We have:- Transaction IDs- Block Headers- Our raw transactions

Hash

TXID

TXID

TXID

Transaction

19

PIR Protocol

Hash

We have:- Transaction IDs- Block Headers- Our raw transactions

Hash

Hash

TXID

TXID

TXID

Transaction

19

PIR Protocol

Hash

Merkle RootHash

We have:- Transaction IDs- Block Headers- Our raw transactions

Hash

Hash

TXID

TXID

TXID

Transaction

19

Costs - PIR Database sizes
Bitcoin Data –– Block 1~ 513502 (March 2018)
All-Time blocks
1 to 508462

Monthly blocks
508463 to 512494

Weekly blocks
512495 to 513502

Total size of DB

3.16 GB

176.04 MB

59.11 MB

Size of manifest file65.99 MB175.33 MB

66.97 MB

Total size of DB

10.18 GB

1.46 GB

1.44 GB

Size of manifest file40.90 MB0.32 MB78.62 KB

Total size of DB

15.87 GB

1.30 GB448.91 MB

Size of manifest file

3.03 GB

218.68 MB

72.45 MB

Address PIR DBs

Merkle Tree PIR DBs

Transaction PIR DBs

Platform –– Ubuntu 16.04 (64-bit) OS, Intel Core i7 3.4 GHz CPU, 16 GB of RAM and a 512 GB hard drive20

Manifest File Trie Scheme

In some cases, manifest files are very big
Transform the simple manifest files into a format suitable for PIR queries.
Clients perform interpolation search on these manifest files, under PIR.

21

Bandwidth comparison to verify a single transaction

BIP-37

PIR: 1 server

PIR: 3 servers

Naive SPV

All-Time

102.80 KB

21.54 MB64.61 MB80.27 GBMonthly132.43 KB

1.70 MB5.11 MB159.19 GB

Weekly128.52 KB

666.07 KB

2.00 MB161.47 GB

Platform –– Ubuntu 16.04 (64-bit) OS, Intel Core i7 3.4 GHz CPU, 16 GB of RAM and a 512 GB hard drive22Bandwidth costs to verify a single transaction

23

Cumulative distribution of bandwidth costs
to verify a single transaction(a) All-Time(b) Monthly(b) Weekly

24Further Improvements

Interpolative Search to skip manifest files

More fine granular separation of databases👀🧐

25

Thank you!

26

Manifest Files•

Format{ ...
“address” / “block-height” / “txid” : [“row index start”,“row index end”,“column index start”,“column index end”,]…}•Manifest File Trie Scheme– In some cases, manifest ﬁles have anearly equivalent or even larger size
compared with the database. Thismay incur a poor performance inbandwidth.
– Transform the simple manifest ﬁlesinto a format suitable for PIR queries.
– Clients perform interpolation searchon these manifest ﬁles, under PIR

27

Protocol•••

Data: SPV client C, one or multiple PIR servers S
Result: C obtains the necessary data for a SPV privately
Initialization: S constructs the PIR databases and associated manifest ﬁles; C downloads the manifest ﬁles from S;

a. Query the Address PIR DB

b. Query the Merkle Tree PIR DB

c. Query Transaction PIR DB

1. C selects an address to fetch arecord from the Address PIR DB
manifest ﬁle and generates the PIR
queries based on row indices of theselected record;
2. S computes the result using the PIR
queries on the Address PIR DB;
3. C parses and decodes the result toobtain one or more Address PIR DBentries;

1. C uses the value of the block heightﬁeld of an entry to fetch thecorresponding record from theMerkle Tree PIR DB manifest ﬁleand generates the PIR queries
based on the row indices;
2. S computes the result using the PIR
queries on the Merkle Tree PIR DB;
3. C parses and decodes the result toobtain the requested list of TXIDs;

1. C uses the value of the TXID ﬁeld
from the same entry that was
selected in step b.1, to fetch thecorresponding record from theTransaction PIR DB manifest ﬁle andgenerates the PIR queries based onthe row indices;
2. S computes the result using the PIR
queries on the Transaction PIR DB;
3. C parses and decodes the result toobtain the requested transaction.

28

Evaluation••

Cumulative bandwidth cost required to verify 1~100 transactions
Latency of PIR-SPV (1-server and 3-servers)•Weekly– Single server PIR-SPV has a similar bandwidth cost to BIP-37 SPV when verifying between 20 and 100 transactions.
– In particular, if a client is interested in performing single-sever PIR SPV on 100 transactions which occurred in the past
week, it will take approximately 2 minutes for this query to be executed, with a bandwidth cost of 11.18 MB. In contrast,BIP-37 SPV will require 12.85 MB in the same scenario.
– Clients who are interested in a smaller number of transactions, such as 20, would incur a bandwidth cost of 8.31 MB in
the multi-server setting, with a latency of approximately 62 seconds.
Monthly– In the multi-server setting, a 20-transaction query would incur a bandwidth cost of 12.20 MB with a latency ofapproximately 2.3 minutes.
All-time– Cost is relatively high, but all-time queries are infrequent.

••29