Inflation Propensity of Collatz Orbits: A New Proof-of-Work for Blockchain Applications

Abstract

Cryptocurrencies such as Bitcoin rely on a proof-of-work system to validate transactions and prevent attacks or double-spending. A new proof-of-work is introduced which seems to be the first number theoretic proof-of-work unrelated to primes: it is based on a new metric associated to the Collatz algorithm whose natural generalization is algorithmically undecidable: the inflation propensity is defined as the cardinality of new maxima in a developing Collatz orbit. It is numerically verified that the distribution of inflation propensity slowly converges to a geometric distribution of parameter $0.714\approx \frac{(\pi -1)}{3}$ as the sample size increases. This pseudo-randomness opens the door to a new class of proofs-of-work based on congruential graphs.

1. Introduction

A decentralized electronic payment system relies on a ledger of transactions shared on a network. The decentralization of a transaction ledger raises the question of security and integrity of the ledger. In the original Bitcoin protocol, the problem of double-spending or alteration of the ledger is solved by the use of blockchain, a system that requires proof-of-work by a network of computers to confirm transactions. In cryptography, intensive computation as proof-of-work allows one party to verify with little computational effort that a counterparty has spent a large amount of computational effort. The concept was originally developed by Dwork and Naor (1992) as a spam prevention technique. Nakamoto (2008) used, for Bitcoin, a proof-of-work based on Back (2002). The protocol consists in finding a nonce value such that the application of the SHA-256 hashing algorithm to a combination of that nonce and a block of information gives a hash starting with series of zeroes by targetting a given threshold. The idea behind the proof-of-work is that participants have an incentive to cooperate rather than to cheat because the computational power required to cheat is too large. However, as cryptocurrencies became more popular and diverse, an over-reliance on mainstream proof-of-work protocols, such as hashcash-SHA256, Ethash (Wood 2014) or hashcash-Scrypt based proof-of-work (Percival 2009) creates a new type of systemic risk in which a cryptographic breakdown would jeopardize cryptocurrencies that rely on these standard proofs-of-work. A weakness of proofs-of-work in cryptocurrency applications is the threat that a single individual (or a coordinated group) would be able to generate blocks faster than 50% of the network. In that case, this entity would completely control the blockchain-based validation system of transactions. In practice, attacks on hash functions could prevent new transactions or alter past ones. In financial markets, exchanges have the possibility to cancel trades in case of infrastructure breakdown or malfunction. By opposition, a systemic failure of the proof-of-work system in decentralized cryptocurrency markets could mean the destruction of the whole history of transactions. Potential risks clouding the proof-of-work system include innovation in technology, mathematics and cryptography that could compromise the existing protocols. Proofs-of-work entirely based on existing hash algorithms such as SHA-256 have been under stress in recent years. Rubin (2017) documented a well-known mining optimization (“ASIC-BOOST”) that allowed to mine Bitcoin blocks faster than the network average by taking advantage of a technical flaw in SHA-256. A specific optimization of the mining instruments allowed reducing the problem’s complexity by exploiting collision attacks on the SHA-256 hash algorithm. The multiplication of proofs-of-work help mitigate this type of hyper-specialized hardware attack. Bitcoin, Ethereum, Bitcoin Cash and Litecoin overwhelmingly dominate the market capitalization of minable coins. Such concentration of the volumes into a few cryptocurrencies represent equally a significant systemic risk. When looking at the top 25 cryptocurrencies by diluted market capitalization (see

Table 1. The 25 top cryptocurrencies as of 15 October 2018 as can be seen on https://onchainfx.com/v/SMT45r.

Name	∼Fully Diluted (Y2050) Marketcap/15 October 2018	Underlying Algorithm
Bitcoin (BTC)	$134,308,812,450	SHA-256
Ethereum (ETH)	$29,787,293,584	SHA-3
Bitcoin Cash (BCH)	$9,225,442,784	SHA-256
Litecoin (LTC)	$4,430,985,913	Scrypt
Dash (DASH)	$2,956,683,098	X11
Monero (XMR)	$2,300,499,210	CryptoNight
ZCash (ZEC)	$2,262,517,311	Equihash
Ethereum Classic (ETC)	$2,161,731,159	SHA-3
Dogecoin (DOGE)	$1,402,169,807	Scrypt
Siacoin (SC)	$564,862,312	Blake-2b
Bitcoin Gold (BTG)	$526,927,423	Equihash
Digibyte (DGB)	$483,402,492	SHA-256 and others
ReddCoin (RDD)	$447,635,857	Scrypt
Bitcoin Diamond (BCD)	$343,664,370	X13
ZenCash (ZEN)	$275,245,426	SHA-3
Verge (XVG)	$229,929,732	Scrypt
Zcoin (XZC)	$194,506,940	Equihash
Monacoin (MONA)	$124,690,762	Scrypt
Syscoin (SYS)	$81,207,881	Scrypt
Zclassic (ZCL)	$67,149,925	Equihash
Vertcoin (VTC)	$53,917,212	Lyra2REv2
Bitcoin Private (BTCP)	$51,124,537	Equihash
LBRY Credits (LBC)	$41,220,511	LBRY
Einsteinium (EMC2)	$25,808,910	Scrypt
GameCredits (GAME)	$13,734,781	Scrypt

), eight of them use Scrypt as underlying hash algorithm for proof-of-work. Introducing new types of proof-of-work is needed to help networks diversifying the protocols in case of increased concentration of hyper-specialized computational power.

So, even though there exist hundreds of different hash functions already, more diversification of proofs-of-work could further mitigate cryptographic risks and improve robustness of the nascent crypto-economy. Several types of proof-of-work have been designed using new hash functions, such as prime numbers verification (King 2013), graph-theoretic proof-of-work (Tromp 2015) or proof-of-work based on the generalized birthday problem (Biryukov and Khovratovich 2017). Post-quantum algorithms are currently being developed in the field of security, see, for example, Bae et al. (2017). In particular, Kiktenko et al. (2018) propose a quantum-safe blockchain that utilizes quantum key distribution. The application presented in the following sections seems to be the first documented attempt to establish a number theoretic proof-of-work unrelated to primes. The hash proposed is based on properties of the Collatz algorithm. In order to describe this algorithm, consider the following function from ${\mathbb{N}}_0$ to ${\mathbb{N}}_0$:

$$T\left(x\right)=\left\{\begin{array}{cc}x/2\hfill & \mathrm{if}x\mathrm{is}\mathrm{even}\hfill \\ (3x+1)/2\hfill & \mathrm{if}x\mathrm{is}\mathrm{odd}\hfill \end{array}\right.$$

(1)

Now, apply the following iterate of T:

$$\left\{\begin{array}{c}{T}^0\left(x\right)=x\hfill \\ T^{(k+1)}\left(x\right)=T\left(T^k\left(x\right)\right)\hfill \end{array}\right.$$

(2)

The Collatz conjecture states that $\forall x\in {\mathbb{N}}_0,\exists \mathrm{a}\mathrm{finite}k\mathrm{such}\mathrm{that}{T}^k\left(x\right)=1$. Lagarias (2010) uses the following terminology: the “total stopping time” is defined as ${\sigma }_{\infty }\left(x\right)=inf\{k:T^k\left(x\right)=1\}$. The “stopping time” $\sigma \left(x\right)$ is $inf\{k:T^k\left(x\right)<x\}$. The “gamma value” is defined as $\gamma \left(x\right)=\frac{{\sigma }_{\infty }\left(x\right)}{log\left(x\right)}$.

For instance, let us consider the case for $x=3$:

$$\left\{\begin{array}{c}{T}^0\left(3\right)=3,\hfill \\ T^1\left(3\right)=(3\times 3+1)/2=5,\hfill \\ T^2\left(3\right)=(5\times 3+1)/2=8,\hfill \\ T^3\left(3\right)=8/2=4,\hfill \\ T^4\left(3\right)=4/2=2,\hfill \\ T^5\left(3\right)=2/2=1.\hfill \end{array}\right.$$

(3)

In this example, the Collatz sequence1 is $\left\{3,5,8,4,2,1\right\}$ and ${\sigma }_{\infty }\left(3\right)$ equals to 5 while $\sigma \left(3\right)=4$. By definition, the value of ${\sigma }_{\infty }\left(x\right)$ depends on the starting point of the algorithm. For example ∀ $\alpha$ ∈ ${\mathbb{N}}_0$, ${\sigma }_{\infty }\left(2^{\alpha }\right)=\alpha$ as

$$T^{\alpha }\left(2^{\alpha }\right)=1.$$

(4)

Analyzing the total stopping time ∀ x ∈ ${\mathbb{N}}_0$ has proven challenging: the lack of clear patterns and the absence of an analytical shortcut to estimate ${\sigma }_{\infty }\left(x\right)$ have left practitioners with numerical methods to compute it and verify the conjecture. e Silva (2010) proved computationally that the conjecture holds up until $x=20\times 2^{58}$. Current computational capabilities have allowed confirming the conjecture for very large numbers. For example, Honda et al. (2017) introduced a GPU-based method to verify the Collatz algorithm. The authors could verify 1.31e12 64-bit numbers per second. A probabilistic approach is also a frequent workaround to justify the validity of the Collatz conjecture: assuming function $T^k\left(x\right)$ is “random enough”, Crandall (1978) showed that half of the time, the next number in the sequence will be $(3x+1)/2$, then for the next iteration, 1/4 of the time it will be $(3x+1)/4$, then for the next iteration, 1/8 of the time it will be $(3x+1)/8$ and so on so that the average growth in the sequence will be ${\left(\frac{3}{2}\right)}^{1/2}{\left(\frac{3}{4}\right)}^{1/4}{\left(\frac{3}{8}\right)}^{1/8}{\left(\frac{3}{16}\right)}^{1/16}{\left(\frac{3}{32}\right)}^{1/32}\cdots =\frac{3}{4}<1$. Terras (1976) demonstrated that the set of integers {x:- x has stopping time ≤ k} has a limiting asymptotic density $F\left(k\right)$ with $F\left(k\right)\to 1$ as $k\to \infty$. These elements tend to indicate that $T^k\left(x\right)$ does not diverge to infinity as k grows. Using Minsky (1961) machines, Conway (1972) showed that a problem generalizing the Collatz conjecture is not algorithmically decidable. Kurtz and Simon (2007) extended the proof to show that this generalization is ${\Pi }_0^2$ complete. If the problem is truly algorithmically undecidable, then no information about the future inflation of the Collatz map is passed from one step k to the next step $k+1$. To explore that hypothesis and the properties of this “pseudo-randomness”, let us define the inflation propensity of order K $\xi (x,K)$ as the cardinality of the set of steps that lead to a number strictly larger than all previous numbers in the same sequence:

$$\xi (x,K)=\mathbf{card}\left\{k:T^k\left(x\right)>max\left(M_{x,k}\right)\right\},k=1,\dots ,k,\dots K,$$

(5)

where $M_{x,k}=\left\{T^0\left(x\right),T^1\left(x\right),\dots ,T^{k-1}\left(x\right)\right\}$. $\xi (x,{\sigma }_{\infty }\left(x\right))$ is a particular case. For the ease of notation: $\xi \left(x\right)=\xi (x,{\sigma }_{\infty }\left(x\right))$. In the above example of $x=3$, $\xi \left(3\right)=2$. Indeed, the set of numbers strictly larger than the previous maxima in the sequence are $\{5,8\}$ so that $\xi \left(3\right)=\mathbf{card}\{5,8\}=2$. In the other example presented supra with $x=2^{\alpha }$, $\xi \left(2^{\alpha }\right)=0$ ∀ $\alpha$ ∈ ${\mathbb{N}}_0$ since no number in their sequences can be strictly larger than the initial one.

This research paper investigates the distribution of $\xi \left(x\right)$, the inflation propensity as a deterministic variable that resembles a random behavior. If past maxima anywhere in the sequence are independent from new maxima later computed in that orbit, we should have that $\xi \left(x\right)\sim G\left(\rho \right)$, a geometric distribution of parameter $\rho$ with density $f(\xi \left(x\right)=y)={\rho }^y(1-\rho )$. The interests of fitting a density distribution to $\xi \left(x\right)$ are multiple. First, in absence of proof of the Collatz conjecture, numerical analysis of the problem stays relevant towards resolving the question. Second, by properly addressing the behavior of the series for large numbers, one can help anticipate the computational challenges related to exploring the orbits of the Collatz map. Third, identifying pseudo-random behavior of Collatz inflation propensity directly leads to a new class of proofs-of-work for blockchain applications. The remainder of this document is built as follows. The next section discusses the empirical distributions of ${\sigma }_{\infty }\left(x\right)$, $\sigma \left(x\right)$ and $\xi \left(x\right)$ ∀ x ∈ ${\mathbb{N}}_0$. The third section details the observed density of $\xi \left(x\right)$. The density parameter of a geometric distribution is estimated using all natural numbers up to 1$\times {10}^{11}$ as sample. The fourth section presents a new proof-of-work based on inflation propensity, while the last section is a conclusion.

2. Inflation Propensity

Lagarias (1985) describes the $3x+1$ conjecture as “a deterministic process that simulates random behavior” and goes further to mention that the problem seems “structureless”. Urvoy (2001) formally proves the non-regularity of the Collatz’s graph. As a visual illustration of this “structurelessness”, the total stopping time for the first 1$\times {10}^6$ natural numbers as a function of their value is presented in Figure 1. The equally “structureless” empirical distribution of the total stopping time for the same numbers is presented in Figure 2. In this context, “structureless” means that it is impossible to anticipate the frequency of the total stopping time. This is unfortunate since it means observing the total stopping times over a region of ${\mathbb{N}}_0$ gives no information whatsoever on the Collatz problem apart from strictly verifying its convergence. The mean of the total stopping time totally depends on the region over which it is computed, and, even when considering a closed subset of ${\mathbb{N}}_0$, the distribution of the total stopping time appears to be erratic and does not seem to follow any regular pattern. As such, the total stopping time has no apparent statistical properties that could be useful in applications such as, for instance, generating random numbers.

Precisely because the Collatz graph is non-regular, its complexity gives rise to a pseudo-random behavior. Nichols (2018) and Kontorovich and Lagarias (2010) explore similarities between the Collatz model and the following dynamical system:

$${log}_2{T}^K\left(x\right)\approx {\log }_{2}x-K+b_3\sum _{k=0}^K{Y}_k,$$

(6)

where $b_3$ is a constant and $Y_k$ are IID (independent and identically distributed) Bernouilli random variables. The stochastic models predict that all orbits converge to a bounded set and that the total stopping time ${\sigma }_{\infty }\left(x\right)$ for the $3x+1$ map of random starting point x is about 6.95212 $logx$ steps, as $x\to \infty$ have a normal distribution centered around that value. The authors point out that a suitable scaling limit for the trajectories is a geometric Brownian motion. This approach is extended in the current research in order to find a discrete metric that could exhibit some type of consistency and is independent from the starting point x. If a geometric Brownian motion can properly describe trajectories of large orbits, it means its Markov property can be exploited: each marginal step in the orbit is independent from the previous step. As a consequence, the probability to find new maxima after any random point $T^k\left(x\right)$ of a large orbit does not depend on how many new maxima were discovered before that point. In other words, for any $x>>4$ ∈ $\mathbb{N}$:

$$P\left(\xi \left(x\right)>M\mid \xi \left(x\right)\ge \xi (x,k)\right)=P\left(\xi \left(x\right)>M-\xi (x,k)\right),$$

(7)

where $M>\xi (x,k)$ and $M\in \mathbb{N}$. If the inflation propensity is memoryless as described by Equation (7), it directly implies that the density $f\left(\xi \right(x)=y)$ follows a geometric distribution. It would mean that

$$f(\xi \left(x\right)=y)={\rho }^y(1-\rho )$$

(8)

with $\rho$ ∈ $]0;1[$ and y ∈ $\mathbb{N}$. The moment generating function is

$${\mu }_n=L{i}_{-n}\left(\rho \right)-\rho L{i}_{-n}\left(\rho \right),$$

(9)

where $L{i}_n\left(\rho \right)$ is the nth polylogarithm of $\rho$ and

$$\widehat{\rho }=\frac{{\mu }_1}{1+{\mu }_1}$$

(10)

is the corresponding estimator of $\rho$ based on Equation (9). It is also the maximum likelihood estimator. The empirical distribution of $\xi \left(x\right)$ defined in (5) is presented in Figure 3. The next step is to test the hypothesis that $\xi \left(x\right)\sim G\left(\rho \right)$.

3. Empirical Results

The samples consist in the first 1 $\times {10}^8$, 1 $\times {10}^9$, 1 $\times {10}^{10}$ and 1 $\times {10}^{11}$ positive integers. For each sample, the maximum likelihood estimator of $\rho$ is computed, then tests are performed to see if elements of the distribution follow a geometric distribution of parameter $\rho$:

$$\begin{array}{cc}\hfill H_0:P(\xi \left(x\right)=n)={(1-\rho )}^{n-1}\rho & \forall n=1,\dots ,q\end{array}$$

(11)

$$\begin{array}{cc}\hfill H_1:P(\xi \left(x\right)=n)\ne {(1-\rho )}^{n-1}\rho & \forall n=1,\dots ,q\end{array}$$

(12)

where $q\in [0,N]$ and N is the largest observed maximum in the sample. When $q=N$, the entire distribution is tested for goodness of fit with a geometric distribution of parameter $\widehat{\rho }$. The tests are performed using Pearson’s ${\chi }^2$ test at a 10% confidence level.

Table 2. Pearson’s ${\chi }^2$ tests for goodness of fit with a geometric distribution.

		Sample 1 $\times {10}^8$	Sample 1 $\times {10}^9$	Sample 1 $\times {10}^{10}$	Sample 1 $\times {10}^{11}$
$\widehat{\mathit{\rho }}$		0.7133482	0.7135956	0.713667	0.713681
$\mathit{q}$	Percentile	p-Value	p-Value	p-Value	p-Value
0	29	0.01	0.15	0.70	0.64
1	49	0.04	0.19	0.70	0.14
2	64	0.09	0.00	0.23	0.25
3	74	0.15	0.00	0.36	0.39
4	82	0.08	0.00	0.11	0.35
5	87	0.05	0.00	0.01	0.37
6	91	0.07	0.00	0.00	0.13
7	93	0.11	0.00	0.00	0.03
8	95	0.00	0.00	0.00	0.04
9	97	0.00	0.00	0.00	0.03
10	98	0.00	0.00	0.00	0.00

summarizes the results of the tests. As the sample size increases, the hypothesis is not rejected when it comes to considering the first quantiles of the distribution. For the last sample (1 $\times {10}^{11}$), the hypothesis that the distribution of the inflation propensity follows a geometric distribution cannot be rejected up to the 91th percentile, compared to the 49th percentile for the 1 $\times {10}^9$ sample. Computational limitations prevent at this stage investigating larger sample sizes so that the geometric behavior of the inflation propensity over the entire domain (${\mathbb{N}}_0$) needs to be conjectured. Interestingly, the estimator for $\rho$ seems also to converge to a given value as the size of the sample increases and is very close to $\frac{\pi -1}{3}$, which is coincidentally the solution to the equation $3x+1=\pi$ (see Figure 4).

Table A1. Distribution of inflation propensity $\xi \left(x\right)$ for the first 1 $\times {10}^{11}$ integers.

$\mathit{\xi }\left(\mathit{x}\right)$	Observations
0	28,631,964,381
1	20,434,254,718
2	14,583,348,496
3	10,407,804,534
4	7,427,954,284
5	5,301,161,512
6	3,783,166,989
7	2,699,976,430
8	1,927,052,441
9	1,375,229,862
10	981,424,318
11	700,353,911
12	499,868,474
13	356,795,944
14	254,706,290
15	181,761,315
16	129,757,032
17	92,628,127
18	66,127,176
19	47,199,172
20	33,676,458
21	24,024,158
22	17,138,021
23	12,231,945
24	8,727,118
25	6,225,787
26	4,432,544
27	3,162,432
28	2,251,004
29	1,599,248
30	1,139,341
31	814,975
32	583,455
33	416,994
34	298,683
35	212,914
36	150,443
37	106,613
38	76,749
39	55,452
40	39,947
41	28,495
42	20,259
43	14,253
44	10,396
45	7791
46	5431
47	3690
48	2640
49	1984
50	1448
51	1041
52	745
53	595
54	467
55	347
56	234
57	170
58	127
59	72
60	41
61	21
62	20
63	17
64	17
65	9
66	2
67	0
68	1
69	0

in Appendix A indicates the distribution of inflation propensities for the first 1 $\times {10}^{11}$ integers.

4. Application

4.1. Collatz-Based Proof-of-Work

Because the distribution of the inflation propensity of Collatz orbits can be assumed to be geometric over large samples, and that a natural generalization of the Collatz algorithm has been proven to be undecidable, the inflation propensity can be considered as a new candidate to generate proofs-of-work, conjecturing the Collatz algorithm is also undecidable. Consider the following problem: find any set X made of n natural numbers $\{X_1,\dots ,X_i,\dots ,X_n\}$ whose values are between B and $B^{*}=B+\alpha$, a larger number, and that have inflation propensities of given values $\{Q_1,\dots ,Q_i,\dots ,Q_n\}$ with $n<<\alpha$. In other terms, find a solution to the problem

$$Q_i=\xi \left(X_i\right)\forall i\in \{1,\dots ,n\},$$

(13)

where $Q_i$ is known, $X_i\in [B,B^{*}]$ and $X_i\ne X_j\forall i\ne j\in \{1,\dots ,n\}$. $\alpha ,B,B^{*},Q,X\in {\mathbb{N}}_0$. B is the unsigned integer value corresponding to a 256 bits block of hashed information. $\alpha$ is set to an arbitrarily large value, for example $\alpha =2^{64}$. Note that this is still a fraction of the value for B so that pre-computation is virtually impossible in practice.

Since $P(\xi \left(X_i\right)=Q_i)\approx {(\frac{\pi -1}{3})}^{Q_i}(1-\frac{\pi -1}{3})$ the difficulty to the problem can be designed in a straightforward manner: solutions for higher targets $Q_i$ will be exponentially more difficult to find. Nevertheless, verifying the proof given inputs X and B is immediate, a desirable property for a proof-of-work. Once a valid solution set X has been found, the nounce $\nu$ is simply:

$$\nu =X-B,$$

(14)

which in practice is an array if X is a set and is an integer if X is a scalar. At the exception of the nonce and the target Q, the remainder of blockchain application based on Collatz is identical to the existing Bitcoin protocol. In practice, the target set Q can be selected by the network so that, similar to Bitcoin, six blocks are mined per hour. Every 2016 blocks, clients can compare the performance of the network and adjust the difficulty accordingly. Thanks to the geometric nature of the inflation propensity, a protocol for this adjustment is straightforward. Let us assume $U_0$ is the average amount of time required by the network to find any single value $\xi \left(x\right)$. Any total computational time $U_T\ge U_0$ can be easily selected by finding a set Q solving the following problem:

$$U_T=\sum _{q\in Q}\frac{1}{{\rho }^q}{U}_0+ϵ.$$

(15)

Two additional constraints must be considered for the protocol to be properly defined: the set Q must be chosen so that $0\le ϵ\le U_0$ and the cardinality of the set must be as small as possible.

4.2. Example: Bitcoin Genesis Hash

A new Bitcoin genesis hash is created using original inputs by Nakamoto (2008), but exploiting inflation propensity proof-of-work instead of hashcash. The inputs are: a hash merkle root that condenses all information related to the first Bitcoin transaction, a version number, a public key, a date, a time stamp that is used as coinbase parameter, and a target for complexity. A genesis block is the first block of a blockchain. Figure 5 illustrates the proof-of-work system. To create a genesis hash using inflation propensity as proof-of-work, only two adjustments to the Bitcoin protocol are required. First, the target for complexity is expressed with an integer, which is the targeted inflation propensity. This directly relates to a specific probability of occurrence. Second, the hashcash is replaced with the inflation propensity algorithm. In practice, the block header is hashed using SHA-256 then converted into an integer using hexadecimal encoding. This corresponds to B in Equation (14). The target set Q is arbitrarily set to a single value of 40 for the generation of this first hash, which corresponds to a probability of occurence of ∼ 4 $\times {10}^{-7}$. The value of B given Nakamoto’s other initial inputs is of ∼ 2.52 $\times {10}^{76}$. The X nonce is then incrementally added to the integer B and inflation propensity is computed until the target of 40 is reached. The values obtained from each iteration are hereafter named “Xis”. In the Python implementation of the algorithm, 2056 Xis are computed per second on an Intel Core i7-4700MQ CPU with 8 × 2.40 GHz. After 28 min of computation, the solution is found. Verification of the solution is done in ≈ 5 $\times {10}^{-4}$ seconds on the same machine.

Table 3. A genesis hash based on original Bitcoin’s inputs for genesis but using inflation propensity as proof-of-work.

block header hash	37d25f7f472fde7bb5b84f4bb319097c580383911b45eff10e68afa06073d6c0
corresponding integer	25248903652996148805237565338196318809513309980842754974279018460154571249344
merkle hash	4a5e1e4baab89f3a32518a88c31bc87f618f76673e2cc77ab2127b7afdeda33b
pszTimestamp	The Times 3 January 2009 Chancellor on brink of second bailout for banks
pubkey	04678afdb0fe5548271967f1a67130b7105cd6a828e03909a67962e0ea1f61deb649f6bc3f4cef38c4f
	35504e51ec112de5c384df7ba0b8d578a4c702b6bf11d5f
time	1231006505
inflation propensity target	40 (0 × 28)
nounce	3420991
genesis hash	9ed4d59e375c60e568524ac7fdfcce2c36dd8d449a20b0be8c9f6f9dbd2f8709
computational time	28 min

describes diagnostics and results of the genesis hash. Using this first instance to calibrate the computational difficulty, the smallest set Q that solves Equation (15) that would yield an expected computational time of 10 min for the next block would be $\{2,6,16,19,22,26,31,36,41\}$. The Python code to generate the Genesis Hash is provided in Appendix B.

4.3. Advantages of the Collatz-Based Proof-of-Work

The advantages of a Collatz-based proof-of-work are many. From a practitioner perspective, the algorithm is easy to implement in code since the underlying problem is made of simple arithmetic operations, however, bigint arithmetics are needed in case values inflate beyond $2^{256}$. Also, the natural generalization of the Collatz algorithm is known to be algorithmically undecidable. If this holds for Collatz algorithm, asymmetry is guaranteed: it is difficult to find the targeted value but easy to verify. From an engineering point of view, difficulty control based on a geometric distribution is significantly more complex than one based on hashcash, however, from a statistical perspective, the geometric distribution allows a very convenient tailoring of the computational complexity. It is very easy to adjust a specific targeted inflation-propensity, or a combination of targets. The same algorithm can also be indefinitely extended to meet new computational improvements since the upper bound of the orbits is infinity. In addition to this scalability, it could be possible to generalize the $3x+1$ algorithm to other congruential graphs exhibiting the same properties (for example, the $5x+1$ graph). Provided further research confirms this hypothesis, such a feature could allow more possibilities to generate new proofs-of-work.

5. Conclusions

For the classical $3x+1$ map, it is conjectured that inflation propensity $\xi \left(x\right)=\mathbf{card}\left\{k:T^k\left(x\right)>max\left(M_{x,k}\right)\right\},k=1,\dots ,k,\dots {\sigma }_{\infty }\left(x\right)$ has a geometric density distribution whose parameter’s value $\rho \approx$$\frac{\pi -1}{3}$. This has been verified numerically for the first 1 ×${10}^{11}$ integers. The inflation propensity of Collatz orbits is a new metric that exhibits properties particularly well suited to be the base for new cryptography applications. A new proof-of-work is suggested: finding a set X of n integers greater than a hashed block of information B but smaller than a threshold $B^{*}$ such that their inflation propensities be of n given values $Q_1,\dots ,Q_n$. Advantages of this approach are multiple, including an infinite scalability and the possibility to easily tune complexity of the algorithm. This work seems to be the first number theoretic proof-of-work unrelated to primes. Further research is needed to generalize this type of proof-of-work to a larger class of congruential graphs.