<div dir="ltr"><div class="gmail_extra">All,</div><div class="gmail_extra"><br></div><div class="gmail_extra">One of the reasons that I am interested in BitCoin is that I want to be able to ground the PPE PKI in some form of Certificate Transparency type append-only log. For my purposes the proof of work concept is just not viable (and I don't think it is viable for BitCoin either after the minting stops).</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">So here is my alternative, a co-op notary which operates under rules that are designed to make it coercion proof after some time t which is sufficiently close to the current time (i.e. no more than one to 24 hours behind depending on taste).</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">We distinguish between the following attacks</div><div class="gmail_extra"><br></div><div class="gmail_extra">1) An attack in which a defecting or coerced notary rewrites the log output for time t-n (n positive)</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">2) An attack in which a defecting or coerced notary rewrites the log output for time t+n (n is >= 0)</div><div class="gmail_extra"><br></div><div class="gmail_extra">
We are only concerned with providing relying parties with an assurance that the system is proof against the first type of attack. For the purposes of analysis coercion and defection have the same effect. For the sake of convenience lets call this an external failure.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">The second attack is one example of an internal failure. An internal failure is not considered a failure of the system but it might lead to consequences and possibly the notary being booted from the co-op.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">Another example of an internal failure would be if a notary failed to provide their next state within the timeframe for the next update.</div><div class="gmail_extra">
<br></div><div class="gmail_extra"><br></div><div class="gmail_extra">A co-op notary would consist of a set of notaries N_0, N_1, .. N_n each of which is a peer. Ideally n should be sufficiently large to ensure that coercion and collusion are improbable, 5 being a bare minimum, 16 being a better one. But admitting members does impose an administrative cost and there is probably little value in having n be greater than 64. If a very large number of parties (thousands) wanted to run a co-op notary it would probably be best to organize it as multiple co-ops participating in a meta-co-op.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">Membership of the co-op is dynamic. Members join and leave periodically. In the case of a defection (or suspected defection) the members of the quorum may vote to eject a member.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">The co-op maintains a single log chain. For the sake of argument, lets assume it is stored as a Merkle tree for efficiency but there are other options.</div><div class="gmail_extra">
<br></div><div class="gmail_extra"><br></div><div class="gmail_extra">All actions of the co-op are recorded in the log-chain. These include votes to accept/reject new members and votes to eject members.</div><div class="gmail_extra">
<br></div><div class="gmail_extra">At each time interval, each member m provides an input value I_mt (i.e. the head of their local notary chain) and a Signature value S_mt described below</div><div class="gmail_extra"><br>
</div><div class="gmail_extra">The output of the log chain at time t is O_t</div><div class="gmail_extra"><br></div><div class="gmail_extra">O_t+1 = H ( O_t + I_st + S_st)</div><div class="gmail_extra"><br></div><div class="gmail_extra">
Where I_st is the set of input values and S_st is the set of signature values</div><div class="gmail_extra"><br></div><div class="gmail_extra">S_m = Sign ( t + O_t + I_mt  + X , k)  </div><div class="gmail_extra"><br></div>
<div class="gmail_extra">Where X is some additional information that might turn out to be needed and Sign (x,k) returns x along with the signature of x under key k.</div><div class="gmail_extra"><br></div><div class="gmail_extra">
X would at minimum include all the signed votes cast by that member.</div><div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra">Ideally the set I_st and S_st should be complete, i.e. have an entry from every member. But that might not always happen. One possibility is that the member comes under a DoS attack. </div>
<div class="gmail_extra"><br></div><div class="gmail_extra">Each member is obliged to publish the S_m value within some fixed interval of a new output being decided. This would be to a publicly visible site that can be seen by relying parties. </div>
<div class="gmail_extra"><br></div><div class="gmail_extra">Each member fetches the S_m values from every other member and publishes them on their own site. </div><div class="gmail_extra"><br></div><div class="gmail_extra">
Each member is obliged to publish its best proposal for the set S_st' and thus the next output of the log chain some time interval before it is due. Each member would then review the proposals and cast a (signed) vote for what they believe the next S_st' should be. A majority being required for a decision. Each notary being obliged to vote for the proposal that includes the most information.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra">If a notary produces multiple signed outputs for a given value then that is a defection and on the signed proof being published members would be obliged to exclude data from that notary unless and until there was an affirmative vote to include it again.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">If the number of members was very large it would not be necessary for every member to vote on every time beat. Voting rights can be assigned pseudorandomly using the previous O_t as the seed.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra">A key design objective of the proposal is that all that is necessary to validate the future outputs of the log chain is to know the output value for just one point in time.<br>
</div><div class="gmail_extra"><br></div><div class="gmail_extra">Unlike my previous proposals it is not necessary to know any public keys of the members. There are no quorate votes. Everything is in the archived log chain. One trusted output value suffices to validate the certificates that can then be used to validate the future log values. </div>
<div class="gmail_extra"><br></div><div class="gmail_extra">For the sake of efficiency, the current state of the notary membership, their signatures keys, etc. could be recorded in a 'crib' that is agreed upon by the members and included in their signed outputs.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra">A relying party looking to verify a notary output may do so with varying degrees of trust.</div><div class="gmail_extra"><br></div>
<div class="gmail_extra">* Always rely on one given member (e.g. US courts might be required to rely on the NIST value).</div><div class="gmail_extra"><br></div><div class="gmail_extra">* Always rely on one randomly chosen member.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">* Choose a set of members and rely on a quorum of signatures.</div><div class="gmail_extra"><br></div><div class="gmail_extra">* Check every signature from every notary.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra"><br></div><div class="gmail_extra">One nice feature of the co-op approach is that it allows for gradualism. The co-ops could be started by grad students at universities and as reliance on the system grows, the functions might be taken over by their departments.</div>
<div class="gmail_extra"><br></div><div class="gmail_extra">Commercial providers are interesting in that they bring an exceptionally high level of resources compared to institutions or even government departments but they are inherently short lived. Google and Facebook might look like they will last forever but so did Netscape and Sun and DEC. IBM once looked more permanent than any of them and it isn't a major force in the businesses it once used to rule. </div>
</div>