BitShares Forum

Other => Graveyard => BitShares PTS => Topic started by: Amazon on November 03, 2013, 08:55:16 pm

Title: Momentum Proof-of-Work Information Thread
Post by: Amazon on November 03, 2013, 08:55:16 pm
White paper:
http://static.squarespace.com/static/51fb043ee4b0608e46483caf/t/52654716e4b01acd1ac8a085/1382369046208/MomentumProofOfWork.pdf

Proof of concept implementation:
https://github.com/InvictusInnovations/BitShares/blob/master/src/momentum.cpp

Proof of work discussion:
https://bitcointalk.org/index.php?topic=313479.0

$5000 Bounty to hack this proof of work:
http://bitsharestalk.org/index.php?topic=22.0
Title: Re: Momentum Proof-of-Work Information Thread
Post by: bytemaster on November 03, 2013, 09:11:32 pm
Some recent thoughts on Momentum Proof-of-Work

FreeTrade @ bitcointalk and I have picked the following parameters for ProtoShares:

Max Nonce:                      2^26
Birthday Hash Bits:           50
Birthday Hash Algorithm:  sha512( (nonce-nonce%8) + seed)[nonce%8] >> 14
Average Number of Birthday Matches Found per Nonce Search Space:  1-2
Minimum Memory Required to Search Space:  12 * 2^26 = 768MB
Hashtable Memory Overhead Factor 2x: 1.5 GB 

Given these settings and FreeTrade's best implementation so far it takes about 10 seconds per search to find about 2 birthday matches.


In the future I think I would make the following changes to prevent botnets.

1) Minimum Memory Required to Search Space:  8 GB
2) Modify Birthday Hash Algorithm to generate 20 birthdays per SHA512 instead of just 8

Given these changes there is nothing preventing the average man from mining provided he outfit his machine with 16 GB of RAM which is fairly common, but most machines that are part of a botnet are older machines with insufficient RAM.  This should also serve to enhance the degree to which the algorithm is resistant to ASICS.   

Anyone planning on mining BitShares will want to make sure their mining machines are upgradable to 16 GB of RAM. 






Title: Re: Momentum Proof-of-Work Information Thread
Post by: jimbobway on November 04, 2013, 09:10:29 am
So for the launch is the minimum RAM 768MB?  Or is the minimum 758MB + 1.5GB?
Title: Re: Momentum Proof-of-Work Information Thread
Post by: bytemaster on November 04, 2013, 09:14:43 am
I have been able to run the POW on a machine with 2GB of RAM installed. 
Title: Re: Momentum Proof-of-Work Information Thread
Post by: gatra on November 04, 2013, 09:32:49 pm
in the following statement:

Minimum Memory Required to Search Space:  12 * 2^26 = 768MB

where does the 12 come from?
For each of the 2^26 nonces you need to store the 50 bit hash. So 50 / 8 = 6.25 bytes
6.25  * 2^26 = 419MB
If I round up, it's 7  * 2^26 = 469MB
Title: Re: Momentum Proof-of-Work Information Thread
Post by: bytemaster on November 04, 2013, 09:45:33 pm
in the following statement:

Minimum Memory Required to Search Space:  12 * 2^26 = 768MB

where does the 12 come from?
For each of the 2^26 nonces you need to store the 50 bit hash. So 50 / 8 = 6.25 bytes
6.25  * 2^26 = 419MB
If I round up, it's 7  * 2^26 = 469MB

You need to store the birthday (50 bits, rounded up to 64 bits) and the nonce, 26 bits rounded up to 32 which is 12 bytes.

If you got fancy you could use 76 bits or 10 bytes rather than 12 and save 16% at the expense of some computation.
Title: Re: Momentum Proof-of-Work Information Thread
Post by: FreeTrade on November 06, 2013, 12:17:06 pm
You need to store the birthday (50 bits, rounded up to 64 bits) and the nonce, 26 bits rounded up to 32 which is 12 bytes.

If you got fancy you could use 76 bits or 10 bytes rather than 12 and save 16% at the expense of some computation.

The current algorithm uses
64bits + 32bits -> 96 bits

Only 50 bits of the 64 bits are relevant, and only 26 bits of the 32 are relevant, so that's a total of 20 you can shave right away.

However, with current implementation 22 bits of the 50 can be immediately inferred from the location in the hash map, so there's another 22bits saving there too . . so a grand total of 28+26 is required - 54bits . . there'd be a little more calculation for all the bit-shifting, but not much. The algorithm could use as little as 432MB without much additional calculation and without loss of collisions.
Title: Re: Momentum Proof-of-Work Information Thread
Post by: Financisto on November 13, 2013, 04:10:28 am
@bytemaster

Have you ever pondered adding some ideas from Primecoin POW into Momentum POW?

Wouldn't anything be of some use in order to spare some energy and achieve more efficiency without giving away the advantages obtained already?

What do you think about their uncommon POW?