Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include "momentum.h"
- #include <boost/unordered_map.hpp>
- #include <iostream>
- namespace bts
- {
- uint64_t getBirthdayHash(const uint256 &midHash, uint32_t a);
- #define MAX_MOMENTUM_NONCE ( 1<<26 )
- #define SEARCH_SPACE_BITS ( 50 )
- #define BIRTHDAYS_PER_HASH ( 8 )
- #define SEARCH_SPACE ( MAX_MOMENTUM_NONCE )
- #define CHAIN_LENGTH ( 2 )
- #define RAINBOW_ENTRIES ( SEARCH_SPACE / CHAIN_LENGTH )
- #define STOP_ON_FIRST_MATCH ( 1 )
- #define DEBUG_MODE ( 0 )
- // Overview:
- // https://en.wikipedia.org/wiki/Rainbow_table
- // Make a "rainbow table" map to hold the equivalent hash space of SEARCH_SPACE
- // For chains of length CHAIN_LENGTH,
- // rainbow table needs (SEARCH_SPACE / CHAIN_LENGTH) elements [name: RAINBOW_ENTRIES]
- // Rainbow table will require (8 bytes (hash) + 4 bytes (nonce)) * RAINBOW_ENTRIES bytes total
- // To compress each SEARCH_SPACE_BITS hash to a new nonce in the range MAX_MOMENTUM_NONCE,
- // simply use (hash % MAX_MOMENTUM_NONCE)
- // Pseudocode:
- // For the first RAINBOW_ENTRIES
- // nonce = element number
- // For i = 1 to CHAIN_LENGTH
- // cur_hash = HASH(nonce)
- // Check if any part of cur_hash is in rainbow table
- // If yes and generated by different nonce: add to result list
- // For each chunk in cur_hash
- // rainbow_map[chunk] = element number
- // nonce = compress(cur_hash)
- //
- // For the next (SEARCH_SPACE - RAINBOW_ENTRIES) elements:
- // nonce = element number
- // For i = 1 to CHAIN_LENGTH
- // cur_hash = Hash(nonce)
- // Check if any part of cur_hash is in rainbow table
- // If yes and generated by different nonce: add to result list
- // nonce = compress(cur_hash)
- //
- // return result list
- ///// MATH SECTION /////
- // Given:
- // CALLS(CHAIN_LENGTH) = total calls to SHA512 using a rainbow table with chain length CHAIN_LENGTH
- // CALLS(CHAIN_LENGTH) = (SEARCH_SPACE / CHAIN_LENGTH) + (SEARCH_SPACE * CHAIN_LENGTH) - (SEARCH_SPACE / CHAIN_LENGTH)
- // + (SEARCH_SPACE / CHAIN_LENGTH) = Calls to generate rainbow table
- // + (SEARCH_SPACE * CHAIN_LENGTH) = Calls to check SEARCH_SPACE nonce values
- // - (SEARCH_SPACE * CHAIN_LENGTH) = Except we skip the nonces used to make the rainbow table
- // CALLS(CHAIN_LENGTH) = (SEARCH_SPACE * CHAIN_LENGTH)
- // Given:
- // MEMORY(CHAIN_LENGTH) = number of bytes required to store a rainbow table representing
- // SEARCH_SPACE elements with chain length CHAIN_LENGTH
- // MEMORY(CHAIN_LENGTH) = rainbow table elements * (size of hash chunk + size of nonce)
- // MEMORY(CHAIN_LENGTH) = (8 + 4) * SEARCH_SPACE / CHAIN_LENGTH
- // Examples:
- // Minimum number of SHA512 calls is CHAIN_LENGTH = 1 (equivalent to the "default" semiordered map setup)
- // Requires (SEARCH_SPACE * 12) = 768 MB memory
- // Requires (SEARCH_SPACE) calls to SHA512
- // For CHAIN_LENGTH = N
- // Requires (SEARCH_SPACE * 12 / N) bytes of memory
- // Requires (SEARCH_SPACE * N) calls to SHA512
- // For CHAIN_LENGTH = 1024
- // Requires (2^26 * 12 / 1024) = 768 KB of memory
- // Requires (2*26 * 1024) calls to SHA512
- // Bottom line:
- // Using a rainbow table map of chain length N,
- // memory usage is multiplied by a factor of 1/N
- // and SHA512 calls are multiplied by a factor of N
- // This means that regardless the CHAIN_LENGTH selected,
- // the ratio of CALLS(CHAIN_LENGTH) to MEMORY(CHAIN_LENGTH)
- // is inversely proportional.
- // EFFICIENCY IS CONSTANT AT ANY MEMORY TARGET.
- // All that matters is brute computational strength.
- // Example:
- // If a GPU/ASIC/FPGA has PROCESSOR number of parallel computing units,
- // and MEM_MAX bytes of available memory, then each
- // Momentum hash instance can use up to (MEM_MAX / PROCESSOR) bytes of memory.
- // To calculate the CHAIN_LEN to acheive this:
- // CHAIN_LEN(MEM_MAX, PROCESSOR) = (8 + 4) * SEARCH_SPACE / (MEM_MAX / PROCESSOR)
- // CHAIN_LEN(MEM_MAX, PROCESSOR) = (8 + 4) * SEARCH_SPACE * PROCESSOR / MEM_MAX
- // Note: This calculation is just the inverse of MEMORY(CHAIN_LEN)
- // Assuming: GPU with 128 compute units, 1 GB memory, and SEARCH_SPACE = MAX_MOMENTUM_NONCE
- // CHAIN_LEN(2^30, 2^7) = (8 + 4) * SEARCH_SPACE * PROCESSOR / MEM_MAX
- // CHAIN_LEN(2^30, 2^7) = (8 + 4) * SEARCH_SPACE * 2^7 / 2^30
- // CHAIN_LEN(2^30, 2^7) = 12 * SEARCH_SPACE / 2^23
- // CHAIN_LEN(2^30, 2^7) = 12 * 2^26 / 2^23
- // CHAIN_LEN(2^30, 2^7) = 12 * 2^3
- // CHAIN_LEN(2^30, 2^7) = 96
- // Verification:
- // MEMORY(CHAIN_LENGTH) = (8 + 4) * SEARCH_SPACE / CHAIN_LENGTH
- // MEMORY(96) = (8 + 4) * 2^26 / 96
- // MEMORY(96) = 8388608 bytes
- // MEMORY(96) = 8 MB
- // CALLS(CHAIN_LENGTH) = (SEARCH_SPACE * CHAIN_LENGTH)
- // Result: 1/96th the normal memory usage of 768 MB, 96x the SHA512 calls.
- // The problem is no longer about memory, it's about computation speed.
- ///// UTILITY FUNCTIONS /////
- // Compresses "hash" to within MAX_MOMENTUM_NONCE space
- #define COMPRESS_CHUNK(chunk) ( chunk % MAX_MOMENTUM_NONCE )
- #define COMPRESS_HASH(hash) ( COMPRESS_CHUNK(hash[0]) )
- // HASH is a wrapper for SHA512
- // It creates BIRTHDAYS_PER_HASH elements, each one
- // right shifted by (64 - SEARCH_SPACE_BITS)
- #define HASH(input, temp, output) \
- { \
- *hash_input = input; \
- SHA512((unsigned char *)temp, sizeof(temp), (unsigned char *)output); \
- output[0] >>= (64 - SEARCH_SPACE_BITS); \
- output[1] >>= (64 - SEARCH_SPACE_BITS); \
- output[2] >>= (64 - SEARCH_SPACE_BITS); \
- output[3] >>= (64 - SEARCH_SPACE_BITS); \
- output[4] >>= (64 - SEARCH_SPACE_BITS); \
- output[5] >>= (64 - SEARCH_SPACE_BITS); \
- output[6] >>= (64 - SEARCH_SPACE_BITS); \
- output[7] >>= (64 - SEARCH_SPACE_BITS); \
- }
- // Given a hash chunk "cur_hash", if it exists in
- // "hash_list", return the index, else -1.
- #define CONTAINS_HASH(cur_chunk, hash_list) \
- (cur_chunk == hash_list[0] ? 0 : \
- cur_chunk == hash_list[1] ? 1 : \
- cur_chunk == hash_list[2] ? 2 : \
- cur_chunk == hash_list[3] ? 3 : \
- cur_chunk == hash_list[4] ? 4 : \
- cur_chunk == hash_list[5] ? 5 : \
- cur_chunk == hash_list[6] ? 6 : \
- cur_chunk == hash_list[7] ? 7 : \
- 0xFF)
- // Given a "hash", return true/false if it exists in "rainbow"
- #define RAINBOW_CHECK(hash, rainbow) (rainbow.find(hash) != rainbow.end())
- // Given "hash" originating from "nonce", see if "hash" exists in "rainbow"
- // If it does, and it originated from a nonce other than "nonce"
- // Then add "nonce" and found nonce to "results"
- #define RAINBOW_SEARCH(hash, nonce, rainbow, results) \
- UNUSED for (uint32_t chunk = 0; chunk < BIRTHDAYS_PER_HASH; ++chunk) { \
- UNUSED if ( RAINBOW_CHECK(hash[chunk], rainbow) ) { \
- UNUSED uint32_t buddy_nonce = getNonceFromHash(hash[chunk], midHash, rainbow); \
- UNUSED \
- UNUSED if (buddy_nonce != -1) { \
- UNUSED if (buddy_nonce != (nonce + chunk)) { \
- UNUSED results.push_back( std::make_pair(nonce + chunk, buddy_nonce) ); \
- UNUSED if (STOP_ON_FIRST_MATCH) { return results; } \
- UNUSED } \
- UNUSED } \
- UNUSED ++hits; \
- UNUSED } else { ++misses; } \
- UNUSED }
- // Given "hash" originating from "nonce", add it to the rainbow table.
- // Note that we use "nonce", not "nonce + chunk".
- // We do this because "nonce" (not "nonce + chunk")
- // hash/compressed CHAIN_LENGTH times produces "hash"
- #define RAINBOW_ADD(hash, nonce, rainbow) \
- for (uint32_t chunk = 0; chunk < BIRTHDAYS_PER_HASH; ++chunk) { \
- rainbow[hash[chunk]] = (nonce - (nonce % BIRTHDAYS_PER_HASH)); \
- }
- #define PRINT_HASH(hash) \
- { \
- std::cerr << " 0: " << hash[0] << "\n" \
- << " 1: " << hash[1] << "\n" \
- << " 2: " << hash[2] << "\n" \
- << " 3: " << hash[3] << "\n" \
- << " 4: " << hash[4] << "\n" \
- << " 5: " << hash[5] << "\n" \
- << " 6: " << hash[6] << "\n" \
- << " 7: " << hash[7] << "\n"; \
- }
- uint64_t getNonceFromHash(uint32_t origin_nonce, uint64_t hash_chunk,
- uint256 midHash,
- boost::unordered_map< uint64_t, uint32_t > &rainbow) {
- // Goal: given that we know "hash" is in "rainbow", find the nonce that made it
- char hash_temp[sizeof(uint256) + 4];
- memcpy((char *)&hash_temp[4], (char *)&midHash, sizeof(midHash));
- uint32_t *hash_input = (uint32_t *)hash_temp;
- uint64_t result_hash[8];
- // Backtracking from start of chain
- uint64_t rain_nonce = rainbow[hash_chunk];
- // Repeatedly hash/compress from the start of the chain
- // until we're at the nonce that created hash_chunk
- uint32_t chain;
- for (chain = 0; chain < CHAIN_LENGTH; ++chain)
- {
- HASH(rain_nonce, hash_temp, result_hash);
- uint32_t offset = CONTAINS_HASH(hash_chunk, result_hash);
- // Did we find an actual hit?
- if (offset != 0xFF) {
- if (DEBUG_MODE && rain_nonce + offset != origin_nonce) {
- std::cerr << "RAINBOW HIT\n";
- std::cerr << " SEEK HASH: " << hash_chunk << "\n";
- std::cerr << " ORIG NONCE: " << origin_nonce << "\n";
- std::cerr << " RAIN NONCE: " << rain_nonce << " + " << offset << "\n";
- PRINT_HASH(result_hash);
- }
- return (rain_nonce + offset);
- }
- rain_nonce = COMPRESS_HASH(result_hash);
- rain_nonce -= (rain_nonce % BIRTHDAYS_PER_HASH);
- }
- // This should never happen.
- std::cerr << "I didnt find " << hash_chunk << " in the table?\n";
- return -1;
- }
- ///// MAIN HASH /////
- std::vector< std::pair<uint32_t, uint32_t> > momentum_search(uint256 midHash)
- {
- std::vector< std::pair<uint32_t, uint32_t> > results;
- boost::unordered_map< uint64_t, uint32_t > rainbow( RAINBOW_ENTRIES );
- rainbow.rehash( RAINBOW_ENTRIES );
- char hash_temp[sizeof(uint256) + 4];
- memcpy((char *)&hash_temp[4], (char *)&midHash, sizeof(midHash));
- uint32_t *hash_input = (uint32_t *)hash_temp;
- uint64_t result_hash[8];
- // Populate the rainbow table using first RAINBOW_ENTRIES elements
- uint32_t progress = 0;
- uint32_t hits = 0, misses = 0, total = 0;
- for (uint32_t i = 0; i < SEARCH_SPACE; i += BIRTHDAYS_PER_HASH) {
- ++total;
- if (i % (SEARCH_SPACE / 128) == 0) {
- if (DEBUG_MODE) {
- std::cerr << "Step " << (++progress) << " of 128...\n";
- std::cerr << " HITS: " << (hits) << "\n";
- std::cerr << " MISS: " << (misses) << "\n";
- std::cerr << " TOTAL: " << (total) << "\n";
- std::cerr << " PCT: " << (100 * hits / (hits + misses + 1)) << "\n";
- hits = 0; misses = 0;
- }
- boost::this_thread::interruption_point();
- }
- uint32_t cur_nonce = i;
- // Apply SHA512 once for each CHAIN_LENGTH
- for (uint32_t chain = 0; chain < CHAIN_LENGTH; ++chain) {
- HASH(cur_nonce, hash_temp, result_hash);
- // If it exists in rainbow table, save it in result list
- // RAINBOW_SEARCH(result_hash, cur_nonce, rainbow, results);
- for (uint32_t chunk = 0; chunk < BIRTHDAYS_PER_HASH; ++chunk) {
- if ( RAINBOW_CHECK(result_hash[chunk], rainbow) ) {
- uint32_t buddy_nonce = getNonceFromHash(cur_nonce + chunk, result_hash[chunk], midHash, rainbow);
- if (buddy_nonce != -1) {
- if (buddy_nonce != (cur_nonce + chunk)) {
- if (DEBUG_MODE) {
- std::cerr << "NAILED IT! Nonce: " << cur_nonce << " + " << chunk << "\n";
- PRINT_HASH(result_hash);
- }
- results.push_back( std::make_pair(buddy_nonce, cur_nonce + chunk) );
- }
- }
- ++hits;
- } else {
- ++misses;
- }
- }
- // The only valid "starting" nonces are divisible by BIRTHDAYS_PER_HASH
- cur_nonce = COMPRESS_HASH(result_hash);
- cur_nonce -= (cur_nonce % BIRTHDAYS_PER_HASH);
- }
- // Once we've hash/reduced it CHAIN_LENGTH times, add the
- // resulting hash to the rainbow table with origin "i"
- // if we're still in the rainbow table building segment
- if (i < RAINBOW_ENTRIES) {
- RAINBOW_ADD(result_hash, i, rainbow);
- }
- if (STOP_ON_FIRST_MATCH && results.size() > 0) {
- if (DEBUG_MODE) {
- uint32_t a = results[0].first;
- uint32_t b = results[0].second;
- std::cerr << "Checking Work:\n";
- std::cerr << " Nonce A: " << a << "\n";
- std::cerr << " Nonce B: " << b << "\n";
- uint64_t hash_a = bts::getBirthdayHash(midHash, a);
- uint64_t hash_b = bts::getBirthdayHash(midHash, b);
- std::cerr << " Hash A: " << hash_a << "\n";
- std::cerr << " Hash B: " << hash_b << "\n";
- std::cerr << "\n";
- }
- return results;
- }
- }
- return results;
- }
- uint64_t getBirthdayHash(const uint256 &midHash, uint32_t a)
- {
- uint32_t index = a - (a % 8);
- char hash_tmp[sizeof(midHash) + 4];
- memcpy(&hash_tmp[4], (char *)&midHash, sizeof(midHash));
- memcpy(&hash_tmp[0], (char *)&index, sizeof(index));
- uint64_t result_hash[8];
- SHA512((unsigned char *)hash_tmp, sizeof(hash_tmp), (unsigned char *)&result_hash);
- uint64_t r = result_hash[a % BIRTHDAYS_PER_HASH] >> (64 - SEARCH_SPACE_BITS);
- return r;
- }
- bool momentum_verify(uint256 head, uint32_t a, uint32_t b)
- {
- if(a == b) {
- return false;
- }
- if(a > MAX_MOMENTUM_NONCE) {
- return false;
- }
- if(b > MAX_MOMENTUM_NONCE) {
- return false;
- }
- bool r = (getBirthdayHash(head, a) == getBirthdayHash(head, b));
- return r;
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement