Improvements to conference paper

[sbellem]

From @sbellem on August 23, 2017 22:44

The purpose of this issue is to communicate small improvements (such as typos) to the research paper by Miller et al. The Honey Badger of BFT Protocols.

Copied from original issue: amiller/HoneyBadgerBFT#31

[sbellem]

small typos

4.4 Instantiating ACS Efficiently

(page 7, last paragraph before subsubsection Communication-optimal reliable broadcast)

We now briefly explain the RBC and ABA constructions before explaing the Ben-Or protocol in more detail.

"explaing" --> "explaining"

Communication-optimal reliable broadcast

(page 7, last paragraph of subsubsection Communication-optimal reliable broadcast)

If the sender is correct, the total running time is three (asynchronous) rounds; and in any case, at most two rounds elapse between when the first correct node outputs a value and the last outputs a value. The reliable broadcast algorithm shown in Figure 2.

"is" seems to be missing

The reliable broadcast algorithm is shown in Figure 2.

[sbellem]

wondering ...

1.1 Our Contributions

Timing assumptions considered harmful.

[...]

on page 2, first paragraph

Second, even when the weak synchrony assumptions are satisfied in practice, weakly synchronous protocols degrade significantly in throughput when the underlying network is unpredictable. Ideally, we would like a protocol whose throughput closely tracks the network’s performance even under rapidly changing network conditions. Unfortunately, weakly asynchronous protocols require timeout parameters that are finicky to tune, especially in cryptocurrency application settings; and when the chosen timeout values are either too long or too short, throughput can be hampered. As a concrete example, we show that even when the weak synchrony assumptions are satisfied, such protocols are slow to recover from transient network partitions (Section 3).

"weakly asynchronous" --> "weakly synchronous" (?)

[sbellem]

wondering ...

C. ASYNCHRONOUS BINARY BYZANTINE AGREEMENT

Realizing binary agreement from a common coin.

[...]
We instantiate this primitive with a protocol based on cryptographic common coin, which essentially act as synchronizing gadgets.

"on cryptographic common coin" --> "on cryptographic common coins" (?)

[sbellem]

7. Reference

ref [42]:

A. Mostefaoui, H. Moumen, and M. Raynal. Signature-free asynchronous byzantine consensus with t< n/3 and o (n 2) messages. In Proceedings of the 2014 ACM symposium on Principles of distributed computing, pages 2–9. ACM, 2014.

o (n 2) --> O (n^2)

[sbellem]

3. THE GAP BETWEEN ASYNCHRONOUS AND WEAKLY SYNCHRONOUS NETWORK MODELS

In this section, we present make two counter arguments that refute the premise above.

present or make ?

[sbellem]

page 2, left column, bottom

We provide a full-fledged implementation of HoneyBadgerBFT, which will we release as free open source software in the near future.

will we --> we will

[sbellem]

DEFERRED PROOFS

[...]

Experiment 1. [...] The adversary selects N - 2f correct nodes and let S denote the union of their proposed transactions -- recall that the ACS protocol guarantees that the agreed set contains at least transactions proposed by N - 2f correct nodes.

contains at least transactions --> contains at least B/4 transactions (?)

Experiment 2. [...]
[...]
[...] If the average number of transactions across these epochs is smaller than 1/4 * B, D guesses that the ciphertexts are real; otherwise it guess they are random.

guess --> guesses (?)

[sbellem]

Applicability to permissionless blockchains.
[...]
Several recent works have suggested the promising idea of leveraging either a slower, external blockchain such as Bitcoin or economic “proof-of-stake” assumptions involving the underlying currency itself [32, 32, 35, 37] to bootstrap faster BFT protocols, by selecting a random committee to perform BFT in every different epoch.

[32, 32, 35, 37] --> [32, 35, 37] ?

[sbellem]

5.1 Bandwidth Breakdown and Evaluation

...
Bandwidth and breakdown findings. ...
...
The system’s effective throughput ... However, when when the batch size reaches 16384, ...

when when --> when

[amiller]

Besides all the above we need to add the improvements from #12 and an explanation of what went wrong

• address issue Reproduce attack and implement fix for liveness issue with ABA/commoncoin #12

[yang-sec]

Dear authors, I have two technical questions after reading the conference paper. Could you help me resolve them?

1. It seems the handling (or "validation", in the application perspective) of transactions is not specified in the paper. For instance, if we deploy HB-BFT for a consortium blockchain, where do we put the validation part? My initial thought was adding validation as a predicate to the BA instances, since by do so the ACS output can be used for block packaging directly.
2. IMHO, the "censorship resistance" property achieved by TPKE is a reduced form of the strong censorship resistance property, or the "liveness"/"fairness" concept. In HB-BFT, nodes has one-to-one correspondence with the randomly sampled tx sets. The adversarial schedulor can still do "blind censoring" by focusing on attacking nodes only. Meanwhile, strong censorship resistance would achieve unanimous acceptance on all valid input txs.
   Thx and really appreciate your feedback!

[amiller]

Nice questions Yang, thanks!

1. "Validation" is left to the application layer, you can think of this as agreeing on inclusion only. This is because the decision of which transactions to include must be made before the entire set of transactions is revealed. In order to prevent spam of invalid transactions, something I'm imagining is that each node checks that the transaction has at least enough balance as of the last block to pay for a worst-case scenario, which is that there are "n" double-spend transactions in the same block (one of them would be valid, the rest would be rejected as garbage, but it would be filling up space regardless). There is some discussion here: Compensate for conflicting transactions? amiller/HoneyBadgerBFT#16 (not sure why it does not show up as an issue in this repo, but same idea)
2. Even if an adversary does blind censoring in block, the transaction can still be included in a later block. This is how the analysis works in the paper, the transaction is guaranteed to be included eventually (with high probability in some k number of blocks) because each time a random node proposes it.

[yang-sec]

Thanks for the answer Andrew! I'm getting a clear picture now. Yes the validation part is much owed to the application layer, depending on how the account/transaction/balance data structures are designed.