public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Peter Todd <pete@petertodd.org>
To: Mike Hearn <mike@plan99.net>
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework)
Date: Thu, 18 Jul 2013 09:18:36 -0400	[thread overview]
Message-ID: <20130718131836.GA28234@petertodd.org> (raw)
In-Reply-To: <20130718121307.GA6062@savin>

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

On Thu, Jul 18, 2013 at 08:13:08AM -0400, Peter Todd wrote:
> 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)=H(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.

Actually, come to think of it a really easy way to create H' is for the
node to create some expensive to compute set of data associated with
their identity. The data set is then stored once by the node, cheap, but
the clients have to store one set for every unique node they connect
too, expensive. A set of the function scrypt(k | i) for i in 0..n is an
obvious way to do it.

This can equally be used as a proof-of-work to make creating lots of
nodes expensive given a cheap way to verify the POW; easily done with a
non-interactive zero-knowledge proofs. It'd be nice if that POW could
incorporate blockchain data, showing that the identity had access to
that data and thus could have computed the UTXO set honestly. (the POW
should be incrementally extendable as new data becomes available)
However that is back to using a bunch of bandwidth at startup if our
peer doesn't have access to blockchain data, so both mechanisms would
probably have to be done independently. Note how we also make MITM
attacks on encrypted P2P connections expensive this way too even without
any form of authentication. (works best when the proof-of-work is
dependent on your IP addresses)

-- 
'peter'[:-1]@petertodd.org
00000000000000762784b647ede3678f172d73dd0c72c2180ab451b00d756959

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

  reply	other threads:[~2013-07-18 13:18 UTC|newest]

Thread overview: 37+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2013-07-15 10:07 [Bitcoin-development] Introducing BitcoinKit.framework Wendell
2013-07-15 13:19 ` Mike Hearn
2013-07-15 14:39   ` Wendell
2013-07-15 15:48     ` Mike Hearn
     [not found]       ` <3E7894A0-06F3-453D-87F8-975A244EBACF@include7.ch>
2013-07-15 20:08         ` Mike Hearn
     [not found]           ` <2BDA0943-22BB-4405-9AF0-86FB41FD04A6@include7.ch>
2013-07-16  9:21             ` Mike Hearn
     [not found]               ` <2F20A509-13A9-4C84-86D7-A15C21BACD53@include7.ch>
2013-07-16  9:51                 ` Mike Hearn
2013-07-16 10:17                   ` Wendell
2013-07-16 10:59                     ` Mike Hearn
2013-07-16 14:16                       ` [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework) Wendell
2013-07-16 15:09                         ` Mike Hearn
2013-07-17 10:58                         ` Peter Todd
2013-07-17 12:29                           ` Mike Hearn
2013-07-17 14:32                             ` [Bitcoin-development] SPV bitcoind? Andreas Schildbach
2013-07-17 19:32                               ` Mike Hearn
2013-07-18 12:13                             ` [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework) Peter Todd
2013-07-18 13:18                               ` Peter Todd [this message]
2013-07-18 13:38                               ` Mike Hearn
2013-07-17 13:37                           ` Wendell
2013-07-17 14:31                             ` Michael Gronager
2013-07-17 14:58                               ` Wendell
2013-07-17 19:33                                 ` Mike Hearn
2013-07-17 22:26                                   ` Michael Gronager
2013-07-17 23:04                                     ` Gregory Maxwell
2013-07-18  8:19                                     ` Mike Hearn
2013-07-18 11:40                                       ` Bazyli Zygan
2013-07-18 13:03                                         ` Michael Gronager
2013-07-18 13:16                                           ` Michael Gronager
2013-07-18 16:22                             ` Peter Todd
2013-07-18 16:46                               ` Wendell
2013-07-18 23:03                                 ` Peter Todd
2013-07-21 15:55                       ` [Bitcoin-development] Introducing BitcoinKit.framework Pieter Wuille
2013-07-21 17:20                         ` Mike Hearn
2013-07-22 13:08               ` Mike Hearn
     [not found] <mailman.108889.1374064174.4583.bitcoin-development@lists.sourceforge.net>
2013-07-17 12:37 ` [Bitcoin-development] SPV bitcoind? (was: Introducing BitcoinKit.framework) Tamas Blummer
2013-07-17 12:50   ` Peter Todd
2013-07-17 13:56   ` Mike Hearn

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=20130718131836.GA28234@petertodd.org \
    --to=pete@petertodd.org \
    --cc=bitcoin-development@lists.sourceforge.net \
    --cc=mike@plan99.net \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox