summaryrefslogtreecommitdiff
path: root/02/5995242a5be4a5112cfe1c9429ee92d30785d3
blob: 2b3a8f170fea03773d4c6d02f6628cdf805e3064 (plain)
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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
Received: from sog-mx-1.v43.ch3.sourceforge.com ([172.29.43.191]
	helo=mx.sourceforge.net)
	by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
	(envelope-from <pete@petertodd.org>) id 1Y2iS7-0004Cj-Di
	for bitcoin-development@lists.sourceforge.net;
	Sun, 21 Dec 2014 15:29:51 +0000
Received-SPF: pass (sog-mx-1.v43.ch3.sourceforge.com: domain of petertodd.org
	designates 62.13.148.93 as permitted sender)
	client-ip=62.13.148.93; envelope-from=pete@petertodd.org;
	helo=outmail148093.authsmtp.net; 
Received: from outmail148093.authsmtp.net ([62.13.148.93])
	by sog-mx-1.v43.ch3.sourceforge.com with esmtp (Exim 4.76)
	id 1Y2iS6-0008ME-4R for bitcoin-development@lists.sourceforge.net;
	Sun, 21 Dec 2014 15:29:51 +0000
Received: from mail-c237.authsmtp.com (mail-c237.authsmtp.com [62.13.128.237])
	by punt14.authsmtp.com (8.14.2/8.14.2) with ESMTP id sBLFTfmW072635; 
	Sun, 21 Dec 2014 15:29:41 GMT
Received: from savin.petertodd.org (75-119-251-161.dsl.teksavvy.com
	[75.119.251.161]) (authenticated bits=128)
	by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id sBLFTbLH095137
	(version=TLSv1/SSLv3 cipher=DHE-RSA-AES128-SHA bits=128 verify=NO);
	Sun, 21 Dec 2014 15:29:39 GMT
Date: Sun, 21 Dec 2014 10:29:37 -0500
From: Peter Todd <pete@petertodd.org>
To: Adam Back <adam@cypherspace.org>
Message-ID: <20141221152936.GB3927@savin.petertodd.org>
References: <20141212090551.GA8259@muck>
	<20141220144800.GA26284@savin.petertodd.org>
	<CALqxMTHC0Rhotei4B1civoc_9NF5M+tw-qmE46EmHSadCrmScQ@mail.gmail.com>
MIME-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha256;
	protocol="application/pgp-signature"; boundary="v9Ux+11Zm5mwPlX6"
Content-Disposition: inline
In-Reply-To: <CALqxMTHC0Rhotei4B1civoc_9NF5M+tw-qmE46EmHSadCrmScQ@mail.gmail.com>
User-Agent: Mutt/1.5.21 (2010-09-15)
X-Server-Quench: 2e1fb398-8926-11e4-9f74-002590a135d3
X-AuthReport-Spam: If SPAM / abuse - report it at:
	http://www.authsmtp.com/abuse
X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR
	aAdMdAMUHFAXAgsB AmIbWlFeUlR7XWM7 bA9PbARUfEhLXhtr
	VklWR1pVCwQmQm59 cHpMLmFyfgBHe3k+ ZEdhWnYVXhF7IxR+
	S0ZJHWQEY3phaTUb TUkOcAdJcANIexZF O1F8UScOLwdSbGoL
	NQ4vNDcwO3BTJTpY RgYVKF8UXXNDIj4x DwoPGTwzHEoDXCUy
	N1QsJ0IDEUsXUA0K K1wmVxcfPVoqFwda HkpEHC5eIREIQSZj
	JAVGXAskHSVZSDYU JQchKRtFGVQI
X-Authentic-SMTP: 61633532353630.1024:706
X-AuthFastPath: 0 (Was 255)
X-AuthSMTP-Origin: 75.119.251.161/587
X-AuthVirus-Status: No virus detected - but ensure you scan with your own
	anti-virus system.
X-Spam-Score: -1.5 (-)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
	See http://spamassassin.org/tag/ for more details.
	-1.5 SPF_CHECK_PASS SPF reports sender host as permitted sender for
	sender-domain
	-0.0 SPF_PASS               SPF: sender matches SPF record
X-Headers-End: 1Y2iS6-0008ME-4R
Cc: Bitcoin Dev <bitcoin-development@lists.sourceforge.net>
Subject: Re: [Bitcoin-development] The relationship between
 Proof-of-Publication and Anti-Replay Oracles
X-BeenThere: bitcoin-development@lists.sourceforge.net
X-Mailman-Version: 2.1.9
Precedence: list
List-Id: <bitcoin-development.lists.sourceforge.net>
List-Unsubscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=unsubscribe>
List-Archive: <http://sourceforge.net/mailarchive/forum.php?forum_name=bitcoin-development>
List-Post: <mailto:bitcoin-development@lists.sourceforge.net>
List-Help: <mailto:bitcoin-development-request@lists.sourceforge.net?subject=help>
List-Subscribe: <https://lists.sourceforge.net/lists/listinfo/bitcoin-development>,
	<mailto:bitcoin-development-request@lists.sourceforge.net?subject=subscribe>
X-List-Received-Date: Sun, 21 Dec 2014 15:29:51 -0000


--v9Ux+11Zm5mwPlX6
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Sun, Dec 21, 2014 at 10:01:37AM +0000, Adam Back wrote:
> On 20 December 2014 at 14:48, Peter Todd <pete@petertodd.org> wrote:
> > We need the following primitives operating on message m, pubkey p, and a
> > valid signature sig1 for m, p:
> >
> >     AntiReplaySign(m, p, sig1) -> sig2
> >     VerifyAntiReplaySig(m, p, sig2) -> True or False
> >
> > Additionally once AntiReplaySign() has been used once for a given pubkey
> > it is impossible to re-run the primitive on a different message m'. This
> > is of course impossible to implement with math alone, but we can
> > implement it with a trusted third party.
>=20
> Well while you cant prevent it you could render it insecure enabling
> miners to take funds.
>=20
> That could work via a one-show signature; normal ECDSA being address
> a=3DH(Q), public key Q=3DdG, R=3DkG, r=3DR.x, s=3D(H(m)+rd)/k, signature =
(r,s),
> verify: a=3D?H(Q) and sR=3D?H(m)G+rQ one-show being: a=3DH(Q,R), verify
> being: a=3D?H(Q,R) and sR=3D?H(m)G+rQ.  Now that is unsafe to double-spend
> by design as only that specific R is usable and as we know reusing R
> with different messages leaks the private key because: s=3D(H(m)+rd)/k
> and s'=3D(H(m')+rd)/k implies sk=3DH(m)+rd and s'k=3DH(m')+rd so
> k=3D(H(m)-H(m'))/(s'-s), and d=3D(sk-H(m))/r.

There's no need to get into the specifics of crypto math so early; you
can just as easily and only slightly less efficiently obtain the same
result with a few extensions to the Bitcoin scripting system to verify
ECDSA signatures directly.

The interesting question is how "risky" this actually is? Sybil attacks
are reasonably easy to pull off, and users have little incentive to
validate if 99% of the time everything works, so you don't want to
create a system where an actual attack will likely go undetected.
Talking about the low level details of how double-spend punishment is
actually detailed is just premature optimization.

As usual in Bitcoin, the hard part is *not* the math.

--=20
'peter'[:-1]@petertodd.org
000000000000000012f5511833a1304a72a754df8afef26f5712438bcc40826b

--v9Ux+11Zm5mwPlX6
Content-Type: application/pgp-signature; name="signature.asc"
Content-Description: Digital signature

-----BEGIN PGP SIGNATURE-----

iQGrBAEBCACVBQJUludcXhSAAAAAABUAQGJsb2NraGFzaEBiaXRjb2luLm9yZzAw
MDAwMDAwMDAwMDAwMDAxMmY1NTExODMzYTEzMDRhNzJhNzU0ZGY4YWZlZjI2ZjU3
MTI0MzhiY2M0MDgyNmIvFIAAAAAAFQARcGthLWFkZHJlc3NAZ251cGcub3JncGV0
ZUBwZXRlcnRvZC5vcmcACgkQJIFAPaXwkfsL9gf/bJRcONR8p8Dwc0MJ3E117NF2
7xavGPx9hxS4Pzf2u7ncuaOROnD+pTmk9BhA2zSZgtA2CCxz3BioC/uOG89nO/YL
tc/2gu4A3keWE7G/YgnJv/56hqRZal3lxhwj7ICYJOqcEYcZIwyedC9gg9RUCOFo
N+luGXdilMjzkhgqY1RK3O1oSIgpwdBtTX0KOvRuqWMCWr7x/GxwTRHX1kLI4G4r
ctPdNbt1aMShjfFH7+SYTAnj9gjqfwU1r5lM8iVeW+1qB0umgHXFm6AxnoODEUF/
TAmy9ozTn1VHURsWo6F2GKX8iMgscbInMP9vHSyowfVuA8xAq0ka/poNRO1wMw==
=zOZB
-----END PGP SIGNATURE-----

--v9Ux+11Zm5mwPlX6--