I doubt that you will hit even 1kh/s with homomorphic encryption. Overhead will definitely be lowered in the future by further researches but it is very unlikely that it will ever be possible to perform encrypted computations with the same speed as unencrypted ones without significant overhead. Creating pool with very large overhead may be possible even now.
Cool, I'm glad you at least see and agree with this. I only mentioned FHE to cement the notion with "overkill" on the math, it certainly wouldn't be the best approach at an SFE delegation solution.
By some very rough number I estimate that state of the art in "general" SFE would probably put the cpu performance on the order of tens of milliseconds per signature, at best. (I haven't actually built a circuit for it, so I could be way off, this is just based on a guestimate of gate/layer counts based on my experience with similar circuit topology on contemporary processors.) Considering you get 64 rounds per signature I think 1kh/s is not so lofty of an initial goal.
My main concern is that this low performance is assumed with generalized approaches, but there might be (probably is, from my understanding) a special case transform of the puzzle into a secured "delegated work" puzzle which would be reasonably efficient to evaluate, at least within the same order as signing directly. In other words, an "application specific SFE" scheme might vastly outperform our notions of resource requirements from generalized approaches.
The real elephant in the room is that the outcome is basically inevitable assuming that the coin doesn't otherwise fail, so the premise of the coin ends up being self-defeating, particularly if we consider something like "garbled fpga" hardware. (I highly suspect that this technology is just around the corner anyway.) Assuming the coin doesn't otherwise fail then eventually either the coin gains enough traction that a pool becomes rational despite the short term losses, or else secure function evaluation technology becomes cheap enough that a pool becomes rational from minimized short term losses. Regardless of which we reach first, on a long enough curve the centralization of your coin ultimately ends up no different from that of BTC with open participation pools dominating mining. Rational investors should consider this eventuality *today* particularly considering that the time-frame of it is entirely open ended - it could happen in an hour, a year, or a decade with the likelihood just asymptotically increasing toward certainty along some unknowable curve.
Personally, I suspect that we are looking at a time-frame of less than a year to see a "useful" pool here, if the project is successful at all. The pace of SFE technology has been startling. The addition of applicable hardware cryptography primitives into most every recent COTS processor has helped significantly in advancing the art. I suspect that the eventual introduction of specifically "SFE enabling" hardware will have an even more significant impact. On the outside, I'd say within 5 years a reasonable pool will become "easy" to make. I could be wrong.
This scheme is used to hide both data being signed and resulting signature from the signer. How do you want to apply it here? You can try to hide data being signed from the miner but then miner will need to send each generated blind signature to the server for unblinding.
It could hypothetically be done in a way that wouldn't require the "redeemer" to unblind every iteration, by using something like a commitment contract. However, after another reading through CheckProofOfWork stuff I now see that the script is appropriately constrained in a way that prevents any of these sorts of "blind output relation puzzle" shenanigans, as they would all be predicated on nonstandard scripts in coin-base that would fail the size check and extraction, as implemented. As such, that whole family of potential concerns is right out, and we can forget that I ever even brought it up.
Address is always recoverable from the signature. This fact is also used to make SpreadCoin transactions smaller.
This simply isn't true in general, but might be true in the particular implementation. I'm not sure yet, but a simple brute force address generation should find one quickly and easily, or something like crypto-mini-sat should find one slowly and with some work. I'll let you know of an example that doesn't extract if I do find the time to find one, and also by which route I found it.
Avoiding GPUs/ASICs is not a goal because it is probably not possible. I don't see how can you get any gains by ignoring nonce, this will only make mining slower because by iterating on r values you will have more work to do. You can use the same method that you describe but with nonce iteration; it can save you memory bandwidth but it won't be as fast as X11 because there is simply more work to do.
I didn't make clear that the optimization to iterate k instead of nonce applies to any processing element, it eliminates the repetition of nonce increment and initial hash. Basically, this coin is somewhat unique in that it might as well not even have a nonce field in the block header at all, since the signature field can serve the same purpose. (Since you are looking for any place to reduce block history size, you may actually even want to make this change?) I haven't tried any mining of the coin, but I might mine just to try comparing performance of this change.
My point was basically that, because of this optimization, the thing that might initially make this algorithm appear to be particularly "gpu hard" is a bit misleading, and the algorithm is not really any more "gpu hard" than x11 itself. Yes, it will always be slightly slower than "just" x11 on any processing element, because of the added signature step, but it is only some added cycles and not more memory hardness. The performance *advantage* from parallelism of gpu or fpga should be roughly the same as that of x11 itself.
This is IMO overall a good project, even if the premise is known to be mathematically impossible and seemingly likely to be pragmatically difficult too. It is obvious that you put a good deal of thought into your approach. Even if someone launches a useful pool in a few months and the project itself falters, I think that you will be able to call your work a success for having created incentive toward advancements in SFE technology.
Further, I think that with some work specifically put toward hardening the process against SFE pools, you might at least have an opportunity to drag out a reasonably long "cat and mouse" game with the progress of the technology. For example, you could pretty easily modify the signing process so that it *would* require full homomorphism over a *very* large circuit to delegate, likely buying yourself some years. (I'd probably even have some interest in helping you with such an effort, if you decide it is worthwhile.)
I will be very interested to see the outcomes!
