From: Bram Cohen <bram@bittorrent•com>
To: Bitcoin Protocol Discussion <bitcoin-dev@lists•linuxfoundation.org>
Subject: [bitcoin-dev] Proposal for utxo commitment format
Date: Tue, 21 Feb 2017 14:00:23 -0800 [thread overview]
Message-ID: <CA+KqGkpVLfGjQUJEYdRppqvN263rHrY-rGL2k22eMryQbb6Q8g@mail.gmail.com> (raw)
[-- Attachment #1: Type: text/plain, Size: 1423 bytes --]
Here is a Merkle set data structure, whose format may be useful for utxo
commitments in Bitcoin blocks. It may also be useful for any other
distributed computation which wants an audit trail:
https://github.com/bramcohen/MerkleSet
This is a fairly straightforward Patricia Trie, with a simple format and a
simple reference implementation plus a performance optimized non-reference
implementation which is much more cache coherent. It will need to be ported
to C and be properly turned before the potential performance gains can be
realized though.
The clever things which affect the format spec are:
It uses blake2s as the internal hash function. This is the fastest hash
function to use on 512 bit inputs because blake2b uses a 1024 bit block
size. It might make sense to use a hypothetical variant of blake which is
optimized for 64 bits with a 512 bit block size, but that hasn't been
specified. Sha256 would take advantage of hardware acceleration, but that
isn't available everywhere.
Two bits of security are sacrificed to include metadata inline which halves
the CPU cost of hashing.
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 resistant
to malicious data, and cleans up some implementation details, at the cost
of some extra complexity.
[-- Attachment #2: Type: text/html, Size: 1656 bytes --]
next reply other threads:[~2017-02-21 22:00 UTC|newest]
Thread overview: 3+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-02-21 22:00 Bram Cohen [this message]
2017-02-23 1:26 ` [bitcoin-dev] Generalized Commitments Peter Todd
2017-02-23 2:56 ` Bram Cohen
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+KqGkpVLfGjQUJEYdRppqvN263rHrY-rGL2k22eMryQbb6Q8g@mail.gmail.com \
--to=bram@bittorrent$(echo .)com \
--cc=bitcoin-dev@lists$(echo .)linuxfoundation.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
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