[Bitcoin-development] Bait for reusable addresses

[Bitcoin-development] Bait for reusable addresses

[Gregory Maxwell]

One challenge with reusable addresses is that while they result in a
small constant overhead for full nodes in searching for their own
transactions they create large overheads for SPV nodes.

One way to address this is for the SPV nodes to hand their servers
their blinding private key so that the server may test addresses on
their behalf. The primary problem with this is that it is
non-reputable:  If I show you a blinding private key and say a set of
transactions are related you will be utterly convinced of it, the
transactions really are related. This makes the privacy brittle.

It also has a downside of not being indexable for the server, the
server must do O(clients * reusable-address-txn) work and the work
includes an ECC multiply.

An idea that Adam Back had originally proposed was including optional
"bloom bait", a small token— say 8 bits— that distinguished
transactions which allowed an anonymity set vs filtering trade off.
Such a bait would be indexable, enabling faster lookup too.

But bloom bait has privacy problems more severe than the current SPV
bloom filtering. While you leak information to your SPV servers today
if you use bloom filtering the leak usually goes no further. So a
compromise requires both a statistical attack _and_ using SPV servers
that log data against your interest.  With bloom bait the whole
network can see the relation. That is unfortunate.

I suggest instead that with optional bait is included in an address
that the sender compute H(nonce-pubkey) and then pick one byte at
random out of the first 16 and xor it with the specified bait and
store the result in the transaction.  An SPV server can now index the
bait as it comes in by extracting 16 8-bit keys from each transaction
(the 16 bytes xored with the bait in the transaction).  When the
client wants to search for transactions it can give the server a list
of keys its interested in— including their real key and number of
random number of cover keys.

ObTechnicalWank:  This is a specific simple instance of a general
class of solutions which are related to locally decodable error
correcting codes: E.g. the transaction data represents a codeword in a
vector-space and the degree of freedom provided by the adjustable
prefix is used to ensure that codeword is never more than a certain
distance from a specified point.  The point isn't made public in the
transaction and it's hidden from the server by providing several
points.   There is still an information leak here— as if someone
believes a set of transactions are related they can intersect their
radiuses and test if the intersection is empty, and if it's not assume
that they found the secret bait— but it is substantially lower an
information leak than the prefix case.

I didn't give any though into the parameters 8-bits and 16 dimensions.
Some reasoning should be done to fix the parameters in order to make
them the most useful: e.g.

Systems derived from more complex linear codes might give better
performance, e.g. two secret bloom baits, two prefixes in the
transaction bait0^random_char[0-8], bait1^random_char[0-8],  server
extracts 16 keys.. and returns to the client transactions which have
at least two key matches with their list.

Obviously whatever is used needs to be easy to implement, but schemes
loosely based on fountain codes should only require picking some
things and xoring... so they should be simple enough.

Re: [Bitcoin-development] Bait for reusable addresses

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 4195 bytes --]

On Wed, Jan 15, 2014 at 05:23:04PM -0800, Gregory Maxwell wrote:
> It also has a downside of not being indexable for the server, the
> server must do O(clients * reusable-address-txn) work and the work
> includes an ECC multiply.
> 
> An idea that Adam Back had originally proposed was including optional
> "bloom bait", a small token— say 8 bits— that distinguished
> transactions which allowed an anonymity set vs filtering trade off.
> Such a bait would be indexable, enabling faster lookup too.
> 
> But bloom bait has privacy problems more severe than the current SPV
> bloom filtering. While you leak information to your SPV servers today
> if you use bloom filtering the leak usually goes no further. So a
> compromise requires both a statistical attack _and_ using SPV servers
> that log data against your interest.  With bloom bait the whole
> network can see the relation. That is unfortunate.

Yes, but remember I proposed prefixing in my blockchain data query paper
because it's a trade-off between theoretical good privacy and
brittleness. The real world experience is that users, or to be exact
wallet authors, turn down SPV privacy parameters until bloom filters
have almost no privacy in exchange for little bandwidth usage. (though
load on the server is unchanged of course)

The brittleness comes in because the moment you connect to a malicious,
data-collecting peer, the contents of your wallet are all revealed.
Frankly that'd be a disaster for CoinJoin too, and I think it'd be a
bigger disaster than the poor specificity patterns leaked by prefix
usage. If anyone wants to deanonymize CoinJoin there will be a lot of
incentives to do so, and you only need wallet content data to do that.

> I suggest instead that with optional bait is included in an address
> that the sender compute H(nonce-pubkey) and then pick one byte at
> random out of the first 16 and xor it with the specified bait and
> store the result in the transaction.  An SPV server can now index the
> bait as it comes in by extracting 16 8-bit keys from each transaction
> (the 16 bytes xored with the bait in the transaction).  When the
> client wants to search for transactions it can give the server a list
> of keys its interested in— including their real key and number of
> random number of cover keys.
> 
> I didn't give any though into the parameters 8-bits and 16 dimensions.
> Some reasoning should be done to fix the parameters in order to make
> them the most useful: e.g.
> 
> Systems derived from more complex linear codes might give better
> performance, e.g. two secret bloom baits, two prefixes in the
> transaction bait0^random_char[0-8], bait1^random_char[0-8],  server
> extracts 16 keys.. and returns to the client transactions which have
> at least two key matches with their list.
> 
> Obviously whatever is used needs to be easy to implement, but schemes
> loosely based on fountain codes should only require picking some
> things and xoring... so they should be simple enough.

Well, that's the big question: How much extra data do we need and what's
the chance that this will get turned into miner-committed indexes? Or
even just provided at all? We keep on saying that miner-commitments may
next happen at all because of performance issues, and adding n extra
indexes doesn't exactly help that situation. I really suspect that the
moment that gets implemented we'll see wallet software use that for
simple security reasons, so plan ahead for that.

In the short term without miner-commitments it's just a question of how
much extra load we subject servers to. Again, getting people to even
implement prefixes isn't a trivial argument to make, yet bloom has some
serious scalability problems. (though does do roughly what you're
proposing)

In any case, your "bait" proposal is stealth address specific - how
would you propose applying the same principle to all addresses? Again,
it's a tradeoff between brittleness - connecting to a malicious peer
reveals your wallet - and blockchain stats data.

-- 
'peter'[:-1]@petertodd.org
0000000000000001315c71472fdce344f85f794a7135e25554f2b51dfa6b83c4

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 685 bytes --]

Re: [Bitcoin-development] Bait for reusable addresses

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 440 bytes --]

>
> brittleness. The real world experience is that users, or to be exact
> wallet authors, turn down SPV privacy parameters until bloom filters
> have almost no privacy in exchange for little bandwidth usage.


That's not fundamental though, it just reflects that the only
implementation of this is used on a wide range of devices and doesn't yet
have any notion of bandwidth modes or monitoring. It can and will be
resolved at some point.

[-- Attachment #2: Type: text/html, Size: 678 bytes --]

Re: [Bitcoin-development] Bait for reusable addresses

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 1055 bytes --]

On Fri, Jan 24, 2014 at 12:26:19PM +0000, Mike Hearn wrote:
> >
> > brittleness. The real world experience is that users, or to be exact
> > wallet authors, turn down SPV privacy parameters until bloom filters
> > have almost no privacy in exchange for little bandwidth usage.
> 
> 
> That's not fundamental though, it just reflects that the only
> implementation of this is used on a wide range of devices and doesn't yet
> have any notion of bandwidth modes or monitoring. It can and will be
> resolved at some point.

Resolved for some users, not for all. The underlying trade-off will
always be there; less bandwidth makes it harder, more addresses to check
makes it harder; an HD wallet used properly without re-using addresses
will quickly lead to a fairly full bloom filter unless addresses are
expired, and expiration leads to scenarios where funds can be lost.

I think we need to provide users with better options than that.

-- 
'peter'[:-1]@petertodd.org
000000000000000064ddd387d7548c97c4d42f4df1008d180f306c59e0440f4f

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [Bitcoin-development] Bait for reusable addresses

[Adam Back]

I think prefix has analysis side effects.  There are (at least) 4 things
that link payments: the graph of payment flows, timing, precise amounts, IP
addresses, but with prefix a 5th: the prefix allows public elmination of
candidates connections, I think that may make network flow analysis even
more effective than it has been.

So SPV can be tuned as Mike just said, and as Greg pointed out somewhere
bloom is more private than prefix because its a wallet to node connection,
not a node broadcast, and Mike mentioned embedded Tor in another post to
boost node-capture issues with hostile network.

So reusable addresses are cool for full node recipients (0-bit prefix) or
trusted server offload (your own desktop, VPS, or trusted service provider
node, and solve real problems for the use case of static and donation
addresses particularly with this second delegatable key for no-funds at risk
search (which is even good as Jeremey said for your own node, in a offline
wallet use case).

Now while it would be clearly a very nice win if reusable addresses could be
made SPV-like in network characteristics and privacy, but we dont have a
plausible mechanism yet IMO.  Close as we got was Greg's enhancement of
my/your "bloom bait"/"prefix" concept to make multiple candidate baits to
provide some ambiguity (still allows elimination, just slightly less of it).

If we can find some efficient crypto to solve that last one, we could even
adopt them generally if it was efficient enough without needing interactive
one-use address release.

Maybe we should ask some math/theoretical crypto people if there is anything
like public key watermarking or something that could solve this problem
efficiently.

For the related but different case of transaction level authenticity I like
Alan's server derived but communicated scalar & base to allow the client to
do at least TOFU.

Payment protocol may add another level of identity framework on top of TOFU
addresses (at a lower level than the payment messages defined now), and
without then needing a batch upload of offline signed secondary address
sigature that Mike described a while back, at least in person, maybe online
somewhere (an add on with similar purpose and effect to Alan's TOFU, but
then with revocation, identity and certification for merchants).

I have not talked about payment protocols main app level function I think we
all understand and agree on the purpose and use of the server and optional
client certs in that.  People may wish to add other cert types later (eg
PGP, SSH etc) but this version covers the common merchant tech, and allows
client-side certs to be experimented with for identity also (eg imagine as a
way to enrol with regulated entities like exchanges.)

Tell me if I am misunderstanding anything :)

Adam

On Fri, Jan 24, 2014 at 12:26:19PM +0000, Mike Hearn wrote:
>     brittleness. The real world experience is that users, or to be exact
>     wallet authors, turn down SPV privacy parameters until bloom filters
>     have almost no privacy in exchange for little bandwidth usage.
>
>   That's not fundamental though, it just reflects that the only
>   implementation of this is used on a wide range of devices and doesn't
>   yet have any notion of bandwidth modes or monitoring. It can and will
>   be resolved at some point.Â

Re: [Bitcoin-development] Bait for reusable addresses

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 5508 bytes --]

On Fri, Jan 24, 2014 at 04:42:35PM +0100, Adam Back wrote:
> I think prefix has analysis side effects.  There are (at least) 4 things
> that link payments: the graph of payment flows, timing, precise amounts, IP
> addresses, but with prefix a 5th: the prefix allows public elmination of
> candidates connections, I think that may make network flow analysis even
> more effective than it has been.

You know, we've made this discussion rather confusing because we're
using the term "prefix" for both prefix filters - which are equivalent
to bloom filters but with better scalability - and the act of forcing a
scriptPubKey to match some given prefix. I suggest we call the latter
concept 'wallet clustering' as it can just as easily be applied to bloom
filters, as well as Gregory Maxwell's candidate bait scheme, and for
that matter, prefix filters with a tweak option, e.g. H(scriptPubKey |
nTweak)

So yeah, clustering schemes make network flow analysis easier if the
attacker only has blockchain data to work from. But they can also make
network flow analysis significantly harder for attackers that have query
logs from attackers running nodes, and as we know sybiling the network
to get query logs is very easy. I'd rather develop systems that don't
fail catastrophically against sybil attack.

> So SPV can be tuned as Mike just said, and as Greg pointed out somewhere
> bloom is more private than prefix because its a wallet to node connection,
> not a node broadcast, and Mike mentioned embedded Tor in another post to
> boost node-capture issues with hostile network.

The hostile network is likely to have a significant percentage of
hostile, query-logging nodes. For one thing, running nodes is expensive
and would be even more so in a blocksize limit raising scenario, and a
easy way to pay those costs is by selling query data.

> So reusable addresses are cool for full node recipients (0-bit prefix) or
> trusted server offload (your own desktop, VPS, or trusted service provider
> node, and solve real problems for the use case of static and donation
> addresses particularly with this second delegatable key for no-funds at risk
> search (which is even good as Jeremey said for your own node, in a offline
> wallet use case).

Sure, in some cases you can use zero-length prefixes with trusted nodes;
not many users have access to such nodes.

> Now while it would be clearly a very nice win if reusable addresses could be
> made SPV-like in network characteristics and privacy, but we dont have a
> plausible mechanism yet IMO.  Close as we got was Greg's enhancement of
> my/your "bloom bait"/"prefix" concept to make multiple candidate baits to
> provide some ambiguity (still allows elimination, just slightly less of it).
> 
> If we can find some efficient crypto to solve that last one, we could even
> adopt them generally if it was efficient enough without needing interactive
> one-use address release.

Conversely, it'd be interesting if someone can dig up a proof showing
that doing much better than Gregory's ambiguity tradeoff is impossible.
My gut feeling is that it is, especially if you take into account the
desire for scalability - if we're to make the blocksize bigger assuming
all nodes have all data for every block just isn't going to happen.

> Maybe we should ask some math/theoretical crypto people if there is anything
> like public key watermarking or something that could solve this problem
> efficiently.

Yes, and I think such schemes should be pursued. But in the near-term
what can we offer users?

Remember that making stealth addresses and similar clustering-using
schemes capable of backward compatible upgrades isn't hard; if the
crypto is found later it can be adopted.

What is harder is that people want miners to commit to various types of
indexes - changing those indexes would require a soft-fork and there's
much pressure for those indexes to have very good performance
properties.

> For the related but different case of transaction level authenticity I like
> Alan's server derived but communicated scalar & base to allow the client to
> do at least TOFU.
> 
> Payment protocol may add another level of identity framework on top of TOFU
> addresses (at a lower level than the payment messages defined now), and
> without then needing a batch upload of offline signed secondary address
> sigature that Mike described a while back, at least in person, maybe online
> somewhere (an add on with similar purpose and effect to Alan's TOFU, but
> then with revocation, identity and certification for merchants).

Note how well the OpenPGP + bitcoin address UID ideas I and others have
been talking about meshes with TOFU: the logic for "Do I trust this
address to send money?" and "Do I trust this PGP key to send more
encrypted mail/verify signatures?" is just different questions about the
same human identity, so combining the two is synergistic. For instance I
might want to communicate securely with a friend via email and also send
funds to them securely.

An interesting nuance is ideally that UID can be used for more than just
a single address type, e.g. BIP32 derivation chains can the same root
pubkeys as stealth addresses. Though I don't know if the added
complexity is worthwhile vs. just adding another UID for the BIP32
derivation case.

-- 
'peter'[:-1]@petertodd.org
0000000000000001a2aeb2101283cb4e35d4a038b38a72a21af5092d8d8c9d2e

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 490 bytes --]

Re: [Bitcoin-development] Bait for reusable addresses

[Jeremy Spilman]

> 
> 
> 
> I think we need to provide users with better options than that.
> 

Perfect privacy without extraordinary computational overhead today means downloading everything. But we could provide better tools to *shift* bandwidth requirements rather than try to reduce them. 

I've been thinking about a setup where user runs a UTXO only, and maybe even outbound-connect only (like bitcoinj), full node at home. Then using Tor, mostly for tunneling, they host a hidden service they can connect back to from their smartphone to see balances, manage receive addresses, send funds, etc.

The smartphone is not doing SPV, it's like a web client for the wallet running at home. The initial connection between the smartphone and home wallet has the phone learn two codes, one is the hidden service name, another is an access token which is revocable. You may require further authentication from that point. 

With fast bootstrapping / checkpointing of the UTXO I think usability could be as good as SPV, and you would get push-notification of relevant transactions with zero privacy trade-off.

I wonder if people would want to run such an app, if they would run it on their desktop, a dedicated machine, or an old smartphone or other cheap ARM device.

Re: [Bitcoin-development] Bait for reusable addresses

[Mike Hearn]

[-- Attachment #1: Type: text/plain, Size: 1861 bytes --]

I've thought about [ab]using Tor as a STUN replacement before, but the
issue is a lot of people don't have computers that are switched on all the
time anymore except for their smartphones, which are too weak to calculate
the UTXO set. The trend has been for a while towards laptops, phones and
tablets, all of which are relatively weak.

I think there might be a market for a one-click "bring up an amazon VPS,
sync a full node and make it accessible only to me" type service though!



On Fri, Jan 24, 2014 at 10:58 PM, Jeremy Spilman <jeremy@taplink.co> wrote:

> >
> >
> >
> > I think we need to provide users with better options than that.
> >
>
> Perfect privacy without extraordinary computational overhead today means
> downloading everything. But we could provide better tools to *shift*
> bandwidth requirements rather than try to reduce them.
>
> I've been thinking about a setup where user runs a UTXO only, and maybe
> even outbound-connect only (like bitcoinj), full node at home. Then using
> Tor, mostly for tunneling, they host a hidden service they can connect back
> to from their smartphone to see balances, manage receive addresses, send
> funds, etc.
>
> The smartphone is not doing SPV, it's like a web client for the wallet
> running at home. The initial connection between the smartphone and home
> wallet has the phone learn two codes, one is the hidden service name,
> another is an access token which is revocable. You may require further
> authentication from that point.
>
> With fast bootstrapping / checkpointing of the UTXO I think usability
> could be as good as SPV, and you would get push-notification of relevant
> transactions with zero privacy trade-off.
>
> I wonder if people would want to run such an app, if they would run it on
> their desktop, a dedicated machine, or an old smartphone or other cheap ARM
> device.
>

[-- Attachment #2: Type: text/html, Size: 2287 bytes --]

[Bitcoin-development] (space) efficient reusable addr via weil pairing IBE (Re: Bait for reusable addresses)

[Adam Back]

I think I figured out a proof of existance for a space efficient way to do
better than bloom filters/prefix/bloom-bait.  (Must have been dreaming on it
as I woke up with the idea following Peter's suggestion to try prove instead
if its possible or not:).

I wrote up the details here:

https://bitcointalk.org/index.php?topic=431756.new

In summary with a use of novel application of IBE (*) based on weil-pairing
so the recipient can send a delegation private key that is specific to the
block being queried.  It means the node that services the query has no
ability to correlate with queries in other blocks from the some user.  The
sender derives a pub=IBE-extract(master-pub, id=previous block hash).  The
above link has more explanation, links and costs/risks.

I think it maybe within possibility to do further than this because it is
not technically necessary to delegate decryption, only to delegate
filtering, which can be a simpler requirement so there remains perhaps
(speculatively) a possibility to do it without introducing weil pairing
hardness problem or using eg I mentioned public key steganography or
something like that if there is anything similarly efficient but with more
widely used hardness assumptions.

Adam

(*) analogous to the way IBE is used as a building block for Non-Interactive
Forward Secrecy (NIFS)

On Fri, Jan 24, 2014 at 11:13:30AM -0500, Peter Todd wrote:
>On Fri, Jan 24, 2014 at 04:42:35PM +0100, Adam Back wrote:
>> Now while it would be clearly a very nice win if reusable addresses could
>> be made SPV-like in network characteristics and privacy, but we dont have
>> a plausible mechanism yet IMO.  [...]
>>
>> If we can find some efficient crypto to solve that last one, we could even
>> adopt them generally if it was efficient enough without needing interactive
>> one-use address release.
>
>Conversely, it'd be interesting if someone can dig up a proof showing
>that doing much better than Gregory's ambiguity tradeoff is impossible.

Re: [Bitcoin-development] (space) efficient reusable addr via weil pairing IBE (Re: Bait for reusable addresses)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 9939 bytes --]

On Sat, Jan 25, 2014 at 05:19:01PM +0100, Adam Back wrote:
> I think I figured out a proof of existance for a space efficient way to do
> better than bloom filters/prefix/bloom-bait.  (Must have been dreaming on it
> as I woke up with the idea following Peter's suggestion to try prove instead
> if its possible or not:).
> 
> I wrote up the details here:
> 
> https://bitcointalk.org/index.php?topic=431756.new

One of the main reasons I post to the bitcoin-development mailing list
rather than the forum is because the mailing list is archived by many
different, independent, parties. The forum is not - as an example
archive.org didn't have that URL until I manually told it to archive it.

So I'm taking the liberty of reposting your two posts there below:

[quote author=adam3us link=topic=431756.msg4729682#msg4729682
date=1390660452]
So have been talking with Greg Maxwell, Peter Todd, Jeremy Spillman,
Mike Hearn, Bytecoin and others about reusable addresses.

There is a summary of the situation here
http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03792.html
and I had posed th question of whether it was possible to do better at
all with Peter Todd:

[quote author=adam3us on bitcoin-dev]
Now while it would be clearly a very nice win if reusable addresses
could be  made SPV-like in network characteristics and privacy, but we
dont have a plausible mechanism yet IMO.  Close as we got was Greg's
enhancement of my/your "bloom bait"/"prefix" concept to make multiple
candidate baits to provide some ambiguity (still allows elimination,
just slightly less of it).

If we can find some efficient crypto to solve that last one, we could
even adopt them generally if it was efficient enough without needing
interactive one-use address release
[/quote]

and Peter proposed also the related problem of proving something about
that existence or not of a solution to that problem.

I think I have a proof-of-concept solution that proves by example we can
do better in space efficiency, linkability defense and non-interactivity
than my bloom bait, Peter Todds related prefix; and Greg Maxwell's
extended bloom bait described
http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03705.html.

So the idea is to use an IBE scheme as a building block in analogous way
to my 1996 problem statement for NIFS and 1998 observation that a novel
use for an IBE scheme can provide a generic solution to NIFS, and the
arrival in 2001 of the first efficient / sensible trapdoor steepness (*)
IBE with the introduction of the Weil Pairing problem by Dan Boneh and
Matt Franklin described here
http://en.wikipedia.org/wiki/Boneh%E2%80%93Franklin_scheme.

Greg summarized IBE as follows on IRC:

[quote]
(for those who may) not be familar with IBE stuff: The idea is that the
user has a master private key, which results in a master public key.
Anyone can take a prior block hash and combine it with the master public
key to get a session pubkey which could be used to encrypt a chaincode
included in an OP_RETURN.   Using the master private key the user can
derrive the session private key, which can then be used to recognize
transactions using the same session key.

In IBE (identity based encryption) this is all used a bit differently:
the master keys are held by a CA, and the session ID is your email
address, and now anyone can make a public key for you— but you need the
CA's help to get your private key)
[/quote]

Basically as Greg said your public key is your address (an email
address, a block hash, whatever is convenient and unique) and from that
and the master public key of the IBE server, the server can compute a
private key corresponding to that.  The master public is usually
considered to be a system-wide domain parameter.   Naturally enough
because a side effect of this is that the IBE server can decrypt
everyones email people were never too excited about the prospect.

However my 1998 NIFS observation is by acting as your own IBE server
(each user creates their own master public server key) they can create a
sequence (NIFS) or set (bitcoin reusable address) of public keys with
interesting and publicly derivable properties!

It is my conclusion from 1996 that to solve this with DL directly at
least in the NIFS case appears to be not possible.


So basically the reusable address becomes an IBE public key, the
existing public derivation via DH or EC Elgamal/ECIES or whatever
variant (bytecoins, mine, Peter Todd/Amir Taaki's) arrives at a factor
that can be recovered.  So with my variant (random sender generated
multiplication factor encrypted with ECIES) you could encrypt the factor
with a pub=IBE-extract(master pub, id=previous block hash) using the
previous block hash as the "identity" and the users own self-owned IBE
"server".

For Bytecoin & Peter Todd/Amir Taaki EC DH version using input or
auxilliary addresses to save space its not even necessary to send the
factor, its already sent.  So then you send a separate message to do
with secure delegatable filtering, a more secure/more space efficient
bloom filter/prefix replacement, and this is a more flexible structure.

So the secure delegatable filter is you separately add an encrypted
bloom bait Greg suggested (eg 1byte prefix communicated with public
address.)  And you can even combine that with Greg's extended bloom bait
above to add anonymity set within the block.

Consequently you can now securely and very network/space efficiently
securely delegate searching a block by computing the private key for the
IBE pub key that any sender would use for that block, and sending it as
a query to a random (or node-capture defended random selected node).
The node can decrypt the encrypted bloom baits with it, but remains
powerless to correlate with bloom baits to other payments received by
the same user in bother blocks.

(In practice you might need an epoch not block or overlapping test
because the user does not have full assurance of their tx ending up in
the pending block).

About weil pairing, and new hardness crypto risk, this is also the
hardness assumption under some ZK-SNARKs as I think used in zerocash,
and while ZK-SNARK introduces its own complexity/crypto system risk on
top; in my view weil pairing is slightly lower assurance/review not so
widely used relative to EC DL problem.  Anyway the interesting thing to
say about that is in the event this scheme got broken in the future it
falls back to the scheme that is being proposed using prefix.  Ie its no
worse than that from linkability and likely would retain some cost even
if broken-- asymmetric crypto breaks are usually somewhat gradual.

This looks more expensive and non-indexable though I didnt look to see
if there is any ciphertext only or batch precomputation that could be
squeezed out of it.

Obviously its more CPU intensive and some eg fee mechanism to prevent
node DoS could be nice, but it seems to demonstrate a proof by existence
that it is possible to do better.


Finally I think it maybe within possibility to do further than this
because it is not technically necessary to delegate decryption, only to
delegate filtering, which can be a simpler requirement.

Adam

(*) There was an earlier scheme by Maurer et al if I recall, but to get
a 1024-bit security margin you had to perform a discrete log attack on a
512-bit prime, so the key generation cost was immense, hence "sensible
trapdoor steepness" thats very shallow in tems of work difference
between setup cost and crypto system strength.
[/quote]

------

[quote author=adam3us link=topic=431756.msg4732503#msg4732503
date=1390669542]
[quote author=Mike Hearn link=topic=431756.msg4730986#msg4730986
date=1390664867]
You would need epochs for another reason. Recall that with Bloom
filtering the remote node is asked for blocks in batches of 500 at a
time and the remote end handles updating the filter as transactions are
matched. This is to avoid the performance hit of a network round-trip
for every block.
[/quote]

I see I dont think I realized that aspect of how bloom query works.  So
you then with IBE-based filtering could send multiple keys, one for each
block; but you are implicitly linked by being in one query, so you'd
just as well mark your key with your preferred epoch size and sender
uses epoch number in the query.

I think Greg is pointing out on IRC that by having a fairly small epoch
you can choose later to go down to that epoch size or scale up by
sending multiple epoch keys in a batch, a privacy/network round-trip
trade off.

Re my other problem with epochs ("In practice you might need an epoch
not block or overlapping test because the user does not have full
assurance of their tx ending up in the pending block") I think that
maybe fixable, if the blocknumber is chosen by the sender, and
communicated in enough bits to be mostly unambiguous in the message.
Then the node can index them by sen block num and no ambiguity.

It could be that another way to partly obscure ownership of queries
would be to relay queries and responses and mix other peoples queries
with your own in a batch, however as we are considering the SPV client
case relaying other peoples queries seems hard to gather query traffic
on demand and to use more bandwidth than it saves relative just issuing
smaller batches.

You could have relaying in the network eg using the embedded Tor but
waiting for queries to mix with adds latency, and suffers flood attacks
on mix-nets (send fake encrypted query traffic to flush out a tx, that
has no-anon set vs the person doing the flooding who can distinguish
their own queries).

Adam

[/quote]

-- 
'peter'[:-1]@petertodd.org
000000000000000075829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 685 bytes --]

Re: [Bitcoin-development] (space) efficient reusable addr via weil pairing IBE (Re: Bait for reusable addresses)

[Jeremy Spilman]

>
> Consequently you can now securely and very network/space efficiently
> securely delegate searching a block by computing the private key for the
> IBE pub key that any sender would use for that block, and sending it as
> a query to a random (or node-capture defended random selected node).
> The node can decrypt the encrypted bloom baits with it, but remains
> powerless to correlate with bloom baits to other payments received by
> the same user in bother blocks.
>

I'm not sure I've fully wrapped my head around it.

   d/Q        - Identity key
   E          - Generate an epoch-pubkey: E = Q * H1(epoch)
   r/P        - Ephemeral privkey/pubkey, or discoverable from inputs
   S = r * K  - Shared secret (ECDE)

Payer derives an encryption key H(S), and encrypts M, which is a 1 byte  
bloom bait.

For each epoch, payee generates e = d * H1(epoch) and provides the key to  
a full node for monitoring. So you are providing a per-block or per-epoch  
private key, along with the block ID or epoch ID that the key corresponds  
to.

The full node then uses this privkey to decrypt the same byte in all the  
transactions in that epoch/block which match the expected layout/template,  
e.g. given a certain length OP_RETURN, pull the specific byte and decrypt.

This decrypted byte is then in turn used as bloom bait which may or may  
not cause the transaction to be sent back to the SPV client.

Am I right in saying the full node has no idea if decryption is  
'succeeding' it just feeds the resultant bait into the bloom filter and  
the transaction may match or not? So we do get some level of repudiation  
by the SPV client -- the server doesn't know exactly which transactions  
belong to the SPV client.

The bloom bait specified in the reusable address is still making the  
bandwidth/privacy trade-off, it just doesn't become public information,  
because it's protected by another factor?

What encryption scheme is being used here?

-=-=-=-==

Another approach (inspired by IBE) which narrows the discoverability of  
transactions to the nodes that your SPV client is actually communicating  
with, for the specific blocks/epochs that you specify, would be to use  
PEKS.

PEKS(Q, W) for a public key Q and a keyword W produces a searchable  
encryption of the word W.

The payee holding 'd' (privkey for Q) can create a trapdoor which allows a  
server to search for transactions with W, where the searching party only  
knows if a match is found or not.

Payer:

   d/Q   - Longstanding / identity privkey/pubkey
   r/P   - Ephemeral privkey/pubkey, or discoverable from inputs
   W     - Searchable Keyword
   H1    - Hash function, {0, 1} ∗ → G1
   H2    - Hash function, G2 → {0, 1}p

Secret, as usual per ECDH:

   S = r * Q

For payer to create the searchable encryption of W for Q, called 'Sw':

   Sw = H2(e(H1(W), S))
   OP_RETURN P, Sw

For payee to search for a given 'W', payee calculates a trapdoor 'Tw':

   Tw = d * H1(W)

For a searcher, given a Trapdoor (Tw), check each Transaction (P, Sw):

   H2(e(Tw, P)) ==? Sw
   If the values match, the keyword matches

Without getting into the concepts of e(g,g) and binomial pairing, I think  
of it this way:

   Sw = H2(r * Q * H1(W)), but recall: rQ == dP, so...
      = H2(d * P * H1(W)), which can be written
      = H2(d * H1(W) * P)

Severs finds all transactions with 'P' on relevant parts of the  
blockchain, multiplies by the provided trapdoor 'Tw', applies 'H2', and  
checks for a matching 'Sw' in the transaction;

   Tw = d * H1(W)
   Sw = H2(Tw * P)
        H2(d * H1(W) * P)

PEKS is vulnerable to an offline keyword guessing attack, where you can  
discover the value of the keyword being searched, if the keyword is low  
entropy. The server/attacker can figure out the value of W, but they can't  
generate their own trapdoors to search for other keywords.

But in this case, the 'keyword' can simply be the block ID / epoch ID  
itself, not a secret value at all. In other words, the server can only  
search for your transactions within the blocks/epochs that you specify.

Using blockID/epochID as W, this would allow a server to find all  
transactions belonging to the payer for that blockID / epochID. The SPV  
client would simply provide the trapdoor for each block/epoch to be  
searched.

There are extensions to PEKS which provide for 'fuzzy' matching but they  
are 'fuzzy' within the scope of Q, not across different Q, so that doesn't  
help provide any repudiation. So I see this as only slightly improving  
Peter's original proposal of providing 'Q' to the searcher, but if you  
want repudiation, not as good as Adam's solution.

Perfunctory disclaimer... Hopefully this is close to correct, but please  
don't anyone actually try to implement this!

Thanks,
Jeremy

Re: [Bitcoin-development] (space) efficient reusable addr via weil pairing IBE (Re: Bait for reusable addresses)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 4296 bytes --]

> On Sat, Jan 25, 2014 at 05:19:01PM +0100, Adam Back wrote:
> [quote author=adam3us link=topic=431756.msg4729682#msg4729682
> date=1390660452]
> So have been talking with Greg Maxwell, Peter Todd, Jeremy Spillman,
> Mike Hearn, Bytecoin and others about reusable addresses.
> 
> There is a summary of the situation here
> http://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg03792.html
> and I had posed th question of whether it was possible to do better at
> all with Peter Todd:

You're explanation is a bit long-winded, so I'll start with a simplified
ECC-based version first and later explain how identity-based encryption
applies to the problem; I have a feeling not many non-crypt-experts
spent the time to figure out what you're talking about; do check if what
I've written below is correct:

So Alice wants to pay Bob, who is bandwidth constrained and frequently
offline. Meanwhile Ivan has a full node, but can't really be trusted.
Meanwhile Eve is busy trying to piece together everyones' financial
details.

Bob publicly publishes three pubkeys, Filter, Recover, and Spend, along
with a short n-bit prefix p. When Alice needs to pay Bob she creates a
ephemeral keypair and uses ECDH *two* shared secrets, n_f and n_r, from
Bob's Filter and Recover pubkeys respectively. She makes a transaction
that pays Bob by deriving pubkey Spend_{n_f} from the Spend and n_r
nonce.  She also uses the Filter nonce and the prefix to derive a
encrypted prefix p'=n_f^p and puts that prefix and the cleartext
ephemeral pubkey in the transaction as data.

When Bob wants to find that transaction he gives the prefix and Filter
secret key to Ivan, who then scans the blockchain. For every transaction
he computes n_f=ECDH(Filter_sec, Ephm_pub), extracts the encrypted
prefix p' from the transaction, and checks if p'=n_f^p If so he gives
that transaction to Bob who can then use his Recover secret key to check
if the transaction was in fact for him. (note how the prefix can
actually always be simply a given length of zeros)

Because Bob's prefix is short Ivan only learns probabalistic information
about what transactions might be Bob's. Eve doesn't know the Filter
secret key, and thus learns nothing at all from the blockchain data. On
the other hand after getting the key once Ivan can forever after get
that probability information about what transactions might be Bob's.

What we'd really like is for there to be some way for Alice to derive a
time-limited Filter pubkey from some public random beacon with value
R_i, such as the Bitcoin blockchain, such that each defined time
interval uses a different key. Bob would then only give Ivan the secret
key(s) for the time interval(s) in question.

Unfortunately ECDSA doesn't have a way to do this. The closest thing
available is BIP32-style key derivation, however it has the property
that given a derived secret key and known master pubkey the master
secret key can be derived. Thus Ivan can simply try every public Filter
key/epoch tweak he knows about until he finds Q,d' st. (d+d')G=Q+d'G
From that he can recover d, reducing the security to where we started.
(or put another way, Ivan can store every (d+d') secret key he is asked
to search with, and test it against every public key he learns about
later)

Identity-based cryptograhy however can do that. Bob publishes a (single)
master public key, and anyone can derive public keys based on that
master key and the random beacon value R_i. Bob can then derive the
corresponding secret key, but unlike with ECDSA, that secret key *can't*
be used to derive the master private key. Having said that, it can of
course be linked to that key, so every query that Bob makes gives Ivan
some knowledge about what transactions might be in Bob's wallet.

Problem is, who the hell has a production-ready Weil pairing library
kicking around? (is this read? http://crypto.stanford.edu/pbc/) Also,
Weil pairing is not yet trustworthy:

    < gmaxwell> (IMO thats how we should be using pairing in
    cryptosystems: for lower value applications, and solving things that
    can't be solved any other way)

-- 
'peter'[:-1]@petertodd.org
000000000000000075829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 685 bytes --]

Re: [Bitcoin-development] (space) efficient reusable addr via weil pairing IBE (Re: Bait for reusable addresses)

[Peter Todd]

[-- Attachment #1: Type: text/plain, Size: 3255 bytes --]

On Sun, Feb 02, 2014 at 01:16:20AM -0800, Jeremy Spilman wrote:
> >
> >Consequently you can now securely and very network/space efficiently
> >securely delegate searching a block by computing the private key for the
> >IBE pub key that any sender would use for that block, and sending it as
> >a query to a random (or node-capture defended random selected node).
> >The node can decrypt the encrypted bloom baits with it, but remains
> >powerless to correlate with bloom baits to other payments received by
> >the same user in bother blocks.
> >
> 
> I'm not sure I've fully wrapped my head around it.
> 
>   d/Q        - Identity key
>   E          - Generate an epoch-pubkey: E = Q * H1(epoch)
>   r/P        - Ephemeral privkey/pubkey, or discoverable from inputs
>   S = r * K  - Shared secret (ECDE)

There needs to be two separate payor pubkeys, which I called elsewhere
the "Filter" and "Recover" pubkeys - the latter I think corresponds to
what you meant by identity key. From those two pubkeys two separate
shared secrets are derived.

The key idea is that you can encrypt a short string of zeros with the
"Filter" pubkey using ECDH and place the resulting "filter bait" in the
transaction. This lets the payor give the secret key corresponding to
that pubkey to a semi-trusted third party. That third party can then
trial decrypt all filter bait seen in transactions in the blockchain,
and every time the decrypted string has a sufficient number of zeros
it's considered a filter pass and the transaction is given to the payor.
For n zero bits one in 2^n transactions will match at random, which sets
your false positive rate.

Basically think of it as a way to outsource the work required for
zero-prefix stealth addresses, but with (less) of a sacrifice of
anonymity compared to just giving the third-party your recovery pubkey.
Identity-based encryption only comes into it because it's nice to be
able to further limit what transactions the server knows about to
specific time intervals rather than forver into the future.

Interestingly both schemes can be used at once - a short public prefix
combined with a second private filter. What's interesting there is that
the public prefix can do a first-pass filtering, with the second private
filter relatively long but still providing plausible deniability - you
can always claim 100% of the matching transactions were false positives
because you didn't receive any funds!

> The full node then uses this privkey to decrypt the same byte in all
> the transactions in that epoch/block which match the expected
> layout/template, e.g. given a certain length OP_RETURN, pull the
> specific byte and decrypt.
> 
> This decrypted byte is then in turn used as bloom bait which may or
> may not cause the transaction to be sent back to the SPV client.

There's no bloom filters involved; as I said before "bloom bait" is a
misleading name. "Filter bait" is a better term given it's a generic
concept.

> What encryption scheme is being used here?

XOR with the ECDH-calculated nonce is fine. (run the nonce though a hash
function first)

-- 
'peter'[:-1]@petertodd.org
000000000000000075829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 685 bytes --]

Re: [Bitcoin-development] (space) efficient reusable addr via weil pairing IBE (Re: Bait for reusable addresses)

[Adam Back]

I think you Peter & Jeremy figured it out - dont disagree with the
explanation details.

And it seems better explained between the two posts than I did.  I think
Peter is right that you do not need an explicit prefix, the prefix after
decryption can be a chosen number of leading 0s and this gives a tunable
amount of false positives.  You already have privacy becaue the query is
only revealed to the semi-trusted full node, and its query scope is limited
to one or a chosen batch of blocks.  But you can if desired add additional
ambiguity as Peter described by reducing the number of bits of 0 in the
decrypted block.  There is no need for matching a specific prefix as its
already a recipient specific calculation.  (It means the actual encrypted
value where it is chosen would have to mimic false positives: random with
n-bits of trailing 0s and expected probability distribution).

It should be compatible for combining with sharding or public prefixes, as
Peter mentioned but for short public prefixes those still has some (reduced)
blockchain ledger logged possibility to reduce anonymity set when combined
with flow analysis.

Maybe you could vary a public prefix per block.  Eg the public prefix for a
given user is the LSBits of the per block IBE derived pubic key for a given
user.  I am not sure if that helps or hinders.  Maybe it hurts anonymity set
because the analyst (Eve) is given multiple chances over time to exclude an
analysed flow candidate.

It would desirable to find a non-IBE way to do this.  (And more
computationally efficient / precomputable / indexable)

Or you could use different address types depending on the circumstance:
one-use, stealth, or IBE.  Kind of difficult to automate that (to know what
the user is planning to do with it) and avoid user confusion.  Clearly users
are quite confused and the convenient and understandable thing is to have a
(safely) reusable address.

Adam

On Sun, Feb 02, 2014 at 07:26:10AM -0500, Peter Todd wrote:
>On Sun, Feb 02, 2014 at 01:16:20AM -0800, Jeremy Spilman wrote:
>> >
>> >Consequently you can now securely and very network/space efficiently
>> >securely delegate searching a block by computing the private key for the
>> >IBE pub key that any sender would use for that block, and sending it as
>> >a query to a random (or node-capture defended random selected node).
>> >The node can decrypt the encrypted bloom baits with it, but remains
>> >powerless to correlate with bloom baits to other payments received by
>> >the same user in bother blocks.
>> >
>>
>> I'm not sure I've fully wrapped my head around it.
>>
>>   d/Q        - Identity key
>>   E          - Generate an epoch-pubkey: E = Q * H1(epoch)
>>   r/P        - Ephemeral privkey/pubkey, or discoverable from inputs
>>   S = r * K  - Shared secret (ECDE)
>
>There needs to be two separate payor pubkeys, which I called elsewhere
>the "Filter" and "Recover" pubkeys - the latter I think corresponds to
>what you meant by identity key. From those two pubkeys two separate
>shared secrets are derived.
>
>The key idea is that you can encrypt a short string of zeros with the
>"Filter" pubkey using ECDH and place the resulting "filter bait" in the
>transaction. This lets the payor give the secret key corresponding to
>that pubkey to a semi-trusted third party. That third party can then
>trial decrypt all filter bait seen in transactions in the blockchain,
>and every time the decrypted string has a sufficient number of zeros
>it's considered a filter pass and the transaction is given to the payor.
>For n zero bits one in 2^n transactions will match at random, which sets
>your false positive rate.
>
>Basically think of it as a way to outsource the work required for
>zero-prefix stealth addresses, but with (less) of a sacrifice of
>anonymity compared to just giving the third-party your recovery pubkey.
>Identity-based encryption only comes into it because it's nice to be
>able to further limit what transactions the server knows about to
>specific time intervals rather than forver into the future.
>
>Interestingly both schemes can be used at once - a short public prefix
>combined with a second private filter. What's interesting there is that
>the public prefix can do a first-pass filtering, with the second private
>filter relatively long but still providing plausible deniability - you
>can always claim 100% of the matching transactions were false positives
>because you didn't receive any funds!
>
>> The full node then uses this privkey to decrypt the same byte in all
>> the transactions in that epoch/block which match the expected
>> layout/template, e.g. given a certain length OP_RETURN, pull the
>> specific byte and decrypt.
>>
>> This decrypted byte is then in turn used as bloom bait which may or
>> may not cause the transaction to be sent back to the SPV client.
>
>There's no bloom filters involved; as I said before "bloom bait" is a
>misleading name. "Filter bait" is a better term given it's a generic
>concept.
>
>> What encryption scheme is being used here?
>
>XOR with the ECDH-calculated nonce is fine. (run the nonce though a hash
>function first)
>
>-- 
>'peter'[:-1]@petertodd.org
>000000000000000075829f6169c79d7d5aaa20bfa8da6e9edb2393c4f8662ba0