Hello,

In the context of presence of biased nonces, I've read in several places that if one doesn't have enough signatures to build a lattice of the required dimension, valid ECDSA signatures should be generated for this purpose.
However, I don't understand how this can help as one will generate "i=1..n" signatures with "Ki=ai+ bi*prvkey" using random (ai, bi) that doesn't provide any informaion about Ki.

Are there any hints for properly choosing (ai, bi) ?
The most obvious one is to have the same bias of Ki (difficult to achieve) but this is not enough, right ?

The problem can be generalized to :

is [chance with x bets in n attempts] = or > [chance with x/y bets in y*n attempts] ?

My answer is based on these extreme case examples :

1) Alice bets on the 6 numbers of the dice and rolls it 1 time  --> Alice is 100% sure of hitting a number

2) Bod bets on 1 number of the dice but rolls it 6 times          --> Bob may not hit a number (even if he bets on the same number). But he is "expected" to hit a number if he increases the number of his attempts.

For me this is why strictly speaking [chance with x bets in n attempts] > [chance with x/y bets in y*n attempts] .

3) Let's assume that Bob bets always on the same number    --> The probability of hitting this number at least one = 66.5% in 6 rolls or = 98.7% in 24 rolls (1-(5/6)^n for the formula).

In the case of bitcoin mining, the winning number is new every 10 min. Then what matters is the available hash rate during these 10 min.

The discussion is interesting, I'll be glad of hearing clarifications from experts.

Sorry, I insist because people might be fooled (and loose money) by the chances of mining a block that were announced.

You say that I'm correct about the Gambler's Fallacy but you are still talking about time. Hashrate and only hashrate matters for the probability of mining a block.

[chance with 50 PH/s for 3h] > [chance with 25 PH/s for 6h] > [chance with 5 PH/s for 30h] that is simply because you can remove "for xh".

The post should be edited to :

Chances to mine a block are :

at   1 PH/s --> 1 in 267.342 per block
at 2.5 PH/s --> 1 in 106,937 per block
at   5 PH/s --> 1 in  53,468 per block
at  10 PH/s --> 1 in  26,734 per block
at  25 PH/s --> 1 in  10,694 per block
at  50 PH/s --> 1 in   5,347 per block

and yet I didn't check the latter, it could be worse.

The calculation in "solochance.com" is also wrong. I don't know if it's intentionally to just encourage people to use a solo-mining service.

Hello,

For me there is a huge mistake in the calculation of the winning chances :


You can't say for example that there are 144 blocks mined each 24h (=1 each 10 min) and thus if we run the miner 24h non-stop we multiply our chances by 144.
Yet this is the reasonning applied as for example : with a hash rate of 50 PH/s --> chance per block = 1/5347 --> chance per 24h = 144/5347 = 1/37 which is false.

Since the draws are independent for mining each new block, the chances are constant as long as the hash rate is constant and no matter how many times you repeat the mining attempts.

There is a topic in wikipedia that gives a better explanation : https://en.wikipedia.org/wiki/Gambler%27s_fallacy

If the project of @Willi9974 is also based on the assumption that we increase the chances by mining for longer periods of time, then a lot of people might be loosing their money.

JeanLuc already gave the ressources that were needed to solve puzzles 110 and 115 using his algorithm :

#120 --> 60  days using 256 Tesla V100 (not yet solved, only prediction)
#115 --> 13  days using 256 Tesla V100
#110 --> 2.1 days using 256 Tesla V100

For the other puzzles, it will depend on which algorithm was used and on ressources involved.

I'm also curious to know how long it would take to solve each of the puzzles from 1 to 120 using JeanLuc's algorithm. Then, one can derive a simple law of complexity of the puzzle.

If r is wrong then s is also wrong.

The right s should be 99827946738399009248825444711200031423675392728917187111450168157978195192231.

If you are using both wrong r and s, you are just balancing the equation to get d.

r is wrong.

ECDSA multiplication using k*Gpoint gives :

R=(42804120235550333264601566912095829673031312040987116166863779393812842042729, 68663269101170998966556989191669958292218975994528865773618353809041762691493)

thus r=Rx=42804120235550333264601566912095829673031312040987116166863779393812842042729

Simply the concatenation of (version+previous_hash+merkle_root+tim_stamp+target_difficulty+nonce) called candidate block header should give the right target number of leading zeros after applying double_sha256.

If you are asking about the theory, here is a link to understand step by step how to build a header. I've never found anything giving a better explanation to start with :
 https://medium.com/fcats-blockchain-incubator/understanding-the-bitcoin-blockchain-header-a2b0db06b515

It's just the theory behind the process for bitcoin. In reality folks use dedicated hardware (asics) and thousands of them to have any chance of succeeding before the others. The discussion in this post was about the probability of success.

Thanks @kano, @a1 Hashrate LLC2022, @NotATether.

My intention was also to have a post that anyone googling mining difficulty can find.

I recommend these two articles that studied statistically the mining difficulty problem :

- https://www.zora.uzh.ch/id/eprint/173483/1/SSRN-id3399742-2.pdf
- https://doi.org/10.2139/ssrn.3399742

Conclusion is that the Hypergeometric Distribution is the correct model and not Poisson Distribution as commonly accepted (also assumed in Satochi's white paper).
Nevetheless, I agree that the way I stated the problem is incomplete. We should also do the calculation "knowing that" there is competition with X hash power.

Overall, I agree that the ratio of own hash power to the network hash power can be a good approximation.

Let's assume we try to mine the next block after block No.749256 whose hash is : 00000000000000000009b06cb40e4302fc0dab3f8031f058351e904e14be2b45.
  --> current difficulty is 19 leading zeros (76 zero bits=19*4) out of 256
  --> the size of the population is N=2^256

In big-endian representation, double_sha256 outcome should have 76 ending zeros. This is equivalent to saying that the leading 180 bits can be any number
  --> total number of possible solution is K=2^180

Let's assume we use one Antminer S19 PRO with a hashpower of 110TH/s for 10 min
 --> total number of attempts is n=66*10^15

One double_sha256 outcome that fulfills the difficulty requirement is sufficient
 --> k=1

To sum up the mining problem, here are the parameters to calculate the probability of mining a block in 10 min :

  N is the population size                                                            =  2^256
  n is the number of draws (double_SHA256 checks)                     = 66*10^15
  K is the number of known success states in the population          = 2^180
  k is the number of wanted successes                                         = 1


This problem is dealt with in probability theory and statistics by the hypergeometric distribution (definition from wikipedia):

The formula for the calculation is available on wikipedia : https://en.wikipedia.org/wiki/Hypergeometric_distribution

Is anyone able to calculate the result for the example I have given ? The values seem too big using Python or Matlab.

We find references to this early post regarding the difficulty of mining but it doesn't give a rigourous answer https://bitcointalk.org/index.php?topic=1682.0.

Kind regards

Hi,

I would like to understand how one can verify that bitcoins in a given address are unspendable.

To me, there are N points on the field of the elleptic curve. That makes (N+1)/2 points with distinct x coordinates (=half side of the symetrical field)

Therefore, there are (N+1)/2 points left, such as (x,y)!=k*G with k in [0,N].

For example:

If I pick x=0 (for which I'm almost sure it cannot result from k*G), we can derive two points :

P1=(0 , 64828261740814840065360381756190772627110652128289340260788836867053167272156)
Adress1=15wJjXvfQzo3SXqoWGbWZmNYND1Si4siqV

P2=(0 , 50963827496501355358210603252497135226159332537351223778668747140855667399507)
Adress2=1MqALQs6ea1ACgwRurqgaBDWzxYPoXCXzu

These adresses are valid (even active in the blockchain). However, they don't have a private key.

Then, is it possible to be sure that a public key has a private key (i.e. derived from k*G) ?

Regards,

Mr. Akaki

Hi,

One question regarding the performance of the algorithm.

It's stated that for puzzle #120, the :
This is really mind boggling  . But does someone know how long it took  (or a time approximation) to solve puzzle #115 using 4 Tesla V100 ?

To me it took (60/2^5)*(256/4)= 4 months, which is surely not reasonnable.

Thanks, I updated my modinv function.

conclusion of discussion:

The N*G result for k=1 is false, and just coincidence.

Yes, indeed I calculate (-k*G + k*G) as any other EC addition using this function :


It seems to work for K=1 as I get N*G (verified by EC multiplication).

What would be the modification to have the correct result for any K ? If it's not supposed to be always the same, does it have any link with k=1 ?

Aditions of the pairs (-k*G, k*G) give each time a different (x,y) result, so please don't add entropy to the discussion.

Maybe the zero infinity point is just an abstract notion and therefore we are not allowed to calculate (-k*G + k*G) as a normal addition.

Yet, having -1*G + 1*G = N*G could help finding a relationship with -k*G + k*G that gives a point with arbitrary-looking cooridnates. An example was given with k=2.
Any help is welcome after verification.

I'm not sure about that, we can also write:

Therefore, there is probably a different "infinity" point for each pair (-k*G, k*G), which is in accordance with the fact that addition of x-axis symetrical points forms parallel lines.

However, in reality with k=2, we get a point not equal to 2N*G and with no apparent link to N*G :
 -2*G + 2*G=(49667982834466148699028630885550314015746939561788444090107179747772288677390, 37758011528734597361759657276645959964664126776856991748971785837209648797521).

So for me the question still needs clarifications.

Before generalizing the formula to any K<N, let's just understand what happens with k=2 that is different from k=1.

yes, by -1*G, I mean  also (N-1)*G.

I'm sure of my calculations. At least the apparent result is that (-k*G+k*G)= N*G only for (k=1). This could be possible since the addition of pairs (-k*G,k*G) on the curve form parallel lines.

Then, the question is about the link between the sums.

For K=1:
(20860373710434931919338205163613943089612844706565330860427609212248504954008, 28589774168867891354814021154080592739878697919018203946384876578134205873990) = N*G

For K=2:
(49667982834466148699028630885550314015746939561788444090107179747772288677390, 37758011528734597361759657276645959964664126776856991748971785837209648797521) = x*G

Are you talking world wide ?

Well, to give an idea, the bank access rate in middle to low income countries is less than 50%. We are talking about a population where 1 person out of 2 is not having a payement card and using only cash.
So, for now a full adoption of bitcoin is just utopic.

Hello,

I need a math clarification please.

Since the points on the Elliptic Curve (secp256k1) form a group, we can apply the laws of addition, substruction and multiplication.

This require a zero.

I checked that -1*G+1*G=N*G (with N=0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141).

Therefore, could we consider N*G as the zero ?

If yes, then why -2*G+2*G = M such as there seems to be no link between M and N.

Generaly speaking, is there any link between (-1*G+1*G) and (-k*G+k*G) ?
 

Hi,

we can read in [https://en.bitcoin.it/wiki/Private_key] the following:


However, in reality even the full 256 bits range and beyond work.
For Example, using 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF, we get the address 1PRWyFKTsQSJaUdX9VKgQNw8JERPw2kMFm that is valid (even transacted before).

As far as I understood, in ECDSA calculations we use %N, therefore we loop, and there is also a prviate key < N that also gives the same address 1PRWyFKTsQSJaUdX9VKgQNw8JERPw2kMFm.

am I right ?