Return-Path: Received: from smtp1.linuxfoundation.org (smtp1.linux-foundation.org [172.17.192.35]) by mail.linuxfoundation.org (Postfix) with ESMTPS id AC639B9B for ; Thu, 23 Feb 2017 02:56:36 +0000 (UTC) X-Greylist: whitelisted by SQLgrey-1.7.6 Received: from mail-it0-f44.google.com (mail-it0-f44.google.com [209.85.214.44]) by smtp1.linuxfoundation.org (Postfix) with ESMTPS id 1A60512F for ; Thu, 23 Feb 2017 02:56:35 +0000 (UTC) Received: by mail-it0-f44.google.com with SMTP id 203so2597720ith.0 for ; Wed, 22 Feb 2017 18:56:35 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=bittorrent-com.20150623.gappssmtp.com; s=20150623; h=mime-version:in-reply-to:references:from:date:message-id:subject:to :cc; bh=tWsHnoOyt6rJvPB9aCikw/3VpbxkqU5ORSG2m8IfRaw=; b=16rEuHf2hvj3DH0UCCFBZYWLJTQsv04NOGolxK5rnZEiDlllB62Qsh7jJOprAFyGxW JFbwcsTBn6Sg+Axp/GJqdHNgbYaLMDKYgcM1NrD3nnxtsppuIPW3huxqRc3CcWf8N5Tw qtpJml+0fFKi9w1DpdrpONp+Yoy+DxDRUj/ejA9G8t29CVbKtpcYgRidr32B57+Fn21e jSgWmeFuD9vvcihMCV1apMt/+Ia1nwA+ELchKopIylH8FRx3YbnsQzsDRaEPg33Zd5XP e0cw9zR89qaoK18u+oABwgi7NnUHfFNUTW7Cs73rIQGFfLNf4K/VSkUCS8VKi5SvR3ye birQ== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc; bh=tWsHnoOyt6rJvPB9aCikw/3VpbxkqU5ORSG2m8IfRaw=; b=LKfsL6aVFKW0M5aWPdE1fDQwqUZOdq/ipI1cvlJpsCtWvQskWFH2W3re5MnY/FdE2P RNHGV+Y0fTF9ZfdEw2q4yksD6KUFSbHAoxkDrxBFBnsuJYmnJx5xF/0bnKJFGWmgse6p 5s5HAAUo90QCbJFAsw68bgI9uerUPebOt4x0BjEjNICJGGXeJ9TpEs36FvalEd9alr+A ZIOPv2FhQkQfueremVqw5WnFFBQssJjBYfwMECXbU/4Hhomvz/ExBjkRcaSDLl8M3W6V oV1C5hrCTH0ptJ3qG8WTC9LUr4yFLg9S+Gj/OYS8Oo9ftm+r7ZyFJg5gkx3viC1Sz5mf nr+w== X-Gm-Message-State: AMke39nZ0hpbTknqY+bCx6EooTm0AQYnmASshNYcZCGt0jA8HxNhNO6crNi/EvRUCPAhpLUcdbCxvJLrOHALRt3Y X-Received: by 10.107.15.70 with SMTP id x67mr25943931ioi.103.1487818595377; Wed, 22 Feb 2017 18:56:35 -0800 (PST) MIME-Version: 1.0 Received: by 10.36.73.150 with HTTP; Wed, 22 Feb 2017 18:56:35 -0800 (PST) In-Reply-To: <20170223012611.GA1454@savin.petertodd.org> References: <20170223012611.GA1454@savin.petertodd.org> From: Bram Cohen Date: Wed, 22 Feb 2017 18:56:35 -0800 Message-ID: To: Peter Todd Content-Type: multipart/alternative; boundary=001a113ed7fede46ce054929c2f1 X-Spam-Status: No, score=-2.1 required=5.0 tests=BAYES_00,DKIM_SIGNED, DKIM_VALID, HTML_MESSAGE, RCVD_IN_DNSWL_LOW, RCVD_IN_SORBS_SPAM autolearn=ham version=3.3.1 X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on smtp1.linux-foundation.org Cc: Bitcoin Protocol Discussion Subject: Re: [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 02:56:36 -0000 --001a113ed7fede46ce054929c2f1 Content-Type: text/plain; charset=UTF-8 On Wed, Feb 22, 2017 at 5:26 PM, Peter Todd wrote: > > 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 > required > 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 > situations > where sub-digest-sized messages are common, may overall be a savings. > Yes I'm basically doing that but to make things be all the same size I'm including the bit inline, sacrificing one bit of security. Actually I'm sacrificing two bits of security, to allow for four values: terminal, middle, empty, and invalid. Invalid is used internally when a value has yet to be calculated lazily and in proofs to mean 'this is a middle node but the children are not included'. One effect of this is that the root of a set containing a single value is just that value with the two high order bits of the first byte reset to the appropriate value. --001a113ed7fede46ce054929c2f1 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
On W= ed, Feb 22, 2017 at 5:26 PM, Peter Todd <pete@petertodd.org> wrote:

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* require= d
that it be difficult to find m given the commitment. Equally, it's not = required
that commitments always be the same size.=C2=A0

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.

Yes I'm basically doing that but to make= things be all the same size I'm including the bit inline, sacrificing = one bit of security. Actually I'm sacrificing two bits of security, to = allow for four values: terminal, middle, empty, and invalid. Invalid is use= d internally when a value has yet to be calculated lazily and in proofs to = mean 'this is a middle node but the children are not included'. One= effect of this is that the root of a set containing a single value is just= that value with the two high order bits of the first byte reset to the app= ropriate value.

--001a113ed7fede46ce054929c2f1--