HackMD
  • Prime
    Prime  Full-text search on all paid plans
    Search anywhere and reach everything in a Workspace with Prime plan.
    Got it
      • Create new note
      • Create a note from template
    • Prime  Full-text search on all paid plans
      Prime  Full-text search on all paid plans
      Search anywhere and reach everything in a Workspace with Prime plan.
      Got it
      • Options
      • Versions and GitHub Sync
      • Transfer ownership
      • Delete this note
      • Template
      • Save as template
      • Insert from template
      • Export
      • Dropbox
      • Google Drive
      • Gist
      • Import
      • Dropbox
      • Google Drive
      • Gist
      • Clipboard
      • Download
      • Markdown
      • HTML
      • Raw HTML
      • Sharing Link copied
      • /edit
      • View mode
        • Edit mode
        • View mode
        • Book mode
        • Slide mode
        Edit mode View mode Book mode Slide mode
      • Note Permission
      • Read
        • Owners
        • Signed-in users
        • Everyone
        Owners Signed-in users Everyone
      • Write
        • Owners
        • Signed-in users
        • Everyone
        Owners Signed-in users Everyone
      • More (Comment, Invitee)
      • Publishing
        Everyone on the web can find and read all notes of this public team.
        After the note is published, everyone on the web can find and read this note.
        See all published notes on profile page.
      • Commenting Enable
        Disabled Forbidden Owners Signed-in users Everyone
      • Permission
        • Forbidden
        • Owners
        • Signed-in users
        • Everyone
      • Invitee
      • No invitee
    Menu Sharing Create Help
    Create Create new note Create a note from template
    Menu
    Options
    Versions and GitHub Sync Transfer ownership Delete this note
    Export
    Dropbox Google Drive Gist
    Import
    Dropbox Google Drive Gist Clipboard
    Download
    Markdown HTML Raw HTML
    Back
    Sharing
    Sharing Link copied
    /edit
    View mode
    • Edit mode
    • View mode
    • Book mode
    • Slide mode
    Edit mode View mode Book mode Slide mode
    Note Permission
    Read
    Owners
    • Owners
    • Signed-in users
    • Everyone
    Owners Signed-in users Everyone
    Write
    Owners
    • Owners
    • Signed-in users
    • Everyone
    Owners Signed-in users Everyone
    More (Comment, Invitee)
    Publishing
    Everyone on the web can find and read all notes of this public team.
    After the note is published, everyone on the web can find and read this note.
    See all published notes on profile page.
    More (Comment, Invitee)
    Commenting Enable
    Disabled Forbidden Owners Signed-in users Everyone
    Permission
    Owners
    • Forbidden
    • Owners
    • Signed-in users
    • Everyone
    Invitee
    No invitee
       owned this note    owned this note      
    Published Linked with GitHub
    Like BookmarkBookmarked
    Subscribed
    • Any changes
      Be notified of any changes
    • Mention me
      Be notified of mention me
    • Unsubscribe
    Subscribe
    # Gossip pubsub simulation in the context of Beacon Chain The network of Libp2p Gossip nodes is simulated to find out how different gossip (and non-gossip) parameters affect message dessimination and network traffic ## Simulator overview - Based on JVM Libp2p Gossip implementation - Written in Kotlin - Currently implemented in the form of [tests](https://github.com/libp2p/jvm-libp2p/blob/feature/simulator/src/test/kotlin/io/libp2p/simulate/gossip/Simulation1.kt) in a separate [jvm-libp2p branch](https://github.com/libp2p/jvm-libp2p/tree/feature/simulator) - Capable of running any Libp2p based protocol - Large scale capability (tested up to 100K nodes) due to short cutting network stack and protocol data serialization - Time control: time can be moved forward, all scheduled tasks are executed in the same order as in a usual system enviroment - Determinism: any simulation with the same random seed may be replayed 1:1 - Multithreading. Two different (not mutually excluding) options available: - Parallel simulation processing: runs several simulations with different parameters concurrently. `N` threads require `xN` memory but gains `xN` speedup. Determinism preserved - Parallel node processing: a single simulation starts `M` threads and shares them across all nodes. Has the same memory footprint, gains speedup depending on protocol performance (gossip gains just up to `x2.5`). Not deterministic. - Network parameters: configurrable topology, individual connection latency (constant or random), node system clock shifts, total node net throughput (not yet tested) ## Simulation setup - Network: 5000-10000 nodes, each has N (normally 10-30) peers connected randomly. - Message payload size: 32Kb as an average block size (having in mind block propagation) - Network latency: either constant 1ms or uniformely distributed random value (1-50ms) - Default Gossip values from the [Eth2.0 spec](https://github.com/ethereum/eth2.0-specs/blob/dev/specs/networking/p2p-interface.md#the-gossip-domain-gossipsub) - Statistics are gathered based on `N` randomly generated networks (normaly 10) and `M` messages sent from random nodes (normally 3-5) for each parameter set - Some BFT test simulations contain a percentage of _bad_ nodes (80-95%, i.e. 5:1-20:1 bad/fair nodes ratio). Those nodes just don't propagate Gossip messages to their peers - In some simulations the Gossip heartbeat start moment is randomly scattered to avoid side effects due to simultaneous node heartbeats - After network is connected a `warmUp` time (5 sec) is rewinded allowing Gossip to exchange initial messages and build more or less stable meshes - Some simulation results contains two sets of statistics - `0-*`: 'immediate' effect after publishing a message when no heartbeats executed yet. This is when 'gossiping' (`IHAVE/IWANT` messages with message IDs) is not involved. - `N-*`: when a significant number of heartbeats is executed after publishing a message and the 'gossiping' is expected to be done across the whole network - The main result measurements are - traffic: number of bytes transmitted (TCP framing is taken into account) per one node per one published message - %% of nodes received the message - message delivery time (ms): 50% percentile/90% percentile/max - traffic overhead: `traffic / [ideal traffic]`, where `ideal traffic` if the simulated message payload size (32Kb for block propagation case) ## Simulation cases ### BFT Simulates network with different fractions of 'bad' nodes. 'Bad' node - the node which doesn't propagate incoming messages With default gossip settings and 20 peer connections the upper bound of bad nodes is 80% (or ~x5 of normal nodes) It shows that 'gossiping' part of the protocol start working in extreme environment only. In that case message delivery timing becomes pretty high. [[Results]](https://docs.google.com/spreadsheets/d/1QvYio6ALnjrEYmsgZMTuK-ktIZzeRbqIOvPrU4b-Cl0/edit#gid=0) ### Results consistency This is just to check that simulation results don't bounce drammatically when the network size changes. [[Results]](https://docs.google.com/spreadsheets/d/1QvYio6ALnjrEYmsgZMTuK-ktIZzeRbqIOvPrU4b-Cl0/edit#gid=1024299423) ### More peers - better BFT Checking how number of connected peers affects BFT. Simulating the network where bad/honest nodes ratio is 10/1. The results are not surprising: more peer connections - better BFT. Traffic increase is the cost of BFT growth. [[Results]](https://docs.google.com/spreadsheets/d/1QvYio6ALnjrEYmsgZMTuK-ktIZzeRbqIOvPrU4b-Cl0/edit#gid=1880641373) ### Less Gossip `D` - less traffic overhead The 'ideal' traffic to disseminate a message is the x1 of a message payload (32Kb in our simulations). Current Eth2.0 gossip settings result in ~x5-6 of traffic overhead. Reducing the `D` param may decrease the overall traffic, while preserving BFT and delivery rate due to 'gossiping' For more consistent results `DLow` and `DHigh` params are set closer to `D`. This would increase gossip mesh rebuilding frequesncy (`GRAFT` messages traffic) but would keep the real mesh size closer to simulated param. [[Results]](https://docs.google.com/spreadsheets/d/1QvYio6ALnjrEYmsgZMTuK-ktIZzeRbqIOvPrU4b-Cl0/edit#gid=130055630) ### Gossip `DLazy` has no much traffic overhead 'Gossiping' improves BFT at little traffic cost. Increasing `DLazy` doesn't result in a significant traffic overhead in a healthy network. [[Results]](https://docs.google.com/spreadsheets/d/1QvYio6ALnjrEYmsgZMTuK-ktIZzeRbqIOvPrU4b-Cl0/edit#gid=305605107) ### Playing with heartbeat period While 'gossiping' saves traffic and improves BFT its delivery delay could be an issue for time critical applications. Message IDs are 'gossiped' on hearbeats (which period is defaulted to 1 sec in Eth2.0 spec) and the cummulative delivery time becomes order of seconds. This simulation increases heartbeat frequency in agressive environment (90% of bad nodes). Due to this delivery time singnificantly improves with no large traffic cost. However `period < 100ms` causes significant traffic increase (probably due to the network latency interference). [[Results]](https://docs.google.com/spreadsheets/d/1QvYio6ALnjrEYmsgZMTuK-ktIZzeRbqIOvPrU4b-Cl0/edit#gid=114511837) ### Trying immediate gossip As a follow up of the previous simulation, this one modifies Gossip implementation to immediately broadcast the message gossip to the peers outside of the mesh. (the similar way Eth1.0 propagates a block: minor peers subset receives full block, others receive only hash) The results are similar to heartbeats with small period: 'gossiping' delivery time significantly improves while traffic overhead increases in a healthy network [[Results]](https://docs.google.com/spreadsheets/d/1QvYio6ALnjrEYmsgZMTuK-ktIZzeRbqIOvPrU4b-Cl0/edit#gid=341160593) ## Conclusions - default gossip options almost don't utilize 'gossipping' feature in a 'normal' environment. - Even when 'gossiping' feature is utilized (e.g. in 'aggressive' environment) the delivery time may be unacceptable due to infrequent heartbeats (1 sec) - In the absense of 'gossiping' effect there is x5-x6 traffic overhead (for block propagation) due to full message duplications - the Gossip is BFT - (unrelated to gossip) BFT is greatly improved by peers number - BFT can be improved by increasing `DLazy` with relatively small cost - Possible attack vector is to spam the network with old messages thus we need to make sure that the gossip 'seen message set' size is large enough and the application validator rejects 'old' data ## Gossip protocol proposals/issues - Separate 'gossiping' (`IHAVE`) and 'mesh' (`GRAFT`) heartbeat periods. To enable fast 'gossiping' without too frequent mesh rebuilding. - consider 0 'gossiping' heartbeat delay (like Eth1.x sends block hashes immediately): While [simulation](https://docs.google.com/spreadsheets/d/1QvYio6ALnjrEYmsgZMTuK-ktIZzeRbqIOvPrU4b-Cl0/edit#gid=341160593) shown x10 faster 'gossippng' message propagation in the normal scenario traffic increases up to x2 - Don't duplicate `IHAVE` messages to peers (on each `gossip_advertise` cycle gossip picks `DLazy` random peers with no respect to already sent `IHAVE` messages). While it may save some bytes of traffic it may over-complicate the gossip protocol.

    Import from clipboard

    Advanced permission required

    Your current role can only read. Ask the system administrator to acquire write and comment permission.

    This team is disabled

    Sorry, this team is disabled. You can't edit this note.

    This note is locked

    Sorry, only owner can edit this note.

    Reach the limit

    Sorry, you've reached the max length this note can be.
    Please reduce the content or divide it to more notes, thank you!

    Import from Gist

    Import from Snippet

    or

    Export to Snippet

    Are you sure?

    Do you really want to delete this note?
    All users will lost their connection.

    Create a note from template

    Create a note from template

    Oops...
    This template is not available.


    Upgrade

    All
    • All
    • Team
    No template found.

    Create custom template


    Upgrade

    Delete template

    Do you really want to delete this template?

    This page need refresh

    You have an incompatible client version.
    Refresh to update.
    New version available!
    See releases notes here
    Refresh to enjoy new features.
    Your user state has changed.
    Refresh to load new user state.

    Sign in

    Forgot password

    or

    By clicking below, you agree to our terms of service.

    Sign in via Facebook Sign in via Twitter Sign in via GitHub Sign in via Dropbox Sign in via Google

    New to HackMD? Sign up

    Help

    • English
    • 中文
    • Français
    • Deutsch
    • 日本語
    • Español
    • Català
    • Ελληνικά
    • Português
    • italiano
    • Türkçe
    • Русский
    • Nederlands
    • hrvatski jezik
    • język polski
    • Українська
    • हिन्दी
    • svenska
    • Esperanto
    • dansk

    Documents

    Tutorials

    Book Mode Tutorial

    Slide Mode Tutorial

    YAML Metadata

    Contacts

    Facebook

    Twitter

    Feedback

    Send us email

    Resources

    Releases

    Pricing

    Blog

    Policy

    Terms

    Privacy

    Cheatsheet

    Syntax Example Reference
    # Header Header 基本排版
    - Unordered List
    • Unordered List
    1. Ordered List
    1. Ordered List
    - [ ] Todo List
    • Todo List
    > Blockquote
    Blockquote
    **Bold font** Bold font
    *Italics font* Italics font
    ~~Strikethrough~~ Strikethrough
    19^th^ 19th
    H~2~O H2O
    ++Inserted text++ Inserted text
    ==Marked text== Marked text
    [link text](https:// "title") Link
    ![image alt](https:// "title") Image
    `Code` Code 在筆記中貼入程式碼
    ```javascript
    var i = 0;
    ```
    var i = 0;
    :smile: :smile: Emoji list
    {%youtube youtube_id %} Externals
    $L^aT_eX$ LaTeX
    :::info
    This is a alert area.
    :::

    This is a alert area.

    Versions

    Versions and GitHub Sync

    Sign in to link this note to GitHub Learn more
    This note is not linked with GitHub Learn more
     
    Add badge Pull Push GitHub Link Settings
    Upgrade now

    Version named by    

    More Less
    • Edit
    • Delete

    Note content is identical to the latest version.
    Compare with
      Choose a version
      No search result
      Version not found

    Feedback

    Submission failed, please try again

    Thanks for your support.

    On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?

    Please give us some advice and help us improve HackMD.

     

    Thanks for your feedback

    Remove version name

    Do you want to remove this version name and description?

    Transfer ownership

    Transfer to
      Warning: is a public team. If you transfer note to this team, everyone on the web can find and read this note.

        Link with GitHub

        Please authorize HackMD on GitHub

        Please sign in to GitHub and install the HackMD app on your GitHub repo. Learn more

         Sign in to GitHub

        HackMD links with GitHub through a GitHub App. You can choose which repo to install our App.

        Push the note to GitHub Push to GitHub Pull a file from GitHub

          Authorize again
         

        Choose which file to push to

        Select repo
        Refresh Authorize more repos
        Select branch
        Select file
        Select branch
        Choose version(s) to push
        • Save a new version and push
        • Choose from existing versions
        Available push count

        Upgrade

        Pull from GitHub

         
        File from GitHub
        File from HackMD

        GitHub Link Settings

        File linked

        Linked by
        File path
        Last synced branch
        Available push count

        Upgrade

        Danger Zone

        Unlink
        You will no longer receive notification when GitHub file changes after unlink.

        Syncing

        Push failed

        Push successfully