Point addition

In affine coordinates: 1*inversion + 2*mul-mod-p + 6*sub-mod-p
  = 16,141,271 + 2*589,568 + 6*3,068 = 17,338,815
Jacobian plus affine: 11*mul-mod-p + 6*sub-mod-p
  = 11*589,568 + 6*3,068 = 6,503,656
256-bit-multiplex: 769

Affine coordinates:
bit  PA   256-bit-muxes
 1: 255   2*256             4,421,791,553
 2: 127   2*4*128           2,202,816,961
 4:  63   2*16*64           1,093,920,257
 8:  31   2*256*32            550,102,561
16:  15   2*65536*16        1,872,792,113
 9:  28   2*(512*28 + 16)     507,560,196
10:  25   2*(1024*25 + 64)    472,941,607
11:  23   2*(2048*23 + 8 )    471,251,001
12:  21   2*(4096*21 + 16)    496,432,331


Jacobian coordinates (including final inversion and 2 mul-mod-p):
bit  PA   256-bit-muxes
 1: 255   2*256 + 256           1,676,343,279
 2: 127   2*4*128 + 128           844,170,607
 4:  63   2*16*64 + 64            428,674,863
 8:  31   2*256*32 + 32           231,557,647
16:  15   2*65536*16 + 16       1,727,597,439
 9:  28   2*(512*28 + 16) + 29    221,518,452
10:  25   2*(1024*25 + 64) + 26   219,403,033
11:  23   2*(2048*23 + 8 ) + 24   239,381,207



Using mixed Jacobian-affine coordinates,
adding in groups of 10 bits (25 1024-point memories plus 64-point memory),
we get 219,403,033 gates.

Multiplication is cheaper since p is fixed.

1-bit full-add: 2*XOR + 2*AND + 1*OR
1-bit half-add: 1*XOR + 1*AND
1-bit full-add-zero: 1*XOR + 1*AND
1-bit full-add-one: 1*XNOR + 1*OR
1-bit full-subtract: 2*XOR + 2*AND + 1*OR + 2*NOT
1-bit half-subtract: 1*XOR + 1*AND + 1*NOT
1-bit half-add-one: 1*NOT + wire

256-bit-add: 255*full-add + 1*half-add
  = 511*XOR + 511*AND + 1*OR
256-bit sub: 255*full-subtract + 1*half-subtract
  = 511*XOR + 511*AND + 255*OR + 511*NOT
256-bit-add-p: 249*full-add-one + 1*half-add-one + 6*full-add-zero
  = 249*XNOR + 249*OR + 1*NOT + 6*XOR + 6*AND
256-bit-add-minus-p: 249*full-add-zero + 1*half-add-one + 6*full-add-one
  = 249*XOR + 249*AND + 1*NOT + 6*XNOR + 6*OR
256-bit mux: 768*NAND + 1*NOT

add-mod-p: 256-bit-add + 256-bit-add-minus-p + 256-bit-mux
 = 6*XNOR + 760*XOR + 760*AND + 7*OR + 768*NAND + 2*NOT
sub-mod-p: 256-bit-sub + 256-bit-add-p + 256-bit-mux
 = 249*XNOR + 517*XOR + 517*AND + 504*OR + 768*NAND + 513*NOT
mul-mod-p: 256*add-mod-p
 = 0x600*XNOR + 0x2f800*XOR + 0x2f800*AND + 0x700*OR + 0x30000*NAND + 0x200*NOT

mul-mod-p is 589,568 gates; this makes it ~27 times cheaper than inversion

For binary euclidean gcd the maximum number of iterations is <=760.

To achieve it let u is zero with msb=1. Then 6 does 255 cycles (the number of zeroes), and we end with u=1. Next 21 and 12 are alternated, except for the few zero bits in p. 12 is executed 255 times, and 21 - 249. Finally u and v are both 1, and 18 is executed.

Another way to look at it is both 6 and 12 have to be executed 255 times max. This limits either 18 or 21 to be executed at most 255 times. This gives <=765 cycles.

Even A tends towards zero, odd A tends towards p. After every execution of 18 u is even and 6 is executed at least once. Same for 21 and 12. Then A and C are between -2p and 2p (after 18/21). 256+1 bits plus 1 sign bit, for toal 258 bits.


1-bit full-adder: 2*XOR + 2*AND + 1*OR
1-bit half-adder: 1*XOR + 1*AND
1-bit full-add-to-zero: 1*XOR + 1*AND
1-bit full-add-to-one: 1*XNOR + 1*OR
1-bit full-subtract: 2*XOR + 2*AND + 1*OR + 2*NOT
1-bit half-subtract: 1*XOR + 1*AND + 1*NOT
1-bit full-sub-zero: 1*XOR + 1*AND + 1*NOT
1-bit full-sub-one: 1*XNOR + 1*OR + 1*NOT
1-bit half-add-to-one: 1*NOT + wire
1-bit half-add-to-one-drop-lsb: wire

258-bit add to p drop lsb (A+p)/2: 249*full-add-to-one + 1*half-add-to-one-drop-lsb + 8*full-add-to-zero
  = 249*XNOR + 249*OR + 8*XOR + 8*AND
256-bit sub: 255*full-subtract + 1*half-subtract
  = 511*XOR + 511*AND + 255*OR + 511*NOT
258-bit sub: 258*full-subtract
  = 516*XOR + 516*AND + 258*OR + 516*NOT
256-bit mux: 768*NAND + 1*NOT
258-bit mux: 774*NAND + 1*NOT
256-bit compare ge: 256*XNOR + 256*AND + 256*NOT +   255*AND +   255*AND + 255*NOT + 255*AND
  = 256*XNOR + 1021*AND + 511*NOT

We have the following possible operations in the cycle:
1. 256-bit check for zero: 255*OR (+ 1*NOT)   <- not omitted
2. 256-bit >=: 256*XNOR + 1021*AND + 511*NOT
3. 256-bit subtraction: 511*XOR + 511*AND + 255*OR + 511*NOT
4. 258-bit add p, div 2: 249*XNOR + 249*OR + 8*XOR + 8*AND
5. 258-bit subtraction: 516*XOR + 516*AND + 258*OR + 516*NOT
3,4,5 are done twice

Control:
u1 = not 1. & not u[0]              - 1*AND + 1*NOT
v1 = not 1. & u[0] & not v[0]       - 2*AND + 1*NOT
u2 = not 1. & u[0] & v[0] & 2.      - 3*AND
v2 = not 1. & u[0] & v[0] & not 2.  - 1*AND   (repeat from up)
u = not (u1 | u2)                   - 1*OR + 1*NOT
v = not (v1 | v2)                   - 1*OR + 1*NOT
A1 = u1 & not A[0]                  - 1*AND + 1*NOT
A2 = u1 & A[0]                      - 1*AND
A3 = u2
A = u
C1 = v1 & not C[0]                  - 1*AND + 1*NOT
C2 = v1 & C[0]                      - 1*AND
C3 = v2
C = v
= 11*AND + 2*OR + 6*NOT

One cycle:
1. 255*OR
2. 256*XNOR + 1021*AND + 511*NOT
3. 1022*XOR + 1022*AND + 510*OR + 1022*NOT
4. 498*XNOR + 498*OR + 16*XOR + 16*AND
5. 1032*XOR + 1032*AND + 516*OR + 1032*NOT
ctrl. 11*AND + 2*OR + 6*NOT
mux. 10800*NAND + 14*NOT
= 754*XNOR + 2070*XOR + 3102*AND + 1782*OR + 10800*NAND + 2585*NOT

760 cycles: 573040*XNOR + 1573200*XOR + 2357520*AND + 1354320*OR + 8208000*NAND + 1964600*NOT
765 cycles: 576810*XNOR + 1583550*XOR + 2373030*AND + 1363230*OR + 8262000*NAND + 1977525*NOT

---

C mod p:
-2p <= C <= 2p, hence two times add to p, and two times add to -p
256-bit add to p: 249*full-add-to-one + 1*half-add-to-one + 6*full-add-to-zero
  = 249*XNOR + 249*OR + 1*NOT + 6*XOR + 6*AND
256-bit add to -p: 248*full-add-to-zero + 1*half-add-to-one + 7*full-add-to-one:
  = 248*XOR + 248*AND + 1*NOT + 7*XNOR + 7*OR

selecting the output:
257-bit mux: 771*NAND + 1*NOT
256-bit mux: 768*NAND + 1*NOT

control the output:
omitted, <16 elements

= 512*XNOR + 508*XOR + 508*AND + 512*OR + 3078*NAND + 8*NOT

---

total:
760 cycle: 573552*XNOR + 1573708*XOR + 2358028*AND + 1354832*OR + 8211078*NAND + 1964608*NOT
765 cycle: 577322*XNOR + 1584058*XOR + 2373538*AND + 1363742*OR + 8265078*NAND + 1977533*NOT

760 cycle: 16,035,806 gates
765 cycle: 16,141,271 gates

this is close to 8.5 times more gates than the wrong estimate

From "SPA vulnerabilities of the binary extended Euclidean algorithm":
Binary extended Euclidean algorithm
Inputs: Integers k and p such that gcd(k, p) = 1
Output: k⁻¹ mod p
 1: u = k
 2: v = p
 3: A = 1
 4: C = 0
 5: while u != 0 do
 6:   while even(u) do
 7:     u = u/2
 8:     if even(A) then
 9:       A = A/2
10:     else
11:       A = (A+p)/2
12:   while even(v) do
13:     v = v/2
14:     if even(C) then
15:       C = C/2
16:     else
17:       C = (C+p)/2
18:   if u ≥ v then
19:     u = u-v
20:     A = A-C
21:   else
22:     v = v-u
23:     C = C-A
24: return C mod p


After unrolling the cycles, we could at each iteration do either of
* u = u/2, A = A/2 or (A+p)/2
* v = v/2, C = C/2 or (C+p)/2
* u = u-v, A = A-C
* v = v-u, C = C-A

So, a single loop cycle would be:
1. In parallel:
* Check if u = 0
* Check if u >= v
* u1 = u/2 (drop lsb)
* u2 = u-v (256-bit subtraction)
* v1 = v/2
* v2 = v-u
* A1 = A/2
* A2 = (A+p)/2 (n-bit addition, dropping lsb)
* A3 = A-C     (n-bit subtraction)
* C1 = C/2
* C2 = (C+p)/2
* C3 = C-A
For u and v we need 3 muxes each - passthrough (old value), u1, u2
For A and C we need 4 muxes each - passthrough, A1, A2, A3

2. Select what happens in this cycle, default being passthrough, highest priority first:
* u = 0 : all passthrough
* u is even : u1, if A is even A1 else A2
* v is even : v1, if C is even C1 else C2
* u >= v : u2, A3
* else : v2, C3

What remains is the maximum number of iterations of the cycle, and how many bits (n) are needed for C and A.

Most probably I made a mistake in binary extended gcd. It should be slower than mul-mod-p.

I'll post a detailed algorithm -> logic tomorrow.

This is a ridiculous statement. All math on computer is done via logical elements. Always has been.



From your gates construct add-mod-p, sub-mod-p, mul-mod-p, binary-extended-gcd-algorithm. Mix them appropriately.

add-mod-p would be 256+256-to-257 bit adder, 257-bit adder, 256-bit multiplexer
sub-mod-p would be 256 bit not, 256+256+1-to-257 bit adder, 257-bit adder, 256-bit multiplexer
mul-mod-p would use add-mod-p + multiplexor (+ sub-mod-p for doubling) up to 256 times, depending on the number we multiply to
binary-extended-gcd can be found in chapter 14 of Handbook of Applied Cryptography, available online at http://cacr.uwaterloo.ca/hac/
Inversion is done only once via b-e-gcd: since v=y=1 skip steps 2 and 5.

Since G is fixed, you should precompute 2^0-255G, and use them via multiplexer.

If it is less costly (less gates), you could group powers of G by 2, 3, or more bits, using more multiplexers.

A minimal example:       there might be mistakes

256-bit adder: 255*(2*XOR + 2*AND +1*OR) + 1*XOR + 1*AND = 511*XOR + 511*AND + 256*OR
257-bit adder: 513*XOR + 513*AND + 257*OR
256-bit adder with carry input: 512*XOR + 512*AND + 256*OR
256-bit sub: 512*XOR + 512*AND + 256*OR + 256*NOT
256-bit multiplexer: 512*AND + 256*OR + 1*NOT

add-mod-p: 0x400*XOR + 0x600*AND + 0x301*OR + 1*NOT
sub-mod-p: 0x401*XOR + 0x601*AND + 0x301*OR + 0x101*NOT
mul-mod-p: 0x100*add-mod-p + 0x100*sub-mod-p + 0x200*multiplex
              = 0x80100*XOR + 0xe0100*AND + 0x80200*OR + 0x30200*NOT
inversion: 0x100*add + 0x300*sub + 0x200*multiplex
              = 0x7ff00*XOR + 0xbff00*AND + 0x60000*OR + 0x30200*NOT

Looks like inversion is less costly than mul-mod-p. (There might be more efficient mul-mod-p method though.)
We'll use affine coordinates then.
In affine coordinates point addition is 1*inversion + 2*mul-mod-p + 6*sub-mod-p
  = 0x181906*XOR + 0x280706*AND + 0x161606*OR + 0x90906*NOT

256 point-additions + 256 multiplexers: 0x18190600*XOR + 0x28090600*AND + 0x14170600*OR + 0x9090700*NOT

some missing logic for the leading zero bits: less than 4K
missing inversion logic: less than 1M

total: 0x5f421900= 1,598,167,296 gates.

Combining several bits:

 2: 128 PA +   4*128 mux = 799,378,944
 4: 64 PA +    16*64 mux = 400,280,064
 7: 37 PA +   128*37 mux = 234,598,648
 8: 32 PA +   256*32 mux = 206,045,952
 9: 29 PA +   512*29 mux = 192,438,200
10: 26 PA +  1024*26 mux = 182,767,728
11: 24 PA +  2048*24 mux = 187,607,616
16: 16 PA + 65536*16 mux = 906,228,096


Looks like the best combination is to do additions in groups of 10 bits. 182,767,728 gates (plus maybe a million more).

With my code 03d322a42421f709d1b6253ecd0c442059534644544276ac3f964154e4b1ca56f4 would become
"spring benefit animal dumb identify trip sudden pond snack giraffe amount razor crucial captain extra excite promote witness motion prefer enrich topple forward observe".

Drop (and remember) the starting 03, encode the rest, "increment" the last word (since y is odd).

Decoding would be: calculate the checksum, if it doesn't match "decrement" last word (and remember y is odd), if it still doesn't match - error, decode, prepend 02 (or 03 when odd), check if point is valid - otherwise error.

Minimal number of bits for public key is 257: 256 bit x and 1 bit y (usually parity).

Compressed public key starts with 02 or 03, which is y parity. If you have a way of avoiding or guessing the y bit, then just use the x bits.

If this is not possible, then transform x to mnemonics, and then, if y is odd, let the last word be the next from the wordlist, modulo 256. Obviously this would break the checksum verification in half of the cases, but then you set the last word to be the previous-mod256 one, and if checksum matches, then you are good to go, knowing y is odd.

For example 020000000000000000000000000000000000000000000000000000000000000001 would be
"abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon diesel"
while 030000000000000000000000000000000000000000000000000000000000000001
"abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon abandon diet"

By next-mod256 I mean if the last word is "cable", next-mod256 would be "abandon" (not "cactus").

secp256k1 uses the equation y² = x³ + 7 (mod p). Only half of the possible x values give a solution for y. Compressed public key is the parity of y represented as 02 when even or 03 when odd followed by x.

Some random thoughts on coins and ownership.

Private keys give possibility to sign transactions. All ownership is on the other hand a fiction, fantasy. It does not exist in reality.

Owning something means everybody else agreeing or being forced to agree to it. This makes some sense locally, (and could be highly beneficial), but for a global thing like bitcoin it's total bullshit. Owning bitcoin then means owning a number. A number can be known or unknown. Owning a number then is forbidding everyone to know a certain number. How ridiculous.

Since bitcoin is decentralized, no one could own coins. Otherwise it is not decentralized. So you have to choose. To bend it to law, bring ownership and centralize it. Or to let it be decentralized, and instead of owning, have access. We could see the push to centralize it - "tainted coins", KYC/AMLx, trying to force you to own coins instead of having access.

Some people (all?) have access to some coins, and think they own it. It's a lot like the access to "your" body, or to "your" mind, or to anything "yours". The day comes, when access is gone. It's a matter of time.

Getting access to some random coins could be impossibly hard, maybe one of the hardest problems right now. Knowing the public key(s) makes it less hard, but still impossibly hard.

There are just less than 2²⁵⁶ possible public keys.
There are 2¹⁶⁰ possible P2PKH addresses.

For quite some time there is already a bitcoin git mirror on laanwj (Wladimir) server:
http://nxshomzlgqmwfwhcnyvbznyrybh3gotlfgis7wkv7iur2yj2rarlhiad.onion/
https://laanwj.github.io/2018/06/08/tor-repository.html

This includes also the issues (bitcoin-gh-meta), and three major lightning implementations.

There are two things here: reversing hash to "a message", and reversing a hash to "the message". Depending on "the message", it is way more impossible than just "a message".

Mining is "a message" one, and can be viewed as finding small number of bits (currently less than 80), which produce corresponding zero bits in the output of a complex single hash function (changing with each new block, selected transactions, etc.).

So, we could view that hash as 80-bit input 80-bit output one.

Given a good hashing function, the probability of being able to get the desired output is 1/2 (for equal number of input and output bits).

Let's look at a hypothetical O(2^n/2) algorithm.

While everyone else would be doing 2⁸⁰ work, the smart algo would be doing only 2⁴⁰.

Such algorithm would be complex, so it would take certain fixed time to get the result, let's say 300 seconds (5 min).

Getting 33% of the hashrate means adding 50% more hashrate than the current one. Adding hashrate should be incremental, with increase about 0.2% per day. This amounts to 250 days til reaching the desired 1/3 of the total.



Reversing p2pkh is way more complex - if we view transformation from private key to public key as a hash function, then we have a sequence of 3 hash funcs., the first one being the most complex, but aslo the lousiest.

With the n/2 hypothetical algo, we get complexity 2⁸⁰ of both operations and memory requirements, which is way beyond what's available now.

But it looks like possible in the future. One day, when a memory cell is of size 9x9x9 nm, a cube with size only 1 meter would contain 2⁸⁰ bits.

The algorithm is hypothetical, and we might never know if anybody found it.

But such memory, and corresponding computers are achievable with todays technology. It's only matter of time, and desire to get rid of the current chip-based stuff.

You sound very confused.

Let me make it more clear.


           Number-of-jumps: 2^128
                 NV100 TDP: 300 W
    NV100 jumps per second: 1.6e9
number of seconds per hour: 3600

So:
  wattseconds per jump: 300 / 1.6e9
    watthours per jump: (300/1.6e9)/3600
    Wh per 2^128 jumps: 2^128 * (300/1.6e9)/3600

Yes it is "possible". But it's currently infeasible.

2¹²⁸ Jumps * 300 W / 1.6e9 Jumps/s / 3600 s/hour = 1.77e28 Wh
You'd have to spend 1.77 YWh (yotta-watt-hours), just to have a fifty-fifty chance of finding out the number.

This is the total output of 2,000,000,000,000,000 big nuclear reactors for one year.

Or 17 seconds of the total energy output of the sun.

Of course knowing something about the private key, any bits of information, could greatly help reduce that number.

I wouldn't count on that.

About 90 years ago Kurt Gödel found out, that one cannot make such "impossible" statements.

It turned out, that there are infinite number of not-yet-known facts about the natural numbers, which are not achievable by any finite set of theorems.

So, it's quite probable, that there's a theorem, which makes ECDLP, or reversing sha256 really easy.

If we deal with n-bit numbers:
For ECDLP I would guess a lower bound of O(n^c), c being a constant.
SHA256, or any hash function, should be at most O(2^n/2), possibly with O(2^n/2) memory as well. With some kind of probabilistic method, it might be even lower.

On the bright side, eventually this would be found by someone. Anyone smart enough to achieve this, would be smart enough to keep it for himself.

ECDLP solved means easy access to any coin with know pubkey(s). I doubt that early bitcoins would be touched though, it's too obvious.

SHA256 "solved" means cheap mining, leaving ASIC farms in the dust. One could easily mine 300 coins/day without being noticed, no need to announce anything to the big world.

Let's have two points with coordinates (x1, y1), (xk, yk), and let (xk, yk) = k * (x1, y1).
Then
k² ≈ x1/xk
k² ≈ x1/xk * (1 - (k⁶ - 1) / y1²) = x1/xk * (1 - (k⁶ - 1) / (x1³ + 7) )
and so on...

If I got it correctly payments are still limited to 0.0429 4967 295 BTC (2^32-1 msat).

From BOLT #2, update_add_htlc

Multiply by 57896044618658097711785492504343953926418782139537452191302581570759080747169


Let the point you want to multiply is G, and the multiplication constant is c. The result will be P=c*G

One way to do it is:

1. Start with the point at infinity P = (0,0) = 0*G, Q = G = 1*G, d = c

2. if d is zero return P

3. If d is odd let P = P + Q

4. Double Q: Q = 2*Q, halve d rounding towards zero: d = floor(d/2)

5. Go to step 2

In secp256k1 there are two important primes - the prime p which is used for coordinates x and y (2^256 - 2^32 - 977), and the prime n, which is the group order (2^256 - 432420386565659656852420866394968145599).

The group is defined by two operations - addition of two points, and doubling a point.

From this we easily could multiply a point by scalar, this is series of additions and doublings.

Multiplying a point by scalar gives another point. Multiplying a point by n gives the point at infinity (0,0).

Dividing by 2 in a group with order n is equivalent to multiplying by the scalar 1/2 (mod n).

One can find the inverse of 2 modulo n by the Extended Euclidean Algorithm.
1/2 (mod n) = 57896044618658097711785492504343953926418782139537452191302581570759080747169

You'd have to multiply (x,y) by 1/2 (mod n), this gives
x = 21505829891763648114329055987619236494102133314575206970830385799158076338148
y = 98003708678762621233683240503080860129026887322874138805529884920309963580118