MIME-Version: 1.0
In-Reply-To: <20170223012611.GA1454@savin.petertodd.org>
References: <CA+KqGkpVLfGjQUJEYdRppqvN263rHrY-rGL2k22eMryQbb6Q8g@mail.gmail.com>
	<20170223012611.GA1454@savin.petertodd.org>
From: Bram Cohen <bram@bittorrent.com>
Date: Wed, 22 Feb 2017 18:56:35 -0800
Message-ID: <CA+KqGkq4LuUw1b2sMW-GdjFPH53U9uoAVUVP33hht5vLvWPBWw@mail.gmail.com>
To: Peter Todd <pete@petertodd.org>
Content-Type: multipart/alternative; boundary=001a113ed7fede46ce054929c2f1
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Generalized Commitments
Precedence: list

--001a113ed7fede46ce054929c2f1
Content-Type: text/plain; charset=UTF-8

On Wed, 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*
> 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

<div dir=3D"ltr"><div class=3D"gmail_extra"><div class=3D"gmail_quote">On W=
ed, Feb 22, 2017 at 5:26 PM, Peter Todd <span dir=3D"ltr">&lt;<a href=3D"ma=
ilto:pete@petertodd.org" target=3D"_blank">pete@petertodd.org</a>&gt;</span=
> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;bo=
rder-left:1px #ccc solid;padding-left:1ex"><br>
A commitment scheme needs only have the property that it&#39;s not feasible=
 to find<br>
two messages m1 and m2 that map to the same commitment; it is *not* require=
d<br>
that it be difficult to find m given the commitment. Equally, it&#39;s not =
required<br>
that commitments always be the same size.=C2=A0</blockquote><blockquote cla=
ss=3D"gmail_quote" style=3D"margin:0 0 0 .8ex;border-left:1px #ccc solid;pa=
dding-left:1ex">
<br>
So a perfectly reasonable thing to do is design your scheme such that the<b=
r>
commitment to short messages is the message itself! This adds just a single=
 bit<br>
of data to the minimum serialized size(1) of the commitment, and in situati=
ons<br>
where sub-digest-sized messages are common, may overall be a savings.<br></=
blockquote><div><br></div><div>Yes I&#39;m basically doing that but to make=
 things be all the same size I&#39;m including the bit inline, sacrificing =
one bit of security. Actually I&#39;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 &#39;this is a middle node but the children are not included&#39;. 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.</div><div><br></div></div></div></div>

--001a113ed7fede46ce054929c2f1--