From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id B17E99B9 for ; Thu, 23 Feb 2017 01:26:16 +0000 (UTC) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from outmail148106.authsmtp.co.uk (outmail148106.authsmtp.co.uk [62.13.148.106]) by smtp1.linuxfoundation.org (Postfix) with ESMTP id E827C210 for ; Thu, 23 Feb 2017 01:26:15 +0000 (UTC) Received: from mail-c247.authsmtp.com (mail-c247.authsmtp.com [62.13.128.247]) by punt22.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v1N1QE3R052722; Thu, 23 Feb 2017 01:26:14 GMT Received: from petertodd.org (ec2-52-5-185-120.compute-1.amazonaws.com [52.5.185.120]) (authenticated bits=0) by mail.authsmtp.com (8.14.2/8.14.2/) with ESMTP id v1N1QCXE023017 (version=TLSv1/SSLv3 cipher=DHE-RSA-AES256-SHA bits=256 verify=NO); Thu, 23 Feb 2017 01:26:13 GMT Received: from [127.0.0.1] (localhost [127.0.0.1]) by petertodd.org (Postfix) with ESMTPSA id 7924440123; Thu, 23 Feb 2017 01:26:12 +0000 (UTC) Received: by localhost (Postfix, from userid 1000) id A058220245; Wed, 22 Feb 2017 20:26:11 -0500 (EST) Date: Wed, 22 Feb 2017 20:26:11 -0500 From: Peter Todd To: Bram Cohen , Bitcoin Protocol Discussion Message-ID: <20170223012611.GA1454@savin.petertodd.org> References: MIME-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha256; protocol="application/pgp-signature"; boundary="5vNYLRcllDrimb99" Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.23 (2014-03-12) X-Server-Quench: 10d0a713-f967-11e6-bcdf-0015176ca198 X-AuthReport-Spam: If SPAM / abuse - report it at: http://www.authsmtp.com/abuse X-AuthRoute: OCd2Yg0TA1ZNQRgX IjsJECJaVQIpKltL GxAVKBZePFsRUQkR aAdMdAEUHlAWAgsB AmEbW1VeUlt7WGc7 bghPaBtcak9QXgdq T0pMXVMcUgQWAH1y bmseUBpydgIIfnhx YQhjXiRbDUN7dlsr S0hTCGwHMGF9OjNL Bl1YdwJRcQRMLU5E Y1gxIyZTNCdWOiMq EgN7FDc0ODRDLSlT Xhpl X-Authentic-SMTP: 61633532353630.1038:706 X-AuthFastPath: 0 (Was 255) X-AuthSMTP-Origin: 52.5.185.120/25 X-AuthVirus-Status: No virus detected - but ensure you scan with your own anti-virus system. X-Spam-Status: No, score=-2.6 required=5.0 tests=BAYES_00,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 Subject: [bitcoin-dev] Generalized Commitments X-BeenThere: bitcoin-dev@lists.linuxfoundation.org X-Mailman-Version: 2.1.12 Precedence: list List-Id: Bitcoin Protocol Discussion List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 23 Feb 2017 01:26:16 -0000 --5vNYLRcllDrimb99 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Tue, Feb 21, 2017 at 02:00:23PM -0800, Bram Cohen via bitcoin-dev wrote: > When one side of a node is empty and the other contains exactly two things > the secure hash of the child is adopted verbatim rather than rehashing it. > This roughly halves the amount of hashing done, and makes it more resista= nt > to malicious data, and cleans up some implementation details, at the cost > of some extra complexity. Note that this is a use-case specific concept of an idea I'm calling a "generalized commitment" A commitment scheme needs only have the property that it's not feasible to = find two messages m1 and m2 that map to the same commitment; it is *not* required that it be difficult to find m given the commitment. Equally, it's not requ= ired that commitments always be the same size. So a perfectly reasonable thing to do is design your scheme such that the commitment to short messages is the message itself! This adds just a single= bit of data to the minimum serialized size(1) of the commitment, and in situati= ons where sub-digest-sized messages are common, may overall be a savings. Another advantage is that the scheme becomes more user-friendly: you *want* programmers to notice when a commitment is not effectively hiding the messa= ge! If you need message privacy, you should implement an explicit nonce, rather than relying on the data to not be brute-forcable. 1) The more I look at these systems, the more I'm inclined to consider bit-granularity serialization schemes... Heck, sub-bit granularity has advantages too in some cases, e.g. by making all possible inputs to the deserializer be valid. --=20 https://petertodd.org 'peter'[:-1]@petertodd.org --5vNYLRcllDrimb99 Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature -----BEGIN PGP SIGNATURE----- iQEcBAEBCAAGBQJYrjowAAoJECSBQD2l8JH76QcH/3Ipz8aGgWcVyRve/EfXijcG F0ptbO4/pKG8WeX4wBy2jyQ6TTK4Czb29uOpMk0Zmtys25R242O2kk5QC5D6ghnf TBUpgwL1YXYmc0zZqNU109Ax2/c1foQiNyXpgbLykGg8mtGXaNN8+KGqsrQs4qQ8 e9I6pQDZOOCqBGoNt4UF4gJyFB3gfeCwxCQN+xhv1+l6W1wCY+B1b1gWSZZFvJMF 11Ixlm+bApwCRJPrkpPdZiUcSEfqjPB26dU1iBIvLyMwmS9zDn0Fv1eSwQecwf5f 8EZ6JVV4OE9pUyGseAN3HIkEc0U0IAjlYqIRC2Q1bpLFtRTpsPRHQepBd/HmtO0= =GaJz -----END PGP SIGNATURE----- --5vNYLRcllDrimb99--