Best alien communication protocol? Let's say we discover alien civilizations that are able to send and receive messages using an interstellar digital communications channel. (Say using modulated radio waves, laser pulses, re-positioning stars in various orbits, what have you.) Let's assume we have decided to make contact with them.

Once we initiate a dialog, how would we go about establishing a communications protocol and language? What methodology would we use to agree on a basic vocabulary and ways of expressing logical ideas? Is it ad-hoc or is there some way to optimize the process of establishing a common language based on symbolic manipulations. We would want to agree on a language quickly and minimize the resources required to encode and send messages (since they're quite slow to send).

Next, reciprocity: Once we have a shared language, how would we make sure that both sides reciprocate in trading secrets? That is, we don't want to be in a situation where we give away valuable technology without receiving anything in return. Can both sides prove that they posses certain technology? Is there a way to send results piecemeal, gradually, so that each side can have increasing confidence in the value of the message?
Your first question is the topic of Brendan Juba's PhD thesis on Universal Semantic Communication. You should take a look at it, as well as some of the papers on his website.

As for your second question, you might want to read about zero-knowledge proofs.