Bitcoin Forum

// Copyright (c) 2016 Satoshi Nakamoto
// Distributed under the MIT/X11 software license, see the accompanying
// file license.txt or http://www.opensource.org/licenses/mit-license.php.


#include <stdio.h>
#include <gmp.h>
#include<math.h>
/* make sure to invoke gcc with -lgmp */


// NEVER i repeat NEVER use a dead big number variable

struct res {
	int rh;	// height
	// each return from recursion increases h by one
	// deepest solution returns zero
	// no solution returns SOLUTIONNOTFOUND

	//logarithm of no. of variables in the level having the most variables)
	double e;	// maximum entropy per round

	long  unsigned long p0; 
	long  unsigned long p1; 
	long  unsigned long p2; 
};

void nxt(mpz_t r, mpz_t a) {
	mpz_t s,t;
	mpz_init(s);
	mpz_init(t);
	mpz_sub_ui(s, a, 1);		// bcsub
	mpz_mul(t, a, s);		// bcmul
	mpz_div_2exp(r, t, 1);		// bcdiv 2
	mpz_clear(s);
	mpz_clear(t);
}

int
compare_doubles (const double da, const double db)
{

  return (da > db) - (da < db);
}

static int SUCCESS = 0;
static int SOLUTIONNOTFOUND = 9999999;

//static struct res oracle;


static long  unsigned long longlongbitsminus1;

// h .. number of already pushed hashes to signature
// s .. NOT the number of objects in this layer  !!! see d
// e .. the already signed entropy (bits)
// d .. how many divisions by two need to be performed on s to get actual number of objects in this layer
// d .. This is optimalization to save memory
// b .. this is burst. during a burst (>0) cannot do growth rounds, only merkle reduce rounds
// .... this is an optimalization because merkle reduce rounds tend to appear in bursts

// m .. the total maximum length of message that needs to be signed
static long double messagedigest;
static int burstdefault;

static double maxentropyperlevel = 0.0;

// ooo and sticky are related to burst
// they activate bursts

static int beancounter = 0;

//int debug() {
//	return oracle.rh != SOLUTIONNOTFOUND;
//}

//void nextoracle() {
//
///		oracle.p0 /= 2;
//		oracle.p0 |= oracle.p1 << longlongbitsminus1;
//		oracle.p1 /= 2;
//		oracle.p1 |= oracle.p2 << longlongbitsminus1;
//		oracle.p2 /= 2;
//
//}

struct res findt(int h, mpz_t s, long  double e, unsigned d, int ooo, int stick) {
beancounter++;

//	int oracbit = oracle.p0 & 1;
//	nextoracle();

	struct res x;
	double n = 0.;


	if (h < 0) {
		// maximum hashes heuristic cap exceeded

		// Terminate without a solution

		x.rh = SOLUTIONNOTFOUND;
		x.e = 0;
		x.p0 = 0;
		x.p1 = 0;
		x.p2 = 0;
		return x;
	}

	int mustreducetopk = 0;
	int canreducebemoreorfour = 0;

	if ((e >= messagedigest) ) {	// must 
		mustreducetopk = 1;
	}

	// here I must compare number of variables with the cached division
	// to see if we have less than 8 variables in this level
	//(after level with 8 variables comes a level with 4 variables-the public key level)
	// in this case the algorithm will terminate and return a valid solution(iff all entropy is signed)
	unsigned long int cacheddiv = 8;
	cacheddiv <<= d;

	int cmp = mpz_cmp_ui(s, cacheddiv);

	if (cacheddiv == 0) {

		// OVERFLOW OF DIVIDER
		// Terminate without a solution here?

		int terminateaftertoomanymerklereductions = 0;

		if (terminateaftertoomanymerklereductions){

			x.rh = SOLUTIONNOTFOUND;
			x.e = 0;
			x.p0 = 0;
			x.p1 = 0;
			x.p2 = 0;
			return x;
		}


		// approximate double based compute

		double huge = mpz_get_d (s);

		double ex = 8.0 * exp2 ((double)d);



		cmp = compare_doubles(huge, ex);


	}




	if ((cmp == 0) || (cmp > 0)) {
		canreducebemoreorfour = 1;
	}



	if (mustreducetopk && !canreducebemoreorfour) {

		// solution found. 0
		x.rh = SUCCESS;
		x.e = 0;
		x.p0 = 0;
		x.p1 = 0;
		x.p2 = 0;
		return x;
	}

	if (mustreducetopk || canreducebemoreorfour) {

		// no entropy signed when reducing
		n = 0;

//		// print
///		mpz_out_str(stdout, 10, b);  putchar('\n');
///		printf("%lf \n", n);


		// counter of the burst
		int ppp = ooo-1;
		if (ppp <= 0) {
			ppp = 0;
		}


//		if ((oracle.rh == SOLUTIONNOTFOUND) || (oracbit == 1)) {

		// recurse
		x = findt(h-1, s, e+n, d+1, ppp, 1);

//		} else {
//		x.rh = SOLUTIONNOTFOUND;
//		x.e = 0;
//		x.p0 = 0;
//		x.p1 = 0;
//		x.p2 = 0;
//		}

		// add this level to total length
		x.rh++;

		// mark 1 bit
		x.p2 *= 2;
		x.p2 |= x.p1 >> longlongbitsminus1;
		x.p1 *= 2;
		x.p1 |= x.p0 >> longlongbitsminus1;
		x.p0 *= 2;
		x.p0++;


		if (mustreducetopk) {
			return x;
		}


	} else {
		x.rh = SOLUTIONNOTFOUND;
		x.e = 0;
		x.p0 = 0;
		x.p1 = 0;
		x.p2 = 0;
	}

	// if not burst
	if (ooo == 0) {
		mpz_t b, t;


		mpz_init(b);

		struct res y;

		//
//		printf("~~~~%i ~~~~ \n",beancounter);

		// explode
		if (d > 0) {
			// here i apply the cached merkle reduce rounds



//			if (debug()) {
//			// print
//			mpz_out_str(stdout, 10, s);  putchar('\n');
//			}



			mpz_init(t);


			if (1) {
			mpz_t xx;
			mpz_init(xx);
			mpz_t gg;
			mpz_init(gg);
			mpz_t oo;
			mpz_init(oo);
			mpz_t pp;
			mpz_init(pp);

			mpz_set_ui(xx, 1);
			mpz_mul_2exp(gg, xx, d);
			mpz_sub_ui(oo,gg,1);

//			if (debug()) {
//			// print
//			mpz_out_str(stdout, 10, oo);  putchar('\n');
//			}


			mpz_add(pp,oo,s);



			mpz_div_2exp(t, pp, d);


//			mpz_div_2exp(t, s, d);

			// don't forget to free the big number
			mpz_clear(pp);
			// don't forget to free the big number
			mpz_clear(oo);
			// don't forget to free the big number
			mpz_clear(gg);
			// don't forget to free the big number
			mpz_clear(xx);

			} else {
			mpz_div_2exp(t, s, d);
			}


//			if (debug()) {
//			// print
//			mpz_out_str(stdout, 10, t);  putchar('\n');
//			}

			// here I calculate the entropy from t
			n = (mpz_get_d (t));

		} else {

			// print
//			mpz_out_str(stdout, 10, s);  putchar('\n');

			// here I calculate the entropy from t
			n = (mpz_get_d (s));

		}

//		if (debug()) {
//		// Print entropy
//		printf("|%i|%lf \n", beancounter,n);
//		}
		

		n = log2(n);


		// explode
		if (d > 0) {
			nxt(b, t);
			mpz_clear(t);
		} else {
			nxt(b, s);
		}

			// print
//			mpz_out_str(stdout, 10, b);  putchar('\n');

		// here I calculate the entropy from b
		n = (mpz_get_d (b));
//		if (debug()) {
//		// Print entropy
//		printf("|%i|%lf \n", beancounter,n);
//		}
		n = log2(n);


//		while (1) {
//			sleep(1);
//		}

		// check if it exceeds the per-round entropy treshold cap
		if ((n > maxentropyperlevel) && (maxentropyperlevel != 0.0)) {




			// don't forget to free the big number
			mpz_clear(b);

			// don't do this
			return x;
		}


//		// print

//		printf("%lf \n", n);


		// burst counter
		int ppp = ooo;
		if (stick == 1) {
			ppp = burstdefault;
		}

		// If x branch was successful, this branch should not be longer.
		if (x.rh != SOLUTIONNOTFOUND) {
			h = x.rh+1;
		}

//		// print
//		printf("|%i|%lf \n", beancounter,n);

//		if ((oracle.rh == SOLUTIONNOTFOUND) || (oracbit == 0)) {
//		// recurse
		y = findt(h-1, b, e+n, 0, ppp, stick);
//		} else {
//		y.rh = SOLUTIONNOTFOUND;
//		y.e = 0;
//		y.p0 = 0;
//		y.p1 = 0;
//		y.p2 = 0;
//		}

		// free big number
		mpz_clear(b);

		// just check if solution
		if (y.rh == SOLUTIONNOTFOUND) {
			return x;
		}

		// add this level to total length
		y.rh++;

		if (y.e < n) {

			y.e = n;

//		// print
//		printf("|%i|%lf \n", beancounter,n);


//		while (1) {
//			sleep(1);
//		}

		}


		// mark 0 bit
		y.p2 *= 2;
		y.p2 |= y.p1 >> longlongbitsminus1;
		y.p1 *= 2;
		y.p1 |= y.p0 >> longlongbitsminus1;
		y.p0 *= 2;



		// get choice leading to shorter. Long is bad
		if (x.rh > y.rh) {
			x = y;

		// get choice leading to less max entropy per level. Big is bad
		} else if ((x.rh == y.rh) && (x.e > y.e)) {
			x = y;
		}

		return x;

	}

	return x;
}

int roundsform_heuristics(double m) {
	double room = 10.; // 10 rounds more than expected allowed

	// m160bit ..  84rounds ~~ +10
	// m256bit .. 133rounds ~~ +10

	return (int)((m * 0.510416667) + 2.333333333 + room);
}

int main(int argc, char *argv[]) 
{
// get machine word
longlongbitsminus1 = ((8*sizeof(unsigned long long))-1);
printf("LLsizem1:%Lu\n",longlongbitsminus1);


  int h;  h = 0;



//  mpz_out_str(stdout, 10, b);  putchar('\n');




struct res r;





long double m = 128.0;
long double md = 8.0;


int burstd = 0;
int burst = 15;

double elimit = 0.;
double elimitd = 0.;

	// load the command line parameters
	if (argc == 7) {
		sscanf(argv[1], "%Lf", &m);
		sscanf(argv[2], "%Lf", &md);

		sscanf(argv[3], "%i", &burst);
		sscanf(argv[4], "%i", &burstd);

		sscanf(argv[5], "%lf", &elimit);
		sscanf(argv[6], "%lf", &elimitd);
	}


	// predict rounds using heuristic
	h = roundsform_heuristics(m);
	h = 0xffff;



	printf("\nINPUT: Digest M=%Lf; Mdelta=%Lf ; HeuriMaxHashes X=%i ;"
		"  BURST=%i Bdelta=%i ; logLimit %lf logLdelta %lf \n\n",m,md,h,burst, burstd, elimit, elimitd);



	// solve slightly different many times over the night
int i;
	for (i = 0; i < 1000;i++) {


  mpz_t b;  mpz_init(b);
  mpz_set_str(b, "4", 10); // the 10 represents the radix

	// real run
//	oracle.rh = SOLUTIONNOTFOUND;
	maxentropyperlevel = elimit;
	burstdefault = burst;
	messagedigest = m;
	r = findt(h,b,0,0,0,0);
//	oracle = r;

//	// also verify
//	findt(h,b,0,0,0,0);


	mpz_clear(b);


	if (r.rh == SOLUTIONNOTFOUND) {
		printf("SOLUTION WAS NOT FOUND PROBABLY BECAUSE HEURISTIC LIMIT IS TOO LOW: %i\n ", h);
		printf("try giving more room to the heuristics\n");

		return 0;
	}

	// print the solution
	printf("BITS of Message Digest: %Lf SHORTEST HASHES: %i, burst=%i , e=%lf , PATH",m, r.rh, burstdefault, r.e);

	// print the algorithm bitmap (solution)
	if (r.p2 == 0) {
	if (r.p1 == 0) {
	printf("  %Lx | %Lx %Lx %Lx\n\n\n", r.p0, r.p2, r.p1, r.p0);
	} else {
	printf("  %Lx%Lx | %Lx %Lx %Lx\n\n\n", r.p1, r.p0, r.p2, r.p1, r.p0);
	}} else {
	printf("  %Lx%Lx%Lx | %Lx %Lx %Lx\n\n\n", r.p2, r.p1, r.p0, r.p2, r.p1, r.p0);
	}

		if ((md == 0.) && (burstd == 0) && (elimitd == 0.)) {

			return 0;
		}


		// solve slightly different again

		m += md;
		if (h != 0xffff) {
			h = roundsform_heuristics(m);
		}
		burst += burstd;
		elimit += elimitd;
	}

  return 0;

}