Bitcoin Forum
January 31, 2023, 10:41:03 PM *
News: Latest Bitcoin Core release: 24.0.1 [Torrent]
 
  Home Help Search Login Register More  
  Show Posts
Pages: [1] 2 3 4 5 6 7 8 9 10 »
1  Bitcoin / Development & Technical Discussion / Re: Why do you think G/2 is so strange? on: January 04, 2023, 05:30:51 PM
But anyway what do you think about the goal of this anomaly?
There is no anomaly, since in secp256k1 all points (except the one at infinity) are equal. No point is more equal than others.

It seems as an easy way to check if your implementation is mostly correct - you try multiplying by 1/2, and then receive small x coordinate. Many things have to be implemented accurately, and any deviation would show up.
2  Bitcoin / Development & Technical Discussion / Re: Are UTXOs stored in a file? on: December 11, 2022, 04:38:49 PM
UTXO are stored in chainstate subdirectory, which is a LevelDB database, currently ~4.8GB.

One could control how much of it is cached by the command line parameter "-dbcache". It might be useful to make it high enough during IBD (initial block download). Note that high dbcache leads to slow shutdown of Bitcoin Core. Other than during IBD, AFAIK, high dbcache is useless.

There are no private keys in UTXO. Or if there ever were, it's all gone.

3  Bitcoin / Development & Technical Discussion / Re: secp256k1 library in pure assembly on: December 05, 2022, 05:48:07 PM
Ok, lets to to write it by parts using openAI

Code:
...
    addq num2(,%rax,8), %rdx
...
As usual, the so called AI gave wrong result. The carry flag is completely ignored, so instead it adds two vectors, each having four 64bit numbers.
4  Bitcoin / Development & Technical Discussion / Re: What is the lowest (non-zero) transaction fee you have ever used or seen? on: October 19, 2022, 06:02:53 PM
Anyone aware of lower fee examples (in 2022)?
Here is a transaction with fee exactly 1 sat from September 2022
https://mempool.space/tx/5d1c002042d56dd856870de97349b5995cd258d42be0c0a3a104ed8f2be047c0

5  Bitcoin / Development & Technical Discussion / Re: Exposed ... Mistakes or ... on: October 12, 2022, 12:19:00 AM
A bit off-topic but...

SAGE seems to have represented these finite fields and curves & operations really well. It would be nice if this  functionality could be had in other languages as well - especially C-C++ where there are many applications for this kind of thing because of its raw speed, but are hard to implement because all the crypto libraries for these languages are half-arsed or incomplete (libsecp256k1 is the closest that replicates SAGE stuff but a general-purpose curve and field library would be a nice to-have).


I have used PARI/GP C library
The following is with the provided gp shell (some empty lines omitted):
Code:
gp > ellgroup(ellinit([0,7]), 2^256 - 2^32 - 977)
%1 = [115792089237316195423570985008687907852837564279074904382605163141518161494337]
gp > factor(%1[1] - 1)
%2 =
[                                2 6]
[                                3 1]
[                              149 1]
[                              631 1]
[               107361793816595537 1]
[            174723607534414371449 1]
[341948486974166000522343609283189 1]

The easiest for me was doing pari_init_opts, then (after recording avma) using gp_read_str with corresponding string (instead of interfacing each and every function), and then pari_sprintf("%Ps",...) to get the result as text (then recovering avma), and parse it to something meaningful.

Couldn't find a function returning the multiplicative order of point though.
6  Bitcoin / Development & Technical Discussion / Re: My own Bitcoin WIF Missing Characters Help on: August 21, 2022, 06:24:17 PM
hello there
i have my own bitcoin address and public key and a WIF recognized as invalid
this txt file was old and recovered from my old HDD
i assume that the wif has more than 19 missing characters at known positions
is there is any chances that i can recover it ??
any guiding help will be appreciated Smiley

The Missing Characters ( Replaced By * ) Are as Follows :
5HpHagT65TZzG1P*********************EB3kEsreAnchuDf

Assuming you manage to tweak Pollard Kangaroo (don't know if it's possible, looks kinda tricky), here are the expected run times and cost (on-demand, spot instance could be 1/3rd of the price) when using AWS GPU instance p3.8xlarge (4x V100):
MC - missing characters, bits - equivalent missing bits
|MC|bits|ETA|$|
|14|82|00:11:17|2|
|15|88|01:25:53|18|
|16|94|10:54:07|133|
|17|100|3d 11:01:37|1,016|
|18|105|26d 08:18:52|7,740|
|19|111|200 days|58,942|
|20|117|4 years 68 days|448,893|
|21|123|32 years|3,418,664|
|22|129|242 years|26,035,770|
|23|135|1849 years|198,282,544|
|24|141|14083 years|1,510,074,752|

This was using my software (not published), Jean_Luc should be faster (50%?), newer hardware should be faster as well.
7  Bitcoin / Development & Technical Discussion / Re: Fail at coding my own Secp256k1 function (Pyhon) on: August 11, 2022, 05:18:23 PM
...
I got it, and  your suggestions are useful. I changed the code here and on Github. However It still doesn't work for small numbers (See the test case 1)
https://github.com/MaltoonYezi/Python-DSA/blob/main/Cryptography/SECP256k1Procedural.py
Sorry, for a delayed response

You got mistaken somewhere (or, as usual, in many places).

Test case 1 asks us to multiply (47,71) by 8 modulo 223 (with a=0, b=7). However with this prime the curve has structure 42x6, it is noncyclic.  Point (47,71) is from the group of (7,166); while (49,71) is from the group of (8,127). So, you could never reach either point from the other one.

You might want to change the test. If you insist on modulo 223, then b=5 is a good choice. Otherwise (b=7) use modulo 67 or 79, they are a bit like p and n in secp256k1, modulo one of them the group size is the other.

8  Bitcoin / Development & Technical Discussion / Re: Why does signature verification calculate the square root of y? on: August 03, 2022, 05:31:31 PM
No look, bitcoinsig.js that is used in the "brainwallet.github.io" sites has this in the verificaiton algo:
verify_message follows this algorithm ECDSA Public key recovery.

The function calling verify_message sets the first byte of signature to 27..34.
This corresponds to the eight cases, two for x (x or x+n, bit zero of recid), and two for y (y or p-y, bit 1, zero for even y, one for odd y), uncompressed or compressed (if first byte is >= 31).

At the end it returns the address of decoded public key.

You could see how Bitcoin Core does sign here
9  Bitcoin / Development & Technical Discussion / Re: Why does signature verification calculate the square root of y? on: August 03, 2022, 01:16:06 PM
To find square root mod p when p%4 = 3 (prime of secp256k1 curve is like that) you can compute x(p+1)/4 (mod p) instead.

I'm trying to grok my head around this.

We have y^2 = x^3 + 7 so before I wrote this topic I had the idea that the next statement took the 4th root of Right Hand Side (power by p+1 is equivalent to just 1, and I had the belief that coord^((p+1)/2) was equivalent to taking the square root - since we clearly cannot raise by the fractional power 1/2, but (p+1)/2 is equivalent to that).

In other words, (y^2)^((p+1)/4) would've been sqrt(y) not y. It's like in algebra how you apply the first sqrt and then you have (y)^((p+1)/2).

But apparently the p+1 is to ensure that modulus is zero, i.e. (p+1) % 4 = 0, and then the division by 4 is done. So how is dividing this shifted prime by 4 equivalent to a square root?

Is it because we are now taking the modular power by a whole number? Then why 4 specifically and not some other number?
It all comes from Fermat's little theorem:
yp = y (mod p)
then
yp+1 = y2 (mod p)
y(p+1)/4 = y1/2 (mod p)

You could do similar stuff for cube roots as well:
xp+2 = x3 (mod p)
x(p+2)/9 = x1/3 (mod p)

10  Bitcoin / Development & Technical Discussion / Re: Why PTLC when HTLC does the job on: August 02, 2022, 09:53:30 AM
This is the main disadvantage of HTLC:
When used to secure multiple payments (e.g. a routed LN payment or an atomic swap), all payments use the same preimage and hash lock. This creates a link between those payments if they’re published onchain or if they’re routed offchain though surveillance nodes.
Also using the same hash gives surveillance information for a single payment as well, by revealing parts of the path.

In contrast PTLC:
Each point lock can use different keys and signatures, so there is nothing about the point lock that correlates different payments either onchain or when routed offchain through surveillance nodes.
11  Bitcoin / Development & Technical Discussion / Re: "Trivial" points on Secp256k1 on: July 27, 2022, 10:07:31 AM
But, after learning a bit more about finding roots in finite fields I can now appreciate how there are three solutions (given Y) to this equation (modulo P):

    Equation B: X = (Y ** 2 - 7) ** 1/3

I'm still not sure what (if any) the corresponding operations are with private keys (i.e. what do you have to do to a private key to produce these "other" X co-ordinates?).

You could obtain the other private keys by multiplying by a non-trivial cubic root of 1 modulo n. Then y will be the same, and x will be multiplied by the corresponding non-trivial root of 1 modulo p.

Here are the two cube roots of 1 (besides the trivial 1) modulo n:
n2: 37718080363155996902926221483475020450927657555482586988616620542887997980018
n3: 78074008874160198520644763525212887401909906723592317393988542598630163514318
and their corresponding cube roots of 1 modulo p:
p2: 55594575648329892869085402983802832744385952214688224221778511981742606582254
p3: 60197513588986302554485582024885075108884032450952339817679072026166228089408

(X2, Y1) = n2 * (X1, Y1) = (p2*X1, Y1)
(X3, Y1) = n3 * (X1, Y1) = (p3*X1, Y1)
(X1, Y2) = -1 * (X1, Y1) = (X1, -Y1)
(X2, Y2) = -n2 * (X1, Y1) = (p2*X1, -Y1)
(X3, Y2) = -n3 * (X1, Y1) = (p3*X1, -Y1)

12  Bitcoin / Development & Technical Discussion / Re: ECDSA: Square roots, cube roots, clock (12th root), and other roots on: July 23, 2022, 02:20:38 PM
Why this value can be rotated like in a clock?
...
Are there other such values? How to get them? Is it possible to reach them for some other value like 2 or 3, for example to get it in five moves or in seven moves? Also, it is true for "n=fffffffffffffffffffffffffffffffebaaedce6af48a03bbfd25e8cd0364141", is it possible to get it based on "p=fffffffffffffffffffffffffffffffffffffffffffffffffffffffefffffc2f"?

There are many such values. Eventually what are you looking for is Primitive root modulo n. From it you can get every possible root of 1.

Here is an algorithm for finding a primitive root modulo prime p (that is (p-1)-th root of 1):
Code:
r = 1
factors = factor(p-1)
for [prime, power] in factors:
    x = (p-1)/prime
    y = (p-1)/(prime ** power)
    for (a=2;;a++):
        b = pow(a, x, p)
        if (b != 1):
            r = (r * pow(a, y, p)) % p
            break
(prime ** power = primepower)

Modulo p we get the following roots: 2 (square), 3 (cube), 7-th, 13341, 205115282021455665897114700593932402728804164701536103180137503955397371, and any multiple of these numbers, for a total of 25-1 = 31 possible roots (2nd, 3rd, 6th, 7th, 14th, 21st, 42th,...). Each k-th prime root has k-1 possible values besides 1. However if k is composite, some of the k-1 values are the corresponding smaller root, i.e. if a is 6-th root of 1, a3 would be square root of 1, and not 6th.

Modulo n we get the following factors (and roots): 26, 3, 149, 631, 107361793816595537, 174723607534414371449, 341948486974166000522343609283189. 7 * 26 - 1 = 447 possible roots. Your example is for 22*3=12-th root.

Here are two primitive roots of 1 modulo the corresponding prime:
n: rn = 106331823171076060141872636901030920105366729272408102113527681246281393517969
p: rp = 77643668876891235360856744073230947502707792537156648322526682022085734511405


So, let's say you want a 631th root of 1 modulo n: x = pow(rn, (n-1)/631, n). Since 631 is prime number, you could get all 631 possible 631-th roots of 1 (modulo n) by rising x to the power from 1 to 631.


13  Bitcoin / Development & Technical Discussion / Re: What is the drawback of PoS ? on: July 05, 2022, 07:22:03 AM
Cooling is solved. You place desalination facilities in the coast region, then you build pipelines into the deserts. Because not only do you need cooling, you also need water for all the inhabitants of those new mining oasis. And you need to clean the panels.
What about sandstorms? A single sandstorm could burry the whole mining facility. And they become more and more frequent.
14  Bitcoin / Development & Technical Discussion / Re: Thoughts on burner addresses on: June 08, 2022, 07:09:51 AM
Quote
Quantum computers cannot reduce anything. Quantum computers are just a scam hidden behind weird probabilistic equations, which are very conveniently excluding almost all real life noise. Quantum computers are so weak, that cannot factor a 6-bit number using the almighty Shor's algorithm - which "breaks ECDLP" - the number 35 turned out just too big for reliable factorization

Quantum Computers do not equal Shor's algorithm. I'm pretty sure if they really wanted to they could factor something bigger than 35 though. We're way past that.


Please show me anything quantum, that could factor big numbers (or even small); besides the obvious random search (adiabatic, annealing, etc), which doesn't scale, and is in fact faster on classical computers.

Who is this "we"? All I see is random buzzwords and utter failure. They wanted to factor, and failed miserably. Now there are 127 qbit computers. And they cannot factor 6 bit numbers.

Repeating buzzwords doesn't make it truth.

15  Bitcoin / Development & Technical Discussion / Re: Thoughts on burner addresses on: June 06, 2022, 12:32:51 PM
Quote from: pooya87
160 bit hash in addresses provides enough security, and that's the important part.
Right now it does. But not eventually. Quantum computer can reduce that to 80 bits.
Quantum computers cannot reduce anything. Quantum computers are just a scam hidden behind weird probabilistic equations, which are very conveniently excluding almost all real life noise. Quantum computers are so weak, that cannot factor a 6-bit number using the almighty Shor's algorithm - which "breaks ECDLP" - the number 35 turned out just too big for reliable factorization.
16  Bitcoin / Development & Technical Discussion / Re: Create a seed from a selection of words on: June 01, 2022, 10:40:14 AM
There cannot be more than 128 bits entropy in BIP39 12-words. There are not enough bits to represent it.
If you have selected each word manually and randomly and you have 12 words then each word represents 11 bits which makes the total 12*11=132 bits.
Yes, it is 132 bits, but only if there's no checksum or required version.

Quote
Quote
Electrum 12-word seeds have less than 128 bits entropy, IIRC it's slightly less than 132-8=124 for legacy addresses, and 132-12=120 for segwit addresses.
That is incorrect. Electrum actually starts with a 132-bit entropy (as an int) then increments it until it finds a correct checksum. Address type does not affect the entropy size, it only affects what checksum is expected.
https://github.com/spesmilo/electrum/blob/abe3955d916521f37e06b96d8996b270413e175f/electrum/mnemonic.py#L190
It very much affects the entropy, since 255 (or 4095 in segwit case) possibilities are rejected (plus the valid BIP39 ones, about one in 16, another loss of additional 0.0931 bits of entropy). You end up with smaller pool of possible seeds, hence smaller entropy.

It seems that entropy is a very tricky subject for many people. I'll give an example. Let's have a hypothetical seed generator, which starts randomly, and increments until it reaches only one specific seed. This is exactly 0 bits of entropy. If the generator stops when it reaches one of 2 seeds, we get 1 bit entropy. If an attacker has no information about these seeds, then he has to scan the whole 256 bit range (or whatever size it is in this case).

So, valid electrum seeds do have less entropy - 123.9 bits for standard, and 119.9 bits for segwit. That doesn't mean it's much easier to crack versus BIP39. If my calculations are correct, it's about twice harder to find a valid Electrum segwit seed versus both Electrum standard and BIP39. (if we are given an address to compare to)

In information theory, the entropy of a random variable is the average level of "information", "surprise", or "uncertainty" inherent to the variable's possible outcomes.

Certainly only one in 24 seeds are valid for BIP39, in 28.09 for Electrum standard, and in 212.09 for Electrum segwit. Hence the entropy is lower.

One might argue, that the attacker sees 132 bits of entropy, since nothing is certain for him. Then this is true for BIP39 as well, although it is generated using 128 bit entropy. Looking the other way if one insists BIP39 to have 128 bits entropy, then Electrum standard has 123.9, and segwit 119.9.
17  Bitcoin / Development & Technical Discussion / Re: Create a seed from a selection of words on: May 31, 2022, 10:06:01 AM
Which means that one must "preselect" another 3 bits. It would look like selecting the last word, taking it's 3 bits and then replace the last word by the final one.
Unfortunately you cannot finish the manual process after 23 words.
Other option is to see which of 8 "correct" last words you like the best.
Exactly, another solution would be doing something similar to what Electrum does. You select 12 words and then increment the last word until you get a valid checksum. As long as the selection process is really random the entropy you get is more than 128 bits.
Same for any other word count.
There cannot be more than 128 bits entropy in BIP39 12-words. There are not enough bits to represent it.

Electrum 12-word seeds have less than 128 bits entropy, IIRC it's slightly less than 132-8=124 for legacy addresses, and 132-12=120 for segwit addresses.

More entropy could be inserted, if you instead of using the 12 words directly mutate them with additional entropy. For example: make some letters lower case, while other upper case, change some words to "leet speak", etc. And then feed this into PBKDF2.

Of course, the easiest method of adding entropy is using password together with the seed.
18  Bitcoin / Development & Technical Discussion / Re: Create a seed from a selection of words on: May 28, 2022, 09:43:34 AM
To be more precise, we may say that if unknown word is on the last position, could be treated as a checksum word (word which contains binary checksum), then the rest (23 words) produce 8 possibilities at the last position.
Assuming the first 23 words are known, there are 8 possibilities for the last word on average.
It's not that there are always exactly 8 possibilities for the last word.
There are always exactly 8 possibilities for the last word for BIP39 (in the 24-word case).

Last word represents 11 bits, 8 of which are checksum. For every of the 3 bits we choose, there is always exactly one word with the needed checksum bits.
19  Bitcoin / Development & Technical Discussion / Re: Deep understanding for Bitcoin on: May 22, 2022, 11:19:53 AM
Additionally the new difficulty is constrained to be between [1/4, 4] times the old one. And cannot be less than 1.
new_difficulty = max(1, old_difficulty * min(4, max(1/4, (20160 / time_elapsed_for_last_2015_blocks))))

In the source actually the new target is calculated, which might give slightly different result than above formula due to rounding.

And that's done with 256-bit integers, or with proper doubles?

The rounding error shouldn't be that large if the difficulty is stored as an int with 256 bits, as the effect that the lowest bits of the difficulty have on the total hashrate at any given time is negligible.


Looked again and remembered, that the target is always represented as a "compact" number (32 bits, similar to float), so double should have enough bits. Possibly double arithmetic should be done in specific rounding modes though.

Then again - compact representation has only 23 significant bits, plus 8 bits exponent (and one sign bit). Instead of being power of 2, the exponent is power of 256. So things still might differ. Even more than I expected.
20  Bitcoin / Development & Technical Discussion / Re: Deep understanding for Bitcoin on: May 22, 2022, 07:23:18 AM
The actual formula is new_difficulty = old_difficulty * (20160 / time_elapsed_for_last_2015_blocks). 2015 blocks is a bug that will probably never be fixed.
Additionally the new difficulty is constrained to be between [1/4, 4] times the old one. And cannot be less than 1.
new_difficulty = max(1, old_difficulty * min(4, max(1/4, (20160 / time_elapsed_for_last_2015_blocks))))

In the source actually the new target is calculated, which might give slightly different result than above formula due to rounding.
Pages: [1] 2 3 4 5 6 7 8 9 10 »
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!