FACT0RN Blockchain: Integer Factorization as Proof-of-Work (PoW) | by Coinbase | May, 2022

Tl;dr: This report updates on what FACT0RN Blockchain, a Coinbase Crypto Community Fund grant recipient, has been working on to replace PoW hashing by work that is of interest to the private sector as well as to the academic community. Code for the FACT0RN Blockchain, which launched April 20, 2022, can be found here and the whitepaper can be found here.

By Escanor Liones (Github)

Proof-of-work (PoW) is the original scheme to secure blockchain technology introduced in 2009 by Satoshi Nakamoto through the Bitcoin whitepaper. An analysis done in late 2021 by the New York Times on the electricity usage of the Bitcoin network indicated that the lowest electricity consumption estimate was on par with the total electricity consumption of Washington State for a year — and more than 7 times as much as Google’s global operations.

Just this month, Forbes reported on a bill that is in the works in New York State, as well as leaked European Union Documents, that signal to ‘A De Facto Ban` on proof-of-work mining in general, for Bitcoin and otherwise. It is worth noting that by and large PoW blockchains are based on some form of hashing — a mathematical function that is easy to compute forward and hard to reverse given an output.

There is a blockchain that uses finding prime constellations as its proof of work, and yet another searches for chains of prime numbers known as Cuningham Chains as its PoW. Vitalik Buterin published an article on July 7, 2013 on Bitcoin Magazine about the latter titled “Primecoin: The Cryptocurrency Whose Mining is Actually Useful” where he observed that “One of the disadvantages of Bitcoin that its proponents often gloss over is the fact that its mining algorithm has little real-world value. ”

The author of the PrimeCoin whitepaper in 2013 stated: “I would expect proof-of-work in cryptocurrency to gradually transition toward energy-multiuse, that is, providing both security and scientific computing values.” I would extend this to include commercial value in addition to security and scientific computing value.

Beyond Bitcoin

The digital security of banks, 500 Fortune companies, governments and many IoT devices depend on RSA — a cryptographic system whose security is provided by the difficulty of factoring integers into their prime factors, and in particular, the difficulty of factoring integers that only have two prime factors where both have exactly the same size in number of digits. These numbers are called strong semiprimes, and factoring them is the RSA problem.

It seems to me, after speaking with mathematicians, cryptographers, and random users on the internet, the reason a blockchain based on the RSA factoring problem has not been created until now is because no one could figure out how the blockchain could generate strong semiprimes for miners to factor without first knowing what the prime factors were.

My solution to this problem is simple: instead of generating strong semiprimes without knowing their factors a priori — which no one can figure out how to do — create conditions under which miners can find these strong semiprimes by way of factoring and reward them for finding them. In the process, tie the blockheader data to this process to secure the blockchain.

The essence of PoW is as follows: generate a random number by hashing the data in the block header of the block to be validated, give miners a range around this generated integer, and allow miners to factor all these integers. If they find a strong semiprime reward them accordingly. If they do not find a strong semiprime they can change the nonce and try again. The miners can generate as many random numbers as they want using nonces, but the search range allowed will always be about the same.

Who cares about integer factorization?

The RSA Challenge, created in 1991 by RSA Labs, has rewarded tens of thousands of dollars for factoring ever bigger integers into their prime factors. The largest such award was given to Jens Frenke in 2005 for factoring RSA-640 in the amount of $20,000 dollars.

As the Springer Encyclopedia of Cryptography and Security notes, “Starting in 1991, RSA Data Security offered a set of ‘challenges’ intended to measure the difficulty of integer factoring. The challenges consisted of a list of 41 RSA Numbers, each the product of two primes of approximately equal length, and another, larger list of Partition Numbers generated according to a recurrence.”

In addition to the interest from private industry there are more than a dozen active academic communities that factor integers as a hobby in the hopes of advancing our knowledge of mathematical theory in various areas. The Cunningham Project has been factoring integers to this end since 1925, yes 1925. The National Science Foundation in the United States funds this project, in part, through XSEDE resources provided by the Texas Advanced Computing Center, the San Diego Supercomputer Center, the National Center for Supercomputing Applications, and Purdue University under grant number TG-DMS100027.

The mersenne prime search project has been factoring in the quest to find ever bigger primes since the mid 90’s. There is a factoring project for Aliquot Sequences, Brilliant Numbers, and the list goes on and on. The factoring interest in the academic community cannot be understated.

The Future of PoW

The concern at large with the energy consumption of PoW mining for blockchain technology is not about the energy usage, but rather about the fact that the work for which the energy is used improves no other part of society or human endeavor in ways mere mortals can point to.

Increasingly, the areas of human endeavor that can benefit from computation in general only continue to grow. The demand for computation can clearly be seen by the success of cloud computing giants like Amazon Web Services (AWS), Google Cloud, Azure by Microsoft, and several other cloud services that are thriving today. There are no major concerns about the energy consumption of these enterprises because the work they do goes to support small business, hospitals, banks, universities, law firms, finance institutions, and every kind of organization you can imagine that need to compute to offer better services to serve society at large.

The issue is not PoW mining, but instead that until now the work in PoW has not gone to benefit any other enterprise but the mining itself. FACT0RN is the first PoW blockchain that seeks to drastically change this situation by replacing hashing by work that is of interest to the private sector as well as to the academic communities and whose success will propel significant funding for universities and mathematical research in general.

–

Coinbase is officially seeking applications for our 2022 developer grants focused on blockchain developers who contribute directly to a blockchain codebase, or researchers producing whitepapers. Learn more about the call for applications here.