Timeline for Minimizing exchanges for ZK proof of a message with given SHA-256
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 8, 2020 at 20:12 | history | edited | Geoffroy Couteau | CC BY-SA 4.0 |
deleted 1 character in body
|
| Jan 18, 2020 at 12:04 | history | bounty ended | fgrieu♦ | ||
| Jan 18, 2020 at 12:04 | vote | accept | fgrieu♦ | ||
| Jan 15, 2020 at 17:23 | comment | added | Geoffroy Couteau | I added an answer to this at the end of my answer. Unfortunately, all existing optimized ZK proof system do not allow for an obvious&easy estimation of their cost for an arbitrary function. For all of them, you need careful and tedious function-tailored optimizations, and not optimizing makes you pay a few orders of magnitude in efficiency. Better finding the numbers directly in the literature (e.g. Ligero has the SHA256 numbers) or extracting them from existing optimized implementations (e.g. libsnark). Last time I had to estimate Ligero costs on some problem, I had to contact the authors :) | |
| Jan 15, 2020 at 17:20 | history | edited | Geoffroy Couteau | CC BY-SA 4.0 |
added 4069 characters in body
|
| Jan 15, 2020 at 15:56 | comment | added | fgrieu♦ | Many thanks for this detailed answer. It will take time for me to grasp. One thing I do not get is which techniques would "just" encode SHA-256 as a boolean-SAT problem, or if (and how and to what degree) it is critical to make use of regularities. Like a lot of XOR, or a lot de 32-bit additions can come for free according to section 5.1 there. This matters because I could come with an approximation of the size fo SHA-256 as 3-SAT, but I do not understand if that's relevant. | |
| Jan 15, 2020 at 14:14 | history | edited | Geoffroy Couteau | CC BY-SA 4.0 |
added 2598 characters in body
|
| Jan 14, 2020 at 18:10 | history | edited | Geoffroy Couteau | CC BY-SA 4.0 |
added 355 characters in body
|
| Jan 13, 2020 at 20:32 | history | edited | Geoffroy Couteau | CC BY-SA 4.0 |
added 11 characters in body; deleted 1 character in body
|
| Jan 13, 2020 at 10:08 | history | answered | Geoffroy Couteau | CC BY-SA 4.0 |