RFC: Ledger hash PoS seeding

[Eitu33]

RFC: Ledger hash PoS seeding

Introduction

We have currently no way to reliably ensure that the local ledgers of two nodes are exaclty the same. This makes the massa node unable to attest for the validity of a given ledger state.

This might give rise to nodes having very slight differences in their respective ledgers.

This proposol consists of saving the local ledger hash in the proof-of-stake module and use it as addtional seeding information when drawing selections.

Computing the ledger hash

Initial computation

The XOR function will be represented as ⊕

The hash function will be represented as h

h(len(key_0) + key_0 + value_0) ⊕ h(len(key_1) + key_1 + value_1) ⊕ ... ⊕ h(len(key_n) + key_n + value_n) = ledger_hash

The ledger hash corresponds to the XOR of every entry hash. An entry is the concatenation of a key and its corresponding data.

Changes computation

Add & Delete:

ledger_hash ⊕ h(len(given_key) + given_key + given_value)

Because of XOR commutative and associative properties the computation is the same for add and delete operations.

Entry update:

ledger_hash ⊕ h(len(previous_given_key) + previous_given_key + previous_given_value)
ledger_hash ⊕ h(len(updated_given_key) + updated_given_key + updated_given_value)

To make a ledger hash entry update we remove the hash of the previous value and add the hash of the updated entry.

Note that both of these computations are only executed after a final ledger change.

Using the ledger hash for PoS seeding

As it was describe above, the ledger hash is updated on every final slot. A snapshot of its state is also saved at the last slot of every cycle.

To ensure that every node has the exact same ledger state, the ledger hash snapshot will be involved in the selection drawing process.

Current behaviour is: Draws at cycle C are generated using the seed from cycle C-2, and the roll distribution from cycle C-3.

Proposed behaviour is: Draws at cycle C are generated using the seed from cycle C-2 concatenated with the ledger hash from cycle C-3, and the roll distribution from cycle C-3.

Possible follow-ups to discuss

Parrallel computing of the initial ledger hash when bootstrapping with an existing disk ledger.

Saving the ledger hash as disk ledger metadata.

[damip]

Amazing, only a small comment: for the hash of a ledger entry, use h(len(key_1) + key_1 + value_1) to avoid two different entries (key = "AAA" value = "A" and key="AA" value = "AA") to get the same hash

[damip]

Maybe it's worth adding the ledger hash to the metadata (alongside the slot)
Note that the hash of the slot can also be XORed with the general hash to also anchor everything in time and also allow checking the integrity of the slot when loading

[Eitu33]

Maybe it's worth adding the ledger hash to the metadata (alongside the slot)

Yeah I think it's a good idea.

Note that the hash of the slot can also be XORed with the general hash to also anchor everything in time and also allow checking the integrity of the slot when loading

Agree with this as well.

Also I was thinking that having the hash and slot saved as disk ledger metadata can allow us to bootstrap with an existing ledger faster. The server node could take its ledger hash and remove the recent changes up to the client node slot, and match it against the client node ledger hash.

[damip]

Not sure how we can undo recent changes, but for sure it can help for quick integrity checking because changes can be ADDED to check for the obtained hash

[Eitu33]

Ah yes it is easier to do it this way indeed 😄