From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-4.v43.ch3.sourceforge.com ([172.29.43.194] helo=mx.sourceforge.net) by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1W3bfs-0000ov-6d for bitcoin-development@lists.sourceforge.net; Thu, 16 Jan 2014 01:23:12 +0000 Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.215.49 as permitted sender) client-ip=209.85.215.49; envelope-from=gmaxwell@gmail.com; helo=mail-la0-f49.google.com; Received: from mail-la0-f49.google.com ([209.85.215.49]) by sog-mx-4.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1W3bfr-0002ZJ-CM for bitcoin-development@lists.sourceforge.net; Thu, 16 Jan 2014 01:23:12 +0000 Received: by mail-la0-f49.google.com with SMTP id y1so1986587lam.22 for ; Wed, 15 Jan 2014 17:23:04 -0800 (PST) MIME-Version: 1.0 X-Received: by 10.112.52.6 with SMTP id p6mr37521lbo.67.1389835384660; Wed, 15 Jan 2014 17:23:04 -0800 (PST) Received: by 10.112.198.65 with HTTP; Wed, 15 Jan 2014 17:23:04 -0800 (PST) Date: Wed, 15 Jan 2014 17:23:04 -0800 Message-ID: From: Gregory Maxwell To: Bitcoin Development Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: -1.6 (-) X-Spam-Report: Spam Filtering performed by mx.sourceforge.net. See http://spamassassin.org/tag/ for more details. -1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for sender-domain 0.0 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (gmaxwell[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record -0.1 DKIM_VALID_AU Message has a valid DKIM or DK signature from author's domain 0.1 DKIM_SIGNED Message has a DKIM or DK signature, not necessarily valid -0.1 DKIM_VALID Message has at least one valid DKIM or DK signature X-Headers-End: 1W3bfr-0002ZJ-CM Subject: [Bitcoin-development] Bait for reusable addresses X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 16 Jan 2014 01:23:12 -0000 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=E2=80=94 say 8 bits=E2=80=94 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=E2=80=94 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=E2=80=94 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=E2=80=94 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.