From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id 6A64F1B02 for ; Tue, 28 May 2019 00:11:59 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-pf1-f171.google.com (mail-pf1-f171.google.com [209.85.210.171]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 48F3EA9 for ; Tue, 28 May 2019 00:11:58 +0000 (UTC) Received: by mail-pf1-f171.google.com with SMTP id u17so10312678pfn.7 for ; Mon, 27 May 2019 17:11:58 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:message-id:in-reply-to:references:subject:mime-version; bh=97mAbHkDzW+C9AAzia9XEB94AyCzewioQYQT2a8S554=; b=JdICXyyjbio00vQYioyPVbYlwb0Cj+b4h83T0LxUe8da+C8LWim+8GYu4ZKscu2GUb X50ggfAO02l5FkHMvIUECtsolQtE1FrG4f8aK8xtDEFVchTtDTwGcHXw5o7c8eA4qZCb yasQ59X7BBvPRFH1J2vl2ZvXbie20Jja7UdL8fqvjglURaB+bFeB77A6GF7SAMXzp6ef QSFENZ192GVJfoT9gkPRSl1ULbrCBDyw/mHcTQaeolYhA545V5d3zuCPeZTg9UInvYxJ BY69vVTn7ZPRP2UT2+VDf3MwcNBpSal3nkhrkY0mdwf0bM398PGyuvq2B1DVFeiaAO5L IBuw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:message-id:in-reply-to:references :subject:mime-version; bh=97mAbHkDzW+C9AAzia9XEB94AyCzewioQYQT2a8S554=; b=tqB22MQ0/GW6wO+hr5+Wo7mXiMaX2Gzbvd8VDULgB2GRkOdmNH6RCJ4xIxE18wjuvI wNn4n7UUSChvgotByZ6UWBCzW/kPzCy7zn4iQDr8gVJlHSvuhgixrokH5n6AyX6sGTTK clM7v5nbNsP5cd1wmu2k9hQQ80YqDcGAHynUcTSATGiO8kNU/H8knh1yKGGLzzdeVduk 1pNoqcckCgD8vuwtHBFKI/qnr+79fLSYXBe77vuxAJrBiZWadoq+rlCCYMFbkXQv7zj+ b/OGlGdS1aFd7cmtUrXbe+YHFZv65vZSLy9BBDpx37zH4zgpdsrAvmiQmFHjLLXo/zsk BvLQ== X-Gm-Message-State: APjAAAVIsg29ca5x53Kij1a2uRUi4XHPQyhD8mmkimnXRoORrbcUTRBZ wtfboHPo4c4dKN67V1evHer7mdybEhM= X-Google-Smtp-Source: APXvYqzMdvYSIU7WAOMlB8OLgKMGwrs2ShAzcCLJBbtRed0a1adoZcVIF+kYz00pAwZESC2yQCsdpg== X-Received: by 2002:a63:454e:: with SMTP id u14mr235061pgk.377.1559002317250; Mon, 27 May 2019 17:11:57 -0700 (PDT) Received: from [10.0.19.154] (s206-116-45-202.bc.hsia.telus.net. [206.116.45.202]) by smtp.gmail.com with ESMTPSA id x1sm6123855pgq.13.2019.05.27.17.11.55 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 27 May 2019 17:11:56 -0700 (PDT) Date: Mon, 27 May 2019 17:11:50 -0700 From: Gleb Naumenko To: Bitcoin Protocol Discussion Message-ID: In-Reply-To: References: X-Readdle-Message-ID: d9eda8a2-4c96-4dec-a34a-cd184eb8aeda@Spark MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="5cec7ccb_66ef438d_14b" X-Spam-Status: No, score=-2.0 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, HTML_MESSAGE, RCVD_IN_DNSWL_NONE autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org X-Mailman-Approved-At: Tue, 28 May 2019 02:52:29 +0000 Subject: [bitcoin-dev] Bandwidth-Efficient Transaction Relay for Bitcoin X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 28 May 2019 00:11:59 -0000 --5cec7ccb_66ef438d_14b Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline Hi all, We are making public our latest work on Erlay, an efficient transaction r= elay protocol for Bitcoin. It is available here:=C2=A0https://arxiv.org/abs/1905.10518 The main idea is that instead of announcing every transaction to every pe= er, announcements are only sent directly over a small number of connectio= ns (only 8 outgoing ones). =46urther relay is achieved by periodically ru= nning a set reconciliation protocol over every connection between the set= s of withheld announcements in both directions. The set reconciliation protocol uses error correcting codes to communicat= e a set of transactions to a peer with an unknown but similar set using b= andwidth only equal to the size of the difference and not the size of the= sets themselves. Results: we save half of the bandwidth a node consumes, allow increasing = connectivity almost for free, and, as a side effect, better withstand tim= ing attacks. If outbound peer count were increased to 32, Erlay saves around 75% overa= ll bandwidth compared to the current protocol. This work uses Minisketch, an efficient library for set reconciliation, w= hich we made public before:=C2=A0github.com/sipa/minisketch. Some of you may already know about it from discussions with me, Scaling B= itcoin 18, or CoreDev in Tokyo. Our proposal has become more precise sinc= e then. The next step here is to receive more feedback, have a broader discussion= , and then write a BIP along with improving reference implementation. We = are looking forward to hearing your suggestions or concerns regarding thi= s work. This protocol is a result of work by myself, Gregory Maxwell, Pieter Wuil= le, and my supervisors at UBC: Ivan Beschastnikh and Sasha =46edorova. I would like to thank Tim Ruffing and Ben Woosley for contributions to th= e write-up, and Blockstream for supporting my work on this protocol. =E2=80=93 gleb --5cec7ccb_66ef438d_14b Content-Type: text/html; charset="utf-8" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline
Hi all,

We are making public our latest work on Erlay, an efficient transaction r= elay protocol for Bitcoin.
It is available here:&=23160;https://arxiv.org/abs/1905.10518

The main idea is that instead of announcing every transaction to every pe= er, announcements are only sent directly over a small number of connectio= ns (only 8 outgoing ones). =46urther relay is achieved by periodically ru= nning a set reconciliation protocol over every connection between the set= s of withheld announcements in both directions.

The set reconciliation protocol uses error correcting codes to communicat= e a set of transactions to a peer with an unknown but similar set using b= andwidth only equal to the size of the difference and not the size of the= sets themselves.

Results: we save half of the bandwidth a node consumes, allow increasing = connectivity almost for free, and, as a side effect, better withstand tim= ing attacks.
If outbound peer count were increased to 32, Erlay saves around 75% overa= ll bandwidth compared to the current protocol.

This work uses Minisketch, an efficient library for set reconciliation, w= hich we made public before:&=23160;github.com/sipa/minisketch.

Some of you may already know about it from discussions with me, Scaling B= itcoin 18, or CoreDev in Tokyo. Our proposal has become more precise sinc= e then.

The next step here is to receive more feedback, have a broader discussion= , and then write a BIP along with improving reference implementation. We = are looking forward to hearing your suggestions or concerns regarding thi= s work.

This protocol is a result of work by myself, Gregory Maxwell, Pieter Wuil= le, and my supervisors at UBC: Ivan Beschastnikh and Sasha =46edorova. I would like to thank Tim Ruffing and Ben Woosley for contributions to th= e write-up, and Blockstream for supporting my work on this protocol.

=E2=80=93 gleb
--5cec7ccb_66ef438d_14b--