Bitwise LMD GHOST

verify the validity of block C3

https://gyazo.com/0e1646f8d18772519994b15d0932d53c

$ agreeing \lbrack h \rbrack: stores the number of votes consistent with block C3 upto height h in C3’s branch.

$ at \lbrack h \rbrack stores the number of votes that support exactly the block at height h in C3’s branch

Validity Check

WIP

proof of correctness

Proof by contradiction. Assume there exists$ h, s.t.

$ agreeing \lbrack h + 1 \rbrack < (agreeing \lbrack h \rbrack - at \lbrack h \rbrack) * 1/2 - ①

Let$ xbe the “current set of validators”

$ agreeing \lbrack h \rbrack < x

From ①,

$ agreeing \lbrack h + 1 \rbrack < agreeing \lbrack h \rbrack * 1/2 < x/2

Therefore,$ his the largest height such that at least$ x/2agrees

This contradicts to ①

Bitwise-Tree

https://gyazo.com/5aa3aeb34a8104be150d9c97381d7fe1

mark all the children in original tree as descendants of B in the virtual tree

create virtual children

V0: have hash with prefix 0

V1: have hash with prefix 1

V0x: have hash with prefix 0x

V1x: have hash with prefix 1x

...

if the hash reaches a certain block in the original block, then replace that with the actual block

Height in the Bitwise-Tree

height: 256 * original_height

yudetamago.icon > 256 is hash length

virtual agreement height: the height up to which the block that their latest attestation pointed to agrees with the current chain

256 * actual_shared_height + number_of_common_bits

actual_shared_height: actual shared height in the original block tree

number_of_common_bits: initial common bits between

LMD GHOST in the Bitwise-Tree

agrees_to[]

last virtual agreement height for each validator

last_at[]

last virtual at height for each validator

last_agreeing[]

mapping of virtual height to number of validators having that height as last agreement height

update last_agreeing[] from it’s previous block when a new block is received

h

The range of last_agreeing[], which is the depth of the block

segment tree

https://www.slideshare.net/iwiwi/ss-3578491 (Japanese)