Problem Set – EthSpring

If you control pp of the overall processing power in Bitcoin, what is the probability that you can get to kk blocks ahead of everyone else in the world at some point in a day? (you can make simplifying assumptions / modeling / estimations)
If you control pp of the overall stake, and we create a committee of kk people out of nn total (assume everyone has 11 stake), what’s the probability that you control more than 1/31/3 of the committee?
(open-ended; research-y) Suppose you can outsource a computation that costs you xx to compute to someone else by giving them your key. Now suppose the protocol allows you to punish people who outsource by showing the protocol that you have their key (and their account would get destroyed) but then the outsource loses reputation and must cancel their service. What kind of market would arise for outsourcing computations? What assumptions would you have to make?
(hard, but interesting) How would a prover prove (quickly) to a verifier that she did the following computation? “Given a polynomial in nn variables, I evaluated the polynomial at all points in the Boolean hypercube (meaning all 2n2n ways where each variable is set to 00 or 11) and I obtained ss.”
(first read Paxos and 2-phase commit) What are some advantages of Paxos over 2PC?
Suppose your computer only does computation in some field pp. How do you give a proof for a+b=c(modq)a+b=c(modq)? (be careful of overflow) For something more specific, assume your “proofs” can only consist of equation checks f(x)=0(modp)f(x)=0(modp).