[tor-talk] Regarding #8244; Including a string not under authority control?

Tom Fitzhenry tor-dev at tom-fitzhenry.me.uk
Tue Nov 26 01:48:14 UTC 2013

On Mon Nov 25 18:10:44 UTC 2013, Nick Mathewson <nickm at alum.mit.edu> wrote:
> So unless I'm missing my guess, the cost of setting N bits of the hash
> with probability P here is equal to the cost of generating a target
> bitcoin block with probability P, times 2^N ?

If this factor (2^N) is considered too low, we could be make it harder by adding an
additional superfluous computation. For example, rather choosing the block header as
our random value, choose SHA-256(SHA-256...(SHA-256(block_header)...) as our random
value. Say, k iterations.

This increases the cost factor to be k*2^N.

Optionally, replace "repeated SHA-256" with one of PBKDF2/bcrypt/scrypt/similar.
Bonus points for the additional computation not being SHA-256 based, because an
attacker is likely to have the ability to compute SHA-256 quickly (to be able to
compete with other miners, who have machines built to compute SHA-256 quickly).

One problem with a /constant/ factor, k, is that as attackers/miners become more
powerful, the constant factor becomes less of a problem. To combat this, k could
track Bitcoin's difficulty[0]. Doing this is more complex, however, and may mean the
directory services have to implement more of the bitcoin client spec.

As an aside, note also that it takes a certain amount of time for a mined block to be
considered part of the block chain. Conventional wisdom defines this to be 6
blocks[1], which is on average one hour. So, if the authorities got together at
23:00, they should look at the block closest(?) to 22:00.

Tom Fitzhenry

0. https://en.bitcoin.it/wiki/Difficulty
1. http://bitcoin.stackexchange.com/questions/146/what-are-bitcoin-confirmations

More information about the tor-talk mailing list