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-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1Uzn5K-0004Q5-Ap for bitcoin-development@lists.sourceforge.net; Thu, 18 Jul 2013 12:13:26 +0000 Received-SPF: pass (sog-mx-4.v43.ch3.sourceforge.com: domain of petertodd.org designates 62.13.148.161 as permitted sender) client-ip=62.13.148.161; envelope-from=pete@petertodd.org; helo=outmail148161.authsmtp.com; Received: from outmail148161.authsmtp.com ([62.13.148.161]) by sog-mx-4.v43.ch3.sourceforge.com with esmtp (Exim 4.76) id 1Uzn5I-00060u-Bq for bitcoin-development@lists.sourceforge.net; Thu, 18 Jul 2013 12:13:26 +0000 Received: from mail-c232.authsmtp.com (mail-c232.authsmtp.com [62.13.128.232]) by punt6.authsmtp.com (8.14.2/8.14.2/Kp) with ESMTP id r6ICDDPB013011; Thu, 18 Jul 2013 13:13:13 +0100 (BST) Received: from savin (76-10-178-109.dsl.teksavvy.com [76.10.178.109]) (authenticated bits=128) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id r6ICD8XO075304 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO); Thu, 18 Jul 2013 13:13:10 +0100 (BST) Date: Thu, 18 Jul 2013 08:13:08 -0400 From: Peter Todd To: Mike Hearn Message-ID: <20130718121307.GA6062@savin> References: <2BDA0943-22BB-4405-9AF0-86FB41FD04A6@include7.ch> <2F20A509-13A9-4C84-86D7-A15C21BACD53@include7.ch> <2A1C412D-414E-4C41-8E20-F0D21F801328@grabhive.com> <8EE501AA-1601-4C28-A32E-80F17D219D3A@grabhive.com> <20130717105853.GA10083@savin> MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="Q68bSM7Ycu6FN28Q" Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-Server-Quench: 6a459e92-efa3-11e2-b10b-0025903375e2 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR bgdMdwoUEkAYAgsB AmUbWldeUV57WGI7 bAxPbAVDY01GQQRq WVdMSlVNFUsqB2Vy chZ2LRl1cgZGfDBz ZUNqWz5dDUB/fBN0 QFMBQzwFeGZhPWIC AkFYJR5UcAFPdx9G aVd6AXFDAzANdhES HhM4ODE3eDlSNilR RRkIIFQOdA4wJgB0 TREeFjIuG0FSD2Us Jgd0Yn8aAFwWPlg5 MF0uOxoyMgMZDQxY PEBRRiFDLlwMWC0x DkIy X-Authentic-SMTP: 61633532353630.1019:706 X-AuthFastPath: 0 (Was 255) X-AuthSMTP-Origin: 76.10.178.109/587 X-AuthVirus-Status: No virus detected - but ensure you scan with your own anti-virus system. X-Spam-Score: -1.5 (-) 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 SPF_PASS SPF: sender matches SPF record X-Headers-End: 1Uzn5I-00060u-Bq Cc: Bitcoin Dev Subject: Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework) 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, 18 Jul 2013 12:13:26 -0000 --Q68bSM7Ycu6FN28Q Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Wed, Jul 17, 2013 at 02:29:26PM +0200, Mike Hearn wrote: > Partial UTXO sets is a neat idea. Unfortunately my intuition is that many > SPV wallets only remain open for <1 minute at a time because the user wan= ts > to see they received money, or to send it. It'd be neat to get some > telemetry from the Android wallet for this - I will ask Andreas to let > users opt in to usage statistics. Good idea. > So for anti-DoS I think smart prioritisation heuristics are the way to go > again. Perhaps by letting clients have an "identity" that they provide to= a > node when it's load shedding. Clients that have been seen before, have a > track record of not being abusive etc get priority and new clients that > were never seen before get dropped. Coming up with a way to do that whilst > preserving privacy sounds like an interesting cryptographic challenge. SPV clients behaving normally are highly abusive: they use up maximum node resources with minimum cost to themselves. (nodes doing an initial block download are similar now, although with partial mode they can contribute back to the network sooner) We can't win if the attacker has more upstream bandwidth than we have downstream, but fortunately botnets are generally comprised of computers on asymetric residential connections. Thus our goal is to prevent the attacker from using lots of downstream bandwidth, and more importantly, =66rom consuming more memory and similar resources than we posess. Annoyingly the raw # of TCP connections is very much a limited resource due to constraints on the # of ports a process can handle, and constraints imposed by stateful firewalls, and memory used by kernel buffers. Anything that allows for more incoming connections with less memory usage is a good thing - bloom filters are limited to 32KiB and the per-peer test if a INV item needs to be relayed to a peer is fairly cheap, but we also have other buffers like pending INV messages and so on. EC2 micro instances, as an example, often need -maxconnections limited or they run out of memory - we've probably got room for improvement; removing mapRelay and just grabbing relayed txs from the mempool comes to mind. More generally a good thing to do would be to force incoming peers to use up RAM to make a connection. We can do that with a proof-of-data posession engineered such that unless you store the data in high-speed memory you will have your connection dropped. Per peer a node can pick a nonce k and define j_i=3DH(k+i), sending the peer a set J=3D(j_0...j_n) to store in RAM. With f(k, n, i) as a pseudo-random sequence generator we create nonce x and ask our peer to compute J'(x, m) =3D j_f(x, n, 0) ^ ... ^ j_f(x, n, m)) and give us the result. (^ as the XOR operator) Because we know the nonce k we can do that cheaply, calculating it on the fly, but our peers have no choice but to store J and retrieve it on demand. If they store J in RAM they can do so quickly; if they store J on disk they can't. We then prioritize peers by how fast they respond to these requests, both measuring ping times, and forcing attackers trying to connect to large numbers of peers to posess large amounts of relatively expensive RAM. This is particularly nice because we've can make it significantly more expensive for anyone to peer to every node in the Bitcoin network simultaneously to do things like watch transaction propagation in real-time. A more sophisticated approach would be possible if there existed a version of H() with a computational trap-door - that is if there existed H'(s, i)=3DH(i) where H' had significantly faster running time than H(), but required knowledge of a secret. Our peers would then be able to answer our challenges quickly only if they stored the intermediate results in a lookup table, while we could check those challenges cheaply without that table. Adam: you're our local crypto-expert, what can we use for H'? Seems that maybe some kind of asymmetric crypto system would work by requiring the peer to crack weak secret keys that we generate deterministicly. --=20 'peter'[:-1]@petertodd.org --Q68bSM7Ycu6FN28Q Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) iQEcBAEBCAAGBQJR59vTAAoJECSBQD2l8JH7jSAIAJrihuCAp8jvXXjbaF+aDusS Bt0MFkrp976PQK4s/V5jorfNBMH+u9vZ4zTjwC2OsHofFyBsHGvJ81xhswNy5XuJ Km9c3U+BLt61EXPsS9y2ISqsURKj3VI6HWSBj7JoW1Dj9RZsmIKuRczS1ZrfXdP5 oEfUA4WT2PAD43OVyRWc60WmZ1fxXkvNfcJ7CkOOnvMg6bf+qJSL7iCwi8ROtTWd AzGngMklodD4m9hRwrUqfMGC+XAeM53M5jYlTAZqXhOlP6Z/qgiZKsq9qCW4hpHi 7chDDn9Ax8RPrk+Wi9TPb+4BD6PuMN4yKQrnr0y5KZ378ksiRXUQi9yOBAKj/38= =rpYP -----END PGP SIGNATURE----- --Q68bSM7Ycu6FN28Q--