{"action":"created","issue":{"url":"https://api.github.com/repos/ZcashFoundation/GrantProposals-2018Q2/issues/25","repository_url":"https://api.github.com/repos/ZcashFoundation/GrantProposals-2018Q2","labels_url":"https://api.github.com/repos/ZcashFoundation/GrantProposals-2018Q2/issues/25/labels{/name}","comments_url":"https://api.github.com/repos/ZcashFoundation/GrantProposals-2018Q2/issues/25/comments","events_url":"https://api.github.com/repos/ZcashFoundation/GrantProposals-2018Q2/issues/25/events","html_url":"https://github.com/ZcashFoundation/GrantProposals-2018Q2/issues/25","id":324037312,"node_id":"MDU6SXNzdWUzMjQwMzczMTI=","number":25,"title":"Design and/or help review new PoW scheme","user":{"login":"solardiz","id":18089797,"node_id":"MDQ6VXNlcjE4MDg5Nzk3","avatar_url":"https://avatars3.githubusercontent.com/u/18089797?v=4","gravatar_id":"","url":"https://api.github.com/users/solardiz","html_url":"https://github.com/solardiz","followers_url":"https://api.github.com/users/solardiz/followers","following_url":"https://api.github.com/users/solardiz/following{/other_user}","gists_url":"https://api.github.com/users/solardiz/gists{/gist_id}","starred_url":"https://api.github.com/users/solardiz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/solardiz/subscriptions","organizations_url":"https://api.github.com/users/solardiz/orgs","repos_url":"https://api.github.com/users/solardiz/repos","events_url":"https://api.github.com/users/solardiz/events{/privacy}","received_events_url":"https://api.github.com/users/solardiz/received_events","type":"User","site_admin":false},"labels":[{"id":965755581,"node_id":"MDU6TGFiZWw5NjU3NTU1ODE=","url":"https://api.github.com/repos/ZcashFoundation/GrantProposals-2018Q2/labels/full-submission","name":"full-submission","color":"333333","default":false},{"id":951823424,"node_id":"MDU6TGFiZWw5NTE4MjM0MjQ=","url":"https://api.github.com/repos/ZcashFoundation/GrantProposals-2018Q2/labels/invited-full","name":"invited-full","color":"32c186","default":false},{"id":929215529,"node_id":"MDU6TGFiZWw5MjkyMTU1Mjk=","url":"https://api.github.com/repos/ZcashFoundation/GrantProposals-2018Q2/labels/proof-of-work","name":"proof-of-work","color":"fbca04","default":false}],"state":"open","locked":false,"assignee":null,"assignees":[],"milestone":null,"comments":9,"created_at":"2018-05-17T14:02:43Z","updated_at":"2018-06-15T19:39:01Z","closed_at":null,"author_association":"NONE","body":"I am creating this pre-proposal primarily to get something in by the deadline, without being sure whether this proposals/grants mechanism is the most appropriate for this specific problem given its scope and importance (to me, it feels like it may very well be beyond these grant rounds, but I don't know whether other funding mechanisms are currently possible). In other words, having this in buys us time to consider my/our (Openwall) involvement under this grants framework, and decide for or against it later.\r\n\r\n# Background/introduction #\r\n\r\nTo provide some background/introduction, I previously worked on/for Zcash in 2016 resulting in this article published in November 2016:\r\n\r\nhttp://www.openwall.com/articles/Zcash-Equihash-Analysis\r\n\r\nwhere I predicted the ASICs as follows:\r\n\r\n> Equihash is not the most ASIC-resistant PoW scheme out there (likely by far) when compared to certain symmetric sequential memory-hard schemes at similar or even lower proof computation times. Yet this comparison isn't fair, since asymmetry is a desirable property, and the maximum acceptable proof verification time may be limiting the memory settings of a symmetric scheme. Thus, the choice of Equihash may pose a reasonable tradeoff given the multiple goals of Zcash and the timing of its release.\r\n\r\n> Overall, I expect that if/once there is sufficient perceived incentive, custom Zcash mining hardware will appear. It is currently unclear which one(s) of the possible forms it will take. My guesstimate for the current Equihash parameters and current technology is a factor of 10 to 100 improvement in energy efficiency and hardware cost over the most suitable commodity hardware. This might eventually put Zcash on par with Litecoin (but not Bitcoin) in terms of ASIC mining, although ASIC design complexity and required investment will likely be way higher than for Litecoin.\r\n\r\nPlease see the article for a lot more detail, including on different possible approaches to design of Equihash ASICs. \"[A] factor of 10 to 100 improvement in energy efficiency and hardware cost over the most suitable commodity hardware\" remains my current guesstimate as well. Thus, what happened now with the ASICs appearing given Zcash's high market capitalization is no surprise to me. In fact, I think they'll continue to improve into and along the 10x to 100x range.\r\n\r\nAlso in 2016, I helped define the terms of and was one of 3 judges for Zcash Miner Challenge:\r\n\r\nhttps://zcashminers.org\r\n\r\nI think that challenge was a success: we got much improved speeds of both CPU and GPU miners just in time for Zcash launch, all of those miners were Open Source, and as far as I'm aware there were no complaints about the process and judging. Although shortly thereafter even faster GPU miners appeared and those tended to be closed source with a dev fee, their additional improvement was relatively minor (the Challenge provided a 10x to 100x improvement over previous best implementations, whereas the post-Challenge improvement was 2x'ish) and the dev fees were small (IIRC, a popular miner had it at 2.5%). Surely things would have been way worse without the Challenge.\r\n\r\nI haven't been involved in Zcash since then (not even as a user, and not mining), but I've been occasionally looking at it curiously from a distance. And I do just a little bit more than that by writing this now.\r\n\r\nMy other (indirect) involvement in cryptocoins / PoW is that I am the designer of yescrypt (which builds upon scrypt, but is also very different from scrypt), which is primarily a password hashing scheme and KDF, and we've released version 1.0 earlier this year:\r\n\r\nhttp://www.openwall.com/yescrypt/\r\n\r\nAs it happens, 11 or so altcoins use an older revision of yescrypt, based off yescrypt 0.5 which was our first submission to Password Hashing Competition in 2014, as those coins' PoW scheme. They do this primarily for GPU resistance, although being GPU resistant does make them more susceptible to specialized ASICs (which would only have to compete with CPUs). I guess for minor altcoins have ASICs developed for them would be a good problem to have, as it'd only happen after reaching significant market capitalization.\r\n\r\nIndeed, yescrypt is also used to hash passwords, and we (Openwall) assisted with some large deployments of yescrypt 0.9.x shortly prior to the 1.0 release, and we work on more. As you're reading this, quite possibly some of your passwords on some popular Internet services are currently hashed with yescrypt.\r\n\r\nyescrypt is very flexible, with lots of tunable parameters (some of them are not exposed externally, but exist as compile-time low-level parameters of its underlying pwxform algorithm, also of my design). Although yescrypt was intended to be GPU-resistant (which is good for password hashing and key derivation on computers that don't necessarily have GPUs anyway), setting of those parameters differently can make it GPU-friendly (which is better for \"ASIC-resistant\" PoW of a cryptocoin with high market capitalization) while making extensive use of the GPUs' hardware (computation, on-die memories, on-card global memory).\r\n\r\nI am also the original author of John the Ripper (JtR) password cracker, first released in 1996 and maintained ever since - now by a community for so-called \"jumbo\" versions of JtR. This is relevant since it's also about high-performance computation and attacks (\"can you crack these hashes faster?\"), and we currently support CPUs, GPUs (via OpenCL; previously also via CUDA, but we dropped that since OpenCL with occasional inline PTX asm mostly works just as well on NVIDIA), and FPGAs (currently reusing ZTEX 1.15y quad-FPGA boards, almost all of which started their life as Bitcoin miners back when this was profitable, but we'll need to re-target this to newer/larger boards and/or AWS F1 instances).\r\n\r\nOf course, I worked on lots of other projects as well, but the above seem most relevant. Sorry for the bragging. I actually find it unfortunate that at this point I have more of a relevant background than of an actual ready-to-implement proposal.\r\n\r\nI also briefly interacted with Zooko prior to Zcash, including online in Password Hashing Competition (where Zooko and I were among the many panel members) and in person at an event unrelated to cryptocurrencies. But I am not affiliated with Zcash.\r\n\r\n# What can realistically be achieved # \r\n\r\nAs some of you noticed, I helped pre-review the nearby and much more complete pre-proposal of ProgPoW (#15), and I did this on my own time. I actually like a lot about that pre-proposal. I also dislike quite some things about it. And there are some I am not yet familiar with and would need to learn if I proceed to help review ProgPoW for real (which would require funding) or work on a new PoW for Zcash on my own or teaming up with others (which would also require funding). I need to more fully understand the current alternatives/competition to make an own even more competitive proposal, or to make an informed decision not to play. There are also specific criteria I have in mind that I'd subject a GPU-friendly PoW to if I were asked (and paid) to review one for real. (Yes, my GitHub comments, although they took me a few hours total as I needed to look up the source code, etc., are not a real review yet, by far.)\r\n\r\nThat pre-proposal claims \"little opportunity for specialized ASICs to gain efficiency\", and specifically \"up to 1.2x gains in efficiency\". I find this unrealistic, although that depends on what exactly we compare and in what terms, and how high the perceived incentive and budget of ASIC producers would be. For cryptocoin mining, we should ultimately be talking monetary returns vs. costs. In those terms, we'd need to factor in the supply chain inefficiencies/middlemen/markups associated with gaming GPU production and sales, vs. those of potential specialized ASICs for our PoW. I think this difference alone is at least 2x.\r\n\r\nRealistically, I think we may target the 2x to 10x range of eventual specialized ASIC advantage (in energy consumption and hardware cost) over then-current most suitable gaming GPUs. It is possible that potential Zcash ASIC miner market is not yet large enough (especially under threat of [another] PoW change) to reach even the 2x mark given that we do our best job at a GPU-specific PoW, but we should not count on it long-term.\r\n\r\nIf we're within 10x, I'd consider that a project success anyway (\"within expectations\"), although I understand that many people mining Zcash with GPUs would be very unhappy (like they're unhappy about the current ASIC miner, which didn't even reach 10x yet). This means that this whole project might not be worth it, although OTOH we might never reach that 10x point or it might take long enough to get there for this PoW change to be worthwhile - this depends on many unknowns - so we could just go ahead and hope for the better while also being realistic about the worse.\r\n\r\nRelevant reading:\r\n\r\nhttps://blog.sia.tech/the-state-of-cryptocurrency-mining-538004a37f9b\r\n\r\n# What may need to be done (pre-proposal) #\r\n\r\nOff the top of my head:\r\n\r\n- Figure out Zcash's current goals and priorities\r\n\r\n  - Is a PoW change worthwhile considering that long-term it'd only limit ASICs to \"2x to 10x\" advantage (and that's assuming we're \"successful\")?\r\n  - Is it important that the PoW be asymmetric, and to what extent?\r\n  - What's the maximum acceptable proof size? (If applicable. This could be an issue/show-stopper for using MTP, which is Equihash designers' slightly later PoW scheme and approach at turning symmetric schemes like Argon2 and yescrypt into asymmetric ones.)\r\n  - What devices would validation need to be done on?\r\n  - Is it still considered important that it'd be do-able from Ethereum smart contracts (IIRC, this was a reason to choose Equihash back then)\r\n\r\n- Identify what expertise is needed for further steps and build a team for this project\r\n\r\n- Re-research the currently available options for asymmetric PoW, along with their pros and cons\r\n\r\n- Consider, among other things, yescrypt ROM or alikes such as #14 (con: also requires lots of memory for validation), building upon Dagger Hashimoto as in #15, creating an yescrypt-MTP or the like, and/or other options we might identify\r\n\r\n- Design, implement, tune/test the lower-level components such as yescrypt's pwxform settings or ProgPoW's math/merge chain specifics. This includes trying and making sure we get close to current GPUs' theoretical peak processing speeds (GB/s from/to global memory, \"GMADs\" as analogous to GFLOPS if we use 32-bit integer math instead of FP32, although per documentation for NVIDIA Volta we'd need to use both at once or we leave half the processing power unused) while nearly-fully occupying the register files and local/shared memories and having reasonable cache hit rates (really tough, especially across a wide variety of GPUs at once).\r\n\r\n- Work on other relevant components as well: integration into a full GPU miner with its host CPU code, validation on CPU\r\n\r\nSome of these are sequential steps, some can/should proceed partially in parallel."},"comment":{"url":"https://api.github.com/repos/ZcashFoundation/GrantProposals-2018Q2/issues/comments/397722683","html_url":"https://github.com/ZcashFoundation/GrantProposals-2018Q2/issues/25#issuecomment-397722683","issue_url":"https://api.github.com/repos/ZcashFoundation/GrantProposals-2018Q2/issues/25","id":397722683,"node_id":"MDEyOklzc3VlQ29tbWVudDM5NzcyMjY4Mw==","user":{"login":"solardiz","id":18089797,"node_id":"MDQ6VXNlcjE4MDg5Nzk3","avatar_url":"https://avatars3.githubusercontent.com/u/18089797?v=4","gravatar_id":"","url":"https://api.github.com/users/solardiz","html_url":"https://github.com/solardiz","followers_url":"https://api.github.com/users/solardiz/followers","following_url":"https://api.github.com/users/solardiz/following{/other_user}","gists_url":"https://api.github.com/users/solardiz/gists{/gist_id}","starred_url":"https://api.github.com/users/solardiz/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/solardiz/subscriptions","organizations_url":"https://api.github.com/users/solardiz/orgs","repos_url":"https://api.github.com/users/solardiz/repos","events_url":"https://api.github.com/users/solardiz/events{/privacy}","received_events_url":"https://api.github.com/users/solardiz/received_events","type":"User","site_admin":false},"created_at":"2018-06-15T19:39:01Z","updated_at":"2018-06-15T19:39:01Z","author_association":"NONE","body":"I just took a look at a few other (unrelated) proposals with the full-submission label, and I realize the $250k fund is probably going to be insufficient for all that would ideally be funded. As this proposal would be eating up a significant fraction of that (especially combined with the related ProgPoW proposal), I would be totally fine with it not getting funded for that reason.\r\n\r\nA reason why I make this proposal at all is that Zcash community appears to be desperate about the ASICs now, so I am reluctantly willing to temporarily switch away from my work on other projects (which are of greater long-term relevance to me and to Openwall) to GPU-friendly PoWs. But if this actually hurts the community through taking funds away from other desirable projects, then maybe I should not?\r\n\r\nIdeally, I think Zcash Foundation should look into allocating budget on top of the $250k for the PoW change related proposals. The need for PoW change and its urgency is a Zcash core issue, and IMHO it shouldn't disrupt the normal grants process for other projects building around Zcash.\r\n\r\nJust thinking out loud."}}
{"actor":{"display_login":"solardiz"}}