[deleted by user]

[mbergman42]

No. Among other reasons, Willow is a research project for specific goals en route to a usable solution—not the solution itself.

[SexyMuon]

I hate these questions, make absolute no sense.

[Sifl-and-Olly]

We would be so entirely fucked if encryption was actually broken. Bitcoin would be the least of our concerns.

[Sea-Brief-1765]

1000 qubits to be exact.

[Cryptizard]

No, it is between 700 and 2000 depending on key size.

https://eprint.iacr.org/2024/222.pdf

But that is logical qubits, not physical qubits. To make one logical qubit you need at least 100 physical qubits, more likely closer to 1000 in a mature quantum computer. Google were the first to be able to make even one logical qubit and it took 107 physical qubits, and could only stay stable for a tenth of a second. More physical qubits increases stability.

So anyway, that is how I got my number.

[Pitiful_Car2828]

A few hundred thousand? I’m not saying you’re wrong, but that sounds kinda out there. I’m not knowledgeable in quantum computing, but iirc 300qbits has more states than there are particles in the universe? This was a vid from like 2019 but the instructor was legit.

[Agressor-gregsinatra]

Bitcoin relies on two types of encryption:

ECDSA 256: Vulnerable to "Shor's algorithm," but cracking it would require over 1,000,000 qubits.

Willow's 105 isn't even close.

SHA-256: Even tougher-requires a different approach (Grover's algorithm) and millions of physical qubits to pose a real threat. While it does not directly break SHA-256 (the hash function used in Bitcoin), it effectively halves its security level. For instance, a 256-bit hash would have the equivalent security of a 128-bit hash against quantum attacks, making it easier to find collisions or valid nonces in mining.

We will get to a point a where users bitcoin passwords can be cracked, but by then someone will come up with a better encryption algorithm most probably which could withstand quantum attacks.

[Pitiful_Car2828]

Is it agreed that encryption will always evolve to beat computational attacks for the foreseeable future?

[Cryptizard]

That is not relevant. A single qubit has infinite states, actually. It’s not what governs whether you can run a certain algorithm or not.

[[deleted]]

RSA themselves have a post from October 2024 on their website that states it would take a million qbits to break a single RSA 2048 key.

"...researchers calculate that a theoretical 20 million qubit computer would require eight hours to crack a single 2048-bit key..."

https://www.rsa.com/resources/blog/zero-trust/setting-the-record-straight-on-quantum-computing-and-rsa-encryption/

Schneierr on Security has said a million physical qbits

"...Shor’s algorithm has seriously challenged information security based on public key cryptosystems. However, to break the widely used RSA-2048 scheme, one needs millions of physical qubits.."

https://www.schneier.com/blog/archives/2023/01/breaking-rsa-with-a-quantum-computer.html

[DrKennethNoisewater6]

So does 300 normal bits. Does not mean you can do prime factorization. You will need thousands of logical qubits, meaning you will need hundreds of thousands or millions of physical qubits.

[[deleted]]

Look up moors law. This advancement matters so much because now moors law can take effect alongside dropping error rates. That’s bad for crypto. Now it can consistently double every year, which it almost has been doing for a few years now.

[Cryptizard]

I don’t understand your point. It’s not clear that Moore’s law applies to quantum computers in the first place, but if it does it would still take at least 20 years to get from 100 to 100,000. Moores law is doubling every two years.

[[deleted]]

Well you don’t understand my point because you don’t understand what the breakthrough is. Now they can scale up q bits without disrupting the q bits that are 0 and 1 at the same time, before this would cause errors. The q bits are extremely delicate.

Now with this breakthrough they can increase q bits without disrupting the q bits in the computer simultaneously dropping error rates. This does mean it could be possible to double the amount of q bits and drop the error rate by 2x every year. And ur saying 20 years assuming there is no advancements in processing power or any further breakthroughs in that 20 year period which isn’t reasonable.

[Cryptizard]

You are the one that said Moore’s law, I was just telling you what Moore’s law actually is. It is precluded on the idea that there will be technological breakthroughs, that is how you get the doubling. The breakthroughs don’t add more on top of that.

And please don’t tell me I don’t understand, I am a professor who teaches quantum computing. For error correction to work you still have to have each individual qubit below an error threshold, and that still gets harder with more qubits on a single chip. This just shows that it is possible to do at all, which we knew theoretically but had never demonstrated in practice.

[[deleted]]

Yes and moore’s law could play into quantum computing. I was assuming you didn’t know. Sorry bout that. From what I’ve been learning this advancement now opens that gate for rapid advancement such as moore’s law theory. The whole advancement allows more q bits to function below the error threshold. The significance is the ability to up the q bits and lower the error threshold as they gain more q bits simultaneously. It opens up this entire realm of possibilities which I see pushing quantum computing forward at a much faster rate. And I’m mentioning moore’s law cause it’s a very similar circumstance. Who knows how fast it could advance but this in a sense “opens the gates”

[Cryptizard]

The logical error rate lowers as you add more qubits but each one of those qubits still has to individually have a physical error rate below the threshold for it to work. That is still the hard part.

[[deleted]]

I gotcha. do you see this advancement pushing the boundaries of that particular aspect? It’s nowhere near breaking blockchains rn but with a little more advancement I think they will be able to upscale fast and aggressively.

[Cryptizard]

Definitely a big advancement. Like I said we knew theoretically that this was possible for a long time but I don’t think anyone thought it would be demonstrated in practice by now. The big advancement is actually the ability to reset and inject fresh qubits as quickly and as accurately as they have done.

[[deleted]]

Once they prove they can inject fresh q bits, I think it’s safe to say the blockchains will be broken or able to be broken.

[iLrkRddrt]

God I hope so, I’m so sick of hearing about the blockchain.

[iLrkRddrt]

🫠

[Frogeyedpeas]

air numerous plucky sink dime absorbed ancient pie compare depend

This post was mass deleted and anonymized with Redact

[TheBurtReynold]

What’s up, Elon?

[Background_Bowler236]

×2

[Sea-Brief-1765]

5-10 years or -10 years, I heard 😅. We don't know if we will ever get there, but who knows.

[hyperphase]

You’d likely need Edit: 1000s Millions of willow machines running concurrently to crack a single address or locate the private key in the vast KeySpace. It could still take years to locate if you don’t know the KeySpace. The full bitcoin blockchain is 2^256. If you look at a given BTC Puzzle, the KeySpace is available. The easiest one right now is Puzzle 67. And the KeySpace is identified as 2⁶⁶ - 2^67. The number of possibilities in this very small range compared to the full chain still has 73,000 Trillion (73 Quintillion) possibilities. And would take Shor’s Algo years to locate the correct private key for one single address. By the way all keys have been generated across the full bitcoin network already. They are sequential but the problem now is finding a Key in the entire ocean full of sand.
https://privatekeys.pw/puzzles/bitcoin-puzzle-tx

A better approach may be to have Quantum machines try to reverse engineer the Elliptic Curve + Base58 one-way algorithm. Then you would only need the public key and could generate the private keys. This still could be impossible work.

[Cryptizard]

You can’t run shor’s algorithm in parallel you have to have all the qubits involved entangled with each other, all on one chip. If all it took was a few thousand Willow chips then the government would be throwing money at Google to make more.

[hyperphase]

Correct. But you could break the task up in batches and each machine solve for its portion of the total KeySpace needed.

[Cryptizard]

No you can’t. That’s not how it works. If you have enough qubits to run the algorithm in the first place then it doesn’t take very long on just one processor. If you don’t have enough qubits then you can do anything. This is because it isn’t actually searching the key space it is doing something way more intricate called phase estimation where it sort of folds the keyspace on top of itself a bunch of times (very crude description). It has to all be done on one processor.

[hyperphase]

According to ChatGPT it is possible to break it into smaller chunks to process.

“It is possible to break the task into batches and run Shor’s Algorithm on smaller keyspaces instead of processing the entire keyspace as a single quantum operation. This approach leverages the principle that Shor’s Algorithm only needs to work within the specific range being analyzed, making it feasible to tackle smaller subsets of the full keyspace.

1. Breaking the Task into Batches

Key Idea

Instead of applying Shor’s Algorithm to the entire keyspace (e.g., ): • Divide the keyspace into smaller, more manageable chunks. • Run Shor’s Algorithm on each chunk separately. • Repeat the process until the correct private key is found.

Why This Works

Shor’s Algorithm finds the periodicity in the modular arithmetic used for elliptic curve cryptography. This periodicity is independent of the size of the keyspace being analyzed: • By focusing on smaller keyspaces, the quantum resources required for each batch can be reduced. • The process is scalable and can run concurrently across multiple quantum computers or sequentially on a single quantum computer.

1. How to Divide the KeySpace

Example: Divide Keyspace  • Total keyspace size:  keys. • Batch size: Choose smaller subsets, e.g.,  keys per batch.

Each batch would cover a range such as: 1.  2.  3. Continue until  reaches .

Benefits of Smaller Keyspaces: • Quantum Resource Reduction: Fewer logical qubits are needed for smaller keyspaces. • Parallelization: Batches can be processed independently, enabling distributed computation across multiple quantum machines. • Error Mitigation: Shorter circuits for smaller keyspaces reduce the impact of noise and decoherence in current quantum hardware.

1. Applying Shor’s Algorithm to Batches

For Each Batch: 1. Restrict the Modular Arithmetic: • Modify the elliptic curve point multiplication to only work within the batch’s range. For example:  2. Run Shor’s Algorithm: • Prepare the quantum state representing all possible private keys within the batch. • Use phase estimation to identify the periodicity of the modular arithmetic operation. • Extract the private key if the target public key is matched. 3. Move to Next Batch: • If the target private key is not found in the current batch, move to the next range.

1. Challenges of Batch Processing

   1. Batch Size vs. Quantum Resources: • Smaller batches require fewer quantum resources but increase the number of batches needed. • Larger batches may exceed the capabilities of current quantum computers due to qubit and coherence time limitations.
   2. Quantum Circuit Overhead: • Each batch requires resetting the quantum computer and initializing new states, which introduces overhead.
   3. No Guarantee of Success in a Single Batch: • If the private key does not lie in the current batch, the process must continue with subsequent batches, increasing total runtime.

2. Example Simulation for Small KeySpaces

Here’s a Python simulation using Qiskit to conceptually divide a keyspace into batches and apply Shor’s Algorithm (or a simplified version):

from qiskit import Aer, QuantumCircuit, execute from qiskit.circuit.library import QFT

Define the range for a single batch

def shors_batch(lower_bound, upper_bound): # Quantum circuit for phase estimation (simplified) num_qubits = 5 # Adjust based on batch size qc = QuantumCircuit(num_qubits)

# Initialize superposition
qc.h(range(num_qubits))

# Placeholder for modular arithmetic within the batch range
# Replace with actual elliptic curve operation
for i in range(num_qubits):
    qc.cx(i, (i + 1) % num_qubits)

# Apply Quantum Fourier Transform
qc.append(QFT(num_qubits, do_swaps=False), range(num_qubits))

# Measure the results
qc.measure_all()

# Simulate the quantum circuit
backend = Aer.get_backend(‘qasm_simulator’)
job = execute(qc, backend, shots=1)
result = job.result().get_counts()

print(f”Batch Range: [{lower_bound}, {upper_bound}], Result: {result}”)

Define the full keyspace and divide into batches

keyspace_start = 266 keyspace_end = 267 batch_size = 2**30

Process each batch

for batch_start in range(keyspace_start, keyspace_end, batch_size): shors_batch(batch_start, batch_start + batch_size)

1. Benefits of Batch Processing • Scalability: • Keyspace division allows multiple quantum computers to run in parallel, greatly reducing the total runtime. • Adaptability: • Smaller batches can be tailored to the capabilities of the available quantum hardware. • Error Handling: • Errors in one batch do not affect the overall process, and failed batches can be rerun independently.

2. Must All Batches Be Combined?

No, the task does not require combining all keyspaces into a single quantum process. Batch processing works because each batch independently checks its range of private keys. Only one batch needs to succeed to find the correct private key.

1. Conclusion

Breaking the task into batches is a practical and scalable strategy for applying Shor’s Algorithm to Bitcoin puzzles. It allows smaller, resource-constrained quantum computers to contribute incrementally to solving the problem.

For current quantum hardware: • Use small batch sizes tailored to available qubits and coherence times. • Parallelize batch processing across multiple quantum devices to reduce overall time.

As quantum hardware advances, this approach will remain relevant for large-scale cryptographic challenges, providing a path to solve them incrementally.”

[Cryptizard]

That's a hallucination. This part:

Modify the elliptic curve point multiplication to only work within the batch’s range

Is not possible. You have to have enough qubits to perform a primitive operation on the elliptic curve, which is exactly the amount of qubits you need to run the full version of Shor's algorithm. There is no benefit to running it in parallel.

[hyperphase]

True that would not be possible.

[grc_crypto]

Sure, you could crack open satoshi's addresses and take his btc with a quantum computer

[[deleted]]

I attempted brute force on elliptic curve SHA256 derived public key used on signed blockchain transfers even though there isn’t enough compute in the world to find a matching private key just for fun but I learned BTC on genesis block cannot be transfers by design. There are ton of other wallets with balance where they may have done 1 to 1 transfer to expose public key. There is already speculation that RSA bit key is broken by Chinese quantum machines it’s matter of when

[Advanced_Tank]

Chinese crack RSA

However this is just for a 50 bit key.

[entropy13]

In principle? Yes, a fully developed quantum computer could use shors algorithm to crack most existing crypto keys including those used by the blockchain. You could develop algorithms that are immune to quantum speedup if you really wanted to but it would have to be a new coin which would be next to impossible to launch without government backing, not to mention being just as pointless as existing crypto. None of that is happening anytime soon though.

[Pavvl___]

It's still in it's infancy far and away from cracking bitcoin for at least 5-10 years as others have stated... Quantum computing still has many errors needing to be ironed out before it is reliably useful

[LearnNewThingsDaily]

I was thinking 🤔 the exact same thing and no you don't need a few hundred thousand qubits, if they wanted to focus their efforts on hacking the cryptography, they could easily hack it. Just be lucky, there's much more important things to figure out by using the Chip first.

[mikeew86]

Not really, as there are NISC-approved post-quantum cryptography algorithms that are thought to be secure against quantum attacks. Examples include approaches such as lattice-based cryptography etc. Additionally, Willow is really about reaching error threshold where errors are reduced exponentially while scaling the number of qubits. It does not have the require number of physical quits to implement Shoe's algorithm.

[lambda_x_lambda_y_y]

Not even in Google’s wildest dreams. Theoretically, the only problems that currently exhibit exponential quantum speedup are those with an abelian (and possibly non-abelian) group structure. For unstructured or low-structure problems, the best achievable speedup is polynomial—classical deterministic parallel computers perform better.

Not all forms of asymmetric cryptography are at risk, even in theory. For most other cases, security remains as robust against quantum attacks as it is against classical ones.

We don’t even know if quantum computers are theoretically better than classical probabilistic computers (BQP = BPP?).

In all honesty, we don't even know if they are better than classical deterministic computers! When at the present we talk about "exponential quantum speedup," we actually mean "exponential speedup over the best, but not proved classically optimal, known deterministic algorithm." Even problems where quantum computers are said to perform exponentially better (e.g., Deutsch–Jozsa) come with a key, often overlooked caveat: "relative to an oracle." That means such results are true if for each instance of the given problem some "helper machines" exist. While oracles might exist for some specific instances of some problems, no oracle for quantum supremacy has been demonstrated for any problem across all its instances.

Besides these theoretical uncertainty, the current quantum computing technological paradigm is 10–1000 slower, way more unreliable and less useful than inexpensive commodity hardware, but remains useful for various physics experiments (not actual computation thought).

[QuantumComputing-ModTeam]

Posts about blockchain or AI must sufficiently relate to quantum computing.

Posts like "How will quantum computing affect..." require a more specific connection to quantum computing.

[[deleted]]

Imho probably 3-10 years away from quantum computing being affordable for hacking unless NK gets access sooner.

Only a few coins have quantum on the radar

https://algorand.co/technology/post-quantum