But the protocol of this hypothetical cryptocurrency would reject this block. The nodes would only accept a block with all the transactions available at 10 minutes.
Miners would try different nonces but they would also try MORE nonces. How many more? That I would like to know. If there is a lot, then we could at least raise the complexity of mining and thus increase the security, but if there isnât, then my idea is useless.
A Proof of Work problem must be NP-difficult. What it means is that an answer can be found in an exponential time but the verification of this answer takes a polynomial time. In other words, slowly resolved but quickly verified.
In a blockchain, the data of the block and the hash of the previous block must be part of this problem, because otherwise an attacker could not only tamper with the last block of the blockchain but also all the other blocks. The fact that the blockchain is a simply linked list is what gives us its security.
And another thing, to follow the blockchain philosophy, verifying a block shouldnât rely on a centralised third-party. For example, if instead of trying useless nonces, miners lent their computing power to the NASA for 9 minutes and then solved a cryptographic puzzle that takes on average 1 minute, then we would rely on the NASA API to be sure that âthis miner has indeed done the job and can now go to the next stepâ.
The problem with a useful mining is that it must meet all these requirements, but Iâm pretty sure someone will come up with something interesting in the future (or maybe it is already the case).
But I want each miner to have their own nonce space. My way to authenticate the winner is to check who is the owner of the correct nonce, and this way we get their walled id.
What do you mean by âall the transactions availableâ? Once a transaction is published, it takes a long for every node to be aware of it. That is why Nakamoto chose a long time (10min) between blocks(well, they wanted blocks to have enough time to propagate, but the same logic applies, only thousands of time per round). With a never-ending stream of new transactions, 2 distant nodes will never see the same set of to-be-processed transactions. And how would you know that you are aware of all the transactions and you can start mine the block?
Another problem is that if you store all the transactions and donât limit them, you will have a 20-GB block every 10 min and your blockchain will grow super fast, excluding small nodes and leading to centralization. A good strategy for big miners would actually be to spam the network with transactions, since they are among the few who can keep up.
There is something why would exploring more nonces would lead to more security?
If a valid block hash needs N leading-zeros, you will need 2^N different tries on average to get one. No matter what you throw in it, be it previous hash + your wallet ID + nonce or previous hash + nonce, or random string, or hash of a random wikipedia page.
Yes, I know. There were such problems about protein folding, where we knew that a particular protein folds, and its potential chemical energy falls from X to Xâ, following an ever decreasing path which we donât know. Miners have to iterate over possible rotations of each part of the molecule. If someone finds a solution itâs trivial to check that the protein indeed reached its final form and that its potential energy is always decreasing along the path. Hard to find, easy to check. No need of NASA API for other miners to check that the solution is correct.
I know that too. The miner just submits (previous hash, its solution, its walletID).
This gives a new hash to include and gives the next molecule to work on.
(In this particular example, project devs published a pre-shared list of millions of molecules, and the hash of the previous block would point to the next molecule to study. The weak point is that the public researchers having made this beauty could have precomputed all or some of the solutions in the list. Consequently, itâs not a zero-trust system, but it illustrates that useful PoW is possible.)
@Akita
Wow indeed the idea of protein folding is brilliant. But one of the problems is that the mining complexity is constant whereas in Bitcoin it is proportional to the amount of computing power of the miners. What it means is that the time to create a new block will decrease more and more as new miners enter the network.
I was referring to the NASA API because I heard a suggestion to make an useful PoW: each time a new block is created, the miners lend their computing power to Facebook, NASA or Google for 9 minutes and then do âuselessâ PoW for 1 minute. I think it is a bad idea because it wouldnât be decentralized (it would rely on trusted third-parties like APIs).
Currently, PoW operates like that:
When a miner finds a new block, he broadcasts it to the network and directly after he opens the next block. In this block, the previous hash is the one he just found, and in the data he puts all the pending transactions (the ones which have been added to the queue during the 10 minutes) plus his reward. Then he broadcasts this block to the network in order to start the mining, so he is the source of authority for âwhich transactions must be included in the next block to mineâ.
My suggestion was: The winning miner should first broadcast the block he has just found to the nodes of the network, then wait the remaining time before 10 minutes to open the next block. During this time, new transactions are added to the queue. If he doesnât wait and sends directly the next block, all the other nodes of the network would reject this block.
What I meant by âall the transactions availableâ is all the transactions in the queue at 10 minutes when the new block is opened.
To know that you have all the transactions needed to start mining, you just have to wait until you receive the next block sent by the winning miner, as he is the source of authority for this block.
But I understand this idea of waiting until 10 minutes has lots of problems so I will just abandon it.
But what prevents this currently in Bitcoin, Ethereum etc?
Letâs say we find hashes with 30 leading zeros in 10 minutes with current PoW, but with my idea in 5 minutes (Iâm (maybe) exaggerating), because if you explore more nonces in as much time you will incidentally find the correct hash in less time. To go back to 10 minutes, we increase the complexity of mining, i.e. the number of leading zeros. For example, if we use my idea, we would have 31 leading zeros instead of 30. But now, 51% attacks would be way harder, because an attacker would have to create new blocks with 31 leading zeros faster than the rest of the miners, which is harder than with 30 zeros using the current PoW. Hence the system is safer.
This can be solved by âNow a miner must submit the solution for N molecules at once to winâ.
Yes, I donât like it either. But Ethereum uses this idea with a trick: the winner gets to execute the snippet submitted by users (for example the smart contracts). Everyone can submit them⌠The âtransaction queueâ is replaced by a ârun thatâ queue. âtransaction feeâ is replaced by gas, which is proportionnal to the amount of computation needed to complete the task. The more computation you need, the more âfeeâ you have to pay the miner. this is to prevent âcrack 2048 bit encryption for a few cents, plzâ.
No. They put 10Mb-worth of transaction (for example), which is the block size of the blockchain. They get to chose which transactions in the much bigger âtransaction queueâ they fit in the block. Itâs in their best interest to fill the block as much as possible (not more or their block will be rejected by the network) and to select the ones with the highest fees (or rather, the best ratio fee/byte). That is why, as a Bitcoin user, you have to put a higher reward if you want your transaction to be processed fast so that it is select by the miner. If there are too many transactions, you have to pay a lot to get your transaction through, but the number of transaction is limited by the block size, which is hardcoded in most PoW blockchains. Thatâs why back at the time we said âBitcoin canât scale!â and people tried to come with solutions (hardfork to increase the block size, compress signatures, Lightning Network to register most transactions off-chain, etc.).
This size limitation severely limit the performance and the throughput, but also limit the blockchain (the registry, not the network) and enable small nodes to be able to check ALL transactions (mining is hard, but check 10Mb every 10 min is easy). Nakamoto chose decentralization and security over throughput and low cost of transacting.
For Ethereum, Iâm less sure, but I think there is no block size limit. The âgasâ has a price, so users only submit if itâs worth it. The gas price is dynamic, but I canât remember how. Mining is of course way harder than validating, but the blockchain is still growing too fast for validators to keep up with common hardware. This is a tremendous problem for decentralization and security. It means that you, as a user, can no longer check the integrity of the chain since it grows faster than you validate it (!) So you have to trust someone that it is indeed valid. They try to hide it with confusing different roles for nodes (that they all refer to as ânodesâ), being less and less transparent about the health of the network, and they buy timewith sharding. I was a big fan of Ethereum, and I considered Bitcoin as a âcrutial but now outdated experimentâ, but itâs no longer the case. (Bitcoin-like PoW is still an energetic catastrophe that must end soon, though!)
You wonât decrease or increase the average time to find a good hash.
Traditional PoW is: Miners all plays with random number in the casinoâs roulette. Whoever hits first a N-win streak wins the game.
Your Pow is: each miner plays on a specific number, different for each player. Whoever hits first a N-win streak wins the game.
In both case, an attacker with more than 50% of the total hashrate wins and takes over. No matter what hashes pattern the network asks them to try.
It will be harder for the attacker, and harder for the defenders. If you donât adjust the difficulty, youâve just improved the throuput at the expense of the decentralization. If you do, youâre back to square one : the same hash power computing non-stop for ten minutes, and whoever controls 51% takes over.
I may have missed something myself, and I would love to be proved wrong with a simulation with low difficulty, iterated 1000 times, in the case of 1000 nodes computing random nonces on their own walletID, and 1000 nodes computing only their allowed nonces following your method. Donât mesure the time needed by your program to switch from one walletID to the other or from one modulo to the next of course.
Yes, you missed what I call the overlap, the amount of nonces that are tested several times during mining. Iâm sorry, I canât do a benchmark right now because all I have is a smartphone, but I will try to explain my reasoning. Letâs simplify the problem:
We have only 2 miners (in the case where we use my idea, letâs say that the first one mines all the even numbers and the other one all the odd numbers)
The nonces are 3 bits long (only 8 possible values, we have to simplify)
The complexity of mining is 2 leading zeros in the hash
=> The number of correct nonces is 2^3/2^2=2 (on average)
=> The probability to get a correct hash in 1 test is 2/8=1/4 (on average)
Method 1: Random tests
Probability to get a correct hash in the 1st try: 1/4
Probability to get a correct hash in the 2nd try: 1/4
Probability to get a correct hash in the 3rd try: 1/4
âŚ
Method 2: Optimized tests (my method)
Probability to get a correct hash in the 1st try: 1/4
Probability to get a correct hash in the 2nd try: 1/3 (we are sure that we wonât try the same nonce as in the first try, so we reduce the list of nonces that may be correct)
Probability to get a correct hash in the 3rd try: 1/2
Probability to get a correct hash in the 4th try: 1
So if we do the math, the probability to get a correct hash in 2 tries:
with method 1: (1/4)+(3/4)(1/4)=7/16=0.4375
with method 2: (1/4)+(3/4)(1/3)=1/2=0.5
So we have actually more chances to get a correct hash in 2 tries using my method than using the random method. And imagine how much more overlap there must be with as many miners as in Bitcoin.
If all the miners of the network try nonces randomly without making sure that they havenât tried them before (i.e. the stupid way) then we can actually calculate the amount of overlap because we can consider them as one unique miner who tries nonces the stupid way. For example if there are only 64 possible values of nonces (6 bits nonce) then the probability of having overlap on the second try is 1/64, the probability to have overlap on the third try is (1/64)(1/64)+(63/64)(2/64) etc. To do the calculations, we have to know the 3 parameters: the number of possible nonces (apparently itâs 2^32 for Bitcoin), the hashrate of the miners and the complexity of mining (number of leading zeros in the hash).
So yes, we can still break my system with 51% of the mining power, but in fact you can have less than 51% of the mining power to break the current PoW system! (assuming the attacker does an efficient exploration of nonces and all the other miners do a random exploration)
Besides, I assume miners currently use LFSR (linear-feedback shift registers) to generate pseudo-randomly the nonce they will try, and if they do Iâm practically sure that using my method is quicker to generate a nonce. So even if my method wasnât more efficient (which Iâm almost sure it is), at least it would be a little bit faster because we would generate nonces slightly faster.
But in the end I agree with you, the Bitcoin PoW system has to disappear. So even if my idea was useful to increase the security of the blockchain, it is just a patch to an obsolete system.
I donât have time to answer at length now, but I challenge the assumption that probability of finding a good nonce will be 1/4, then 1/3, then 1/2 and finally 1 with your method. You seem to consider that 2 nonces cannot produce the same hash, but itâs not true. Your 4th nonce can output the same hash as the first one for example. It has 1/8 chance to do so. You donât necessarily exhaust all possible outputs by testing the first 8 hashes.
Sorry if I reply now without waiting your long answer.
We have 8 nonces, each of which has a probability of 1/4 to be correct. The expected value is 8(1/4)=2, yes statistically you can have only 1 correct nonce, 0 even, sometimes you also have more than 2, but ON AVERAGE (i.e. if you repeat a large number of times) you will have exactly 2. To reduce the probability of having no correct nonce (and basically get stuck), you can increase the number of possible nonces or decrease the difficulty of mining, but I chose simple values to explain.
Letâs say we are on an average case and there are 2 correct nonces. We are miner 1 so we try only every even nonce. There are 2 miners, so they try 4 nonces each, and ON AVERAGE they each have a correct nonce in their set. Letâs suppose we try nonce 0000 and we get a bad hash (we had 1/4 of chances to get a good one). Next we try nonce 0010 (reminder: we wonât try nonce 0000 again). We get a bad hash again (we had 1/3 of chances to get a good one, because we knew that the good nonce was one of the 3 remaining ones). Next we try nonce 0100 and we get a good hash, we had 1/2 of chances to do so because there were only 2 nonces remaining and the correct one was inevitably one of them. Of course, these are conditional probabilities (i.e. provided that that the precendent try failed, what is the probability that this one succeeds?).
With my method, instead of choosing a nonce pseudo-randomly using a LFSR, we increment it each time by a certain value (that I have explained in my first post), so 2 miners of the network never try the same nonce 2 times.
No, we donât. Or more precisely we do if we consider only the case where we know there are exactly 2 winning nonces and one of them is odd, the other is even. This is a very particular case. This favorable case will be offset by cases were both nonces are odd, or even. Same for having less, or more than 2 winning nonces in the 8 you try.
Same answer.
You seem to think that the situation is: âThere are (on average) N winning tickets on M slots. Letâs find oneâ. The situation is âevery slot have N/M chance of being a winning ticketâ. This is very different, as the probabilities are independent.
You have the chance of finding a 2-leading-zero hash by trying (0000,0001,0010,0011 (incrementing)), by trying (0000,0010,0100,0110 (the first even numbers), by trying (0001,0011,0101,0111 (the first odd numbers), (0111,0100,1110,1111 (a random list)),⌠The only import thing is how many tries you do. Because the probabilities are independent.
They are not independant, and your calculations are correct in the case you know for sure there are exactly 2 winning nonces in the 8 first possible nonces, which you donât. All we know is that each nonce has a 1/4 chance of being a winner. You canât generalize from reasoning on a special case: the average.
What you are saying is: There are a black ball and a white one in a bag. If I try once, I have 1/2 chance to win. If I try twice, Iâm guaranteed to win.
The situation is: You flip a coin. If you flip once, you have 1/2 chance of winning. If you play twice, you are not guaranteed to win.
Additionally, in the case of Bitcoin-like PoW, different miners do not even try the same nonces. They all try unique combinations of (their walletID, a set of transaction, a nonce). (previous hash is common, you can argue that set of transaction is almost unique since they all wan to maximize their fees but the order may change). No miner ever input the same string of byte in their hash function as any other miner will or have in the history of Bitcoin. Exactly like your solution.
Oh, you could have said that sooner, it would have spared us all this argument. So my idea is useless. Indeed, adding the wallet id in the hash is a simpler and more elegant way to make sure that 2 miners never do the same calculation (and waste electricity). To not try the same nonce 2 times, I assume that a miner doesnât choose the nonces randomly, but with a simple counter (0, 1, 2, 3, 4,âŚ).
So we can leave it at that, but I will continue to reply on the probability subject because I am almost certain I am correct.
No, they are dependant. There is a difference between âdrawing with remplacementâ and âdrawing without replacementâ. Letâs say we generate a nonce randomly. When we generate the next nonce randomly, there is a probability that they will be equal (1/8). However, if you are absolutely sure that the next nonce you draw is different from the first one, by using a trick like just incrementing the nonce, then the probability to get the correct nonce on the next try is greater (1/7).
This is the law of large numbers. Besides, the outliers do not disprove what I say. If the 2 correct nonces are all owned by 1 miner instead of 2, then this miner will find the correct nonce quicker and tell the other miner to stop mining. If there is only 1 correct nonce, then the miner owning it will find it and warn the other miner like previously. If there is no correct nonce, then the miners are screwed no matter which method we use, but the difference is that if we use the first method, the miners would mine indefinitely because they have no memory of which nonces they tried, unlike with my method.
I think it was said earlier in this thread by MatthewSteeples in comment 11. I tried to reformulate (maybe badly, I give you that) in comment 12.
The set of all the (aParticularWalletID, any nonce) was what I goofily called a particular minerâs ânonce spaceâ. Poor word choice from my side.
So if independent miners chose the same nonce, but with different walletID, they still input a different thing, hence independent probabilities. I later wrapped this (walletIT+nonce) input into the word ânonceâ, which was, again, a lazy choice not to type âwalletâ.
I think that now that the misunderstanding is resolved, we both agree that as long as miners never input the same byte string in the hash function (be it with different prefix (the walletID) or different modulo for the nonces), they will collectively perform equally in both cases.
Here you are drawing with replacement. Using a different nonce can lead you to the same hash (and draw the same result). You are not narrowing down the possibilities by trying more nonces because having a bad nonce gives you zero information about the next ones (namely their probability of them being good or bad).
Why that? Because hash functions outputting an n-bit-long hash are not (in general) a bijection from the first 2^n nonces to the 2^n potential outputs. They are designed so that every output have the same probability of happening, not for them to happen once and only once in the first 2^n inputs. These would be perfect hash functions.
Ok, my argument was weak. It was a confusing and not useful way to look at the problem. I assumed it was clear that nodes never submit the same input in the hash function.
Letâs make a new hash function, which has an output of 1-bit (yeah, I know, it has a crap-ton of collisionsâŚ). I will flip a coin 2^n times and map each try number to 0 if itâs a tail, and 1 if itâs a head. Once itâs done (after an almost infinite time), my function is defined and any input gives a deterministic output. \o/
Is this function uniform? Yes. If you give a random input, do you have an equal chance to have a 1 or a 0? Yes. Is it guaranteed that there is an equal number of 1 and 0 in the list of the outputs corresponding to the 2^n inputs? No. Does having 75% of 0s in the first 2^(N/2) inputs increase my chance of having a majority of 1 in the second half? No.
What does the Law of large numbers tell me? That this is very unlikely to happen.
What does the Law of large numbers canât tell me? If it does happen, it gives me zero information about whatâs next.
What if there is exactly the same number of 0s and 1s in the first half?
No information about whatâs next.
What if the number of 0s and 1s differ by what you could expect from such an experiment?
No information about whatâs next.
IF we had a Perfect hash function from 2^n in 2^n (letâs say we do 2^n coin flips for each input, and if this output is already taken, we reiterate for this input :P), THEN, YES, having no output beginning by 000000 in our first tries would increase our chance to find one quickly after.
Ok I misunderstood, sorry to have wasted your time as well as Matthewâs, I was foolish to suggest an idea without understanding properly the intricacies of the blockchain.
Firstly, yes I commited a fallacy by suggesting that if it is true for 1 case (when there are 2 correct nonces, the average case), then it must always be true, but letâs acknowledge that it is less of a fallacy to infer something from the average case than from any other case, because it is quite literally the means of all the other cases.
Ok so now letâs compare separately each possible case. A miner has to test 4 different nonces, so there are 5 cases to consider. These are the probabilities of getting the correct nonce on the second try using method 1 (choose nonce randomly) and method 2 (increment nonce).
Nb correct nonces
Proba method 1
Proba method 2
0
0
0
1
0.4375
0.5
2
0.75
0.83
3
0.9375
1
4
1
1
I am not saying that there is a higher chance of getting a correct nonce after an unsuccessful try because the hash function gives a different output for every input. In fact, I am not disputing the fact that hash functions are imperfect and can give sometimes the same hash for 2 different nonces. What I am saying is that there is a higher chance of getting a correct nonce after an unsuccessful try because no matter the number of correct nonces, the probability to find it after 2 tries is always higher if we use my method instead of the random one, as I showed above (except if there is no correct nonce or all the nonces are correct).
I havenât checked, but I have no doubt the calculations are correct. We know that nodes donât try truly randomly, now, though.
Now that I write this, I think there was another misunderstanding. When I write that miners were checking nonces randomly, I meant randomly but without trying the same nonce twice. (And without interfering with other miners because of their different walletID used as prefix for the nonces). In that case, I think we can agree that will have the numbers above of the scenario 2, if there is exactly one wining nonce et the 4 they plan to test first. More generally, we will have the same probabilities for incrementing or checking randomly if by random I mean random but not trying the same (walletID,nonce) twice. Do we agree on that? Did we have a misunderstanding here too?
No no, donât be, that was an interesting talk.
On average, a human being has one testicle and one ovary. Knowing that help you predict things on large groups (I can expect this much wining nonces for this big sample), but nothing on the next human you will see (will it be a wining nonce or not?). (And the analogy is bad because you know there will be roughly half men half women. A better analogy would be group with a large number of people chosen at random. The typical group (hash function) would be slightly off the average repartition. But you donât know in which direction and how much, so the only info you have is that each human of the group was polled at random in an infinitely large group of men and women in equal proportions and have 1/2 chance of being a man, 1/2 of being a woman). Another to put it is that if you win early and stop, you have no way to know if itâs because you were lucky or because there happen to be a lot of them. Idem if you donât find one way after you shouldâve, statistically speaking: was I unlucky or this prefix is poorly represented among the outputs of this hash function. Itâs not uncommon for a prefix to over- or under-represented. Of course, with big numbers, both effect are negligable. In any case, if the hash function really is uniform, you know exactly how you can perform on big polling spree, but never how will behave the last try, even knowing all the other. Thatâs the definition of uniformity.
(And yet, if you have to chose only one case, yes, the average is often the less misrepresentative. I agree with that )
Yes! Thatâs what I meant by overlap, I was thinking that if we check randomly there will statistically be some nonces that we try several times, but you were assuming that we donât try the same nonce twice if we check randomly. We were at cross-purposes because of that.
I think everything has been settled. Thank you for all your time and patience, and thank you also to everyone else who replied to my post, I hope to see you another day on this website.
