1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
|
Return-Path: <roconnor@blockstream.io>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
[172.17.192.35])
by mail.linuxfoundation.org (Postfix) with ESMTPS id AC75EA48
for <bitcoin-dev@lists.linuxfoundation.org>;
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 <bitcoin-dev@lists.linuxfoundation.org>;
Fri, 28 Apr 2017 20:53:26 +0000 (UTC)
Received: by mail-ua0-f173.google.com with SMTP id q26so7344171uaa.1
for <bitcoin-dev@lists.linuxfoundation.org>;
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" <roconnor@blockstream.io>
Date: Fri, 28 Apr 2017 16:53:05 -0400
Message-ID: <CAMZUoK=FtNjvfO3uBHFy-fO_hqum+UtpJVQ7o5aq=6hYrpn_0A@mail.gmail.com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
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 <bitcoin-dev.lists.linuxfoundation.org>
List-Unsubscribe: <https://lists.linuxfoundation.org/mailman/options/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=unsubscribe>
List-Archive: <http://lists.linuxfoundation.org/pipermail/bitcoin-dev/>
List-Post: <mailto:bitcoin-dev@lists.linuxfoundation.org>
List-Help: <mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=help>
List-Subscribe: <https://lists.linuxfoundation.org/mailman/listinfo/bitcoin-dev>,
<mailto:bitcoin-dev-request@lists.linuxfoundation.org?subject=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
<https://github.com/bitcoin/bips/blob/959fecc15bdad070afa63455468b1dba54655fa6/bip-0134.mediawiki>
now supports SIGHASH_SINGLE and friends. However, this support seems to
reintroduce some quadratic hashing behavior because it calls
<https://github.com/zander/bitcoinclassic/blob/9c688c6d3866890f16a36aaea453e8bdd43c1266/src/script/interpreter.cpp#L1186>SerializePartialTransactionv4
per non-SIGHASH_ALL input
<https://github.com/bitcoinclassic/bitcoinclassic/blob/9c688c6d3866890f16a36aaea453e8bdd43c1266/src/script/interpreter.cpp#L1186>.
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
<div dir=3D"ltr"><div><div>I noticed that the <a href=3D"https://github.com=
/bitcoin/bips/blob/959fecc15bdad070afa63455468b1dba54655fa6/bip-0134.mediaw=
iki" target=3D"_blank">the latest BIP 134</a> now supports SIGHASH_SINGLE a=
nd friends.=C2=A0 However, this support seems to reintroduce some quadratic=
hashing behavior because it <a href=3D"https://github.com/zander/bitcoincl=
assic/blob/9c688c6d3866890f16a36aaea453e8bdd43c1266/src/script/interpreter.=
cpp#L1186" target=3D"_blank">calls </a><span class=3D"m_4115989833037037540=
gmail-m_-6187962426531096253m_-301435513863200495gmail-pl-c1"><a href=3D"ht=
tps://github.com/bitcoinclassic/bitcoinclassic/blob/9c688c6d3866890f16a36aa=
ea453e8bdd43c1266/src/script/interpreter.cpp#L1186" target=3D"_blank">Seria=
lizePartialTransactionv4 per non-SIGHASH_ALL input</a></span>.=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.</div></div></div>
--f403043ed1bccd0c53054e404332--
|
