Remix.run Logo
Remix clone Hacker News
new | show | ask | jobsGithub
▲ tromp 8 months ago

Does the gridbach server trust all submitted results to be correct, or can it somehow verify them (much faster than the outsourced computation) ? I managed to contribute 2B verifications in a few minutes.

▲oefrha 8 months ago | parent | next [-]

I had a brief look at the network traffic and code. The network communication is very simple:

To request a new batch:

  POST https://jqarehgzwnyelidzmhrn.supabase.co/rest/v1/rpc/get_job
  apikey: ...
  authorization: Bearer ...

  {"_client_hash":"..."}
returns something like

  {
    "jobId": 755344,
    "message": "get_job() succeeded, got jobId: 755344 as a new one"
  }
which means the client should check 4000075534400000000-4000075534500000000.

Once done:

  POST https://jqarehgzwnyelidzmhrn.supabase.co/rest/v1/rpc/put_job
  apiKey: ...
  authorization: Bearer ...

  {"_client_hash": "...","_job_id": 755344,"_status": 1,"_elapsed_time": 19.54,"_p": 3463,"_q": "4000075534448687929"}
Here, _client_hash is generated by wasmHash(`{"method":"Hash"}`) in /js/worker.js (yes, the payload is a fixed string), and while I didn't try to disassemble the wasm, one can pause execution and repeatedly call wasmHash() to observe it's basically a TOTP that changes every 10s, so it doesn't carry any mathematical information.

Therefore, all the info that can be used for verification on the server is a single pair of _p and _q adding up to one number in the entire range. That's the extent of the verification.

One can of course patch the code to check a single number before reporting that the entire range has been checked. Pretty sure it's impossible for the server to detect that.

Correct me if I made a mistake somewhere.

Edit: On second thought, maybe the specific number reported back is deterministically chosen in a way that relies on finishing all the checks in the range, and thus can be compared with other reported results for the same range?

Even in that case, the server can't verify the work without repeating it. mersenne.org hands out a double checking job about 8 years later presumably to thwart determined attackers.[1]

[1] https://www.mersenne.org/various/math.php

▲looofooo0 8 months ago | parent | next [-]

Yeah, I mean what OP doing is statistically searching for counterexample at worst, but without verification about the completeness of the range. Only if we assign jobs randomly and multiple times, we may believe in the truth about the whole range, at least under the assumption, that there is enough people and no big enough attacker.

▲jay_gridbach 8 months ago | parent | prev [-]

[flagged]

▲MauranKilom 8 months ago | parent | next [-]

But you posted this to a site that is literally called Hacker News... To be clear, I am not supporting any attempt at undermining your project, but people are pointing out to you that your results will be called into question if your only defence against "hacking" is "I hope people don't figure out how to do that".

▲throwaway150 8 months ago | parent [-]

> jay_gridbach: @oefrha I am afraid I had to flag your comment.

OP! This isn't cool. @oefrha basically did a free security audit for you and instead of being grateful for that, you get defensive and flag them? How is this cool?

I also had the same question as tromp about how you're validating that clients aren't cheating. @oefrha's analysis shows you aren't validating. How can we be 100% sure that none of the clients cheated? What if there is a counterexample to the conjecture but one of your clients didn't report it because they cheated? Math results require rigor and without rigor the bold claim is only a "claim" right now, not a fact!

▲tgv 8 months ago | parent | prev | next [-]

That is understandable, but counterproductive. Tou can’t walk away from this by pretending it doesn’t exist. It only takes one troll to ruin the achievement.

▲jay_gridbach 8 months ago | parent [-]

Hope everyone can enjoy the application.

▲oefrha 8 months ago | parent | prev | next [-]

Note: The parent comment accused me of giving clues to hack the application, but that part was later edited out, making my response a bit strange.

---

This is basically a free security audit, even though I only spent like five minutes. If your application can be "hacked" so easily, it's very irresponsible to say you're "verifying" the conjecture. Removing the comment doesn't make your application any more secure.

Btw, I even helpfully pointed to prior art which you can learn from. A butthurt response is pretty sad.

▲jay_gridbach 8 months ago | parent [-]

At this point, I am not capable with addressing the thing you pointed out. I didn't want to make the system closed-network nor login required. Technically, I think it is impossible to prevent reporting fake result as long as it is open network system - which means my design doesn't fit to seeking rigor.

I hope this comment answers to your question.

I will continue my project to seek meaningful purpose in some extent.

▲gpvos 8 months ago | parent | prev | next [-]

The most foolproof way to verify the results would be to have the client return all the 100 million values back to the server. This may be a bit much though, so alternatively, after submission, send a random selection of numbers in the range back to the client, which will have to return the prime summands* for those. Possibly with a time limit to prevent it from doing the calculation for only those numbers. So it probably also needs to be a fairly large selection.

*I had to look up that word

▲fragmede 8 months ago | parent | prev [-]

Respectfully, you have put in an amazing amount of work. Unfortunately life is not so kind in other parts of the world, and people are just not nice on the Internet, and they will try and break your project just for the fun of it. It is very sad, but that is the reality of the Internet today.

▲throwaway150 8 months ago | parent | next [-]

> people are just not nice on the Internet

That's not what's happening here. People in this thread are simply asking in good faith how the server-side verifies the results submitted by the client. It’s a fair question. And an important one. In fact, it might be the most important question when making such a bold claim.

If this isn't addressed, there's no way to know that a client didn't cheat by withholding a valid counterexample. And if even one client cheats, the entire claim made in this 'Show HN' thread falls apart.

▲gyesxnuibh 8 months ago | parent | next [-]

I took it to mean that people (clients) would give the project fake data for fun. But there's no statement about how those people might find the project (basically not necessarily people from hackernews).

You both are agreeing with each other.

▲fragmede 8 months ago | parent | prev [-]

I have plenty of friends on red teams so the deeper philosophical conversation doesn't elude me, but simplistically that is what it boils down to. Don't misunderstand my comment as accusations as to respective posters' morality. If there were no bad people, would you need to lock your door? So this is only coming up in this context. Unfortunately, on the Internet, we do have to lock our doors, and that's just the reality, despite what society we'd like to live in.

▲ 8 months ago | parent | prev | next [-]
[deleted]
▲jay_gridbach 8 months ago | parent | prev [-]

Thank you. I will do my best to make my project sustainable.

▲jay_gridbach 8 months ago | parent | prev [-]

Thanks for giving it a try. The Gridbach server only accepts computed result sent from my component.

▲Gehinnn 8 months ago | parent | next [-]

But how do you make sure the user actually runs your component without any modification?

▲jay_gridbach 8 months ago | parent [-]

All I can tell here is that I do certain level of valication on server side. As one of the goals of this project is to popularize the fun of mathematics among the general public, I think I would need to avoid a open network configuration to strictly conduct academic verification. The algorithm itself is publicly opened, so anyone can verify the computation step is correct or not. https://github.com/nakatahr/gridbach-core

▲gus_massa 8 months ago | parent | next [-]

Never trust the client. You must do a full verification. IIUC from another comment, you only ask the client to return the interval they tested and some token to ensure the server send them that interval.

You must ask for each number in the interval the two primes and a Primality certificate for each prime. https://en.wikipedia.org/wiki/Primality_certificate

The idea is that it's very hard to find the two primes and it's very hard to prove that they are actually primes. But if the client send you both primes and send you each primality certificate, then the verification is very fast. Also, you can store that info so people can see it.

▲jay_gridbach 8 months ago | parent [-]

Thanks. Your advice is really helpful.

▲comboy 8 months ago | parent | prev [-]

zk-SNARKS maybe?

▲Sesse__ 8 months ago | parent [-]

For demonstrating verification of a conjecture, surely you can do much simpler things than a zero-knowledge proof: Send one of the primes.

▲sebzim4500 8 months ago | parent | next [-]

It would still take a nontrivial amount of computation to do all the verification afterwards. Back of the envelope calculations suggest it should less than 100x longer to find the two primes than to verify them.

▲yujzgzc 8 months ago | parent [-]

It'd be neat to do the verification in the same manner by redistributing one client's results to another, therefore obtaining a proof modulo client collusion.

▲looofooo0 8 months ago | parent | prev | next [-]

Say smaller prime is less then 10,000. Then this one or two Byte per Nummer. E.g. 100 Mio number is already 100mb or

▲johnisgood 8 months ago | parent | prev [-]

I am curious about alternatives or solutions in such a setting / context.

▲montroser 8 months ago | parent | prev [-]

That sounds interesting. How does that verification work?