Author [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] [EN] [ZH] [ES] [PT] [IT] [DE] [FR] [NL] [TR] [SR] [AR] [RU] Topic: Momentum Proof-of-Work Information Thread  (Read 2053 times)

0 Members and 1 Guest are viewing this topic.

Offline Amazon

  • Hero Member
  • *****
  • Posts: 831
    • View Profile
    • Bitshares Forum
« Last Edit: November 03, 2013, 09:31:11 PM by bytemaster »
Forum Donation: PforumPLfVQXTi4QpQqKwoChXHkoHcxGuA

Offline bytemaster

Re: Momentum Proof-of-Work Information Thread
« Reply #1 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. 






« Last Edit: November 03, 2013, 09:14:39 PM by bytemaster »
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline jimbobway

  • Newbie
  • *
  • Posts: 7
    • View Profile
Re: Momentum Proof-of-Work Information Thread
« Reply #2 on: November 04, 2013, 09:10:29 AM »
So for the launch is the minimum RAM 768MB?  Or is the minimum 758MB + 1.5GB?

Offline bytemaster

Re: Momentum Proof-of-Work Information Thread
« Reply #3 on: November 04, 2013, 09:14:43 AM »
I have been able to run the POW on a machine with 2GB of RAM installed. 
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline gatra

  • Newbie
  • *
  • Posts: 3
    • View Profile
Re: Momentum Proof-of-Work Information Thread
« Reply #4 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

Offline bytemaster

Re: Momentum Proof-of-Work Information Thread
« Reply #5 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.
For the latest updates checkout my blog: http://bytemaster.bitshares.org
Anything said on these forums does not constitute an intent to create a legal obligation or contract between myself and anyone else.   These are merely my opinions and I reserve the right to change them at any time.

Offline FreeTrade

  • Board Moderator
  • Hero Member
  • *****
  • Posts: 700
    • View Profile
Re: Momentum Proof-of-Work Information Thread
« Reply #6 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.
“People should be more sophisticated? How are you gonna get that done?” - Jerry Seinfeld reply to Bill Maher

Offline Financisto

  • Newbie
  • *
  • Posts: 19
    • View Profile
Re: Momentum Proof-of-Work Information Thread
« Reply #7 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?

 

Google+