path: root/a6/1da4fd54c4a4ca4e22f0ddff76f7f9c11508d9

Return-Path: <hearn@vinumeris.com>
Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org
	[172.17.192.35])
	by mail.linuxfoundation.org (Postfix) with ESMTPS id 90879409
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 20 Jul 2015 14:40:38 +0000 (UTC)
X-Greylist: whitelisted by SQLgrey-1.7.6
Received: from mail-ie0-f176.google.com (mail-ie0-f176.google.com
	[209.85.223.176])
	by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 2311CEE
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 20 Jul 2015 14:40:37 +0000 (UTC)
Received: by iehx8 with SMTP id x8so38915836ieh.3
	for <bitcoin-dev@lists.linuxfoundation.org>;
	Mon, 20 Jul 2015 07:40:36 -0700 (PDT)
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=vinumeris.com; s=google;
	h=mime-version:date:message-id:subject:from:to:cc:content-type;
	bh=2b23ZojHlo4G//pW0rNY+p2ugMb9Qaz/VVdZXKFxTP0=;
	b=RNP1qhvLptpVejEo4gGwMRkOksNEjNBPdJrQLNO9LjLuMgS5ONo5JDuGEeSyd2nIZA
	MDQiT3WVuuIw2cB0FTU2a/nYFmTYX3H99DNBCRKROOYGZzJQLPOBZm9D1s3LOggmTzQ2
	DKibl+uCB/kooDocrltcqcsKSH4Y4XPil3Fnc=
X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed;
	d=1e100.net; s=20130820;
	h=x-gm-message-state:mime-version:date:message-id:subject:from:to:cc
	:content-type;
	bh=2b23ZojHlo4G//pW0rNY+p2ugMb9Qaz/VVdZXKFxTP0=;
	b=FFTzycjVckqsLRMRTE3pEn3UM3/CGWtMA2sOMG8b7Bjg6bUJZMtTKhToMRlsA2BgJ7
	S2HRENKHPxdDSttFhJeRV02sbizix7TuLxb0I+Cq14h4zxMepYrBNjxffbuXYoVkt+/i
	loaKkl+8Hqvrt9UpB4/xZlTpicZgz/FCG0x08hX9+C76nX/eoNk1VBVdJKgyE0qOjKEz
	9R6Z9B4Kcbn7Wehrmn1e6pEo0ZrY8wIMeTKWpmIgbcEIv0DLRc56WWxbrzooGYmY+Qit
	eHCc0HqJj3A68gjeev5JgMe5NjGKhwztPrQCrXovTdQ1U54MPpE+bUcVpTk/AxeYKLKz
	UY4g==
X-Gm-Message-State: ALoCoQl42fP0m1f5Ju4nApt0N7aZt97E0Qa2SLJaqgat8OKw75kirskIxFDztmm5d2JQd6RP7FZH
MIME-Version: 1.0
X-Received: by 10.50.44.8 with SMTP id a8mr15418024igm.70.1437403236503; Mon,
	20 Jul 2015 07:40:36 -0700 (PDT)
Received: by 10.50.108.111 with HTTP; Mon, 20 Jul 2015 07:40:36 -0700 (PDT)
Date: Mon, 20 Jul 2015 16:40:36 +0200
Message-ID: <CA+w+GKRRfT=8xALsVMqEUAZWzd87Lf4HqFPuDigatY+nHzafQQ@mail.gmail.com>
From: Mike Hearn <hearn@vinumeris.com>
To: Thomas Voegtlin <thomasv@electrum.org>
Content-Type: multipart/alternative; boundary=e89a8f6471354fb32f051b4f8539
X-Spam-Status: No, score=-2.7 required=5.0 tests=BAYES_00,DKIM_SIGNED,
	DKIM_VALID,DKIM_VALID_AU,HTML_MESSAGE,RCVD_IN_DNSWL_LOW autolearn=ham
	version=3.3.1
X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on
	smtp1.linux-foundation.org
Cc: bitcoin-dev@lists.linuxfoundation.org
Subject: [bitcoin-dev] QR code alternatives (was: Proposal: extend bip70
	with OpenAlias)
X-BeenThere: bitcoin-dev@lists.linuxfoundation.org
X-Mailman-Version: 2.1.12
Precedence: list
List-Id: Bitcoin Development 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: Mon, 20 Jul 2015 14:40:38 -0000

--e89a8f6471354fb32f051b4f8539
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

Hey Thomas,

Here are some thoughts on a third way we can tackle our BIP 70 usability
problem sans servers: by finding an upgrade to QR codes that give us more
space and then optimising the hell out of BIP70 to make it fit.

*Better QR codes*

Let's start with this paper, High Capacity Colored Two Dimensional Codes
<http://proceedings2010.imcsit.org/pliks/79.pdf>. It develops an upgrade to
standard QR codes that extend them with the use of colour. The resulting
codes have ~4x the capacity but similar levels of scanning robustness.

This paper is also interesting: DualCodes
<https://books.google.at/books?id=3DO5a6BQAAQBAJ&pg=3DPA25&lpg=3DPA25&dq=3D=
%22DualCodes:+Backward+Compatible+Multi-layer+2D-Barcodes%22&source=3Dbl&ot=
s=3Dql_G8iyXXi&sig=3D9-VwhFLbkfgh2Fi0tdM3AWOyajA&hl=3Den&sa=3DX&redir_esc=
=3Dy#v=3Donepage&q=3D%22DualCodes%3A%20Backward%20Compatible%20Multi-layer%=
202D-Barcodes%22&f=3Dfalse>

It works by overlaying one QR code on top of another using shades of grey.
The resulting code is still scannable by older applications (backwards
compatibility!) but an enhanced reader can also extract the second code.
They explicitly mention digital signatures as a possible use case.

In both cases the code does not appear to be available but the same
approach was used: extend libqrcode for creation and ZXing for decoding
(Android). We could ask the authors and see if they're willing to open
source their work.

BIP 70 has the potential to add many features. But most of them, even the
extensions currently proposed only as ideas, can be expressed with
relatively few bytes.

So with a 4x boost in capacity, or a 2x boost with backwards compat, what
could we do?

*Optimised BIP70*

If we define our own certificate formats and by implication our own CAs,
then we can easily make a certificate be 32 bytes for the ECC
signature+length of the asserted textual identity, e.g. email address.

Can we go smaller? Arguably, yes. 32 bytes for a signature is for Really
Strong Security=E2=84=A2 (a 256 bit curve), which gives 128 bits of securit=
y. If we
are willing to accept that a strong adversary could eventually forge a
certificate, we can drop down to a weaker curve, like a 128 bit cure with
64 bits of security. This is well within reach of, say, an academic team
but would still pose a significant hurdle for run of the mill payment
fraudsters. If these short CA keys expired frequently, like once a month,
the system could still be secure enough.

As we are defining our own PKI we can make CA keys expire however
frequently we like, up to the expiry period of the BIP70 request itself.
Thus certificates that expire monthly is not an issue if the wallet has a
way to automatically refresh the certificate by using a longer term
stronger credential that it keeps around on disk.

If we accept a single payment address i.e. no clever tricks around merge
avoidance, such a QR code could look like this:

bitcoin:1aBcD1234....?x=3Dserialized_payment_request

However this requires text mode and wastes bytes at the front for the URI
type.

If we're willing to accept QR codes that can't be read by a standalone app
and which requires an embedded reader, then we can just scrap the legacy
and serialise a binary BIP70 request directly into the QR code. Andreas'
wallet, for example, can already handle this because it has an embedded QR
reader. I don't know what the situation on iOS is like.

If we were to use the DualCodes system we could define the primary QR code
as being an unsigned payment request, and the second layer as being the
signature/pki data.

*Getting response data back to the recipient*

One reason to have a store/forward network is the "forward" part: we don't
only want to host a static PaymentRequest, but also receive a private
response e.g. for the memo field, or to implement the well known "Stealth
Address" / ECDH in the payment protocol proposals:

https://medium.com/@octskyward/ecdh-in-the-payment-protocol-cb2f81962c1b

Stealth addresses try and (ab)use the block chain as a store/forward layer
and break SPV in the process as well as wasting lots of resources. ECDH in
BIP70 avoids those issues but at the cost of requiring a separate
store-and-forward network with some notion of account privacy.

These ideas come with another steep price: restoring a wallet from seed
words is no longer possible. You must have the extra random data to
calculate the private keys for money sent to you :(  If you lose the extra
data you lose the money. It can be fixed but only by having wallets
regularly sweep the sent money to keys derived from the BIP32 seed, meaning
privacy-hurting merging and extra traffic.

I don't know of any way to solve this except by using some servers,
somewhere, that store the Payment messages for people: potentially for a
long period of time. If we have such servers, then having them host BIP70
requests is not a big extra requirement.

I have imagined this being a p2p-ish network of HTTPS servers that accept
POSTs and GETs. But if we are thinking about alternatives, it could also be
a separate service of the existing Bitcoin P2P network. That's what
OP_RETURN (ab)use effectively does. But as these messages don't really have
to be kept forever, a different system could be used: Payment messages
could be broadcast along with their transactions and stored at every node,
waiting for download. But unlike regular transactions, they are not stored
forever in a block chain. They are just written to disk and eventually
erased, perhaps, ordered in a mempool like way where more fee attached =3D=
=3D
stored for longer, even though the nodes storing the data aren't actually
receiving the fee.

A signature over the Payment metadata using the same output keys as the
transaction would bind them together for the purposes of broadcast, but
doesn't need to be stored after that.

As the data storage is just a helpful service but not fundamentally
required, nodes could shard themselves by announcing in their addr messages
that they only store Payment metadata for e.g. the half which have a hash
starting with a one bit. And when outputs are seen being spent, the
associated Payment metadata can be erased too, as by then it's fair to
assume that the users wallet has downloaded the metadata and no longer
cares about it.

Of course you have then all the regular DoS issues. But any P2P network
that stores data on the behalf of others has these.

--e89a8f6471354fb32f051b4f8539
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr"><div class=3D"gmail_extra">Hey Thomas,</div><div class=3D"=
gmail_extra"><br></div><div class=3D"gmail_extra">Here are some thoughts on=
 a third way we can tackle our BIP 70 usability problem sans servers: by fi=
nding an upgrade to QR codes that give us more space and then optimising th=
e hell out of BIP70 to make it fit.</div><div class=3D"gmail_extra"><br></d=
iv><div class=3D"gmail_extra"><b><font size=3D"4">Better QR codes</font></b=
></div><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">Let&=
#39;s start with this paper, <a href=3D"http://proceedings2010.imcsit.org/p=
liks/79.pdf">High Capacity Colored Two Dimensional Codes</a>.=C2=A0It devel=
ops an upgrade to standard QR codes that extend them with the use of colour=
. The resulting codes have ~4x the capacity but similar levels of scanning =
robustness.=C2=A0</div><div class=3D"gmail_extra"><br></div><div class=3D"g=
mail_extra">This paper is also interesting: <a href=3D"https://books.google=
.at/books?id=3DO5a6BQAAQBAJ&amp;pg=3DPA25&amp;lpg=3DPA25&amp;dq=3D%22DualCo=
des:+Backward+Compatible+Multi-layer+2D-Barcodes%22&amp;source=3Dbl&amp;ots=
=3Dql_G8iyXXi&amp;sig=3D9-VwhFLbkfgh2Fi0tdM3AWOyajA&amp;hl=3Den&amp;sa=3DX&=
amp;redir_esc=3Dy#v=3Donepage&amp;q=3D%22DualCodes%3A%20Backward%20Compatib=
le%20Multi-layer%202D-Barcodes%22&amp;f=3Dfalse">DualCodes</a></div><div cl=
ass=3D"gmail_extra"><br></div><div class=3D"gmail_extra">It works by overla=
ying one QR code on top of another using shades of grey. The resulting code=
 is still scannable by older applications (backwards compatibility!) but an=
 enhanced reader can also extract the second code. They explicitly mention =
digital signatures as a possible use case.</div><div class=3D"gmail_extra">=
<br></div><div class=3D"gmail_extra">In both cases the code does not appear=
 to be available but the same approach was used: extend libqrcode for creat=
ion and ZXing for decoding (Android). We could ask the authors and see if t=
hey&#39;re willing to open source their work.</div><div class=3D"gmail_extr=
a"><br></div><div class=3D"gmail_extra">BIP 70 has the potential to add man=
y features. But most of them, even the extensions currently proposed only a=
s ideas, can be expressed with relatively few bytes.</div><div class=3D"gma=
il_extra"><br></div><div class=3D"gmail_extra">So with a 4x boost in capaci=
ty, or a 2x boost with backwards compat, what could we do?</div><div class=
=3D"gmail_extra"><br></div><div class=3D"gmail_extra"><b><font size=3D"4">O=
ptimised BIP70</font></b></div><div class=3D"gmail_extra"><br></div><div cl=
ass=3D"gmail_extra">If we define our own certificate formats and by implica=
tion our own CAs, then we can easily make a certificate be 32 bytes for the=
 ECC signature+length of the asserted textual identity, e.g. email address.=
=C2=A0</div><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra"=
>Can we go smaller? Arguably, yes. 32 bytes for a signature is for Really S=
trong Security=E2=84=A2 (a 256 bit curve), which gives 128 bits of security=
. If we are willing to accept that a strong adversary could eventually forg=
e a certificate, we can drop down to a weaker curve, like a 128 bit cure wi=
th 64 bits of security. This is well within reach of, say, an academic team=
 but would still pose a significant hurdle for run of the mill payment frau=
dsters. If these short CA keys expired frequently, like once a month, the s=
ystem could still be secure enough.</div><div class=3D"gmail_extra"><br></d=
iv><div class=3D"gmail_extra">As we are defining our own PKI we can make CA=
 keys expire however frequently we like, up to the expiry period of the BIP=
70 request itself. Thus certificates that expire monthly is not an issue if=
 the wallet has a way to automatically refresh the certificate by using a l=
onger term stronger credential that it keeps around on disk.</div><div clas=
s=3D"gmail_extra"><br></div><div class=3D"gmail_extra">If we accept a singl=
e payment address i.e. no clever tricks around merge avoidance, such a QR c=
ode could look like this:</div><div class=3D"gmail_extra"><br></div><div cl=
ass=3D"gmail_extra">bitcoin:1aBcD1234....?x=3Dserialized_payment_request</d=
iv><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">However =
this requires text mode and wastes bytes at the front for the URI type.</di=
v><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">If we&#39=
;re willing to accept QR codes that can&#39;t be read by a standalone app a=
nd which requires an embedded reader, then we can just scrap the legacy and=
 serialise a binary BIP70 request directly into the QR code. Andreas&#39; w=
allet, for example, can already handle this because it has an embedded QR r=
eader. I don&#39;t know what the situation on iOS is like.</div><div class=
=3D"gmail_extra"><br></div><div class=3D"gmail_extra">If we were to use the=
 DualCodes system we could define the primary QR code as being an unsigned =
payment request, and the second layer as being the signature/pki data.</div=
><div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra"><b><font s=
ize=3D"4">Getting response data back to the recipient</font></b></div><div =
class=3D"gmail_extra"><b><br></b></div><div class=3D"gmail_extra">One reaso=
n to have a store/forward network is the &quot;forward&quot; part: we don&#=
39;t only want to host a static PaymentRequest, but also receive a private =
response e.g. for the memo field, or to implement the well known &quot;Stea=
lth Address&quot; / ECDH in the payment protocol proposals:</div><div class=
=3D"gmail_extra"><br></div><div class=3D"gmail_extra"><a href=3D"https://me=
dium.com/@octskyward/ecdh-in-the-payment-protocol-cb2f81962c1b">https://med=
ium.com/@octskyward/ecdh-in-the-payment-protocol-cb2f81962c1b</a><br></div>=
<div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">Stealth add=
resses try and (ab)use the block chain as a store/forward layer and break S=
PV in the process as well as wasting lots of resources. ECDH in BIP70 avoid=
s those issues but at the cost of requiring a separate store-and-forward ne=
twork with some notion of account privacy.</div><div class=3D"gmail_extra">=
<br></div><div class=3D"gmail_extra">These ideas come with another steep pr=
ice: restoring a wallet from seed words is no longer possible. You must hav=
e the extra random data to calculate the private keys for money sent to you=
 :( =C2=A0If you lose the extra data you lose the money. It can be fixed bu=
t only by having wallets regularly sweep the sent money to keys derived fro=
m the BIP32 seed, meaning privacy-hurting merging and extra traffic.</div><=
div class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">I don&#39;t =
know of any way to solve this except by using some servers, somewhere, that=
 store the Payment messages for people: potentially for a long period of ti=
me. If we have such servers, then having them host BIP70 requests is not a =
big extra requirement.</div><div class=3D"gmail_extra"><br></div><div class=
=3D"gmail_extra">I have imagined this being a p2p-ish network of HTTPS serv=
ers that accept POSTs and GETs. But if we are thinking about alternatives, =
it could also be a separate service of the existing Bitcoin P2P network. Th=
at&#39;s what OP_RETURN (ab)use effectively does. But as these messages don=
&#39;t really have to be kept forever, a different system could be used: Pa=
yment messages could be broadcast along with their transactions and stored =
at every node, waiting for download. But unlike regular transactions, they =
are not stored forever in a block chain. They are just written to disk and =
eventually erased, perhaps, ordered in a mempool like way where more fee at=
tached =3D=3D stored for longer, even though the nodes storing the data are=
n&#39;t actually receiving the fee.</div><div class=3D"gmail_extra"><br></d=
iv><div class=3D"gmail_extra">A signature over the Payment metadata using t=
he same output keys as the transaction would bind them together for the pur=
poses of broadcast, but doesn&#39;t need to be stored after that.</div><div=
 class=3D"gmail_extra"><br></div><div class=3D"gmail_extra">As the data sto=
rage is just a helpful service but not fundamentally required, nodes could =
shard themselves by announcing in their addr messages that they only store =
Payment metadata for e.g. the half which have a hash starting with a one bi=
t. And when outputs are seen being spent, the associated Payment metadata c=
an be erased too, as by then it&#39;s fair to assume that the users wallet =
has downloaded the metadata and no longer cares about it.</div><div class=
=3D"gmail_extra"><br></div><div class=3D"gmail_extra">Of course you have th=
en all the regular DoS issues. But any P2P network that stores data on the =
behalf of others has these.</div></div>

--e89a8f6471354fb32f051b4f8539--