|
It just occurred to me: Removing the limit opens up bitcoin network for cheap DOS attacks.
Instead of lengthy rants, please show how the network will be attacked, and what would prevent disruptions from happening.
|
|
|
|
I'm curious if they would manage even a single bit ECDLP with Shor's algorithm. As mentioned on the website 3-bit would be a breakthrough. Error-prone qubits - Today's qubits have 99% - 99.9% fidelity - is that good enough?
99.9% fidelity might be enough for lg2(1000)=10 bit RSA via Shor's, maybe, sometimes. For a 25 bit one would need 99.999997% fidelity, not only in qubits, but Toffoli (or whatever) gates as well. I'm not sure what these 99.9% mean though. In what time frame is the error so low? After all, more time equals more noise. If I got it correctly, let it be 99.9% for 1 nanosecond, it would get down to 99% in just 10 nanoseconds, then 90% in 100 ns, and then is kinda gone with 1% in 1 microsecond. Meanwhile there's a few million dollar prize on finding any real world use of quantum computers - by google & xprize The quantum computer scam continues. |
|
|
|
I am concerned that quantum computing could potentially brute-force all existing wallets. However, I am unsure whether internet connection speed would impose a limitation on such attacks. If not, how will the Bitcoin community protect itself against this threat? Additionally, how can I contribute, follow existing projects working on this issue, or learn more about this topic?
Quantum computing doesn't scale. It just generates noise. Shor's algorithm, which is supposed to break ECDSA, fails miserably with any presence of noise, even in theory. Hence the largest integer reliably factored up to now by a quantum computer using Shor's is 21. All those new and "very superior" QC managed only to generate more noise. |
|
|
|
|
Neither.
NTRU and Kyber are PKE/KEM - Public Key Encryption / Key Encapsulation Mechanism.
You should rather look at:
FIPS 204, ML-DSA, former Dilithium
FIPS 205, SLH-DSA, former SPHINCS+
FIPS 206, FN-DSA, former FALCON, not yet standardized
|-------------------+-------------+------------+-----------+----------+-----------|
| | Private Key | Public Key | Signature | security | average |
| | bytes | bytes | bytes | bits | block MB* |
|-------------------+-------------+------------+-----------+----------+-----------|
| secp256k1 | 32 | 32 | 64 | 128 | 2 |
|-------------------+-------------+------------+-----------+----------+-----------|
| ML-DSA-44 | 2560 | 1312 | 2420 | 128 | 78 |
| ML-DSA-65 | 4032 | 1952 | 3309 | 192 | 110 |
| ML-DSA-87 | 4896 | 2592 | 4627 | 256 | 150 |
|-------------------+-------------+------------+-----------+----------+-----------|
| SLH-DSA-SHA2-128s | | 32 | 7856 | 128 | 164 |
| SLH-DSA-SHA2-192s | | 48 | 16224 | 192 | 339 |
| SLH-DSA-SHA2-256s | | 64 | 29792 | 256 | 622 |
|-------------------+-------------+------------+-----------+----------+-----------|
| Falcon-512 | 1281 | 897 | 666 | 128 | 33 |
| Falcon-1024 | 2305 | 1793 | 1280 | 256 | 64 |
|-------------------+-------------+------------+-----------+----------+-----------|
* could be off by a factor of 2
|
|
|
|
However, the same method won't work for p-value in secp224k1 for some reason: p=0xfffffffffffffffffffffffffffffffffffffffffffffffeffffe56d
n=0x10000000000000000000000000001dce8d2ec6184caf0a971769fb1f7
p%4=1 (failed, expected 3)
p%9=1 (failed, expected 7) If all of those curves were generated together, then why p-value for secp224k1 was picked differently, than for three other curves? And how to efficiently compute square roots and cube roots for this curve? Also, how to proceed with all n-values? I heard there are some algorithms, to compute those results for any values, but if those curves were selected specifically, to make operations like that "fast", then everything should be solvable by simple equations like "(p+x)/y", similar to "(p+1)/4" and "(p+2)/9", right? There are "complex" algorithms: A remark on the computation of cube roots in finite fieldsOne could solve the square and cube root in this case by "simple equation" too. To my knowledge this is not published anywhere. The smallest pair x & y for square root is (p+3)/8; and for cube root is (p+8)/27. r4 and r9 are non-trivial 4th and 9th roots of 1 mod p more info
r4 = 11913830147633844989339888812832642491211314989669855304438134084459
r9 = 452128346974922831777605865588626403245808317223927710376180600773
b2 = a (mod p)
if a(p-1)/2 = 1 ; if square root exists
b = a(p+3)/8
if b2 != a
b = b * r4
b3 = a (mod p)
if a(p-1)/3 = 1 ; if cube root exists
b = a(p+8)/27
if b3 != a
b = b * r9
if b3 != a
b = b * r9
|
|
|
|
The question is: does it mean that there is some kind of connection between y^2=x^3+7, and for example y^2=x^3+2? Or maybe there is another connection, where points on curves with identical p-value and n-value can be mapped? Does it mean, that if we have b=0x7, where there are "n" points, and for example b=0xc curve also has the same amount of points, then does it mean we can map them 1:1?
For y2=x3+d (mod p), and d being non-zero integer, the group falls into one of these different sets:
1: 2x 2 * 3 * 20412485227 * 83380711482738671590122559 * 5669387787833452836421905244327672652059
2: 3x 3 * 132 * 3319 * 22639 * 1013176677300131846900870239606035638738100997248092069256697437031
3: 109903 * 12977017 * 383229727 * 211853322379233867315890044223858703031485253961775684523
4: 3 * 199 * 18979 * 5128356331187950431517 * 1992751017769525324118900703535975744264170999967
6: 14x 2 * 7 * 10903 * 5290657 * 10833080827 * 22921299619447 * 41245443549316649091297836755593555342121
7: 115792089237316195423570985008687907852837564279074904382605163141518161494337
Here ' x' is the torsion group - then the group is noncyclic (as a whole). One can move between different d by multiplying the whole equation by k6, and getting the new coordinates with the new d (the usual isomorphism):
y2 = x3 + d
k6*y2 = k6*x3 + k6*d
(k3*y)2 = (k2*x)3 + k6*d
Trying to move between these six groups doesn't work - either k3 and/or k2 are outside the usual group of numbers mod p. If one thinks a bit it is obvious. Groups have different number of points, so - when trying to map - every point from one group corresponds to all the points in another. So, only thing needing in order to jump to an isomorphic equation is taking sixth root of some number a (mod p).
ap = a
ap+1 = a2
a(p+1)/4 = a1/2
ap+2 = a3
a(p+2)/9 = a1/3
(a(p+1)/4)(p+2)/9 = a1/6 = k
One should then check if this root exists, i.e. if k6=a |
|
|
|
I mean lots of words explaining it. Here is the code I made back in 2019, this is slower than the 5x52 version (it is 8x32), but was faster than x p-2. __device__ static void invModP_(unsigned int value[8]) {
//INPUT : Prime p and a in [1, p−1].
//OUTPUT : a^−1 mod p.
//1. u = a, v = p.
unsigned int u[8], v[8];
copyBigInt(value, u);
copyBigInt(_P, v);
//2. x1 = 1, x2 = 0.
unsigned int x1[8] = { 0,0,0,0, 0,0,0,1 };
unsigned int x2[8] = { 0,0,0,0, 0,0,0,0 };
//3. While (u != 1 and v != 1) do
for (;;) {
if ( ((u[7] == 1) && ((u[0] | u[1] | u[2] | u[3] | u[4] | u[5] | u[6]) == 0)) ||
((v[7] == 1) && ((v[0] | v[1] | v[2] | v[3] | v[4] | v[5] | v[6]) == 0)) )
break;
//3.1 While u is even do
while ((u[7] & 1) == 0) {
//u = u/2.
shift_right(u);
unsigned int carry = 0;
//If x1 is even then x1 = x1/2; else x1 = (x1 + p)/2.
if ((x1[7] & 1) != 0) {
carry = add(x1, _P, x1);
}
shift_right_c(x1, carry);
}
//3.2 While v is even do
while ((v[7] & 1) == 0) {
//v = v/2.
shift_right(v);
unsigned int carry = 0;
//If x2 is even then x2 = x2/2; else x2 = (x2 + p)/2.
if ((x2[7] & 1) != 0) {
carry = add(x2, _P, x2);
}
shift_right_c(x2, carry);
}
//3.3 If u >= v then: u = u − v, x1 = x1 − x2 ;
unsigned int t[8];
if (sub(u, v, t)) {
//Else: v = v − u, x2 = x2 − x1.
sub(v, u, v);
subModP(x2, x1, x2);
} else {
copyBigInt(t, u);
subModP(x1, x2, x1);
}
}
//4. If u = 1 then return(x1 mod p); else return(x2 mod p).
if ((u[7] == 1) && ((u[0] | u[1] | u[2] | u[3] | u[4] | u[5] | u[6]) == 0)) {
copyBigInt(x1, value);
} else {
copyBigInt(x2, value);
}
}
/*
INPUT : Prime p and a in [1, p−1].
OUTPUT : a^−1 mod p.
1. u = a, v = p.
2. x1 = 1, x2 = 0.
3. While (u != 1 and v != 1) do
3.1 While u is even do
u = u/2.
If x1 is even then x1 = x1/2; else x1 = (x1 + p)/2.
3.2 While v is even do
v = v/2.
If x2 is even then x2 = x2/2; else x2 = (x2 + p)/2.
3.3 If u >= v then: u = u − v, x1 = x1 − x2 ;
Else: v = v − u, x2 = x2 − x1.
4. If u = 1 then return(x1 mod p); else return(x2 mod p).
*/
|
|
|
|
|
Because 0x1110...f784 has many small factors:
2^2 * 17 * 4289 * 6196937 * 9672199247 * 441571470858719851994038335827739586159888848835828007
While 0x1b88...e5e9 has factor 3, and then some unholy big numbers.
Your funny random mapping then produces some random integer, which is very very unlikely to have one of the big factors in the second one.
That said, what is the purpose of this exercise?
Point coordinates are not integers, they are instead infinite sets of all kind of numbers, represented by integers.
Specially y^2 = x^3 + 7 does not have integer or rational number solutions. Plugging integers makes even less sense here.
Why not use an isomorphic curve of rank>0, i.e. y^2 = x^3 - 2. Then at least you'd know that there are rational solutions, and have a single nice generator (3,5).
|
|
|
|
|
There is an elliptic curve equation, which is taken modulo P. This produces a group with N points.
Now you'd like to change the modulo to N, and get a group with P points.
Congratulations! There are many many such curves.
But there's a caveat.
Taking something modulo P does not produce an integer. Instead the result is a "number modulo P". The "something" could be any of infinite numbers, both positive, negative, rational, irrational, etc.
So the real curve could be y^2 = x^3 + kPx + B, which reduces to y^2 = x^3 + B (mod P), and you could vary k in order to get the desired number of points modulo N. Or in a rare cases y^2 = x^3 + kPx + B + mP, if more flexibility is needed.
That means: the curves in different modulo are not related in any way.
Any curve in one modulo is equivalent to any curve in any other modulo.
Zero bits of information are gained here.
Edit:
BTW, there is no curve possible with P=97 and N=67 or vice-versa. The number of points possible lays in the interval P+1±2√P, which gives [79, 117] mod 97, and [52, 84] mod 67.
|
|
|
|
Shor's algorithm with noiseless qubits and gates works in theory.
Shor's algorithm with noisy qubits and gates does not work in theory. It needs exponentially small noise.
Both in theory.
That's it.
I thought that this is what error correction fixes-- with a huge but only polynomial blow up. If I understand it correctly, the error correction could reduce noise only in linear fashion - QC are analog machines - ten times more resources would reduce error only tenfold at most. For Shor's to work this is not enough at all - it needs exponentially smaller noise. |
|
|
|
You got it wrong. RSA-2048 is not vulnerable to QC even theoretically.
Now you're just talking nonsense. Shor's algorithm factorizes n-digit numbers on a theoretical QC in time O(n^2 * log n * log log n) [1]. Which can in theory factorize numbers of tens of thousands of digits. This is correct only with ideal noiseless qubits and gates. That's exactly what a "theoretical QC" is. Hence, your claim of "not vulnerable to QC even theoretically" being wrong. Shor's algorithm with noiseless qubits and gates works in theory. Shor's algorithm with noisy qubits and gates does not work in theory. It needs exponentially small noise. Both in theory. That's it. |
|
|
|
You got it wrong. RSA-2048 is not vulnerable to QC even theoretically. Neither is RSA-128 - yes only 128 bits are beyond Shor's algorithm even in theory.
Now you're just talking nonsense. Shor's algorithm factorizes n-digit numbers on a theoretical QC in time O(n^2 * log n * log log n) [1]. Which can in theory factorize numbers of tens of thousands of digits. This is correct only with ideal noiseless qubits and gates. Shor's algorithm fails when exponentially small noise is present. That is, it needs noise levels of the order 2 -n. The same is true for ECDLP. Good luck achieving noise level 2 -256. It is very easy to figure out why that happens. We start with qubits which are independent, each representing only 1 bit of information. But before reaching the final result it is not yet clear which of the 2 n possibilities are the correct ones. So midway of the quantum computation, qubits have to represent 2 2n states at the same time. This enormous amount of information vanishes with any noise present. Read the last sentence in this section https://en.wikipedia.org/wiki/Shor%27s_algorithm#Physical_implementation. |
|
|
|
they might not factor 10^1000 size numbers but 2048 bit numbers are an entirely different animal and should be vulnerable to quantum computers at some point. very vulnerable. the only question is, when do companies like atom computing scale up past 1000 qbits to say 1 million qbits. i'd say in the next 10 years at worst.
they went from 100 qbits to 1000 in like 2 years.
You got it wrong. RSA-2048 is not vulnerable to QC even theoretically. Neither is RSA-128 - yes only 128 bits are beyond Shor's algorithm even in theory. Current QC hardware struggles with RSA-6 (six bits). Finally someone did put the noise into quantum equations and this is the result: We consider Shor's quantum factoring algorithm in the setting of noisy quantum gates. Under a generic model of random noise for (controlled) rotation gates, we prove that the algorithm does not factor integers of the form pq when the noise exceeds a vanishingly small level in terms of n - the number of bits of the integer to be factored, where p and q are from a well-defined set of primes of positive density. We further prove that with probability 1−o(1) over random prime pairs (p,q), Shor's factoring algorithm does not factor numbers of the form pq, with the same level of random noise present.
|
|
|
|
Humanity developing a quantum computer strong enough to break ECDSA seems far more likely than someone finding an effective alternative to Shor's algorithm for classical computing tho.
It is exactly the opposite. Quantum computers are likely never going to do any useful cryptography related stuff. And Shor's algorithm is yet to be implemented, it exists just on paper, and very small and truncated versions happened. With current hardware, to even have a theoretical chance at ECDLP, one needs more than 28*10 15 qubits - this is 28 Peta qubits. Even with ideal, zero noise QC, one needs 126*10 9 Toffoli gates. And something more about the all-hyped Shor's algorithm: We consider Shor's quantum factoring algorithm in the setting of noisy quantum gates. Under a generic model of random noise for (controlled) rotation gates, we prove that the algorithm does not factor integers of the form pq when the noise exceeds a vanishingly small level in terms of n - the number of bits of the integer to be factored, where p and q are from a well-defined set of primes of positive density. We further prove that with probability 1−o(1) over random prime pairs (p,q), Shor's factoring algorithm does not factor numbers of the form pq, with the same level of random noise present.
Well, looks like even quantum error correction wouldn't help with ECDLP. All quantum hope is gone. |
|
|
|
How do you create a "coinbase tx"? Can it be built via createrawtransaction or can it only be created in code? Then I don't fully understand how to build this transaction.
Create it manually: createrawtransaction doesn't allow you to set the script of the input. version: 02000000
marker: 00
flag: 01
txIns:
num: 01
in-1:
txid: 0000000000000000000000000000000000000000000000000000000000000000
index: ffffffff
script:
length: 31
block-height-BIP34: 03 ed630c
extra-nonce: 04a95e29652f466f756e6472792055534120506f6f6c202364726f70676f6c642f1a0727769676000000000000
sequence: ffffffff
txOuts:
num: 02
out-1:
value: 46edf02500000000
script:
length: 16
P2SH: 00 14 35f6de260c9f3bdee47524c473a6016c0c055cb9
out-2:
value: 0000000000000000
script:
length: 26
OP_RETURN: 6a
OP_PUSH_36: 24
commitment-header: aa21a9ed
commitment-hash: 95c53abf59b8c6df571b1ca9ff8ad0e6f77a82b2b59c229463cda7a0281a4caf
witness:
count: 01
witness-1:
length: 20
data: 0000000000000000000000000000000000000000000000000000000000000000
locktime: 00000000
There are enough books explaining all this. I suggest to look inside "Programming Bitcoin" before asking here. |
|
|
|
What happens if such solution is found?
Nothing. Anybody finding it would keep silent. The incentive to not spill out the secret is just too big. Is there any alternatives to replace ECC?
|-------------+-------+-------+-------+----------+-------+-------+-------+----------|
| Name | PrivK | PubK | Sig | Security | PubK | Sig | block | average |
| | bytes | bytes | bytes | bits | *secp | *secp | *secp | block MB |
|-------------+-------+-------+-------+----------+-------+-------+-------+----------|
| secp256k1 | 32 | 32 | 64 | 128 | 1.0 | 1.0 | 1.0 | 1.3 |
|-------------+-------+-------+-------+----------+-------+-------+-------+----------|
| RSA 2048 | 512 | 256 | 256 | 112 | 8.0 | 4.0 | 6.0 | 7.8 |
| RSA 3072 | 768 | 384 | 384 | 128 | 12.0 | 6.0 | 9.0 | 11.7 |
|-------------+-------+-------+-------+----------+-------+-------+-------+----------|
| Dilithium2 | 2528 | 1312 | 2420 | 128 | 41.0 | 37.8 | 39.4 | 51.2 |
| Dilithium3 | 4000 | 1952 | 3293 | 192 | 61.0 | 51.5 | 56.2 | 73.1 |
| Dilithium5 | 4864 | 2592 | 4595 | 256 | 81.0 | 71.8 | 76.4 | 99.3 |
|-------------+-------+-------+-------+----------+-------+-------+-------+----------|
| Falcon-512 | 1281 | 897 | 666 | 128 | 28.0 | 10.4 | 19.2 | 25.0 |
| Falcon-1024 | 2305 | 1793 | 1280 | 256 | 56.0 | 20.0 | 38.0 | 49.4 |
|-------------+-------+-------+-------+----------+-------+-------+-------+----------|
| Sphincs+ | 64 | 32 | 7856 | 128 | 1.0 | 122.8 | 61.9 | 80.5 |
| Sphincs+ | 96 | 48 | 16224 | 192 | 1.5 | 253.5 | 127.5 | 165.8 |
| Sphincs+ | 128 | 64 | 29792 | 256 | 2.0 | 465.5 | 233.8 | 303.9 |
|-------------+-------+-------+-------+----------+-------+-------+-------+----------|
|
|
|
|
lambda and beta are non-trivial cube roots of 1 modulo n and p. λ 3 = 1 (mod n) β 3 = 1 (mod p) [λ](x,y) = (βx,y) Since there are 3 of each you'd have to match them (2 are non-trivial, so there is just one equality check). You could find how to get such root of 1 here. So, let your curve is modulo q, and has order m, both prime numbers. Compute a primitive root of 1 modulo q: a≠1 a q-1 = 1 (mod q) Then the cube root of 1 would be: k = a (q-1)/3 = 1 1/3 (mod q) Instead of finding a primitive root of 1, one could directly find a cube root of 1, this is faster: k = (-1-sqrt(-3))/2 (mod q) Do the same modulo the order of the curve m: b≠1 b m-1 = 1 (mod m) λ = b (m-1)/3 = 1 1/3 (mod m) Then check which one matches: [λ](x,y) = (kx,y) β = k or [λ](x,y) = (k 2x,y) β = k 2 (mod q) |
|
|
|
This is a segwit transaction. Remove the marker, flag, and witness. https://github.com/bitcoin/bips/blob/master/bip-0141.mediawiki#user-content-Transaction_ID nVersion: 01000000
marker: 00
flag: 01
txins: 010000000000000000000000000000000000000000000000000000000000000000ffffffff5e03e7610c0446f724652f4d41524120506f6f6c2ffabe6d6d621175c7c1371ebd43cefcefc3ab0453b7f952101cb5575976420d0104e9f0dd01000000000000006ffead5c76d2571ade6aa17dc7be6bde12b33031f30094000000ffffffffffffffff
txouts: 02c2c0e825000000001976a9142fc701e2049ee4957b07134b6c1d771dd5a96b2188ac0000000000000000266a24aa21a9edaf182da3eb02887057bacf92ae319a024020f02c8d50537fe33f45f1c922e08d
witness: 01200000000000000000000000000000000000000000000000000000000000000000
nLockTime: 453007e0
|
|
|
|
|
Show Posts
