Unit 3: Basic Distributed Computing and Cryptography - Practice Quiz

Consensus is the process by which a group of distributed nodes reaches an agreement on a single value or state. In blockchain, this is crucial for maintaining a consistent and valid shared ledger across the entire network.

A Byzantine fault is the most severe type of fault, where a component can exhibit unpredictable and malicious behavior. A system that can withstand such faults is called Byzantine Fault Tolerant (BFT).

The core purpose of a hash function is to map data of an arbitrary size to a fixed-size output, known as the hash value or digest. For example, SHA-256 always produces a 256-bit hash, regardless of the input size.

A digital signature is created using the signer's private key. This ensures that only the owner of that key could have produced the signature, providing authenticity and non-repudiation.

Anyone can use the signer's corresponding public key to verify that the signature is authentic and was created by the owner of the private key, and that the signed message has not been altered.

Collision resistance is a critical security property. While collisions must theoretically exist (due to infinite possible inputs mapping to a finite number of outputs), it should be infeasible for an attacker to find one.

Puzzle-friendliness means it's hard to find an input that results in a specific hash. This is the basis of Proof-of-Work mining, where miners expend computational effort to find a nonce that produces a hash below a certain target.

A ZKP allows a 'prover' to convince a 'verifier' of the truth of a statement without revealing any extra information beyond the fact that the statement is indeed true.

Atomic broadcast, also known as total order broadcast, ensures two key properties: atomicity (all-or-nothing delivery) and total order (all recipients receive messages in the same sequence).

A VRF outputs a pseudorandom value along with a proof. The proof allows anyone with the public key to verify that the output was correctly calculated from the input, without being able to predict the output beforehand.

Cryptographic hash functions are deterministic. This means that a given input will always produce the exact same output, which is essential for verification purposes.

The purpose of BFT is to ensure that a distributed network can reach consensus and continue to operate securely and correctly, despite a limited number of nodes behaving in arbitrary, malicious ways.

A digital signature confirms the authenticity of the sender, ensures non-repudiation (the sender cannot deny signing it), and guarantees the integrity of the message (it has not been altered).

If an attacker could easily find a collision, they could create a malicious contract or file that hashes to the same value as a legitimate one, thereby fooling systems that use hashes for verification.

Puzzle-friendliness means there is no better way to find an input x that produces a desired output y (or an output in a certain range) than to simply try random inputs. This makes the search process a "puzzle".

This is a classic privacy-enhancing application of ZKPs. The proof can confirm that a financial rule is met (e.g., balance > transaction amount) without disclosing the specific sensitive numbers involved.

By ensuring all nodes agree on a single, ordered history of transactions, consensus mechanisms prevent a user from spending the same digital currency more than once (double-spending).

Atomicity ensures that if a message is delivered to one correct process, it is eventually delivered to all correct processes. It prevents a state where some nodes have received a message and others haven't.

A VRF allows a potential block producer to determine if they've been selected and create a proof of it, without tipping off other participants. This prevents targeted attacks on the next block producer before they have a chance to create the block.

The avalanche effect is a desirable property of cryptographic hash functions. It means that even a one-bit change in the input will, on average, change about half of the bits in the output hash, making the new hash appear completely random and unrelated to the first.

Total Order is a crucial property of atomic broadcast that ensures all non-faulty nodes deliver messages in the exact same sequence. This prevents state inconsistencies that arise from different orderings of operations, such as in the transaction example.

Atomic broadcast can be reduced to a series of consensus instances. For each 'slot' in the message log, nodes can run a consensus algorithm to agree on which message goes into that slot, thereby creating a total order agreed upon by all participants.

Probabilistic finality means that the certainty of a transaction being immutable increases with each subsequent block (or 'confirmation'). While the chance of a fork reversing the transaction becomes astronomically small over time, it is never mathematically zero.

Safety properties in consensus ensure that the system never enters an undesirable state. For consensus, this primarily means ensuring all non-faulty nodes agree on the same value (agreement) and that the agreed-upon value was proposed by some node (validity). Liveness, in contrast, ensures that something good eventually happens (e.g., a decision is eventually reached).

For a classical Byzantine Fault Tolerant system to reach consensus, it requires a minimum of total nodes, where is the maximum number of faulty nodes. In this case, . We solve for : . Therefore, the system can tolerate up to 4 faulty nodes.

pBFT operates in what is effectively a partially synchronous or weakly synchronous model. It doesn't require hard real-time deadlines (fully synchronous), but it relies on timeouts and the assumption that messages aren't delayed forever, allowing the protocol to make progress and eventually reach consensus.

The condition is a strict requirement for safety and liveness. If the number of Byzantine nodes exceeds , the protocol's assumptions are violated. Malicious nodes can then potentially equivocate (send conflicting messages) in a way that partitions the network, preventing honest nodes from reaching consensus (violating liveness) or, worse, causing them to agree on a fraudulent state (violating safety).

Pre-image resistance, also known as one-wayness, is the property that given a hash output , it is computationally infeasible to find an input such that . This is precisely what protects the original password from being discovered from its hash.

The avalanche effect is a desirable property of cryptographic hash functions where a tiny change in the input (like flipping a single bit) results in a drastic and unpredictable change in the output. On average, about half of the output bits should change, making the new output appear uncorrelated with the original.

A hash function is puzzle-friendly if, for any desired -bit output value , it's infeasible to find an input in time significantly less than such that , where is chosen from a high-entropy distribution. This means there's no shortcut to finding a valid nonce; miners must iterate through possibilities in a brute-force search.

The puzzle-friendly property relies on the hash function behaving like a random oracle. For any given input, the output should be pseudorandom and unpredictable. This requires the outputs to be uniformly distributed, ensuring that no part of the input search space is more likely to yield a "successful" hash than any other part. This forces a brute-force search.

Collision resistance is the property that makes it computationally infeasible to find any two different inputs, and , such that . In this scenario, the adversary is trying to find a fraudulent contract () that collides with the hash of the original contract ().

The birthday problem in probability shows that you don't need to check all possibilities to find a match. To find a collision for an -bit hash function (with possible outputs), one only needs to hash about inputs before the probability of a collision becomes substantial. Therefore, a 256-bit hash function offers about 128 bits of security against collision attacks.

To create a digital signature, the signer (Alice) uses her own private key on the message hash. This proves she is the originator, as only she has access to it. The verifier (Bob) then uses the signer's corresponding public key to validate the signature. If it's valid, it proves authenticity and integrity.

A digital signature verifies the sender's identity and the message's integrity. However, it does not encrypt the message content itself. The message is typically sent in plaintext alongside the signature. To achieve confidentiality, the message must be separately encrypted, for example, using the recipient's public key.

A standard hash function's output is just the hash value. A VRF, on the other hand, takes a private key and an input to produce a pseudorandom output and a proof. Anyone with the corresponding public key can use the proof to verify that the output was generated correctly for that specific input, without needing to know the private key. This is crucial for provably fair and unpredictable leader election.

Using a future block hash for randomness is vulnerable to manipulation by miners. A miner could try to solve for a block hash that makes them win the lottery. A VRF solves this by having a user generate the random number using their private key. The result is pseudorandom and unpredictable to others, but the accompanying proof ensures it was generated honestly according to the protocol rules.

The core principle of 'zero-knowledge' is that the interaction (the proof) leaks no information about the secret (the 'witness') other than the truth of the statement being proven. The Verifier is convinced but gains no knowledge that would help them reconstruct the secret.

Systems like ZK-SNARKs often require an initial trusted setup phase to generate public parameters. This process creates a secret byproduct, often called 'toxic waste.' If any participant in the setup ceremony retains this toxic waste, they can forge proofs for false statements, compromising the integrity of the system. ZK-STARKs are often favored for their lack of this requirement ('transparent' setup).

The core property of consensus is Agreement: all correct processes must agree on the same value. The specific value chosen (e.g., X or Y) depends on the algorithm's rules, but the essential goal is that all honest participants converge on one and only one of the proposed values.

While Validity, Integrity, and Agreement are properties of Reliable Broadcast, Total Order is the unique, defining guarantee of Atomic Broadcast. For state machine replication, it is not enough that all nodes receive the same set of messages (guaranteed by Reliable Broadcast); they must also process them in the exact same sequence to maintain identical states. Total Order ensures this sequential consistency across all correct replicas, which is the cornerstone of preventing state divergence in systems like blockchains.

The FLP result applies strictly to fully asynchronous systems where messages can be delayed indefinitely. Practical BFT protocols like PBFT operate in a model that is mostly asynchronous but makes certain weak synchrony assumptions. For instance, they assume that messages between correct nodes will eventually be delivered within some unknown but finite time bound (). This assumption is used in mechanisms like view changes, which are triggered by timeouts, to ensure liveness. By stepping outside the strict constraints of the FLP model, they can provide guarantees of both safety and liveness.

The core problem with arises from the possibility of a network partition orchestrated by faulty nodes. Consider a system with nodes. If nodes are Byzantine (including the primary), they can send one message to a group of honest nodes and a conflicting message to the other honest nodes. From the perspective of the first group of honest nodes, they see their message plus faulty nodes and are waiting for a response from the other honest nodes, whom they cannot distinguish from the faulty ones. They cannot reach a quorum of to proceed. The same deadlock occurs in the second group. By having , any two quorums of size must intersect by at least nodes. Since at most can be faulty, this intersection is guaranteed to contain at least one honest node, ensuring that conflicting information cannot be committed.

In Bitcoin mining, the block header (or parts of it, like the Merkle root and previous block hash) acts as the high min-entropy key . Because this k is different and unpredictable for every new mining attempt, miners cannot perform amortization attacks. An amortization attack would involve pre-computing a massive table of inputs that lead to desirable outputs (e.g., hashes with many leading zeros). Since the k changes for each block, any pre-computed work becomes useless. This forces miners to perform the full brute-force search for each new block, making the puzzle genuinely 'friendly' to parallel, real-time computation rather than pre-computation.

The attacker can manipulate the two signature equations. From the equations, we have and . By setting them equal: . Rearranging this gives , which leads to . Once the secret value is recovered, the attacker can substitute it back into either of the original signature equations to solve for the private key : . This demonstrates the catastrophic failure caused by -reuse.

The security of the zk-SNARK relies on the prover not knowing the underlying structure of the CRS, which is defined by the secret 'toxic waste' values. If an attacker knows these secrets, they can bypass the computational constraints that an honest prover must adhere to. This allows them to forge proofs for any statement, including false ones. For example, in a system like Zcash, they could create a proof for a transaction that creates new coins without a corresponding input, violating the system's conservation-of-value rule. This breaks the 'soundness' property of the proof system.

The core of a grinding attack is trying multiple inputs to 'grind' through possibilities until a favorable outcome is found. A VRF's verifiability property binds a specific public key (and its corresponding secret key) to a unique and deterministic output for a given public input (the seed). The proof allows anyone to verify that is the correct output for that specific key and seed. This means a user cannot try to influence the seed or their key and then generate a proof for a more favorable output; the proof would simply fail verification. It forces them to commit to the single output produced by their key, making the randomness fair and non-malleable.

Digital signature schemes are almost always implemented as 'hash-then-sign' for efficiency and security. The user signs the cryptographic hash of the message, not the entire message. In this scenario, the CEO sees and approves the benign contract.pdf. Their signing software computes and the CEO signs , producing a signature . Since , the same signature is also a valid signature for the hash of malware.exe. The attacker can now pair with malware.exe, and any verification process will confirm that the CEO signed it, as Verify(PK_CEO, malware.exe, \sigma) will compute and check the signature against it, which will succeed.

The length extension attack is a characteristic vulnerability of hash functions that use the Merkle-Damgård construction, which includes the widely used SHA-1 and SHA-2 families. The internal state of the hash function after processing a message is precisely the hash output . An attacker can use this output as the initialization vector (IV) to continue hashing additional data (the extension), effectively computing using only and the length of . Hash functions like SHA-3, which use a sponge construction, are not vulnerable to this attack.

The original oral messages protocol by Lamport, requiring , assumed messages could be forged by Byzantine nodes pretending to be someone else. The Dolev-Strong protocol introduces the assumption of an 'authenticated broadcast' channel, practically implemented with digital signatures. With unforgeable messages, a Byzantine node cannot relay a message and change its content, nor can it forge a message from a correct node. This added security reduces the node requirement to . However, the classic Dolev-Strong protocol pays a significant performance penalty: it requires rounds of communication, which can be inefficient compared to the constant number of rounds in protocols like PBFT.

zk-STARKs (Scalable Transparent Arguments of Knowledge) build their security on much simpler and more battle-tested cryptographic assumptions. Their primary building block is the collision resistance of a hash function. The 'T' for 'Transparent' in STARK refers to the fact that the public parameters are generated in a deterministic way from a public string, requiring no secret 'toxic waste' and therefore no trust. This makes them quantum-resistant (assuming the hash function is). In contrast, many popular zk-SNARKs rely on more complex and less understood assumptions like bilinear pairings on elliptic curves, which are known to be vulnerable to quantum computers.

The linearity of Schnorr signatures allows for simple aggregation through elliptic curve point addition. A Schnorr signature is a pair where and . For two signatures on the same message , we have and . By simply adding the components, we get an aggregate public key , an aggregate nonce commitment , and an aggregate signature . The verification equation will hold for the aggregated values, making it a highly efficient method for multi-party signatures.

The requirement is a hard requirement for safety. With and , we have . This means the condition for intersecting quorums is no longer met. A malicious leader (one of the 4 Byzantine nodes) can propose Block A to 3 honest nodes and a conflicting Block B to the other 3 honest nodes. The Byzantine nodes can then provide the necessary supporting messages to each partition. The first set of 3 honest nodes + 3 Byzantine nodes (pretending to agree on A) form a quorum of 6. The second set of 3 honest nodes + 3 Byzantine nodes (pretending to agree on B) also form a quorum of 6. Each partition sees a valid quorum and commits its respective block, leading to a permanent fork or state divergence, which is a catastrophic safety failure.

During a network partition, Bitcoin does not halt. Both sides of the partition continue to mine and add blocks to their respective chains. This demonstrates that the system remains Available and is inherently Partition Tolerant. However, this comes at the cost of Consistency. The two partitions will have different versions of the ledger. Once the partition is resolved, the network follows the 'longest chain' rule to resolve the fork, and one of the chains is orphaned. This means that for a period, the system was inconsistent. Therefore, Nakamoto consensus is best described as an AP system that provides eventual consistency.

An ideal cryptographic hash function should behave like a random oracle, where every output bit is a separate, unpredictable function of the input. This puzzle design, however, creates a potential vulnerability if there are subtle biases or correlations in the output bits. For example, if an attacker finds a way to slightly bias the output towards having more 0s than 1s, they gain an advantage in solving the puzzle. Standard puzzle-friendliness (finding an output with a certain prefix) relies on the infeasibility of finding an input for a specific output value. This new puzzle relies on a statistical property of the entire output, making it sensitive to non-randomness across the output bits, a property that is often assumed but harder to prove than basic resistance properties.

A collision attack gives the attacker freedom to choose both inputs ( and ). Due to the birthday paradox, the complexity of this attack is approximately . A second-preimage attack is more constrained: the attacker is given a specific input and must find a different input that produces the same hash. The best known attack for this is a brute-force search, which has a complexity of . Therefore, for a secure hash function, finding a second preimage is exponentially harder than finding a collision.

The pseudorandomness property of a VRF ensures that its output is computationally indistinguishable from a truly random value to anyone who does not possess the secret key. Even if an adversary has a large number of input-output pairs , they cannot gain any advantage in predicting the output for a new input . This is analogous to the security property of a standard Pseudorandom Function (PRF). The verifiability and uniqueness properties are distinct: verifiability allows for public checking, and uniqueness guarantees a single valid output per input, but pseudorandomness is what guarantees unpredictability.

The Fiat-Shamir heuristic replaces the verifier's random challenge with a non-interactive, deterministic one. The prover first computes their commitment message (). Then, instead of waiting for the verifier, the prover computes the challenge as . The prover is now 'committed' to the value before knowing the challenge , because they cannot find a different commitment that would yield a favorable challenge without breaking the collision resistance of the hash function . This process models the behavior of a truly random oracle, and its security relies on the hash function behaving like one. The prover then computes the response based on and and publishes the tuple (commitment, response) as the non-interactive proof.

The PREPARE phase is critical for safety, specifically for achieving total order within a view. A malicious primary could send a PRE-PREPARE message for a request with sequence number seq to some replicas, and a different PRE-PREPARE for another request with the same seq to other replicas. Without the PREPARE phase, both sets of replicas might proceed to commit conflicting requests at the same sequence number. The PREPARE phase acts as a cross-check among replicas. By broadcasting PREPARE messages and waiting for a quorum of , each replica verifies that a sufficient number of other replicas agree on the same request for that specific sequence number before committing. This prevents conflicting requests from being committed at the same logical point in the sequence.

A commitment scheme must have two properties: Hiding and Binding.

• Hiding means that given the commitment h, it is infeasible to determine the value v. This property relies on the preimage resistance of the hash function. Because of the secret nonce r, an attacker cannot simply guess v and check the hash; they would have to find a preimage for h, which is computationally infeasible.
• Binding means that after committing to v, the user cannot later open the commitment to a different value v'. This relies on collision resistance. If the user could find a different (v', r') such that H(v || r) = H(v' || r'), they could break their commitment. Therefore, preimage resistance protects the secrecy of the value, and collision resistance binds the committer to their value.