Hashgraph Consensus Timing Vulnerability


#22

(Disclaimer: I am not endorsing Hedera Hashgraph in any way)

I played with the Hashgraph consensus a while back, and understand how it works rather well. Not a PhD, so feel free to disregard my comment entirely :slight_smile:

The vulnerability you described depends on how exactly you use HashGraph. If you wait for a transaction to receive a round receivable, then your vulnerability doesn’t work. Consider the algorithm on page 14. The median timestamp is computed among the events that are reachable from the round r unique famous witness, where r is the round receivable of the event with the transaction in question.

Assuming other proofs in the paper are not wrong, once the round receivable is assigned it doesn’t change, the unique famous witness is known by definition, and doesn’t change either, thus the set of events reachable from it doesn’t change as well, neither does a median timestamp of them.

Note that if you don’t wait for the round receivable to be assigned before executing smart contracts, that your timing attack is also somewhat incomplete, because the events are first sorted by the round receivable and only then by timestamp, and since you don’t know the round receivable for the event yet, you cannot just look at the timestamps of two events to attempt to predict their order.

Unrelatedly, something I personally found funny about hashgraph is their coin rounds (see bottom part of page 10). They effectively say that their voting for famous witnesses can stall under certain conditions, and to account for that every now and then they would have all the witnesses vote randomly, and since there’s a chance that 2/3 of votes will end up being the same, that will unstall the algorithm. This can give you an estimate of how many witnesses they plan to run, because even for 20 witnesses the chance that in 20 coin tosses more than 2/3 will end up the same is very low.


#23

Understood :slight_smile: My objection to Hashgraph is fundamental. IMHO it is impossible to cheaply transform DAG into a linear ordering required by blockchain. The reason for this is because linear blockchain ordering is equivalent to a binary consensus for each block, and asynchronous binary consensus is expensive, the best known asynchronous binary consensus algorithms are N^2. DAGs are much cheaper to build. So it is fundamentally impossible for Hashgraph to end up with a linear ordered consensus and run smartcontracts on it. It is unfixable imho, the entire chain of thought of Hashgraph is wrong and insecure, because they do not understand that DAG and linear ordering are fundamentally different.

And the reason why they do not understand is because they are not mathematicians or computer scientists and are not able to specify things in logical way. The entire paper is a joke imho.


#24

“They are not mathematicians or computer scientists” is an attempt to appeal to authority.

I wanted to use Hashgraph for Near, and read all the proofs very carefully, as well as had an implementation that I stress tested, and I am personally convinced that it does properly order transactions. I also understand the algorithm very well, so if you want to try to break it, I would be happy to answer any questions.

Note that before a round received can be assigned, at least one round needs to pass, and a round requires 2/3 of participants to observe that 2/3 of participants observed a witness message for the round (so called “strongly seeing”), and computing this property for each message cannot be done faster than O(n^2) of compute. Since a consensus for a particular transaction takes on the order of O(n log n) messages, it takes O(n^3 log n) compute on each node to reach a consensus for a single transaction (this gets amortized when you have multiple, so ordering k transactions takes way less than O(k n^3 log n), but I don’t have an exact estimate handy). This computation cost is why I personally ended up not using Hashgraph. But it somewhat should address your concern with the complexity – Hashgraph is by no means cheap.

Again, disclaimer: I’m attesting to the validity of the Hashgraph consensus algorithm, but do not endorse the Hedera Hashgraph protocol in general.


#25

First of all I must say that kladkogex communication style appears very annoying to me, almost like a textbook version of a stereotype Russian troll. This is unfortunate as the topic is super interesting IMHO. Personally I would like to see a valid counterexample to the hashgraph consensus, so I decided to get into the discussion despite the annoying communication style.

Ok, first of all we need to clarify what we want to achieve and I propose the following:


Proof that hashgraph consensus is not a byzantine fault tolerant atomic broadcast algorithm under the assumptions made in the hashgraph paper.


Do you agree? (Please no moral, hate talk, accusations bla, bla… Its hard enough to go that road with you anyway. Stay scientific, ok?)

Ok, how do we do that? BFT atomic broadcast, which hashgraph claims to be, is defined by the following four axioms:

1.) Validity: if a correct participant broadcasts a message, then all correct participants will eventually receive it.

2.) Uniform Agreement: if one correct participant receives a message, then all correct participants will eventually receive that message.

3.) Uniform Integrity: a message is received by each participant at most once, and only if it was previously broadcast.

4.) Uniform Total Order: the messages are in a total order in the mathematical sense; that is, if any correct participant receives message 1 first and message 2 second, then every other correct participant must receive message 1 before message 2.


The task is then to find a concrete counterexample to one of these axioms. This boils down to finding a time-series of concrete hashgraphs (for users A(t),B(t),C(t),…) which violates one of the previous points after we run the algorithms of the paper on it.

Now kladkogex claimed in the initial post to have found such a situation. Unfortunately his example missed the actual hashgraph. So kladkogex can you please rewrite your example into an actual series of hashgraphs for users A,B,C,…, so everyone can run the algorithms on it (by hand) and see the contradiction? After all you made very strong accusations and according to the rules of science, which you brought stubborn into the game, the burdon of proof is on you. As you accused craigdrabiktxmq as being mathematically imprecise it’s now your turn to make your also mathematically imprecise proposed counterexample precise, so we all can see that it works.

I think its enough to write the appropriate hashgraph related to your counterexample with pen&paper and then send a picture of it here for discussion.

P.S: Leemon Baird was a professor of mathematic by the time he wrote the paper. He wrote >40 other math papers. This of course does not mean, that it is correct. Personally I like the style of the hashgraph paper.

However, I’m not a fan of Hedera, not the least! I think they are like the pest for decentralized payment and I would love to see them fall. But we have to do it properly. Its David against Goliath and David can not afford to rank high on the crackpot index, if he claims any chance in this battle.


#26

This post was flagged by the community and is temporarily hidden.


#27

Atomic Broadcast and Weak Synchrony?
I will repeat what is already written and referenced about the hashgraph timing:
“The validity is dependent on the (directly or indirectly) outgoing edges of the transaction, which represents the nodes that have validated it. A scale-out throughput can be achieved if the acquirement of the complete graph is not obligated for all nodes. Then, the validity of the transactions is compromised due to its dependency on the validators”.
A Scale-out Blockchain for Value Transfer with Spontaneous Sharding, Zhijie Ren and four more authors. Link here: https://arxiv.org/pdf/1801.02531.pdf