public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Bram Cohen <bram@bittorrent.com>
To: Peter Todd <pete@petertodd.org>
Cc: Bitcoin Protocol Discussion <bitcoin-dev@lists.linuxfoundation.org>
Subject: Re: [bitcoin-dev] Generalized Commitments
Date: Wed, 22 Feb 2017 18:56:35 -0800	[thread overview]
Message-ID: <CA+KqGkq4LuUw1b2sMW-GdjFPH53U9uoAVUVP33hht5vLvWPBWw@mail.gmail.com> (raw)
In-Reply-To: <20170223012611.GA1454@savin.petertodd.org>

[-- Attachment #1: Type: text/plain, Size: 1253 bytes --]

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.

[-- Attachment #2: Type: text/html, Size: 1738 bytes --]

      reply	other threads:[~2017-02-23  2:56 UTC|newest]

Thread overview: 3+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2017-02-21 22:00 [bitcoin-dev] Proposal for utxo commitment format Bram Cohen
2017-02-23  1:26 ` [bitcoin-dev] Generalized Commitments Peter Todd
2017-02-23  2:56   ` Bram Cohen [this message]

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

  Avoid top-posting and favor interleaved quoting:
  https://en.wikipedia.org/wiki/Posting_style#Interleaved_style

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=CA+KqGkq4LuUw1b2sMW-GdjFPH53U9uoAVUVP33hht5vLvWPBWw@mail.gmail.com \
    --to=bram@bittorrent.com \
    --cc=bitcoin-dev@lists.linuxfoundation.org \
    --cc=pete@petertodd.org \
    /path/to/YOUR_REPLY

  https://kernel.org/pub/software/scm/git/docs/git-send-email.html

* If your mail client supports setting the In-Reply-To header
  via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox