<html>
  <head>

    <meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
  </head>
  <body bgcolor="#FFFFFF" text="#000000">
    Hi Gang,<br>
    <br>
    last night I mentioned that the hashing algorithm bitcoin uses is
    based on another well known computer science problem. Well here it
    is: The Byzantine Generals' Problem<br>
    <br>
    On a bitcoin site there is a short write up:<br>
    <br>
    <a class="moz-txt-link-freetext" href="https://bitcointalk.org/oldSiteFiles/byzantine.html">https://bitcointalk.org/oldSiteFiles/byzantine.html</a><br>
    <font style="font-size: 18px"><br>
      The Byzantine Generals' Problem</font><br>
    <font style="font-size: 13px" face="helv, arial">
      <br>
      A number of Byzantine Generals each have a computer and want to
      attack the King's wi-fi by brute forcing the password, which
      they've learned is a certain number of characters in length. Once
      they stimulate the network to generate a packet, they must crack
      the password within a limited time to break in and erase the logs,
      lest they be discovered. They only have enough CPU power to crack
      it fast enough if a majority of them attack at the same time.<br>
      <br>
      They don't particularly care when the attack will be, just that
      they agree. It has been decided that anyone who feels like it will
      announce an attack time, which we'll call the "plan", and whatever
      plan is heard first will be the official plan. The problem is that
      the network is not instantaneous, and if two generals announce
      different plans at close to the same time, some may hear one first
      and others hear the other first.<br>
      <br>
      They use a proof-of-work chain to solve the problem. Once each
      general receives whatever plan he hears first, he sets his
      computer to solve a difficult hash-based proof-of-work problem
      that includes the plan in its hash. The proof-of-work is difficult
      enough that with all of them working at once, it's expected to
      take 10 minutes before one of them finds a solution and broadcasts
      it to the network. Once received, everyone adjusts the hash in
      their proof-of-work computation to include the first solution, so
      that when they find the next proof-of-work, it chains after the
      first one. If anyone was working on a different plan, they switch
      to this one, because its proof-of-work chain is now longer.<br>
      <br>
      After about two hours, the plan should be hashed by a chain of 12
      proofs-of-work. Every general, just by verifying the difficulty of
      the proof-of-work chain, can estimate how much parallel CPU power
      per hour was expended on it and see that it must have required the
      majority of the computers to produce in the allotted time. At the
      least, most of them had to have seen the plan, since the
      proof-of-work is proof that they worked on it. If the CPU power
      exhibited by the proof-of-work is sufficient to crack the
      password, they can safely attack at the agreed time.<br>
    </font><br>
    I also attached the full paper on it.<br>
    <br>
        Ciao,<br>
        Clif<br>
  </body>
</html>