Received: from sog-mx-2.v43.ch3.sourceforge.com ([172.29.43.192] helo=mx.sourceforge.net) by sfs-ml-4.v29.ch3.sourceforge.com with esmtp (Exim 4.76) (envelope-from ) id 1UcwQF-0007hA-UC for bitcoin-development@lists.sourceforge.net; Thu, 16 May 2013 11:32:35 +0000 Received-SPF: pass (sog-mx-2.v43.ch3.sourceforge.com: domain of gmail.com designates 74.125.83.43 as permitted sender) client-ip=74.125.83.43; envelope-from=adam.back@gmail.com; helo=mail-ee0-f43.google.com; Received: from mail-ee0-f43.google.com ([74.125.83.43]) by sog-mx-2.v43.ch3.sourceforge.com with esmtps (TLSv1:RC4-SHA:128) (Exim 4.76) id 1UcwQE-000112-R3 for bitcoin-development@lists.sourceforge.net; Thu, 16 May 2013 11:32:35 +0000 Received: by mail-ee0-f43.google.com with SMTP id d41so1393972eek.30 for ; Thu, 16 May 2013 04:32:28 -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:x-hashcash:x-hashcash; bh=vhi41t6Nf4+53ywkS12lGxGShJF6TqvQcRNUnd3N/x8=; b=Wzq56CQ4U1cUCnTlL0UzDGmCmzM47SvPC93Gi2ihG33A+6nDFO8MOUkDXLmQgjAOwM HUcX+licmSUyjFQPp0eD3/X0dYQar9/GpejrFyhH3Z2NwkYJDo7aPtTu4G18slwiiZTm RKvPAFzQTwoJ+lBKpjFJSYg6kHZa8lroo+r+50f2i37ah2DB2Yv7+KKV0dhRn6GcM3F3 NK3qX0yfdDmaMdecF3mjS9LSsP2L1XCuG5IgWEmIHr2q0fsk255wndtHcOHmstwlXS0+ 0eIiErNGSGviW6t6rasgw6JZPVFwQdyVopqBd4qeW+BPQ/KoKgjK+bWMV5FnlKDktc+e Nq6Q== X-Received: by 10.15.107.77 with SMTP id ca53mr114254325eeb.40.1368703948444; Thu, 16 May 2013 04:32:28 -0700 (PDT) Received: from netbook (c83-90.i07-21.onvol.net. [92.251.83.90]) by mx.google.com with ESMTPSA id m48sm9653723eeh.16.2013.05.16.04.32.26 for (version=TLSv1.1 cipher=ECDHE-RSA-RC4-SHA bits=128/128); Thu, 16 May 2013 04:32:27 -0700 (PDT) Received: by netbook (Postfix, from userid 1000) id 20A6A2E0652; Thu, 16 May 2013 13:32:25 +0200 (CEST) Received: by flare (hashcash-sendmail, from uid 1000); Thu, 16 May 2013 13:32:23 +0200 Date: Thu, 16 May 2013 13:32:22 +0200 From: Adam Back To: Gregory Maxwell Message-ID: <20130516113222.GA16384@netbook.cypherspace.org> References: <20130515102509.GA3401@netbook.cypherspace.org> <20130515111906.GA26020@savin> <20130515114956.GA5863@netbook.cypherspace.org> <5193825B.20909@lavabit.com> <20130515162129.GB6156@netbook.cypherspace.org> <20130515234030.GA17920@netbook.cypherspace.org>

MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii; format=flowed Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) X-Hashcash: 1:20:130516:gmaxwell@gmail.com::/JRrZ/1p9FFaDnn8:0000000000000000000 00000000000000000000000019vr X-Hashcash: 1:20:130516:mike@plan99.net::XvjbNuyBcRXjkAUq:0056Mq X-Hashcash: 1:20:130516:bitcoin-development@lists.sourceforge.net::UF15wFIEsCBjK 5AW:000000000000000000003/pz X-Hashcash: 1:20:130516:adam@cypherspace.org::tFj/Ffsmon0ijADY:00000000000000000 0000000000000000000000002iII 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: 1UcwQE-000112-R3 Cc: "bitcoin-development@lists.sourceforge.net" Subject: Re: [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: Thu, 16 May 2013 11:32:36 -0000 On Wed, May 15, 2013 at 07:45:34PM -0700, Gregory Maxwell wrote: >[committed coins] depending on how its done, at most conceals the >transactions from people who aren't a party to them... though as time goes >on eventually everyone becomes a party to a sufficiently old coin, and >avoiding publication creates quadratic costs in evaluating a private >clique's claims.... so I believe the coin size and verification cost is linear not quadratic, but maybe it depends on the parameter you're measuing in. The coin size is linear with the number of committed (uncompacted) spends. You can view reveals as committed compaction. For efficiency a recipient of a committed coin may as well compact and spend in one transaction so no new messages are created. Btw I believe if one were concerned about the committed coin size, I can see a small tweak that would keep the size of the committed coins small eg 256-bit regardless of number of spends (no longer grows), and let the block store the encrytped & MACed commitment. Then compaction is no longer a concern. However I think that is SPV -> SPV client unfriendly. (A full client -> SPV client should still be workable as the full client could alternatively send the client the MACed data and key, rather than have him look at it from his block history.) (Crypto sketch below). However I am not sure multi-spend committed coin size is really a concern because to the extent people hold long commitments without revealing to the network for the long term, that is a bandwidth saving to the network. Overall about privacy it would be typically temporary, though the peers have the technical means to react and defend themselves by using longer committed chains if dishonest mining is detected on a significant scale. >instead an implementation would make the identities public but only once >they're burred a bit. That was the seed idea. The more aggressive "spend lots of times in committed form" is just a technical threat that will keep dishonest mining in check. By definition the coin is already irrevocably spent before the reveal (without the threat of having the dishonest miners endlessly redoing their own deeply burried work). The only person who could be punished by policy by >50% dishonest miner (retroactively) is the recipient, not the spender, and the punishment is very muted: all he can do is prevent coin compaction. If the committed coins are small, compact doesnt even hurt the committed coin user, just network itself. Therefore a dishonest miner is wasting his time his dishonesty cant enforce his dishonest policy. To store the commitments in the block chain replace: > (blind-sender, auth-tag, tx-commit) > > blind-sender = SHA1( SHA256( 1, pub ) ) > auth = HMAC-SHA256-128( K, tx-commit ) > tx-commit = SHA-256( tx ) > K = SHA-256( pub ) with: (blind-sender, auth-tag, encrypted-tx-commit) blind-sender = SHA1( SHA256( 1, pub ) ) auth = HMAC-SHA256-128( K, encrypted-tx-commit ) encrypted-tx-commit = AES( K, tx-commit ) (*) K = SHA-256( pub ) then a reveal is just to send the recipient the public key (32 bytes) per hop, still linear but ~3x smaller. I suggested fixed size committed coin spends, that also you can do but with public key crypto needed probably, and so dropping to the verification efficiency of standard transactions. Sketch 2: (blind-sender, auth-tag, encrypted-tx-commit) (pub key P = xG, G = base point) blind-sender = cP (public key EC multiplied by constant c) sig = ECDSA( cx, encrypted-tx-commit ) encrypted-tx-commit = AES( K, tx-commit ) K = random as K is random, knowledge of P if stored unencrypted does not allow committed spend-to-junk. To reveal to a recipient just send them P and K at each hop. (Same K each time, anyone on the committed coin spend chain can already chose to reveal at any time so no loss of security.) You dont need to verify a second signature inside the tx-commit because you already signed the encrypted-tx which binds to it (encryption with out MAC is malleable but you cant change it at all without invalidating the encryption). Just need to check the input tx in the tx-commit has P as its recipient. P does not even need to go into tx-commit as its already bound by cP and signature security (cant create a signature with someone elses key). So I think the commited coins of this form are the same size and verification cost for the network. And small and fixed size to spend offline. (32+32=64 bytes fixed). Adam (*) You should not as a principle re-use keys across algorithms, I omitted a second key for simplicity. Really K1 = SHA256( 1||pub ), K2 = SHA256( 2||pub ) encrypted-tx-commit = AES( K1, tx-commit ), auth = HMAC( K2, encrypted-tx-committ ). Or more simply a combined authenticated mode like CCM or GCM and a single key managed by the mode.