From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from sog-mx-3.v43.ch3.sourceforge.com ([172.29.43.193] helo=mx.sourceforge.net) by sfs-ml-2.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1UcYti-0003NR-GK for bitcoin-development@lists.sourceforge.net; Wed, 15 May 2013 10:25:26 +0000 Received-SPF: pass (sog-mx-3.v43.ch3.sourceforge.com: domain of gmail.com designates 209.85.215.174 as permitted sender) client-ip=209.85.215.174; envelope-from=adam.back@gmail.com; helo=mail-ea0-f174.google.com; Received: from mail-ea0-f174.google.com ([209.85.215.174]) by sog-mx-3.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1UcYtd-0005Cx-Aa for bitcoin-development@lists.sourceforge.net; Wed, 15 May 2013 10:25:26 +0000 Received: by mail-ea0-f174.google.com with SMTP id z7so918060eaf.5 for ; Wed, 15 May 2013 03:25:15 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=20120113; h=x-received:date:from:to:cc:subject:message-id:references :mime-version:content-type:content-disposition:in-reply-to :user-agent:x-hashcash:x-hashcash; bh=GGhT4+O6DTr6n10L2RnAxmVl8Q1xqDZby1E4lWYG9RI=; b=JSkAa82MAG2ItcZJg4sX/vK6CwWSCwnvthw5rWid1k2k37PMjkhT0h3dVu20mG3dLX GDLbNRNHPVkCbAkBRtEq1JcPBSY69FINul/XXCvXGIPuJQWvEKYbZA9oInj9/kM/IcWg 0xzZ6PcdjK15DdN/JJt+OgIvZrtLuoCV/ffUXKxNAv9W+cNzvu7lIcphisfWzvSFh+TI +7xdbkcz+e4E9zJjEte/9cJ1GUn+Y6W1DyNntf6X2ai3INvc2oDP9HuoTbFrHVNMDLO0 oSLMgxQY484YwN5oguwBguOo4aZh6z2NeqeMwYzaP7fVhjGHpbsGfwkFCaTjyd1snTBB 15iQ== X-Received: by 10.15.81.197 with SMTP id x45mr9599021eey.9.1368613514862; Wed, 15 May 2013 03:25:14 -0700 (PDT) Received: from netbook (c83-90.i07-21.onvol.net. [92.251.83.90]) by mx.google.com with ESMTPSA id i3sm3021343eev.1.2013.05.15.03.25.12 for (version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Wed, 15 May 2013 03:25:13 -0700 (PDT) Received: by netbook (Postfix, from userid 1000) id 81FDA2E05A1; Wed, 15 May 2013 12:25:10 +0200 (CEST) Received: by flare (hashcash-sendmail, from uid 1000); Wed, 15 May 2013 12:25:09 +0200 Date: Wed, 15 May 2013 12:25:09 +0200 From: Adam Back To: Bitcoin-Dev Message-ID: <20130515102509.GA3401@netbook.cypherspace.org> References: <20130514115151.GA21600@netbook.cypherspace.org> <20130514140902.GA22447@netbook.cypherspace.org> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Disposition: inline In-Reply-To: <20130514140902.GA22447@netbook.cypherspace.org> User-Agent: Mutt/1.5.21 (2010-09-15) X-Hashcash: 1:20:130515:bitcoin-development@lists.sourceforge.net::T2nnwKfExAGhb YhG:000000000000000000003eTz X-Hashcash: 1:20:130515:adam@cypherspace.org::ZaJKBR8rRcM7X6KQ:00000000000000000 0000000000000000000000000S43 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 FREEMAIL_FROM Sender email is commonly abused enduser mail provider (adam.back[at]gmail.com) -0.0 SPF_PASS SPF: sender matches SPF record X-Headers-End: 1UcYtd-0005Cx-Aa Subject: [Bitcoin-development] blind symmetric commitment for stronger byzantine voting resilience (Re: bitcoin taint & unilateral revocability) X-BeenThere: bitcoin-development@lists.sourceforge.net X-Mailman-Version: 2.1.9 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 15 May 2013 10:25:26 -0000 So in a previous mail I described a simple, extremely efficient and easy to implement symmetric key commitment that is unlinkable until reveal time (at bottom). I think this can help improve the byzantine generals problem, that bitcoin only defends to simple majority (with one vote per CPU power), and so assumes most nodes by cpu power are honest. With this simple protocol change you dont need any honest nodes, just some honest clients to spend to, to have your transaction accepted. You can think of this in terms of a (somewhat distributed) server performing validations, but in a way that it sufficiently blind to the details of the validations that it can not selectively enforce a policy, it power is limited to random DoS. There are other situations where you can rely on a server for one property but not another - eg a somewhat distributed encrypted backup (like Tahoe LAFS) you rely on for availability, but not integrity nor confidentiality (because you encrypt those, and some sharing scenarios still work.) So this is in that class of protocols - zero-trust in server, but can extract service and some guarantees from the (optionally distributed) server anyway. (Bitcoin does not use known better than majority results for byzantine generals based on fair coin toss, relying instead on simple majority and an assumed largely unjammable network. I notice Nick Szabo was complaining about this on his blog and saying bitcoins majority is not even a standard or proven byzantine voting protocol - something adhoc. I think the bitcoin unjammable network assumption is a false at the limit so that someone with strong network hacking capabilities can create network splits long enough to even overcome the network majority vote without having any compute power of their own. All they need is to have a split with enough power to plausibly quickly get the victims their desired number of (split) confirmations.) Anyway this should be a clear voting improvement, that is efficient. Imagine a couple of big pools or ASIC miners started enforcing some arbitrary coin policy, eg say coins must not have some taint according to its list of black coins, or coins must be certified by some entity, be traceable to some type of event etc. Well call these miners/voters "dishonest", in that they are not following the intended zero-policy protocol. If the coins dont match their chosen policy, the dishonest miners will refuse to include transactions in blocks they issue. If they see a transaction which does not match their policy in a block by someone else they will ignore it and try to make it into an orphan. As they have say 75% of the network power they can do that successfully. Even with current validation protocols in the clients, so the "but clients wont accept the change" argument does not apply - the existing clients will accept the policy change, because they cant detect it, nor prove it, and dont have the voting power to impose honest policies. (For realism of this risk, note that according to Kaminsky there already exist multiple entities with reserve ASIC power each exceeding current network difficulty who are holding part of their power in reserve for profit maximisation reasons. This is a coming to fruition of the concentration of power issue I was talking about in my first bitcoin forum post. People who have that kind of power in reserve have clearly invested millions of dollars, which probably makes them more vulnerable to political influence.) Alright so the solution. Use the commitment protocol (below) which even though it is symmetric key strongly hides the committed transaction public key. (Symmetric in the sense that the validation steps are all highly efficient symmetric key based). Now send the transaction (which includes the public key) direct to the receiver, over a secure channel, or an assumed non-eavesdropped direct channel, with no p2p flood of the transaction. The receiver can check the hash to the commitment, and decide how many confirmtions he needs. Once he has eg 6 confirmations he reveals the commitment to the transaction (by publishing it). The sender may also send the reveal/transaction to the network directly himself, if the recipient is offline. However there is no advantage to publishing early so it seems better to let the recipient do it when he is ready to incorporate the payment into his wallet. Now the powerful dishonest voters if they try to apply their policy when they see the reveal triggers it, must redo the work of the 6-commitments that they computed themselves. This is like starting 6-steps behind in the statstical gamblers ruin game that Nakamoto describes in the bitcoin paper. Consequently even with 75%, they will find it very hard to outcompete their own prior work, to create a 6 chain long orphan while the 25% is moving forward on the honest chain. Each time they see transactions which violate their policy, they have to restart their chain recalculation again from scratch. Often if simple lower powered intermittent recipient sends the coin will be burried hundreds of blocks back. In addition 6 chain long branches are extremely unlikely with honest payers, so clients can (and maybe already do?) act with suspicion of they see one. Going further, I said for best security, the recipient should never even reveal (to the network) until he is actually about to spend, but futher he does not even have to reveal publicly ever, he can choose to reveal only to the recipient with a direct connection (no p2p flood fill of transaction.) And the direct spend argument composes, ie the 2nd recipient can not do the same thing again. (public key A sends to public key B sends to public key C: B publishes COM( transaction B->C ), sends the reveal of COM( transaction A->B ), and COM transaction B->C ) to C. C waits 6 confirmations and is convinced. So its the approach is composable, and in fact the network doesnt learn the size of the transaction even, though the spend grows each time. Eventually presumably someone will publish will the confirmations to the network to trim the tansaction size, though it is not strictly necessary, and the transaction flow is small and direct (no network scaling issues), so that it wouldnt be a huge problem to have a 1MB payment representing 1000s of hops of network blind transactions. (For the composable network blind respending the commitment has to commit publicly to both the sender and next hop recipient keys, so the network can see how long the chain is). Probably you can cope with multiple inputs and outputs, and maybe given even you can work with a 100% dishonest network mining network (all the dishonest miner can do is selectively DoS transactions if they are all network blind except the mining), maybe the mining can even be decoupled from the voting, as you no longer demand much from the voting process. That admits more interesting things like pool free direct mining, low variance hashcash coins, probably. Many things to think through. I suppose the commitment could be described as a blind symmetric commitment. Adam On Tue, May 14, 2013 at 04:09:02PM +0200, Adam Back wrote: > [...] > >One related concept is commitments. I think its relatively easy to commit >to a payment and lock a coin without identifying yourself, until the >commitment is released. You might do the commitment, wait 6-blocks for >confirmation, then reveal the commitment. Then that is like a self-issued >green coin with no need for trust, that can be immediately cleared. The >recipient has to be committed to at the same time to prevent double >spending. > >So just commit = H( input-pub ) H( transaction ) and put it in the block >chain. Where transaction the is usual ( input signature, output-pub, >script). (Fee for the commit would have to come from an unlinked coin or >the input-pub reveals the coin). Wait 6 blocks, send/reveal the transaction >(free because fee was already paid). Validators check input-pub hash >against committed coins by hash, check the transaction hash, and the usual >ransaction validations = sum inputs, otherwise reject. The user better pay >change if any to a different public key, as the inputs public keys are one >use - are after the reveal they are DoS lockable by other people reposting >H( input-pub ). > >The input-pub coin is locked as normal transactions have their public key hash >validate as not being locked. > >Adam