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