Light clients will not need to download blocks with inputs matching their address, let alone trust a full node to do it correctly. See etotheipi's proposal for zero-trust light clients using merkle trees. https://bitcointalk.org/index.php?topic=88208.0 The only remaining challenge for a lite client is (correctly) selecting the largest valid chain, which is what I am discussing.

Just to be clear, the additional data I am recommending is a single additional hash per block.

kjj:

Suppose the back-link from the current head looks like 000xxx (value 3). We also include an 'up'-link to the parent of the most recent block that looks like 0000xxxx (value 4). If you skip to that parent block, then it will have an 'up'-link to the parent of a block that looks like 00000xxxxxx (value 5). And so on, until you get to the parent of the largest block for which there's no up-link.

Suppose you start at that largest block, which looks like 00000xxxxx (value 5). It contains an up-link, either to a previous block with value 00000xxx (value 5), or to one with lower value. You can skip your way to the highest-value hash in every sub-interval of history.


Ben-abuya: right, this pretty much solves the same problem except with O(1) additional storage per block rather than O(log N).

Since you are busy in another thread about variable-difficulty blocks, I'd like to point out my approach to that here, although it will take a few steps to show how it relies on the hash-value-highway to be viable.

The "difficulty" of a block could be set by each individual miner who "bids" on the difficulty they want to get. So a winning block at difficulty 4 would be H(difficulty: 4 zeros || nonce || header) -> 0000xxxxxxxxx. Instead of taking the largest chain, we would take the chain that has the largest sum-difficulty (according to the difficulty bids, not the actual hash value).

There should be a disincentive for miners to spam the network with low-difficulty blocks. Each miner should have stake in the game - the miner himself could place down a bet, effectively a fee for the storage of his block header. If his block is accepted, then he gets the money back. If his fork gets swept up by a higher-difficulty fork, then he loses his bet and the fees he would have earned.

The hash-value-highway makes it efficient to evaluate the sum-difficulty of a fork, and also to merge forks by cherry picking valid transactions. Long chains of low-difficulty blocks will tend to get preempted by higher-difficulty forks. If each transaction includes a 'minimum difficulty', then you'll only be included in the difficult blocks which are less likely to be reordered.

I don't expect this part of the explanation to be totally clear, especially since I haven't elaborated on how a fork is 'swept up' by the main chain, but I will get to that later. But since you've been working on similar ideas, I think you might have the right intuition for how this works.

Sure, it would also work as an overlay. It's also something an alt-chain could experiment with.

The problem you're talking about where clients need to validate the entire chain in order to see their transactions - that is already solved (conceptually) using merkle trees. Read etotheipi's proposal for that here: https://bitcointalk.org/index.php?topic=88208.0 Of course, this only works if the client is able to correctly choose the right 'head'. That's what my current proposal is about.

Here's the next thing cool thing you can do with a high-value-hash highway: quickly discover exactly where two blockchains meet at a fork, even if the chains are very large and have many difficulty changes.

Quickly skip up to the highest-value-hash in each chain. If the chains share the highest-value-hash, then the fork point is more recent than that block. If one chain contains a higher-value hash than the other, then the fork point is behind that block. You can use a bisection search to find the true fork point.


I suppose I'm not being too clear on what the overarching goal is with this, so let me just say what my motivating principles are:
- The blockchain should eventually converge to a single correct chain, regardless of the network behavior and changes in cpu power over time (except for a persistent 34% adversary, which is unavoidable)
- Global parameters (like 10 minutes) should not need to be hard coded, but instead should automatically adjust according to demand and availability.

I'm going to build the argument that this is all possible using just a single additional back-link per block.

Lite clients need to process every header of the correct chain. However, if a lite client is presented with several head nodes, only one of which is truly the largest, it would be nice to quickly skip iterating through the rest.

Here's a simple proposal. Let me define the 'value' of a block as the number of leading zero bits in its hash. For every block, we already include the hash of the previous block. I propose to also include the hash of the most recent block with higher value than the previous.

This data structure could be considered a 'merkle skip list'. A skip list lets you traverse in either of two directions - 'backwards' or 'up'. This would let you quickly follow a chain of hashes up to the highest-value we've ever found.

This is a trivial modification to the current block chain, yet the significance of this data structure is absolutely staggering. I will just describe one application for now.

--- Proposal for "eventually zero-trust" clients ---

How does a lite client know which block chain is the largest? By iterating through the whole chain from front to back? Ick!

Using the high-value-hash highway, you can skip 'up' to the largest hash found in O(log N) effort. That immediately gives you a rough estimate of how much work was performed. You can now branch-and bound to gradually improve your estimate. From the largest block (i.e., the 'top'), skip backwards, and then up to the top again. You're now at the highest-value-hash from the era that preceded the current-highest. You can traverse the 'proof-of-work' content of a chain directly, with the most-informative hashes first and working your way down. You could quickly select the largest out of a pool of potential block chains without having to iterate through them all.

A lite client could easily use the high-value-hash highway to determine the largest chain very quickly and begin using it. The estimate improves as the process continues, and if the lite client eventually gets around to validating the whole thing, then that's great.

It's important to check the work first, and only then to validate. This should apply to the entire block chain as well as to individual blocks.


--- Experiment ---

I can show you a neat trick. What's the highest value for a hash in the current blockchain? Write that number down. Now, count how many blocks in the chain have that value or higher.

You probably counted '1', or at least very close to it.

This trick works regardless of how much time has passed, how fast our computers run, how connected our network is, how the difficulty has adjusted over time, etc. It is completely scale invariant. The overall shape of the hash highway would be roughly scale invariant as well. See also: https://en.wikipedia.org/wiki/Benford's_law

[EDIT] I finally got around to running this experiment, and it turned out I was correct. I also produced visualizations of the "overall shape of the hash highway," which I'm copying here because I think this illustration is very important. Read this post for an explanation.

Perhaps one reason to prefer a balanced binary tree is that if you want to store a snapshot of every previous blockchain, you only have to store the differences. There is a "Persistent Authenticated Datastructure" that would let you handle roll backs efficiently.


(This image is from "Persistent Authenticated Dictionaries and their Applications" by Anagnostopoulos Goodrich and Tamassia http://cs.brown.edu/people/aris/pubs/pad.pdf )

I do not know if this is possible with tries.

Only an additional block header would need to be stored. There's no need to validate the redundant blocks, they could just be blank proofs-of-work. If someone really wants to do unpaid overtime to increase the difficulty then it's just as well.

I'm not totally sure about the number 2 though, so I'll think about that a bit more.

The important idea is to adjust the puzzle difficulty in order to maintain a stationary ratio of chain length to number of runners-up.

What's the optimal setting for the puzzle difficulty? Is 10 minutes between blocks correct?

Ideally, there should be one stale block for every fee-earning block. This strikes the best balance between two performance goals:
- (Latency) the chain should grow quickly
- (Convergence) the network should settle quickly

Here's an easy way to maintain the proper difficulty setting. Miners should include in each block a set of novel stale blocks with shorter height. For every fee-winning block, we decrease the difficulty. For every stale block, we increase the difficulty. It's clear that in the steady state with constant hashpower, this scheme results in two proofs-of-work for every block in the chain.

Notice it would no longer be necessary for miners to report timestamps, and the parameter "10 minutes" would be eliminated altogether. The only remaining parameter is a 'gain' for how much to adjust the difficulty per block.

tl;dr:  First place wins a prize. Runners-up receive an honorable mention.

[edit] I originally used the wrong term "orphan block" when I meant "stale block", thanks sipa

"Pruning the trees" is a red herring. Here is another way of explaining what this proposal is about.

Bitcoin already supports a Zero-Trust validation technique that is also 100% pruned - it only requires storing a single O(1) block hash. The problem is that it's blatantly inefficient. What we are doing with Merkle trees is altering the blockchain to make this technique, which is inherently fully pruned and zero-trust, more efficient.

[Inefficient O(N), Zero-trust, 100%-pruned technique] (It's just a counter example, bear with me) The entire bitcoin blockchain is already represented by the current block hash. Every client, even the lightest of light clients, stores the current block hash. If you know your current block hash, then you can't be fooled about any of the data in the chain. For example, if you want to check that a particular txoutput hasn't been spent, you iterate backwards through the blocks all the way to that transaction, checking that there's no previous transaction that spends it.

This isn't efficient. It literally involves processing the whole damn chain each time you validate a transaction. So, current light clients certainly don't do this - instead they have to trust a helper to validate that the transactions aren't double-spends. Full nodes have an easier time because they have the storage available to maintain an indexed database of unspent txouts.

[Merkle trees O(log N), Zero-trust, 100%-pruned] What we are all proposing in various ways is to alter how the blockchain history is represented in the current block hash. In addition to the previous block data, we will also include a 'snapshot' of the unspent txoutputs database in each block hash. This snapshot is the root of a Merkle tree, which gives us little shortcuts so we can validate a transaction much more efficiently, O(log N) per validation.

For anyone interested in understanding Ripple better, I know a handful of academic papers proposing the same idea with variations:
   - [1] is most similar to Ripple or OpenTransactions, in that each Node creates its own currency and only accepts currencies of adjacent nodes that it 'trusts'. The point of this paper is to show that for some reasonable models of transaction behavior, 'bankruptcy' is isolated and doesn't spiral out of control.
   - [2] is about 'insurance,' rather than credit. Each node 'vouches' for the adjacent nodes that it trusts by putting up some collateral.
   - [3] is also about self-issued currency, except the units are related to storage utilization in a peer-to-peer filesharing network. Nodes only accept currency from adjacent nodes they trust.

All of these have the same basic structure as Ripple. There are three key features:
   a) "Local" assessments of trust. Alice is never left holding debts/credits to a stranger, instead she indicates ahead of time who she's willing to have such a relationship with, e.g. with Bob but not Carol.
   b) Indirect (transitive) transactions. Alice can pay Carol without presuming or creating any trust/relationship between them. Instead, Bob acts as a conduit.
   c) Non-scarce self-issued on-demand currency. Whether it's credit, insurance collateral, trust, or a promise to buy a beer, these transactions are about a fundamentally different currency that is unlike gold: it is not money, it is not universal, and it is not scarce. Alice can inflate her IOU currency at will, but Bob is only vulnerable if he extended a line of credit to her - and then he's only vulnerable up to the 'credit limit' he indicated.

This leads to a very simple web-like topology that models how humans actually socialize! If I invite you to my party, and you bring your asshole friend who pisses on my carpet, then you're the one that needs pay to get my floor cleaned. That is a transitive economic/trust relationship.

Again, Ripple credit is unlike money and therefore unlike BTC: it's not scarce, it's not universal, and it depends on an out-of-band assessment of trustworthiness. So, a Ripple credit won't be as broadly valuable as a Bitcoin. But, since the Ripple transaction mechanism makes transitive exchanges efficient, a Ripple credit is much more broadly useful than an ordinary static debt between two parties. Example: If I owe you a beer, then maybe you'll get a beer. But if I owe you a beer and post it on a Ripple network, then it might help one of your friends buy a used video game from one of my friends. People _do_ establish such trust/credit relationships, and Ripple is about extending these to facilitate exchange within a wider network of indirect trust. The overall economic effect is that we make better utilization of latent trusting relationships in order to increase cooperation and exchange.

I hope this post brings a bit of clarity about the purpose of Ripple and doesn't just add noise. May this thread bear fruitful discussion!

[1] Pranav Dandekar, et al. "Liquidity in Credit Networks: A Little Trust Goes a Long Way" http://www.stanford.edu/~ppd/papers/cn-liquidity.pdf
[2] Dimitri do B. DeFigueiredo and Earl T. Barr. "TrustDavis: A Non-Exploitable Online Reputation System" http://www.cs.ucdavis.edu/~defigued/index_files/trustdavis.pdf
[3] D Levin, et al. "Making Currency Inexpensive with iOwe" http://people.csail.mit.edu/katrina/papers/iowe.pdf

Combining Bitcoin with Ripple is a very important idea. The "Ripple" is an abstract kind of transaction involving a chain reaction / bucket brigade / relay of value between multiple people. The basic Ripple goes like this:
      Alice pays Carol via Bob. Before the transaction, Carol owed Bob, but now Alice owes Bob instead, and Carol's debt is canceled. Bob had also previously granted Alice a 'line of credit' allowing her to do this.

Again this is an abstract transaction, the units of value are arbitrary and may as well be denominated in "BobBux" or "Beers from Bob" or the like. There are potentially many ways of implementing this, mostly varying by whether a central party manages the accounts and whether or not the funds are frozen in escrow. This is the technical challenge, it's about an atomic commit for multiple transactions.

Notice that in the above example, Bob was central to the transaction, yet he played a passive role. Alice was able to initiate and commit the transaction all on her own, as Bob had already granted her the capability to do so. There are potentially several middle parties, perhaps Bob1, Bob2, Bob3. This is a truly different structure than Bitcoin, since it requires storing both the credits (which are like account balances) and the credit lines (which are like potential credits or capabilities).

As far as I can tell, Mike Hearn's proposal and cjp's proposal are two different ways of performing the commit, although both of them require the passive parties like Bob to play an online role. They both involve collecting signatures from everyone involved in the transaction, including the intermediaries. Both involve the potential for funds to be held up in Escrow, at least temporarily, resulting in loss of liquidity.

CJP's proposal:
   If I understand this correctly, the central novelty of this paper is that the initiator of a Ripple transaction can post a Bitcoin bounty to be given as a reward to the first party that publishes the N valid Ripple signatures (N=5 means Alice, Bob1, Bob2, Bob3, Carol, all need to sign). The BTC bounty has a timeout, so if the transaction fails it can be reclaimed by the initiator. Could you elaborate on what model of rationality might be used to show that this incentive scheme makes a difference between a failed Ripple transaction and a success? Except for this incentive scheme, the Ripple transactions themselves are handled out of band - in particular, not on a blockchain.

Mike Hearn's proposal:
   This is about implementing Ripple in an alternate blockchain. But it seems to require that each transaction is committed separately. Not only must each party respond online, including the intermediaries, but there is also no guard against a partially committed Ripple.


Open question:
    Can we use a blockchain to implement Ripple with the following desirable qualities?
     - Once a line of credit is extended, it can be exercised (spent) without further intervention from the creditor. (Intervention from the creditor may still occur, though, e.g. to revoke the line of credit)
     - Atomic commits: Multiple transactions (from Alice to Bob1, Bob1 to Bob2, Bob2 to Carol) should be processed in a single transaction update, without any escrow period.

Notice that if the lightweight Client runs the Merkle tree scheme I described, it can rejected double-spends, invalid scripts, etc. Even without needing to store a copy of the unspent outputs.

Instead, the Client receives each block header, as well as O(M log N) of verification data (paths through the Merkle tree). This way, the Client can check each transaction against the database, as indicated by the current root hash. Only a full node acting as an untrusted helper needs to store the entire unspent outputs database, in order to generate the verification data.

One of the neat things about a Merkle search structure, rather than just an arbitrarily-ordered Merkle tree, is that you can prove that a key is not in the database. Even with a typical Merkle tree, like the current blockchain, it would require a linear effort to prove that a transaction doesn't exist - assuming all you have is an O(1) root hash, and you don't trust anyone!

Even more generally, you can do a verified 'range query' for only O(M log N) effort (where M is the number of results, N is the size of the tree). If you store each unspent-coin in a binary search tree, ordered by the address, then you can ask an untrusted server to give you a snapshot of all the spendable coins associated with that address. There's no way for them to omit any.

Let me try to describe the scenario how I prefer, since it's hard to keep track of the terms otherwise. There are two parties, the Lite-Client (Client) and the Helper (Server). The goal is for the Client not to have to trust the Server, but for the Server to store all the data. The Client only ever needs to store (like, on disk) a constant O(1) amount of state - the root hash. In order to decide what root hash to use, the Client will have to rely on the proof-of-work to recognize the most recent block.

If the Client asks the Server for the list of unspent-coins matching a target address, he receives two or more O(log N) paths through the Merkle tree. The first one is path is to the element with the largest address (lexical ordering) that is smaller than the target address. The last one is a path to the smallest element with a larger address. If there were no transactions matching the target, then these two elements will be adjacent. In any case, the Client iterates through the paths he receives, at each step checking that the paths are adjacent in the tree (and, of course, that the hashes are consistent and lead to the root).

[edit]I hope this turns into a Merkle trees megathread![/edit]

There are two kinds of orderings here. First is the order in which updates are made to the Merkle trees. Each block is ordered, and within a block transactions are ordered, and within a transaction the txIns and txOuts are ordered. To update your Merkle trees as the result of a bitcoin transaction, you remove all the inputs, and insert all the new outputs. Everyone should be able to do this in the same order, right?


Now, within a Merkle tree, the order is determined by a key. Think of each Merkle tree as a database index. We would like to have at least two kinds of indexes, which means maintaining two instances of the Merkle tree:

1) TxOuts are identified by the transaction hash and an index within that transaction. So we need to search by (txhash,idx) in order to see if an output has been spent. When outputs are inserted into this tree, they're stored in sorted order according to (txhash,idx).

2) It's also desirable to find all the available txouts for a particular address. Let a second Merkle tree contain keys of the form (scriptpubkey). Now, given a root hash, you can ask for a verifiable list of all your spendable coins.


Alternately, instead of thinking of it as a different tree for each index, you can think of it as a composite structure. The general form is a Search DAG (Directed Acyclic Graph), but the idea is exactly the same [5]. (This includes B-Trees).



[5] A General Model for Authenticated Data Structures
     Martel, Nuckolls, Devanbu, Gertz, Kwong, Stubblebine, 2004.
     http://truthsayer.cs.ucdavis.edu/algorithmica.pdf

Let me try to explain a solution to the 'alternate Merkle tree' you require.

The basic idea is to use a balanced binary search tree, such as a red-black tree or a 2-3 tree. Updating such a data structure, including rebalancing, only requires accessing O(log N) tree nodes. A lite client would be able to verify such an update by receiving just the relevant nodes. There is never a need to recompute the entire tree from scratch. Balancing is strict, in that the worst-case length from the root to a leaf never exceeds O(log N).

There's been a bunch of academic research on this topic, where it's known as "Authenticated Data Structures" [1,2,3]. Although the idea has been around for almost 15 years, I don't know of a single implementation. So I made a toy implementation available at https://github.com/amiller/redblackmerkle

I'm hoping to spread awareness of this technique, since it's pretty clear that some clever use of Merkle trees is going to be important in Bitcoin's future. Let's discuss this!


P.S. Most of these structures only require collision resistant hash functions. However, if you want to use a fancy hash functions with special (homomorphic) properties, you can make even more efficient structures, e.g. a Merkle 'bloom filter' [4].
 

[1] Certificate Revocation and Certificate Update
     Noar and Nissim, 1998. USENIX
     https://www.usenix.net/publications/library/proceedings/sec98/full_papers/nissim/nissim.pdf

[2] Authenticated Data Structures
     Roberto Tamassia, 2003.
     http://cs.brown.edu/research/pubs/pdfs/2003/Tamassia-2003-ADS.pdf

[3] Persistent Authenticated Data Structures and their applications
     Anagnostopoulos, Goodrich, and Tamassia
     http://cs.brown.edu/people/aris/pubs/pad.pdf

[4] Cryptography for efficiency: Authenticated Data Structures Based on Lattices and Parallel Online Memory Checking
     Papamanthao and Tamassia, 2011
     http://www.cse.msstate.edu/~ramkumar/gw-102.pdf

Here are a few papers on this topic that might be helpful:

[Rivest, 1997] Electronic Lottery Tickets as Micropayments http://people.csail.mit.edu/rivest/Lottery.pdf
[Rivest and Shamir, 1996] PayWord and MicroMint: Two simple micropayment schemes http://people.csail.mit.edu/rivest/RivestShamir-mpay.pdf
[Rivest, 2002] Micropayments Revisited http://people.csail.mit.edu/rivest/pubs/MR02a.pdf
[Hashem et al, 2005] New probabilistic scheme with Variable Sized Micropayments http://www.setit.rnu.tn/last_edition/setit2005/electronique/293.pdf

I'm very satisfied.
I traded 0.15 btc for a logo design, completed (three iterations) within a few hours. Exactly what I hoped for!

LMGTFY, it's not likely they are transferring the coins to mybitcoin themselves. The address is a mybitcoin.com address - it happens automatically.

My belief is that the motivation behind establishing a donation box for the EFF wasn't just to help them raise money, but as a way of introducing bitcoin to the EFF, with the hope that EFF will take the time to learn how bitcoin works and become an ally in advocating it to other organizations. If they find a way report it as donation income, for example, then that would set a precedent that the rest of us could follow. Like you said ribuck, EFF has better things to do then install some software and help us debug it. But, thanks to your donations, now they have a stake in it, and an incentive to play along!

It's none of our business what they do with it, but if it's the case that they're just sitting in the account because we haven't followed up on it, then I it's appropriate for us to let them know about the alternatives. It should be a learning opportunity, I'm pretty sure that was the whole point.