> When he shared his thoughts with Ethereum’s cryptographers, he was startled to learn that they were unfamiliar with this work
It would be nice if the article included timelines. Ethereum researchers have been talking about GKR since 2020,so it's hard to imagine the lack of familiarity.
The time is given as "last October," and the work they were unfamiliar with is presumably "contrived proof protocols that are vulnerable to attack, no matter which hash function you use" as stated in the immediately preceding sentence.
That's confusing to me because back in 2020 when they were looking into GKR inside of a Snark, they were worried about these attacks. Following up in 2022, Ethereum researchers were talking about attacking GKR by forging proofs and not having sufficient randomness/collision resistant.
It's hard to align what's being researched on Ethresar.ch and this statement.
I don't believe the "this work" that the article is talking about here is GKR, but work that is referenced earlier in the article:
> In the early 2000s, computer scientists showed how to do just that, contriving interactive proof protocols that were specifically designed to fail when they underwent Fiat-Shamir
Indeed, the artcile points out that targeting GKR was the idea of the Ethereum Foundation researcher.
> Soukhanov had the idea to target a Fiat-Shamir proof system based on something called the GKR protocol
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.
The article is lacking a lot of details, so maybe I'll check the paper if I have the time in the coming days. But, my understanding from the article is that this attack works by breaking a premise of the considered protocols that doesn't have much to do with the random oracle model. They basically say that, if you agree on a program to use and you hash it as part of your commitment, then you can use the Fiat-Shamir transform to prove claims regarding the program's output. But it seems natural to me that, if you are tricked into accepting the use of a malicious program, then the protocol breaks. After all, the hashing of the program at the beginning is meant to ensure that you're using a specific binary you agreed upon, but it does nothing to show that such a binary works as intended. This has to be verified outside of such protocol.
Am I missing something? Or maybe the point is that, under the random oracle model, it should be hard to write a program that contains its own hash? But then again, would the trick of reading the hash from an external configuration file that isn't considered as part of the hashing be fair game?
I think the thing that you're missing here is that the "malicicous program" being discussed here isn't malicious from the usual point of view of what "malicious" means. It's truly functionally identical to the original program -- it returns the same outputs on the same inputs, there isn't some secret input that makes it do something wrong.
Despite that, it's nonetheless "malicious" in that, with the modifications made to it, FS can be made to "prove" false things about it. So you can "prove" that M(x)=y, even though when you actually run M(x), you find that you don't get y.
Yes, what you are missing is that attacks on Fiat Shamir were very contrived up to now.
However the paper shows that there in fact exists a pretty simple way to break the Fiat Shamir heuristic, for a protocol operating in the RO model. And such kind of efficient attacks are rather concerning in cryptography land.
So this isn't about the attack per se, rather it's about the existence of such an easy one.
I understand that this is the claim being made, but I think I'm still missing what is the attack's heart. From the article, it seems to boil down to "if you use a malicious program, then Fiat-Shamir is broken". But to me it seems more like that Fiat-Shamir would still give a correct proof of the program's output, it's just that the output itself was wrong from the start (I'm referring to the point in the article where they say such a malicious program behaves differently than intended when it detects its own hash being used). Is this attack actually letting you generate a valid proof for an output that the program doesn't generate under the given input?
As I understand the paper, the point is that Fiat-Shamir does *not* give a correct proof of the program's output.
They gave a (maliciously constructed) program whose outputs are pairs (a,b) where certainly a != b (instead the program is constructed such that a = b+1 always). But you can get the corresponding Fiat-Shamir protocol to accept the statement "I know a secret x such that Program(x) = (0,0)", which is clearly a false statement.
I haven't done a real review yet, but skimming it seems to relate to
Arthur-Merlin[0] oracles and public fair coins.
If you view random numbers as normal numbers, they will seem to be algorithmically random, or at least exceed the complexity of any proof, or even practical proof.
Basically the work of Chatlin, where given the kolmogorov complexity of your verifier, you only have a limited number of bits in any L that you can prove anything.
Probably simpler to think about the challenges of proving a fair coins is fair.
They just have to produce an unfair coin that looks fair as a flawed analogy.
Fiat-Shamir depends on interactive proofs, which equals PSPACE, which seems huge, but it can be a hay in the haystack, and if you are using a magnet to reach into the haystack you will almost never pull out a piece of hay.
The protocol is in charge of producing the proof. Fiat Shamir is a heuristic, some kind of rule of thumb, which consists in using a hash function as a source of randomness.
Cryptographic protocols often feature coin tosses. The idea is that if we replace a hash function in place of the protocol coin tosses, it should still be hard for a malicious prover to craft a false statement with an accepting proof - making the protocol unsound.
Roughly, the meat of the attack consists in baking in the statement being proven the ability for the prover to predict upfront how the hash function is going to behave - hereby breaking the Fiat Shamir heuristic and making the prover able to craft a false statement with an accepting proof.
That’s it, this is “How to Prove False Statements“!
Yes, I happened to study how the Fiat-Shamir transform works a couple years ago, but I only saw it in the context of using it to transform an interactive zero knowledge proof into a digital signature scheme.
So, if the prover can know beforehand how an hash function behaves, wouldn't this make it a more general attack on hash functions (so potentially even worse than how it is presented in the article) and the Fiat-Shamir transform is only broken as a consequence of it relying on an hash function? If not, why?
This is not an attack on hash functions in general. In this paper, the authors build a statement (or "circuit") which should, by construction, not have any accepting claim. Yet, they show that when using GKR along the FS transform, you can still get accepting proofs.
This has to do with "how an hash function behaves" in the sense that, in the context of a specific protocol (GKR), it is possible to bake in the circuit the ability to predict the randomness obtained from hashing the statement itself and the public values satisfying it.
What does "easy" mean in this context? From my [ignorant] reading, it sounds like it requires being able compute a fixed point for the hash function in order to be able to integrate it into the program and respond differently under test. I thought that was one of the things cryptographically secure hash functions explicitly made difficult?
Previous examples which showed how instantiating Fiat Shamir leads to an unsound protocol were so contrived that people use to think that they were a testament to how unlikely breaking FS would be [1].
In "How to Prove False Statements", you can actually build what they show.
The attack does not require a fixed point of the hash function to be integrated into the program, it merely involves an implementation of the hash function included in the program, being fed the exact same input as the hash function used as part of the protocol. This is possible because the input is entirely attacker-controlled, so it's easy to duplicate some values as necessary.
The “choosing the program” part is vague, but in many practical cases the user gets to choose the program by choosing input data.
This goes back to the rather fuzzy distinction between “data” and “program” you may remember from your early CS days. More precisely, from a theoretical CS perspective, there is no solid difference between data and program.
Almost all practical ZK schemes require the user to choose some input (eg the root of the merkle tree representing the “current state” of the blockchain and secrets like keys and the amount of a transaction).
From some perspective, you get a different program for each different input; sometimes people call this “currying” or “partial evaluation”.
So yeah, it’s more serious than it seems at first blush.
It seems to be pretty explicit that the "program" being run contains the full hashing algorithm used (to output the correct answers most of the time) plus additional logic to allow cheating.
That rather clearly goes wildly beyond what most ZK schemes use. That's arbitrary code execution of your choice, either as input or as part of selecting the program. Which seems like it puts this somewhere near "if you allow `eval` on user input in your script, it could do anything", doesn't it?
Plus like. They fixed it. That seems to imply it's more of an implementation flaw than a fundamental, even if it may be a surprisingly achievable one.
So the proofs I’m most familiar with embed programs as polynomials over finite fields. Input data also corresponds to choosing some coefficients, and if you can choose enough coefficients (enough to embed the hash function) then the attack may be feasible.
The problem is compounded because the hash functions are typically chosen to have extremely short polynomial representations.
So, in the end, what is the core concept of the attack? Were they able to generate a program (maybe exloit the fuzzyness of the distinction between data and program to generate a program) that contains the hash of itself? I doubt that this is it, as if this were the case, then it would be likely to be an issue with a specific hash function and not a general issue. Unless they are using some trick like the one I presented above, but then it seems to me that the problem wouldn't be with Fiat-Shamir itself.
There were parts of the process that check whether its a valid proof, which were previously thought to be equivalent, which were in fact not the case. Computer scientists involved knew of cases where this was not the case but moved ahead anyway because no one would design the systems in the ways the attacks would work.
Attacks only get better.
The original process included the original hash in such systems inputs, but also allowed additional malicious features which could be included to rearrange the output in a way that passes the proof scheme checks despite it being incorrect.
By placing a constraint on input entropy they believe they've mitigated the issue, but it also breaks many applications; with no good alternative.
Imo, This is a weak assertion considering finite fields are used. The title is really misleading.
It should be "Fiat Shamir is broken"; Practical attacks.
These are finite fields so the token output generated doesn't necessarily correspond to the specific path taken.
There may be an infinite many paths, and computation has classical problems of computer science with being able to automatically derive decidable paths from tokens given; potentially leading to the same issues of discovering simple breaks.
Simply put, a reliable random oracle in an adversarial environment should be based on sources of randomness from multiple sources and participants, usually the sources are the participants’ meaningful actions to prevent collusion.
It has been known for quite a while that if the space of inputs being hashed is small, the hashing is relatively useless for most benefits of a true one-way function (eg hashing a phone number in USA).
I recall someone creating a crypto system and then forgetting to protect the constructor of the initial object so other could change the constructor and do whatever they wanted with that crypto system, but in the end the creators were just web developers with a little training in crypto.
In those circumstances those millions of coins flying in or out are not a tragedy (at least for me) but a very plausible outcome.
That's a completely different and unrelated type of vulnerability, though.
Implementation mistakes leading to mass coin theft would certainly be cryptocurrency news, but they would not be crypto(graphy) news. Breaking an actual peer-reviewed zero knowledge proof scheme would be.
Hashes should never be a source of randomness. Randomness makes assumptions far outside their intended use case.
Hashes should only be a reproducible label that cannot be used to produce the material described by the hash. When used for their intended purposes hashes serve as the strongest point of integrity until value collisions are discovered.
But once you've made a function that "cannot be used to produce the material described by the hash", you've also made a very good pseudo-randomizer. In fact, if a cryptographic hash function cannot be trusted for its ability to produce apparent randomness, then it cannot be trusted for its "intended purposes". You get both properties or neither.
There is an untested assumption that hashes achieve randomness because they appear to be a random collection of characters. Hash sequences are completely reproducible given a set of input, and that is by definition not random.
I think you are confusing loss of prediction as randomness. Never in mathematics or logic is that line of thinking correct. This can be described by equivocation, fallacy of composition, inductive fallacy, and more.
I think you are mixing the function itself and it's output, if for a given input to the function the output is uniformly random, then this is a way to derive randomness. The fact that the function itself is deterministic tells you nothing about the distribution of it's output.
You started your comment with a correct distinction, but got the wrong conclusion. Asking if somthing is random is actually a question about the process used to obtain some value and not the value itself. If I ask you if 42 is a random number, can you actually answer? I can get that number with an intrinsically random process based on some quantum effect, or I can say it from the top of my head because I just read a very famous book. You can indeed use an hash function to extract randomness, but, to be precise, we are talking about pseudo-randomness. The crucial difference here is that, if I'm measuring photons' polarization to get a random number, then an attacker repeating the same process will (very likely) obtain a different number. If I'm instead hashing some data, an attacker passing the same data through the same hash function will get the same result. Another example: if I hash the digits of pi, I will get a sequence that will pass statistical tests for randomness. But an attacker that knows how I am generating such sequence can easily reproduce it.
> lol, no. Cryptographic hash functions are specifically designed to achieve this property.
That completely ignores the definition of the word random.
What I find most interesting about this thread of comments is that the article explains the failure of using hashes as a means of randomness and despite that failure people are eager to ignore what hashes are otherwise used for to invent oppositional arguments. it's weird.
It's a lot less weird if you consider the possibility that you don't understand this as well as you think, and the reason people are consistently correcting you is because you are mistaken.
You're saying something being reproducible implies that it is not pseudo-random. This is a definition of pseudo-random that exists only in your head.
The first sentence of the wikipedia entry on pseudo-randomness is:
"A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process."
That misses a factor called good enough, or degree of predictability. Ultimately everything eventually becomes predictable if analyzed deeply enough. Another word for that is entropy. That is what my linked comment referred to. For security concerns, such as PRNGs, the appearance of randomness is not enough.
This is why security analysis requires a higher threshold than software employment at large.
A hash function cannot create entropy. Let's be clear about that.
A good hash function will preserve entropy, up to the length of its output. If the input X has K bits of entropy and H is an N-bit cryptographic hash function, then the entropy of H(X) is min(K, N). In simpler terms, GIGO.
However, a hash function also scrambles its input, which means the output is indistinguishable from (uniform) random noise. This is the randomizing property I was talking about. It is good enough for hash functions to be used to build stronger primitives, like HMACs, PBKDFs, CSPRNGs, etc. There are many formalizations of this property, but one of the simplest is that given any K bits of the output, you cannot predict the other N-K output bits any better than guessing, even knowing the algorithm.
Of course, if you know the input to a hash function, you can predict the output perfectly. But if you don't know the input, the hash looks like random noise, and for cryptographic hash functions, this is a very strong and fundamental guarantee indeed.
You may want to stay away from all modern CSPRNGs then. Eg Yarrow and Fortuna rely on sources of random input data being mixed in but using a strong hash function (nowadays sha-256) to produce the output at arbitrarily fast rates without consuming entropy.
And to your criticism that this is just programmers who don’t know what they’re doing, these algorithms were developed by Bruce Schneier, Niels Ferguson, and John Kelsey.
I was so frustrated as a noob trying to understand why people were using hashes this way. Even a professional told me "yeah but a collision is really unlikely," and compared it to neutrino interference. How is that supposed to be good enough?
Hash functions are used to instantiate a random oracle (which is a theoretical object that can't be instantiated because it would be of infinite size but makes it easy to reason about) because it doesn't seems crazy as an assumption that if finding a collision between 2 hashes is hard it should be hard to predict the output of the so called hash function. However it is well known that there was some contrive counter example for protocols that are secure under the Random Oracle model and unsecure when instanciated with any hash function. The problem with this paper is that the protocol it described isn't so contrive anymore.
Cryptography is a matter of assumptions and what you believe in or not. You might want to not use random oracle but you will therefore have to restrict yourself in what you can concretely build.
And the reason behind the problem outlined in the paper isn't a biased randomness problem but the fact that you can represent the hash function compared to a RO.
I'm sorry, but this comment is very vague and unclear.
Cryptographers know that hashes (even cryptographically strong ones!) are deterministic. Yet, it is possible that in going from an interactive proof to a non-interactive one, one does not actually need randomness. Indeed, for some class of protocols, we know how to design hash functions satisfying a particular property (correlation intractability) so that the resulting non-interactive proof is sound. It's just that (a) these hashes are inefficient, and (b) until now no one had found a non-contrived protocol where using standard hashes leads to an attack.
You should look into the HyperLogLog algorithm, where fair hash "randomness" is required for the algorithm to work. There are use cases where the pseudo-randomness of hashes is useful, is what I'm trying to say.
This is why you should NEVER trust software developers to make security decisions unless certified to do so. True randomness is challenging to achieve, because computers are inherently predictable. Pseudo-randomness is an intended process to intentionally achieve randomness in spite of this high predictability, often through use of physical or electromagnetic criteria outside the computing machine.
Hash algorithms are none of that. They are not pseudo-randomness merely because a software developer merely wishes them to be so. Hash algorithms are intentionally designed to achieve high reproducibility in that a given set of input should always result in the same hash sequence as output. That intended reproducibility is by definition not random.
You don't understand what pseudo-randomness means. Virtually all PRNGs, even many CSPRNGs, have a way to initialize the algorithm with a seed, and its outputs are fully predictable based on that seed. Choosing a truly random seed, such as one produced by RNG hardware, will lead to a usefully random sequence - but the algorithm is still fully deterministic based on that seed.
>True randomness is challenging to achieve, because computers are inherently predictable
Most modern CPUs now contain a true RNG. They usually use some combination of a metastable latch, or thermal randomness through some kind of analog amplification. Bit strings from this are passed into a pseudorandom number generator to amplify the amount of random data generated.
There probably attacks on this too but it's much harder.
More accurately, the CPU RNG instruction is generally considered untrusted by itself and the only reason it's used is that kernel RNGs are CSPRNGS based on cryptographic hashes (which is what the CS refers to - cryptographically secure) where mixing in a corrupted bit stream along with uncompromised bit streams still results in an uncompromised bit stream out. No one uses the CPU RNG instruction directly (both for security & also secondary perf reasons)
What? You’ve managed to mangle so many terms in so few words… Signatures can refer to two things: integrity checks on a file or authentication checks for a recieved file. In the integrity check situation a hash function (e.g., SHA) is often used. In the authentication check situation, we usually use a public/private keypair for asymmetric encryption; the hash function is only part of the process. The key material used to make this keypair (should) comes from some random number generator…
The ‘hash’ function is a deterministic transform, not a source of randomness.
He is technically not wrong, most signatures can be seen has a public coin interactive proof system where you prove knowledge of a private key.
They are then compiled into an non-interactive proof system via the Fiat-Shamir transform that uses a random oracle concretely instantiated using a hash function (easy to see in Schnorr signature).
So at the end you are using a Hash function to generate your random coin.
Internally, most signature algorithms use hash functions. RSA-PSS, EdDSA and ML-DSA use them to provide something like randomness, and the security analysis of those signature schemes includes arguments assuming (in some very particular, technical ways) that the hash function outputs "look random".
Classical DSA and ECDSA do not use hash functions this way, but in my opinion they aren't stronger for it: they're basically assuming instead that some other mathematical function "looks random", which seems riskier than assuming that about a hash function. I've heard that the reason for this is to get around Schnorr's patent on doing it with hash functions, which has since expired.
The SHA3 and SHAKE hash functions (underlying e.g. ML-DSA) are explicitly designed to "look random" as well.
There are some signature schemes that try not to make such strong assumptions: in particular SLH-DSA targets properties more like first- and second-preimage resistance, target-collision-resistance, and so on.
All the algorithms you mention are PKI. RSA uses two large prime numbers. I don't see what hash sequences have to do with this at all.
PKI isn't even really about randomness. RSA does use a kind of randomness to generate its large primes, but that is beneficial and not required. The primary consideration is the math to reverse guess a factor of two primes or the square root of a large number, or something else computers currently find cheap to compute in one way but extremely expensive to reverse.
The intro textbook descriptions of cryptographic systems omit a lot of very important details.
When using RSA to sign a message m, in practice you don't send m^d mod N. That would generally be insecure, depending on what kinds of messages your system sends and/or accepts. In practical systems, instead you hash m, and then adjust the hash through a (possibly randomized) process called "padding" to be a value in [0,N). There are different standards for padding, and the better designs use additional hashing.
The security of the system depends in part on the hashed-then-padded message "looking random", i.e. not having structure that can be exploited by an attacker. It turns out to be tricky to formalize what exact randomness property you need, so cryptosystems are often analyzed in the "random oracle model" (ROM) in which the hash function has impossibly strong randomness properties.
It seems that usually, if you use a strong hash function, a scheme that's proved secure in the ROM is secure in real life (or at least it's not the ROM part that breaks); the counterexamples are usually really contrived. This article is about a somewhat-less-contrived, but still not quite realistic, example where something that's secure in the ROM would break due to the ROM being an unrealistic model.
It's not wrong. The only thing preventing me from forging your certificate is my inability to generate a new cert which hashes to the same digest as what is in your cert's signature. I don't actually need the keys if I break the hash.
EDIT2: I'm doing a bad job of explaining this... you obviously need the keypair associated with the cert to initiate connections with it and not trigger MITM alerts. But if you break the hash function, you don't need the private key from the root cert, the verbatim signature from the original cert will appear to be valid when spliced into your forged cert if the hash digest computation on the forged cert is the same.
And checking the validity of a certificate involves checking a signature of... The certificate's hash. If you can break the underlying hash function, then the trust chain is broken.
I also had to just go to the paper. It was really difficult trying to get through the article. Needlessly hyped language like "proving lies" and hyperfixations on things like leaking boats... felt like the author was either out of their element or inexperienced with math comms. However, the article still provides a bit of context that the paper doesn't.
That said, this is honestly just a bad article that is needlessly sensationalized and fails to impart any real knowledge.
(Note: the original title was "Computer Scientists Figure Out How To Prove Lies" before being changed by the admin)
I honestly think that Quanta Magazine just found the perfect formula to farm HN traffic. The titles are clearly carefully engineered for this audience: not the outright clickbait of university press releases, but vague profoundness that lets us upvote without reading the whole thing and then chime in with tangential anecdotes.
I don't think they're bad people, but I honestly think they end up on the front page multiple times a week not on the quality of the articles alone.
That's the case with many cryptographic explanations for laypeople, in my experience (as mostly a layperson).
Maybe all these elaborate analogies of Alice walking into a cave and Bob yelling which exit she should come out of, Alice wanting to sell Bob a Hamiltonian cycle trustlessly, Alice and Bob mixing buckets of paint and shipping them via the mail back and forth etc. are working for some people, but it's not me.
Are you using "crypto" here to mean "cryptocurrency", rather than "cryptography"? Because if so, that's not obvious considering you just mentioned cryptographers in the previous sentence.
If, on the other hand, you mean "all of cryptography is a fraud", then I'm curious to know what makes you think that.
hard disagree here. I think crypto currencies are built on hype and bluster and scams, but blockchain as a technology is actually super interesting. There are plenty of cool use cases for an open immutable ledger that aren't scammy.
right, because there's no other way to prevent modification. no other way. also it's not possible for a single operator to have 51% of the compute in a blockchain.
both of those are obviously false and both have already happened.
blockchain is stupid. it is insanely inefficient, it burns power solely so you can say that you've burned power. it is stupid beyond belief.
51% attacks, on anything at a large scale, are generally more theoretic than practical. The amount of resources you'd need to invest to achieve that on any large currency are astronomical, and you'd need to just completely wreck everything engaging in widescale fraud (which would be a felony, carried out repeatedly and at scale - and likely fairly easy to tie back to you given the massive resource investment to get here in the first place) to try to recoup your losses.
The most probable outcome being a rapid fork and rollback as already with e.g. Ethereum over a relatively negligible amount of money relative to what you'd need to get a 51% on Bitcoin. You'd likely end up losing a massive amount of money, as well as look at possibly spending the rest of your life in prison. So the only real purpose in doing so is for attention or trolling, but the costs involved generally preclude this motivation.
Hard focus on one use case, albeit most famous and has some properties you mention.
There are other use cases, like it or not. And its popularity - don't blame tools for basic human greed they only allow to be manifested, that's not a smart approach to get anywhere apart from endless complaints how this and that sucks.
how do banks do it now? you know the answer, at a high level. it's the same way we prevent unauthorized access when the blockchain isn't involved, and it's how we prevented unauthorized access before the blockchain existed.
it's how banks prevent someone from withdrawing money from your account without your permission, everywhere across the entire globe at once, all the time.
it's the same reason that I, a normal user, can't delete people from active directory at work, or change their passwords to mess with them.
you've dealt with this kind of permission system your entire computer-using life. you know how it works. you know what it is. being distributed doesn't matter at all.
Blockchain isn't just distributed, it's decentralized and trustless.
We live in a time where any form of centralized authority is increasingly abused. Blockchain prevents this. It also prevents incompetence as we also live in a time where centralized data and credentials are regularly leaked or hacked with no recourse available.
how do you not know this? think about that. think really hard. you can do it. how do people prevent unauthorized access when the blockchain isn't involved, or before blockchains existed? really, really think. you know the answer.
If you don’t already know how simple permissions, read-only storage, and digital signatures work, I don’t think that you have any business telling anyone that they’re misunderstanding anything.
Bitcoin was made to solve problems that exist only in the minds of those who wish to make money with bitcoin. Other blockchains serve the same purpose. Zero people use it as a ledger, except as a joke or to prove how stupidly limited and inefficient it is.
Bitcoin also has created problems that didn’t exist prior to the invention of the blockchain.
So, aside from the myriad negative effects of the blockchain, it is wholly and completely pointless unless you think it will make you money. If that’s how you think of yourself, you are a parasitic scammer spreading ransomware trying to make people think you are a legitimate human person with a right to live.
Hmm. The blockchain is actually a very clever solution to a very old coordination problem. In that sense it is not BS at all.
But I agree that it is an open question whether it can directly support a useful economy the way a currency can. It doesn’t seem to have the throughput for that, to start with. But maybe it could be useful for interbank settlements, if for some reason traditional methods weren’t working.
This has been known for a long time that in order for crypto backed securities to work, Bitcoin’s blockchain would need to be the clearing house for assets tied to it. We’re in derivatives of derivatives of indexed derivatives land.
Banks have already started exploring using it as the clearing house and recent US policy has cleared the path for more.
My hot take, crypto(currency) is for pure peer markets, since all individuals are accounted for by a government its not especially useful for people. However, governments are essentially peers without some disinterested third party with the power of enforcement. This is place where crypto lives.
Yea, something like that. Although even there you still have bond ratings and just straight up reputations to tell you which governments are trustworthy enough to do business with, even without a blockchain.
blockchains and bitcoin are good for two things only: money laundering, and collecting ransomware payments.
blockchains as an immutable ledger should be the dumbest thing anyone has ever heard of. but somehow people saw dollar signs and put aside all their reservations and are using it to try to get rich quick.
as if a set of banks are going to secretly conspire to remove your money from you specifically, without a paper trail, or something. it's a nonsense premise to begin with.
you're right. "all of crypto is fraud" and the Ethereum cryptographers not knowing about this important detail are two statements that are true separately.
> Ethereum’s cryptographers are not cryptographers
I guess I'll bite, what are they then? If they're focusing on the cryptography of a project, doesn't that make them cryptographers? Or you mean they aren't "real cryptographers"?
> It's a wish club of technical yes people.
Isn't that basically one of the ways doing innovation? Instead of saying "No, that's not possible" when someone asks if they can build something faster than a horse and carriage, a bunch of people get together to see if there any way of doing that, trying to avoid any per-concieved ideas about if it's actually possible or not.
Isn't that basically one of the ways doing innovation? Instead of saying "No, that's not possible" when someone asks if they can build something faster than a horse and carriage, a bunch of people get together to see if there any way of doing that, trying to avoid any per-concieved ideas about if it's actually possible or not.
Yes, but if people graduate from engineering schools that explicitly teach the concepts of the combustion engine, and the carriage manufacturers claiming to be engineers are unaware of basic principles like the 4 stroke cycle, you have a completely different kind of problem.
It's the old "we use first principles thinking" approach. Too often it means "we don't actually know or care what came before us, we just move fast and break things, how hard can it be lol yolo" Then that's what you get, insufficiently educated folks re-inventing the wheel, repeating mistakes others have done before.
Yes, sometimes you need to break out from pre-conceived notions, evaluating whether conditions have changed and earlier assumptions are maybe not valid anymore. But that's no excuse to be ignorant.
> Isn't that basically one of the ways doing innovation? Instead of saying "No, that's not possible" when someone asks if they can build something faster than a horse and carriage, a bunch of people get together to see if there any way of doing that, trying to avoid any per-concieved ideas about if it's actually possible or not.
This does not take real-world limits into account. There are limits to information theory (which includes crypto), thermodynamics and mechanics that make certain things generally impossible. Like a perpetuum mobile. Social or intelligence factors do not matter. Knowing your field also includes understanding those "hard" limits.
lol. I work in Applied cryptography and I don’t know a harder distributed system built on such a broad spectrum of primitives which has seen such high uptime.
What is a lie? what is the truth? It is very difficult to find the truth, and the descriptions of the same thing are different for different persons. So the title and its content is a lie.
Your question is very simple to solve for someone who has done enough real philosophy lol :) a lie is when you tell something differently than it is. the truth means "what exists as it is".
If you say that "it is difficult to find the truth", aside from the blatant subjectivity of your claim, then , if we believe your statement, then that itself must be a "truth". And yet you invalidate your own claim immediately by saying "different for different persons". Well, if that statement is true, then it invalidates itself as well.
You cannot disprove the existence of truth by using a system that relies on truth and falsehood.
You seem to have some misunderstandings about truth. Many truths are our understanding of real existence, not existence itself. Obviously, our understanding of complex things may be different, but complex things do exist.
For example, the movement of things exists, but Newton's understanding of this existence is different from Einstein's understanding of the same existence (or the movement of more things).
Please understand the restrictions of Newton's Laws of Motion, many years ago, some people think they are right in every environments. My point here is it is difficult to get the truth for somethings. the title means proving everythings whether they are lies.
> and the descriotions of the same thing are different for different persons
When my son says, "I wasn't there" when the glass broke, it's not just a matter of differing descriptions, it's a clear denial of a fact. There are facts, and when someone deliberately twists or denies them, that's not just a different perspective. That's a lie.
> it is difficult to find the last truth, only reach its truth over time
The fact that is difficult to find out the truth, does not mean that something was or wasn't a lie. Paradoxically this is an attribute of a "good" lie: it is difficult to find out that it wasn't the truth.
I think this is a good example of a lie because you and your son both have a shared understanding of the world and he is deliberately saying something he does not believe to be true (that does not match his own internal recall of events).
There is a physical component to this lie but it seems to me that the social part dominates.
That’s not the point. You know your son knows what happened - knowledge of his mental state. Not that you have a physical proof about the chain of causality.
My initial prediction is they just divided by zero someplace - just like every other undergrad in any degree program that requires some advanced math has. I'm happy to see they didn't make this obvious mistake.
>if a professor has assigned 100 problems for homework but doesn’t want to grade a student’s entire assignment, she can randomly choose 10 problems to grade. In the language of computer scientists, she is making 10 “random challenges” to the student’s homework. If the answers to those 10 problems are correct, the professor can feel confident that most of the other answers are correct too.
Eureka! I found the reason that so many things in society have gone to shit in the last few years. Far too many professors are so overworked or maybe just lazy and are using this type of tool to grade student work and the end result is that we have too many students passing through the system who have demonstrably only been able to score a 10/100.
I'm over 60 now and if I had scored lower than my current age back in the day I would fail and need to repeat the grade/course. Now they just kick the can('ts) on down the road and hope no one ever notices.
Too bad some of these failures end up in positions of influence where their uncharted deficiencies have the power to disrupt or destroy functional systems.
Or maybe I'm joking. I'll know once the caffeine hits.
I'll accept your math this morning with the note that without checking the other 90/100 answers you have no way outside of accepting probabilities to know whether your random examples are representative of the quality of the full set. It becomes a "trust me bro" situation.
I processed hundreds of thousands of miles of seismic data in my career. The first thing we needed to do for any processing project was to select a subset of the data for use in defining the parameters that would be used to process the full volume of data. We used brute stacks - a preliminary output in the process - to locate interesting areas with complex attributes to make sure we could handle the volume's complexities. In industry slang these were "carefully selected random examples".
It was inevitable that we would find a situation during the processing for which our parameters were not optimized because we had missed that edge case in selecting the examples used for testing.
In the same way in real life if you only demonstrably know that 10% of the test answers are correct then it is also true that some edge case in the 90% of untested answers could leave all or part of that untested space false or sub-optimum.
If there was a point to my original post it is this. You only know something is true when you have proven it to be true. A maximum likelihood of truth is not a guarantee of truth it is only a guarantee that it is likely to be true. You won't know how sharp the sting will be until you peel the onion.
Having checked an answer also doesn't guarantee anything with certainty. Which, coincidentally, is the actual topic of the OP, the grading was just a tangential example and not a description of something actually happening anywhere in practice. But sticking with the grading example, the failure modes could be much more benign, such as the examiner failing to spot a mistake, or the answer being copied,...
Probabilities aren't a matter of faith, they're mathematics and as such represent a logical trueism. Your critiques are just nitpicking for the sake of it and void of substance. Have a coffee and leave this topic.
>they're mathematics and as such represent a logical trueism
I'm a full pot in now and find that I agree with this.
The fact is though that the article demonstrates that something previously considered logically true or a maximum likelihood was proven false.
It's great to see that there are people, whether they're mathematicians or cryptographers, who will take a look at something that has been a useful part of a stable process of verification and try to find cracks or instabilities. The fact that they found an edge case that could be exploitable undermines trust in an important part of the process.
Trust - but verify, wins again. Logically, this is the best way.
> You only know something is true when you have proven it to be true. A maximum likelihood of truth is not a guarantee of truth it is only a guarantee that it is likely to be true.
It's just a random decaffeinated thought here this morning. Considering that it must be true that even a blind squirrel gets a nut once in a while it is also likely to be true that a professor at random can select the exact 10 problems that were solved correctly.
There's a difference between something with a probability of being true and another thing that is proven to be true. There are no doubts remaining after the proof whereas the probability always leaves wiggle room even if that wiggle room is a pretty tight space.
We should be careful about using probable and possible interchangeable.
You are right - it is possible that is happens but not probable.
However, overly focusing on this really deprives you of a lot of great intellectual stimuli from randomized algorithms and, like here, a large chunk of cryptography.
>However, overly focusing on this really deprives you of a lot of great intellectual stimuli from randomized algorithms and, like here, a large chunk of cryptography.
I agree with your first points about using probable and possible carefully. I originally posted a bit of a tongue in cheek, carefully selected example, from the full text of the article since that example fit the point that I hoped to make in jest. It was my carefully selected random example.
I think the focus of the article is on demonstrating that a tool used in cryptography to verify truth was widely assumed to be infallible and it turns out that is unfortunately not true since it can be manipulated to identify false results as true. This tool uses probabilities as a tool to minimize compute times that would be enormous if one had to verify absolutes so it is an important tool. Now that it is demonstrated that it can be successfully attacked, the basis of the system of verification is vulnerable and in the case of Ethereum at least, monetary losses can result.
There is a risk here that the professor who only assigns 10 problems will only check one of them for correctness. If 5/10 of the answers are wrong but the professor verifies a correct answer for one of the 5/10 with a correct solution then their conclusion that the other 9/10 answers are correct due to some likelihood or probability function is invalid and a dimwit makes the grade.
Maybe professors should flip the script, instead of testing a student, have the student convince the professor they know the material. You will not pass until the professor feels confident.
Presumably more questions can cover a wider variety of skills/techniques/topics. If the student doesn't know in advance which 10 will be selected, they either have to pray they're lucky, or work diligently on all problems.
presumably they glance at the other 90 too, and they then do a thorough verification on that random 10
the analogy is not great, but in cryptography something similar is at play (easy to get/check trivial properties and then hard to achieve/produce/fake the interesting ones)
they were shit all along, but the energy (and productivity) surplus allowed for decades of amazing growth, which created the feeling of prosperity
unfortunately most people doesn't understand (and as a consequence doesn't appreciate) how little wealth we have compared to capacity, in other words how much upkeep we do to maintain that wealth
and now that it's time to scale back the waste a bit people are up in arms
As the caffeine sweeps through my system activating latent stores of energy and powers of analysis, I find that I appreciate this response without needing to understand all of it. It's a bit like assuming that the remaining 90/100 answers are correct after only verifying 10 of them.
I feel like I have accomplished more than I actually have and so I have plenty of incentive now to sweep through all the work of the day hoping that each randomly selected set of results yields similar levels of perfection and that all the inaccurate answers assumed to be correct do not cause the student to make assumptions in later life about things that are not supportable by facts.
> When he shared his thoughts with Ethereum’s cryptographers, he was startled to learn that they were unfamiliar with this work
It would be nice if the article included timelines. Ethereum researchers have been talking about GKR since 2020,so it's hard to imagine the lack of familiarity.
The time is given as "last October," and the work they were unfamiliar with is presumably "contrived proof protocols that are vulnerable to attack, no matter which hash function you use" as stated in the immediately preceding sentence.
That's confusing to me because back in 2020 when they were looking into GKR inside of a Snark, they were worried about these attacks. Following up in 2022, Ethereum researchers were talking about attacking GKR by forging proofs and not having sufficient randomness/collision resistant.
It's hard to align what's being researched on Ethresar.ch and this statement.
I don't believe the "this work" that the article is talking about here is GKR, but work that is referenced earlier in the article:
> In the early 2000s, computer scientists showed how to do just that, contriving interactive proof protocols that were specifically designed to fail when they underwent Fiat-Shamir
Indeed, the artcile points out that targeting GKR was the idea of the Ethereum Foundation researcher.
> Soukhanov had the idea to target a Fiat-Shamir proof system based on something called the GKR protocol
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?
Extremely theoretically, and the article is very sensational.
The paper is half a year old, and hasn't made a splash; if this were significant news, I would expect to be able to find more coverage on it.
I did find this more nuanced take here: https://blog.cryptographyengineering.com/2025/02/04/how-to-p...
I haven't seen much of Quanta "Magazine", but I feel all of it has been stuff like this?
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.
The nuanced take was also discussed here at the time: https://news.ycombinator.com/item?id=42939312
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 :)
Quanta is “pop science” for smart lay people who might also read, for instance, the New Yorker.
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.
I'm not sure if they can trace the fraud to you.
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.
The major blockchains are basically billion-dollar bug bounty programs. If they were hackable that easily, we'd probably know already.
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.
Here's a whiteboard session going over that but https://blog.zksecurity.xyz/posts/pudding3/
The article is lacking a lot of details, so maybe I'll check the paper if I have the time in the coming days. But, my understanding from the article is that this attack works by breaking a premise of the considered protocols that doesn't have much to do with the random oracle model. They basically say that, if you agree on a program to use and you hash it as part of your commitment, then you can use the Fiat-Shamir transform to prove claims regarding the program's output. But it seems natural to me that, if you are tricked into accepting the use of a malicious program, then the protocol breaks. After all, the hashing of the program at the beginning is meant to ensure that you're using a specific binary you agreed upon, but it does nothing to show that such a binary works as intended. This has to be verified outside of such protocol.
Am I missing something? Or maybe the point is that, under the random oracle model, it should be hard to write a program that contains its own hash? But then again, would the trick of reading the hash from an external configuration file that isn't considered as part of the hashing be fair game?
I think the thing that you're missing here is that the "malicicous program" being discussed here isn't malicious from the usual point of view of what "malicious" means. It's truly functionally identical to the original program -- it returns the same outputs on the same inputs, there isn't some secret input that makes it do something wrong.
Despite that, it's nonetheless "malicious" in that, with the modifications made to it, FS can be made to "prove" false things about it. So you can "prove" that M(x)=y, even though when you actually run M(x), you find that you don't get y.
Yes, what you are missing is that attacks on Fiat Shamir were very contrived up to now.
However the paper shows that there in fact exists a pretty simple way to break the Fiat Shamir heuristic, for a protocol operating in the RO model. And such kind of efficient attacks are rather concerning in cryptography land.
So this isn't about the attack per se, rather it's about the existence of such an easy one.
I understand that this is the claim being made, but I think I'm still missing what is the attack's heart. From the article, it seems to boil down to "if you use a malicious program, then Fiat-Shamir is broken". But to me it seems more like that Fiat-Shamir would still give a correct proof of the program's output, it's just that the output itself was wrong from the start (I'm referring to the point in the article where they say such a malicious program behaves differently than intended when it detects its own hash being used). Is this attack actually letting you generate a valid proof for an output that the program doesn't generate under the given input?
As I understand the paper, the point is that Fiat-Shamir does *not* give a correct proof of the program's output.
They gave a (maliciously constructed) program whose outputs are pairs (a,b) where certainly a != b (instead the program is constructed such that a = b+1 always). But you can get the corresponding Fiat-Shamir protocol to accept the statement "I know a secret x such that Program(x) = (0,0)", which is clearly a false statement.
I haven't done a real review yet, but skimming it seems to relate to Arthur-Merlin[0] oracles and public fair coins.
If you view random numbers as normal numbers, they will seem to be algorithmically random, or at least exceed the complexity of any proof, or even practical proof.
Basically the work of Chatlin, where given the kolmogorov complexity of your verifier, you only have a limited number of bits in any L that you can prove anything.
Probably simpler to think about the challenges of proving a fair coins is fair.
They just have to produce an unfair coin that looks fair as a flawed analogy.
Fiat-Shamir depends on interactive proofs, which equals PSPACE, which seems huge, but it can be a hay in the haystack, and if you are using a magnet to reach into the haystack you will almost never pull out a piece of hay.
They are basically choosing the magnet for you.
[0] https://complexityzoo.net/Complexity_Zoo:A#am
The protocol is in charge of producing the proof. Fiat Shamir is a heuristic, some kind of rule of thumb, which consists in using a hash function as a source of randomness.
Cryptographic protocols often feature coin tosses. The idea is that if we replace a hash function in place of the protocol coin tosses, it should still be hard for a malicious prover to craft a false statement with an accepting proof - making the protocol unsound.
Roughly, the meat of the attack consists in baking in the statement being proven the ability for the prover to predict upfront how the hash function is going to behave - hereby breaking the Fiat Shamir heuristic and making the prover able to craft a false statement with an accepting proof.
That’s it, this is “How to Prove False Statements“!
Yes, I happened to study how the Fiat-Shamir transform works a couple years ago, but I only saw it in the context of using it to transform an interactive zero knowledge proof into a digital signature scheme.
So, if the prover can know beforehand how an hash function behaves, wouldn't this make it a more general attack on hash functions (so potentially even worse than how it is presented in the article) and the Fiat-Shamir transform is only broken as a consequence of it relying on an hash function? If not, why?
This is not an attack on hash functions in general. In this paper, the authors build a statement (or "circuit") which should, by construction, not have any accepting claim. Yet, they show that when using GKR along the FS transform, you can still get accepting proofs.
This has to do with "how an hash function behaves" in the sense that, in the context of a specific protocol (GKR), it is possible to bake in the circuit the ability to predict the randomness obtained from hashing the statement itself and the public values satisfying it.
What does "easy" mean in this context? From my [ignorant] reading, it sounds like it requires being able compute a fixed point for the hash function in order to be able to integrate it into the program and respond differently under test. I thought that was one of the things cryptographically secure hash functions explicitly made difficult?
By "easy" I mean straightforward.
Previous examples which showed how instantiating Fiat Shamir leads to an unsound protocol were so contrived that people use to think that they were a testament to how unlikely breaking FS would be [1].
In "How to Prove False Statements", you can actually build what they show.
[1]: e.g. see https://eprint.iacr.org/1998/011.pdf
The attack does not require a fixed point of the hash function to be integrated into the program, it merely involves an implementation of the hash function included in the program, being fed the exact same input as the hash function used as part of the protocol. This is possible because the input is entirely attacker-controlled, so it's easy to duplicate some values as necessary.
The “choosing the program” part is vague, but in many practical cases the user gets to choose the program by choosing input data.
This goes back to the rather fuzzy distinction between “data” and “program” you may remember from your early CS days. More precisely, from a theoretical CS perspective, there is no solid difference between data and program.
Almost all practical ZK schemes require the user to choose some input (eg the root of the merkle tree representing the “current state” of the blockchain and secrets like keys and the amount of a transaction).
From some perspective, you get a different program for each different input; sometimes people call this “currying” or “partial evaluation”.
So yeah, it’s more serious than it seems at first blush.
It seems to be pretty explicit that the "program" being run contains the full hashing algorithm used (to output the correct answers most of the time) plus additional logic to allow cheating.
That rather clearly goes wildly beyond what most ZK schemes use. That's arbitrary code execution of your choice, either as input or as part of selecting the program. Which seems like it puts this somewhere near "if you allow `eval` on user input in your script, it could do anything", doesn't it?
Plus like. They fixed it. That seems to imply it's more of an implementation flaw than a fundamental, even if it may be a surprisingly achievable one.
So the proofs I’m most familiar with embed programs as polynomials over finite fields. Input data also corresponds to choosing some coefficients, and if you can choose enough coefficients (enough to embed the hash function) then the attack may be feasible.
The problem is compounded because the hash functions are typically chosen to have extremely short polynomial representations.
So, in the end, what is the core concept of the attack? Were they able to generate a program (maybe exloit the fuzzyness of the distinction between data and program to generate a program) that contains the hash of itself? I doubt that this is it, as if this were the case, then it would be likely to be an issue with a specific hash function and not a general issue. Unless they are using some trick like the one I presented above, but then it seems to me that the problem wouldn't be with Fiat-Shamir itself.
My read of this is:
There were parts of the process that check whether its a valid proof, which were previously thought to be equivalent, which were in fact not the case. Computer scientists involved knew of cases where this was not the case but moved ahead anyway because no one would design the systems in the ways the attacks would work.
Attacks only get better.
The original process included the original hash in such systems inputs, but also allowed additional malicious features which could be included to rearrange the output in a way that passes the proof scheme checks despite it being incorrect.
By placing a constraint on input entropy they believe they've mitigated the issue, but it also breaks many applications; with no good alternative.
Imo, This is a weak assertion considering finite fields are used. The title is really misleading.
It should be "Fiat Shamir is broken"; Practical attacks.
These are finite fields so the token output generated doesn't necessarily correspond to the specific path taken.
There may be an infinite many paths, and computation has classical problems of computer science with being able to automatically derive decidable paths from tokens given; potentially leading to the same issues of discovering simple breaks.
The key to why this even works (and didn’t work before) is here: https://community.intercoin.app/t/paper-shows-relying-on-has...
Simply put, a reliable random oracle in an adversarial environment should be based on sources of randomness from multiple sources and participants, usually the sources are the participants’ meaningful actions to prevent collusion.
It has been known for quite a while that if the space of inputs being hashed is small, the hashing is relatively useless for most benefits of a true one-way function (eg hashing a phone number in USA).
I recall someone creating a crypto system and then forgetting to protect the constructor of the initial object so other could change the constructor and do whatever they wanted with that crypto system, but in the end the creators were just web developers with a little training in crypto.
In those circumstances those millions of coins flying in or out are not a tragedy (at least for me) but a very plausible outcome.
That's a completely different and unrelated type of vulnerability, though.
Implementation mistakes leading to mass coin theft would certainly be cryptocurrency news, but they would not be crypto(graphy) news. Breaking an actual peer-reviewed zero knowledge proof scheme would be.
Hashes should never be a source of randomness. Randomness makes assumptions far outside their intended use case.
Hashes should only be a reproducible label that cannot be used to produce the material described by the hash. When used for their intended purposes hashes serve as the strongest point of integrity until value collisions are discovered.
But once you've made a function that "cannot be used to produce the material described by the hash", you've also made a very good pseudo-randomizer. In fact, if a cryptographic hash function cannot be trusted for its ability to produce apparent randomness, then it cannot be trusted for its "intended purposes". You get both properties or neither.
This is broken logic.
There is an untested assumption that hashes achieve randomness because they appear to be a random collection of characters. Hash sequences are completely reproducible given a set of input, and that is by definition not random.
I think you are confusing loss of prediction as randomness. Never in mathematics or logic is that line of thinking correct. This can be described by equivocation, fallacy of composition, inductive fallacy, and more.
I think you are mixing the function itself and it's output, if for a given input to the function the output is uniformly random, then this is a way to derive randomness. The fact that the function itself is deterministic tells you nothing about the distribution of it's output.
You started your comment with a correct distinction, but got the wrong conclusion. Asking if somthing is random is actually a question about the process used to obtain some value and not the value itself. If I ask you if 42 is a random number, can you actually answer? I can get that number with an intrinsically random process based on some quantum effect, or I can say it from the top of my head because I just read a very famous book. You can indeed use an hash function to extract randomness, but, to be precise, we are talking about pseudo-randomness. The crucial difference here is that, if I'm measuring photons' polarization to get a random number, then an attacker repeating the same process will (very likely) obtain a different number. If I'm instead hashing some data, an attacker passing the same data through the same hash function will get the same result. Another example: if I hash the digits of pi, I will get a sequence that will pass statistical tests for randomness. But an attacker that knows how I am generating such sequence can easily reproduce it.
> There is an untested assumption that hashes achieve randomness because they appear to be a random collection of characters.
lol, no. Cryptographic hash functions are specifically designed to achieve this property.
> Never in mathematics or logic
Let's not get ahead of ourselves. Start with English - what does "pseudo" mean?
> This can be described by equivocation, fallacy of composition, inductive fallacy, and more.
For example, what is a pseudo-intellectual?
> lol, no. Cryptographic hash functions are specifically designed to achieve this property.
That completely ignores the definition of the word random.
What I find most interesting about this thread of comments is that the article explains the failure of using hashes as a means of randomness and despite that failure people are eager to ignore what hashes are otherwise used for to invent oppositional arguments. it's weird.
It's a lot less weird if you consider the possibility that you don't understand this as well as you think, and the reason people are consistently correcting you is because you are mistaken.
he said pseudo-randomness
And this still wrong for the same reasons. See: https://news.ycombinator.com/item?id=44521194
You're saying something being reproducible implies that it is not pseudo-random. This is a definition of pseudo-random that exists only in your head.
The first sentence of the wikipedia entry on pseudo-randomness is:
"A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process."
That misses a factor called good enough, or degree of predictability. Ultimately everything eventually becomes predictable if analyzed deeply enough. Another word for that is entropy. That is what my linked comment referred to. For security concerns, such as PRNGs, the appearance of randomness is not enough.
This is why security analysis requires a higher threshold than software employment at large.
A hash function cannot create entropy. Let's be clear about that.
A good hash function will preserve entropy, up to the length of its output. If the input X has K bits of entropy and H is an N-bit cryptographic hash function, then the entropy of H(X) is min(K, N). In simpler terms, GIGO.
However, a hash function also scrambles its input, which means the output is indistinguishable from (uniform) random noise. This is the randomizing property I was talking about. It is good enough for hash functions to be used to build stronger primitives, like HMACs, PBKDFs, CSPRNGs, etc. There are many formalizations of this property, but one of the simplest is that given any K bits of the output, you cannot predict the other N-K output bits any better than guessing, even knowing the algorithm.
Of course, if you know the input to a hash function, you can predict the output perfectly. But if you don't know the input, the hash looks like random noise, and for cryptographic hash functions, this is a very strong and fundamental guarantee indeed.
I agree that hash functions do not create entropy. That is what I have been saying all along.
> Ultimately everything eventually becomes predictable if analyzed deeply enough.
How would this apply to hash algorithms, but not CSPRNGs?
You may want to stay away from all modern CSPRNGs then. Eg Yarrow and Fortuna rely on sources of random input data being mixed in but using a strong hash function (nowadays sha-256) to produce the output at arbitrarily fast rates without consuming entropy.
And to your criticism that this is just programmers who don’t know what they’re doing, these algorithms were developed by Bruce Schneier, Niels Ferguson, and John Kelsey.
I was so frustrated as a noob trying to understand why people were using hashes this way. Even a professional told me "yeah but a collision is really unlikely," and compared it to neutrino interference. How is that supposed to be good enough?
Hash functions are used to instantiate a random oracle (which is a theoretical object that can't be instantiated because it would be of infinite size but makes it easy to reason about) because it doesn't seems crazy as an assumption that if finding a collision between 2 hashes is hard it should be hard to predict the output of the so called hash function. However it is well known that there was some contrive counter example for protocols that are secure under the Random Oracle model and unsecure when instanciated with any hash function. The problem with this paper is that the protocol it described isn't so contrive anymore. Cryptography is a matter of assumptions and what you believe in or not. You might want to not use random oracle but you will therefore have to restrict yourself in what you can concretely build.
And the reason behind the problem outlined in the paper isn't a biased randomness problem but the fact that you can represent the hash function compared to a RO.
Every hash function will have collisions as long as the input is larger than the resulting hash.
Some are designed that changing a bit has a massive influence on the resulting hash, others do the opposite.
Whether hashes are appropriate depend on the details of the usecase.
However, if the negligible chance of a collision is what you are worried about, those also happen with random numbers.
I'm sorry, but this comment is very vague and unclear.
Cryptographers know that hashes (even cryptographically strong ones!) are deterministic. Yet, it is possible that in going from an interactive proof to a non-interactive one, one does not actually need randomness. Indeed, for some class of protocols, we know how to design hash functions satisfying a particular property (correlation intractability) so that the resulting non-interactive proof is sound. It's just that (a) these hashes are inefficient, and (b) until now no one had found a non-contrived protocol where using standard hashes leads to an attack.
You should look into the HyperLogLog algorithm, where fair hash "randomness" is required for the algorithm to work. There are use cases where the pseudo-randomness of hashes is useful, is what I'm trying to say.
This is why you should NEVER trust software developers to make security decisions unless certified to do so. True randomness is challenging to achieve, because computers are inherently predictable. Pseudo-randomness is an intended process to intentionally achieve randomness in spite of this high predictability, often through use of physical or electromagnetic criteria outside the computing machine.
Hash algorithms are none of that. They are not pseudo-randomness merely because a software developer merely wishes them to be so. Hash algorithms are intentionally designed to achieve high reproducibility in that a given set of input should always result in the same hash sequence as output. That intended reproducibility is by definition not random.
You don't understand what pseudo-randomness means. Virtually all PRNGs, even many CSPRNGs, have a way to initialize the algorithm with a seed, and its outputs are fully predictable based on that seed. Choosing a truly random seed, such as one produced by RNG hardware, will lead to a usefully random sequence - but the algorithm is still fully deterministic based on that seed.
>True randomness is challenging to achieve, because computers are inherently predictable
Most modern CPUs now contain a true RNG. They usually use some combination of a metastable latch, or thermal randomness through some kind of analog amplification. Bit strings from this are passed into a pseudorandom number generator to amplify the amount of random data generated.
There probably attacks on this too but it's much harder.
More accurately, the CPU RNG instruction is generally considered untrusted by itself and the only reason it's used is that kernel RNGs are CSPRNGS based on cryptographic hashes (which is what the CS refers to - cryptographically secure) where mixing in a corrupted bit stream along with uncompromised bit streams still results in an uncompromised bit stream out. No one uses the CPU RNG instruction directly (both for security & also secondary perf reasons)
You realize all signatures in use today basically use hash functions as randomness
What? You’ve managed to mangle so many terms in so few words… Signatures can refer to two things: integrity checks on a file or authentication checks for a recieved file. In the integrity check situation a hash function (e.g., SHA) is often used. In the authentication check situation, we usually use a public/private keypair for asymmetric encryption; the hash function is only part of the process. The key material used to make this keypair (should) comes from some random number generator…
The ‘hash’ function is a deterministic transform, not a source of randomness.
He is technically not wrong, most signatures can be seen has a public coin interactive proof system where you prove knowledge of a private key. They are then compiled into an non-interactive proof system via the Fiat-Shamir transform that uses a random oracle concretely instantiated using a hash function (easy to see in Schnorr signature). So at the end you are using a Hash function to generate your random coin.
That is wrong. Most digital signatures in use today use certificates trusted through a certificate trust chain. The algorithms are different.
Internally, most signature algorithms use hash functions. RSA-PSS, EdDSA and ML-DSA use them to provide something like randomness, and the security analysis of those signature schemes includes arguments assuming (in some very particular, technical ways) that the hash function outputs "look random".
Classical DSA and ECDSA do not use hash functions this way, but in my opinion they aren't stronger for it: they're basically assuming instead that some other mathematical function "looks random", which seems riskier than assuming that about a hash function. I've heard that the reason for this is to get around Schnorr's patent on doing it with hash functions, which has since expired.
The SHA3 and SHAKE hash functions (underlying e.g. ML-DSA) are explicitly designed to "look random" as well.
There are some signature schemes that try not to make such strong assumptions: in particular SLH-DSA targets properties more like first- and second-preimage resistance, target-collision-resistance, and so on.
All the algorithms you mention are PKI. RSA uses two large prime numbers. I don't see what hash sequences have to do with this at all.
PKI isn't even really about randomness. RSA does use a kind of randomness to generate its large primes, but that is beneficial and not required. The primary consideration is the math to reverse guess a factor of two primes or the square root of a large number, or something else computers currently find cheap to compute in one way but extremely expensive to reverse.
The intro textbook descriptions of cryptographic systems omit a lot of very important details.
When using RSA to sign a message m, in practice you don't send m^d mod N. That would generally be insecure, depending on what kinds of messages your system sends and/or accepts. In practical systems, instead you hash m, and then adjust the hash through a (possibly randomized) process called "padding" to be a value in [0,N). There are different standards for padding, and the better designs use additional hashing.
The security of the system depends in part on the hashed-then-padded message "looking random", i.e. not having structure that can be exploited by an attacker. It turns out to be tricky to formalize what exact randomness property you need, so cryptosystems are often analyzed in the "random oracle model" (ROM) in which the hash function has impossibly strong randomness properties.
It seems that usually, if you use a strong hash function, a scheme that's proved secure in the ROM is secure in real life (or at least it's not the ROM part that breaks); the counterexamples are usually really contrived. This article is about a somewhat-less-contrived, but still not quite realistic, example where something that's secure in the ROM would break due to the ROM being an unrealistic model.
It's not wrong. The only thing preventing me from forging your certificate is my inability to generate a new cert which hashes to the same digest as what is in your cert's signature. I don't actually need the keys if I break the hash.
EDIT2: I'm doing a bad job of explaining this... you obviously need the keypair associated with the cert to initiate connections with it and not trigger MITM alerts. But if you break the hash function, you don't need the private key from the root cert, the verbatim signature from the original cert will appear to be valid when spliced into your forged cert if the hash digest computation on the forged cert is the same.
And checking the validity of a certificate involves checking a signature of... The certificate's hash. If you can break the underlying hash function, then the trust chain is broken.
I find the actual paper more readable and understandable than this summarization.
https://eprint.iacr.org/2025/118
I also had to just go to the paper. It was really difficult trying to get through the article. Needlessly hyped language like "proving lies" and hyperfixations on things like leaking boats... felt like the author was either out of their element or inexperienced with math comms. However, the article still provides a bit of context that the paper doesn't.
That said, this is honestly just a bad article that is needlessly sensationalized and fails to impart any real knowledge.
(Note: the original title was "Computer Scientists Figure Out How To Prove Lies" before being changed by the admin)
I honestly think that Quanta Magazine just found the perfect formula to farm HN traffic. The titles are clearly carefully engineered for this audience: not the outright clickbait of university press releases, but vague profoundness that lets us upvote without reading the whole thing and then chime in with tangential anecdotes.
I don't think they're bad people, but I honestly think they end up on the front page multiple times a week not on the quality of the articles alone.
> That said, this is honestly just a bad article that is needlessly sensationalized and fails to impart any real knowledge.
There's a joke to be made here, since the issue is with zero-knowledge proof systems.
I recommend this whiteboard session as well o.o https://blog.zksecurity.xyz/posts/pudding3/
They do at least link to that in the 4th paragraph of the article. Many of these summary articles don't do that.
That's the case with many cryptographic explanations for laypeople, in my experience (as mostly a layperson).
Maybe all these elaborate analogies of Alice walking into a cave and Bob yelling which exit she should come out of, Alice wanting to sell Bob a Hamiltonian cycle trustlessly, Alice and Bob mixing buckets of paint and shipping them via the mail back and forth etc. are working for some people, but it's not me.
[dead]
[flagged]
[flagged]
> This is why all of crypto is a fraud...
Are you using "crypto" here to mean "cryptocurrency", rather than "cryptography"? Because if so, that's not obvious considering you just mentioned cryptographers in the previous sentence.
If, on the other hand, you mean "all of cryptography is a fraud", then I'm curious to know what makes you think that.
Sorry, "cryptocurrency".
Cryptography is big enough that you can't expect every academic cryptographer to be intimately familiar with every obscure theoretical result.
Yes, all cryptocurrency is basically a scam, but that's independent from whether the Ethereum foundation's experts know X or not.
One anecdote => All Ethereum’s cryptographers are a fraud => All crypto is a fraud
You're deducing a lot from this one quote lol
"all crypto is fraud" stands alone just fine. It's very clear that the blockchain is 100% BS to anyone who is not incentivized to see it as valid.
> "all crypto is fraud" stands alone just fine.
It might, but in this case it is preceded by "This is why", which makes the sentence as a whole simply wrong.
And "this is why" is preceded by "they don't know their own critical specializations history" Which is the complete statement.
hard disagree here. I think crypto currencies are built on hype and bluster and scams, but blockchain as a technology is actually super interesting. There are plenty of cool use cases for an open immutable ledger that aren't scammy.
right, because there's no other way to prevent modification. no other way. also it's not possible for a single operator to have 51% of the compute in a blockchain.
both of those are obviously false and both have already happened.
blockchain is stupid. it is insanely inefficient, it burns power solely so you can say that you've burned power. it is stupid beyond belief.
51% attacks, on anything at a large scale, are generally more theoretic than practical. The amount of resources you'd need to invest to achieve that on any large currency are astronomical, and you'd need to just completely wreck everything engaging in widescale fraud (which would be a felony, carried out repeatedly and at scale - and likely fairly easy to tie back to you given the massive resource investment to get here in the first place) to try to recoup your losses.
The most probable outcome being a rapid fork and rollback as already with e.g. Ethereum over a relatively negligible amount of money relative to what you'd need to get a 51% on Bitcoin. You'd likely end up losing a massive amount of money, as well as look at possibly spending the rest of your life in prison. So the only real purpose in doing so is for attention or trolling, but the costs involved generally preclude this motivation.
Hard focus on one use case, albeit most famous and has some properties you mention.
There are other use cases, like it or not. And its popularity - don't blame tools for basic human greed they only allow to be manifested, that's not a smart approach to get anywhere apart from endless complaints how this and that sucks.
What's the other way?
the same way you prevent modification on anything else.
Please elaborate specifically how you would do it for a byzantine-safe distributed network.
how do banks do it now? you know the answer, at a high level. it's the same way we prevent unauthorized access when the blockchain isn't involved, and it's how we prevented unauthorized access before the blockchain existed.
it's how banks prevent someone from withdrawing money from your account without your permission, everywhere across the entire globe at once, all the time.
it's the same reason that I, a normal user, can't delete people from active directory at work, or change their passwords to mess with them.
you've dealt with this kind of permission system your entire computer-using life. you know how it works. you know what it is. being distributed doesn't matter at all.
Blockchain isn't just distributed, it's decentralized and trustless.
We live in a time where any form of centralized authority is increasingly abused. Blockchain prevents this. It also prevents incompetence as we also live in a time where centralized data and credentials are regularly leaked or hacked with no recourse available.
You’ve been drinking too much kool-aid.
which is???
how do you not know this? think about that. think really hard. you can do it. how do people prevent unauthorized access when the blockchain isn't involved, or before blockchains existed? really, really think. you know the answer.
take as much time as you need.
At least 3 of us really want you to tell us. I suspect you have a massive misunderstanding of the topic but you have your chance to explain.
If you don’t already know how simple permissions, read-only storage, and digital signatures work, I don’t think that you have any business telling anyone that they’re misunderstanding anything.
Bitcoin was made to solve problems that exist only in the minds of those who wish to make money with bitcoin. Other blockchains serve the same purpose. Zero people use it as a ledger, except as a joke or to prove how stupidly limited and inefficient it is.
Bitcoin also has created problems that didn’t exist prior to the invention of the blockchain.
So, aside from the myriad negative effects of the blockchain, it is wholly and completely pointless unless you think it will make you money. If that’s how you think of yourself, you are a parasitic scammer spreading ransomware trying to make people think you are a legitimate human person with a right to live.
You're too far gone. I am not bothered trying to help you.
[dead]
All money is fraud, but we still use it.
> It's very clear that the blockchain is 100% BS…
Hmm. The blockchain is actually a very clever solution to a very old coordination problem. In that sense it is not BS at all.
But I agree that it is an open question whether it can directly support a useful economy the way a currency can. It doesn’t seem to have the throughput for that, to start with. But maybe it could be useful for interbank settlements, if for some reason traditional methods weren’t working.
This has been known for a long time that in order for crypto backed securities to work, Bitcoin’s blockchain would need to be the clearing house for assets tied to it. We’re in derivatives of derivatives of indexed derivatives land.
Banks have already started exploring using it as the clearing house and recent US policy has cleared the path for more.
My hot take, crypto(currency) is for pure peer markets, since all individuals are accounted for by a government its not especially useful for people. However, governments are essentially peers without some disinterested third party with the power of enforcement. This is place where crypto lives.
Yea, something like that. Although even there you still have bond ratings and just straight up reputations to tell you which governments are trustworthy enough to do business with, even without a blockchain.
blockchains and bitcoin are good for two things only: money laundering, and collecting ransomware payments.
blockchains as an immutable ledger should be the dumbest thing anyone has ever heard of. but somehow people saw dollar signs and put aside all their reservations and are using it to try to get rich quick.
as if a set of banks are going to secretly conspire to remove your money from you specifically, without a paper trail, or something. it's a nonsense premise to begin with.
That piece of information about Ethereum's cryptographers does not mean "all of crypto is a fraud".
No, but if crypto was generally legit, one might expect the people working on Ethereum cryptography to know their area of specialisation...
Two of the authors of the paper listed their affiliation as the Ethereum foundation.
It seems more like the project was doing due diligence?
How about Silvio Micali in the Algorand world? How does ethereum make Algorand not legit?
Again, you mean "if Ethereum was". You're conflating things.
not really. Ethereum is pretty big and sometimes central to other crypto projects.
you're right. "all of crypto is fraud" and the Ethereum cryptographers not knowing about this important detail are two statements that are true separately.
Made me laugh, then chuckle. Both funny and logic joke funny.
> Ethereum’s cryptographers are not cryptographers
I guess I'll bite, what are they then? If they're focusing on the cryptography of a project, doesn't that make them cryptographers? Or you mean they aren't "real cryptographers"?
> It's a wish club of technical yes people.
Isn't that basically one of the ways doing innovation? Instead of saying "No, that's not possible" when someone asks if they can build something faster than a horse and carriage, a bunch of people get together to see if there any way of doing that, trying to avoid any per-concieved ideas about if it's actually possible or not.
Isn't that basically one of the ways doing innovation? Instead of saying "No, that's not possible" when someone asks if they can build something faster than a horse and carriage, a bunch of people get together to see if there any way of doing that, trying to avoid any per-concieved ideas about if it's actually possible or not.
Yes, but if people graduate from engineering schools that explicitly teach the concepts of the combustion engine, and the carriage manufacturers claiming to be engineers are unaware of basic principles like the 4 stroke cycle, you have a completely different kind of problem.
It's the old "we use first principles thinking" approach. Too often it means "we don't actually know or care what came before us, we just move fast and break things, how hard can it be lol yolo" Then that's what you get, insufficiently educated folks re-inventing the wheel, repeating mistakes others have done before.
Yes, sometimes you need to break out from pre-conceived notions, evaluating whether conditions have changed and earlier assumptions are maybe not valid anymore. But that's no excuse to be ignorant.
> Isn't that basically one of the ways doing innovation? Instead of saying "No, that's not possible" when someone asks if they can build something faster than a horse and carriage, a bunch of people get together to see if there any way of doing that, trying to avoid any per-concieved ideas about if it's actually possible or not.
This does not take real-world limits into account. There are limits to information theory (which includes crypto), thermodynamics and mechanics that make certain things generally impossible. Like a perpetuum mobile. Social or intelligence factors do not matter. Knowing your field also includes understanding those "hard" limits.
lol. I work in Applied cryptography and I don’t know a harder distributed system built on such a broad spectrum of primitives which has seen such high uptime.
Are you qualified to speak on this topic?
[flagged]
What is a lie? what is the truth? It is very difficult to find the truth, and the descriptions of the same thing are different for different persons. So the title and its content is a lie.
There is a famous "4 theories of truth" classification: Correspondence, Coherence, Consensus and Pragmatic.
In this case they are talking about mathematical truth, which is a case of Coherence truth.
For mathematical truth, there is an example, please search "The Limitations of Euclidean Geometry"
Can you recommend a book that expands on this classification?
I'm not aware of any book about this, but I've read it in several blog posts, like this one: https://commoncog.com/four-theories-of-truth/
In context, these terms have specific definitions where this is not an issue.
Your question is very simple to solve for someone who has done enough real philosophy lol :) a lie is when you tell something differently than it is. the truth means "what exists as it is".
If you say that "it is difficult to find the truth", aside from the blatant subjectivity of your claim, then , if we believe your statement, then that itself must be a "truth". And yet you invalidate your own claim immediately by saying "different for different persons". Well, if that statement is true, then it invalidates itself as well.
You cannot disprove the existence of truth by using a system that relies on truth and falsehood.
You seem to have some misunderstandings about truth. Many truths are our understanding of real existence, not existence itself. Obviously, our understanding of complex things may be different, but complex things do exist.
For example, the movement of things exists, but Newton's understanding of this existence is different from Einstein's understanding of the same existence (or the movement of more things).
this is a lie
Please understand the restrictions of Newton's Laws of Motion, many years ago, some people think they are right in every environments. My point here is it is difficult to get the truth for somethings. the title means proving everythings whether they are lies.
source?
> and the descriotions of the same thing are different for different persons
When my son says, "I wasn't there" when the glass broke, it's not just a matter of differing descriptions, it's a clear denial of a fact. There are facts, and when someone deliberately twists or denies them, that's not just a different perspective. That's a lie.
You are right, for somethings, the truth is clear, but for other things, it is difficult to find the last truth, only reach its truth over time
> it is difficult to find the last truth, only reach its truth over time
The fact that is difficult to find out the truth, does not mean that something was or wasn't a lie. Paradoxically this is an attribute of a "good" lie: it is difficult to find out that it wasn't the truth.
I think this is a good example of a lie because you and your son both have a shared understanding of the world and he is deliberately saying something he does not believe to be true (that does not match his own internal recall of events).
There is a physical component to this lie but it seems to me that the social part dominates.
Yes, They have the same understanding of the meanings of the words "I", "was", "not" and "there", and the sentence.
That’s not the point. You know your son knows what happened - knowledge of his mental state. Not that you have a physical proof about the chain of causality.
My initial prediction is they just divided by zero someplace - just like every other undergrad in any degree program that requires some advanced math has. I'm happy to see they didn't make this obvious mistake.
>if a professor has assigned 100 problems for homework but doesn’t want to grade a student’s entire assignment, she can randomly choose 10 problems to grade. In the language of computer scientists, she is making 10 “random challenges” to the student’s homework. If the answers to those 10 problems are correct, the professor can feel confident that most of the other answers are correct too.
Eureka! I found the reason that so many things in society have gone to shit in the last few years. Far too many professors are so overworked or maybe just lazy and are using this type of tool to grade student work and the end result is that we have too many students passing through the system who have demonstrably only been able to score a 10/100.
I'm over 60 now and if I had scored lower than my current age back in the day I would fail and need to repeat the grade/course. Now they just kick the can('ts) on down the road and hope no one ever notices.
Too bad some of these failures end up in positions of influence where their uncharted deficiencies have the power to disrupt or destroy functional systems.
Or maybe I'm joking. I'll know once the caffeine hits.
If the questions are randomly chosen, the probability of the true score being 10/100 in that scenario is 10!/(100!/90!) ~ 6e-14
I'll accept your math this morning with the note that without checking the other 90/100 answers you have no way outside of accepting probabilities to know whether your random examples are representative of the quality of the full set. It becomes a "trust me bro" situation.
I processed hundreds of thousands of miles of seismic data in my career. The first thing we needed to do for any processing project was to select a subset of the data for use in defining the parameters that would be used to process the full volume of data. We used brute stacks - a preliminary output in the process - to locate interesting areas with complex attributes to make sure we could handle the volume's complexities. In industry slang these were "carefully selected random examples".
It was inevitable that we would find a situation during the processing for which our parameters were not optimized because we had missed that edge case in selecting the examples used for testing.
In the same way in real life if you only demonstrably know that 10% of the test answers are correct then it is also true that some edge case in the 90% of untested answers could leave all or part of that untested space false or sub-optimum.
If there was a point to my original post it is this. You only know something is true when you have proven it to be true. A maximum likelihood of truth is not a guarantee of truth it is only a guarantee that it is likely to be true. You won't know how sharp the sting will be until you peel the onion.
Having checked an answer also doesn't guarantee anything with certainty. Which, coincidentally, is the actual topic of the OP, the grading was just a tangential example and not a description of something actually happening anywhere in practice. But sticking with the grading example, the failure modes could be much more benign, such as the examiner failing to spot a mistake, or the answer being copied,...
Probabilities aren't a matter of faith, they're mathematics and as such represent a logical trueism. Your critiques are just nitpicking for the sake of it and void of substance. Have a coffee and leave this topic.
>they're mathematics and as such represent a logical trueism
I'm a full pot in now and find that I agree with this.
The fact is though that the article demonstrates that something previously considered logically true or a maximum likelihood was proven false.
It's great to see that there are people, whether they're mathematicians or cryptographers, who will take a look at something that has been a useful part of a stable process of verification and try to find cracks or instabilities. The fact that they found an edge case that could be exploitable undermines trust in an important part of the process.
Trust - but verify, wins again. Logically, this is the best way.
> You only know something is true when you have proven it to be true. A maximum likelihood of truth is not a guarantee of truth it is only a guarantee that it is likely to be true.
Better not use cryptographic signatures then
Now calculate the probability that the professor at random selects the exact 10 problems that were solved correctly.
Your Eureka moment seems to be misinformed - I hope you can have it returned for another occasion.
It's just a random decaffeinated thought here this morning. Considering that it must be true that even a blind squirrel gets a nut once in a while it is also likely to be true that a professor at random can select the exact 10 problems that were solved correctly.
There's a difference between something with a probability of being true and another thing that is proven to be true. There are no doubts remaining after the proof whereas the probability always leaves wiggle room even if that wiggle room is a pretty tight space.
We should be careful about using probable and possible interchangeable.
You are right - it is possible that is happens but not probable.
However, overly focusing on this really deprives you of a lot of great intellectual stimuli from randomized algorithms and, like here, a large chunk of cryptography.
>However, overly focusing on this really deprives you of a lot of great intellectual stimuli from randomized algorithms and, like here, a large chunk of cryptography.
I agree with your first points about using probable and possible carefully. I originally posted a bit of a tongue in cheek, carefully selected example, from the full text of the article since that example fit the point that I hoped to make in jest. It was my carefully selected random example.
I think the focus of the article is on demonstrating that a tool used in cryptography to verify truth was widely assumed to be infallible and it turns out that is unfortunately not true since it can be manipulated to identify false results as true. This tool uses probabilities as a tool to minimize compute times that would be enormous if one had to verify absolutes so it is an important tool. Now that it is demonstrated that it can be successfully attacked, the basis of the system of verification is vulnerable and in the case of Ethereum at least, monetary losses can result.
This is just an analogy used by the article to explain the Fiat-Shamir transform.
Why would they not simply, assign 10 problems?
There is a risk here that the professor who only assigns 10 problems will only check one of them for correctness. If 5/10 of the answers are wrong but the professor verifies a correct answer for one of the 5/10 with a correct solution then their conclusion that the other 9/10 answers are correct due to some likelihood or probability function is invalid and a dimwit makes the grade.
Maybe professors should flip the script, instead of testing a student, have the student convince the professor they know the material. You will not pass until the professor feels confident.
Sounds a dissertation format maybe.
Presumably more questions can cover a wider variety of skills/techniques/topics. If the student doesn't know in advance which 10 will be selected, they either have to pray they're lucky, or work diligently on all problems.
presumably they glance at the other 90 too, and they then do a thorough verification on that random 10
the analogy is not great, but in cryptography something similar is at play (easy to get/check trivial properties and then hard to achieve/produce/fake the interesting ones)
they were shit all along, but the energy (and productivity) surplus allowed for decades of amazing growth, which created the feeling of prosperity
unfortunately most people doesn't understand (and as a consequence doesn't appreciate) how little wealth we have compared to capacity, in other words how much upkeep we do to maintain that wealth
and now that it's time to scale back the waste a bit people are up in arms
As the caffeine sweeps through my system activating latent stores of energy and powers of analysis, I find that I appreciate this response without needing to understand all of it. It's a bit like assuming that the remaining 90/100 answers are correct after only verifying 10 of them.
I feel like I have accomplished more than I actually have and so I have plenty of incentive now to sweep through all the work of the day hoping that each randomly selected set of results yields similar levels of perfection and that all the inaccurate answers assumed to be correct do not cause the student to make assumptions in later life about things that are not supportable by facts.