4 ms·

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 c

by tromp 2y 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.

jay_gridbach 2y ago
Thanks for giving it a try. The Gridbach server only accepts computed result sent from my component.
- Gehinnn 2y ago
  But how do you make sure the user actually runs your component without any modification?
  - jay_gridbach 2y ago
    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 https://github.com/nakatahr/gridbach-core
    - gus_massa 1y ago
      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 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 1y ago
        Thanks. Your advice is really helpful.
    - comboy 2y ago
      zk-SNARKS maybe?
      - Sesse__ 2y ago
        For demonstrating verification of a conjecture, surely you can do much simpler things than a zero-knowledge proof: Send one of the primes.
        sebzim4500 2y ago
        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 2y ago
        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.
        johnisgood 2y ago
        I am curious about alternatives or solutions in such a setting / context.
        looofooo0 2y ago
        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
- montroser 2y ago
  That sounds interesting. How does that verification work?
oefrha 2y ago
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 https://www.mersenne.org/various/math.php
- jay_gridbach 2y ago
  [flagged]
  - tgv 2y ago
    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.
    - 2y ago

by tromp 2y ago

jay_gridbach 2y ago

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

Gehinnn 2y ago
But how do you make sure the user actually runs your component without any modification?
- jay_gridbach 2y ago
  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 https://github.com/nakatahr/gridbach-core
  - gus_massa 1y ago
    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 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 1y ago
      Thanks. Your advice is really helpful.
  - comboy 2y ago
    zk-SNARKS maybe?
    - Sesse__ 2y ago
      For demonstrating verification of a conjecture, surely you can do much simpler things than a zero-knowledge proof: Send one of the primes.
      - sebzim4500 2y ago
        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 2y ago
        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.
      - johnisgood 2y ago
        I am curious about alternatives or solutions in such a setting / context.
      - looofooo0 2y ago
        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
montroser 2y ago
That sounds interesting. How does that verification work?

oefrha 2y ago

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 https://www.mersenne.org/various/math.php

jay_gridbach 2y ago
[flagged]
- tgv 2y ago
  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.
  - 2y ago