Concurrent Honest Slot Leaders in Proof-of-Stake Blockchains

A Proof-of-Stake blockchain execution where honest blocks have double borders and adversarial blocks have single borders. The nodes are labeled with their round numbers. Note that there are multiple adversarial blocks at rounds 2 and 4. Also, there are multiple honest blocks at rounds 6 and 9. These latter rounds were treated sub-optimally in all previous analyses, in part because the adversary could possibly use them to create inconsistent views for honest nodes. Our new paper closes this gap by putting forth a stronger analysis.

Consider the eventual consensus Proof-of-Stake (PoS) blockchains under the longest-chain rule such as Ouroboros, Ouroboros Praos, Sleepy Consensus, Snow White, etc. All existing analyses use a sub-optimal honest majority assumption in that if multiple honest nodes win the block-creation lottery in the same round, the analysis either treats it as a bad event or, at best, a neutral event.

In our paper, we put forth a consistency analysis that takes advantage of these events and thus achieves an asymptotically optimal consistency error under the optimal honest majority assumption; this is a first in the literature. The analysis applies to both synchronous communication and communications with a bounded delay.

This improvement is important since a sub-optimal honest majority assumption leads to weak security parameters for the blockchain system. The paper is going to appear at the prestigious conference IEEE ICDCS 2020. We posted the full version of our paper at https://eprint.iacr.org/2020/041.

 

 

Hi, I’m Saad, a software engineer at Google. Welcome to my blog!

Here’s my curriculum vitae (updated February 2022).

 

This is one of my prized possessions, a 0x$1 check from Donald Knuth’s Bank of San Serriffe!

My Takeaways from “Endure,” by Alex Hutchinson

“Endure” by Alex Hutchinson

I finished listening to the book “Endure” by Alex Hutchinson. It is one of the most important books that I have read. I have had multiple important realizations from it.

Brain sets an expectation. Giving up is almost always a choice.

Brain sets an expectation. You know it or not, feel it or not, your brain sets an expectation at a physiological as well as a psychological level. Try as we may, the brain controls your actions (again, at both the physiological and psychological levels) so that you meet the expectation, but don’t exceed it.

Therefore, these expectations matter. Sometimes these expectations are conscious, in that we can spell them out. Other times, they are at a subconscious or even unconscious level. Are you aware of what you expect of yourself? Expect does not mean hope: what do you really, really expect of yourself?

Notes on the PCP Theorem and the Hardness of Approximation: Part 1

In this note, we are going to state the PCP theorem and its relation to the hardness of approximating some NP-hard problem.

PCP Theorem: the Interactive Proof View

Intuitively, a PCP (Probabilistically Checkable Proof) system is an interactive proof system where the verifier is given random bits and he is allowed to look into the proof in many locations. If the string is indeed in the language, then there exists a proof so that the verifier always accepts. However, if is not in the language, no prover can convince this verier with probability more than . The proof has to be short i.e., of size at most . This class of language is designated as PCP[r(n), q(n)].

Theorem A (PCP theorem). Every NP language has a highly efficient PCP verifier. In particular,

.

What I Learned from “Never Split the Difference,” a Book by Chris Voss

[In a hurry? Jump straight to the bullet points.]

HBO charged me $15 via Amazon for my subscription that I forgot to cancel after the Game of Thrones was over. Upon writing to Amazon, the representative said:

As per policy we are unable to issue refund for the previous month charge (September) for your HBO subscription. However, I am able to make an exception for you and have issued you a promotional credit of $15.14 in your account.

Walmart manager said he would not accept my returns (worth $107) without a receipt.  Although the first guy said he would give me a gift card, the system didn’t let him proceed. The manager came in and told me they wouldn’t take these returns. Why? Because they have recently changed the rule: without a receipt, I can return items worth only up to $25.

Impagliazzo’s Hardcore Lemma: a Proof

Informally speaking, Impagliazzo’s hardcore lemma says that if a boolean function is “hard to compute on average” by small circuits, then there exists a set of inputs on which the same function is “extremely hard to compute on average” by slightly smaller circuits.

In this post, I am going to explain how I understand the proof of the hardcore lemma presented in the Arora-Barak complexity book (here). Because the formal proof can be found in the book I intend to write in an informal way. I think some subtleties are involved in turning the context of the lemma into a suitable two-player zero-sum game. Doing so enables one to use von Neumann’s minimax theorem to effectively “exchange the quantifiers” in the contrapositive statement of the lemma. Although the Arora-Barak proof mentions these subtleties, I am going to explore these in more detail and in a more accessible way for a beginner like me.

What Is Your Excuse Today?

I changed my mind before entering the blue doors of the weight room in my gym. There was the soothing sound of water trickling  down from the fountain. I felt more thirsty as I waited.

— “Hey, Saad!” exclaimed a low voice. I looked to my right. He just came out of that blue door of the weight room.

— “You used to be my TA !” he said. It always feels good to meet your past students, especially ones that still remember you. I looked hard. Remembering my students’ names used to be my forte, but probably not anymore.

Const-Pointer and Pointer-to-Const in C / C++

You must have known it already, but I can’t stop myself from showing off the interplay of const with pointers in C/C++.

Here goes the code. It’s simple.

void main() {

	int arr[]={1,2,3,4}; // data

	const int *p1 = &arr[0]; // non-const ptr to const data
	int const *p2 = &arr[0]; // non-const ptr to const data
	int* const p3 = &arr[0]; // const ptr to non-const data
	const int* const p4 = &arr[0]; // const ptr to const data

	p1++; // ok
	p1[0]++; // compile error: modifying const data

	p2++; // ok
	p2[0]++; // compile error: modifying const data

	p3++; // compile error: modifying const ptr
	p3[0]++; // ok 

	p4++; // compile error: modifying const ptr
	p4[0]++; // compile error: modifying const data

}

Eigenvalues of the Laplacian Matrix of the Complete Graph

A complete graph (source: David Benbennick)

We will show that the eigenvalues of the Laplacian matrix of the complete graph are where  the eigenvalue has (algebraic) multiplicity and the eigenvalue has multiplicity .

Hello world!

Welcome to WordPress.com. This is your first post. Edit or delete it and start blogging!