PascalCoin/PIP/PIP-0015.md

  PIP: PIP-0015
  Title: Fast Block Propagation
  Type: Protocol
  Impact: Soft-Fork
  Author: Herman Schoenfeld <[email protected]>
  Comments-URI: https://discord.gg/sJqcgtD  (channel #pip-0015)
  Status: Active
  Created: 2018-01-04

Summary

A method to rapidly propagate blocks is proposed in order to minimize orphan rates. It involves propagating a block skeleton rather than the full block, reducing network traffic by 95%. Nodes can rebuild the full block by plugging operations from the Pending Pool into the skeleton.

Motivation

Due to slow block propagation and expensive SafeBox rollbacks, PascalCoin tends to experience high orphan rates when mining community becomes highly decentralized. Due to the current centralization, this has not been noticable. However, once decentralization is resolved as has been proposed, this issue will re-emerge. As a result, a solution is required in combination with centralization resolution.

Specification

Block Propagation Change

Currently, when a peer is notified of a new block the entire block is sent. In this proposal only a Block Skeleton is sent, structured as follows:

Block Skeleton

[BLOCK HEADER]  (~200 bytes)
[NUM OPERATIONS] (4 bytes)
[OP_REF_1] (8 bytes)
....
[OP_REF_N] (8 bytes)

The skeleton does not contain full operation data, only a reference to the operation. The reference is a 64bit value composed of the AccountNumber and the N_OPERATION of the account authoring the operation.

function GetOpRef(operation : Operation) : QWord
begin
  let accountNumber = operation.Account
  let n_operation = operation.n_operation
  Result = (QWord(accountNumber) SHL 32) BIT-OR QWord(n_operation))
end

The concept of OP_REF is already in PascalCon as part of Albert Molina's OPHASH algorithm:

OPHASH = OP_BLOCK_ID ++ OP_REF ++ RIPEMD160(OP_RAW_DATA)

Block Construction From Skeleton

The receiving node is required to rebuild the full block from the skeleton it has received as follows:

Function ReconstructBlock(skeleton : BlockSkeleton) : Block
begin
    let missing = List<QWord>.Create
    let block = Block.Create
    block.Header = skeleton.Header
    for i = 0 to skeleton.NumOperations - 1 do
        let opRef = skeleton.Operations[i]
        if PendingPool.Contains(opRef) then
            block.Operations[i] = PendingPool.GetByOpRef(opRef)
        else
            missing.Add(opRef)

        if missing.Length > 0 then
            PendingPool.AddMany( NET_OP_PULL_ACCOUNT_OPS(missing) )
            Result := ReconstructBlock(skeleton)
        else
            Result := block
end

NOTE Care must be taken to ensure endianess correctness in OP_REF as done now in PascalCoin OPHASH calculations.

New Network Operation: NET_OP_PULL_ACCOUNT_OPS

This network operation allows a node to fetch specific block operations from other nodes that it does not have. It is used for rebuilding the full block from the block skeleton. The requesting node references the desired block operation using a BLOCK_OP_REF which is a QWord structure defined as follows:

    BLOCK_OP_REF = (QWord(BlockNumber) SHL 32) BIT-OR QWord(OperationIndex)

If the receiving node does not have this operation, the requesting node re-sends the request to other nodes until one is found (or abandoned). This operation will be used in-frequently since most nodes have most of the operations most of the time.

Arguments

• N: DWord - the number of operations being requested

• BLOCK_OP_REF_1: QWord - the first operation being requested

  . . .

• BLOCK_OP_REF_N: QWord - the N'th operation being requested

Output

• M: DWord - the number of operations being returned
• OP_SIZE_1 : DWord - the size of first operation being returned

• OP_1 : ByteArray[OP_SIZE_1] -- the raw data of first operation being returned

  . . .

• OP_SIZE_M : DWord - the size of the M'th operation being returned

• OP_M - the raw data of M'th operation being returned

Block Propagation Workflow

Suppose Bob and Alice run nodes and Alice encounters a new valid block B.

• Alice sends B to Bob in the form of a Block Skeleton
• Bob reconstructs block by pulling missing operations from Alice using NET_OP_PULL_ACCOUNT_OPS
• Bob validates block B
  • If invalid, Bob reconstructs B again by pulling all the operations from Alice, including ones he already had.
  • If invalid, Bob discards B and blacklists Alice
  • Otherwise Bob accepts B as the next block
  • Otherwise Bob accepts B as the next block
    

NOTE: other network operations will need to be modified to support Block Skeleton pushing.

Rationale

This provides a 95% reduction in the block data being transmitted increasing propagation efficiency. As a result, orphan rates are expected to proportionally reduce resulting a dramatically less number of orphans. In combination with other PIPs that improve SafeBox rollback efficiency, PascalCoin will be able to seamlessly support CPU-mining such as proposed in PIP-0009.

Backwards Compatibility

This change is backwards compatible and can be introduced as a soft-fork.

## Links

1. PIP-009: RandomHash: GPU & ASIC Resistant Hash Algorithm