Bitcoin Forum
December 08, 2016, 10:07:39 PM *
News: Latest stable version of Bitcoin Core: 0.13.1  [Torrent].
 
   Home   Help Search Donate Login Register  
Pages: « 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 [16] 17 18 19 20 21 22 »  All
  Print  
Author Topic: Ultimate blockchain compression w/ trust-free lite nodes  (Read 68613 times)
ThomasV
Legendary
*
Offline Offline

Activity: 1722



View Profile WWW
May 12, 2013, 05:01:55 PM
 #301

I don't think so.  If you are at ABCD and it has only 3 children, "ABCDE" "ABCDP" and "ABCDZ", there's still only 3 seeks.  You seek for "ABCDA", and the iterator ends up at ABCDE (which is the first element equal-to-or-greater-than your seek value).  So you know that's the first child, and that there's no point in seeking for "ABCDB", "ABCDC" etc.  Then your next seek is "ABCDF", which puts you at "ABCDP".  Rinse and repeat.
oh indeed, I did not see that. thank you

Electrum: the convenience of a web wallet, without the risks
1481234859
Hero Member
*
Offline Offline

Posts: 1481234859

View Profile Personal Message (Offline)

Ignore
1481234859
Reply with quote  #2

1481234859
Report to moderator
Advertised sites are not endorsed by the Bitcoin Forum. They may be unsafe, untrustworthy, or illegal in your jurisdiction. Advertise here.
1481234859
Hero Member
*
Offline Offline

Posts: 1481234859

View Profile Personal Message (Offline)

Ignore
1481234859
Reply with quote  #2

1481234859
Report to moderator
lunarboy
Hero Member
*****
Offline Offline

Activity: 544



View Profile
May 13, 2013, 04:58:00 PM
 #302

Fascinating. Logical. Influential...... Open source development such a privilege to watch.
maaku
Legendary
*
expert
Offline Offline

Activity: 905


View Profile
May 13, 2013, 08:36:10 PM
 #303

Since @etotheipi is occupied for the next half-year and since I have a large interest in this proposal, I am offering my services to help make it happen. I have created a new thread with specific details of my proposal:

https://bitcointalk.org/index.php?topic=204283.msg2135237#msg2135237

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
2112
Legendary
*
Offline Offline

Activity: 1708



View Profile
May 14, 2013, 05:19:45 AM
 #304

I originally wrote this post couple of days ago in response to another humorous/pithy comment. However the original comment got deleted before I finished editing it and it made almost no sense afterwards. It appears that this thread is now approaching its end and I decided to post re-edited version of it to put it in a permanent public record.

The original Greenspun's tenth rule of programming states:
Quote
Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp.
I propose a modified version of it pertaining to Bitcoin and other blockchain-based cryptocurrencies:
Quote
Any sufficiently complete attempt at implementing Bitcoin will contain an ad hoc, informally-specified, bug-ridden, slow implementation of half of MUMPS.

I'm trying to suggest that MUMPS should be used to implement Bitcoin. I'm just observing that there will be tremendous amount of work expended to re-invent and re-implement one key feature of MUMPS: larger-than-core sparse hierarchical tree storage with all the expected ACID properties.

For those who are interested why the technology from circa 1975 outperforms all previous attempts at blockchain storage (both full and pruned) I have the following links:


It is a shame that I don't know of any open-source software that is compatible with the MIT license and other requirements specific to Bitcoin.

Please comment, critique, criticize or ridicule BIP 2112: https://bitcointalk.org/index.php?topic=54382.0
Long-term mining prognosis: https://bitcointalk.org/index.php?topic=91101.0
Peter Todd
Legendary
*
expert
Offline Offline

Activity: 1064


View Profile
May 14, 2013, 05:33:11 AM
 #305

In case anyone misses 2112's remarkably obscure troll with regard to MUMPS, see this: http://thedailywtf.com/Comments/A_Case_of_the_MUMPS.aspx

Sukrim
Legendary
*
Offline Offline

Activity: 1848


View Profile
May 14, 2013, 10:33:22 AM
 #306

I might start mining again if this gets implemented! Smiley
Also as long as there is a UTXO block merge mined every few hours or even days this is still much better/faster than the current situation with checkpoints + the bootstrap.dat torrent.

By the way, thanks for not rushing this and debating about proper solutions longer as this is in my opinion one thing that can drive forward bitcoin adoption a LOT more than another porn site accepting them! The frustration and confusion when starting a full client for the first time for sure is one of the major reasons why this is still seen as a "geek tool". It is important to get this right on the first try.

https://bitfinex.com <-- leveraged trading of BTCUSD, LTCUSD and LTCBTC (long and short) - 10% discount on fees for the first 30 days with this refcode: x5K9YtL3Zb
Mail me at Bitmessage: BM-BbiHiVv5qh858ULsyRDtpRrG9WjXN3xf
maaku
Legendary
*
expert
Offline Offline

Activity: 905


View Profile
May 15, 2013, 06:58:08 PM
 #307

I don't know all the details of the proposals, but let me explain it the way I see it and then you people tell me what I'm missing.
I propose "trust levels" as the name. For simplicity, I'm assuming the root of the UTXO tree is part of the headers, not just merged mined, but we can argue about that later.

Trust level 2: The current Simplified payment verification.

Trust level 1: We define a distance in blocks to the past which is secure for the node to assume won't suffer a reorg, say 1000 blocks ago and call it the "pseudo-checkpoint". He downloads the full UTXO tree that was in block (currentHeight-1000), the UTXO tree in the pseudo-checkpoint. He downloads 1000 blocks and reproduces the current UTXO tree from the the old one. For a given unspent output, he can provide its full merkle branch until coinbase OR the pseudo-checkpoint if the coinbase is older.

Trust level 0: The node downloads the rest of the chain, being able to verify that the UTXO tree from the pseudo-checkpoint he used was correct, and he will be able to always provide full output markle branches to their coinbases from now on.

You could download the whole chain from the top to the bottom and optimistically start assuming the last UTXO tree was legit, then validate it with the previous one and the transactions of last block, and so on to the genesis. Effectively decreasing the pseudo-checkpoint height from last block created to genesis.
Once you've achieved trust 0, nothing forces you to store the whole chain. You can then set another pseudo-checkpoint, only being afraid of reorgs and/or not being able to provide long enough output chains.
In fact, you can go to trust level 1 or even trust level 0 to operation level 2 if you want. You can download the whole chain but then only keep the branches of your own outputs.

Nodes would have more room for specialization. I think there will be always "librarian nodes" ala block explorer. distributing the whole history. But I think their lack is what worries @Sukrim.

After this I think you can only improve the storage of the UTXO (and posibly their full merkle brach) using caches.

Is this basically what we're talking about or am I lost and the name "trust levels" is awful?

@jtimon, you are essentially correct although what you describe is only part of the story. I think “trust level” is an appropriate term. Here's how I would lay them out:

Level 4: Electrum-like client/server. Keys are stored on the client, the but the client trusts the server for information about the unspent-TxOut set. This is only marginally better than sticking your coins on a server-side wallet. I would never make a general recommendation to operate at this level unless you own both the server and the client and have a secure, authenticated connection between the two.

Level 3: Simplified payment verification. Client trusts the “longest” (most work) chain, but reads and processes every block. The client must scan the contents of every block more recent than the oldest address in its wallet in order to be sure that its record of unspent wallet outputs is correct. BitcoinJ has some optimizations not mentioned, but only because they make simplifying assumptions about the circumstances under which wallet transactions might be generated. It remains true that you must touch every transaction of every block that might have a wallet input or output within it.

Both of the above levels will be completely obsoleted by this proposal.

Level 2: The client downloads the “longest” (most work) meta-chain, and retrieves the block of data associated with the current head of the meta-chain. This data includes the Merkle hash of the unspent-TxOut trie and it's associated block height. The client then queries any node exposing the correct service bits about its wallet addresses, retrieving either the associated transaction outputs with proof-of-inclusion, or a negative proof showing that no such output exists in the trie. I call this enhanced simple payment verification, or SPV+, and operates trust-free at an economic security level equal to the hash power of the merged-mined meta-chain.

Level 1: The meta-chain data block probably will include other information, such as a deterministic bittorrent infohash of the serialized unspent-TxOut trie and blockchain checkpoint data. The client downloads the unspent-TxOut trie torrent and verifies that its root hash matches what was in the meta-chain. It then reconstructs the information necessary to do full-block validation from that point forward. The initial synchronization is at the meta-chain level of economic security, but after that it would take a 51% attack on bitcoin itself to subvert a client at this level.

Level 0: The client either verifies the entire chain forwards from the genesis block, or backwards up to the most recent checkpoint as @jtimon described. It is now a fully-validated client operating exactly as the Satoshi client does today, and with the same level of security.

There is also a “0.5” mode that might be good enough for most people: only verify backwards long enough to satisfy your own security requirements (a configurable number of blocks, perhaps as a command line parameter).

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
socrates1024
Full Member
***
Offline Offline

Activity: 125


Andrew Miller


View Profile
May 21, 2013, 10:41:33 PM
 #308

IMO your 3-point plan is missing out on the best aspect of having a Merkle UTXO. It's unnecessary for Level 2 to be a weaker security "SPV+", it can still do Full Validation even without having to do download the whole chain. The reason why is that you can check EVERY TX IN A BLOCK (not just ones involving your wallet) just by knowing the root hash of the UTXO and requesting short checkable proofs from untrusted nodes.

At one point I convinced etotheipi of how this works, and he basically said he hadn't realized that it would be possible. https://bitcointalk.org/index.php?topic=101734.0 I made a reference implementation using a redblack tree but it would be totally fine to substitute a merkle patricia trie for it.

amiller on freenode / 19G6VFcV1qZJxe3Swn28xz3F8gDKTznwEM
[my twitter] [research@umd]
I study Merkle trees, credit networks, and Byzantine Consensus algorithms.
maaku
Legendary
*
expert
Offline Offline

Activity: 905


View Profile
May 22, 2013, 12:07:24 AM
 #309

I'm not doubting that it's possible, just wondering if you'd actually be gaining anything. I suppose the application would be for devices with suitable bandwidth but very tight memory constraints, like hardware wallets?

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
etotheipi
Legendary
*
expert
Offline Offline

Activity: 1428


Core Armory Developer


View Profile WWW
May 22, 2013, 05:21:37 AM
 #310

I'm not doubting that it's possible, just wondering if you'd actually be gaining anything. I suppose the application would be for devices with suitable bandwidth but very tight memory constraints, like hardware wallets?

If I understand (remember) correctly, Socrates1024 is making the point that someone could theoretically do mining without having the full blockchain.  All they need is the root hash of the last block, and to see the full blocks coming in.  This is because you can verify that the UTXOs being spent by the new transactions are unspent with a simple branch request from a peer.

Right now, if you wanted to do this... you can't.  You can easily prove that a UTXO once existed, but you don't know it was spent since then without downloading all the blocks since then and verifying no spends.  But with this UTXO tree structure, you can prove both inclusion and exclusion of UTXOs on any given block.  It may not be that big of a distinction today, but perhaps in the future when you require TB of storage, that could make a difference. 

But I do question how much is gained -- since only some upper limits ratio of the network could operate like this without being extremely burdensome on the actual full nodes.  And I'm not confident that these lite nodes could expect reliable branch information from each other even if they all "agreed" to hold, say, 1% of the full thing.  I certainly wouldn't want to risk my miner becoming idle because it's having trouble finding some subset of the tree (or large subsets of the network going dark for that reason)

Have I understood this properly?



One thing that has come up before, is that I'd like to see an additional piece of information added to the header:  fast-forward data each block.  sipa has already implemented undo data because you need it in the event of a reorg, and I tried to convince him he might as well include fast-forward data, because you save some 75% bandwidth on transmission of block data (to those that request it).  If the OutPoints-removed-and-TxOuts-added data is organized into a merkle tree, then that root could be included in the merkle tree, and such UTXO-only nodes would be able to avoid pulling whole blocks.  sipa didn't like the complexity for a "constant" factor, but I think 75% is worthy constant factor.  Unless I'm missing something...

Founder and CEO of Armory Technologies, Inc.
Armory Bitcoin Wallet: Bringing cold storage to the average user!
Only use Armory software signed by the Armory Offline Signing Key (0x98832223)

Please donate to the Armory project by clicking here!    (or donate directly via 1QBDLYTDFHHZAABYSKGKPWKLSXZWCCJQBX -- yes, it's a real address!)
TierNolan
Legendary
*
Offline Offline

Activity: 1050


View Profile
May 22, 2013, 09:58:24 AM
 #311

If I understand (remember) correctly, Socrates1024 is making the point that someone could theoretically do mining without having the full blockchain.  All they need is the root hash of the last block, and to see the full blocks coming in.  This is because you can verify that the UTXOs being spent by the new transactions are unspent with a simple branch request from a peer.

I think providing a way to pre-package blocks would help here.  You send the block you are mining in advance (subject to spam protection).

Another option is to allow transactions to be packaged.  You send a hash + 64 transactions.  Later, you can include all 64 just with the header hash.

1LxbG5cKXzTwZg9mjL3gaRE835uNQEteWF
socrates1024
Full Member
***
Offline Offline

Activity: 125


Andrew Miller


View Profile
May 22, 2013, 01:09:59 PM
 #312

I'm not doubting that it's possible, just wondering if you'd actually be gaining anything. I suppose the application would be for devices with suitable bandwidth but very tight memory constraints, like hardware wallets?

Sure, hardware wallets are an example. You could plug it in to an untrusted host computer that has already downloaded the proof data. Or even a mobile phone wallet, where you don't have much bandwidth during the day so it's SPV, but maybe it could sync up with the network overnight when it's around an untrusted wifi.

amiller on freenode / 19G6VFcV1qZJxe3Swn28xz3F8gDKTznwEM
[my twitter] [research@umd]
I study Merkle trees, credit networks, and Byzantine Consensus algorithms.
LvM
Full Member
***
Offline Offline

Activity: 126


View Profile
May 22, 2013, 11:57:04 PM
 #313


@etotheipi:
Is it REALLY impossible for each client
"to download just the unspent-TxOut list for each address in their wallet, and verify that list directly against the blockheaders."
...quickly and easily without your proposed complications with alt/meta-chains ?

I cannot believe that. If so, this seems besides the "Cash/Change" concept*) another remarkable bug at the lowest level.

*) CASH/CHANGE simulation vs. GAAP fundamentals
https://bitcointalk.org/index.php?topic=211835

BTC violates GAAP, result a MESS  https://bitcointalk.org/index.php?topic=211835.0
Anforderungen an eine PROFESSIONELLE BTC-Anwendung https://bitcointalk.org/index.php?topic=189669
BANKGEHEIMNIS mit BTC gleich NULL!? https://bitcointalk.org/index.php?topic=188383 Antwort: Ja, wenn man nicht höllisch aufpaßt.
d'aniel
Sr. Member
****
Offline Offline

Activity: 461


View Profile
May 23, 2013, 12:36:32 AM
 #314

I'm not doubting that it's possible, just wondering if you'd actually be gaining anything. I suppose the application would be for devices with suitable bandwidth but very tight memory constraints, like hardware wallets?

Sure, hardware wallets are an example. You could plug it in to an untrusted host computer that has already downloaded the proof data. Or even a mobile phone wallet, where you don't have much bandwidth during the day so it's SPV, but maybe it could sync up with the network overnight when it's around an untrusted wifi.
The big value of validation-without-the-blockchain seems to me to be when it's combined with the fraud proof/challenge idea, where an SPV node can reject invalid blocks upon receiving a short proof or challenge that proves the block was formed incorrectly (e.g. nonexistent txin, double spend, invalid coinbase).   It turns out all important cases of fraudulently formed blocks can be covered by these - including cheating on the block reward, after a simple change to the way the Merkle trees are constructed.  This would greatly increase the trust model of an SPV node, under the assumption that it's connected to at least one well-connected, honest peer.

The more honest nodes there are auditing blocks and forming these fraud proofs/challenges, the better chance SPV nodes will promptly and reliably receive them.  This is where the validation-without-the-blockchain idea really shines IMO, since it allows resource constrained nodes to contribute to overall network security, but without biting off more than they can chew - they only partially validate blocks.  I tend to think of this as the "correct" way to preserve decentralization while scaling up block sizes.
jtimon
Legendary
*
Offline Offline

Activity: 1246


View Profile WWW
May 23, 2013, 11:42:21 AM
 #315

@maaku, you said yesterday we left an open conversation more or less here:

maaku: Metachain miners could get lazy and not maintain the indexes properly.
jtimon: If the indexes are in the main chain there wouldn't be such a problem.
maaku: In the main chain the thing gets worse.
jtimon: How that's possible? blocks with wrong indexes will be orphaned.

Also, about socrates proposal. I think it's also useful for custom assets that can be issued, used and destroyed. New miners (or users) don't really care about these destroyed assets.

@LvM
I think the purpose of the "change" approach is to make obfuscation easier. You could do GAAP and maintain a sequence number for the transactions from each account like Ripple does.
You claim that would reduce the size of the chain by half. But how do you know how many keypairs will people create to obfuscate their finances?
Another problem is that you have to maintain a list of "existent accounts" forever. If miners forget about them and then the users uses it again (not a good idea on his part), the sequence for that keypair would be reset and anyone can "replay" the old transactions if he has them. That's why you can't destroy accounts (funded keypairs) in Ripple. You may say "there's no replay, all BTC funds will be gone". Well, I'm thinking about people reissuing custom assets from "resurrected" accounts.
Well, probably we should go to your thread to discuss this anyway...

2 different forms of free-money: Freicoin (free of basic interest because it's perishable), Mutual credit (no interest because it's abundant)
maaku
Legendary
*
expert
Offline Offline

Activity: 905


View Profile
May 23, 2013, 04:13:45 PM
 #316

@maaku, you said yesterday we left an open conversation more or less here:

maaku: Metachain miners could get lazy and not maintain the indexes properly.
jtimon: If the indexes are in the main chain there wouldn't be such a problem.
maaku: In the main chain the thing gets worse.
jtimon: How that's possible? blocks with wrong indexes will be orphaned.

Actually we should let gmaxwell respond to this, as I was really just relaying his concerns expressed to me at the conference. I think perhaps he is considering the case where the information is included in the bitcoin coinbase, but not actually enforced as a protocol rule?

Also, about socrates proposal. I think it's also useful for custom assets that can be issued, used and destroyed. New miners (or users) don't really care about these destroyed assets.

True except for the miner part. You can fork the blockchain just as easily with invalid asset transactions.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
jtimon
Legendary
*
Offline Offline

Activity: 1246


View Profile WWW
May 26, 2013, 02:37:43 PM
 #317

Actually we should let gmaxwell respond to this, as I was really just relaying his concerns expressed to me at the conference. I think perhaps he is considering the case where the information is included in the bitcoin coinbase, but not actually enforced as a protocol rule?

I'm really interested. If the indexes are enforced by the protocol I see no problem.

Also, about socrates proposal. I think it's also useful for custom assets that can be issued, used and destroyed. New miners (or users) don't really care about these destroyed assets.

True except for the miner part. You can fork the blockchain just as easily with invalid asset transactions.

I don't understand.
If I validate the full chain leaving out the ones that nobody says still exist and only download the hashes of the transactions involved...
Never mind. Once a death asset appears with living assets in the same transaction you have also to validate the full asset, recursively.
So probably miners need to validate death assets anyway, am I thinking this straight or did I got lost on recursion?

Anyway, asking for the full proofs on the whole current UTXO would let you mine at level 1.

1) You ask for the longest header chain.

2) You ask for the UTXO

3) You ask for the full proofs of all outputs, not just yours. Maybe starting with yours.

4) Maybe in parallel, or only with wifi, or whatever, you download the whole chain from the in-chain signed torrent.
You validate everything until "your checkpoint" independenlty.

What happens when there's a reorg?

1) You change "your checkpoint" to the last common block so you ask for the that block's UTXO

2) You ask for the new UTXO at the top

3) You ask for the missing proofs you lack for the new UTXO.

Hummh, maybe GAAP is also better for reorgs...
And in fact I already solved the "immortal accounts" on the new Ripple forum by substituting the sequence number for the hash of the previous transaction from that account.
LvM is right, GAAP and a ledger instead of the UTXO like Ripple would make things much simpler.
Is there any obvious arguments in favor of the change-like design I am missing?
Is there anything that makes the UTXO cooler than a simple ledger?
Anyway, that's too big of a change, but since nobody answered in LvM's thread and I'm doubting...

2 different forms of free-money: Freicoin (free of basic interest because it's perishable), Mutual credit (no interest because it's abundant)
maaku
Legendary
*
expert
Offline Offline

Activity: 905


View Profile
May 26, 2013, 04:28:33 PM
 #318

I got confused following your logic, but the conclusion is right. Miners must validate everything or the whole system falls apart.

As for ledger vs. UTXO, these UTXO indices give the advantages of a ledger (being able to look up final balances, for example), while maintaining an underlying block structure. But that connection to the underlying system is important - you still need it if you are going to create new transactions, for example. Does that make sense?

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
aaaxn
Full Member
***
Offline Offline

Activity: 126


View Profile
May 26, 2013, 08:04:42 PM
 #319

Another problem is that you have to maintain a list of "existent accounts" forever. If miners forget about them and then the users uses it again (not a good idea on his part), the sequence for that keypair would be reset and anyone can "replay" the old transactions if he has them.
You can simply use block number of last account operation. There is no way you get same sequence twice this way.

As for ledger vs. UXTO I think all this concept of outputs and scripts doesn't make sense and should be dropped and replaced with account balances and account types (EG. multisig accounts)
maaku
Legendary
*
expert
Offline Offline

Activity: 905


View Profile
May 26, 2013, 08:10:43 PM
 #320

Another problem is that you have to maintain a list of "existent accounts" forever. If miners forget about them and then the users uses it again (not a good idea on his part), the sequence for that keypair would be reset and anyone can "replay" the old transactions if he has them.

You can simply use block number of last account operation. There is no way you get same sequence twice this way.

As for ledger vs. UXTO I think all this concept of outputs and scripts doesn't make sense and should be dropped and replaced with account balances and account types (EG. multisig accounts)

What doesn't make sense?  Outputs and scripts is how bitcoin works.

I'm an independent developer working on bitcoin-core, making my living off community donations.
If you like my work, please consider donating yourself: 13snZ4ZyCzaL7358SmgvHGC9AxskqumNxP
Pages: « 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 [16] 17 18 19 20 21 22 »  All
  Print  
 
Jump to:  

Sponsored by , a Bitcoin-accepting VPN.
Powered by MySQL Powered by PHP Powered by SMF 1.1.19 | SMF © 2006-2009, Simple Machines Valid XHTML 1.0! Valid CSS!