Skip to content
Permalink
Branch: master
Find file Copy path
Find file Copy path
Fetching contributors…
Cannot retrieve contributors at this time
222 lines (163 sloc) 6.96 KB

UIP-21 Transfer Esperanza Transactions

Author:   Stanislav Frolov <stanislav@thirdhash.com>
Status:   Proposed
Created:  2018-11-08

Note: this document is actively being developed and might be changed

It's the second version of the document, see previous one.

TODO: describe push messaging

Context

We're implementing a Casper-inspired finalization protocol named Esperanza. As part of the protocol we need to adapt fork choice rule, a significant portion of that change is to follow the longest justified chain. To represent justification and finalization, we have the finalization state for every chain which is based on transactions of blocks that belong to the chain.

To explain the problem imagine Node A has the longest chain and Node B has the shortest but recently justified one. Nodes were disconnected/unsynced, so were able to build different chains, and eventually get connected to each other.

main finalized root
     ∨
     R ... - A1 - A2 - A3 - A4 - A5   Node A
     ------------------------------
            \
             B1 - B2 - B3             Node B
                   ^
                justified

According to the fork-choice rule, after being connected Node A must switch to longest justified chain with tip B3. To calculate B3's finalization state Node A needs Esperanza transactions for blocks B1, B2, and B3. The current p2p implementation which is taken from bitcoin prohibits this as it won't download B1, B2, and B3 blocks since their tip's Work is less than the work of A5.

This document proposes to add new pull-like commands to retrieve headers and Esperanza transactions (which we'd name Commits below) for epochs which might be used as a trigger to start downloading the whole blocks in order to change to the longest justified chain.

Esperanza transactions (Commits) are:

  • DEPOSIT
  • VOTE
  • LOGOUT
  • SLASH
  • WITHDRAW
  • ADMIN

Decision

We add a new mechanism of headers-and-commits exchange which would allow peers to download headers and commits incrementally, dynasty by dynasty. Once a node receives the bunch of headers-and-commits, it can decide to download corresponding blocks, validate it, and continue the process, or to reject it.

getcommits message

Request block headers and corresponding commits from the most recent block hash until one of the termination conditions depends on what happened first:

  • the next finalized checkpoint,
  • the end of the main chain in case of no finalization found,
  • the stop block hash.

The node should respond only on the main chain.

Size Name Type Comments
1-4 length var_int Length of the start vector
? start uchar[32][] Vector of block hashes, ascend order
32 stop uchar[32] 0x0 disables this termination condition

The behavior of start is similar to bitcoin's block locator. In the sync-mode it makes sense to fill it with checkpoints in between last known finalization point and most recent checkpoint, and keep stop=0x0.

TODO: later it'd reused in PUSH.

F -> ...blocks... -> C1 -> ...blocks... -> C2 -> ...blocks...

F is a finalized checkpoint
C1 and C2 are checkpoints (C1 is justified by definition).

If you want to ask for headers and commits after checkpoint C2, the node can use

getcommits
  length = 3
  start = [ F, C1, C2 ]
  stop = 0x0

When a peer receives such message, it scans the main chain starting from F to find C1 and C2. It replies with headers and commits next to the most recent checkpoint and until the next finalization point or the tip, or stop.

In a green path when every checkpoint is finalized such request usually would look like

getcommits
  length = 2
  checkpoints = [ F, C1 ]
  stop = 0x0

where C1 and F are respectively the last justified and the last finalized checkpoint.

commits message

Response to getcommits.

Size Name Type Comments
1 status uint8 Status of reply, 0 = finalization or "stop" reached, 1 = tip reached, 2 - message length limit exceeded
1-4 length var_int
? headers_and_commits header_and_commits[]

When the message length limit exceeded, send the message and continue with a new one; repeat until you reach the termination condition.

header_and_commits type

Size Name Type Comments
140 header header Size is actual for time this document created
1-4 commits_length var_int
? commits tx[]

header type

We extend the header type by adding commits merkle root hash.

Note, this table might become outdated due to further protocol updates.

Size Name Type Comments
4 version uint32
32 prev_block uchar[32]
32 merkle_root uchar[32] No change: all transactions including commits
32 witness_merkle_root uchar[32] No change: all transactions including commits
32 merkle_root_commits uchar[32] New field: merkle root hash of commits
4 timestamp uint32
4 bits uint32

Examples

Fork choice: full sync

main finalized root     checkpoints
     ∨                  ∨         ∨
     R0 - R1 - J - A1 - A2 - A3 - A4 - A5   Node A
     -----------------------------------------
                  \
                   B1 - B2 - B3             Node B
                        ^
                     justified

Items represent blocks.
R0 is finalized checkpoint.
J is justified checkpoint.

Node A syncs with Node B and have to switch to the longest justified chain, B3.

A->B: getcommits
getcommits
  length = 4
  start = [ R, J, A2, A4 ]
  stop = 0x0
B->A: commits
  1. B finds R on the main chain.
  2. B finds J on the main chain.
  3. B doesn't find A2 on the main chain.
  4. B prepares commits after J.
commits
  status = 0
  length = 3
  commits = [ commits(B1), commits(B2), commits(B3) ]
A: fork choice
  1. A reconstructs finalization state for B3 on top of J
  2. As B3 is longest justified chain, A downloads B1, B2, and B3 blocks and switches its main chain there.

Reference implementation

Unit-e pull request

Changelog

  • 2019-04-16 Added reference implementation and changed status to proposed
  • 2018-12-12 Moved to UIP repository as UIP-21

Copyright

This document is dual-licensed under CC0 and MIT.

You can’t perform that action at this time.