Does that mean you can fake Bitcoins or cryptocurrency transactions? What exactly could be affected by these vulnerabilities? Is there a better article anywhere that actually spells it out for the layman?
Quanta is a pretty popular, popular science outlet. It tends to be closer to the theory than (capital P, S) Popular Science magazine, but ultimately much of what they publish is digested to a degree for lay consumption.
They had an article just the other day about a more optimal sphere packing that was up my alley as a technical (programmer) person with a casual interest in broader pure math.
They do sensationalize a bit as a side effect of their process though, no argument there.
usually they are very thorough (for a magazine targeting curious well-motivated, but of course still a virtually completely laymen audience), but it seems recently their volume has increased whil quality stayed constant :)
From my cursory reading, it doesn't seem related to Bitcoin at all, but it might affect some more complex Ethereum protocols. Doesn't seem related to Ethereum itself, but it seems related to some zero-knowledge proofs.
edit: it seems to be related to something called "GKR protocol" that some cryptocurrencies use (?) - can use (?) - for somehow proving ... something? mining?.. using zero-knowledge proofs.... like here - https://www.polyhedra.network/expander (as usual in cryptocurrency, hard to tell what is actually being done/sold)
what I take from this, as a laic, is that... experimental ZK-proofs are indeed experimental.
Schnorr signatures, which Bitcoin uses, are based on the Fiat-Shamir transform, but I don't know enough about this attack to be able to tell whether there's any problem with that particular instance of it.
So the way Ethereum comes in is that the community at large is moving user activity to "L2s" - separate blockchains (sidechains) usually rolled up in and therefore secured by Ethereum Mainnet. Some of the newer L2s where apparently using this. So it affects Ethereum to the extent that its users could be bridging witg unsane protocols and implementations.
There are usually "bridge contracts" deployed on Mainnet to allow briding assets/tokens between them. This (besides obv exchanges) is where most of the ridiculous hacks and online theft of past few years have happened. The Axie/Ronin hack was a huge facepalm and should have been a lesson to be more wary of handwavy security claims of these more experimental networks.
No, this could not allow for faking Bitcoin or Ethereum TXs. This type of vulnerability mainly concerns "zero-knowledge" proof methods, which do not occur inside the Bitcoin or Ethereum base layers. Some teams are building ZK proofs on top of these and other blockchains though, so those systems could be vulnerable, though they are still largely experimental.
(Take this with a grain of salt as I only learned about the Fiat-Shamir heuristic via this HN thread last week https://news.ycombinator.com/item?id=44458168, and I only have basic experience in theoretical cryptography)
There exists the concept of a zero-knowledge proof: check out the Wikipedia page for some intuitive examples of how these work in an interactive context. Basically, by asking someone who wants to prove something (the prover) a bunch of questions (challenges), you can get probabilistic confidence that they actually know that thing: https://en.wikipedia.org/wiki/Zero-knowledge_proof#Abstract_...
You want it to be interactive because that makes it much harder for the prover to "fake it" on the spot. But it would be more convenient if you didn't need to be online and actively talking to each other - so we want a non-interactive way to do the same thing.
The Fiat-Shamir transform (or heuristic) says that we can transform interactive protocols into non-interactive ones by relying on "random" challenges. If the prover can't control the randomness, then it's about as good as you interactively challenging them (and you can e.g. make them do more challenges to make up for it).
How do we get randomness? In computing we don't really have anything totally random, but cryptographic hash functions are believed to be very difficult to predict the output to. So, in cryptography there's the "random oracle model" where you say, "Well, I don't know if this protocol is safe with these real-life hashes. But if the hash function was a truly random oracle, I can prove it's safe." (The Fiat-Shamir transform is only provably secure if you believe in the random oracle model).
In the past, researchers have constructed new protocols that are safe in the random oracle model, but once you use a real hash function they're breakable because of real-world implementation details. As the abstract of this paper says, "So far, all of these examples have been contrived protocols that were specifically designed to fail." See https://crypto.stackexchange.com/q/879 for some discussion of the mechanics of how it might happen, once you choose a real hash function.
This new paper advances the field by showing an attack that targets a real-world protocol that people actually use, GKR. It shows (and again, take my interpretation with a grain of salt) that when you pick a real hash function, the attacker can construct an input (circuit) that results in whatever output the attacker wants.
---
What's the real-world impact?
There do exist real non-interactive zero-knowledge proof systems, mainly used in blockchains. Instead of publicly exposing all the info to the world and doing computation on the (slow) blockchain, you can protect privacy of transactions and/or bundle a bunch of updates into a cheaper one (ZK-rollups). Theoretically these could be attacked using the methods described in the paper.
It's unclear to me whether those are affected here (though my guess is no, since they could have mentioned it if so).
Probably - but you are likely to be caught as eventually someone will verify your work with a non-broke program. I'm not clear exactly how likely that is (I'm not interested enough in cryptocurrency to bother to dig into the algorithm, but IIRC several different parties need to agree on a transaction before it is considered real - or something like that, I hope I sound confused), but if you are doing a lot of bitcoin fraud someone will notice.
A security researcher showed me years ago that blockchains were hackable. I don’t remember the proof, but since then have had low interest in crypto or blockchains. I’d like to make money off of it, but it’s insecure.
That depends on the hack. If the hack is something that is traceable to you then the hack becomes fraud and the police will be at your door. This assumes that the likes of Russia and North Korea have decided that there is more value in bitcoin remaining operational than the one time haul of money they can get from the fraud (which to be fair seems unlikely since it is prisoners dilemma where the defector chooses the final round)
North Korea recently executed what I believe is the largest known theft in history, $1.5 billion in ETH stolen from the ByBit exchange. It was easily traceable to a state-run North Korean hacking group. No police at the door, and ETH only had a temporary dip.
I'd think that if NK was sitting on a $1-10 billion Bitcoin bug, they'd execute it too before it got fixed or exploited by someone else.
> If the hack is something that is traceable to you then the hack becomes fraud and the police will be at your door.
That would be somewhat ironic, given the "code is law" mentality of many blockchain proponents.
I don't doubt that many people would file police reports and lawsuits if any fundamental paradigm of blockchain cryptography were to suddenly be revealed as insecure, but I'd be following the lawsuits with a big bowl of popcorn.
I dislike bitcoin, but you gotta admit that that's a rather clever aspect of it: Anybody with the power to destroy it is better off participating in it instead.
We'll need to find our way out of that logic eventually. Scarcity in general and proof of work in particular are terrible bases for an economy. But it is a respectable foe.
it is a prisoner dilemma where the defector controls when the final round is. If you know of a flaw you can win more long term by not exploiting it - but if someone else exploits it bitcoin becomes worthless. Thus if you know of a flaw there is pressure to exploit it first before someone else gets the benifits of defecting and ends the game
It depends on the flaw, for most of the attack surface that bitcoin has, your "flaw" is just an unfair advantage against the other miners, which you'll likely keep secret and keep on mining. That's not exactly a "bitcoin becomes worthless" scenario, it's not really that different from a halving, which are block-height-scheduled events built into the protocol.
