* Arista [2021a] Arista (2021a) 7170 Series Programmable Data Center Switches Data Sheet. URL https://www.arista.com/assets/data/pdf/Datasheets/7170-Datasheet.pdf
  * Arista [2021b] Arista (2021b) Arista 100G Transceivers and Cables. URL https://www.arista.com/assets/data/pdf/Arista100G_TC_QA.pdf
  * Arista 7170 Price [2022] Arista 7170 Price (2022) Arista 7170 Price - Arista Price List 2022. URL https://itprice.com/arista-price-list/7170.html
  * Arista 7170 Price [2023] Arista 7170 Price (2023) DCS-7170-64C. URL https://it-market.com/en/components/newcomers/arista/dcs-7170-64c
  * Arévalo et al [2017] Arévalo GV, Hincapié RC, Gaudino R (2017) Optimization of multiple pon deployment costs and comparison between gpon, xgpon, ngpon2 and udwdm pon. Optical Switching and Networking 25:80–90. https://doi.org/10.1016/j.osn.2017.03.003, URL https://www.sciencedirect.com/science/article/pii/S1573427716300522
  * Ballani et al [2020] Ballani H, Costa P, Behrendt R, et al (2020) Sirius: A Flat Datacenter Network with Nanosecond Optical Switching. In: SIGCOMM, ACM, URL https://www.microsoft.com/en-us/research/publication/sirius-a-flat-datacenter-network-with-nanosecond-optical-switching/
  * Benes [1965] Benes VE (1965) Mathematical theory of connecting networks and telephone traffic / V.E. Benes. Academic Press New York
  * Benjamin and Zervas [2020] Benjamin JL, Zervas G (2020) Scaling pulse data center network architecture and scheduling optical circuits in sub-microseconds. In: 2020 Optical Fiber Communications Conference and Exhibition (OFC), pp 1–3
  * Benjamin et al [2020] Benjamin JL, Gerard T, Lavery D, et al (2020) PULSE: Optical Circuit Switched Data Center Architecture Operating at Nanosecond Timescales. J Lightwave Technol 38(18):4906–4921. URL http://jlt.osa.org/abstract.cfm?URI=jlt-38-18-4906
  * Benjamin et al [2022] Benjamin JL, Ottino A, Parsonson CWF, et al (2022) Traffic tolerance of nanosecond scheduling on optical circuit switched data center network. In: 2022 Optical Fiber Communications Conference and Exhibition (OFC), pp 1–3
  * Bernauer and Kashinkunti [2021] Bernauer J, Kashinkunti P (2021) Accelerating AI at-scale with Selene DGXA100 SuperPOD and Lustre Parallel Filesystem Storage. URL https://wiki.lustre.org/images/3/30/LUG2021-Accelerating_AI_at_Scale-Bernauer-Kashinkunti.pdf
  * Bruck et al [1997] Bruck J, Ho CT, Kipnis S, et al (1997) Efficient Algorithms for All-to-All Communications in Multiport Message-Passing Systems. IEEE Transactions on Parallel and Distributed Systems 8(11):1143–1156. 10.1109/71.642949
  * Centre [2021] Centre CSNS (2021) Piz Daint. URL https://www.cscs.ch/computers/piz-daint/
  * Chen et al [2016] Chen T, Xu B, Zhang C, et al (2016) Training deep nets with sublinear memory cost. 10.48550/ARXIV.1604.06174, URL https://arxiv.org/abs/1604.06174
  * Chunduri et al [2018] Chunduri S, Parker S, Balaji P, et al (2018) Characterization of MPI Usage on a Production Supercomputer. In: SC18: International Conference for High Performance Computing, Networking, Storage and Analysis, pp 386–400, 10.1109/SC.2018.00033
  * Clark and et al. [2018] Clark K, et al. (2018) Sub-Nanosecond Clock and Data Recovery in an Optically-Switched Data Centre Network. In: 2018 European Conference on Optical Communication (ECOC), pp 1–3
  * Clarke et al [1994] Clarke L, Glendinning I, Hempel R (1994) The MPI Message Passing Interface Standard. In: Decker KM, Rehmann RM (eds) Programming Environments for Massively Parallel Distributed Systems. Birkhäuser Basel, Basel, pp 213–218
  * Day [2021] Day TA (2021) URL https://www.youtube.com/watch?v=j0z4FweCy4M
  * DELL Technologies [2022] DELL Technologies (2022) Dell Power Edge System. URL https://www.dell.com/en-us/work/shop/dell-NVIDIA-nvlink-for-quadro-rtx6000-and-rtx8000/apd/490-bfhk/graphic-video-cards#polaris-pd
  * Fedus et al [2021] Fedus W, Zoph B, Shazeer N (2021) Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. 10.48550/ARXIV.2101.03961, URL https://arxiv.org/abs/2101.03961
  * Fiberworks [2021] Fiberworks (2021) QSFP28 100G Copper Twinax cable (DAC). URL https://www.fiberworks.net/fiberworks-as/qsfp28-dac/qsfp28-100g-copper-twinax-cable-dac-passive-100gbase-cr4
  * Figueiredo et al [2015] Figueiredo RC, Ribeiro NS, Ribeiro AMO, et al (2015) Hundred-Picoseconds Electro-Optical Switching With Semiconductor Optical Amplifiers Using Multi-Impulse Step Injection Current. Journal of Lightwave Technology 33(1):69–77. 10.1109/JLT.2014.2372893
  * Fu et al [2016] Fu H, Liao J, Yang J, et al (2016) The sunway taihulight supercomputer: system and applications. Science China Information Sciences 59(7):072,001. 10.1007/s11432-016-5588-7, URL https://doi.org/10.1007/s11432-016-5588-7
  * Funnell et al [2016] Funnell A, Benjamin J, Ballani H, et al (2016) High port count hybrid wavelength switched TDMA (WS-TDMA) optical switch for data centers. In: 2016 Optical Fiber Communications Conference and Exhibition (OFC), pp 1–3
  * Grobe and Eiselt [2013] Grobe K, Eiselt M (2013) Wavelength division multiplexing: a practical engineering guide. John Wiley & Sons
  * Habana Labs Ltd [2019] Habana Labs Ltd (2019) Gaudi Training Platform Paper White. URL https://habana.ai/wp-content/uploads/2019/06/Habana-Gaudi-Training-Platform-whitepaper.pdf
  * Hemsoth [2016] Hemsoth N (2016) Measuring Top Supercomputer Performance in the Real World. URL https://www.nextplatform.com/2016/06/21/measuring-top-supercomputer-performance-real-world/
  * Inggs et al [2015] Inggs M, Sandenbergh J, Lewis S (2015) Investigation of white rabbit for synchronization and timing of netted radar. In: 2015 IEEE Radar Conference, pp 214–217, 10.1109/RadarConf.2015.7411882
  * Jacobs et al [1991] Jacobs RA, Jordan MI, Nowlan SJ, et al (1991) Adaptive mixtures of local experts. Neural computation 3(1):79–87
  * Jeon et al [2019] Jeon M, Venkataraman S, Phanishayee A, et al (2019) Analysis of large-scale multi-tenant GPU clusters for DNN training workloads. In: 2019 USENIX Annual Technical Conference (USENIX ATC 19). USENIX Association, Renton, WA, pp 947–960, URL https://www.usenix.org/conference/atc19/presentation/jeon
  * Kaplan et al [2020] Kaplan J, McCandlish S, Henighan T, et al (2020) Scaling laws for neural language models. 10.48550/ARXIV.2001.08361, URL https://arxiv.org/abs/2001.08361
  * Khani et al [2020] Khani M, Ghobadi M, Alizadeh M, et al (2020) TeraRack: A Tbps Rack for Machine Learning Training. In: TeraRack: A Tbps Rack for Machine Learning Training
  * Khani et al [2021] Khani M, Ghobadi M, Alizadeh M, et al (2021) SiP-ML: High-Bandwidth Optical Network Interconnects for Machine Learning Training. In: Proceedings of the 2021 ACM SIGCOMM 2021 Conference. Association for Computing Machinery, New York, NY, USA, SIGCOMM ’21, p 657–675, 10.1145/3452296.3472900, URL https://doi.org/10.1145/3452296.3472900
  * Koos et al [2016] Koos C, Leuthold J, Freude W, et al (2016) Silicon-Organic Hybrid (SOH) and Plasmonic-Organic Hybrid (POH) Integration. Journal of Lightwave Technology 34(2):256–268. 10.1109/JLT.2015.2499763
  * Li et al [2020] Li A, Song S, Chen J, et al (2020) Evaluating modern gpu interconnect: Pcie, nvlink, nv-sli, nvswitch and gpudirect. IEEE Transactions on Parallel and Distributed Systems 31(01):94–110. 10.1109/TPDS.2019.2928289
  * Medhi and Ramasamy [2018] Medhi D, Ramasamy K (2018) Chapter 12 - routing and traffic engineering in data center networks. In: Medhi D, Ramasamy K (eds) Network Routing (Second Edition), second edition edn. The Morgan Kaufmann Series in Networking, Morgan Kaufmann, Boston, p 396–422, https://doi.org/10.1016/B978-0-12-800737-2.00014-4, URL https://www.sciencedirect.com/science/article/pii/B9780128007372000144
  * Mellanox Technologies. [2021] Mellanox Technologies. (2021) Introducing 200G HDR InfiniBand Solutions. URL https://www.mellanox.com/pdf/whitepapers/WP_Introducing_200G_HDR_InfiniBand_Solutions.pdf
  * Mellanox Technologies [2021] Mellanox Technologies (2021) QM8790 Mellanox Quantum™ HDR Edge Switch. URL https://www.mellanox.com/related-docs/prod_ib_switch_systems/PB_QM8790.pdf
  * Micikevicius et al [2017] Micikevicius P, Narang S, Alben J, et al (2017) Mixed precision training. 10.48550/ARXIV.1710.03740, URL https://arxiv.org/abs/1710.03740
  * Mikami et al [2019] Mikami H, Suganuma H, U-chupala P, et al (2019) Massively distributed sgd: Imagenet/resnet-50 training in a flash. 1811.05233
  * Moralis‐Pegios et al [2021] Moralis‐Pegios M, Pitris S, Mitsolidou C, et al (2021) Silicon circuits for chip‐to‐chip communications in multi‐socket server board interconnects. IET Optoelectronics
  * Mudigere et al [2022] Mudigere D, Hao Y, Huang J, et al (2022) Software-hardware co-design for fast and scalable training of deep learning recommendation models. 2104.05158
  * Naumov et al [2019] Naumov M, Mudigere D, Shi HJM, et al (2019) Deep learning recommendation model for personalization and recommendation systems. 1906.00091
  * NVIDIA [2021] NVIDIA (2021) 200Gb/s HDR QSFP56 MMF Active Optical Cable. URL https://www.mellanox.com/related-docs/prod_cables/PB_MFS1S00-HxxxE_200Gbps_QSFP56_AOC.pdf
  * NVIDIA Corporation [2017] NVIDIA Corporation (2017) NVIDIA DGX-1 With Tesla V100 System Architecture: The Fastest Platform for Deep Learning. URL https://images.NVIDIA.com/content/pdf/dgx1-v100-system-architecture-whitepaper.pdf
  * NVIDIA Corporation [2018] NVIDIA Corporation (2018) NVIDIA NVSWITCH: The World’s Highest-Bandwidth On-Node Switch. URL https://images.NVIDIA.com/content/pdf/nvswitch-technical-overview.pdf
  * NVIDIA Corporation [2020] NVIDIA Corporation (2020) NVIDIA A100 Tensor Core GPU Architecture: unprecedented acceleration at every scale. URL https://images.NVIDIA.com/aem-dam/en-zz/Solutions/data-center/NVIDIA-ampere-architecture-whitepaper.pdf
  * NVIDIA Corporation [2021a] NVIDIA Corporation (2021a) NVIDIA DGX SuperPOD: Scalable Infrastructure for AI Leadership, Reference Architecture, Featuring NVIDIA DGX A100 Systems. Version 15. URL https://images.NVIDIA.com/aem-dam/Solutions/Data-Center/gated-resources/NVIDIA-dgx-superpod-a100.pdf
  * NVIDIA Corporation [2021b] NVIDIA Corporation (2021b) NVIDIA MQM8790-HS2F Quantum HDR InfiniBand Switch Cost. URL https://store.NVIDIA.com/en-us/networking/store/product/MQM8790-HS2F/NVIDIAMQM8790HS2FQuantumHDRInfiniBandSwitch/
  * NVIDIA Corporation: Optimized primitives for inter-GPU communication. [2022] NVIDIA Corporation: Optimized primitives for inter-GPU communication. (2022) NCCL: Optimized primitives for inter-GPU communication. URL https://github.com/NVIDIA/nccl
  * NVIDIA Inc [2022] NVIDIA Inc (2022) NCCL Tests. URL https://github.com/NVIDIA/nccl-tests
  * Ottino [2022a] Ottino A (2022a) Data for figures and additional analysis for RAMP. UCL Research Data Repository 10.5522/04/19590973.v1, URL https://rdr.ucl.ac.uk/articles/dataset/Data_for_figures_and_additional_analysis_for_RAMP/19590973
  * Ottino [2022b] Ottino A (2022b) dlrm_part. URL https://gitlab.ee.ucl.ac.uk/zceeaot/dlrm_part
  * Ottino [2022c] Ottino A (2022c) Mp transformer encoder. URL https://gitlab.ee.ucl.ac.uk/zceeaot/partitioned_encoder_library
  * Ottino [2022d] Ottino A (2022d) Profiled DDL RAMP. UCL Research Data Repository 10.5522/04/19590799.v1, URL https://rdr.ucl.ac.uk/articles/dataset/Profiled_DDL_RAMP/19590799
  * Ottino [2022e] Ottino A (2022e) Profiled DLRM RAMP. UCL Research Data Repository 10.5522/04/20015678.v1, URL https://rdr.ucl.ac.uk/articles/dataset/Profiled_DLRM_RAMP/20015678
  * Ottino [2022f] Ottino A (2022f) RAMP-Public. URL https://gitlab.ee.ucl.ac.uk/zceeaot/ramp-public
  * Oyama et al [2021] Oyama Y, Maruyama N, Dryden N, et al (2021) The case for strong scaling in deep learning: Training large 3d cnns with hybrid parallelism. IEEE Transactions on Parallel and Distributed Systems 32(7):1641–1652. 10.1109/TPDS.2020.3047974
  * Parsonson et al [2020] Parsonson CWF, Shabka Z, Chlupka WK, et al (2020) Optimal control of soas with artificial intelligence for sub-nanosecond optical switching. Journal of Lightwave Technology 38(20):5563–5573. 10.1109/JLT.2020.3004645
  * Patarasuk and Yuan [2009] Patarasuk P, Yuan X (2009) Bandwidth Optimal All-Reduce Algorithms for Clusters of Workstations. J Parallel Distrib Comput 69(2):117–124. 10.1016/j.jpdc.2008.09.002, URL https://doi.org/10.1016/j.jpdc.2008.09.002
  * Rabenseifner [2004] Rabenseifner R (2004) Optimization of collective reduction operations. In: Bubak M, van Albada GD, Sloot PMA, et al (eds) Computational Science - ICCS 2004\. Springer Berlin Heidelberg, Berlin, Heidelberg, pp 1–9
  * Ren et al [2021] Ren J, Rajbhandari S, Aminabadi RY, et al (2021) Zero-offload: Democratizing billion-scale model training. 10.48550/ARXIV.2101.06840, URL https://arxiv.org/abs/2101.06840
  * Shallue et al [2018] Shallue CJ, Lee J, Antognini J, et al (2018) Measuring the effects of data parallelism on neural network training. arXiv preprint arXiv:181103600
  * Shoeybi et al [2019] Shoeybi M, Patwary M, Puri R, et al (2019) Megatron-lm: Training multi-billion parameter language models using model parallelism. 10.48550/ARXIV.1909.08053, URL https://arxiv.org/abs/1909.08053
  * Summit [2021] Summit (2021) URL https://www.olcf.ornl.gov/summit/
  * Tao Wang [2021] Tao Wang AS (2021) Google wins MLPerf benchmarks with TPU v4. URL https://cloud.google.com/blog/products/ai-machine-learning/google-wins-mlperf-benchmarks-with-tpu-v4/
  * Taubenblatt [2019] Taubenblatt M (2019) “ECOC, Workshop on Optical Interconnects for Data Centers”
  * Thakur et al [2005] Thakur R, Rabenseifner R, Gropp W (2005) Optimization of Collective Communication Operations in MPICH. Int J High Perform Comput Appl 19(1):49–66. 10.1177/1094342005051521, URL https://doi.org/10.1177/1094342005051521
  * Thomas et al [2021] Thomas G, Christopher P, Zacharaya S, et al (2021) AI-optimised tuneable sources for bandwidth-scalable, sub-nanosecond wavelength switching. Opt Express 29(7):11,221–11,242. 10.1364/OE.417272, URL http://www.osapublishing.org/oe/abstract.cfm?URI=oe-29-7-11221
  * Ueno and Yokota [2019] Ueno Y, Yokota R (2019) Exhaustive Study of Hierarchical AllReduce Patterns for Large Messages Between GPUs. In: 2019 19th IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGRID), pp 430–439, 10.1109/CCGRID.2019.00057
  * Vaswani et al [2017] Vaswani A, Shazeer N, Parmar N, et al (2017) Attention is all you need. 10.48550/ARXIV.1706.03762, URL https://arxiv.org/abs/1706.03762
  * Wang et al [2022] Wang W, Khazraee M, Zhong Z, et al (2022) Topoopt: Optimizing the network topology for distributed dnn training. 10.48550/ARXIV.2202.00433, URL https://arxiv.org/abs/2202.00433
  * Wiggers [2021] Wiggers K (2021) Microsoft and Nvidia team up to train one of the world’s largest language models. URL https://venturebeat.com/ai/microsoft-and-nvidia-team-up-to-train-one-of-the-worlds-largest-language-models/
  * Williams et al [2009] Williams S, Waterman A, Patterson D (2009) Roofline: An Insightful Visual Performance Model for Multicore Architectures. Commun ACM 52(4):65–76. 10.1145/1498765.1498785, URL https://doi.org/10.1145/1498765.1498785
  * Williamson et al [2020] Williamson IAD, Minkov M, Dutt A, et al (2020) Integrated Nonreciprocal Photonic Devices With Dynamic Modulation. Proceedings of the IEEE 108(10):1759–1784. 10.1109/JPROC.2020.3023959
  * Wolf et al [2018] Wolf S, Zwickel H, Kieninger C, et al (2018) Coherent modulation up to 100 GBd 16QAM using silicon-organic hybrid (SOH) devices. Opt Express 26(1):220–232. 10.1364/OE.26.000220, URL http://www.osapublishing.org/oe/abstract.cfm?URI=oe-26-1-220
  * Yoshimatsu et al [2012] Yoshimatsu T, Nada M, Oguma M, et al (2012) Compact and high-sensitivity 100-gb/s (4 × 25 gb/s) apd-rosa with a lan-wdm plc demultiplexer. Opt Express 20(26):B393–B398. 10.1364/OE.20.00B393, URL http://opg.optica.org/oe/abstract.cfm?URI=oe-20-26-B393
  * Zervas and Benjamin [2019] Zervas G, Benjamin JL (2019) Pulse: Sub-microsecond optical circuit switched data center network. In: 2019 24th OptoElectronics and Communications Conference (OECC) and 2019 International Conference on Photonics in Switching and Computing (PSC), pp 1–3, 10.23919/PS.2019.8817674
  * Zhu et al [2021] Zhu Q, Luo H, Yang C, et al (2021) Enabling and scaling the hpcg benchmark on the newest generation sunway supercomputer with 42 million heterogeneous cores. In: Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis. Association for Computing Machinery, New York, NY, USA, SC ’21, 10.1145/3458817.3476158, URL https://doi.org/10.1145/3458817.3476158


# Challenges of Proof-of-Useful-Work (PoUW)

Felix Hoffmann
Johann Wolfgang Goethe-Universität Frankfurt am Main
<EMAIL_ADDRESS>
## I. Introduction

Traditional proof-of-work cryptocurrencies have been widely criticized for
using up lots of energy in order to run and secure the underlying blockchain.
In the past few years, there has been done research with the goal of replacing
repeated hash operations with useful work. Notable projects such as Primecoin
[Kin13], Coinami [IOG+16] and CoinAI [BS19] use search for certain kinds of
prime number chains, multiple sequence alignment of protein sequences or
training of deep learning models as useful work consensus algorithms. In order
to give an overview of the challenges these projects have to overcome, the
following part gives an outline of important properties that hash-based PoW
solutions have.

## II. Properties of hash-based PoW

Hash-based PoW consensus algorithms use cryptographically secure hash
functions such as SHA256 or KECCAK256 in order generate hex strings of fixed
size. The proof-of-work hash puzzle consists of finding a result that is
smaller than a given number which defines the difficulty of the problem. Hash
functions are one-way functions which also allow for quick verification of a
proposed solution’s validity. If a hash function is not considered to be
broken, there is no known way to manipulate the hash function’s input to
influence its output in a preferred direction. Therefore, the nodes of the
blockchain have to brute-force different inputs until they solve the hash
puzzle by luck. This leads to an arms race between miners, in which more
hardware is acquired to increase ones hash rate. For non-ASIC-resistant
cryptocurrencies such as Bitcoin, specialized hardware with the sole purpose
of efficiently mining can be used.
In the following, advantageous properties of hash-based PoW algorithms are
outlined and it is described why these properties are useful in the context of
blockchains.

### i. Block sensitivity & non re-usability

In order to prevent the re-usage of existing proofs-of-work, it is necessary
to bind the validity of a PoW to the block it validates. This means that the
computational work has to factor in information that is not known beforehand
to prevent pre-calculation of future blocks. A common strategy to retain the
block sensitivity property is to require the hash of the previous block to be
used as part of the hash function’s input for the PoW of the next block. Since
the hash of the previous block is only known when it is successfully added to
the blockchain, this makes it infeasible to pre-calculate future blocks as
long as the hash function used is not fundamentally broken. However, there
exists an attack called Selfish Mining in which a group of malicious miners
that solved the current hash puzzle do not broadcast their solution to all
miners but instead continue mining additional blocks in secret until they
decide to publish a long chain of new blocks. Since common blockchain
implementations obey the longest chain rule, all other valid blocks that were
mined by other nodes during this time will be discarded if the public state of
the chain is shorter than the secretly mined chain. Selfish Miners always run
the risk of not being able to keep up with the speed of the chain they compete
against, in which case block rewards that could have been collected by Selfish
Miners are lost. As a result, Selfish Mining strategies are only feasible if
large amounts of a blockchain network’s computational power is controlled by
an organized group of miners.

### ii. Adjustable problem hardness

The difficulty of the PoW needs to be adjustable. This property is required so
that block intervals can be regulated (e.g. Bitcoin’s average block time is
around 10 minutes [Nak08]). The goal is to both counteract
inflation111Additionally, in the case of Bitcoin, block rewards are decreased
over time to further prevent inflation. (miners of blocks are financially
compensated for their work) and to guarantee a stable transaction throughput.
Problem hardness commonly is dynamically adjusted over time depending on the
current total hash rate of the network. It should be noted that the difficulty
of PoW problems need to have a lower bound: Trivial problems that can be
solved instantly are not suitable for a consensus algorithm because then
miners are incentivized to mine empty blocks instead of filling them with
pending transactions. Using hash-based PoW approaches has the advantage that
the difficulty of problems can trivially be adjusted in both directions by
lowering/increasing the required upper bound of accepted hash values.

Another property of hash-based PoW is that miners with limited computational
power have a non-zero chance of quickly solving the hash puzzle by luck. If an
entity with computational power $\alpha$ would always lose against entities
with computational power $\beta>\alpha$, then the blockchain would be dictated
by the single largest group of miners, which as a result would disincentivize
miners from participating in the blockchain. This would be the death of the
blockchain since known attacks like the 51% attack would become feasible.
Therefore, it is not only important that in the long term a miner earns block
rewards that are proportional to that miners hash rate contribution to the
overall network, but also that any miner has a non-zero chance to successfully
solve the proof-of-work puzzle.

### iii. Fast verification

In order to be able to find consensus and be protected from spam attacks,
miners need to be able to quickly verify the validity of blocks proposed by
other miners. Therefore, it is crucial that the proof-of-work can efficiently
be verified in reasonable time without demanding excessive computational
resources. The need for fast verification mechanisms is the main factor why
hash functions are commonly used in proof-of-work algorithms. Executing one
SHA256 or KECCAK256 function call on a small input barely uses any
computational power, since the main difficulty is finding an input for such a
function that produces the required output. Thus, the term one-way function.

### iv. Problem is parallelizable

In order to make efficient use of existing hardware, it is preferred to use
proof-of-work problems that can be parallelized. For instance, finding hash
function outputs that have a certain of amount of leading zeroes is called an
embarrassingly parallel problem since there is no need for communication
between threads.
Further, parallelizable problems enable the formation of mining pools:
Depending on the difficulty of the hash puzzle, low hash rate miners might
have a probability close to zero to mine a new block alone. By joining
existing mining pools in which computational power of multiple entities is
combined and block rewards are shared proportionally to the provided hash rate
of every pool member, weak miners can collect small amounts of financial
compensation in regular intervals.
All in all, while a proof-of-work consensus algorithm does not necessarily
have to be parallelizable, this property makes mining more accessible for a
wider range of participants which positively affects network diversity and
strengthens the blockchain’s overall security.

## III. Proof-of-Useful-Work (PoUW)

This section consists of two parts: In the first part, existing PoUW
approaches and ideas are briefly introduced. In the second part, they are
analyzed with regards to how the properties of hash-based PoW consensus
algorithms are retained and which issues might occur.
Even though exotic consensus algorithm classes like Proof-of-Storage can be
considered useful, the focus in this publication is on computationally-heavy
PoUW which shares lots of similarities with hash-based PoW.

### i. Primecoin

Primecoin is a PoUW cryptocurrency that was launched in 2013 by Sunny
King.[Kin13]
Its PoUW consists of finding certain types of prime number chains, so-called
Cunningham and bi-twin chains. Cunningham chains are a series of prime numbers
that nearly double each time. In mathematical terms, a prime chain of length
$n\in\mathbb{N}$ must fulfill

$p_{i+1}=2p_{i}+1$ (1)

to be considered a first order chain or

$p_{i+1}=2p_{i}-1$ (2)

to be considered a second order chain for all $1\leq i<n$. For instance,
$\\{41,83,167\\}$ is a first order chain of length $n=3$ and $\\{7,13\\}$ is a
second order chain of length $n=2$.
In addition to Cunningham chains, the third type of chain that Primecoin
allows as proof-of-work are bi-twin chains. These are prime chains that
consist of a strict combination of first and second order Cunningham primes.
The mathematical definition of a bi-twin chain of length $k+1$ is the sequence
$\\{n-1,n+1,2n-1,2n+1,2^{2}n-1,2^{2}n+1,...,2^{k}n-1,2^{k}n+1\\}$.
For instance, choosing $n=6$ leads to $\\{5,7,11,13\\}$ which is a bi-twin
chain of length 2 that consists of 4 prime numbers.

As of writing this publication, a Primecoin is traded for about $0.04 and the
currency’s total market capitalization is around $1.7 million. [Coi22] The
success of Primecoin can be seen as evidence that PoUW is a viable concept
with real-world applications.

### ii. Coinami

In 2016, a theoretical proposal of a mediator interface for a volunteer grid
similar to BOINC middleware that can be connected to a cryptocurrency was
published and named Coinami. [IOG+16] The PoUW of Coinami is built on DNA
sequence alignment (HTS read mapping in particular) and aims to generate and
analyze huge datasets of disease signatures which can help us to gain a better
understanding of diseases such as different cancer variants.
The authors of Coinami describe their approach as a three-level multi-centric
system which consists of a root authority, sub-authorities and miners. Miners
download problem sets from sub-authorities, map HTS reads to a reference
genome and send the results back to sub-authorities for verification. Sub-
authorities are certified by the root authority. [IOG+16]

As a result, this approach can be seen as a hybrid of Proof-of-Authority (PoA)
and Proof-of-Useful-Work (PoUW) consensus algorithms. As of writing, while
Coinami does have a prototype implementation on Github [Coi16], there
currently exists no cryptocurrency that is connected to this academic
proposal.

### iii. CoinAI

In 2019, a theoretical proposal of PoUW consensus that is built on training
and hyperparameter optimization of deep learning models was published and
named CoinAI. [BS19]
The goal of CoinAI is to secure a blockchain-based cryptocurrency with a
consensus algorithm that both secures the underlying blockchain while also
producing deep learning models that solve real-world problems. The proposed
proof-of-work consists of training a model that passes a certain performance
threshold in order for it to be considered valid. In addition to the training
of deep learning models, the CoinAI proposal features another financial
incentive to participate in the blockchain: Nodes can rent out available hard
drive storage to provide distributed storage for the resulting deep learning
models of the blockchain. [BS19]

Thus, CoinAI’s approach can be described as a hybrid of Proof-of-Useful-Work
(PoUW) and Proof-of-Storage (PoS). As of writing, CoinAI remains an academic
proposal that has not yet been implemented to secure a tradeable
cryptocurrency.

### Analysis of PoUW approaches

#### PoUW: Non re-usability

To prevent future calculation and re-usability of proofs-of-work, a given
problem must involve information or parameters that can not reliably be
guessed beforehand. All nodes must be able to agree on how these parameters
are to be adjusted over time so that the problem sets are adjusted over time
and it can be decided whether a given proof-of-work is valid for some time
interval. A common approach here is to involve the hash of the previous block
as a parameter as part of the next problem. However, since this directly
influences the result of the calculations, it must be decided on a case-per-
case basis whether the resulting information can still be considered to be
useful.
If incorporating hashes into the calculations is not possible, then another
approach must be found to bind the PoUW to a given period in time. Relying on
an external (as in information taken from outside the blockchain) source that
continuously publishes new information over time is not desirable, since this
approach leads to a high degree of centralization which not only opposes core
principles of a decentralized blockchain but which also has the potential to
create security issues and conflicts of interest, especially if the underlying
blockchain is connected to a cryptocurrency.

$\triangleright$ Primecoin retains the property of block sensitivity by
requiring the origin of the prime chains to be divisible by the hash of the
previous block. In this case, the resulting quotient is defined as a so-called
PoW certificate. [Kin13] This guarantees that pre-calculation of future blocks
is not a viable strategy as long as there is no scientific breakthrough in
efficiently calculating certain chains of large primes.

$\triangleright$ The theoretical Coinami approach tries to evade re-usability
and pre-calculation problems by relying on an authority approach, in which
miners must request tasks from (sub)-authority nodes. Since miners can not
guess which task they might be given next, pre-calculation of future blocks is
not feasible. Since sub-authorities know which problems have already been
given out, re-usability is not an issue either. The main issue of this
solution can be seen as a high degree of centralization which forces miners to
trust any (sub)-authority.

$\triangleright$ The CoinAI proposal concatenates information such as previous
block hash, a random number called nonce and a list of pending transactions
which then is hashed. This hash result then is used to determine the initial
hyperparameter structure of a deep learning architecture which must be trained
until it satisfies performance requirements. An issue that potentially arises
with this approach is that if the goal is to produce useful deep learning
models, then starting the training with an inadequate initial hyperparameter
configuration affects the amount of training required to reach acceptable
model performance which can be seen as wasted energy. Assuming that the space
of all allowed hyperparameter configurations is limited to prevent this from
happening, the next problem that might arise is that now hash-to-
hyperparameter-configuration mapping collisions are bound to happen more
frequently, which in this case means that multiple hashes lead to the same
initial hyperparameter configuration which as a result could make pre-
calculation strategies feasible.

#### PoUW: Adjustable hardness

Since miners might join or leave the network of nodes at any time, the
blockchain’s total computational power fluctuates over time. In order to
provide regular block intervals which in the case of a cryptocurrency is
necessary to stabilize the transaction throughput, there must be consensus
between nodes with respect to how the difficulty of problems is to be adjusted
over time. Hash-based PoW approaches control the problem difficulty by
dynamically adjusting the amount of leading zeroes that the resulting hash
must have in order to be valid depending on the current hash rate of the
network. Increasing the amount of required leading zeroes by just one
increases the difficulty of the hash puzzle exponentially, which is why softer
variations of this approach can be used (such as e.g. amount of leading digits
smaller than eight) to provide a more fine-grained control of the problem
difficulty.
For useful work approaches, it needs to be decided on a case-per-case basis
how the hardness of a given problem can dynamically be adjusted without
jeopardizing usefulness of results.

$\triangleright$ In the context of Primecoin, two intuitive mechanics to
control problem difficulty come to mind: First of all, the size of prime
numbers that start a chain could be increased over time. However, the prime
number theorem states that

$\lim\limits_{x\to\infty}\frac{\pi(x)}{\frac{x}{\ln(x)}}=1$ (3)

with $\pi(x)$ being the so-called prime-counting function. The for our context
useful interpretation of this equation is that the prime density approaches
zero, which means that the proof-of-work difficulty over time might become too
high to sustain stable transaction throughput long-term.
The second intuitive approach that comes to mind is to dynamically adjust the
required length of valid prime number chains to control the problem
difficulty. This is the approach Primecoin takes: Given a prime chain of some
length, Primecoin dynamically adjusts its Fermat primality test which results
in a relatively linear continuous difficulty function (as opposed to the non-
linear difficulty function of the first approach) that is claimed to be
accurate enough to adjust the problem hardness appropriately over time.
[Kin13]

$\triangleright$ The Coinami authors have not yet defined how the difficulty
of the DNA sequence alignment problems can be dynamically adjusted over time.
The issue here is that the network must rely on an external source for HTS
data and simply increasing the size of assignments potentially leads to issues
with resulting data size and networking bottlenecks. An idea here is to let
miners solve multiple problems at once and then let authority nodes randomly
select one of these solutions and discard the others. While this can be seen
as a waste of useful work it might be necessary sacrifice to control problem
difficulty without increasing data sizes.

$\triangleright$ CoinAI aims to adjust the PoUW difficulty over time by
dynamically adjusting the required performance requirements of resulting deep
learning models over time. The idea behind this approach is that validating
the performance of a given model is less computationally expensive than
training the model. An issue with this approach is that even when knowing the
network’s total computational power, it would be difficult to estimate an
adequate performance threshold. With respect to this problem, Coinami authors
note that even slightly increasing the difficulty can potentially result in
unsolvable problems. Another problem here is that a centralized entity is
supposed to collect all submitted models, test their performance and then
announce the winner. A negative aspect here is that miners would be forced to
trust a centralized authority. If no such authority were to be involved, then
other issues would occur: Deep learning models that solve non-trivial problems
can have a size from a few megabytes to many gigabytes. If there were no
centralized authority, then every node would be forced to download the models
of all other nodes and test the performance of all of them in order to
determine the winner model. As a result bandwidth limitations, spam and sybil
attacks potentially make this approach infeasible.

#### PoUW: Verification

A core principle of consensus algorithms in public blockchains is that they
are used in order to provide nodes with a method that enables them to form
consensus about the current state of the blockchain without having to rely on
trust. Hash functions are useful in this regard since the validity of a
proposed (input, output) tuple can quickly be verified. As soon as hash-based
approaches are discarded in favor of methods that perform useful work, it can
become difficult to find a verification method that does not have to rely on a
verification-by-replication approach in which the entire useful work process
has to be repeated by many nodes. For a given problem there might or might not
exist a probabilistic verification approach in which the likelihood of some
proposed solution being valid can be estimated efficiently. Therefore, it
needs to be decided on a case-per-case basis what is the best way to formulate
a PoUW problem in such a way that verification of results can happen quickly
and with reasonable amounts of computational effort.

$\triangleright$ In the case of Primecoin, probable primality of prime chains
is verified using a combination of both the Fermat and the Euler-Lagrange-
Lifchitz test for prime numbers. These are proven mathematical methods that
can be used to efficiently verify the primality of a given number with the
downside that there exist so-called pseudoprimes that pass those prime tests
but which are in fact not prime numbers. The authors of Primecoin have
concluded that the probability of pseudoprimes occurring is low enough that
this issue can be traded in favor of being able to provide a fast and
efficient verification mechanism. [Kin13]

$\triangleright$ In the Coinami proposal, sub-root authorities collect results
from miners and verify the validity of alignments using decoy reads that have
been placed into the problem. These decoys are planned to make up around 5% of
each problem and they can be pre-calculated by the sub-authorities. After
verification, decoy data is removed from the results. The main challenge here
is to place decoy data in such a way that miners are not able to spot these
segments in their assignments. If a sub-authority has validated a miners
solution, then the data is signed and sent back so that it can be added to the
blockchain.

$\triangleright$ In CoinAI resulting deep learning models are considered to be
valid proofs-of-work only if they pass the current performance threshold. The
authors provide no concrete plans about whether a centralized entity is
responsible for verification or if every miner has to verify all submitted
models by other nodes. Potential issues that might occur in either case have
already been presented in the adjustable hardness section of this publication.
III
A common approach to validate the performance of a deep learning model is to
use two separate datsets, one containing training data used for training the
model and the second dataset being the validation/test dataset. CoinAI gives
no specifics on how nodes acquire required training datasets which potentially
poses a challenge in overcoming issues such as networking bottlenecks due to
large datasets that need to be downloaded. The current state-of-the-art in
training of deep learning models boils down to the fact that you need more and
more training data to improve your model over time, since hyperparameter
tuning of a model that was trained on a small dataset alone rarely results in
a robust model than can reliably solve non-trivial problems. As a result, the
training dataset would have to be extended over time which raises further
questions about who provides this data, how this affects centralization and
who is willing to sacrifice computational power and network bandwidth to test
the performance of all submitted models. Even if all of these potential issues
were to be resolved, assuming the same model is trained over many blocks one
could argue that as soon as better performing models for a given task are
discovered all previously published models lose their usefulness since they
perform worse than the newer models. This raises the question if such an
approach can be considered to be useful work in the first place. If, however,
completely different deep learning models are to be trained at regular block
intervals, potential problems of continuously broadcasting new training data
sets and generating robust models performance might become overwhelming.

#### PoUW: Parallelizability

In order to enable the efficient usage of multi-core CPUs, GPUs and facilitate
the existence of mining pools, a PoUW consensus algorithm preferable should be
of embarrassingly parallel nature. An intuitive example of such a problem is
any form of processing or generation of unrelated data, like it is done in
e.g. brute-force searches.
There are many non hash-based approaches that fulfill this property: For
instance, Monte Carlo event generation and reconstruction in particle physics,
pattern matching over DNA sequences in bioinformatics and hyperparameter
tuning in deep learning can all be considered to be embarrassingly parallel
problems.

$\triangleright$ In Primecoin the search for prime chains can trivially be
implemented in a parallelizable way.

$\triangleright$ Pattern matching over DNA sequences in bioinformatics like
proposed in Coinami is of embarrassingly parallel nature.

$\triangleright$ Training deep learning models and hyperparameter tuning like
proposed in CoinAI is an embarrassingly parallel problem.

All in all, it can be concluded that retaining the parallelizability property
is not an issue for PoUW approaches.

## IV. Conclusion

This publication has provided an overview over essential properties that
conventional hash-based proof-of-work consensus algorithms possess.
Additionally, an analysis of which measures were taken by existing PoUW
approaches such as Primecoin, Coinami and CoinAI in order to retain hash-based
PoW properties while rewarding useful work was provided. It was concluded that
domain-specific knowledge is required to make PoUW consensus possible and that
implementation details must be decided on a case-by-case basis using domain
knowledge from that area of research.

The main weakness that all presented PoUW approaches have in common is the
verification of results. While the author of Primecoin was able to find an
elegant probabilistic solution of this problem, theoretical publications like
Coinami and CoinAI had to make both efficiency and decentralization sacrifices
to prevent potential problems.

A common issue with designing new PoUW consensus approaches is that the size
of resulting data can be significant compared to hash-based approaches which
leads to situations in which data must either be stored externally or on-chain
which negatively affects not only storage requirements of full nodes but also
sync times of new nodes which effectively raises the entry barriers of
participating in the blockchain.

All in all, problems of mathematical nature seem to be best suited for PoUW.
These problems have the advantage that a large repertoire of probabilistic
verification methods already exists for a wide range of problems, which in
addition to a generally asymmetrical ratio of computational effort and size of
resulting output make this class of problems potential suitable for making
PoUW consensus mainstream.

It remains to be seen whether the concept of Proof-of-Work itself will survive
the surge of alternative blockchain consensus algorithms like Proof-of-Stake
which do not require notable amounts of computational effort to efficiently
form consensus and therefore secure the underlying blockchain.

## References

  * [BS19] Alejandro Baldominos and Yago Saez.  Coin.ai: A proof-of-useful-work scheme for blockchain-based distributed deep learning.  Entropy, 21(8):723, 2019.
  * [Coi16] Coinami.  Coinami prototype.  https://github.com/coinami/coinami-pro, 03 2016.
  * [Coi22] Coinmarketcap.  Primecoin.  https://coinmarketcap.com/currencies/primecoin/, 08 2022.
  * [IOG+16] Atalay Mert Ileri, Halil I. Ozercan, Alper Gundogdu, Ahmet K. Senol, M. Yusuf Oezkaya, and Can Alkan.  Coinami: A cryptocurrency with dna sequence alignment as proof-of-work.  CoRR, abs/1602.03031, 2016.
  * [Kin13] Sunny King.  Primecoin: Cryptocurrency with prime number proof-of-work.  https://primecoin.io/primecoin-paper.pdf, 07 2013.
  * [Nak08] Satoshi Nakamoto.  Bitcoin: A peer-to-peer electronic cash system.  https://nakamotoinstitute.org/literature/bitcoin/, 10 2008.