1
$\begingroup$

If I understand correctly, the term "consensus" in distributed consensus algorithms means that all the participants ("peers") achieve a common understanding of some data value. Different algorithms can handle different types of failures or misbehavior by some of the peers, network disconnections or partitions, lost messages, and so on. For example, PBFT has the property that any small group of peers (less than a third) cannot prevent the remaining peers from achieving a common understanding of the data value.

BUT there is nothing in these algorithms that prevents any peer from setting the data to a value that they shouldn't set it to. So "consensus" just means we all agree that the value has been set to X. It does not mean we all agree that X is the correct value.

Is that right? And, if so, is there some general research into how to enforce a set of application-specific rules about who is allowed to set the data to a given value?

For example, Bitcoin has a set of rules that ensure that only "valid" transactions are accepted by the network. So, for example, Joe can't give Fred the same bitcoin that he's already given to Mary. Joe can't give Fred a bitcoin unless someone else already gave Joe that bitcoin, or Joe earned that bitcoin by mining. And so on...

So what we have in Bitcoin are a set of application-layer rules that make sense for money, and these rules are embedded in the distributed consensus protocol used by Bitcoin (i.e. blockchain and proof-of-work and the bitcoin reference implementation).

However, what if I have a different set of rules that make sense in MY application - how can I ensure that a distributed consensus protocol (e.g. PBFT) not only ensures consensus across all peers about what the data value is, handling various failures and misbehavior by peers, and ALSO ensures that only "legal" values are set by the peers.

For example, I might have rules like: The value can only increase - nobody is allowed to decrease it. Except on Sundays, when it can be decreased, but must only be set to an even value. Except peer P can set it to whatever value they want to. And if the value=5, then peer Q is the only one who can change it. And so on... (Believe me, I have a real-world problem that requires this kind of complexity.)

Ideally, the rules would be expressed in a formal language, and the distributed consensus protocol would reject any attempts by any peers to change the data value in a way that does not conform to the rules.

Could I do this by implementing PBFT and adding in a check where each peer checks that a proposed new value is consistent with the rules, and then refusing to accept (possibly broadcasting a NACK) if the proposed change is not valid?

I'm wondering if this has already been studied. Perhaps this is the same as the concept of "consistency" in a distributed database, but I don't want to use a database replication solution, because I want eventual consistency, not strong consistency, and I want the kind of fault-tolerance that PBFT provides.

Thanks!

Duncan

$\endgroup$

1 Answer 1

1
$\begingroup$

You've asked multiple questions here. I'll answer the first one.

Typically consensus means that all the honest participants have the same view of the state of the system. There's not necessarily a guarantee that this state is "correct" in any sense (some protocols might also provide that guarantee, but it is in some sense a separate or additional request).

Often there are some rules about what kinds of state changes are "valid" or "allowed", and the honest participants are also tasked with ensuring that every state transition is valid; they won't generate or request transitions that aren't valid, and they won't accept transitions from others that are invalid. If you do this right then you get the additional guarantee that all the honest participants have the same view of the state of the system, and this state is valid.

There are multiple ways to define which states or transitions are valid. One way is by defining a state machine (like a DFA) that represents which state changes are valid; then the protocol provides a distributed implementation of the state machine.

I'm not an expert, but if you want to get a more authoritative answer, you could read the literature about state machine replication. It's probably worth reading the PBFT paper, which is presented as an instance of state machine replication.

$\endgroup$
3
  • $\begingroup$ Thanks for your answer. It's somewhat useful, but I'm hoping for a solution using a well-known algorithm (e.g. PBFT), that can also ensure "Correctness". Are you saying that I will get this if I just have peers reject changes that are not "correct" (even if the rules of the PBFT algorithm say they should accept the change? I don't want to start from scratch and solve both distributed consensus and "correctness" enforcement by defining and implementing a state machine. That sounds hard. I was hoping that this was a well-studied problem and someone could just point me to the solution. $\endgroup$
    – Duncan
    Feb 1, 2018 at 20:23
  • $\begingroup$ @Duncan, unfortunately my knowledge on the subject is limited, so I can't speak with 100% confidence. But my understanding is, yes, you do exactly that. You do two things. 1. You define the protocol so that honest participants will never send a message with a proposal to follow an illegal transition. 2. When you receive a message, you first check whether it proposes an illegal transition. If it does, you discard the message (you know it didn't come from an honest participant; so the best you can do is ignore it). $\endgroup$
    – D.W.
    Feb 1, 2018 at 21:01
  • $\begingroup$ Thanks @D.W. I'm now well down the path of implementing this, building on Tendermint, and your answer is exactly right, and I marked it as such. $\endgroup$
    – Duncan
    Feb 22, 2019 at 1:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.