Hash-based chainless transactions theory

[awwright]

This is an idea I have thought of while exploring hashing functions, what if you could store the entire transaction history and make payments by using a very small set (a small graph) of hashes, with no need to track individual transactions, no need to store the transaction history, and reduced need to be connected to the network to make a transaction? But you have to have the history of each transaction to be able to prove a transaction is acceptable, right? I don't think so, if you can hash the history (so it still exists, but you can't read it).

You don't make the block network a linear directed graph, make each individual's transactions an acyclic directed graph that is (usually) linear.

Here is the introduction: Each person starts off with the same initial block. After that, each transaction records a block of the state of the network at that time. Each transaction contains information that modifies the block in such a way that double-spending will not "cleanly" apply (that is, double-spending and the like is detected by examining the resulting hash), and furthermore, will incorperate all the information for all the transactions that came before it. Each person has the private key that can create a transaction that will cleanly apply for only an amount not greater than their current balance.

Here is how it might work: Define a hashing function GETTHEBLOCK( inputs ) which takes the entire list of private keys and how much they hold, and produces a very large number based on it, in such a way a private key with a balance of zero passed to the input does not affect the output, and additionally such that an examination of the hash can securely reveal how many total units of currency it embodies. All numbers are unsigned (since they are simply bit arrays like any computer), so there cannot be a negative balance. Create a public/private key pair "ORIGIN", and define that private key to own T units of currency (T being the maximum number that the configuration of the algroithm permits). Create the first block B0 by passing that private key/balance pair to GETTHEBLOCK to produce the prime block B0.

Produce a second public/private key pair "A". Create an acyclic directed graph with a single node of value B0, this represents A's first "transaction" formally giving that private key a balance of zero. That is, by taking the private key/balance pair of ORIGIN and the private key/balance pair of A, A can re-create B0.

Now here is the magic. GETTHEBLOCK is defined in such a way that ORIGIN can pass a message to A, that allows A to modify the block to what GETTHEBLOCK would produce if ORIGIN had x less currency and A had x more currency (maybe they have to negotiate the actual change that happens interactively, who knows). If ORIGIN has transactions that A does not have and vice versa and can be merged "cleanly", the clients also exchange this information (probably beforehand). Each side enters the transaction into their transaction history graph as a decedent of the most recent block that the transaction will cleanly apply to.

Clients will not be able to re-create the updated block because they do not have each individual's private key (except maybe for ORIGIN once that balance is zero, so they can verify B0 for themselves). But they can still verify that they have an increased balance, and that the total number of currency has not changed so it must have come from someone else's private key, presumably the person they are making the exchange with.

There is no need to download the block chain, and you can (probably) compress an indefinite number of transactions into a constant size hash, that is no less insecure than modern private key cryptography.

There is no central authority here, no block chain. However, there is no risk of counterfeiting, since individuals will not accept an increased money supply by definition (it could be technically impossible too if the money supply is the limit for the storage container, an unsigned int64 or whatever). The only real problem (if possible at all--see below) is double spending. If A decides to double-spend the entire balance to B and C, from the same block, B and C will not be able to make a transaction with each other because they cannot "cleanly" do so, they may be forced to apply a transaction to an older block, and one of them will have to invalidate their transaction with A. Possibly there could be two separate histories now, one where B got the "actual" transaction and one where C got the "actual" transaction. Or as I calculate it, eventually no one will want to exchange with the second B or C block because they will already have the other key has already gotten the currency, and the only option B or C will have is to transact against an older block where they have less balance. This could all be mitigated with a central clearing network that broadcasts transactions instantly to everyone connected (or can do it quickly distributed like the current block chain, doesn't matter), so the receiving party merely needs to wait a few seconds before finishing the transaction to see that everyone in sight accepts the transaction.

Now GETTHEBLOCK might not even exist, it could be impossible. Most of the functionality should be possible. You could make it satisfy the first condition, that private keys with a balance of zero do not affect the output, possibly by signing the balance with that private key, then multiplying that number (treating it as a number) by the balance. But could you make it satisfy the second condition, that you can verify how much currency it embodies by examining it? You don't even have to return a number, just a true/false that it is the same number that it was the previous transaction (and since everyone will know the ORIGIN private key, they can determine how much currency was in the B0 block). You might need to so something creative like using an alternative public-private key algorithm, where the sum of the individual bytes or bits is a constant, so key×balance carries the same pattern.

[kiba]

BUMP.

[awwright]

Alright, I'm putting up a 10 BTC bounty for anyone who can find such a function OR prove that it doesn't exist, with a reasonable description of what combination of features makes is making it impossible.

All it has to do is this: Define a hashing function GETTHEBLOCK_1( inputs ) which takes a map of (private key, balance) pairs, and produces a very large number based on it, in such a way that any pairs with a balance of zero passed to the input does not affect the output, and additionally such that an examination of the hash can securely prove that the amount of currency embodied within it has not changed from a reference.

[ribuck]

Alright, I'm putting up a 10 BTC bounty for anyone who can find such a function

I have found the function, and I claim my 10 BTC.
13NyUj5StfFDLCT1xrwDWShp51H9Ve9xMW

Unfortunately it won't make you happy, because the function simply maps its inputs to its output, resulting in a very large hash (but you said that's OK).

[awwright]

Unfortunately it won't make you happy, because the function simply maps its inputs to its output, resulting in a very large hash (but you said that's OK).

Not quite because (1) a hash (by definition) returns a fixed-size bit string, as in, the number it returns must never exceed a certain value/size, (2) the balance wouldn't be cryptographically tied to the the private key, I could modify the balance of the "hashed" output and it would be undetected, and (3) pairs with a balance of zero would affect the output.

I have a feeling that what I overall described would be impossible, you cannot accurately verify the existence of an item in a large enough set, it will have to grow more and more inaccurate (false positives or such) as a constant size hash needs to store more information, the only thing you would be able to retrieve with complete accuracy is the total balance (if it exists, by definition). This problem by itself is not asking to query information, however, except for the total balance. It is likely a transaction chain would still be necessary...

How about this, 10 BTC bounty (another one) for a function called GETTHEBLOCK_2 that is like GETTHEBLOCK_1 but it returns an arbitrarily large number, and it must be cryptographically secure and must not leak the private keys used (that is, it must be mathematically hard).

[ribuck]

Unfortunately it won't make you happy, because the function simply maps its inputs to its output, resulting in a very large hash (but you said that's OK).

Not quite because (1) a hash (by definition) returns a fixed-size bit string, as in, the number it returns must never exceed a certain value/size, and (2) the balance wouldn't be cryptographically tied to the the private key, I could modify the balance of the "hashed" output and it would be undetected.

A hash does not need to return a fixed-size bit string (although in software applications it usually does). Show me a definition that says it must be fixed-size. A hash function "number of vowels in the input" is an example of a hash function with no upper size limit. The Wikipedia article says "one can use the datum itself as the hashed value".

You wanted assurance that the balance had not changed "from a reference". Since you can easily calculate the balance of the output of my hash function and compare it to the reference balance, it meets your challenge. :-)

But I will let you off the 10 BTC payment.

[awwright]

A hash does not need to return a fixed-size bit string (although in software applications it usually does). Show me a definition that says it must be fixed-size. A hash function "number of vowels in the input" is an example of a hash function with no upper size limit. The Wikipedia article says "one can use the datum itself as the hashed value".

You wanted assurance that the balance had not changed "from a reference". Since you can easily calculate the balance of the output of my hash function and compare it to the reference balance, it meets your challenge. :-)

In some cases it might not be fixed size but a hashing function won't ever produce output proportional to the input, that's just a regular function, otherwise, what differentiates a hash from a general function? I was looking at http://en.wikipedia.org/wiki/Cryptographic_hash_function which specifies fixed size but that has other things that aren't strictly necessary like "it is infeasible to find a message that has a given hash" (though that will certainly be true if you can't determine the very large private key used as the input).

"from a reference" meaning, I can verify that the sum of the inputs is the same sum of the inputs of a previous hash (B0 most likely), and such that you can't (easily) create a hash that passes the test even though the sum of the inputs was not the same as the reference (or wasn't derived from a hashed set of inputs at all).

[jib]

If your hash size is less than the input size, there will be collisions. There will be multiple states with the same hash, in which people have different balances. So it will be impossible to unambiguously tell whether a transaction should be allowed or not

[theboos]

Alright, I'm putting up a 10 BTC bounty for anyone who can find such a function OR prove that it doesn't exist, with a reasonable description of what combination of features makes is making it impossible.

All it has to do is this: Define a hashing function GETTHEBLOCK_1( inputs ) which takes a map of (private key, balance) pairs, and produces a very large number based on it, in such a way that any pairs with a balance of zero passed to the input does not affect the output, and additionally such that an examination of the hash can securely prove that the amount of currency embodied within it has not changed from a reference.

I'm assuming you are asking for a cryptographic hash function because, as has been discussed, merely outputting the input is not acceptable. The Wikipedia page lists four properties of a suitable function, paraphrased here:

• The function can be computed easily
• Given an output, it is infeasible to find a matching input
• Given an input, it is infeasible to find another input with the same output
• It is infeasible to find any two inputs with the same output (birthday attack)

Your requirement that a balance of zero not be included in the hash violates the last two properties. The third property is violated because an input can be constructed from another input that has the same hash, simply by appending an account with a balance of zero. The final property is most trivially violated; any time a new (zero) balance is added, the hash is unchanged. I'll ignore these for the purpose of discussion, but I consider them alone a valid proof of the nonexistence of a cryptographic hash function, and claim the bounty.

As has been discussed, you are looking for a hash function which produces a fixed-size output, which, while not explicitly a property of a hash function, is reasonable for any practical system. Now consider the requirement that the hash can be examined to check that the total amount of currency in circulation has not changed. (I'm a bit unclear on this, I'm assuming this is what you are saying). A fixed-size output can only store a fixed amount of information. A 256-bit hash can only store 256 bits of information. The fundamental advantage of hashes like SHA is that they are destructive. You feed in an variable-length message and get a fixed-size output. Information is lost in the process so it is impossible to reconstruct the original message from its hash. As more and more inputs are added to GETTHEBLOCK_1 (more bits of information), you will eventually not be able to fit the precise allocation of funds into the hash. This is OK because all you want in the hash is a verification of the total amount of currency.

So let's consider an alternative method: addition. Forget traditional hash functions for a moment. You add the balances of every account in the system together, and take the sum as your output (if it's really critical that the output be fixed-length, pad the result appropriately). This is one of the computationally simplest hashes for any number of inputs (follows property 1). However, it is trivial to find another set of balances that have the same sum (violates properties 2, 3, and 4). Now consider the number of addresses in existence. Looking at the SourceForge download statistics page, I'm going to make a conservative estimate of 300,000 clients. Each of these clients produces 100 keypairs the first time they are started, and users will produce, on average, as a conservative estimate, 1 keypair per week. Even though zero balances are not reflected in the hash, they do have to be either added to the running total (with no change) or branched around. This makes 30 million balances that have to be added together each time a transaction is made (conservative estimate of 5 per minute), and this is still completely ignoring the private keys (which don't even need to factor into the verification). I say this violates the first property even though it runs in linear time, simply because n is very large. Also, it will be impossible to scale as more and more balances are introduced. The current model works because nodes look at a balance and a transaction, check that it is valid, and then do some SHA hashing, and then clients trust that the nodes are doing their math correctly.

Finally, who has all of the private keys in the first place? Who is computing GETTHEBLOCK_1 and how does he "securely" collect private keys?

As for GETTHEBLOCK_2, what about hash(hash(private key₁) x balance₁)+hash(hash(private key₂) x balance₂)+hash(hash(private key₃) x balance₃) and so on where + is concatenation, x is multiplication, and hash is a standard cryptographic hash function of your choosing?

Bitcoin address: 1AJnX8Rf29kw72D4L9hBBEdHmZZRMYjW6

[awwright]

Your requirement that a balance of zero not be included in the hash violates the last two properties. The third property is violated because an input can be constructed from another input that has the same hash, simply by appending an account with a balance of zero. The final property is most trivially violated; any time a new (zero) balance is added, the hash is unchanged. I'll ignore these for the purpose of discussion, but I consider them alone a valid proof of the nonexistence of a cryptographic hash function, and claim the bounty.

I specified that the hash must be cryptographically secure, so yes, a cryptographic hash function of fixed length, except for GETTHEBLOCK_2 which may be of arbitrary length.

Appending an account with a balance of zero does not change the distribution of funds, and thus does not change the input, so there is no violation. If this is impossible to do and remain cryptographically secure, that merely needs to be proven. This requirement alone (cryptographically secure or not) can be done as follows: hash(private key₁)×balance₁ + hash(private key₂)×balance₂ + ... + hash(private key_n)×balance_n (where "+" denotes addition and/or XOR). But again, this may not be cryptographically secure.

Even if it were cryptographically secure (such that the private keys are unrecoverable), it does not meet the requirement that a change in funds from one person to another must cause a predictable change in the hash (specifically, the algorithm must offer a way to prove the total amount of funds in all the accounts is the same before and after the transfer).

[JoelKatz]

All it has to do is this: Define a hashing function GETTHEBLOCK_1( inputs ) which takes a map of (private key, balance) pairs, and produces a very large number based on it, in such a way that any pairs with a balance of zero passed to the input does not affect the output, and additionally such that an examination of the hash can securely prove that the amount of currency embodied within it has not changed from a reference.

Seems pretty simple:
1) Take map of private key, balance pairs.
2) Omit any pairs with a balance of zero.
3) Sort the pairs.
4) Take the SHA1 hash.
5) Append the SHA1 hash to the total of all balances expressed in any fixed-length format.

This should meet your requirements. Adding or removing zero balance pairs will not affect the calculation at step 4 (because they are eliminated in step 2) nor the total at step 5, because they have no affect on the total. So the output is the same with or without zero-balance pairs.

You can prove the amount of currency has not changed because any change in the amount of currency will require changing one of the private key / balance pairs, which will change the hash in step 4.

[awwright]

You can prove the amount of currency has not changed because any change in the amount of currency will require changing one of the private key / balance pairs, which will change the hash in step 4.

This does not cryptographically verify that the sum of the values of all the keys is the same as another hash, of a different distribution of values/currency/funds, sorry for the confusion. The idea is I should be able to compare GETTHEBLOCK_x( (private key₁, balance₁₁), (private key₂, balance₂₁) ) and GETTHEBLOCK_x( (private key₁, balance₁₂), (private key₂, balance₂₂) ), and verify whether or not balance₁₁+balance₂₁ == balance₁₂+balance₂₂ .

The "reference" I'm talking about is the initial input that contains a publicly known private key, and the initial currency. You compare future hashes to this block to verify the sum amount of currency in circulation has not changed.

This does happen to be a bit of a departure from a traditional hash, in that it's supposed to preserve exactly one piece of information information somehow: the sum of the values, even if you can't tell exactly how much, you should be able to compare it to another block.

[JoelKatz]

I don't understand your objection. This does cryptographically verify that the sums are the same, precisely the same way the BitCoin system ensures that a transaction doesn't import more money from a previous transaction than that transaction exported. All the inputs are cryptographically protected by hashes, so no special magic is needed to check the sanity, you just do it directly.

[awwright]

I don't understand your objection. This does cryptographically verify that the sums are the same, precisely the same way the BitCoin system ensures that a transaction doesn't import more money from a previous transaction than that transaction exported. All the inputs are cryptographically protected by hashes, so no special magic is needed to check the sanity, you just do it directly.

Because it's still the case that a different distribution of private keys creating a different hash could carry the same total amount of currency. The sum would be the same, but the hash would be different, and when you run the balance through SHA1, it will very nearly destroy the information about the currency in circulation. There's no way to compare the sum of values of the (key, value) pairs when the hashes are not the same, there's not even a probabilistic way of comparing them (which could suffice for GETTHEBLOCK_1).

Suppose I have the following sample pairs of keys/values with a sum of 7: { (A, 5), (B, 2) }

I need to be able to verify from the hash of that set that it contains the same balance as another distribution of the values, maybe { (B, 2), (C, 1), (D, 4) }, and likewise, I need to be able to verify from the hash of { (D, 5) } that the listed hashes do not embody the same sum of the values as the others (as 5 != 7). The hashes will be different when different private keys are associated with different values, but a comparison of the sum of all the values to the private keys, and only that comparison, must be possible.

[vector76]

I don't think hashes will protect what you're wanting to protect.  People with only the hash should be confident that the money is not being fabricated, but whoever is doing the hashing can fake it, and unless they are forced to prove that the full accounting generates the hash, there is no way to know.  So you might as well just append the unencrypted total to the hash of the sorted list.

You could store the map in "unary", in other words { (A, 5), (B, 2) } would be stored as "AAAAABB" (lexicographically sorted before expanding)

Then encrypt with a public key.

The length serves as an indicator of total value.  If you use a block cipher in counter mode then whoever has the private key could decrypt portions to prove that certain keys own certain coins, without having to divulge the entire ownership map.

[awwright]

I don't think hashes will protect what you're wanting to protect.  People with only the hash should be confident that the money is not being fabricated, but whoever is doing the hashing can fake it, and unless they are forced to prove that the full accounting generates the hash, there is no way to know.  So you might as well just append the unencrypted total to the hash of the sorted list.

The sum of the values must be cryptographically secure, else you could tamper with the hash and say the total is different than the actual totals of the input to the hash. And it isn't enough to merely be confident that the sum isn't rapidly growing, you have to have certainty that it hasn't changed. This means if you're going to use length of the encrypted data, you must not pad it.

You could store the map in "unary", in other words { (A, 5), (B, 2) } would be stored as "AAAAABB" (lexicographically sorted before expanding)

Then encrypt with a public key.

The length serves as an indicator of total value.  If you use a block cipher in counter mode then whoever has the private key could decrypt portions to prove that certain keys own certain coins, without having to divulge the entire ownership map.

This possibly meets the requirements for GETTHEBLOCK_2, though you can extract way more information than just the amount of currency from this which is sort of pushing what I asked for by a cryptographically secure hash... How do you guarantee all the keys are the same length, for instance? The keys, too, may be of arbitrary size.

[vector76]

Whoever is generating the hash has access to the plaintext map of accounts can alter it at will before hashing it.  You have to take the word of the person who is doing the hashing, and I don't see a way around that.

If your account map is { (A, 5), (B, 2) } you could add all the accounts, then take the total amount, 7, and append a nonce, so you have 7_snei238nbd, and then just sign that with the private key of whoever is doing the hashing.  Third parties can verify the signature but they cannot forge messages.

You could go further and take the SHA-256 hash of the account data, and append it to the total and the nonce before signing.  Then if the signer/hasher is challenged or "audited" they can't arbitrarily assign values to keys.  They are locked into revealing how the values were assigned to keys at the time of signing.

[vector76]

No bounty?  lol

[awwright]

Whoever is generating the hash has access to the plaintext map of accounts can alter it at will before hashing it.  You have to take the word of the person who is doing the hashing, and I don't see a way around that.

If your account map is { (A, 5), (B, 2) } you could add all the accounts, then take the total amount, 7, and append a nonce, so you have 7_snei238nbd, and then just sign that with the private key of whoever is doing the hashing.  Third parties can verify the signature but they cannot forge messages.

You could go further and take the SHA-256 hash of the account data, and append it to the total and the nonce before signing.  Then if the signer/hasher is challenged or "audited" they can't arbitrarily assign values to keys.  They are locked into revealing how the values were assigned to keys at the time of signing.

No bounty?  lol

This doesn't begin to solve the problem I identified, read my original post again and see what I'm trying to accomplish, then read the requirements for what the hash needs to do. It needs to be cryptographically secure against recovering individual inputs. I'm looking for a formal written research here. Prepending the total sum to the hash of the pairs is not cryptographically secure in the context of this problem. Examining the output to determine the sum of the inputs (but no other information may be recoverable, like private keys) must guarantee that it's the same sum of the inputs that used to produce the hash. An output of 7;<somehash> is not secure because <somehash> could be anything, something whose inputs do not sum to 7, or even nonsense that's not a hash at all. Using a nonce in a function disqualifies it from being a hash because the input produces an unpredictable output.

And also, I would need your Bitcoin address.

[hashcoin]

edit nvm