Submitted: 21 October 2021
Rejected: 13 January 2022
Review 1: -1 Reject
Review 2: 1 Accept
Review 3: 2 Definitely 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.
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.
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.
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)
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` 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` 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
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
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.