Hacker News Reader

Comment by bockris | Hacker News Reader

It doesn't matter. The exact point of a one-way function is to go forward from a known answer. It should be very hard (impossible) to go backwards. As the article mentioned, he could have stopped at 1 round but did 5 just to show the concept.

View on HN

It matters (in the case of the example), because if I tell you "things", you have no way to know if I got it by starting from folio, or from another word X that gave me the steps (for example):

X -> Y -> Z -> or -> alternatives -> things

EDIT: grammatical correction.

I don't want to tell you 'folio'. I want to prove to you that I know the answer is 'folio' without telling you the word 'folio'.

If you thought the answer was 'bored' and you followed the steps (which are not a secret) and you didn't come up with the same end confirmation word as I did. (i.e. me = 'things' you = 'hamster') one of us is wrong and neither of us had to provide our starting word to the other. We don't know who is right yet, we just know we don't agree.

One round leaves some room for error because we could both accidentally choose a word that resolves to the same word in the target position. But since we are doing 5 rounds and moving the target word (1st, 2nd, 3rd etc) for each successive round the odds become much better that we won't have an accidental collision.

(edit: grammar)

I'm not quite sure your last point is true (ie "each successive round the odds become much better") although it's more of a gut feeling than anything else. The universe words in a dictionary is the same so every iteration just chooses another random word from the set. Am I missing something?

Agreed. I think it's clear that looking at the backwards tree, it increases the longer the chain gets. Specifically, the preimage of "things" is at least as large as singleton set "alternatives"; the preimage of the preimage of "things" is larger than the preimage of "alternatives", etc.

I'd argue that you might even run into some convergence since some words will be more common than others. I suppose that's why you're always taking the "Nth" word you find but at some point you just run out words in the definition.

That's actually backwards. Since each round is independent of the last, collisions on an intermediate step will propagate forward. Since each round has the same chance of creating a collision, more rounds means higher total odds.

Yes, and I think it has a jump once you hit a very frequent word (such as "or" from the example).

Reply on news.ycombinator.com