4 ms·
I don't think we need either a strong hash or to submit hashed URLs to a server. We can use an ordinary hash and the only URLs we need to submit to a server are
by tzs 9y ago
I don't think we need either a strong hash or to submit hashed URLs to a server. We can use an ordinary hash and the only URLs we need to submit to a server are story requests to HN, if we do this thing like this:
Include in the extension a hash table construction as follows:
foreach ID of an HN story submission
URL = the URL of the submitted story
URL = normalize(URL)
insert_into_hash_table(URL, ID)
insert_into_hash_table(key, val) is a function that inserts val into a hash table with key key. The hashing function does not need to be cryptographically secure.
normalize(URL) is a function that takes a URL and normalizes it. What normalize means in this context is a little fuzzy, but the basic idea is that if URL_1 and URL_2 are different URLs to the same article, normalize(URL_1) == normalize(URL_2).
NOTE: what you include with the extension is the hash table itself. Conceptually it is probably just a sparse array containing HN IDs, with maybe a little more depending on how collisions are handled.
In the extension, do this:
URL = normalize(URL_of_current_page)
ID_list = lookup_URL_in_hash(URL)
foreach ID in ID_list
story = get_HN_story(ID)
if (normalize(URL_of_story(story)) == URL
show_story_comments(story)
The hash is only used for data retrieval from a local hash table, so does not need to be cryptographically secure.
After the hash lookup we have a list of candidate stories on HN that might match the browser story. It's a list because due to collisions there might be more than one HN story with matching hash.
Note that all that is ever fetched from the server during operation of this are HN stories, so there is minimal information leakage.
- Ajedi32 9y agoDon't hash tables typically store the key itself in the table though? Wouldn't that take up _more_ space per entry than a 160-bit hash? Using a sufficiently collision-resistant hash function allows you to eliminate the need to store URLs entirely, which in theory should reduce the size of the hash table significantly.
- tzs 9y agoWhether or not you need to store keys depends on how you handle collisions. For instance, if we had a hash table whose keys were names, and whose values were telephone numbers, we'd probably have to store keys with the phone numbers so that in the case of a collision we could figure out which phone number matches the search key. If, on the other hand, we had a hash table that stored record numbers of employee records from our employee database, keyed by employee name, then we probably would not need to store keys with the hash table values. If there is a collision, we can just retrieve all of the colliding records from the database. Those records will contain the employee name, and we can use that to figure out which is the right one. For the HN comment extension we are closer to the second case. The HN story contains the URL, so in the case of a collision we can fetch all the colliding HN stories and see which one is the right one.