TheWebConf '22 Paper #2054 Reviews and Comments

Paper #2054 WebBFT: a Client-centric Web-based BFT Platform for Decentralized and Resilient Community Web-Apps

Submitted: 21 October 2021
Rejected: 13 January 2022

Review 1: -1 Reject
Review 2: 1 Accept
Review 3: 2 Definitely accept

Metareview

Recommendation

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.

Review 1

Overall evaluation

-1 (Reject)

Summary

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.

Originality

-1 (Limited: Rather straightforward ideas without much creativity.)

Impact

-1 (Limited: The work may be of marginal interest in a narrow research community.)

Technical quality

-1 (Poor: Potentially reasonable approach, but certain core claims lack justification.)

Related work quality

-1 (Inadequate: Literature review misses many important past papers.)

Presentation quality

-1 (Sub-standard: Heavy rewriting is required to make the paper more readable.)

Strengths

Engieering details for the implementation of WebBFT are clear. Figures are well drawn.

Weaknesses

  1. It is not clear how the consensus protocal guarantees liveness. The paper claims in section 2.1 that "the set of possible values to vote on gets **smaller** with every round, and eventually the view of all the replicas on the votes in round 0 will become the **same**, and the winning value can be chosen unanimously." and claims in appendix A.2 "the currently known votes will all be the **same**". However, the protocal limits honest replicas can only vote to the winner value of round 0 but `votes[0]` on each replica is never updated according to Algorithm 2. It is not clear how replicas agree on the same value. Furthermore, it is not clear whether the protocal can work with multiple parallel proposers in round 0.
  2. The basic protocal is still based on 3PC with limited innovation.
  3. The motivation is not clear nor convincing enough. Evaluation does not consider resource comsumption such as CPU and memory, and the results about network bandwidth show that BFT-SMaRt beats WebBFT at all scales. This paper does not develop a more practical application to solve problems in web 3.0 scenarios.
  4. As a research paper about consensus protocal, this paper uses too many pages to illustrate engineering details and list related works that are not closely related to it. This paper focuses on explain what the protocal and the browser-based implementation look like with limited insights and fails to show clearly what the real problem is, why existing solutions are not suitable, and how the proposed method solves the problem with better performance than state-of-the-art.
  5. There are typos and formatting issues in this paper.

Relevance to the Web Conference

1 (In scope)

Ethics

No ethical concerns.

Reviewer's confidence

4 ((high))

Review 2

Overall evaluation

1 (Accept)

Summary

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.

Originality

1 (Creative: An original research question and/or approach that distringuishes the work from the state of the art.)

Impact

1 (Broad: Could help ongoing research in a broader research community.)

Technical quality

1 (Good: Generally solid work, and any claims that might need adjustment are unlikely to impact the central contributions of the paper.)

Related work quality

0 (Reasonable: Coverage of past work is acceptable, but a few papers are missing.)

Presentation quality

0 (Reasonable: Understandable to a large extent, but parts of the paper need more work.)

Strengths

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.

Weaknesses

  1. A real-world example of why WebBFT is needed might be a good addition to the paper. For example, what in the context of web-applications a Byz fault could be? what would be the implications?
  2. Section 2.2 is hard to follow and understand. For example, Figure 1 is not described in detail. Additionally, there are some references to Algorithms' lines that do not specify which of the two Algorithms they refer to. A light re-structuring of the paper might make reading better. For example, 1. high-level description of the protocol (workflow), 2. example description and 3. detailed description with reference to those two Algorithms (a line-by-line discussion might also be helpful).
  3. Section 3 shows the architecture of WebBFT but it might be better if 3.1 was discussed and placed before 2.2.
  4. Details and a workflow of the protocol could be added.
  5. Question: Are all atomic-registers from all browsers placed into a single merkle-tree? Merkle-trees do not scale well with updates/insertions, could we use hashing and more merkle trees to increase parallelism?

Relevance to the Web Conference

1 (In scope)

Ethics

No ethical concerns.

Reviewer's confidence

3 ((medium))

Review 3

Overall evaluation

2 (Definitely accept)

Summary

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.

Originality

2 (Excellent: Only a few people in our community would have come up with these ideas.)

Impact

2 (Excellent potential to bring new ideas and/or open up new research directions.)

Technical quality

2 (Excellent: The approach is well-justified and all the claims are convincingly supported.)

Related work quality

1 (Comprehensive: Cannot think of any important paper that is missed.)

Presentation quality

1 (Lucid: Very well written in every aspect, a pleasure to read, easy to follow.)

Strengths

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.

Weaknesses

Very minor points:

Relevance to the Web Conference

1 (In scope)

Ethics

none

Reviewer's confidence

4 ((high))

Rebuttal

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.