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 1F428C2A for ; Wed, 25 Sep 2019 11:28:20 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-wr1-f41.google.com (mail-wr1-f41.google.com [209.85.221.41]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 4F9E18A8 for ; Wed, 25 Sep 2019 11:28:11 +0000 (UTC) Received: by mail-wr1-f41.google.com with SMTP id h7so6403545wrw.8 for ; Wed, 25 Sep 2019 04:28:11 -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=Zeb8rO4fAyXCiWwMMTxe5ymBYUwtBTalreOQiSO4Q7o=; b=DOqOdqjPvKQAPBfcQubYopF5HouOsAQdNnmmVBJEPrbnyojd9TNZdD56oU+Tne3Wxe rCwDyqzXRNb6jSZ/9rHzK/pLu/X95RhcjCt7kMdAW8DHXwTDYNVgqeDjP5kk5ZCvRvwO Qb9IW27Xk3SAgRV/K7RtUfZgEEesbPDmn2Kgg10CJxkFdDbZLpmAcNnOvGJj+o6WgPNn KtZH5GbXeZ4ZVMYwMjxUBclW79wwCbK0AStBNksv76kylDwVNTYaXfcoZ0TZTBSqe4yt SbNR2eX4+t2VWTij3pfk9qmKaj6AMfPDcYauFAlTbBPhDiDiw1HbHawBY56cyxIxezTN jYCg== 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=Zeb8rO4fAyXCiWwMMTxe5ymBYUwtBTalreOQiSO4Q7o=; b=AZPm0XqTPsIor9g2gVwjsC5wm9A04xQ3gM9KRveGZfefY2yYU/3W2lRPTMRU4PZunc ygdOxR2f5SyW7cKOLr59Mk0O3OdY1OhWe15yhfOmOyUD3gqzT/Pl3LIIUyGkEefZjvz3 CfQ9ok/5jQB7e+Q9JlF8DOaQDLHk2cWCTXw8Q8p4/F6XVT3no9J1ytcsmZvccBygMwLR /wHb6OWKxVhtAKnKuHsqRneKp/6sp+QAehO0W+TIZ27zVFO/pQx1aMzQLYzOqDXEs71S rHxsXMHEsBLFFSUf1JMq8CQyjPsQbNyjm9nhQw10Lizy8lCQB86YKc9m2vaI2HovQ30v kWBQ== X-Gm-Message-State: APjAAAUGhqkDg2NzCjZzSgzPKwSS09R01vSmp0yr2zsTHeXwjla572WN 61sARKpj/z7ZCSy2GLcBMurFeZhx1fnYsw== X-Google-Smtp-Source: APXvYqzpzFMVxBFmx7q8yYwEjGtfR4aEJAPI0qCC+jLNwnnnMIt71/6+twrteL7WTknyOlQL3U3ZuA== X-Received: by 2002:a05:6000:12c9:: with SMTP id l9mr8715653wrx.163.1569410889193; Wed, 25 Sep 2019 04:28:09 -0700 (PDT) Received: from [172.22.0.30] ([82.117.251.135]) by smtp.gmail.com with ESMTPSA id c6sm5369038wrb.60.2019.09.25.04.28.07 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 25 Sep 2019 04:28:08 -0700 (PDT) Date: Wed, 25 Sep 2019 14:28:00 +0300 From: Gleb Naumenko To: Bitcoin-Dev Message-ID: <8914e269-e922-43f4-8846-9fb21a8044f3@Spark> In-Reply-To: References: X-Readdle-Message-ID: 8914e269-e922-43f4-8846-9fb21a8044f3@Spark MIME-Version: 1.0 Content-Type: multipart/alternative; boundary="5d8b4f45_3a95f874_4055" 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: Wed, 25 Sep 2019 11:37:09 +0000 Subject: [bitcoin-dev] New BIP for p2p messages/state enabling reconciliation-based protocols (Erlay) 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: Wed, 25 Sep 2019 11:28:20 -0000 --5d8b4f45_3a95f874_4055 Content-Type: text/plain; charset="utf-8" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline We are opening for review a draft of the new BIP, which describes low-lev= el specifications for the reconciliation-based transaction announcement p= rotocol. https://github.com/naumenkogs/bips/blob/bip-reconcil/bip-reconcil.mediawi= ki Agreeing on this spec would enable integration of more bandwidth-efficien= t relay protocols, like Erlay (https://arxiv.org/abs/1905.10518). The draft has all the background necessary to understand the work, so ple= ase read and review. It introduces salted short transaction IDs (required to do reconciliation= efficiently) and demonstrates how to compute sketches based on these IDs= (including simple python scripts). It also introduces wtxid-based truncated transaction IDs (to trivially sa= ve significant fraction of the bandwidth). =46inally, it specifies all the messages to be used by an efficient recon= ciliation-based protocol, and new state variables required for the protoc= ol. Please note that, comparing to the Erlay paper, we decided to add extra r= ound, where 2 parties explicitly map 32-bit short IDs to 128-bit truncate= d IDs, because otherwise peers which take >1s to reconcile would cause tr= ansmitting duplicate transactions (extra bandwidth), and we cannot assume= <1s latency in Bitcoin, especially over Tor. According to my estimates, the bandwidth overhead due to the measure from= the BIP (extra communication round) is only extra 10% comparing to the o= riginal Erlay estimates. It is possible that we missed some of the state variables required to han= dle corner cases of the protocol, because the spec is based on my prototy= pe code, and it might evolve when we will be building an actual productio= n-ready implementation. Overall, I believe that this spec is ready for review. Even though this work does not require a fork, the change is quite signif= icant, and peer-review is critical for the system, so please take a look.= =46eel free to reach out for questions and comments here or directly ove= r email. =E2=80=93 gleb --5d8b4f45_3a95f874_4055 Content-Type: text/html; charset="utf-8" Content-Transfer-Encoding: quoted-printable Content-Disposition: inline
We are opening for review a draft of the new BIP, w= hich describes low-level specifications for the reconciliation-based tran= saction announcement protocol.
https://github.com/naumenkogs/bips/blo= b/bip-reconcil/bip-reconcil.mediawiki

Agreeing on this spec would enable integration of more bandwidth-efficien= t relay protocols, like Erlay (https://arxiv.org/abs/1905.10518).

The draft has all the background necessary to understand the work, so ple= ase read and review.
It introduces salted short transaction IDs (required to do reconciliation= efficiently) and demonstrates how to compute sketches based on these IDs= (including simple python scripts).
It also introduces wtxid-based truncated transaction IDs (to trivially sa= ve significant fraction of the bandwidth).
=46inally, it specifies all the messages to be used by an efficient recon= ciliation-based protocol, and new state variables required for the protoc= ol.

Please note that, comparing to the Erlay paper, we decided to add extra r= ound, where 2 parties explicitly map 32-bit short IDs to 128-bit truncate= d IDs, because otherwise peers which take >1s to reconcile would cause= transmitting duplicate transactions (extra bandwidth), and we cannot ass= ume <1s latency in Bitcoin, especially over Tor.
According to my estimates, the bandwidth overhead due to the measure from= the BIP (extra communication round) is only extra 10% comparing to the o= riginal Erlay estimates.

It is possible that we missed some of the state variables required to han= dle corner cases of the protocol, because the spec is based on my prototy= pe code, and it might evolve when we will be building an actual productio= n-ready implementation.

Overall, I believe that this spec is ready for review.

Even though this work does not require a fork, the change is quite signif= icant, and peer-review is critical for the system, so please take a look.= =46eel free to reach out for questions and comments here or directly ove= r email.

=E2=80=93 gleb
--5d8b4f45_3a95f874_4055--