diff options
| author | Matthew Roberts <matthew@roberts.pm> | 2015-06-13 17:16:52 +1000 |
|---|---|---|
| committer | bitcoindev <bitcoindev@gnusha.org> | 2015-06-13 07:17:00 +0000 |
| commit | f58a96677864bf4be8c0dd10eb8ce50772bf96fb (patch) | |
| tree | 40c4afb47dbc4b62d38e9f88fa9b5715f97f84af | |
| parent | 6681958c2ef4a5925c02cb499ddc66171793202c (diff) | |
| download | pi-bitcoindev-f58a96677864bf4be8c0dd10eb8ce50772bf96fb.tar.gz pi-bitcoindev-f58a96677864bf4be8c0dd10eb8ce50772bf96fb.zip | |
[Bitcoin-development] The timechain: an idea to solve TX malleability in smart contract protocols with minimal involvement and without requiring a fork.
| -rw-r--r-- | b9/652775a89f3bac5d068c671129f34554957d15 | 329 |
1 files changed, 329 insertions, 0 deletions
diff --git a/b9/652775a89f3bac5d068c671129f34554957d15 b/b9/652775a89f3bac5d068c671129f34554957d15 new file mode 100644 index 000000000..585305258 --- /dev/null +++ b/b9/652775a89f3bac5d068c671129f34554957d15 @@ -0,0 +1,329 @@ +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'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 -> output.</p> +<p style=3D"margin-bottom:0cm">3. Hash the output -> output.</p> +<p style=3D"margin-bottom:0cm">4. Hash the output -> 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'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=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 +"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.</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 "into" 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'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'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'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'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.</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'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-- + + |