Is that really any better? Quoting a recent Hacker News comment of mine ( https://news.ycombinator.com/threads?id=tromp) Bitcoin mining could be more decentralized if it better resembled a lottery, where huge numbers of people play for an expected loss.
In other words, the lack of people mining at a loss makes mining profitable and hence subject to forces of centralization.
There are several reasons why mining as a lottery substitute is rare, a major one being that commodity hardware is inefficient by many orders of magnitude, making even a botnet next to useless.
Perhaps, if a proof of work, whose efficiency gap (with custom hardware) is at most an order of magnitude, were adopted (or slowly phased in), enough lottery players would arise to make mining unprofitable at scale.
Botnets should then just be welcomed as a modest increase in decentralization.
However I don't expect Spondoolies-Tech to support this vision of unprofitable mining... Disclaimer: I designed Cuckoo Cycle |
|
|
|
If you're willing to target recent x86 exclusively, then you can increase resistance by employing the AES-NI instruction.
That is not one but rather a group of instructions. Perhaps you just typoed the missing 's'. One of those instructions was of particular focus of mine. I wasn't sure if it was one or multiple, but was too lazy to figure out which:-( Thanks for correcting... |
|
|
|
Hmmm - smartphone mining would be a splendid feature . . . any idea how much more efficient a GPU vs a CPU setup would be - say based on the cost of purchase of most efficient GPU vs CPU setup + 1 year of electric fees. If the GPU setup was 2X more efficient, I could live with that for the advantage of a wide variety of mining equipment (phones, game consoles etc), but if it was 10X, not so workable.
I have very limited data. A GTX980 with a TDP of around 160W was 5x faster than an i7-4790K with a TDP of around 80W. So the GPU appears to be between 2x and 3x more efficient in this case. But since Cuckoo Cycle is memory bound, neither CPU nor GPU is going to be near their TDP. So we really need to bench it with power measuring tools, which I'm lacking... |
|
|
|
No, there is no cryptocurrency using Cuckoo Cycle as proof of work.
Btw, in absolute performance, it runs much better on GPUs than on CPUs.
But I don't know which is better in terms of performance per watt.
Thanks, I've been reading a bit more about it. I've been away for a while - did I miss anything in the CPU space? What do you think is the most GPU resistant PoW around now? I've come to realize it's really really hard to resist GPUs. For portability across different CPU architectures, I haven't seen anything more resistant than Cuckoo Cycle. If you're willing to target recent x86 exclusively, then you can increase resistance by employing the AES-NI instruction. Replacing the underlying siphash in Cuckoo Cycle by an AES-NI based hash function would likely render it much more GPU resistant. But I don't like the idea of excluding vast markets of potential hashing power (like smartphones while charging overnight). Slowly ramping up coin distribution does seem fairer, but then a coin loses the 'goldrush' feeling that is so helpful in gaining momentum and early user adoption.
That's not so much user adoption as miner adoption, and does little to the long term staying power... |
|
|
|
I would also ramp down slowly rather than halving days
Agree that Bitcoin's reward halving every 4 years is way too disruptive. Putting it on the same schedule as the biweekly difficulty adjustments would seem to be vastly preferable... |
|
|
|
Hey Tromp, are there any altcoins implementing Cuckoo yet? No, there is no cryptocurrency using Cuckoo Cycle as proof of work. Btw, in absolute performance, it runs much better on GPUs than on CPUs. But I don't know which is better in terms of performance per watt. To eliminate profitable mining, how about block rewards that are inversely proportional to chain difficulty? Only those who can mine at a (someone elses) loss will mine.
I don't like that, since I want a predictable distribution curve. But I'd make two changes to Bitcoin's curve. First, rewards should ramp up slowly, only peaking after a year or two, allowing the mining software to mature and become widespread. Second, the rewards should converge to some constant greater than zero; making the currency non-deflationary. You cannot avoid losing coins due to bugs, misconfiguration, typos, loss of private keys, stupidity, etc. If we assume a yearly loss rate of 1%, then a limit reward of X per year results in an effective soft-cap of 100X, so it's still not really inflationary. |
|
|
|
You didn't prove any point. You just vaguely alluded that since QC can do many computations in superposition, that it must somehow speedup Cuckoo Cycle finding.
Is it what was written in that paper? That by increasing number of qubits 30-fold number of computations done within the same timeframe is increased 1'000'000'000-fold? I don't think the paper would be discussing a 30 fold increase in qubits. More likely they discussed an extra 30 qubits. For some very particular computation, like integer factoring, an extra 30 qubits allow you to factorize a number that has 15 more bits. ( http://arxiv.org/abs/quant-ph/0205095 showed a Circuit for Shor's algorithm using 2n+3 qubits). So in that case you have 2^15 more states in superposition. |
|
|
|
It is a big misconception to think that QC are some magical device that can speedup arbitrary computation. Evidence suggests that they have limited speedup applicability (all variations of Grover's unstructured search and Shor's group structured search). I think I urged you to read Scott Aaronson's "The Limits of Quantum Computers" http://www.scottaaronson.com/writings/limitsqc-draft.pdflast time, to correct this misconception. Yes, and I quoted text that was proving my point. You didn't prove any point. You just vaguely alluded that since QC can do many computations in superposition, that it must somehow speedup Cuckoo Cycle finding. |
|
|
|
The best-known tmto algorithm is 20 million times slower with 1 millionth' the memory.
Of course, even being just 200 times slower means you will rarely find a block
if the block interval is just 100 proof attempts long...
This is where we stopped the last time - I claimed that it's not a problem for a QC to do 20 million computations at once (25X qubits is enough to do a computation on 33 million sets of data). It is a big misconception to think that QC are some magical device that can speedup arbitrary computation. Evidence suggests that they have limited speedup applicability (all variations of Grover's unstructured search and Shor's group structured search). I think I urged you to read Scott Aaronson's "The Limits of Quantum Computers" http://www.scottaaronson.com/writings/limitsqc-draft.pdflast time, to correct this misconception. |
|
|
|
Cuckoo Cycle reduces the gap between commodity and custom hardware by being memory bound, making mining less centralized.
What is the time-memory ratio for algorithm that works with 1 million smaller RAM? The best-known tmto algorithm is 20 million times slower with 1 millionth' the memory. Of course, even being just 200 times slower means you will rarely find a block if the block interval is just 100 proof attempts long... |
|
|
|
There are no PoW competitions. But I will be happy to submit once there are.
The only thing left is to note that your statement
"PoW blockchains are inherently vulnerable to QCs"
only applies to PoWs where a huge range (at least billions) of nonces is searched
(by one miner in one block interval).
If you "solve" PoW blockchain vulnerability by making mining centralized then I can't accept this as a solution. Cuckoo Cycle reduces the gap between commodity and custom hardware by being memory bound, making mining less centralized. |
|
|
|
What's cons?
Everything in that paper by dga is addressed in more recent versions of the Cuckoo Cycle whitepaper (e.g. the version published in BITCOIN'2015 from Jan 2015).
Good, you should send it to the next tradeoff-resistant algorithm competition. There are no PoW competitions. But I will be happy to submit once there are. The only thing left is to note that your statement "PoW blockchains are inherently vulnerable to QCs" only applies to PoWs where a huge range (at least billions) of nonces is searched (by one miner in one block interval). |
|
|
|
What's cons? Everything in that paper by dga is addressed in more recent versions of the Cuckoo Cycle whitepaper (e.g. the version published in BITCOIN'2015 from Jan 2015). |
|
|
|
Cuckoo Cycle proofs are instantly verifiable, just like Bitcoin nonces.
Bitcoin nonces are not verifiable instantly, but they require only very little memory. How much memory is required to verify Cuckoo Cycle nonce? 336 bytes. Quoting from https://github.com/tromp/cuckoo: "Proofs take the form of a length 42 cycle in a bipartite graph with N nodes and N/2 edges, with N scalable from millions to billions and beyond. This makes verification trivial: compute the 42x2 edge endpoints with one initialising sha256 and 84 very cheap siphash-2-4 hashes, check that each endpoint occurs twice, and that you come back to the starting point only after traversing 42 edges. A final sha256 hash on the sorted 42 nonces can check whether the 42-cycle meets a difficulty target. This is implemented in just 157 lines of C code (files src/cuckoo.h and src/cuckoo.c). From this point of view, Cuckoo Cycle is a very simple PoW, requiring hardly any code, time, or memory to verify." The verify() function uses 2*42 ints of memory. For graph sizes up to 2^32, those can be 32-bit ints, so that's 336 bytes. |
|
|
|
Let's say the block interval only allows for a 100 proof attempts (nonces) by a single miner.
How will you protect nodes against DoS attacks sending junk bytes pretending that they contain a valid nonce? Cuckoo Cycle proofs are instantly verifiable, just like Bitcoin nonces. |
|
|
|
PoWs requiring billions of bits are pretty safe from QC quadratic speedup,
which is still struggling to work for mere dozens of qubits.
We have stopped on time-memory trade-off... Not all TMTOs are linear... You don't even need a PoW with superlinear TMTO. A simple and practical PoW like Cuckoo Cycle suffices. They key insight is that the longer a single proof attempt takes, relative to the block interval, the smaller the advantage of the QC. Let's say the block interval only allows for a 100 proof attempts (nonces) by a single miner. (e.g. 10 second block interval, and 0.1 second proof attempt). A QC can use quadratic speedup to search those 100 nonces in 1/10 the time, but this will small 10x advantage will be completely wiped out by 1) the TMTO slowdown and penalty (already a factor 10^3 for a million qubit QC running cuckoo on 2^27 nodes) 2) cycle time of QC being way longer than that of classical computers 3) constant factor overhead in running Grover algorithm. |
|
|
|
PoWs requiring billions of bits are pretty safe from QC quadratic speedup,
which is still struggling to work for mere dozens of qubits.
We have stopped on time-memory trade-off... Not all TMTOs are linear... Some PoWs need q^2 more time to use q times less memory, which you cannot overcome with a quadratic quantum speedup. |
|
|
|
In the whitepaper mthcl showed that PoW blockchains are inherently vulnerable to QCs because they do hashing at quadratic speed.
PoWs requiring billions of bits are pretty safe from QC quadratic speedup, which is still struggling to work for mere dozens of qubits. PS: this is my 19*19th post, an important milestone for any Go player:-) |
|
|
|
A recent study has revealed that any (ir)rational number can be represented in a form that gives "9" as the final sum of all its digits...
What's the representation of sqrt(2) then? sqrt((3+3)/3) is not much of a representation... |
|
|
|
|
Show Posts
