ECDSA

I set out in October 2020 to attempt to put the ECDSA curve into an Excel spreadsheet without using array formulas, add-ins, or macros. It sounded like a good exercise in spreadsheet building and a chance to learn how Bitcoin uses the ECDSA curve.

What I thought would be a few months of work turned into a multi-year project that finished in April 2023. The project went down many paths — building the SHA256 spreadsheet, a private key tutorial spreadsheet, a number of aspects around math — yet the secp256k1 ECDSA remained elusive.

I shelved the ECDSA spreadsheet a few times, incomplete, stopped by time constraints, computer constraints, Excel constraints, but primarily brain constraints — my understanding of the math behind the code was limited. There were many times I thought I would not complete the task.

Thankfully I had help. A lot of help. A big thank you to my mathematician guide KP who made modulo inverse multiplication and many other aspects of ECDSA math within the curve become less difficult, and without whom this project would not have completed. Also a big thank you to AP and a supportive crew, as well as to Mastering Bitcoin by Antonopoulos and Programming Bitcoin by Song, the learnmeabitcoin.com website, and many other people and websites that contributed magnitudes above what I have done in this exercise.

A nice aspect of the spreadsheet is it lays bare the inner workings of the ECDSA curve. You can use it to see one of the steps of how a private key is converted into a public key. Instructions are in a separate tab.

Play with the spreadsheet and if you break it please give me feedback for improvement. A few well-known methods such as 256 precalculated points are used — at over 200MB the spreadsheet is already too large. Why so large? The spreadsheet must go through a number of steps to achieve accurate calculations:

• All numbers are at sizes well above Excel's floating point limitations — as such, simple math (addition, subtraction, multiplication, division) must be done long form
• Maths operate within a modulus finite field, so Euclidean Division (remainders) must be used
• The biggest memory demand comes from the Extended Euclidean Algorithm and the steps necessary to derive the Greatest Common Divisor of the algorithm's points — this added over 180 tabs of division and multiplication to the spreadsheet, though the tabs are all identical with automated references between them

All of these calculations are just for the result of adding two points on the ECDSA curve. That's it — one step. It is not the entire number of times around the ECDSA curve. The spreadsheet is built so you can continue adding and bouncing around the curve by copy-pasting the resulting ECDSA third point to manually find subsequent points, eventually resulting in the Bitcoin x,y public key. As noted in a hackernoon article, the most copy/pasting you will have to do is 255 times.

The RIPEMD-160 spreadsheet followed not long after — you can find it on the spreadsheets page. The conversion of the ECDSA output into a public key and public address is also complete.

Lots of risk in using spreadsheets for holding Bitcoin value. This is educational. Enjoy. — dp