blockchain1 Flashcards
what is the goal of a fault tolerant distributed system
when failures occur, continue to operate in an acceptable way while repairs are being made
What is the server behaviour with byzantine failure
may produce arbitrary responses at arbitrary times
if process P no longer perceives any action from another process Q, can process P always assume that Q has halted
Depends on the synchrony assumption of the network
Why do we need different communication models (aka. synchrony assumption)
- different models have their own definitions of reliability.
- different networks have different protocols have a different complexity of making a disparate tradeoff
- o If the assumption is violated (in reality), then the properties guaranteed (in
theory) by the distributed system protocols might not hold anymore, leading to unexpected or undesirable outcomes.
Partial synchrony model [DLS88]
– asynchronous until Global Stabilization
Time (GST), then eventually synchronous with known time bound Δ
o adversary must cause the GST event to happen after some unknown finite time
o message sent at time t must be
delivered by time Δ + max(t, GST)
Why Partial Synchrony, Why not using only synchrony model, and set a conservative (large) bound Δ?
o Many protocols run in “rounds/epoch”, but a large Δ (e.g. 1 hour) would result in
a long timeout for each round of communication, thus degrading performance.
o An aggressively small Δ may not faithfully model the reality, and thus, protocols
whose safety relies on the realistically set bound might suffer safety violations.
Achieving Fault Tolerance
- Process resilience (protection against process failure) via replicating processes into groups
- Consensus among the group members
o Two types of replications ___________
primary-based replication (a hierarchical group
with a leader) and replicated-write replication (a flat group structure)
Consensus among the group members, describe what this means
o Ensure that the whole group behaves as “a single, highly robust process”
o Each non-faulty process executes the same user-defined commands or
incoming user requests in the same order to maintain homogeneity!
A distributed system is k-fault tolerant if ___________
it can survive faults in k components
and still meet its specifications, requirements and deliverables to the users.
Conditions of consensus: // this is low priority to answer (LP)
o Agreement: No two honest nodes decide on different values at the end.
o Validity: If all honest nodes have input v, then v must be the decision value.
o Termination: Honest nodes must eventually decide on a value in V and halt.
Safety property:
nothing bad will happen
o “agreement” will not be disturbed in Agreement Problem
o “no transaction executed twice” in an accounting system
o “consistency” in context of CAP theorem (coming up soon)
Liveness property:
something good will eventually happen
• “termination” will be guaranteed in Agreement Problem
• “new blocks will always be mined” in a blockchain system
• “document on the cloud is available for access and edit” indicates the
liveness being held among the cloud servers running their consensus
• “availability” in context of CAP theorem (coming up soon)
Assuming there are f dishonest/treacherous generals within the group, how many total generals are required in the group to reach consensus?
We need at least 3f + 1 generals in the group for consensus.
what are the 2 most important characteristics of distributed systems
Appears as a single coherent system
Consists of Autonomous Computing Elements (Soccer Team)
What are the main design goals for distributed systems
Scalability
Distribution Transparency
What are the primary motivations behind replication in a distributed system
Scalability
Reliability
Fundamental Characteristics of Distributed Systems
- Concurrency
All components run concurrently; programs execute concurrently. - Loosely Coupled
There is no global clock and global shared memory. - Independent Failures
Any component can fail at any time and failures occur of each other.
What are the requirements for a crypto hash function
Efficiently computable
preimage resistance
2nd preimage resistance
collision resistance.
In Blockchain, we are interested in what type of hash functions
keyless collision resistant Hash Functions
What function does bitcoin key generation use
Elliptic Curve Cryptography (curve secp256k1)
What function does bitcoin ADDRESS generation us e
SHA256 and RIPEMD160
In Bitcoin transactions, what is the gap between the input and the output
the fee
How are digital signatures used to validate the authenticity of a transaction and the sender of that transaction
Step 1: The sender has some data that he/she would like to send to the receiver. The receiver wants to ensure that the data he/she receives from the sender has not been tampered and must have come from the sender and nobody else.
Step 2: The sender collects the data to be sent. Once finalized, the sender uses the SHA256 hash function to hash the data into a 256-bit number.
Step 3: The sender then signs the 256-bit number with his/her private key encrypting the 256-bit number into what’s called a Digital Signature. Now the sender sends the data, the Digital Signature, and his/her public key to the receiver (remember, you can’t use the public key to figure out the corresponding private key so it is ok to share).
The receiver must authenticate that the data sent was not altered and must have been sent by the person who has the corresponding private key to the shared public key.
Step 1: The receiver takes the Digital Signature and decrypts it with the received public key to get a 256-bit number. Applying the public key to the Digital Signature ‘reverses’ the sender’s step 3 above.
Step 2: Then, the receiver takes the received data and applies the SHA256 hash to it to get a 256-bit number. This is the same thing as the sender’s step 1 and 2.
Step 3: The receiver then checks to make sure the two 256-bit numbers are equal. If false, then somebody has tampered with the data or provided a public key that does not correspond to the private key of the sender. If true, the receiver knows the data is good to go.
