# Validation of Merkle branch for a root

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?

• 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. – kelalaka Sep 21 '18 at 9:37
• But still more information is needed to verify the hash. – Strernd Sep 21 '18 at 10:34
• 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$. – kelalaka Sep 21 '18 at 10:50
• 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. – Strernd Sep 21 '18 at 11:20
• At first, it was not for me,too. – kelalaka Sep 21 '18 at 11:23