Nexa Proof-of-Work algorithm changes are already planned and being worked towards. A Cellular Automaton was already mentioned as a coming upgrade to the new NexaPoW 2.0 version. The President of Bitcoin Unlimited, Andrew Clifford, also briefly introduced a part of the new Nexa algorithm, and Chief Scientist Dr Peter Rizun released an article which explained why Nexa is redesigning the mining algorithm.
With the new NexaPoW 2.0 algorithm a Cellular Automaton will be introduced which can change configuration too frequently and unpredictably for any dedicated ASICs to be deployed. This change in the mining algorithm will effectively make mining ASIC-resistant and limited to FPGAs.
To better understand these changes it is worth getting deeper into the new engine. The Cellular Automaton is one of the simplest machines in computer science and can be understood in five minutes.
The Simplest Machine
The basics of a Cellular Automaton are very simple, and it can be described as one of the simplest machines in all computer science. It is fundamentally the idea of having many very simple entities acting in parallel that make local decisions based on local state. It has been observed that very complex behavior can emerge from large groups of these entities. See John Conway’s game of life https://playgameoflife.com/ for the classic (and fun) example of a Cellular Automaton.
In computing, to keep with the theme of simple entities, we can even choose the simplest data representation – there are only two states, which can be represented as 1 or 0, or black and white in the illustrated pattern below. Each is a single cell or square in a row.
Time moves with ticks, and with each tick each cell is looking at its left neighbor, itself and its right neighbor (so each cell is only examining the area near itself – local state). Based on the pattern of these three bits or squares, a fixed rule produces the next state of this cell – local modifications. Applying the same rule to each cell gives a whole new pattern which is represented by a line below, and it can grow infinitely, producing another new pattern.
This describes a one-dimensional cellular automaton in a full picture. There is no memory and no processor, just cells, neighbors and a rule.
What Is A Rule In Cellular Automata
A rule is simply a truth table, a short list with the answers to a given sequence above. The current pattern describes what kind of new center cell will appear below. Just like demonstrated above, it shows the very basics of how a simple sequence can produce a new state.
However this is just the simplest example to grasp where we are heading. Depending on how much a cell (square) is allowed to see, there can be many more rules. A cell that reads three bits, its two neighbors and itself, has eight possible patterns. With these 1 or 0 states, or yes or no answers, there can be exactly 256 possible rules.
It is too small a variety of possibilities. But if we add one more cell to the existing three, the possibilities jump to 65,536 rules, and we can have as many connected cells as needed to produce different results each and every time.
To better understand this model and why it is fascinating, it is good to use Stephen Wolfram’s catalogue of the 256 three-input rules from 1983, which are numbered from 0 to 255 by reading their eight answers as a binary number, and called Rule 30.
Rule 30
The name of Rule 30 comes from the eight patterns: their binary string, 00011110, equals the number 30. You can start with a single black cell on a white strip and run Cellular Automaton Rule 30, which will produce a different pattern below. There is no existing formula to predict what comes next other than running the machine. The outcome looks totally random, even though every step of it is deterministic, and represents chaotic behavior.
Back in 2019 Stephen Wolfram announced $30,000 in prizes to whoever can answer basic questions about Rule 30. Does the center column ever become periodic? Or do black and white cells appear equally often in the long run? The rule has resisted analysis since its introduction in 1983, there are no answers up to today, and no one has claimed the prize.
Nobody can prove why, but the center column of that triangle, read downward as a stream of bits, behaves like a fair coin flip. In fact it behaves so well that for many years finite-size Rule 30 systems were the source of random numbers in the Wolfram Language, the system behind Mathematica, and no legitimate non-randomness was ever found.
Upcoming NexaPoW 2.0
The upcoming NexaPoW 2.0 mining algorithm will use a Cellular Automaton grid as its computational core. In a textbook automaton every cell follows the same rule, and we can call it a gift to CPUs and GPUs because they can process an entire row with a very few machine instructions.
In Nexa’s design every single cell will have its own rule, its own properties and truth table, and it will be drawn from a curated set with strong cryptographic properties. Instead of a single rule there will be many rules which will work together. In the case of a CPU or GPU, each unit of computation is massively overpowered for the job. Why have the ability to add, multiply, divide, execute if statements, or jump if all you are doing is converting one bit pattern to another? This means a lot of the space on the chip – the actual silicon is unused. But those operations are still on-chip, so the chip cannot run nearly as many cells in parallel.
But in the case of an FPGA its fabric is already designed and made of literally small programmable truth tables, so it costs a single fundamental FPGA logic cell to implement one cell..
In analogy, consider an army of dedicated ants carrying a bunch of crumbs away, or you doing the job. But you can’t use all of a human’s size and abilities; you are stuck using only a single pair of tweezers. Who would win? Who is more efficient?
The beautiful part of it is that the new mining algorithm won’t be reproducible in ASICs, which tend to centralize the mining. These rules will change themselves at regular intervals, and this timelapse will be below the required time to produce an ASIC, effectively decentralizing the mining ground to the broad community. To stay open and transparent, the new rules will be generated from the last epoch block hash, which will only be mined and known just before the new epoch starts.
However, people will be able to mine with GPUs, especially at first. We cannot know exactly how competitive GPUs will be compared to FPGAs, although our estimates put FPGAs as the winner. It is a complex topic because the FPGAs have (say) 5 to 6 figures of slower parallel automata, GPUs have 4 to 5 (and growing rapidly) figures of fast parallel processing, and they will be able to handle the non-cellular portions (the Schnorr signatures) of our PoW algorithm much more quickly.
This design will renew incentives with benefits to the network’s scalability and decentralization. The operations inside the hash are the same operations a node needs to verify blocks. An FPGA which will mine Nexa will also have the circuits for Schnorr verification, (in the future) UTXO lookups and transaction validation, resulting in an FPGA that can handle the core blockchain updates massively and in parallel. This was designed on purpose and targeted to FPGAs to align the algorithms of mining and signature verification, effectively converging mining and node hardware to an energy efficient platform that, unlike ASICs, can be upgraded as new features are added to the blockchain.
To Wrap Up
The Cellular Automaton is just a part of the new NexaPoW 2.0 version that will enable the algorithm to change all the time. The basics are very simple, however combined with the protocol’s other cryptography it becomes a crucial part for dynamic changes. This article was designed to give you a feeling of what Cellular Automata are, and if you want to learn more details about the NexaPoW 2.0 algorithm, check the sources down below.
Sources
-
Why We’re Redesigning Nexa’s Mining Algorithm for FPGA: Peter R. Rizun on X: "https://t.co/oRM5ONQSJ5" / X
-
A Cellular Automaton Game invented by John Conway: https://playgameoflife.com/
-
Rule 30: Rule 30 - Wikipedia
-
Wolfram prizes: https://writings.stephenwolfram.com/2019/10/announcing-the-rule-30-prizes/
NexaPoW 2.0 and its dynamic Cellular Automaton approach look really interesting. Excited to see how this helps improve mining decentralization and ASIC resistance. 