Submitted: 21 October 2021
Rejected: 13 January 2022
Review 1: -1 Reject
Review 2: 1 Accept
Review 3: 2 Definitely accept
Accept
The paper presents WebBFT; a peer-to-peer consensus protocol designed explicitly for decentralized community-driven applications. In contrast to other BFT protocols, WebBFT is well-suited to web applications because (1) it does not require heavy h/w infrastructure and (2) it does not require all replicas/browsers to interconnect. The paper compared WebBFT's performance against Smart-BFT and showed that it achieves good performance in the presence of Byzantine environments, e.g., failures. Reviewers agree that the proposed idea/techniques advance state of art. The reviewers do have comments and feedback for the authors to address to improve the paper
------------------------------ Additional appendix added by track chairs
------------------------------
Although this paper was judged of high quality by our reviewers and meta
reviewer, we had to take the difficult decision to reject it. The main
reason is the lack of room to accommodate all submitted papers to the
track. We apologize for this disappointing news, the decision has not
been taken lightheartedly.
-1 (Reject)
This paper presents an optimistic state-based BFT algorithm, and the browser-based implementation WebBFT. This paper then evaluates WebBFT via a simple loyalty points application and compare WebBFT with Tendermint and BFT-SMaRt. The optimistic state-based BFT algorithm maintains atomic resigters with CRDT and organize these atomic resigters with a merkle tree. The BFT consensus is achieved through a 3PC-like protocal based on votes without a leader. WebBFT is implementated in browser and optimized with some engineering efforts.
-1 (Limited: Rather straightforward ideas without much creativity.)
-1 (Limited: The work may be of marginal interest in a narrow research community.)
-1 (Poor: Potentially reasonable approach, but certain core claims lack justification.)
-1 (Inadequate: Literature review misses many important past papers.)
-1 (Sub-standard: Heavy rewriting is required to make the paper more readable.)
Engieering details for the implementation of WebBFT are clear.
1 (In scope)
No ethical concerns.
4 ((high))
1 (Accept)
The paper presents WebBFT, a peer-to-peer consensus protocol specifically design for decentralized community-driven applications (e.g., web applications). In contrast to other BFT protocols, WebBFT is well-suited to web applications because (1) it does not require heavy h/w infrastructure and (2) does not require all replicas/browsers to be connected to each other. WebBFT is evaluated against Smart-BFT. The evaluation shows that WebBFT achieves good performance in the presence of Byzantine environments, e.g, failures.
1 (Creative: An original research question and/or approach that distringuishes the work from the state of the art.)
1 (Broad: Could help ongoing research in a broader research community.)
1 (Good: Generally solid work, and any claims that might need adjustment are unlikely to impact the central contributions of the paper.)
0 (Reasonable: Coverage of past work is acceptable, but a few papers are missing.)
0 (Reasonable: Understandable to a large extent, but parts of the paper need more work.)
The paper tries to strengthen the properties of existing replication protocols used to web applications to further consider Byzantine settings. This research problem sounds very interesting and promising.
1 (In scope)
No ethical concerns.
3 ((medium))
2 (Definitely accept)
The paper describes WebBFT, a distributed in-browser consensus-finding library with a fixed set of participants. The paper shows how consensus is reached wrt the content of a register, in the face of the usual up to (n-1)/3 byzantine participants. The paper discusses the algorithm, implementation and optimization issues, and related work.
--- Update after rebuttal ---
This reviewer thanks the authors for their detailed rebuttal, and hopes
they could convince the other reviewers to reconsider their review. I
agree of course that a formal model of the algorithm is out of scope for
the present publication, but can say from personal experience that,
e.g., TLA+ can find surprising corner cases; its use will certainly
raise confidence both in the algorithm and in optimizations thereof.
2 (Excellent: Only a few people in our community would have come up with these ideas.)
2 (Excellent potential to bring new ideas and/or open up new research directions.)
2 (Excellent: The approach is well-justified and all the claims are convincingly supported.)
1 (Comprehensive: Cannot think of any important paper that is missed.)
1 (Lucid: Very well written in every aspect, a pleasure to read, easy to follow.)
This is a very good paper. Both the algorithm and implementation sections go into reassuring levels of detail. The related work mentions all similar systems this reviewer was aware of, as well as several others. In order not to break anonymity, the reviewer has not tried to locate and test the implementation, but might do so after the review period is over.
Very minor points:
1 (In scope)
none
4 ((high))
Reviewer#1 asks how the protocol guarantees liveness.
What is not explicitly shown in algorithm 2 is that all votes are
gossiped between the replicas, so `votes[0]` is in fact updated when new
votes are received. What is also important is that a replica will not
only gossip `votes[i]` in a certain round, but also all votes for the
previous rounds. This means that when two replicas disagree with each
other in a certain round, once they communicate with each other, they
will learn each other’s state and in the next round they will both vote
for the same value (as their views on `votes[0]` will be the same).
Malicious replicas can try to shift the balance to violate liveness, but
with each round they have less possibility to do so, because when they
gossip `votes[i]` they also gossip the previous rounds which should show
why they voted on a certain value.
Reviewer#1 questions the difference with 3PC.
3PC is used in trusted settings and only deals with crash-fault
tolerance, while WebBFT tolerates malicious clients. 3PC consists of
three phases where the leader communicates directly with all replicas.
PBFT extends this and all replicas communicate directly with all other
replicas in the last two phases. WebBFT does not use a leader and
replicas communicate only to a subset of the other replicas using a
gossip-like protocol. There is not a fixed number of three communication
rounds to reach consensus in WebBFT. Instead, the PRE-COMMIT phase can
consist of multiple rounds in which the replicas communicate with each
other until one unique proposal is chosen.
Reviewer#1 questions our motivation and asks whether BFT-SMaRt is
superior to WebBFT.
We mention several motivating use-cases in the introduction and describe
our loyalty points use-case in more detail in section 4. Our evaluation
shows the trade-offs that WebBFT makes. In an optimal scenario where
there is a good connection available between all replicas and no network
disruptions or crashes happen, then a classical leader-based protocol
such as BFT-SMaRt will outperform WebBFT. However, as we mention in the
introduction, we envision a more ad-hoc network between low-end devices
on a residential or even a mobile network, where short-term disruptions
are common. Our evaluation shows that WebBFT is very robust against this
kind of setting and achieves similar performance as in the optimal
scenario. A leader-based protocol such as BFT-SMaRt is not well suited,
the temporary failure of a leader leads to long commit times, and even
total failure for larger network sizes. This leader also needs more
resources and a direct connection to every other replica. Keeping 100
WebRTC connections open in a browser, while theoretically possible,
drastically reduces performance.
Reviewer#1 mentions minor issues concerning missing related work,
formatting issues and typos.
We will certainly fix these in the camera ready if the reviewer points
these out in his next iteration of the review.
Reviewer#2 asks abouts real world examples and the impact of Byzantine
faults.
In the paper we mention small, local merchants who can use the WebBFT
framework to integrate their loyalty systems with each other so
customers can spend their loyalty points in any of the participating
stores. This is very similar to the ‘miles’ system of big airlines and
hotel chains, except that the focus here is on smaller networks, where
the participants don’t have the knowledge or money for a large
infrastructure setup. With the WebBFT framework, the merchants only need
a low-end device and a web browser to get started. Examples of Byzantine
faults are customers who try to double-spend their loyalty points at
multiple stores, or merchants who would try to favor friends and family
members by “printing” loyalty points out of thin air.
Reviewer#2 asks whether all registers are placed in a single
Merkle-tree.
Yes, all registers are placed in a single Merkle-tree, this way the
gossiping protocol only has to exchange the root hash to know whether
updates need to be sent between two replicas. The Merkle-tree we used
has a fixed depth and the location of a register in the tree is also
fixed based on their unique id. This solves the problem with updates, as
only the direct path to the root hash must be updated, no other
rebalancing is necessary. This might lead to an unbalanced tree, but in
practice ids are generated randomly, so this does not become a problem.
Reviewer#3 asks whether the algorithm is model checked.
That is certainly an interesting next trajectory in our research, but at
the moment, we did not use any model-checking software or mechanically
verify the proof. We think that requires a dedicated and different kind
of paper that even might require a research visit. As systems and
infrastructure researchers we focused on performance, scalability and
robustness as well as the implementation support in a usable middleware.