public inbox for bitcoindev@googlegroups.com
 help / color / mirror / Atom feed
From: Elden Tyrell <tyrell.elden@gmail.com>
To: bitcoin-development@lists.sourceforge.net
Subject: Re: [Bitcoin-development] [PROPOSAL] Merkle tree of unspent transactions (MTUT), for serverless thin clients and self-verifiable prunned blockchain.
Date: Sun, 29 Jan 2012 12:40:23 -0600	[thread overview]
Message-ID: <jg43qn$jbn$1@dough.gmane.org> (raw)
In-Reply-To: CAE98tO0Nh=L2mSy-MzEW7o+0=Tzivw0zj8cG8e1EscmW0C0kBg@mail.gmail.com

On 2012-01-23 20:00:59 -0600, Alberto Torres said:
> This proposal describes how to add a hash-tree based check in the
> blockchain that allows to verify if a transaction is unspent without
> downloading and checking all the blockchain. The idea is not new, but
> at the time of this writing there isn't any technical description of
> how this should be done.

Thanks for writing this up (it's high time somebody did).  I like your 
acronym, but shouldn't it be "MTUO" since you spend *outputs* rather 
than *transactions*?  A transaction can have multiple outputs, some of 
which are spent and others which aren't.

I've added a link to your proposal on the 
https://en.bitcoin.it/wiki/Thin_Client_Security wiki page.

> Once 55% of blocks includes a valid MTUT hash in a 2-week timespan, 
> they should reject any block with an invalid (i.e. probably malicious) 
> MTUT hash block while accepting blocks without MTUT.

Just like OP_EVAL/p2sh, this creates the (small) risk of a blockchain split.

Unlike adding a new transaction type, here it's possible to eliminate 
this risk: give each MTUT an additional "prev" pointer (hash of some 
prior block) which points to the latest prior block with a correct 
MTUT.  This produces a "chain within the chain" of blocks that have 
valid MTUTs.  Hostile miners are free to add bogus-MTUT-blocks; those 
bogus blocks will simply never be included in the "inner chain", just 
like invalid blocks mined by hostile miners are never included in the 
blockchain.  By downloading the last day's worth of blocks (which is 
not much data at all), a client can see which "inner chain" the 
majority of the hashpower believed during the last 24 hours.  This 
eliminates the need for a vote in any specific block -- in effect you 
get a "rolling election".

This "inner chain" approach can be broadened to a K-ary tree by 
including K-many prior-block pointers.  With one of these in every 
block (and sensible choices) you wind up with 
O(log_K(chain_length))-operation hash-secure access to arbitrary blocks 
in the middle of the chain.  This is an important building block for 
ultra-high-security thin clients.  Even if only a 1/K of the network's 
hashpower starts adding these pointers the worst-case number of 
operations needed to reach an arbitrary block will still converge 
(though much more slowly) towards this ideal.

  - e





      reply	other threads:[~2012-01-29 18:40 UTC|newest]

Thread overview: 2+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
2012-01-24  2:00 [Bitcoin-development] [PROPOSAL] Merkle tree of unspent transactions (MTUT), for serverless thin clients and self-verifiable prunned blockchain Alberto Torres
2012-01-29 18:40 ` Elden Tyrell [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='jg43qn$jbn$1@dough.gmane.org' \
    --to=tyrell.elden@gmail.com \
    --cc=bitcoin-development@lists.sourceforge.net \
    /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