Parsec: discussion about Liveness proof

parsec

#1

From what I understand the only known problem is that it seems hard to say that Pasec is fully asynchronous because if something is fully asynchronous then it may never reach a decision. Otherwise it does not seem like their is another problem, otherwise Vlad Samfir would probably gladly point that out since he looked at the whitepaper and Parsec is a competitor to Ethereums Casper. Disclaimer I’am not a mathematician either but it is what I got out of the conversation when Vlad pointed out that liveness with asynchronous was little problematic. I’dont want to bother Pierre as he probably has better things to do but I tag @pierrechevalier83 if he would like to weigh in on something because I’am walking in deep waters and may have understod things wrong. But I think you can sleep with ease of mind Sascha. :wink:


MaidSafeCoin (MAID) - Price & Trading topic
#2

If something is fully asynchronous then it may never reach a decision.

It’s not exactly that but you’re close. We do have an issue with proving Liveness in an asynchronous setting because of a specific part of our algorithm: the concrete coin. It is not theoritically impossible to get liveness in an asynchronous setting. In fact, I am pretty convinced that when we get a bit of time away from the coding and look at the concrete coin again, we can create one that is strictly asynchronous.

The only reason we’re not alarmed about it and trying desperately to fix this part of the algorithm at the moment is because being strictly live in an asynchronous setting may not be necessary to be practically live in an asynchronous setting.

For instance HashGraph has a similar issue (actually, they’ve put less thought into fixing it than we have with our concrete coin, so theirs is more likely to be an issue in practice) but they haven’t bothered trying to address it because they don’t think it’s an issue.
Even the blockchain isn’t asynchronously live in theory, but it doesn’t prevent it from being useful without any use of time.


#3

When it comes to cryptography or mathematics, it’s generally not enough that something “seems” good. Especially if it’s a novel proposition. If there were proof, Vlad wouldn’t just be quiet. He would possibly even promote the tech.

But I’m grateful to Pierre for taking the time to explain some of this stuff non-formally here.


#4

Vlad is sitting on the throne with one of the biggest crypto market cap project, he has alot to lose and don’t want anything to be as good or better than what they are doing. He clearly shows that in the conversation between him and Maidsafe but Parsec was that good that he couldn’t resist give them a compliment, something like “They show more skills than most other crypto project teams”. I think it was his way of saying that they did a realy good job because he is tied to say anything that would compromise Ethereums power position.


#5

If there were proof

We have proofs for our claims in the paper. There is an issue with the liveness proof as discussed here (for now), but the general approach is mathematically proven.


#6

I did a summary of the conversation between Vlad and Maidsafe awhile ago, if you have not read it and want to take a look. Not just another decentralized web whitepaper?


#7

Specifically, we prove Validity, Agreement, Integrity and Termination (aka Liveness). The last one has a hidden syncrhony assumption, which is why we don’t claim to be fully async, but all the rest holds.

These are the properties you need to prove to prove a BFT consensus protocol.


#8

Thanks guys! I was a bit worried there was more to Vlad’s first criticism, but now I guess PARSEC really is solid. Not being a mathematician myself it’s difficult to say. (I have studied a bit of logic, and I did prove 2>1 or something like that for some assignment at uni about 20 years ago. As I recall it required about four handwritten notebook pages. Now I wouldn’t even know where to start. :slight_smile:


#9


#10

Hi,
Quick question please:

Did you get a chance to look at Cosmos-Tendermint Byzantine fault-tolerant (BFT) consensus
(https://cosmos.network) ?

Thanks


#11

@pierrechevalier83 Just need to comment how happy I am to be somewhat close to understand the livness issue. :rofl: When Vlad mentioned it I had to look up the definition of statistical livness. :sweat_smile: I’ve also studied logic and half a year of statistics but I can assure that it was not enough. Remember my bachelor thesis where I was lucky that the examiner was not that expert on statistics. Should have done a multiple panel regression but we had no support so it ended up as a simple cross-section regression. The examiner only commented that maybe 0.6 correlation of some variable could be close to auto-correlation, then i laughed inside my head and thought that maybe if the correlation was over 0.8 then maybe I would consider auto-correlation. Just a funny memory to share. :grinning:


#12

I guess I skipped the spreadsheet stage (except for keeping track of what hen lays her eggs where she’s supposed to, instead of hiding them in the woods). But I have learned how to turn a raccoon dog into a piece of clothing using just a knife and some salt. So also back to basics in its own way. :wink:


MaidSafeCoin (MAID) - Price & Trading topic
#13


MaidSafeCoin (MAID) - Price & Trading topic
#14

Tendermint is a variation of PBFT, from Castro and Liskov, and is not asynchronous (to be more precise without the very weak synchrony assumptions that have Parsec) and not leaderless.

In fact, removing the gossip termination mechanism and the leader election, is quite similar to the consensus that is currently working in the Safe Testnet 2 witch is also inspired of PBFT.