Discussion:
Combining SPV and Stealth addresses
(too old to reply)
Henning Kopp via bitcoin-dev
2017-05-04 12:51:39 UTC
Permalink
Raw Message
Hi all,

Recently I think a lot about combining Stealth addresses with SPV but
I did not come to a satisfying conclusion, so I post this as a
challenge to the wider community. Maybe you have an idea.

## Explanation of SPV
In SPV a thin client puts his public keys in a bloom filter
and asks a full node to give him Merkle proofs of all transactions
whose pubkey are in the bloom filter. Since a bloom filter has a lot
of false positives depending on the parameters, this gives privacy to
the thin client, since the full node cannot detect if a specific
transaction belongs to the thin client. This is cool if you want to
use Bitcoin on your smartphone.

## Explanation of Stealth Addresses
Stealth addresses on the other hand enable receiver privacy. The
sender of a transaction derives a one-time pubkey to which he sends the
money. The receiver can check if the money was sent to him and recover
the one-time private key. This is cool, since an observer cannot
decide if two payments belong to the same recipient. Further the
recipient needs only to have one pubkey.
For a more formal explanation see https://github.com/genjix/bips/blob/master/bip-stealth.mediawiki#Reuse_ScanPubkey
I will use their notation in the following.

## The Problem
My line of thought was to combine stealth addresses with spv, so that
I can use stealth addresses on my smart phone without losing privacy.

Basically to check if a payment belongs to a pubkey (Q,R), the full
node needs to check if R' = R + H(dP)*G for each transaction. For this
it needs the private scanning key d.
This sucks, since when I give my d to a full node, he can link all my
transactions. For an online-wallet this may be okay, but not for thin
client synchronisation.

## Ideas
In the following I detail some ideas of me which did not work.

It does not suffice to have a Bloom filter and check if d is
contained since there is no way to recompute d from the equation. If
there were a way to recompute d, the scheme would offer no privacy,
since anyone could compute the private scanning key d and scan for
payments.
So, if we modify the scheme we need to be sure that d is kept private.

Multiparty computation may be possible in theory. The full node and
the thin client could collaboratively check R' = R + H(dP)*G, where d
is the private input of the thin client and R, R',P is provided by the
full node. But this is costly and they need to do it for each
transaction. It may be more costly than simply setting up a full node.

I do not think that some kind of search functionality without leaking
the search pattern (PIR?) would work, since the full node needs to compute on the
data it has found. And further it needs to retrieve the whole Merkle
proofs.

Any better ideas?

Best,
Henning
--
Henning Kopp
Institute of Distributed Systems
Ulm University, Germany

Office: O27 - 3402
Phone: +49 731 50-24138
Web: http://www.uni-ulm.de/in/vs/~kopp
Chris Pacia via bitcoin-dev
2017-05-04 16:23:27 UTC
Permalink
Raw Message
Yes I've had it working using two pushes in op_return.

op_return op_pushdata <flag> op_pushdata <ephem_pubkey>

Flag goes in your filter. You anonymity set is all other transactions using
that same flag.

This is fairly decent privacy but the problem is you still need filter
matches on outgoing transactions to build a functioning wallet. So it might
not be an improvement over standard bloom filters but at least you can do
stealth if you want.

On May 4, 2017 9:00 AM, "Henning Kopp via bitcoin-dev" <
Post by Henning Kopp via bitcoin-dev
Hi all,
Recently I think a lot about combining Stealth addresses with SPV but
I did not come to a satisfying conclusion, so I post this as a
challenge to the wider community. Maybe you have an idea.
## Explanation of SPV
In SPV a thin client puts his public keys in a bloom filter
and asks a full node to give him Merkle proofs of all transactions
whose pubkey are in the bloom filter. Since a bloom filter has a lot
of false positives depending on the parameters, this gives privacy to
the thin client, since the full node cannot detect if a specific
transaction belongs to the thin client. This is cool if you want to
use Bitcoin on your smartphone.
## Explanation of Stealth Addresses
Stealth addresses on the other hand enable receiver privacy. The
sender of a transaction derives a one-time pubkey to which he sends the
money. The receiver can check if the money was sent to him and recover
the one-time private key. This is cool, since an observer cannot
decide if two payments belong to the same recipient. Further the
recipient needs only to have one pubkey.
For a more formal explanation see https://github.com/genjix/
bips/blob/master/bip-stealth.mediawiki#Reuse_ScanPubkey
I will use their notation in the following.
## The Problem
My line of thought was to combine stealth addresses with spv, so that
I can use stealth addresses on my smart phone without losing privacy.
Basically to check if a payment belongs to a pubkey (Q,R), the full
node needs to check if R' = R + H(dP)*G for each transaction. For this
it needs the private scanning key d.
This sucks, since when I give my d to a full node, he can link all my
transactions. For an online-wallet this may be okay, but not for thin
client synchronisation.
## Ideas
In the following I detail some ideas of me which did not work.
It does not suffice to have a Bloom filter and check if d is
contained since there is no way to recompute d from the equation. If
there were a way to recompute d, the scheme would offer no privacy,
since anyone could compute the private scanning key d and scan for
payments.
So, if we modify the scheme we need to be sure that d is kept private.
Multiparty computation may be possible in theory. The full node and
the thin client could collaboratively check R' = R + H(dP)*G, where d
is the private input of the thin client and R, R',P is provided by the
full node. But this is costly and they need to do it for each
transaction. It may be more costly than simply setting up a full node.
I do not think that some kind of search functionality without leaking
the search pattern (PIR?) would work, since the full node needs to compute on the
data it has found. And further it needs to retrieve the whole Merkle
proofs.
Any better ideas?
Best,
Henning
--
Henning Kopp
Institute of Distributed Systems
Ulm University, Germany
Office: O27 - 3402
Phone: +49 731 50-24138
Web: http://www.uni-ulm.de/in/vs/~kopp
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Henning Kopp via bitcoin-dev
2017-05-06 09:38:06 UTC
Permalink
Raw Message
Sorry, I cannot quite follow you. What do you mean with flag?

Best,
Henning
Post by Chris Pacia via bitcoin-dev
Yes I've had it working using two pushes in op_return.
op_return op_pushdata <flag> op_pushdata <ephem_pubkey>
Flag goes in your filter. You anonymity set is all other transactions using
that same flag.
This is fairly decent privacy but the problem is you still need filter
matches on outgoing transactions to build a functioning wallet. So it might
not be an improvement over standard bloom filters but at least you can do
stealth if you want.
On May 4, 2017 9:00 AM, "Henning Kopp via bitcoin-dev" <
Post by Henning Kopp via bitcoin-dev
Hi all,
Recently I think a lot about combining Stealth addresses with SPV but
I did not come to a satisfying conclusion, so I post this as a
challenge to the wider community. Maybe you have an idea.
## Explanation of SPV
In SPV a thin client puts his public keys in a bloom filter
and asks a full node to give him Merkle proofs of all transactions
whose pubkey are in the bloom filter. Since a bloom filter has a lot
of false positives depending on the parameters, this gives privacy to
the thin client, since the full node cannot detect if a specific
transaction belongs to the thin client. This is cool if you want to
use Bitcoin on your smartphone.
## Explanation of Stealth Addresses
Stealth addresses on the other hand enable receiver privacy. The
sender of a transaction derives a one-time pubkey to which he sends the
money. The receiver can check if the money was sent to him and recover
the one-time private key. This is cool, since an observer cannot
decide if two payments belong to the same recipient. Further the
recipient needs only to have one pubkey.
For a more formal explanation see https://github.com/genjix/
bips/blob/master/bip-stealth.mediawiki#Reuse_ScanPubkey
I will use their notation in the following.
## The Problem
My line of thought was to combine stealth addresses with spv, so that
I can use stealth addresses on my smart phone without losing privacy.
Basically to check if a payment belongs to a pubkey (Q,R), the full
node needs to check if R' = R + H(dP)*G for each transaction. For this
it needs the private scanning key d.
This sucks, since when I give my d to a full node, he can link all my
transactions. For an online-wallet this may be okay, but not for thin
client synchronisation.
## Ideas
In the following I detail some ideas of me which did not work.
It does not suffice to have a Bloom filter and check if d is
contained since there is no way to recompute d from the equation. If
there were a way to recompute d, the scheme would offer no privacy,
since anyone could compute the private scanning key d and scan for
payments.
So, if we modify the scheme we need to be sure that d is kept private.
Multiparty computation may be possible in theory. The full node and
the thin client could collaboratively check R' = R + H(dP)*G, where d
is the private input of the thin client and R, R',P is provided by the
full node. But this is costly and they need to do it for each
transaction. It may be more costly than simply setting up a full node.
I do not think that some kind of search functionality without leaking
the search pattern (PIR?) would work, since the full node needs to compute on the
data it has found. And further it needs to retrieve the whole Merkle
proofs.
Any better ideas?
Best,
Henning
--
Henning Kopp
Institute of Distributed Systems
Ulm University, Germany
Office: O27 - 3402
Phone: +49 731 50-24138
Web: http://www.uni-ulm.de/in/vs/~kopp
_______________________________________________
bitcoin-dev mailing list
https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev
Loading...