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