amiller/gist:2232636

## gistfile1.py
"""
   An alternate proof-of-work scheme for Bitcoin where competitive mining implies a
low marginal cost of "honesty." The new work has nothing to do with GPUs, but
instead requires random access to the 'tx_outputs' database, just as you would need
in order to thoroughly double check incoming transactions against history, i.e. to
be "honest" in the sense of the Satoshi paper [1]. May we lug Ascii Bernanke around
forever.

   Parameters:
      N: the total number of txoutputs, each of which can be spent at most once
      k: the path length / security parameter

   A miner begins with a nonce and the previous block hash. At each of k iterations,
the hashes the current data and uses this hash to index into the table of tx_outputs.
The tx_output data (including the 'spent' value) is hashed to provide the next index,
and so on, k times. The final hash is compared to a difficulty value.

   The central argument is that a lazy miner with incomplete history (i.e. a
miner that only keeps around a subset of M/N transactions) has an exponential
computational disadvantage compared to an "honest" miner with full access to the
database. At each iteration in compute_work(), the lazy miner has only an (N/M)
chance of the operation succeeding. This means the miner will need to try (N/M)^-k
more hashes in order to keep up.

There are several implications of adopting this proof-of-work work scheme. Most
importantly, there will no longer be a need for 'checkpointing' and other tricky
complicated strategies for coping with the increasing storage burden of the growing
blockchain. We're effectively "hiding" this extra resource cost inside the mining
costs, which are set through competition anyway. SSDs will replace GPUs as the
sought-after commodity; but they'll all holding copies of blockchain data, which
has good implication for the longevity and availability of your unspent coins.


[1] http://bitcoin.org/bitcoin.pdf
"""

# (blockchain) is what you need to check against double-spends.
# It is a table of txoutputs, where each key is a txout_idx. Each
# value is of the form (spend, txout), where spend is None if the
# coin is currently unspent and a txin_idx otherwise. (txout)
# contains the output amount and the SCRIPTPUBKEY.
blockchain = {}

def random_nonce():
    return os.urandom(32)

def bytes_to_long(b):
    return long(b.encode('hex'), 16)

def hash_to_index(h):
    assert(len(h) == 256)  # Only intended for us with a 32 byte hash sha256
    return bytes_to_long(h) % len(blockchain)

# An "honest" miner always double checks new transactions against their
# database of blockchain history
def validate_tx(tx):
    in_total = 0.0
    for txin in tx.txinputs:
        # Query the txoutput/coin database
        spend, txout = blockchain[txin.txout_idx]

        # Check for double spends
        assert not spend

        # Check that the current txin matches the previous txout
        assert validate_script(txout, txin)

	# Add to the total
	in_total += txout.amount

    # The inputs and outputs must balance
    assert in_total == sum((txout.amount for txout in tx.txouts))


# A comeptitive miner demonstrates the low marginal cost of "honesty" by
# randomly accessing the txoutput database very many times.
def compute_work(header, nonce):
    # Header is a hash that depends on the previous block and the
    # current transactions

    # Initialize the seed
    data = header + nonce

    # Compute a path of length k through the transaction database
    for i in xrange(k):
        h = H(data)
        txout_idx = hash_to_index(h)
        spend, txout = blockchain[txout_idx]
        data = h + tx + spend

    # The final hash will be compared to the difficulty threshold
    return H(data)


def mine(header, difficulty):
    while True:
        nonce = random_nonce()
        h = compute_work(header, nonce)
        if h < difficulty:
            return nonce, h
	"""
	An alternate proof-of-work scheme for Bitcoin where competitive mining implies a
	low marginal cost of "honesty." The new work has nothing to do with GPUs, but
	instead requires random access to the 'tx_outputs' database, just as you would need
	in order to thoroughly double check incoming transactions against history, i.e. to
	be "honest" in the sense of the Satoshi paper [1]. May we lug Ascii Bernanke around
	forever.

	Parameters:
	N: the total number of txoutputs, each of which can be spent at most once
	k: the path length / security parameter

	A miner begins with a nonce and the previous block hash. At each of k iterations,
	the hashes the current data and uses this hash to index into the table of tx_outputs.
	The tx_output data (including the 'spent' value) is hashed to provide the next index,
	and so on, k times. The final hash is compared to a difficulty value.

	The central argument is that a lazy miner with incomplete history (i.e. a
	miner that only keeps around a subset of M/N transactions) has an exponential
	computational disadvantage compared to an "honest" miner with full access to the
	database. At each iteration in compute_work(), the lazy miner has only an (N/M)
	chance of the operation succeeding. This means the miner will need to try (N/M)^-k
	more hashes in order to keep up.

	There are several implications of adopting this proof-of-work work scheme. Most
	importantly, there will no longer be a need for 'checkpointing' and other tricky
	complicated strategies for coping with the increasing storage burden of the growing
	blockchain. We're effectively "hiding" this extra resource cost inside the mining
	costs, which are set through competition anyway. SSDs will replace GPUs as the
	sought-after commodity; but they'll all holding copies of blockchain data, which
	has good implication for the longevity and availability of your unspent coins.


	[1] http://bitcoin.org/bitcoin.pdf
	"""

	# (blockchain) is what you need to check against double-spends.
	# It is a table of txoutputs, where each key is a txout_idx. Each
	# value is of the form (spend, txout), where spend is None if the
	# coin is currently unspent and a txin_idx otherwise. (txout)
	# contains the output amount and the SCRIPTPUBKEY.
	blockchain = {}

	def random_nonce():
	return os.urandom(32)

	def bytes_to_long(b):
	return long(b.encode('hex'), 16)

	def hash_to_index(h):
	assert(len(h) == 256) # Only intended for us with a 32 byte hash sha256
	return bytes_to_long(h) % len(blockchain)

	# An "honest" miner always double checks new transactions against their
	# database of blockchain history
	def validate_tx(tx):
	in_total = 0.0
	for txin in tx.txinputs:
	# Query the txoutput/coin database
	spend, txout = blockchain[txin.txout_idx]

	# Check for double spends
	assert not spend

	# Check that the current txin matches the previous txout
	assert validate_script(txout, txin)

	# Add to the total
	in_total += txout.amount

	# The inputs and outputs must balance
	assert in_total == sum((txout.amount for txout in tx.txouts))


	# A comeptitive miner demonstrates the low marginal cost of "honesty" by
	# randomly accessing the txoutput database very many times.
	def compute_work(header, nonce):
	# Header is a hash that depends on the previous block and the
	# current transactions

	# Initialize the seed
	data = header + nonce

	# Compute a path of length k through the transaction database
	for i in xrange(k):
	h = H(data)
	txout_idx = hash_to_index(h)
	spend, txout = blockchain[txout_idx]
	data = h + tx + spend

	# The final hash will be compared to the difficulty threshold
	return H(data)


	def mine(header, difficulty):
	while True:
	nonce = random_nonce()
	h = compute_work(header, nonce)
	if h < difficulty:
	return nonce, h