Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Efficient block relay format and mempool soft consensus

RECENT CHANGES:

  • (3 Dec 2015) Added transaction bundles, cleaned up the details, described the Global Mining Pool extension
  • (5 Dec 2015) Some p2p network message descriptions, explained how anonymous mining works.
  • (19 Jan 2016) New soft block format
  BIP: bip-soft-blocks
  Title: Efficient block relay format and mempool synchronization
  Author: John L. Jegutanis (john at coinomi.com)
  Status: Draft
  Type: Standards Track
  Created: 2015-12-01

Table of Contents

Abstract

This BIP defines a new block format called "soft block". It contains transaction lists and optional metadata to synchronize peer mempools. This lowers bandwidth requirements to propagate a block solution on the p2p network and minimizes consensus lag (faster fork resolution).

Motivation

Currently the peer to peer network relays block solutions in an inefficient way. Each block contains the 80-byte proof-of-work header along a list of serialized transactions. As most of the transactions were previously relayed and present in the mempool, it is possible to reference them and reduce the bandwidth usage.

Another issue is the long time it takes for a 1mb block to fully propagate the network. This increases the probability of pruned blocks that negatively affects the security of the system.

Specification

All serialized values use the Bitcoin's little endian wire format and use native types or scripts where present.

Soft block format

Additionally to the header we add a list of transactions or ids that describe the merkle tree and optional metadata that the miner can add.

  80-byte - Bitcoin header
  <tx reference> - Merkle tree transactions
  <metadata> - Optional miner metadata
  <signature> - Miner signature

The soft block id is the SHA256(Bitcoin header | metadata if present). When metadata is present, the id hash must be signed with the miner committed key.

Transaction reference

Transaction reference is a list where each entry can be a raw transaction, transaction id, selection, or a difference.

All transaction ids are truncated to 32bit. In case of id collisions, each conflicting id must be expressed in 64, 128, or 256bits by setting the appropriate flag.

Entry type

  0x00 raw tx list
  0x01 tx id list
  0x02 select [index start, end]
  0x03 transform [index start, end]
  0x04 metric or per fee sorting ?

Id precision flags

  0x00 32bit ids
  0x40 64bit ids
  0x80 128bit ids
  0xC0 256bit ids

Misc

  0xff reserved

---

Raw transaction list

One or more serialized transactions. This is useful when a miner wants to include a transaction that they didn't broadcast like the coinbase transaction.

  0x00 <varint number of transactions> <serialized tx 1> <serialized tx 2> ... <serialized tx n>

---

Transaction id list

A list of transaction ids. This is the usual reference to a new transaction that appeared in the mempool.

  0x01 <varint number of transactions> <tx id 0> <tx id 1> <tx id 2> ... <tx id n>

or if higher precision is needed

---

Select

Returns a list of transactions that were included in a previous soft block based on the indexes start to end.

  0x02 <soft block id> <varint start index> <varint end index>

---

Transform

Construct a transaction list based on a previous soft block tx list.

  0x03 <soft block id> <varint start index> <varint end index> <double sha256 of the final list> <varint algorithm> <varstr binary data>

If a node fails to recreate the new transaction list or does not support a particular algorithm, can request the block originator another encoding e.g. 0x01 transaction id list.

TODO: define supported algorithms like: bsdiff, IBLTs, or a custom differ

---

Example transaction reference list

  0x00 <the coinbase transaction>
  0x01 <list of individual 32bit transaction ids>
  0x41 <transactions with ids that conflict in 32bit precision>
  0x02 <id of a soft block> <index start> <index end>
  0x00 <a list of raw transactions that were not broadcast before>

The coinbase transaction must be always present in raw format or in diff. After the coinbase, the rest of the transactions are listed in the order they appear in the merkle tree. The calculated merkle root must match the value in the Bitcoin header.

Another usage of the reference transaction list are the proposed transactions that are validated in the mempool but are not mined in the current soft block. Transactions in this list are usually ordered by fees and generally contain transactions the the miner indents to include in the next block they will work. In a full block cannot the proposed transactions list is dropped and not relayed, so it cannot be referenced in next blocks.

Metadata

Metadata is an optional data list that the miner attaches. It must be signed with the miner key that is committed in the coinbase transaction.

  <varint> total size in bytes
  <entry 1 data>
  <entry 2 data>
  ...
  <entry k data>

Entry:

  <varstr> unique extension identifier
  1-byte extension version
  <varstr> the extension specific data

TODO: define some default metadata: parent list, witnessed transactions, miner identifier

Miner key commitment

The miner creates a private key and calculates the hash160 of the public key (default is EC Secp256k1). This hash is committed to the coinbase transaction.

  1-byte - OP_RETURN (0x6a)
  1-byte - Push the following 25 bytes (0x19)
  4-byte - Commitment magic (0x50f7b10c)
  1-byte - Version (0x00 == secp256k1)
  20-byte - Signing key public key hash160

If there are more than one scriptPubKey matching the pattern, the one with highest output index is assumed to be the public key commitment.

P2P network

TODO: incomplete

To discover soft block compatible nodes a service bit must be registered. The p2p network shall use the same bitcoin data structures but it would be capable to work over UDP.

TODO: define a BIP36 compatible service and UDP network. Some additional commands we need are:

  • Broadcast a soft block.
  • Soft ACK - When a node that received the soft block was able to verify the mempool transactions.
  • Soft NACK - When a node that received a soft block is missing transactions and includes the missing mini TX ids in the same message.
  • Hard ACK - When a node was able to verify a full block locally by using the bitcoin core consensus rules.
  • Hard NACK - When a node was not able to verify a full block. This could happen due to bugs and the full node should fall back to sending the full block via the legacy protocol.
  • Request previous soft blocks, on a specific height etc
  • Get transactions by using mini TX ids

Appendix

Constructing a blockdag with soft blocks

Each soft block can have multiple parents that doesn't contain conflicting transactions and it must not be in conflict with it's parents. A parent cannot be a simultaneously an ancestor of another parent at the same time i.e. when graphing the DAG, there are no triangles.

TODO: add difficulty and size adjustment code.

The soft block must contain transaction references that validates the merkle tree root of the header. In case a transaction is not present, the block is not valid until the missing pieces are fetched from the block originator peer.

In case of a blockdag fork, we calculate the amount of work for each tip to determine the miner consensus.

A soft block shall be transmitted before any other data and first to peers that have the smallest RTT (discovered with ping/pong messages).

Acknowledgements

  • Pieter Wuille for pointing out that the relation between block spacing and difficulty is logarithmic, not linear.
  • Gregory Maxwell for pointing out that UTXO commitment validations are IO expensive and that the network should not punish in case a commitment is not honored. Additionally for describing a similar scheme that we presented.
  • Bob McElrath for the Braid DAG and the no-incest parent linking rule.
  • Gavin Andresen, Rusty Russell, Matt Corallo, Peter Todd, Tier Nolan and the P2Pool team for independently inventing some of the concepts used in this proposal.
@petertodd
Copy link

petertodd commented Dec 19, 2015

Please don't self-assign BIP #'s

@btcdrak
Copy link

btcdrak commented Dec 19, 2015

the correct naming strategy is

bip-authorname-shorttitle, this is defined by the BIP1 document

@gubatron
Copy link

gubatron commented Dec 20, 2015

typo: "It is know " -> "It is known"

@erasmospunk
Copy link
Author

erasmospunk commented Dec 21, 2015

@petertodd @btcdrak I asked Gregory for 109 and he reserved it for me. However this document was not meant to go public yet, I am changing to bip-authorname-shorttitle format to avoid further confusion.

@kanzure
Copy link

kanzure commented Jan 4, 2016

Arguments for small blocks don't stop at "bitcoin p2p consensus latency"; weak blocks are useful even if they don't resolve question of big vs small max block size limit. I don't think the current "motivation" section makes sense ( e211e886ccd2b3ba139d19a7e94fb799ffd5ac2c ). also mentioned this in http://gnusha.org/bitcoin-wizards/2016-01-03.log

some other recent work (or discussion) on weak blocks:
https://www.reddit.com/r/Bitcoin/comments/3m2wpf/bitcoindev_weak_block_thoughts/cvbre8i

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment