* [Bitcoin-development] [PROPOSAL] Merkle tree of unspent transactions (MTUT), for serverless thin clients and self-verifiable prunned blockchain.
@ 2012-01-24 2:00 Alberto Torres
2012-01-29 18:40 ` Elden Tyrell
0 siblings, 1 reply; 2+ messages in thread
From: Alberto Torres @ 2012-01-24 2:00 UTC (permalink / raw)
To: bitcoin-development
Hello,
I've written this proposal. C&P of the overview:
Satoshi's original paper describes a way of prunning spent
transactions in the blockchain to save storage space while it remains
consistent and verifiable, but it's useless for partial blockchain
downloads: while you can know if a given transaction is in the
blockchain, you can't know if it has been spent in a subsequent
transaction.
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. Aditionally, this solution is rather simple.
https://en.bitcoin.it/wiki/User:DiThi/MTUT
Cheers
--
Alberto Torres Ruiz (a.k.a. DiThi)
^ permalink raw reply [flat|nested] 2+ messages in thread
* Re: [Bitcoin-development] [PROPOSAL] Merkle tree of unspent transactions (MTUT), for serverless thin clients and self-verifiable prunned blockchain.
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
0 siblings, 0 replies; 2+ messages in thread
From: Elden Tyrell @ 2012-01-29 18:40 UTC (permalink / raw)
To: bitcoin-development
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
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2012-01-29 18:40 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
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 is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox