I wonder if this C++ code does qualify me for the honorary Satoshi Nakamoto title
// 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
#include
#include
/* 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;
}
