Alice wants to attack the blockchain.
She owns private keys of 400 accounts totalling to 75% of the stake.
She is planning to rewrite the history from block 5'000.
Legit chain is at block 5'300 (less than 720).
Cumulative difficulty at block 5'000 is 8'000'000.
Cumulative difficulty at block 5'300 is 9'000'000.
How many SHA256 operations in average it's necessary to do to find a branch where cumulative difficulty at block 5'300 is at least 9'000'001?
Hint: Blocks from 5'000 to 5'300 were forged by 100% of the stake.
Without a detailed further explanation of the so called Nothing at Stake 'problem', further discussion is quite useless.
Well, first of all, if Alice has 75% of stake, then the simplest attack would be in the future: just fork and keep both branches as equal in cumulative difficulty as possible, never letting one get too far ahead of the other. Thus, there will never be consensus. In fact, for this attack, one needs only 51%. Or even much less if other stakeholders work on both branches. But for argument's sake, let's consider the original challenge. The math is pretty tricky, but let me sketch the rough idea of an attack. The regular history developed by picking, at each block, the minimum delay among the stakeholders. This delay has some probability distribution and some expectation which is the average block interval. If you reduce the stakeholders to 75%, then the distribution will shift to longer delays. BUT, Alice is not limited to single-step extensions. She can compute a huge tree of all possible k-step extensions. With 400 accounts, this tree will have 400^k leaves, and require roughly that many SHA256 computations. But for large enough k, one would expect one of these leaves to have a path with an unusually small sum of k delays, less than k times the average delay for all stakeholders. The question is, how big a k do you need. And this obviously depends on both the number of accounts, and percentage of stake held by Alice. For the given numbers, I expect a small k like 4 would suffice, but this needs to be worked out in detail. In that case, to cover 300 blocks, you'd need to compute 75 trees of 400^4 leaves each, for a rough total of 75*400^4 = 1.92*10^12 SHA256s, well within the realms of feasibility. For k larger than 6 this attack would become quite infeasible, but it's not clear to what percentage of stake that corresponds, unless one goes through the math... |
|
|
|
|
Cuckoo Cycle.
The only proof-of-work mentioned here that can claim anywhere near the same resistance is Burst.
|
|
|
|
There is no a dis-incentive to forge multiple branches because there is no a proof that such activity is harmful.
Extending multiple branches indefinitely is clearly harmful to reaching consensus. |
|
|
|
There is no a dis-incentive to forge multiple branches because there is no a proof that such activity is harmful.
So the point of forging is not to reach consensus? |
|
|
|
You mean that blocks with late timestamps are delayed rather than rejected?
If the timestamp of an incoming block is 5 minutes ahead of my time, do I reconsider it in 5 minutes?
Yes. Eventually you connect to that node and if it still offers that block and that branch is the longest then you'll download it. So it would seem to benefit a forger to forge on all the chains they see, even if not the longest, or if the timestamp is more than 15s ahead. Because any branch they forge on could eventually become the longest. Example: last block is at timestamp ts=10. At time 55, blocks A is announced with ts=60, and people forge on that, which will lead to a next block at time 115. At time 60, block B is announced with ts=80. Now even though not longer and ahead of time by 20s, everyone might as well forge on that, which could lead to a next block at, say, time 110. Or block B could be announced at time 120 and be on a strictly shorter chain. Then it should still be forged on and immediately announce its successor with ts=110. This would seem to lead to a multitude of branches all extended in parallel. In bitcoin there is a clear dis-incentive to work on multiple branches. What dis-incentive is there in NXT? |
|
|
|
This is an incorrect statement: "To those that receive it late the block is invalid and they ignore it."
It should be: "To those that receive it late the block is invalid and they ignore it for several seconds."
You mean that blocks with late timestamps are delayed rather than rejected? If the timestamp of an incoming block is 5 minutes ahead of my time, do I reconsider it in 5 minutes? |
|
|
|
What if a node purposely sets the timestamp 15 seconds ahead so that there will be large disagreement
on whether the new block has a valid timestamp?
This is a critical issue for network-wide consensus.
Nxt uses so-called "Transparent Forging". In plain English it means that the forger of the next block is known, the timestamp of that block is also known in advance. It's not allowed to set another value for the timestamp, blocks with incorrectly set timestamps are considered invalid and rejected. Answering your question: If a node purposely sets the timestamp 15 seconds ahead then all other nodes will ignore such the block. With timers not being perfectly synchronized, some will see the timestamp as only 14.999 seconds late, and thus acceptable, while others will see it as 15.001 seconds late, and thus not acceptable. Isn't that what your 15sec rule decrees? |
|
|
|
In part 2, the function verifyHit :: Integer -> Block -> Timestamp -> Integer -> Bool relies on a timestamp. How do you propose to deal with the fact that different participants in the network will have different verification outcomes (due to clock variation) and the resulting large scale disagreement? It appears you just shifted the problem from next-block-consensus to time-consensus... Also see https://nxtforum.org/general/forging-questions/?PHPSESSID=q72j729c59804eajc23qt07uo3where NXT people failed to acknowledge the issue. Timestamp is to be included into block so network members have ability to have determined verification result. However, a node can cheat by shifting timestamp a little bit (see 15 seconds rule in the topic). Due to this rule difference in clocks should be within a range of few seconds. But that's not the important issue for network-wide consensus, I guess. What if a node purposely sets the timestamp 15 seconds ahead so that there will be large disagreement on whether the new block has a valid timestamp? This is a critical issue for network-wide consensus. |
|
|
|
In part 2, the function verifyHit :: Integer -> Block -> Timestamp -> Integer -> Bool relies on a timestamp. How do you propose to deal with the fact that different participants in the network will have different verification outcomes (due to clock variation) and the resulting large scale disagreement? It appears you just shifted the problem from next-block-consensus to time-consensus... Also see https://nxtforum.org/general/forging-questions/?PHPSESSID=q72j729c59804eajc23qt07uo3where NXT people failed to acknowledge the issue. |
|
|
|
This is similar to, but more complicated than Momentum, which asks for a simple hash collision.
I read that Momentum was only used in the initial phase of BitShares. Now they use a form of proof of stake. Are there any other altcoins that have used or are using Momentum? I also read some of the Momentum whitepaper, but not enough to understand how the algorithm works. It was and still is used in Protoshares (nowadays also called Bitshares PTS). Not used anywhere else. |
|
|
|
Large memory PoW with fast verification, updated version:
The miner sends h and λi as proof.
h is the block hash value.
λi is a key for an elliptic curve point.
i is the value h MOD N.
N is the number of keys used.
The verifier calculates a point pi on the elliptic curve. The proof is valid if pi = λiG and h XOR hash(λi) is less than the target difficulty. G is a predefined constant point on the elliptic curve. (Notice here that G and pi have switched since the previous version.)
The point pi is calculated by setting x to hash(i) MOD M, where M is the order of the finite field FM for the elliptic curve y2 = x3 + 6. If no solution y is found for x, then x = x + 1 until a solution is found.
Since the calculations of pi and λiG are easy the verification is fast without the need for much memory. The miner on the other hand needs the value λi which is difficult to calculate and therefore the miner has to store all keys λi, i = 0, ... N-1 in memory as pre-calculated values.
So this asks for a point that can be calculated in two ways: as the curve point with minimal x>=i, and as λ i G This is similar to, but more complicated than Momentum, which asks for a simple hash collision. |
|
|
|
This could be a mistake of mine. I'm just learning about elliptic curves and as I understood it, to add a point to itself a number of times is easy, while going backwards to find the original value is very difficult. Isn't that the method used when calculating a public key from a private key in elliptic curve cryptography?
No, in EC crypto the λ is the private key. The difficult part is finding λ given P and G. Yes, A is a predefined constant. It's needed so that the verifier can calculate Gi and then compare it with λPi.
So your previous description of what the verifier does is wrong. |
|
|
|
Yes, λP is a point on the elliptic curve. And the point must fulfill G = λP.
The last part makes no sense since G is defined as λP, so there's nothing to fulfill. There can be many Ps for which λP is a point on the elliptic curve, so many possible Gs. It's enough for the verifier to calculate G from the P it got from the miner multiplied by λ. That's a much easier calculation than calculating P from λ and G.
No; that's about as easy, since P = (λ -1 λ) P = λ -1 (λ P) =λ -1 G. The miner on the other hand must produce the correct value for P, which is a very difficult calculation.
Why do you say the correct value for P, when there can be many? When the miner uses lots of memory then the points Pi are pre-calculated and put into a list for direct lookup. Each value Pi is calculated by setting x to a predefined constant A in the elliptic curve equation y2 = x3 + i. For the particular i, there may be no solution for y with x = A, and then x = A + 1,2,3... and so on is calculated until a solution is found.
The miner doesn't have to search from any particular A, so I don't know why you bother defining A. There's also no need to store points on the curve. For each point G you find on the curve, you just compute the corresponding P as above and check the difficulty target. |
|
|
|
As proof, the miner sends h and P. Verification is first done by taking i = h MOD N and checking if G = λP when using the elliptic curve y2 = x3 + i. The second part of the verification is to check that h XOR hash(P) is less than the target difficulty.
This looks pretty symmetric to me. The miner just keeps trying random Ps until verification succeeds, just as in hashcash. Only P for i = h MOD N is valid. If another value is used then G != λP. With sufficiently large field F M there will be an enormous number of random trials needed. I don't understand your definitions. What exactly is the verifier checking when given h and P? Is he checking that λP is any point on the curve y 2 = x 3 + i, where i = h MOD N ? Then where do the points P_i come in, and how is P_i defined? |
|
|
|
As proof, the miner sends h and P. Verification is first done by taking i = h MOD N and checking if G = λP when using the elliptic curve y2 = x3 + i. The second part of the verification is to check that h XOR hash(P) is less than the target difficulty.
This looks pretty symmetric to me. The miner just keeps trying random Ps until verification succeeds, just as in hashcash. |
|
|
|
Some altcoins use scrypt-N in the sense that the memory requirement can be increased. But if the scrypt memory becomes huge, then what about validation performance?
What part of "There are already PoWs that combine a large memory requirement with instant verifiability" didn't you understand? I tried to find information about scrypt and verification. I found one paper describing the scrypt details, but it was too complicated for me to quickly understand. Do you mean scrypt values are fast to verify, regardless of amount of memory used? And can the verification be done without the need for the same amount of memory? Scrypt is just one of many hash functions that can be used in the hashcash proof of work system. These are all symmetric, in that a proof attempt and verification both consist of computing the hash function, and thus no hope of faster verification. You need an asymmetric, non-hashcash PoW to avoid this limitation. |
|
|
|
Some altcoins use scrypt-N in the sense that the memory requirement can be increased. But if the scrypt memory becomes huge, then what about validation performance?
What part of "There are already PoWs that combine a large memory requirement with instant verifiability" didn't you understand? |
|
|
|
Hmm... Ok. Darn. I think my random index jumping would work, but it does require that the verification algorithm has the same amount of memory. I need to go back to the drawing board I guess.
There are already PoWs that combine a large memory requirement with instant verifiability (and where memory access dominates computation). I'm an amateur when it comes to this, but isn't memory access also an important factor? For example, if the memory requirement is large and the memory access rate low, then thousands of computation cores could share the same memory in an ASIC. If on the other hand the memory access rate requirement is high, then a shared memory would become a bottleneck with too many cores on the same chip. What part of "where memory access dominates computation" didn't you understand? |
|
|
|
And the number of iterations must be low enough so that validation of blocks becomes fast enough.
Seems you never heard of asymmetric PoWs, where only proof attempts require a lot of memory, but verification requires negligible... But is it really a problem if validation requires an equal amount of memory? It's a big problem in SPV clients, e.g. on mobile devices, and also makes the network more susceptible to ddos-attacks with false proofs. Hmm... Ok. Darn. I think my random index jumping would work, but it does require that the verification algorithm has the same amount of memory. I need to go back to the drawing board I guess. There are already PoWs that combine a large memory requirement with instant verifiability (and where memory access dominates computation). |
|
|
|
And the number of iterations must be low enough so that validation of blocks becomes fast enough.
Seems you never heard of asymmetric PoWs, where only proof attempts require a lot of memory, but verification requires negligible... But is it really a problem if validation requires an equal amount of memory? It's a big problem in SPV clients, e.g. on mobile devices, and also makes the network more susceptible to ddos-attacks with false proofs. |
|
|
|
|
Show Posts
