Ещё не предлагали хранить историю распределённо?
Каждая транзакция и каждый блок сверяется с историей, и признаётся только информация, прошедшая проверку.
Клиент может кэшировать проверки. Большая часть платежей клиента будет происходить в пределах некой группы (при достаточном развитии сети). Поэтому кэширование будет иметь смысл.
Теоретически, клиент может хранить локально только часть информации, например, хеш каждого блока. При необходимости, он будет подгружать полные блоки из сети и сверять их хеши с хранящимися локально. Майнерам, пожалуй, удобнее будет хранить всю историю локально - вот они-то и могут стать "серверами" истории. А также те, кому надёжность важнее экономии места. Думаю, в случае успеха Bitcoin, найдётся достаточное количество желающих иметь "полные" узлы.
Это уже задачи распределённой файловой системы: балансировка нагрузки, обеспечение безотказности, равномерная нагрузка и т.п. Главное, это снижение требований к дисковой памяти одного клиента.
Очень грубо: если сотня клиентов за сутки находится час в он-лайн, то они обеспечат примерно четырех-кратное дублирование. Делим ещё на два для надёжности и получаем, что каждому из них достаточно хранить только половину информации. И это всего один час он-лайн в сутки. (Это очень грубо. На самом деле объём в значительной степени будет зависить от требований к доступности.)
Кроме того, информация в это хранилище очень редко записывается (по сравнению с чтением), а значит поддаётся значительной оптимизации в этом направлении.
Илья