		Search-engine friendly clone of the ACL2 documentation.

Committees

Committee-quorum-stake

Quorum stake in a committee.

Signature
(committee-quorum-stake commtt) → quorum
Arguments: commtt — Guard (committeep commtt).
Returns: quorum — Type (natp quorum).

As in the BFT literature, the quorum number in AleoBFT is n - f, where n and f are the numbers explained in max-faulty-for-total. As n and f are functions of the committee, the quorum number is a function of the committee too.

Some recent BFT literature uses 2f + 1 as the quorum number, which is correct only if n = 3f + 1, but not if n = 3f + 2 and n = 3f + 3, which are the other two possibilities, as discussed in max-faulty-for-total. Unfortunately that literature uses 2f + 1 without explicating the n = 3f + 1 assumption. There is indeed no reason for making this assumption, which is unnecessarily restrictive, given that the more general quorum n - f works for any value of n.

If the committee is not empty, the maximum tolerated faulty stake is less than the quorum stake.

Definitions and Theorems

Function: committee-quorum-stake

(defun committee-quorum-stake (commtt)
  (declare (xargs :guard (committeep commtt)))
  (let ((__function__ 'committee-quorum-stake))
    (declare (ignorable __function__))
    (- (committee-total-stake commtt)
       (committee-max-faulty-stake commtt))))

Theorem: natp-of-committee-quorum-stake

(defthm natp-of-committee-quorum-stake
  (b* ((quorum (committee-quorum-stake commtt)))
    (natp quorum))
  :rule-classes (:rewrite :type-prescription))

Theorem: posp-of-committee-quorum-stake

(defthm posp-of-committee-quorum-stake
  (implies (committee-nonemptyp commtt)
           (b* ((quorum (committee-quorum-stake commtt)))
             (posp quorum)))
  :rule-classes (:rewrite :type-prescription))

Theorem: committee-max-faulty-stake-lt-committee-quorum-stake

(defthm committee-max-faulty-stake-lt-committee-quorum-stake
  (implies (committee-nonemptyp commtt)
           (< (committee-max-faulty-stake commtt)
              (committee-quorum-stake commtt)))
  :rule-classes :linear)

Theorem: committee-quorum-stake-of-committee-fix-commtt

(defthm committee-quorum-stake-of-committee-fix-commtt
  (equal (committee-quorum-stake (committee-fix commtt))
         (committee-quorum-stake commtt)))

Theorem: committee-quorum-stake-committee-equiv-congruence-on-commtt

(defthm committee-quorum-stake-committee-equiv-congruence-on-commtt
  (implies (committee-equiv commtt commtt-equiv)
           (equal (committee-quorum-stake commtt)
                  (committee-quorum-stake commtt-equiv)))
  :rule-classes :congruence)