Topic: Hash-based chainless transactions theory (Read 4040 times)

I don't think this can work. If I have 10 bitcoins, I have to be able to transfer them to Joe or Edward, but not Joe and Edward. What in this mechanism allows me to generate one but stops me from generating two? The chain solves this because there is, globally, one and only one longest chain and it can contain either transaction but not both.

I somehow doubt that what you are asking for is an open problem in cryptography or protocol design.  But I was apparently not understanding it well enough, but after rereading a few times, I think I am starting to get it.

I think the block chain/graph is in fact not a chain at all because there is no 'link' from one state to its successor(s).  In Bitcoin, each hash is computed on data that includes the hash from a previous block, establishing linkage.  But no such link is possible with your definition, because this wouldn't match what ORIGIN would have computed for that particular state.

The transaction history must also be completely absent, which I think is intentional.  If multiple transaction histories leading to the same account balances were to have different hashes, they couldn't both match what ORIGIN would have computed.  The hash must be completely invariant to the transaction history.  From an information theory perspective it must contain zero information about the history.

Consider this:  there are multiple 'coins' all concatenated together, each with a unique id signed by ORIGIN's private key.  Anyone with ORIGIN's public key can verify the authenticity, and it prevents other people from later padding with fake coins.  They could delete coins, so to prevent that, there is a statement at the very beginning "there exist 1000 coins" which is also signed with ORIGIN's private key.  If the number of coins does not match the signed statement, the block is held to be invalid.

Each coin contains a message, "coin 1 is owned by A" which is signed by ORIGIN's private key.  The owner is specified by public key, but for convenience here we'll call them A, B, C, etc.

Each coin also contains a list of all its possible signed ownership statements
"coin 1 is owned by A" signed by ORIGIN
"coin 1 is owned by B" signed by ORIGIN
"coin 1 is owned by C" signed by ORIGIN
etc.,
and this list of signed statements is encrypted with A's public key.

(In this scheme, ORIGIN does not need users' private keys, only public keys to generate the initial block.)

If A wishes to give this coin to B, she can decrypt the list of statements using her private key, extract the statement "coin 1 is owned by B" (including ORIGIN's signature) and re-encrypt the entire list using B's public key.  She then sends the statement and encrypted list to B.  B can decrypt the list and verify ORIGIN's signature on all possible future recipients (otherwise a future recipient might reject it).  B then broadcasts the statement and encrypted list to everyone else, and all recipients replace the ownership information for coin 1.  Anyone can verify ORIGIN's signature on the statement "coin 1 is owned by B".

This is the same as what ORIGIN would have produced if B were the initial owner of the coin.

This scheme is very inefficient and scales very poorly, as N*M where N is the number of units of currency and M is the number of people in the system.

There are also some really bad implications for double-spending as it is hard to distinguish between B spending the coin and A spending it a second time.  Also, if someone ever gets back a coin that they had previously owned and spent, they would be vulnerable to a replay attack.  It would be smart for everyone to reject coins that they had previously owned, but then this leads to a limited lifetime on each coin.

I think all of these are a consequence of the block chain/graph not actually being linked.  And it seems they cannot possibly be linked if the block is to be invariant to everything except the allocation of coins.  The authenticity is independent of any history or connection to any other valid block, which cuts both ways.  Even for innocent deconfliction clients may have to keep old blocks so they can resolve merges.  Diff/merge on two branches from a common ancestor is much easier because when the branches differ, you can presume the one that matches the ancestor is the earlier one that should be overridden (another reason not to accept coins you have owned previously).

To help get around the double-spend lack of history problem, B might insist on a signed statement from A, stating "coin 1 has been transferred from A to B".  This would not appear in the block but B could keep it privately or broadcast it, to help reduce the chance that someone else would accept the same coin from A.  This may be redundant, since B is already broadcasting his ownership of the coin that A was previously known to hold, but it might make a difference if A were to attempt to rebroadcast her ownership of the coin.  Or in the case of deconflicting branches, a chain of signed 'deeds' could help resolve what should happen.

So the history will still need to be kept, it will just be at the client level and outside of the blocks themselves.


I'm not that interested in the bounty, I just love a puzzle and I want to know if it's solved or not.

edit nvm

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; is not secure because 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.

No bounty?  lol

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.

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.

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.

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.

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.

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.

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.

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.

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).

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

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

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).

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.

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).

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).

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.