(By items I mean hashable objects.) As an example (with obviously way too short hashes for readability), say I packed my bag and in it I put
- a shovel (hashed to
S
) - a bucket (hashed to
B
) - a towel (hashed to
T
) - a random number (hashed to
R
)
Now friends of mine (who packed their bag too) and I agree on a game of multiple rounds, and each round consists of the following steps:
- someone to be picked at random suggests something that might happen (e.g. going to the swimming pool, hitchhiking, Alien invasion) and what item(s) we might need then
- everyone who doesn't have a mentioned item in their bag has to pay a small prize equally shared among those with the item in their bag; this is done for each mentioned item
- additional items may be added to each ones bag
Would the game last only one round, we could simply open our bags and confirm the items' presence, but for multiple rounds the person to pick the next hypothetical event would of course choose something for which they'd probably gain the most due to knowing what everyone had in their bags (and maybe guessing the additions). Therefore, the round actually starts with
- we'll tell each other something (a hash) and confirm that
and for confirmation, I propose to use a hash H
with the following properties:
H
can take an arbitrary amount of inputs such asH(shovel) = S
,H(shovel, bucket) = E
H
is commutative, i.e.H(A,B) = H(B, A)
H
is chainable, i.e.H(H(A,B),C) = H(H(A), H(B), C)
(if calling H
a hash is still adequate).
With such a hash, we'd simply share the entire bag's hash, and for a given item I
we'd have H(bag) = H(I, bag without I)
, i.e. by providing the remainder's hash there's proof of the item's presence in a bag without requiring to unpack it (that's also why the random number is added, otherwise everyone could figure out when one's bag is fully revealed).
So, long story short, does such a "hash" exist?
Of course, we could simply alphabetically sort our items and use a hash-chain, but for the question's sake let's assume sorting is beyond our capabilities ;)
H(H(A))=H(A)
, but what I (maybe unfortunately) called chainability merely allows splitting the hashes, and come to think of it is not even necessary $\endgroup$