The multiplication (and division, which is multiplication with the inverse) is by scalar only. You cannot multiply two public keys without solving ECDLP first. And if you somehow can, then all coins are belong to you.

@mrxtraf
In the private key group (mod n) we can add, negate, and invert - this allows for multiplication and division.

In the public key group (elliptic curve mod p of size n) we can add, negate, and double only. This leads to multiplication by a scalar.

One public key corresponds to exactly one private key, and vice versa. The proof is very easy. Let G is the generator of secp256k1. Let P=k*G is a point on the curve. Let also P=k'*G. Then (k-k')*G=O => (k-k') divides n. But n is prime, hence k=k' (mod n).

IMO OpenCL on AMD would work only if written in assembler. I lost the race for #90 because of it. One week of random hard lock-up. And the worst. Wrong computations. Totally unusable. (It might have a chance to work properly with newer hardware, and a specific driver version, but I highly doubt.)

I looked last year at FPGA, and it will be slower than current top-end GPUs, costing much more for the same performance (per chip).

As for an ASIC, if it ever is done, I expect 3x performance per chip price compared to GPU. The performance per watt would be way better, maybe 50x. It might be feasible only after bitcoin price goes above $5M, making new chip costs millions. There's a huge disadvantage - unlike mining chips it would be used only one-two times.

Kangaroos should collide at ~sqrt(n)/NumKangaroos jumps. Otherwise something is very wrong.

There's a windows build of v0.2.10 from Laszlo Hanyecz (bitcoin pizza).

http://heliacal.net/~solar/bitcoin/builds/Win32-MinGW-SVN-81/

Miners collect also fees. Today they collected ~120BTC in fees.

You could find old versions here: https://satoshi.nakamotoinstitute.org/code/

Very old nodes wouldn't be able to find peers, to connect, to deal with blocks bigger than half megabyte, or finish downloading the blocks in reasonable time.
Versions prior 0.2.9 would not work without changes in p2p protocol.

In order for a collision to happen, one needs at least 1 DP per kangaroo. This is the absolute minimum. In my software (June 26 - July 5, 2019) I was targeting 8 DP/kangaroo at 100% expected jumps. Then my very simple hash table was with max 2³² entries, but DPs were limited to 2²⁹ entries (IIRC 2²⁸ for #95). The whole program was using 48GB for the data - 32GB for DP, 16GB for hash table. For #95 2^27.79 points were used at 86.55%, for #100 2^26.97 at 69.1%. All the DPs were written to file, there was no performance difference on the AWS instance (p3.8xlarge). The file was write-only, since I never needed to read from it, software just found the keys.

In my experiments collision was happening between 3 and 12 DP/kangaroo. There was never tame/tame or wild/wild collision, since I used the original Pollard Kangaroo, no wrapping around 0 or other funky stuff - IMO it would make it faster in half of the cases, and way slower in the other half, when it's negative.

I was using 72*512*256 = 3²2²⁰ kangaroos per GPU. So for #110 if one is using the same number of kangaroos on 128 GPUs, at 8 DP/kangaroo it would be 2^33.17 DPs, or 576GB for DPs, and maybe 128GB for (a not-so-simple) hash table minimum.

The other thing that would affect performance is the bandwidth in server-GPU communication. With 8 DP/kgr at 100% of expected time, one can calculate the DP/second of each client. For #110, 128 GPUs, and 9 million kangaroos/GPU, 42.18 million jumps/kgr for 100% exp. time, 1600 MJ/s per GPU, 172.6 Jumps/second/kangaroo, about 618 DP/GPU/second are needed, which is 39 KB/s without overhead. For 128 GPUs the total bandwidth without overhead would be 5 MB/s, or 40 Mbit/s.

If your key was reused then it's possible to recover it. Then the time complexity is only 2⁴⁰, which is doable in 15 minutes on a V100 GPU.

Reused key means you sent coins from it, and know the public key.
Or if you signed anything and have the signature.

Looks like this paper is about solving DLP in Z*, not ECDLP. Furthermore the wild and tame jumps differ, which leads to significant memory requirements. Not suitable for GPU as well.

The values I provided for a and b are correct, given the input. According to the puzzle there are a bit less than 2²⁵⁶ possible pairs.

The screenshot provides more information, one could see the tops of the numbers, and restrict a and b. A quick look makes it obvious where 7 5 4 1 6 are.

Well, that's easy:
So, an obvious solution is a=12447032699845648078645791161909514142990644957498005805208944683777961822095, b=1

Both mnemonics have invalid checksum. For 12 words the chance to get a valid checksum is 1/16. So if you don't check it, in 15 of 16 cases you'd get garbage.

QC could not improve computing power.

Classical computing will always be cheaper and faster than QC.

It is very simple physics, noise ruins all and every extrapolated prediction of QC efficiency.

IMO, quantum physics is not the reality, but rather a set of very useful statistical tools.

Due to the imaginary nature of quantum physics, people easily get confused.

I was using 4x Tesla V100 for it. Here is a table with expected times:

|------+-------------------+-------------------|-------------------|
| bits |      4x V100      |     100x V100     |    27648x V100    |
|------+-------------------+-------------------|-------------------|
|  100 |       2d 19:52:51 |          02:42:54 |          00:00:35 |
|  105 |           16 days |          15:21:34 |          00:03:19 |
|  110 |           90 days |       3d 14:53:14 |          00:18:51 |
|  115 |  1 year  147 days |           20 days |          01:46:39 |
|  120 |  7 years 341 days |          116 days |          10:03:23 |
|  125 | 44 years 323 days |  1 year  290 days |       2d 08:53:15 |
|  130 |       253 years   | 10 years  57 days |      13d 09:48:19 |
|  135 |     1,436 years   | 57 years 166 days |      75d 20:24:23 |
|  140 |     8,125 years   |         325 years |  1 year   64 days |
|  145 |    45,964 years   |       1,838 years |  6 years 237 days |
|  150 |   260,011 years   |      10,400 years | 37 years 225 days |
|  155 | 1,470,848 years   |      58,833 years |         212 years |
|  160 | 8,320,376 years   |     332,815 years |       1,203 years |
|------+-------------------+-------------------|-------------------|

Looks like a "world record" would be 120 bits.

Edit: added timings for the fastest (June 2019) top500 supercomputer - Summit.

#100 - af55fc59c335c8ec67ed24826

Lucky with only 69% of the expected time - 1d 22:49:48 of the 2d 19:46:27 expected.

Who says it's not optimal?

Almost 38 million kangaroos spread across 4 Tesla V100.
Only 86% of the expected run time was needed.

Each kangaroo has to produce at least few distinguished points.
All these points have to be stored in a hash table, for efficient collision detection.
Experiments show, that collision happens with 3-12 DP/kangaroo.

And since none bothered to post the key from the image:
#95 - 0000000000000000000000000000000000000000527a792b183c7f64a0e8b1f4

There is nothing "hacked" so far. The Distributed Pollard Kangaroo algorithm is known since 2000.

Let's get some numbers for the 90 bit challenge:

BitCrack runs at about 715 MKeys/s on Tesla V100 - look here.
If we remove hash160, the rate would be 1430 Mj/s. Mj here stands for million kangaroo jumps.
The algorithm has expected run time 2*sqrt(b-a) jumps, here b-a = 2⁸⁹.
This gives expected running time of 09:39:55.
Looks quite fast.
Of course this is just a probability, if lucky, the time goes down to 3-4 hours, or not lucky, then time doubles to 18-20 hours.
Or really unlucky, with triple the expected run time - 1 day 04:59:47.
Since the algorithm scales linearly, one could use multiple V100, let's say 8, resulting in expected time 01:12:29.
The price for 8x V100 in google cloud is $15/hour.

Someone having 20x RX 480, each running BitCrack at 107 MKeys/s.
Using the same assumptions that would give 214 Mj/s each, for a total of 4280 Mj/s.
Please note, that for complex code AMD OpenCL compiler is very, very bad, and the system might crash, or even worse, bug the computations.
Assuming 150W per RX 480, the system would consume 3kW.

|------+-------------+---------+---+-----------------+-------------|
|      |     8x Tesla V100     |   |         20x RX 480            |
| bits +-------------+---------+---+-----------------+-------------|
|      |    time     |  price  |   |       time      |    power    |
|------+-------------+---------+---+-----------------+-------------|
|   90 |    01:12:29 |     $18 |   |        03:13:45 |     9.7 kWh |
|   95 |    06:50:04 |    $103 |   |        18:16:05 |    54.8 kWh |
|  100 | 1d 14:39:43 |    $580 |   |     4d 07:20:24 |   310.0 kWh |
|  105 | 9d 02:42:22 |   $3281 |   |    24d 08:34:45 |  1753.7 kWh |
|  110 |   51 days   |  $18558 |   |   137 days      |  9920.6 kWh |
|  115 |  291 days   | $104979 |   | 2 years 49 days | 56119.6 kWh |
|------+-------------+---------+---+-----------------+-------------|

Of course these numbers could easily double when unlucky.
And someone else could solve it before, then it's all a loss.

You are off with the numbers.
Security is 128 bit for 256 bit public keys, and 50 bit for 100 bit pk.
So the security headroom is 128-50 = 78 bits.