• Top
  • Documentation
  • Books
  • Boolean-reasoning
  • Projects
    • Apt
    • Acre
    • Milawa
    • Smtlink
    • Aleobft
      • Aleobft-static
      • Aleobft-dynamic
      • Aleobft-stake2
        • Definition
          • Initialization
          • Transitions
          • States
            • Committees
              • Max-faulty-for-total
              • Bonded-committee-at-round
              • Committee-members-stake
              • Active-committee-at-round
              • Update-committee-with-transaction
              • Committee-quorum-stake
              • Lookback
              • Committee-option
              • Update-committee-with-transaction-list
              • Committee-after-blocks
              • Same-bonded-committees-p
              • Same-active-committees-p
              • Committee
              • Committee-member-stake
              • Committee-total-stake
              • Committee-max-faulty-stake
              • Committee-nonemptyp
              • Committee-members
              • Address-pos-map
              • Genesis-committee
            • System-states
            • Certificates
            • Messages
            • Transactions
            • Validator-states
            • Addresses
            • Blocks
          • Events
      • Aleobft-stake
      • Library-extensions
    • Abnf
    • Vwsim
    • Isar
    • Wp-gen
    • Dimacs-reader
    • Pfcs
    • Legacy-defrstobj
    • Proof-checker-array
    • Soft
    • Farray
    • Rp-rewriter
    • Instant-runoff-voting
    • Imp-language
    • Sidekick
    • Leftist-trees
    • C
    • Java
    • Taspi
    • Bitcoin
    • Des
    • Ethereum
    • X86isa
    • Sha-2
    • Yul
    • Riscv
    • Zcash
    • Proof-checker-itp13
    • Regex
    • ACL2-programming-language
    • Json
    • Jfkr
    • Equational
    • Cryptography
    • Poseidon
    • Where-do-i-place-my-book
    • Bigmems
    • Builtins
    • Axe
    • Execloader
    • Solidity
    • Leo
    • Paco
    • Concurrent-programs
  • Debugging
  • Std
  • Proof-automation
  • Macro-libraries
  • ACL2
  • Interfacing-tools
  • Hardware-verification
  • Software-verification
  • Math
  • Testing-utilities

• 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+2, 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)