Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id AC75EA48 for ; Fri, 28 Apr 2017 20:53:27 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-ua0-f173.google.com (mail-ua0-f173.google.com [209.85.217.173]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 1A4B2189 for ; Fri, 28 Apr 2017 20:53:26 +0000 (UTC) Received: by mail-ua0-f173.google.com with SMTP id q26so7344171uaa.1 for ; Fri, 28 Apr 2017 13:53:26 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=blockstream-io.20150623.gappssmtp.com; s=20150623; h=mime-version:from:date:message-id:subject:to; bh=vwKtycVukoqc1NKeXYugXwnXvlVDOpK/ROMb/76f9Pw=; b=OoeHZArkXMjhS5w5lDPglHsu+TJ6K7k0m4Pu77ovieNTk9VyIOB/dxwYTq0hUng2F/ 8AsS+8Svx5sN91kt4WUBufY1wgja4BMH/XxeMFAqc4mV9aY+Gf/mJ3lyQ7iHtwvna376 INhy5yE/k8DshFofWjfyMicppjN+yGzADYxoFIpSlGVG/Lyam25DRpWypQUziFrUxx99 IMWJku6B6FuNoVGFceT/xmiwuYHok6kdwsOroaQivapN67MEWV0Ym2A1rhjmf5dT/rB9 zgMzHBSXG9ZecXa91FWEjZDxNPH8iaRZkEWzunGx8n3WXeQHSyImMfajUWfmAn+G73aE T0RA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to; bh=vwKtycVukoqc1NKeXYugXwnXvlVDOpK/ROMb/76f9Pw=; b=EwgQ8adZitGKWF2kedwe/RzPtMGJH5M8aViRdiqDMTWiNleOsBG40TrJJt54UmW1HF 4fGCEwIE3R8GBOJ1r4ByjpEBJ0pJeuXls7oDZMOMuPh69PgAxeOzlsnl3X7P7Itz3LXr BdbFzPFo1rdkr8ud66q3gc1sdcqQLyyC+WMoaq8CAi8h55iXrS7ofZ1LCSbPAf8CbBiF 7cy5vJFo+WsppI0r6mZtFGogvSnDqW3z2LtgV60QeP9kSJXKHlcI7k+KMhPOralPneON B+1iMylYbW1UZPFi6u8qUtdnbQFyLeyWw0EF/Zp8XatjKFUC1shHyMg0xd0kMfYV6bGZ 7z+w== X-Gm-Message-State: AN3rC/5DjKyUl+ebSUSSl8lIEj3Ygmx/mwEeD7TVeWk+YraxzWcNXrub sBnh1kgpWO0jpbCXlSvb49TSKo7FwxoZHgg= X-Received: by 10.159.60.38 with SMTP id u38mr7272124uah.152.1493412805924; Fri, 28 Apr 2017 13:53:25 -0700 (PDT) MIME-Version: 1.0 Received: by 10.176.81.48 with HTTP; Fri, 28 Apr 2017 13:53:05 -0700 (PDT) From: "Russell O'Connor" Date: Fri, 28 Apr 2017 16:53:05 -0400 Message-ID: To: Bitcoin Protocol Discussion Content-Type: multipart/alternative; boundary=f403043ed1bccd0c53054e404332 X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, 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 Subject: [bitcoin-dev] Quadratic Hashing in BIP 134 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: Fri, 28 Apr 2017 20:53:27 -0000 --f403043ed1bccd0c53054e404332 Content-Type: text/plain; charset=UTF-8 I noticed that the the latest BIP 134 now supports SIGHASH_SINGLE and friends. However, this support seems to reintroduce some quadratic hashing behavior because it calls SerializePartialTransactionv4 per non-SIGHASH_ALL input . In particular, if each input in a transaction has one SIGHASH_SINGLE CHECKSIG operation then the total amount of hashing done for the transaction will be quadratic in the number of inputs. While amount of hashing is not as severe as with the SIGHASH_ALL case, the amount of hashing done is still non-linear. --f403043ed1bccd0c53054e404332 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
I noticed that the the latest BIP 134 now supports SIGHASH_SINGLE a= nd friends.=C2=A0 However, this support seems to reintroduce some quadratic= hashing behavior because it calls Seria= lizePartialTransactionv4 per non-SIGHASH_ALL input.=C2=A0 In particular, if each input in a transaction has one SIGHASH_SINGLE CHECK= SIG operation then=20 the total amount of hashing done for the transaction will be quadratic=20 in the number of inputs.=C2=A0 While amount of hashing is not as severe=20 as with the SIGHASH_ALL case, the amount of hashing done is still=20 non-linear.
--f403043ed1bccd0c53054e404332--