README

Proof-of-Work algorithms, like the one used in Bitcoin, require lots of energy to run and provide no benefit other than consensus. Proof-of-SAT is a prototype blockchain consensus algorithm that is no more energy efficient than Proof-of-Work but provides somewhat useful information as a byproduct of the consensus that it provides. Being a prototype means that many features that would actually make it an effective blockchain consensus algorithm are missing such as timestamps and a solution verifier. In Proof-of-SAT, the cryptographic puzzle problem that is used in Proof-of-Work is replaced by approximating the maximum satisfiability problem (MAX-SAT, https://en.wikipedia.org/wiki/Maximum_satisfiability_problem), a problem that has long intrigued computer scientists.

The instances of the maximum satisfiability problem in Proof-of-SAT are deterministically and pseudorandomly generated from the solutions of previous instances of the maximum satisfiability problem, as is similarly done in Proof-of-Work. These instances being pseudorandom somewhat hamper the usefulness of the solution. Although given enough solutions, statistical analysis could be performed to gain insight into satisfiability solving.

This algorithm incorporates the maximum satisfiability problem but this selection was done somewhat arbitrarily. There are many computational problems that would be ideal as a blockchain consensus algorithm and may provide more useful statistics than the Proof-of-SAT algorithm. MAX-SAT being an NP-complete problem means that it can be reduced to any other NP-complete problem whichs opens the door to a wealth of problems that could potentially be encoded as a blockchain consensus algorithm, so long as they can be approximated effectively.

Furthermore, any problem that can be solved or approximated within a predetermined degree only needs to have the ability to have an instance be generated pseudorandomly and deterministically to be elgible to be created into a blockchain consensus algorithm. This process is performed within the solution_to_sat function in Proof-of-SAT in such a way that could be easily generalized to other problems. However, an effective blockchain consensus algorithm will have other features as well such as being hard to solve and easy to verify, having adjustable difficulty, and having a predictable solve time. Hopefully, Proof-of-SAT serves as an effective model of what is possible with blockchain consensus algorithms.