path: root/b9/652775a89f3bac5d068c671129f34554957d15

Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192]
	helo=mx.sourceforge.net)
	by sfs-ml-3.v29.ch3.sourceforge.com with esmtp (Exim 4.76)
	(envelope-from <matthew@roberts.pm>) id 1Z3fga-0007xa-2Y
	for bitcoin-development@lists.sourceforge.net;
	Sat, 13 Jun 2015 07:17:00 +0000
X-ACL-Warn: 
Received: from mail-vn0-f46.google.com ([209.85.216.46])
	by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128)
	(Exim 4.76) id 1Z3fgX-0006z9-UJ
	for bitcoin-development@lists.sourceforge.net;
	Sat, 13 Jun 2015 07:17:00 +0000
Received: by vnbf7 with SMTP id f7so9045850vnb.13
	for <bitcoin-development@lists.sourceforge.net>;
	Sat, 13 Jun 2015 00:16:52 -0700 (PDT)
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
	:content-type;
	bh=k/QGTv3UpgfplHonApqEkzvKO/hci7jofCIHM1Ro2oI=;
	b=mwiqYpZjWiif++ORRY/F8i6OkgD74c1HnL5bEeaHcTCnPli2Cx8AnaSKGLvtYiuTOR
	pkZq2bHz15d2T1cRdVWl7I9wBK9juzGkTLUy0Wuk3GDlUF2/EWlC3nosbfAWAehXhnQM
	P7uV8Myp6sLqjq7FkqrEM8beCGPkxhZ3zD27GrtIwLeBd/xLriH1v54hWil3gHqsCHL4
	odns1TOAl+pm6X1bqT64ICT/sxFWxDo+mvEgU7+RgWrNtVqnH9nfQw55+tPrPaGcRWe6
	h6uosDN80EhRMjz1lbAjVI9RSeZWNXqwDwbMZ5h0Qbscj2odMTeTV69DpctDfWbOM4PP
	4CqA==
X-Gm-Message-State: ALoCoQlyrDzPe1euoe9b3JRDrfnHEvGeXkD5iLdSKrGDj0up2gE+Nx0gN05bH5N7K7cmlPolCDp/
MIME-Version: 1.0
X-Received: by 10.52.230.2 with SMTP id su2mr31312347vdc.55.1434179812475;
	Sat, 13 Jun 2015 00:16:52 -0700 (PDT)
Received: by 10.31.191.205 with HTTP; Sat, 13 Jun 2015 00:16:52 -0700 (PDT)
X-Originating-IP: [121.216.12.250]
Date: Sat, 13 Jun 2015 17:16:52 +1000
Message-ID: <CAAEDBiEZ9CrgFwg10BL_f+sv2mi_sZD_e5NLZ75nCg3gXf57Bg@mail.gmail.com>
From: Matthew Roberts <matthew@roberts.pm>
To: bitcoin-development@lists.sourceforge.net
Content-Type: multipart/alternative; boundary=001a11343f28445e3a05186102b4
X-Spam-Score: 1.0 (+)
X-Spam-Report: Spam Filtering performed by mx.sourceforge.net.
	See http://spamassassin.org/tag/ for more details.
	1.0 HTML_MESSAGE           BODY: HTML included in message
X-Headers-End: 1Z3fgX-0006z9-UJ
Subject: [Bitcoin-development] The timechain: an idea to solve TX
 malleability in smart contract protocols with minimal involvement and
 without requiring a fork.
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: Sat, 13 Jun 2015 07:17:00 -0000

--001a11343f28445e3a05186102b4
Content-Type: text/plain; charset=UTF-8

I've been tossing around an idea in my head that involves time-locked
encryption [0] and I wondered what the devs here think about it. In a
nutshell: the timechain is a serial chain of time-lock encrypted GPG keys
at N minute intervals (meaning that it requires N minutes to decrypt a
single link / key in the chain and each link must be fully decrypted before
decryption can start on the next link.) For those not aware of how
time-lock encryption works it goes something like this:

1. Choose some random, unique text - this is the initialisation vector or
IV.

2. Hash that text -> output.

3. Hash the output -> output.

4. Hash the output -> output.

5. ...

6. Process is repeated for N minutes.

7. Result is then used to generate encryption keys and the public key can
be used to time-lock encrypt an arbitrary number of plaintexts.

8. All intermediary results are discarded -- only the pub key is kept and
giving out the IV forces an individual to have to repeat the same amount of
work used to generate the encryption key.

What's interesting about this is that the keys can be generated in parallel
and then "stitched" together to form a single serial chain of keys. So
potentially, if a person had access to a GPU cluster then they could
generate a years worth of keys in only 5 minutes. Now imagine if one were
to stitch these keys together into a chain of keys at five minute intervals
(a structure I refer to as the "timechain"): you could use this structure
to encrypt ECDSA keys which could then be used in multi-signature contract
schemes as a 100% decentralized, trustless way to execute refunds in
contract protocols.

Unexpected benefit: time-lock encryption can be used to build unbreakable
DACs.

Peter Todd has already done work on using Bitcoin to incentivize the
decryption process of time-lock encryption [1] but what he may not be aware
of is how important this process is for the construction of DACs.

Imagine a true peer-to-peer cryptocurrency exchange [2] that time-lock
encrypts a chain of ECDSA keys using the timechain and then sets up
contracts to pay a small portion of their fees "into" the ECDSA keys.
Essentially the exchange has created a DAC that pays its participants to
decrypt itself. This is the incentive for the decryption. The reason for
the incentive is that another chain of keys can be generate at 5 minute
intervals which can be used in contract protocols in place of nTimeLocked
refund transactions (which are vulnerable to transaction malleability.)

Sample contract using the timechain:

3 of 4 multi-sig: Owner, Owner, Recipient, Timelock

Pay N coins to recipient sequentially (micropayment channel) before [time /
date], otherwise fall back on timelock decrypted refund key to give full
leverage back to owner. This is how smart contracts would work using the
timechain for refunds (instead of nTimeLock TXs.)

Using the DAC, it might also be possible to force participants to reveal
their solutions to the decryption of the timechain (otherwise the first
person who starts on the chain would receive all the fees which isn't very
fair.) One way to do this would be to use the public key for the fee ECDSA
key as the IV used to generate the next key on the chain. To spend the fees
would therefore require revealing the public key if the fees were paid to a
pay-to-pub-key-hash transaction.

A further precaution would be to generate the pay to fee transaction in
such a way that the amount needed to be redeemed before a certain
time-frame otherwise another transaction would burn the coins. (I haven't
worked out the full details for this yet but similar schemes have been used
successfully, for example in BitHalo [3] and the Lightning Network [4]
offers another potential solution.) Perhaps a custom blockchain or
sidechain could be used to award coins for successful (and timely
solutions) but this is a subject for future work.

In conclusion: I have described a simple way to solve the TX malleability
problem in smart contract protocols without requiring a fork or relying on
a third-party escrow services to hold keys. My solution doesn't require any
trust beyond the initial need for the timechain to be generated in a secure
environment and the solution remains secure so long as participants stick
to using future keys in the chain regardless of how far along the
decryption is.

Critique / flaws

Obviously the biggest flaw here is that the integrity of a timechain can't
be known before-hand but if a timechain were to be generated securely by a
reputable party, the biggest benefit of using it is that it basically runs
itself: it does not require any third-party to manage its functionality and
the entity which originally generated it can completely disappear without
interrupting service. This could, for instance - allow companies to create
entirely secure and reliable systems that couldn't be hacked as the
behaviour of a timechain is deterministic. I think this is a huge
improvement over existing systems which require third-parties to be
perpetually trusted with managing key-pairs on their web servers.

You could even use collateral as a way to incentivize the reliable
construction of the timechain by collecting collateral into a multi-sig
controlled by a number of neutral parties and only releasing the coins back
to the entity if the chain behaves as expected. I imagine some kind of
signed copy of a GPU cluster bill + proof of code executed would be
additional proof.

Anyway, that's the basic idea. Let me know what you think.


Sources:

[0] http://www.gwern.net/Self-decrypting%20files

[1]
https://www.mail-archive.com/bitcoin-development@lists.sourceforge.net/msg05547.html

[2] http://www.uptrenda.com/uptrenda.pdf

[3] https://bithalo.org/wp-content/uploads/2014/06/whitepaper_twosided.pdf

[4] https://lightning.network/lightning-network-paper-DRAFT-0.5.pdf

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

<div dir=3D"ltr"><p style=3D"margin-bottom:0cm">I&#39;ve been tossing aroun=
d an idea in my
head that involves time-locked encryption [0] and I wondered what the
devs here think about it. In a nutshell: the timechain is a serial
chain of time-lock encrypted GPG keys at N minute intervals (meaning
that it requires N minutes to decrypt a single link / key in the
chain and each link must be fully decrypted before decryption can start on
the next link.) For those not aware of how time-lock encryption works
it goes something like this:</p>
<br>
<p style=3D"margin-bottom:0cm">1. Choose some random, unique text -
this is the initialisation vector or IV.</p>
<p style=3D"margin-bottom:0cm">2. Hash that text -&gt; output.</p>
<p style=3D"margin-bottom:0cm">3. Hash the output -&gt; output.</p>
<p style=3D"margin-bottom:0cm">4. Hash the output -&gt; output.</p>
<p style=3D"margin-bottom:0cm">5. ...</p>
<p style=3D"margin-bottom:0cm">6. Process is repeated for N minutes.</p>
<p style=3D"margin-bottom:0cm">7. Result is then used to generate
encryption keys and the public key can be used to time-lock encrypt
an arbitrary number of plaintexts.</p>
<p style=3D"margin-bottom:0cm">8. All intermediary results are
discarded -- only the pub key is kept and giving out the IV forces an
individual to have to repeat the same amount of work used to generate
the encryption key.</p>

<p style=3D"margin-bottom:0cm">What&#39;s interesting about this is that
the keys can be generated in parallel and then &quot;stitched&quot;
together to form a single serial chain of keys. So potentially, if a
person had access to a GPU cluster then they could generate a years=20
worth of keys in only 5 minutes. Now imagine if one were to stitch these
 keys together into a chain of
keys at five minute intervals (a structure I refer to as the
&quot;timechain&quot;): you could use this structure to
encrypt ECDSA keys which could then be used in multi-signature
contract schemes as a 100% decentralized, trustless way to execute
refunds in contract protocols.</p>

<p style=3D"margin-bottom:0cm">Unexpected benefit: time-lock encryption can=
 be
used to build unbreakable DACs.</p>

<p style=3D"margin-bottom:0cm">Peter Todd has already done work on
using Bitcoin to incentivize the decryption process of time-lock
encryption [1] but what he may not be aware of is how important this
process is for the construction of DACs.</p>

<p style=3D"margin-bottom:0cm">Imagine a true peer-to-peer
cryptocurrency exchange [2] that time-lock encrypts a chain of ECDSA
keys using the timechain and then sets up contracts to pay a small
portion of their fees &quot;into&quot; the ECDSA keys. Essentially
the exchange has created a DAC that pays its participants to decrypt=20
itself. This is the incentive for the decryption. The reason for the
incentive is that another chain of keys can be generate at 5 minute
intervals which can be used in contract protocols in place of
nTimeLocked refund transactions (which are vulnerable to transaction
malleability.)</p>

<p style=3D"margin-bottom:0cm">Sample contract using the timechain:</p>
<p style=3D"margin-bottom:0cm">3 of 4 multi-sig: Owner, Owner,
Recipient, Timelock</p>
<p style=3D"margin-bottom:0cm">Pay N coins to recipient sequentially
(micropayment channel) before [time / date], otherwise fall back on
timelock decrypted refund key to give full leverage back to owner.
This is how smart contracts would work using the timechain for
refunds (instead of nTimeLock TXs.)</p>

<p style=3D"margin-bottom:0cm">Using the DAC, it might also be
possible to force participants to reveal their solutions to the
decryption of the timechain (otherwise the first person who starts on
the chain would receive all the fees which isn&#39;t very fair.) One way
to do this would be to use the public key for the fee ECDSA key as
the IV used to generate the next key on the chain. To spend the fees
would therefore require revealing the public key if the fees were
paid to a pay-to-pub-key-hash transaction.</p>

<p style=3D"margin-bottom:0cm">A further precaution would be to
generate the pay to fee transaction in such a way that the amount
needed to be redeemed before a certain time-frame otherwise another transac=
tion would burn the
coins. (I haven&#39;t worked out the full details for this yet but similar =
schemes
have been used successfully, for example in BitHalo [3] and the Lightning N=
etwork [4] offers another potential solution.) Perhaps a
custom blockchain or sidechain could be used to award coins for
successful (and timely solutions) but this is a subject for future
work.</p>

<p style=3D"margin-bottom:0cm">In conclusion: I have described a
simple way to solve the TX malleability problem in smart contract
protocols without requiring a fork or relying on a third-party escrow servi=
ces to hold keys. My solution doesn&#39;t require any trust beyond
the initial need for the timechain to be generated in a secure environment =
and the solution remains secure so long as participants stick
to using future keys in the chain regardless of how far along the
decryption is.</p>

<br><p style=3D"margin-bottom:0cm">Critique / flaws<br></p>

<p style=3D"margin-bottom:0cm">Obviously the biggest flaw here is that
the integrity of a timechain can&#39;t be known before-hand but if a
timechain were to be generated securely by a reputable party, the
biggest benefit of using it is that it basically runs itself: it does
not require any third-party to manage its functionality and the
entity which originally generated it can completely disappear without
interrupting service. This could, for instance - allow companies to
create entirely secure and reliable systems that couldn&#39;t be hacked
as the behaviour of a timechain is deterministic. I think this is a
huge improvement over existing systems which require third-parties to
be perpetually trusted with managing key-pairs on their web servers.</p><p =
style=3D"margin-bottom:0cm">You could even use collateral as a way to <span=
>incentivize</span> the reliable construction of the timechain by collectin=
g collateral into a multi-sig controlled by a number of neutral parties and=
 only releasing the coins back to the entity if the chain behaves as expect=
ed. I imagine some kind of signed copy of a GPU cluster bill + proof of cod=
e executed would be additional proof.<br></p>

<p style=3D"margin-bottom:0cm">Anyway, that&#39;s the basic idea. Let me kn=
ow what you think.<br></p>

<p style=3D"margin-bottom:0cm"><br>Sources:</p>
<p style=3D"margin-bottom:0cm">[0]
<a href=3D"http://www.gwern.net/Self-decrypting%20files" target=3D"_blank">=
http://www.gwern.net/Self-decrypting%20files</a></p>
<p style=3D"margin-bottom:0cm">[1]
<a href=3D"https://www.mail-archive.com/bitcoin-development@lists.sourcefor=
ge.net/msg05547.html" target=3D"_blank">https://www.mail-archive.com/bitcoi=
n-development@lists.sourceforge.net/msg05547.html</a></p>
<p style=3D"margin-bottom:0cm">[2]
<a href=3D"http://www.uptrenda.com/uptrenda.pdf" target=3D"_blank">http://w=
ww.uptrenda.com/uptrenda.pdf</a></p>
<p style=3D"margin-bottom:0cm">[3]
<a href=3D"https://bithalo.org/wp-content/uploads/2014/06/whitepaper_twosid=
ed.pdf" target=3D"_blank">https://bithalo.org/wp-content/uploads/2014/06/wh=
itepaper_twosided.pdf<br><br></a></p>[4] <a href=3D"https://lightning.netwo=
rk/lightning-network-paper-DRAFT-0.5.pdf" target=3D"_blank">https://lightni=
ng.network/lightning-network-paper-DRAFT-0.5.pdf</a><br><br></div>

--001a11343f28445e3a05186102b4--