6 ms·

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

jay_gridbach 1y 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
- comboy 1y ago
  zk-SNARKS maybe?
  - Sesse__ 1y 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 1y 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 1y 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 1y ago
      I am curious about alternatives or solutions in such a setting / context.
    - looofooo0 1y 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
- 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.

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

comboy 1y ago
zk-SNARKS maybe?
- Sesse__ 1y 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 1y 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 1y 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 1y ago
    I am curious about alternatives or solutions in such a setting / context.
  - looofooo0 1y 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
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.