Checkpoint

Checkpoints are the most crucial part of the Polygon network. It represents snapshots of the Bor chain state and is supposed to be attested by ⅔+ of the validator set before it is validated and submitted on the contracts deployed on Ethereum.

Types

Checkpoint structure on Heimdall state looks like following:

type CheckpointBlockHeader struct {
    // Proposer is selected based on stake
    Proposer        types.HeimdallAddress `json:"proposer"`

    // StartBlock: The block number on Bor from which this checkpoint starts
    StartBlock      uint64                `json:"startBlock"`

    // EndBlock: The block number on Bor from which this checkpoint ends
    EndBlock        uint64                `json:"endBlock"`

    // RootHash is the Merkle root of all the leaves containing the block
    // headers starting from start to the end block
    RootHash        types.HeimdallHash    `json:"rootHash"`

    // Account root hash for each validator
  // Hash of data that needs to be passed from Heimdall to Ethereum chain like withdraw topup etc.
    AccountRootHash types.HeimdallHash    `json:"accountRootHash"`

  // Timestamp when checkpoint was created on Heimdall
    TimeStamp       uint64          `json:"timestamp"`
}

Root hash

RootHash is the Merkle hash of Bor block hashes from StartBlock to EndBlock. Root hash for the checkpoint is created using the following way:

blockHash = keccak256([number, time, tx hash, receipt hash])

Pseudocode for the root hash for 1 to n Bor blocks:

B(1) := keccak256([number, time, tx hash, receipt hash])
B(2) := keccak256([number, time, tx hash, receipt hash])
.
.
.
B(n) := keccak256([number, time, tx hash, receipt hash])

// checkpoint is Merkle root of all block hash
checkpoint's root hash = Merkel[B(1), B(2), ....., B(n)]

Here are some snippets of how checkpoint is created from Bor chain block headers.

Source: https://github.com/maticnetwork/heimdall/blob/develop/checkpoint/types/merkel.go#L60-L114

// Golang representation of block data used in checkpoint
blockData := crypto.Keccak256(appendBytes32(
    blockHeader.Number.Bytes(),
    new(big.Int).SetUint64(blockHeader.Time).Bytes(),
    blockHeader.TxHash.Bytes(),
    blockHeader.ReceiptHash.Bytes(),
))

// array of block hashes of Bor blocks
headers := [blockData1, blockData2, ..., blockDataN]

// merkel tre
tree := merkle.NewTreeWithOpts(merkle.TreeOptions{EnableHashSorting: false, DisableHashLeaves: true})
tree.Generate(convert(headers), sha3.NewLegacyKeccak256())

// create checkpoint's root hash
rootHash := tree.Root().Hash

AccountRootHash

AccountRootHash is the hash of the validator account-related information that needs to pass to the Ethereum chain at each checkpoint.

eachAccountHash := keccak256([validator id, withdraw fee, slash amount])

Pseudocode for the account root hash for 1 to n Bor blocks:

B(1) := keccak256([validator id, withdraw fee, slash amount])
B(2) := keccak256([validator id, withdraw fee, slash amount])
.
.
.
B(n) := keccak256([validator id, withdraw fee, slash amount])

// account root hash is Merkle root of all block hash
checkpoint's account root hash = Merkel[B(1), B(2), ....., B(n)]

Golang code for the account hash can be found here: https://github.com/maticnetwork/heimdall/blob/develop/types/dividend-account.go#L91-L101

// DividendAccount contains Fee, Slashed amount
type DividendAccount struct {
    ID            DividendAccountID `json:"ID"`
    FeeAmount     string            `json:"feeAmount"`     // string representation of big.Int
    SlashedAmount string            `json:"slashedAmount"` // string representation of big.Int
}

// calculate hash for particular account
func (da DividendAccount) CalculateHash() ([]byte, error) {
    fee, _ := big.NewInt(0).SetString(da.FeeAmount, 10)
    slashAmount, _ := big.NewInt(0).SetString(da.SlashedAmount, 10)
    divAccountHash := crypto.Keccak256(appendBytes32(
        new(big.Int).SetUint64(uint64(da.ID)).Bytes(),
        fee.Bytes(),
        slashAmount.Bytes(),
    ))

    return divAccountHash, nil
}