Bitwise LMD GHOST

Resources

Medium by Aditya

Validity Check of BitwiseGHOST

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

Binary search in$ agreeing[\rbrackfor maximum height h where at least half of the validators agree.

Verify that $ 2 * agreeing[h+1\rbrack ≥ (agreeing[h\rbrack-at[h\rbrack)

Repeat for maximum height where at least a quarter of the validators agree, and verify the inequality. Next, repeat for maximum height where at least 1/8 of the validators agree, and so on. Continue until you reach the head.

Proof of correctness

Necessity is obvious.

Prove sufficiency 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”

$ |V| / 2^{n + 1} < agreeing \lbrack h \rbrack < |V| / 2^n = x

$ 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 ①

With slacking for validator rotation

QUOTIENT = q

Assume towards contradiction

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

Let$ xbe the “current set of validators”

$ agreeing \lbrack h \rbrack < x

From ①,

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

This contradicts to ①

(Without this proof, it is clear since the validity check with slacking is weaker than the normal validity check)

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

nrryuya.icon > Hash of what?

yudetamago.icon >

Basically it is just a "bits". About actual blocks, it represents something like a hash of block header.

Lighthouse uses the hash of block-id (for actual block) : https://gitter.im/sigp/lighthouse?at=5c7474584d8904118cea2ec7

Height in the Bitwise-Tree

Virtual 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

h: the depth of the block

LMD GHOST in the Bitwise-Tree

Mappings

last virtual agreement height

agrees_to[]: Validator -> Virtual height

last virtual agreement height for each validator

the virtual height up to which the block that v's latest attestation pointed to agrees with the current chain

last_agreeing[]: Virtual height -> Weight

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

agreeing[]: Virtual height -> Weight

sum of the weights of the validators v where agrees_to[v] > h

last virtual at height

last_at[]: Validator -> Virtual height

last virtual at height for each validator

at[]: Virtual height -> Weight

how many validators’ latest messages signed exactly some block hash(?).

Updates

last_agreeing[]

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

last_agreeing[agrees_to_perv[v]] - weight[v]

last_agreeing[agrees_to_new[v]] + weight[v]

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

at[]

For each validator v, check if last_at[v] is equal to it’s last virtual agreement height.

If yes, then add the weight of the validator to at[last_at[v]].

This process will take $ O(V)

Queries

agreeing[]

agreeing[x] = last_agreeing[x] + … + last_agreeing[h]

Ref

segment tree

プログラミングコンテストでのデータ構造 by Takuya Akiba