[Cryptography] Preventing co-op notary defection

[Phillip Hallam-Baker]

All,

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

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

We distinguish between the following attacks

1) An attack in which a defecting or coerced notary rewrites the log output
for time t-n (n positive)

2) An attack in which a defecting or coerced notary rewrites the log output
for time t+n (n is >= 0)

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.

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.

Another example of an internal failure would be if a notary failed to
provide their next state within the timeframe for the next update.


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.

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.

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.


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.

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

The output of the log chain at time t is O_t

O_t+1 = H ( O_t + I_st + S_st)

Where I_st is the set of input values and S_st is the set of signature
values

S_m = Sign ( t + O_t + I_mt  + X , k)

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.

X would at minimum include all the signed votes cast by that member.


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.

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.

Each member fetches the S_m values from every other member and publishes
them on their own site.

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.


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.

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.


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.

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.

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.


A relying party looking to verify a notary output may do so with varying
degrees of trust.

* Always rely on one given member (e.g. US courts might be required to rely
on the NIST value).

* Always rely on one randomly chosen member.

* Choose a set of members and rely on a quorum of signatures.

* Check every signature from every notary.


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.

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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.metzdowd.com/pipermail/cryptography/attachments/20140701/ce69511f/attachment.html>