Advertisement
gigawatt

momentum.cpp MODIFIED

Nov 9th, 2013
324
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 15.12 KB | None | 0 0
  1. #include "momentum.h"
  2. #include <boost/unordered_map.hpp>
  3. #include <iostream>
  4.  
  5. namespace bts
  6. {
  7. uint64_t getBirthdayHash(const uint256 &midHash, uint32_t a);
  8.  
  9. #define MAX_MOMENTUM_NONCE ( 1<<26 )
  10. #define SEARCH_SPACE_BITS  ( 50 )
  11. #define BIRTHDAYS_PER_HASH ( 8 )
  12.  
  13. #define SEARCH_SPACE    ( MAX_MOMENTUM_NONCE )
  14. #define CHAIN_LENGTH    ( 2 )
  15. #define RAINBOW_ENTRIES ( SEARCH_SPACE / CHAIN_LENGTH )
  16. #define STOP_ON_FIRST_MATCH ( 1 )
  17.  
  18. #define DEBUG_MODE ( 0 )
  19.  
  20.  
  21. // Overview:
  22. // https://en.wikipedia.org/wiki/Rainbow_table
  23. // Make a "rainbow table" map to hold the equivalent hash space of SEARCH_SPACE
  24. //   For chains of length CHAIN_LENGTH,
  25. //     rainbow table needs (SEARCH_SPACE / CHAIN_LENGTH) elements [name: RAINBOW_ENTRIES]
  26. //   Rainbow table will require (8 bytes (hash) + 4 bytes (nonce)) * RAINBOW_ENTRIES bytes total
  27. // To compress each SEARCH_SPACE_BITS hash to a new nonce in the range MAX_MOMENTUM_NONCE,
  28. //   simply use (hash % MAX_MOMENTUM_NONCE)
  29.  
  30. // Pseudocode:
  31. // For the first RAINBOW_ENTRIES
  32. //   nonce = element number
  33. //   For i = 1 to CHAIN_LENGTH
  34. //     cur_hash = HASH(nonce)
  35. //     Check if any part of cur_hash is in rainbow table
  36. //       If yes and generated by different nonce: add to result list
  37. //     For each chunk in cur_hash
  38. //       rainbow_map[chunk] = element number
  39. //     nonce = compress(cur_hash)
  40. //
  41. // For the next (SEARCH_SPACE - RAINBOW_ENTRIES) elements:
  42. //   nonce = element number
  43. //   For i = 1 to CHAIN_LENGTH
  44. //     cur_hash = Hash(nonce)
  45. //     Check if any part of cur_hash is in rainbow table
  46. //       If yes and generated by different nonce: add to result list
  47. //     nonce = compress(cur_hash)
  48. //
  49. // return result list
  50.  
  51.  
  52. ///// MATH SECTION /////
  53. // Given:
  54. // CALLS(CHAIN_LENGTH) = total calls to SHA512 using a rainbow table with chain length CHAIN_LENGTH
  55. // CALLS(CHAIN_LENGTH) = (SEARCH_SPACE / CHAIN_LENGTH) + (SEARCH_SPACE * CHAIN_LENGTH) - (SEARCH_SPACE / CHAIN_LENGTH)
  56. //   + (SEARCH_SPACE / CHAIN_LENGTH) = Calls to generate rainbow table
  57. //   + (SEARCH_SPACE * CHAIN_LENGTH) = Calls to check SEARCH_SPACE nonce values
  58. //   - (SEARCH_SPACE * CHAIN_LENGTH) = Except we skip the nonces used to make the rainbow table
  59. // CALLS(CHAIN_LENGTH) = (SEARCH_SPACE * CHAIN_LENGTH)
  60.  
  61. // Given:
  62. // MEMORY(CHAIN_LENGTH) = number of bytes required to store a rainbow table representing
  63. //                          SEARCH_SPACE elements with chain length CHAIN_LENGTH
  64. // MEMORY(CHAIN_LENGTH) = rainbow table elements * (size of hash chunk + size of nonce)
  65. // MEMORY(CHAIN_LENGTH) = (8 + 4) * SEARCH_SPACE / CHAIN_LENGTH
  66.  
  67. // Examples:
  68. // Minimum number of SHA512 calls is CHAIN_LENGTH = 1 (equivalent to the "default" semiordered map setup)
  69. //   Requires (SEARCH_SPACE * 12) = 768 MB memory
  70. //   Requires (SEARCH_SPACE) calls to SHA512
  71. // For CHAIN_LENGTH = N
  72. //   Requires (SEARCH_SPACE * 12 / N) bytes of memory
  73. //   Requires (SEARCH_SPACE * N) calls to SHA512
  74. // For CHAIN_LENGTH = 1024
  75. //   Requires (2^26 * 12 / 1024) = 768 KB of memory
  76. //   Requires (2*26 * 1024) calls to SHA512
  77.  
  78. // Bottom line:
  79. // Using a rainbow table map of chain length N,
  80. //   memory usage is multiplied by a factor of 1/N
  81. //   and SHA512 calls are multiplied by a factor of N
  82. // This means that regardless the CHAIN_LENGTH selected,
  83. //   the ratio of CALLS(CHAIN_LENGTH) to MEMORY(CHAIN_LENGTH)
  84. //   is inversely proportional.
  85. // EFFICIENCY IS CONSTANT AT ANY MEMORY TARGET.
  86. // All that matters is brute computational strength.
  87.  
  88. // Example:
  89. // If a GPU/ASIC/FPGA has PROCESSOR number of parallel computing units,
  90. //   and MEM_MAX bytes of available memory, then each
  91. //   Momentum hash instance can use up to (MEM_MAX / PROCESSOR) bytes of memory.
  92. // To calculate the CHAIN_LEN to acheive this:
  93. //   CHAIN_LEN(MEM_MAX, PROCESSOR) = (8 + 4) * SEARCH_SPACE / (MEM_MAX / PROCESSOR)
  94. //   CHAIN_LEN(MEM_MAX, PROCESSOR) = (8 + 4) * SEARCH_SPACE * PROCESSOR / MEM_MAX
  95. //   Note: This calculation is just the inverse of MEMORY(CHAIN_LEN)
  96.  
  97. // Assuming: GPU with 128 compute units, 1 GB memory, and SEARCH_SPACE = MAX_MOMENTUM_NONCE
  98. //   CHAIN_LEN(2^30, 2^7) = (8 + 4) * SEARCH_SPACE * PROCESSOR / MEM_MAX
  99. //   CHAIN_LEN(2^30, 2^7) = (8 + 4) * SEARCH_SPACE * 2^7 / 2^30
  100. //   CHAIN_LEN(2^30, 2^7) = 12 * SEARCH_SPACE / 2^23
  101. //   CHAIN_LEN(2^30, 2^7) = 12 * 2^26 / 2^23
  102. //   CHAIN_LEN(2^30, 2^7) = 12 * 2^3
  103. //   CHAIN_LEN(2^30, 2^7) = 96
  104. //   Verification:
  105. //   MEMORY(CHAIN_LENGTH) = (8 + 4) * SEARCH_SPACE / CHAIN_LENGTH
  106. //   MEMORY(96) = (8 + 4) * 2^26 / 96
  107. //   MEMORY(96) = 8388608 bytes
  108. //   MEMORY(96) = 8 MB
  109. //   CALLS(CHAIN_LENGTH) = (SEARCH_SPACE * CHAIN_LENGTH)
  110. // Result: 1/96th the normal memory usage of 768 MB, 96x the SHA512 calls.
  111. //   The problem is no longer about memory, it's about computation speed.
  112.  
  113.  
  114. ///// UTILITY FUNCTIONS /////
  115.  
  116. // Compresses "hash" to within MAX_MOMENTUM_NONCE space
  117. #define COMPRESS_CHUNK(chunk) ( chunk % MAX_MOMENTUM_NONCE )
  118. #define COMPRESS_HASH(hash)   ( COMPRESS_CHUNK(hash[0]) )
  119.  
  120. // HASH is a wrapper for SHA512
  121. // It creates BIRTHDAYS_PER_HASH elements, each one
  122. //   right shifted by (64 - SEARCH_SPACE_BITS)
  123. #define HASH(input, temp, output)                                         \
  124. {                                                                         \
  125.     *hash_input = input;                                                  \
  126.     SHA512((unsigned char *)temp, sizeof(temp), (unsigned char *)output); \
  127.     output[0] >>= (64 - SEARCH_SPACE_BITS);                               \
  128.     output[1] >>= (64 - SEARCH_SPACE_BITS);                               \
  129.     output[2] >>= (64 - SEARCH_SPACE_BITS);                               \
  130.     output[3] >>= (64 - SEARCH_SPACE_BITS);                               \
  131.     output[4] >>= (64 - SEARCH_SPACE_BITS);                               \
  132.     output[5] >>= (64 - SEARCH_SPACE_BITS);                               \
  133.     output[6] >>= (64 - SEARCH_SPACE_BITS);                               \
  134.     output[7] >>= (64 - SEARCH_SPACE_BITS);                               \
  135. }
  136.  
  137. // Given a hash chunk "cur_hash", if it exists in
  138. //   "hash_list", return the index, else -1.
  139. #define CONTAINS_HASH(cur_chunk, hash_list) \
  140.     (cur_chunk == hash_list[0] ? 0 :        \
  141.      cur_chunk == hash_list[1] ? 1 :        \
  142.      cur_chunk == hash_list[2] ? 2 :        \
  143.      cur_chunk == hash_list[3] ? 3 :        \
  144.      cur_chunk == hash_list[4] ? 4 :        \
  145.      cur_chunk == hash_list[5] ? 5 :        \
  146.      cur_chunk == hash_list[6] ? 6 :        \
  147.      cur_chunk == hash_list[7] ? 7 :        \
  148.      0xFF)
  149.  
  150.  
  151. // Given a "hash", return true/false if it exists in "rainbow"
  152. #define RAINBOW_CHECK(hash, rainbow) (rainbow.find(hash) != rainbow.end())
  153.  
  154.  
  155. // Given "hash" originating from "nonce", see if "hash" exists in "rainbow"
  156. // If it does, and it originated from a nonce other than "nonce"
  157. // Then add "nonce" and found nonce to "results"
  158. #define RAINBOW_SEARCH(hash, nonce, rainbow, results)                             \
  159. UNUSED for (uint32_t chunk = 0; chunk < BIRTHDAYS_PER_HASH; ++chunk) {                   \
  160. UNUSED     if ( RAINBOW_CHECK(hash[chunk], rainbow) ) {                                  \
  161. UNUSED         uint32_t buddy_nonce = getNonceFromHash(hash[chunk], midHash, rainbow);   \
  162. UNUSED                                                                                   \
  163. UNUSED         if (buddy_nonce != -1) {                                                  \
  164. UNUSED             if (buddy_nonce != (nonce + chunk)) {                                 \
  165. UNUSED                 results.push_back( std::make_pair(nonce + chunk, buddy_nonce) );  \
  166. UNUSED                 if (STOP_ON_FIRST_MATCH) { return results; }                      \
  167. UNUSED             }                                                                     \
  168. UNUSED         }                                                                         \
  169. UNUSED     ++hits;                                                                       \
  170. UNUSED     } else { ++misses; }                                                          \
  171. UNUSED }
  172.  
  173.  
  174. // Given "hash" originating from "nonce", add it to the rainbow table.
  175. // Note that we use "nonce", not "nonce + chunk".
  176. // We do this because "nonce" (not "nonce + chunk")
  177. //   hash/compressed CHAIN_LENGTH times produces "hash"
  178. #define RAINBOW_ADD(hash, nonce, rainbow)                           \
  179. for (uint32_t chunk = 0; chunk < BIRTHDAYS_PER_HASH; ++chunk) {     \
  180.     rainbow[hash[chunk]] = (nonce - (nonce % BIRTHDAYS_PER_HASH));  \
  181. }
  182.  
  183. #define PRINT_HASH(hash)                         \
  184. {                                                \
  185. std::cerr << "         0: " << hash[0] << "\n"   \
  186.           << "         1: " << hash[1] << "\n"   \
  187.           << "         2: " << hash[2] << "\n"   \
  188.           << "         3: " << hash[3] << "\n"   \
  189.           << "         4: " << hash[4] << "\n"   \
  190.           << "         5: " << hash[5] << "\n"   \
  191.           << "         6: " << hash[6] << "\n"   \
  192.           << "         7: " << hash[7] << "\n";  \
  193. }
  194.  
  195.  
  196. uint64_t getNonceFromHash(uint32_t origin_nonce, uint64_t hash_chunk,
  197.                           uint256 midHash,
  198.                           boost::unordered_map< uint64_t, uint32_t > &rainbow) {
  199.     // Goal: given that we know "hash" is in "rainbow", find the nonce that made it
  200.     char hash_temp[sizeof(uint256) + 4];
  201.     memcpy((char *)&hash_temp[4], (char *)&midHash, sizeof(midHash));
  202.     uint32_t *hash_input = (uint32_t *)hash_temp;
  203.     uint64_t result_hash[8];
  204.  
  205.     // Backtracking from start of chain
  206.     uint64_t rain_nonce = rainbow[hash_chunk];
  207.  
  208.     // Repeatedly hash/compress from the start of the chain
  209.     //   until we're at the nonce that created hash_chunk
  210.     uint32_t chain;
  211.     for (chain = 0; chain < CHAIN_LENGTH; ++chain)
  212.     {
  213.         HASH(rain_nonce, hash_temp, result_hash);
  214.         uint32_t offset = CONTAINS_HASH(hash_chunk, result_hash);
  215.  
  216.         // Did we find an actual hit?
  217.         if (offset != 0xFF) {
  218.             if (DEBUG_MODE && rain_nonce + offset != origin_nonce) {
  219.                 std::cerr << "RAINBOW HIT\n";
  220.                 std::cerr << "  SEEK HASH: " << hash_chunk << "\n";
  221.                 std::cerr << " ORIG NONCE: " << origin_nonce << "\n";
  222.                 std::cerr << " RAIN NONCE: " << rain_nonce << " + " << offset << "\n";
  223.                 PRINT_HASH(result_hash);
  224.             }
  225.             return (rain_nonce + offset);
  226.         }
  227.  
  228.         rain_nonce  = COMPRESS_HASH(result_hash);
  229.         rain_nonce -= (rain_nonce % BIRTHDAYS_PER_HASH);
  230.     }
  231.  
  232.     // This should never happen.
  233.     std::cerr << "I didnt find " << hash_chunk << " in the table?\n";
  234.     return -1;
  235. }
  236.  
  237.  
  238.  
  239. ///// MAIN HASH /////
  240.  
  241. std::vector< std::pair<uint32_t, uint32_t> > momentum_search(uint256 midHash)
  242. {
  243.     std::vector< std::pair<uint32_t, uint32_t> > results;
  244.     boost::unordered_map< uint64_t, uint32_t > rainbow( RAINBOW_ENTRIES );
  245.     rainbow.rehash( RAINBOW_ENTRIES );
  246.  
  247.     char hash_temp[sizeof(uint256) + 4];
  248.     memcpy((char *)&hash_temp[4], (char *)&midHash, sizeof(midHash));
  249.     uint32_t *hash_input = (uint32_t *)hash_temp;
  250.     uint64_t result_hash[8];
  251.  
  252.  
  253.     // Populate the rainbow table using first RAINBOW_ENTRIES elements
  254.     uint32_t progress = 0;
  255.     uint32_t hits = 0, misses = 0, total = 0;
  256.     for (uint32_t i = 0; i < SEARCH_SPACE; i += BIRTHDAYS_PER_HASH) {
  257.         ++total;
  258.         if (i % (SEARCH_SPACE / 128) == 0) {
  259.             if (DEBUG_MODE) {
  260.                 std::cerr << "Step " << (++progress) << " of 128...\n";
  261.                 std::cerr << "  HITS: " << (hits) << "\n";
  262.                 std::cerr << "  MISS: " << (misses) << "\n";
  263.                 std::cerr << " TOTAL: " << (total) << "\n";
  264.                 std::cerr << "   PCT: " << (100 * hits / (hits + misses + 1)) << "\n";
  265.                 hits = 0; misses = 0;
  266.             }
  267.            
  268.             boost::this_thread::interruption_point();
  269.         }
  270.  
  271.  
  272.         uint32_t cur_nonce = i;
  273.  
  274.         // Apply SHA512 once for each CHAIN_LENGTH
  275.         for (uint32_t chain = 0; chain < CHAIN_LENGTH; ++chain) {
  276.             HASH(cur_nonce, hash_temp, result_hash);
  277.  
  278.             // If it exists in rainbow table, save it in result list
  279.             // RAINBOW_SEARCH(result_hash, cur_nonce, rainbow, results);
  280.             for (uint32_t chunk = 0; chunk < BIRTHDAYS_PER_HASH; ++chunk) {
  281.                 if ( RAINBOW_CHECK(result_hash[chunk], rainbow) ) {
  282.                     uint32_t buddy_nonce = getNonceFromHash(cur_nonce + chunk, result_hash[chunk], midHash, rainbow);
  283.  
  284.                     if (buddy_nonce != -1) {
  285.                         if (buddy_nonce != (cur_nonce + chunk)) {
  286.                             if (DEBUG_MODE) {
  287.                                 std::cerr << "NAILED IT! Nonce: " << cur_nonce << " + " << chunk << "\n";
  288.                                 PRINT_HASH(result_hash);
  289.                             }
  290.                             results.push_back( std::make_pair(buddy_nonce, cur_nonce + chunk) );
  291.                         }
  292.                     }
  293.  
  294.                     ++hits;
  295.                 } else {
  296.                     ++misses;
  297.                 }
  298.             }
  299.            
  300.             // The only valid "starting" nonces are divisible by BIRTHDAYS_PER_HASH
  301.             cur_nonce  = COMPRESS_HASH(result_hash);
  302.             cur_nonce -= (cur_nonce % BIRTHDAYS_PER_HASH);
  303.         }
  304.  
  305.         // Once we've hash/reduced it CHAIN_LENGTH times, add the
  306.         //   resulting hash to the rainbow table with origin "i"
  307.         //   if we're still in the rainbow table building segment
  308.         if (i < RAINBOW_ENTRIES) {
  309.             RAINBOW_ADD(result_hash, i, rainbow);
  310.         }
  311.  
  312.         if (STOP_ON_FIRST_MATCH && results.size() > 0) {
  313.             if (DEBUG_MODE) {
  314.                 uint32_t a = results[0].first;
  315.                 uint32_t b = results[0].second;
  316.  
  317.                 std::cerr << "Checking Work:\n";
  318.                 std::cerr << "    Nonce A: " << a << "\n";
  319.                 std::cerr << "    Nonce B: " << b << "\n";
  320.                 uint64_t hash_a = bts::getBirthdayHash(midHash, a);
  321.                 uint64_t hash_b = bts::getBirthdayHash(midHash, b);
  322.                 std::cerr << "     Hash A: " << hash_a << "\n";
  323.                 std::cerr << "     Hash B: " << hash_b << "\n";
  324.                 std::cerr << "\n";
  325.             }
  326.  
  327.             return results;
  328.         }
  329.     }
  330.  
  331.     return results;
  332. }
  333.  
  334.  
  335. uint64_t getBirthdayHash(const uint256 &midHash, uint32_t a)
  336. {
  337.     uint32_t index = a - (a % 8);
  338.     char  hash_tmp[sizeof(midHash) + 4];
  339.  
  340.     memcpy(&hash_tmp[4], (char *)&midHash, sizeof(midHash));
  341.     memcpy(&hash_tmp[0], (char *)&index, sizeof(index));
  342.  
  343.     uint64_t  result_hash[8];
  344.  
  345.     SHA512((unsigned char *)hash_tmp, sizeof(hash_tmp), (unsigned char *)&result_hash);
  346.  
  347.     uint64_t r = result_hash[a % BIRTHDAYS_PER_HASH] >> (64 - SEARCH_SPACE_BITS);
  348.  
  349.     return r;
  350. }
  351.  
  352. bool momentum_verify(uint256 head, uint32_t a, uint32_t b)
  353. {
  354.     if(a == b) {
  355.         return false;
  356.     }
  357.  
  358.     if(a > MAX_MOMENTUM_NONCE) {
  359.         return false;
  360.     }
  361.  
  362.     if(b > MAX_MOMENTUM_NONCE) {
  363.         return false;
  364.     }
  365.  
  366.     bool r = (getBirthdayHash(head, a) == getBirthdayHash(head, b));
  367.     return r;
  368. }
  369.  
  370. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement