Topic: Momentum Proof-of-Work Bounty - 30 BTC [PAID] - page 2. (Read 14110 times)

Aye, you've got me wishing I'd just kept my mouth shut and waited to see if it was in the live code, could have mined a bounty out if not

Regardless, it's a good PoW system and will be considering using it, or a variation of it with a customized salsa20 in the future.

Yep... there are many checks I left out of the verify method  

1) I need to check that nonce < MAX
2) check that a != b

Your feedback is useful from an open source development point of view and of course I cannot ever prove that these checks were on my TODO list.  And I am glad you brought it up because we should never assume others didn't miss something.  Look at what recently happened to Namecoin!   

Anyway my plan is to offer smaller bounties for implementation bugs once I have completed my implementation.   I will send you a tip for pointing it out because after thinking about it your feedback did provide non-zero value.   

Thanks for looking at things.

Yes, do remember to update that verify function too, sometimes it's the most obvious things that catch you out further down the line

Webr3, thank you for the feedback.  It would certainly add clarity that such a thing must be checked.   Other things that we are checking that are not referenced in the white paper is that A and B are both below some MAX NONCE value.   I will update the white paper with additional clarity and enhancements regarding the ideal parameters for various goals. 

so currently you have:

1) Given a block of data D, calculate H = Hash(D).
2) Find nonce A and nonce B such that BirthdayHash(A +H) == BirthdayHash( B+H)
3) If Hash(H + A + B) < TargetDifficulty then a result has been found, otherwise keep
searching.

Step 2 never needs to be run, BirthdayHash is never executed.

All you do is increment A and run Hash(H + A + A) until a result has been found that is under the TargetDifficulty. As soon as you've found this, then B == A and of course BirthdayHash(A+H) == BirthdayHash(B+H).

To fix this, all you need to do is create a rule such that A and B must be different.

Rather than just assuming it and not hard coding it or building it in to the algo that A != B. Seems quite a critical thing to miss from a white paper.

You'll also note that you didn't check for this in your own validation function


Very surprised to see it missing given your comment to me that:


Hopefully it is of some value, and you correct the code and add it in to the paper, else of course the whole approach is pointless is A can equal B

Hmmm - I'm reconsidering this. While the 256 bit hash is cryptologically secure . . . can we say the same thing about just the first 32 bits of it? Could an attacker shape the data to generate a hash where he controlled the first 32 bits of it?

I think that Momentum also has Time-Memory-Trade-Off (TMTO).
There are some birthday attack algorithms, one particular example is Floyd's cycle finding algorithm, which can be used to find hash collisions using memory of O(1).

Fortunately, because the nonce space is limited to 2^26 bits, and the collision difficulty is 50 bits, the "memoryless" attacker is forced to try about 16 million (2^(50-26)) times harder to find one 50-bit-collision than he was given full nonce size of 50 bits.

No.  Finding the collision depends upon the block header and everything is based on sha512 for finding collisions.

Could existing sha256 ASICs be used to pre-compute nonce filed in block header?

THe 5 BTC bounty from this thread has been supplanted by: https://bitcointalksearch.org/topic/protoshares-bounty-30-btc-start-mining-bitshares-in-november-315973

I have put together this code which is not optimized in the least, but I estimate once fully optimized will require 2^26 * 12 = 768 MB of RAM minimum and will run in one or two seconds on a Core i7.    The nonce space is limited to 2^26 items and the collision difficulty is 50 bits which on average finds 2-3 pairs per run.    This would require memory bandwidth of 512 MB/sec sustained.    Assuming you built an ASIC for SHA512 it would be at most 100x faster given the highest memory bus speeds available.   

To integrate this with a new blockchain you simply add 2 nonces to the block header, call momentum_verify and then use the existing sha256 difficulty from bitcoin to adjust the difficulty.

 

Doesn't this mean that the PoW loses its "momentum" property then, though? I think it's probably for the better anyway, as relying on an unusual mechanic of the PoW algorithm to reduce some gameable property of bitShares is probably a short-sighted idea. Or am I mistaken about the momentum?

The question becomes what is the fastest possible cryptographically secure hash that can be performed by a CPU?   It doesn't have to be the most secure of cryptographic hash functions...  I am thinking that there could probably be some combination of cryptographic hash function extended by a non cryptographically secure hashing algorithm such as city.   

For example:  You could generate a large number of birthdays per nonce like so:

P = sha512( H + nonce )
CITY256( P + 1 ) + CITY256(P+2) + ...

If you generated 16KB of nonces per sha512()... you would get a massive speed up and I suspect suffer little if any from the potential of attacks on CITY.

Okay, yes, by limiting the nonce search space, and keeping the memory bus full, I don't think adding hashing power will be helpful. Thanks for the explanation.

You want hash-speed to be linear once the target memory has been consumed.   As the number of items in memory grows the performance of the algorithm approaches the linear speed of the birthday hash alone; however, it does not eliminate the need for the memory to be present.   Putting the momentum property-aside, having a linear hash function that requires multiple GB of RAM to perform at peak performance means that the cost of going parallel with the hash function is an order of magnitude higher.

But lets see if we can keep things non-linear.    Suppose your BirthdayHash has 32 bits, but your nonce search space only has 16 bits.    You will run out of nonces long before you are able to generate enough birthdays to get very high on the q(n) curve.    I would guess you could tune the parameters in the following way:

Limit the nonce search space such that the expected number of birthday matches is 1.   If this were the actual birthday problem, we would set the nonce nonce search space to ~50 and number of days to 365.  99% of the time you would find 1 match, though sometimes you might find 2 or 0. 

Once all nonces of been searched, you have to start over again.   

Using these parameters you would require 50x as much memory to find the target as to verify the target.   If you were to grow both the nonce search space and the bits of the BirthdayHash you would maintain the same principle while requiring any amount of RAM.

The performance of the hash function would now be a matter of how quickly one could fill the RAM.  This is of course linear with respect to processing power.   The goal is to require as much RAM as possible per unit of processing power.   All we are really achieving with this hash function is to increase the number and type of transistors necessary.

Some goals:
1) get the fastest possible BirthdayHash algorithm because this will generate data via a CPU at a rate that nears the memory throughput.   Any ASIC that could perform the HASH faster would be stuck waiting on the memory bus.   
Once the memory bus becomes the bottleneck in performance we have won.

Actually I've given it some more thought, and now I'm finding this very convincing.

Let's say 365 possible birthdays and a CPU can generate 10 per second, and process a maximum of 10 per second into memory.

Add a GPU that can generate 100 per second, reduce the search space by 90%, discard 90 of the birthdays that aren't in the smaller search space, and send the 10 to the CPU to process into a search space of 36 days.

So the q(n) might only be half as effective as the p(n), but hashing can be added *infinity and we're getting linear scaling.

We need to prevent easy reduction of the search space.

I agree with this configuration. It encourages the use of low power, low cost, fanless boards for always on use which are also useful for personal clouds, self hosting, and community networks. I have had a hard time finding low cost ARM boards with more than .5 gb per core. The 4 gb configuration favors desktops and laptops which use a lot more power and are prone to cooling problems over time due to dust accumulation from always on use. Failed power supplies from overheating with dust clogged vents are by far the most common hardware failure I've seen in 12 years of servicing computers as a business.

We have solved this problem by limiting the nonce search space so that the maximum amount of useful memory for gaining non-linear performance increases is around 4 GB.     Assuming you have exhausted all possible nonces you would have to clear the memory and start over.   Now it is a race to see how fast you can fill 4 GB of memory.   While an ASIC could certainly do it quickly, memory bus speeds would still be the limiting factor.   

Thanks for the reference, I will gladly give credit where it is due.

bytemaster: Your idea of using hash collisions is good, but is not new!

I proposed it on my paper MAVEPAY, April 16, 2012  (and even then I thought I wasn't  something new).

Here is the part of the paper where the Colission POW (as I called it) is proposed, available in http://bitslog.files.wordpress.com/2012/04/mavepay1.pdf

The Collision POW:
The collision POW is based on the difficulty of finding partial preimage collisions of two messages. The packet broadcast has the following properties:
•packet=< command, nonce1, nonce2, bn >
•tmp=Hash(command||bn).
•pow1=Hash(tmp||nonce1).
•pow2=Hash(tmp||nonce2).
•pow1 and pow2 must be prefixed by some predefined number of zero bits and share some number of following bits (the remaining bits can differ).
The related attack is the partial collision attack.

Birthday attacks require large amounts of memory and so preclude the use of GPUs and other massively parallel computer architectures. An attacker is therefore less capable of using these technologies to mount a command flooding attack.

Could you please add a reference in your paper to the Collision Pow of MAVEPAY ?

Best regards, Sergio.