Multiple questions on the Casper protocol including equivocation and liveness  

  RSS

Kelly
(@kelly)
Member Admin
Joined:6 months  ago
Posts: 5
23/03/2018 2:25 pm  

Originally published to #cbc-casper channel on Discord on 3/22/18. 

I'm reading the CasperTFG.pdf ( https://github.com/ethereum/research/blob/master/papers/CasperTFG/CasperTFG.pdf)...  

I can see how the protocol will never fork if there are fewer than t faults - i.e. that we will not be "safe" on competing outcomes... but that part is almost trivial - or shall I say, by construction? 🙂 - but what is not clear to me is that we will always converge on a choice at all.

It would seem to be properties of the evaluator that determine convergence and we'd have to examine the evaluator in detail, (along with the distribution of weights) to determine how many bad actors we can tolerate.
In this case a bad actor is not equivocating in the sense of running multiple instances of the protocol, but rather carefully choosing which messages from other validators they chose to pretend not to have seen in order to move the estimate back toward uncertainty and keep it there. Of course the justifications in the protocol messages are included precisely to make this type of thing very hard to do, but it is not impossible.

[not sure I'm making myself clear. also not yet finished reading... I read section 4 next]

-----

I see later on in section 7 that "liveness considerations are considered largely out of scope, and should be treated in future work." ... I suppose I was asking about the 'liveness' property.

------

another question about "equivocation" as defined in the document. Suppose I have total validator weight T but that I am split into three identities, a tiny one (v) with weight t and two others V¹ and V² with weight 0.5 * (T-t) each.

Let's say we're doing a binary consensus.
V¹ sends a message of zero, V² sends a message of one. and with account v I will equivocate.

Then I can create a valid message with estimate of zero and total weight T. This message comes from V² and has V¹ and v voting "zero" as justification. I send this message to Alice.

On the other hand I can send a message from V¹ to Bob, voting for "one" with justification being V² and v voting "one". This is also valid and has total weight T.

So did I just manage to send two messages of weight T, with different estimates, one to Alice and one to Bob but with only tiny 't' counting as equivocating?

BTW I'm typing these questions as they occur. I'm not saying that this is exploitable per se. In particular it seems I can only do this once.

My thought process was: what would I have to do to prevent finality - sending estimates of zero to those who estimate 1 and sending estimates of 1 to those who estimate zero...

I could probably do this without equivocating at all by using small v¹ and v² and getting a weight T-w(v¹) instead of T.

it's just that what I feel that equivocation is is not the same as the definition - of running multiple instances of the protocol.

I'm trying to think if I can split my weight carefully into many accounts and using only tiny amounts to "equivocate", by carefully selecting when to send which message to whom, I might be able to confuse the other long enough to noticeably delay finality... OK, I guess this is just my liveness question again....


MichaelBirch:-Yesterday at 1:03 PM

@cobordism: You can't get liveness in any distributed consensus protocol in an asynchronous setting by FLP impossibility. But in the partially synchronous setting you can and I think @Vlad: has a livelness proof for Casper in that case. The essence of it is that in Casper if everyone has the same information they arrive at the same conclusion (because the estimator is specified in the protocol), so long as there are not more faults than the tolerance. In the partially synchronous setting there is a bound on how long it takes information to propagate, and so also a bound on how long before everyone will agree (or consensus failure will happen due to breached fault tolerances).

As for equivocation, don't think about multiple validators being controlled by the same external user -- that's not what is meant. Instead we mean that the only way to explain the sequence of messages we have seen from a single validator would be if that single validator were executing two different instances of the protocol (because some messages mutually do not justify each other, but a single protocol instance will always have a well ordered sequence of justified messages)

It could be the case that a single external entity is controlling many validators, and that is totally fine if each validator follows the protocol correctly

 

cobordism:-Yesterday at 1:09 PM

I know that we cannot prove liveness. But I want to know how hard it is for someone to prevent consensus for a long time.

and yes I know the definition of equivocation used and no I don't think of it as one person controlling multiple accounts....

I think that there are other faults than those "equivocations" defined in the paper...

for example you can pretend to not have seen specific messages as a tactic to delay finality.

In the meantime another question: I am two validators of equal weight. We are doing a binary consensus. If the weights are equal, my estimator is allowed to be arbitrary.

I vote 0 with account A and 1 with account B as initial message M_0
Then I vote 1 with account A (citing B's M_0 as justification along with my previous message) and I vote 0 with B (citing A's message as justification along with my own previous message).

Question - can I do this over and over? always pretending to just have seen the other accounts previous message and choosing to flip my vote (as the estimator allows) ... as long as I never acknowledge receiving any other message from anyone else?

This is not equivocation as defined in the pdf

even though I can send 1 to some people and 0 to others

 

MichaelBirch:-Yesterday at 1:11 PM

> for example you can pretend to not have seen specific messages as a tactic to delay finality

That's called censorship. It is another type of attack, but the problem with it is that you cannot prove someone is censoring in an asynchronous setting because messages can take arbitrarily long to arrive. In a partially synchronous setting you could make censoring a slashing condition (as in change the offending validator's weight because they have broken the protocol).

(In proof-of-stake validator weight = staked tokens of some value, so slashing conditions use economics to protect the protocol)

 

cobordism:-Yesterday at 1:13 PM

I think we are talking past each other. I am not talking about any censorship.

and the messages I suggest sending above are not slashable(edited)

 

MichaelBirch:-Yesterday at 1:16 PM

It's not censorship in the sense of government propaganda or anything. The word "censorship" in distributed consensus means preventing messages from propagating and often that is done by pretending you have not seen them.

The case you're talking about with tied stake is an edge case, which maybe is not handled super well in the binary consensus. It's handled better in the blockchain part because ties are broken more or less randomly, but in such a way that everyone knows who the winner of the tie is

 

cobordism:-Yesterday at 1:19 PM

I don't have to prevent messages from propagating, I just don't include them in my justifications (nor do I include any other messages that include them in their justifications and so on).

tell me more about that "more or less randomly" part 🙂

and I can always have tied stake in my messages if I control two validators. and whether I'm voting 0 or 1 or block x or block y makes little difference to me(edited)

 

MichaelBirch:-Yesterday at 1:20 PM

In Algorithm 1 on page 7 it says that in the case of tied scores when doing GHOST you pick the block with the lowest hash. Since crpyographic hash functions are used, the result of this is essentially random.

Ignoring messages prevents them from propagating in the sense that they are not influencing the result of the consensus in they way they ought to. Of course, this only matters in the case when the validator attempting the censor has enough weight to sway the consensus, even when others see and recognize the message.(edited)

 

cobordism:-Yesterday at 1:23 PM

pseudo random but importantly: deterministic. that's the key

MichaelBirch:-Yesterday at 1:24 PM

Yes, deterministic is important for sure. The outcome is a priori unpredictable though, which is what I mean by "random"

 

cobordism:-Yesterday at 1:28 PM

ok.
but by sacrificing my small validator with weight t, I can still cast contradicting messages of weight T even in the blockchain case. Is that correct?
And can't I use that setup to engineer a similar ping-pong of votes ?

as long as I only include messages from my validators on the justifications and order them in just the right way

 

MichaelBirch:-Yesterday at 1:31 PM

If you're the puppet master who controls all the stake (assuming T is some significant fraction of the total), then sure you can do whatever you want.

 

cobordism:-Yesterday at 1:31 PM

I meant the setup in my pastebin above

 

MichaelBirch:-Yesterday at 1:35 PM

Yes, I understand. What I am trying to say is that you can concoct all sorts of tricky things you might try and do, but in end what impact that has on the outcome depends on the context in which you are doing it. In a simplified analysis you could say that if you control the majority of the stake then you can achieve whatever you want, but if not then what happens depends on the details of the other participants

You could try simulating the sorts of situations you're interested in investigating

 

cobordism:-Yesterday at 1:35 PM

I am trying to understand the protocol.

 

MichaelBirch:-Yesterday at 1:36 PM

https://github.com/ethereum/cbc-casper/ is an open source code base for writing such simulations

It also has a wiki if you aren't finding the paper to be answering all your questions https://github.com/ethereum/cbc-casper/wiki

 

cobordism:-Yesterday at 1:36 PM

in particular I don't understand the idea that equivocation is detectable and I am trying to come up with a construct as an example in which weight T is effectively equivocating but only weight t is detectable.

where T is my total weight and t is arbitrarily small.

Well of course I will continue reading 🙂

 

MichaelBirch:-Yesterday at 1:38 PM

Your question is all about definitions. The definition of "equivocation" in the paper is a pair of messages from the same sender which do not justify each other. So in the situation you describe yes there is only t stake which is equivocated.

(Definition 2.6)

 

cobordism:-Yesterday at 1:40 PM

eexactly.
and yet I have two valid messages of weight T with different estimates that I can send to different people.

 

MichaelBirch:-Yesterday at 1:41 PM

And that's fine. The protocol will work out which of those competing proposals wins eventually

cobordism:-Yesterday at 1:42 PM

"eventually" -> liveness

 

MichaelBirch:-Yesterday at 1:43 PM

Yes. I am implicitly assuming that the details of the network allow for liveness to be proven

 

cobordism:-Yesterday at 1:43 PM

and I'm trying to confuse everyone with competing messages to prevent (or delay) that outcome 😀

 

MichaelBirch:-Yesterday at 1:44 PM

If the network is one in which alice and bob can communicate without going through you then you can't stop liveness

(if the amount of faulty weight resulting from your shinanary is less than the fault tolerances of alice and bob)(edited)

 

cobordism:-Yesterday at 1:47 PM

that's probably true. but if I can delay their messages even a little in order to front-run them with message of my own, then I might be able to prevent them from converging on a consensus.


I admit, what I am suggesting is a careful balancing act and may not be practical.

ah yes, but fault tolerance is defined only in the "equivocation" sense which I have already shown how to keep artificially small for the purposes of this exercise

 

MichaelBirch:-Yesterday at 1:49 PM

> I admit, what I am suggesting is a careful balancing act and may not be practical.

That's what simulations are all about! If you can write up a bit of code which successfully implements your strategy to delay consensus forever then I would love to see it

You can keep it arbitrarily small for a single instance of your attack. That doesn't translate into delaying consensus forever(edited)

If you repeat that move over and over then you will break fault tolarances

 

cobordism:-Yesterday at 1:56 PM

I remember having this discussion with Greg around (or shortly after) ethereum devcon 1. How to detect when someone is deliberately changing their votes in order to delay finality (we called it equivocating). Adding justifications to votes was an important step in that direction but the definition of equivocating in the doc now, does not cover all versions of that original idea.


Ok I admit that I am "burning" weight t and that - as long as there is a minimum staking weight - it could get very expensive and also go over the error threshold.

but I have not yet convinced myself that I have to spend more than t to change my vote multiple times in this manner during consensus forming on a specific block.

for subsequent blocks it'll cost another t. so every time I try to delay finality on a block, a little something gets slashed.

I'll keep working on it.

but I can't code a simulation. I'm not code literate.

 

MichaelBirch:-Yesterday at 2:01 PM

It's worth noting that you don't have a "vote" in CBC Casper at all. The value you propose has to be based on the estimator, i.e. E(b) = estimator(J(b)), otherwise the block is invalid. So the most you can do is try to prune your justification in order to get the result you want. But if you do that too much you could end up equivocating(edited)

 

cobordism:-Yesterday at 2:02 PM

you have a choice only in message zero

after that it's all about selecting the right justification

 

MichaelBirch:-Yesterday at 2:05 PM

Which you can't do arbitrarily because you may equivocate. And even making sure that you don't with your "main" identities, you still need to be selecting from messages which are sent by other parties. So again whether the plan works or not depends on the context in which you try it

 

cobordism:-Yesterday at 2:05 PM

you don't have to select messages from other parties

I specifically do not

only my own

always

in this game at least.

🙂

My two main identities will keep referring to each other's previous message as the justification to change their vote/estimate and the little t ambiguity is enough to set this ping pong in motion

 

MichaelBirch:-Yesterday at 2:08 PM

So then alice and bob look at each other and go "gee I guess our messages aren't getting through" and remove your identities from the protocol (if this is happening in a partially synchronous network where they can know after some time that you must have gotten a message).

cobordism:-Yesterday at 2:09 PM

but why are their messages not getting through? Is someone censoring them and I am innocently confused? It's not a slashable offence.

but yes. that's the kind of extra reasoning we might have to introduce

 

MichaelBirch:-Yesterday at 2:12 PM

It is a slashable offence to have failed to have received messages within the bound specified by a partially synchronous network. It doesn't matter whether you are at fault or not because regardless of the reason you are not participating properly

 

cobordism:-Yesterday at 2:13 PM

I ddos you and you get slashed??

ouch

 

iteratee:-Yesterday at 2:14 PM

Set up DDos protection.

Anyone running a plain vanilla service loses money if it's down.

 

cobordism:-Yesterday at 2:16 PM

How do you prove that someone didn't receive a message? ... how do you prove it was ever sent to them at all?

 

MichaelBirch:-Yesterday at 2:17 PM

That's precisely what justifications are for.

 

cobordism:-Yesterday at 2:17 PM

I disagree

 

MichaelBirch:-Yesterday at 2:17 PM

I know my message was sent because I sent it. And I know if it was received because it would have appeared in a justification

cobordism:-Yesterday at 2:17 PM

justifications are there so that you cannot disavow messages later if you rely on them now.

you know. but does a smart contract know?

if you want to slash someone your proof had better be better than just your word

 

MichaelBirch:-Yesterday at 2:18 PM

It can if you write it to know (edited)

 

iteratee:-Yesterday at 2:19 PM

People will accept your proof because they received the message you're claiming a peer didn't respond to.

So they've seen it.

 

cobordism:-Yesterday at 2:19 PM

You can't prove that you sent it to me if I don't give you a receipt.

 

iteratee:-Yesterday at 2:19 PM

I can prove I sent it out.

Because others have copies.

And they also forwarded them to the non-responding peer.

 

MichaelBirch:-Yesterday at 2:20 PM

> You can't prove that you sent it to me if I don't give you a receipt.

That's an implementation detail. You can definitely assume that in any reasonable system the entity sending a message knows that it was sent

 

cobordism:-Yesterday at 2:20 PM

I can also send messages between my multiple identities and then later blame you for not receiving them. It doesn't work. And all my multiple identities agree.

you might know what you sent, but an outsider cannot tell which one of us is lying

 

iteratee:-Yesterday at 2:21 PM

That only works if your multiple identities have a majority stake.

And if they do, game over.

 

cobordism:-Yesterday at 2:21 PM

where do majorities come into it?

we never talked about majorities here

 

iteratee:-Yesterday at 2:21 PM

You need a majority to concur a slashing.

 

cobordism:-Yesterday at 2:21 PM

you said you can prove that you sent something. I say you can't.

 

iteratee:-Yesterday at 2:21 PM

Or it didn't happen.

 

MichaelBirch:-Yesterday at 2:22 PM

You need to come to consensus on slashing -- it doesn't just happen when one validator claims someone committed an offence.

 

cobordism:-Yesterday at 2:22 PM

ok now proving has turned into "convincing a majority".
that's not the same

 

iteratee:-Yesterday at 2:22 PM

That's all you ever get in blockchain.

 

cobordism:-Yesterday at 2:22 PM

Equivocation is provable to a smart contract.

non-receipt of messages sent is not(edited)

clearly these are very different things in terms of proof

 

iteratee:-Yesterday at 2:23 PM

Yes, the proof of equivocation is not the same.

Equivication has a higher cost. You lose the whole stake for one offence.

 


ReplyQuote
Germany
(@germany)
Active Member
Joined:3 months  ago
Posts: 6
05/06/2018 6:13 am  

Hey kelly. 

Not sure if you’re still confused or interested in correct-by construction, but i have worked on a blog post going over what it is and how’s it’s being used in RChain. Hope you find it useful. 

 

https://docs.google.com/document/d/1LtA8_oSbAeHtcLnUSuR6Wr-sfBAifIS-eNrs1jzuulU


ReplyQuote
  
Working

Please Login or Register