Team members: Jenny Chen, Jeffrey Kwan, Seongbin Park, Anastasia Simonova, John Wang
Our team used Quantum Grover’s search to significantly decrease the compute time it takes to do proof-of-work -- technology used by Bitcoin to approve addition of blocks to the blockchain. We use a four-bit system to compare performance of classical vs. quantum proof-of-work. The simplified model demonstrates the impact quantum computers can have with a greater number of qubits at their disposal.
Compare Grover’s search with classical “mining” algorithms in obtaining proof-of-work.
- Classical Proof-of-Work
- Quantum Implementation
- Comparison
- Conclusion
Classically, proof-of-work is an algorithm that ensures entities have undertaken enough computational work before adding blocks & completing transactions. An example of such an algorithm is SHA256 Hash Algorithm.
In our implementation, we use a parity of our our own hash that utilizes 4 bits to encode information and utilise brute force. The link to our notebook is here.
One of the challenges in comparing a classical vs. quantum proof of work algorithm is creating a hash function implementable both in classical and quantum terms. Here is our take: Quantum Hash
Using the hash created above, we integrate with Grover's search to find a far more superior search algorithm than classical brute force: Quantum Proof-of-Work
It is unviable to directly benchmark the performance of our Grover search implementation against its classical equivalent, due to the small scale of our circuit (resulting in the theoretical speedup being eclipsed by overhead).
However, as a general benchmark, here's how long bitcoin has set their proof-of-work problem to take, and how long Grover search would take to solve the same problem.
Though these results are exciting, we also tried our hand at a more realistic quantum proof of work circuit that involved nonces (https://coincentral.com/what-is-a-nonce-proof-of-work/). Though we got close to a working implementation, we did not have enough resources at hand to complete. Thus, we have linked it in the extras folder as extra goodies from our quantum exploits!
Big shoutout to the UCLA QCSA for organizing! This was a lot of fun!
https://qiskit.org/documentation/
https://forkast.news/proof-of-work-what-is-it-bitcoin-halving/
https://www.youtube.com/watch?v=bBC-nXj3Ng4 (3Blue1Brown)
https://www.youtube.com/watch?v=3EUAcxhuoU4 (Binance Academy)
https://www.youtube.com/watch?v=9V1bipPkCTU (Khan Academy)
https://blog.gameoflife.co/implementing-a-simple-proof-of-work-algorithm-for-the-blockchain-bdcd50faac18
https://arxiv.org/pdf/2202.10982.pdf \
https://arxiv.org/pdf/1603.09383.pdf