In the paper of the Honey Badger BFT link, which is a BFT algorithm, that makes use of cryptography, there is described an algorithm for a reliable broadcast with erasure codes. Following part of the algorithm is relevant for this question:

upon input(v) (if Pi = PSender):
  let {sj}j∈[N] be the blocks of an (N −2 f, N)-erasure coding scheme applied to v
  let h be a Merkle tree root computed over {sj}
  send VAL(h,bj,sj) to each party Pj, where bj is the j-th Merkle tree branch

upon receiving VAL(h,bi,si) from PSender,
  multicast ECHO(h,bi,si)

upon receiving ECHO(h,bj,sj) from party Pj,
  check that bj is a valid Merkle branch for root h and leaf sj, and otherwise, discard

The formulation "check that bj is a valid Merkle branch for root h and leaf sj" opens the question of how I can verify that. How is the tree supposed to look? Is it a binary Merkle Tree? If yes, what is the j-th branch then? Is it a tree of depth 1, so that every block is a branch of the root?

For an example of 10 (1,...,10) parties, me being party 5 and the sender being 1: I received VAL(h,b5,s5) and then for example ECHO(h,b10,s10), how can I verify with just having h, b5, b10, s5 and s10, that b10 is a valid Merkle branch?

  • $\begingroup$ They use Cachin et al.'s idea , where they assume the tree is complete binary tree. J-th branch then is the J-th element? This is not clear. See page 12 at cs.ucsb.edu/~tessaro/papers/dds.pdf. NoteL to verification a finger print is defined. $\endgroup$
    – kelalaka
    Sep 21, 2018 at 9:37
  • $\begingroup$ But still more information is needed to verify the hash. $\endgroup$ Sep 21, 2018 at 10:34
  • $\begingroup$ The fingerprint contains the siblings on the path to the root from the $i-th$ leaf. So you can, as usual in Merkle trees, Go up by using the hashes and $v_l$, the sibling of $i-th$. $\endgroup$
    – kelalaka
    Sep 21, 2018 at 10:50
  • $\begingroup$ So every message sent, needs to have the hashes of the siblings on the path? That's what I thought, but it isn't quiet clear form the description of the algorithm in the paper. $\endgroup$ Sep 21, 2018 at 11:20
  • $\begingroup$ At first, it was not for me,too. $\endgroup$
    – kelalaka
    Sep 21, 2018 at 11:23


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.