An approximate introduction to how zk-SNARKs are possible (part 2)
If tasked with the problem of coming up with a zk-SNARK protocol, many people would make their way to this point and then get stuck and give up. How can a verifier possibly check every single piece of the computation, without looking at each piece of the computation individually? But it turns out that there is a clever solution.
Polynomials
Polynomials are a special class of algebraic expressions of the form:
- x+5
- x^4
- x^3+3x^2+3x+1
- 628x^{271}+318x^{270}+530x^{269}+…+69x+381
i.e. they are a sum of any (finite!) number of terms of the form cx^k
There are many things that are fascinating about polynomials. But here we are going to zoom in on a particular one: polynomials are a single mathematical object that can contain an unbounded amount of information (think of them as a list of integers and this is obvious). The fourth example above contained 816 digits of tau, and one can easily imagine a polynomial that contains far more.
Furthermore, a single equation between polynomials can represent an unbounded number of equations between numbers. For example, consider the equation A(x)+ B(x) = C(x). If this equation is true, then it's also true that:
- A(0)+B(0)=C(0)
- A(1)+B(1)=C(1)
- A(2)+B(2)=C(2)
- A(3)+B(3)=C(3)
And so on for every possible coordinate. You can even construct polynomials to deliberately represent sets of numbers so you can check many equations all at once. For example, suppose that you wanted to check:
- 12+1=13
- 10+8=18
- 15+8=23
- 15+13=28
You can use a procedure called Lagrange interpolation to construct polynomials A(x) that give (12,10,15,15) as outputs at some specific set of coordinates (eg. (0,1,2,3)), B(x) the outputs (1,8,8,13) on thos same coordinates, and so forth. In fact, here are the polynomials:
- A(x)=-2x^3+\frac{19}{2}x^2-\frac{19}{2}x+12
- B(x)=2x^3-\frac{19}{2}x^2+\frac{29}{2}x+1
- C(x)=5x+13
Checking the equation A(x)+B(x)=C(x) with these polynomials checks all four above equations at the same time.
Comparing a polynomial to itself
You can even check relationships between a large number of adjacent evaluations of the same polynomial using a simple polynomial equation. This is slightly more advanced. Suppose that you want to check that, for a given polynomial F, F(x+2)=F(x)+F(x+1) with the integer range {0,1…89} (so if you also check F(0)=F(1)=1, then F(100) would be the 100th Fibonacci number)
As polynomials, F(x+2)-F(x+1)-F(x) would not be exactly zero, as it could give arbitrary answers outside the range x={0,1…98}. But we can do something clever. In general, there is a rule that if a polynomial P is zero across some set S=\{x_1,x_2…x_n\} then it can be expressed as P(x)=Z(x)*H(x), where Z(x)=(x-x_1)*(x-x_2)*…*(x-x_n) and H(x) is also a polynomial. In other words, any polynomial that equals zero across some set is a (polynomial) multiple of the simplest (lowest-degree) polynomial that equals zero across that same set.
Why is this the case? It is a nice corollary of polynomial long division: the factor theorem. We know that, when dividing P(x) by Z(x), we will get a quotient Q(x) and a remainder R(x) is strictly less than that of Z(x). Since we know that P is zero on all of S, it means that R has to be zero on all of S as well. So we can simply compute R(x) via polynomial interpolation, since it's a polynomial of degree at most n-1 and we know n values (the zeros at S). Interpolating a polynomial with all zeroes gives the zero polynomial, thus R(x)=0 and H(x)=Q(x).
Going back to our example, if we have a polynomial F that encodes Fibonacci numbers (so F(x+2)=F(x)+F(x+1) across x=\{0,1…98\}), then I can convince you that F actually satisfies this condition by proving that the polynomial P(x)=F(x+2)-F(x+1)-F(x) is zero over that range, by giving you the quotient:
H(x)=\frac{F(x+2)-F(x+1)-F(x)}{Z(x)}
Where Z(x) = (x-0)*(x-1)*…*(x-98).
You can calculate Z(x) yourself (ideally you would have it precomputed), check the equation, and if the check passes then F(x) satisfies the condition!
Now, step back and notice what we did here. We converted a 100-step-long computation into a single equation with polynomials. Of course, proving the N'th Fibonacci number is not an especially useful task, especially since Fibonacci numbers have a closed form. But you can use exactly the same basic technique, just with some extra polynomials and some more complicated equations, to encode arbitrary computations with an arbitrarily large number of steps.
see part 3
(Edited)
Hackernoon
3 years ago
👏 Awesome post! When is part 3 coming?
Trent Lapinski
3 years ago
Very complex topic, great explanation
More on Web3 & Crypto
Tim Denning
3 years ago
The Dogecoin millionaire mysteriously disappeared.
The American who bought a meme cryptocurrency.
Cryptocurrency is the financial underground.
I love it. But there’s one thing I hate: scams. Over the last few years the Dogecoin cryptocurrency saw massive gains.
Glauber Contessoto overreacted. He shared his rags-to-riches cryptocurrency with the media.
He's only wealthy on paper. No longer Dogecoin millionaire.
Here's what he's doing now. It'll make you rethink cryptocurrency investing.
Strange beginnings
Glauber once had a $36,000-a-year job.
He grew up poor and wanted to make his mother proud. Tesla was his first investment. He bought GameStop stock after Reddit boosted it.
He bought whatever was hot.
He was a young investor. Memes, not research, influenced his decisions.
Elon Musk (aka Papa Elon) began tweeting about Dogecoin.
Doge is a 2013 cryptocurrency. One founder is Australian. He insists it's funny.
He was shocked anyone bought it LOL.
Doge is a Shiba Inu-themed meme. Now whenever I see a Shiba Inu, I think of Doge.
Elon helped drive up the price of Doge by talking about it in 2020 and 2021 (don't take investment advice from Elon; he's joking and gaslighting you).
Glauber caved. He invested everything in Doge. He borrowed from family and friends. He maxed out his credit card to buy more Doge. Yuck.
Internet dubbed him a genius. Slumdog millionaire and The Dogefather were nicknames. Elon pumped Doge on social media.
Good times.
From $180,000 to $1,000,000+
TikTok skyrocketed Doge's price.
Reddit fueled up. Influencers recommended buying Doge because of its popularity. Glauber's motto:
Scared money doesn't earn.
Glauber was no broke ass anymore.
His $180,000 Dogecoin investment became $1M. He championed investing. He quit his dumb job like a rebellious millennial.
A puppy dog meme captivated the internet.
Rise and fall
Whenever I invest in anything I ask myself “what utility does this have?”
Dogecoin is useless.
You buy it for the cute puppy face and hope others will too, driving up the price. All cryptocurrencies fell in 2021's second half.
Central banks raised interest rates, and inflation became a pain.
Dogecoin fell more than others. 90% decline.
Glauber’s Dogecoin is now worth $323K. Still no sales. His dog god is unshakeable. Confidence rocks. Dogecoin millionaire recently said...
“I should have sold some.”
Yes, sir.
He now avoids speculative cryptocurrencies like Dogecoin and focuses on Bitcoin and Ethereum.
I've long said this. Starbucks is building on Ethereum.
It's useful. Useful. Developers use Ethereum daily. Investing makes you wiser over time, like the Dogecoin millionaire.
When risk b*tch slaps you, humility follows, as it did for me when I lost money.
You have to lose money to make money. Few understand.
Dogecoin's omissions
You might be thinking Dogecoin is crap.
I'll take a contrarian stance. Dogecoin does nothing, but it has a strong community. Dogecoin dominates internet memes.
It's silly.
Not quite. The message of crypto that many people forget is that it’s a change in business model.
Businesses create products and services, then advertise to find customers. Crypto Web3 works backwards. A company builds a fanbase but sells them nothing.
Once the community reaches MVC (minimum viable community), a business can be formed.
Community members are relational versus transactional. They're invested in a cause and care about it (typically ownership in the business via crypto).
In this new world, Dogecoin has the most important feature.
Summary
While Dogecoin does have a community I still dislike it.
It's all shady. Anything Elon Musk recommends is a bad investment (except SpaceX & Tesla are great companies).
Dogecoin Millionaire has wised up and isn't YOLOing into more dog memes.
Don't follow the crowd or the hype. Investing is a long-term sport based on fundamentals and research.
Since Ethereum's inception, I've spent 10,000 hours researching.
Dogecoin will be the foundation of something new, like Pets.com at the start of the dot-com revolution. But I doubt Doge will boom.
Be safe!
Sam Hickmann
3 years ago
Nomad.xyz got exploited for $190M
Key Takeaways:
Another hack. This time was different. This is a doozy.
Why? Nomad got exploited for $190m. It was crypto's 5th-biggest hack. Ouch.
It wasn't hackers, but random folks. What happened:
A Nomad smart contract flaw was discovered. They couldn't drain the funds at once, so they tried numerous transactions. Rookie!
People noticed and copied the attack.
They just needed to discover a working transaction, substitute the other person's address with theirs, and run it.
In a two-and-a-half-hour attack, $190M was siphoned from Nomad Bridge.
Nomad is a novel approach to blockchain interoperability that leverages an optimistic mechanism to increase the security of cross-chain communication. — nomad.xyz
This hack was permissionless, therefore anyone could participate.
After the fatal blow, people fought over the scraps.
Cross-chain bridges remain a DeFi weakness and exploit target. When they collapse, it's typically total.
$190M...gobbled.
Unbacked assets are hurting Nomad-dependent chains. Moonbeam, EVMOS, and Milkomeda's TVLs dropped.
This incident is every-man-for-himself, although numerous whitehats exploited the issue...
But what triggered the feeding frenzy?
How did so many pick the bones?
After a normal upgrade in June, the bridge's Replica contract was initialized with a severe security issue. The 0x00 address was a trusted root, therefore all messages were valid by default.
After a botched first attempt (costing $350k in gas), the original attacker's exploit tx called process() without first 'proving' its validity.
The process() function executes all cross-chain messages and checks the merkle root of all messages (line 185).
The upgrade caused transactions with a'messages' value of 0 (invalid, according to old logic) to be read by default as 0x00, a trusted root, passing validation as 'proven'
Any process() calls were valid. In reality, a more sophisticated exploiter may have designed a contract to drain the whole bridge.
Copycat attackers simply copied/pasted the same process() function call using Etherscan, substituting their address.
The incident was a wild combination of crowdhacking, whitehat activities, and MEV-bot (Maximal Extractable Value) mayhem.
For example, 🍉🍉🍉. eth stole $4M from the bridge, but claims to be whitehat.
Others stood out for the wrong reasons. Repeat criminal Rari Capital (Artibrum) exploited over $3M in stablecoins, which moved to Tornado Cash.
The top three exploiters (with 95M between them) are:
$47M: 0x56D8B635A7C88Fd1104D23d632AF40c1C3Aac4e3
$40M: 0xBF293D5138a2a1BA407B43672643434C43827179
$8M: 0xB5C55f76f90Cc528B2609109Ca14d8d84593590E
Here's a list of all the exploiters:
The project conducted a Quantstamp audit in June; QSP-19 foreshadowed a similar problem.
The auditor's comments that "We feel the Nomad team misinterpreted the issue" speak to a troubling attitude towards security that the project's "Long-Term Security" plan appears to confirm:
Concerns were raised about the team's response time to a live, public exploit; the team's official acknowledgement came three hours later.
"Removing the Replica contract as owner" stopped the exploit, but it was too late to preserve the cash.
Closed blockchain systems are only as strong as their weakest link.
The Harmony network is in turmoil after its bridge was attacked and lost $100M in late June.
What's next for Nomad's ecosystems?
Moonbeam's TVL is now $135M, EVMOS's is $3M, and Milkomeda's is $20M.
Loss of confidence may do more damage than $190M.
Cross-chain infrastructure is difficult to secure in a new, experimental sector. Bridge attacks can pollute an entire ecosystem or more.
Nomadic liquidity has no permanent home, so consumers will always migrate in pursuit of the "next big thing" and get stung when attentiveness wanes.
DeFi still has easy prey...
Sources: rekt.news & The Milk Road.
Sam Hickmann
3 years ago
A quick guide to formatting your text on INTΞGRITY
[06/20/2022 update] We have now implemented a powerful text editor, but you can still use markdown.
Markdown:
Headers
SYNTAX:
# This is a heading 1
## This is a heading 2
### This is a heading 3
#### This is a heading 4
RESULT:
This is a heading 1
This is a heading 2
This is a heading 3
This is a heading 4
Emphasis
SYNTAX:
**This text will be bold**
~~Strikethrough~~
*You **can** combine them*
RESULT:
This text will be italic
This text will be bold
You can combine them
Images
SYNTAX:
RESULT:
Videos
SYNTAX:
https://www.youtube.com/watch?v=7KXGZAEWzn0
RESULT:
Links
SYNTAX:
[Int3grity website](https://www.int3grity.com)
RESULT:
Tweets
SYNTAX:
https://twitter.com/samhickmann/status/1503800505864130561
RESULT:
Blockquotes
SYNTAX:
> Human beings face ever more complex and urgent problems, and their effectiveness in dealing with these problems is a matter that is critical to the stability and continued progress of society. \- Doug Engelbart, 1961
RESULT:
Human beings face ever more complex and urgent problems, and their effectiveness in dealing with these problems is a matter that is critical to the stability and continued progress of society. - Doug Engelbart, 1961
Inline code
SYNTAX:
Text inside `backticks` on a line will be formatted like code.
RESULT:
Text inside backticks on a line will be formatted like code.
Code blocks
SYNTAX:
'''js
function fancyAlert(arg) {
if(arg) {
$.facebox({div:'#foo'})
}
}
'''
RESULT:
function fancyAlert(arg) {
if(arg) {
$.facebox({div:'#foo'})
}
}
Maths
We support LaTex to typeset math. We recommend reading the full documentation on the official website
SYNTAX:
$$[x^n+y^n=z^n]$$
RESULT:
[x^n+y^n=z^n]
Tables
SYNTAX:
| header a | header b |
| ---- | ---- |
| row 1 col 1 | row 1 col 2 |
RESULT:
| header a | header b | header c |
|---|---|---|
| row 1 col 1 | row 1 col 2 | row 1 col 3 |
You might also like
KonstantinDr
3 years ago
Early Adopters And the Fifth Reason WHY
Product management wizardry.
Early adopters buy a product even if it hasn't hit the market or has flaws.
Who are the early adopters?
Early adopters try a new technology or product first. Early adopters are interested in trying or buying new technologies and products before others. They're risk-tolerant and can provide initial cash flow and product reviews. They help a company's new product or technology gain social proof.
Early adopters are most common in the technology industry, but they're in every industry. They don't follow the crowd. They seek innovation and report product flaws before mass production. If the product works well, the first users become loyal customers, and colleagues value their opinion.
What to do with early adopters?
They can be used to collect feedback and initial product promotion, first sales, and product value validation.
How to find early followers?
Start with your immediate environment and target audience. Communicate with them to see if they're interested in your value proposition.
1) Innovators (2.5% of the population) are risk-takers seeking novelty. These people are the first to buy new and trendy items and drive social innovation. However, these people are usually elite;
Early adopters (13.5%) are inclined to accept innovations but are more cautious than innovators; they start using novelties when innovators or famous people do;
3) The early majority (34%) is conservative; they start using new products when many people have mastered them. When the early majority accepted the innovation, it became ingrained in people's minds.
4) Attracting 34% of the population later means the novelty has become a mass-market product. Innovators are using newer products;
5) Laggards (16%) are the most conservative, usually elderly people who use the same products.
Stages of new information acceptance
1. The information is strange and rejected by most. Accepted only by innovators;
2. When early adopters join, more people believe it's not so bad; when a critical mass is reached, the novelty becomes fashionable and most people use it.
3. Fascination with a novelty peaks, then declines; the majority and laggards start using it later; novelty becomes obsolete; innovators master something new.
Problems with early implementation
Early adopter sales have disadvantages.
Higher risk of defects
Selling to first-time users increases the risk of defects. Early adopters are often influential, so this can affect the brand's and its products' long-term perception.
Not what was expected
First-time buyers may be disappointed by the product. Marketing messages can mislead consumers, and if the first users believe the company misrepresented the product, this will affect future sales.
Compatibility issues
Some technological advances cause compatibility issues. Consumers may be disappointed if new technology is incompatible with their electronics.
Method 5 WHY
Let's talk about 5 why, a good tool for finding project problems' root causes. This method is also known as the five why rule, method, or questions.
The 5 why technique came from Toyota's lean manufacturing and helps quickly determine a problem's root cause.
On one, two, and three, you simply do this:
We identify and frame the issue for which a solution is sought.
We frequently ponder this question. The first 2-3 responses are frequently very dull, making you want to give up on this pointless exercise. However, after that, things get interesting. And occasionally it's so fascinating that you question whether you really needed to know.
We consider the final response, ponder it, and choose a course of action.
Always do the 5 whys with the customer or team to have a reasonable discussion and better understand what's happening.
And the “five whys” is a wonderful and simplest tool for introspection. With the accumulated practice, it is used almost automatically in any situation like “I can’t force myself to work, the mood is bad in the morning” or “why did I decide that I have no life without this food processor for 20,000 rubles, which will take half of my rather big kitchen.”
An illustration of the five whys
A simple, but real example from my work practice that I think is very indicative, given the participants' low IT skills. Anonymized, of course.
Users spend too long looking for tender documents.
Why? Because they must search through many company tender documents.
Why? Because the system can't filter department-specific bids.
Why? Because our contract management system requirements didn't include a department-tender link. That's it, right? We'll add a filter and be happy. but still…
why? Because we based the system's requirements on regulations for working with paper tender documents (when they still had envelopes and autopsies), not electronic ones, and there was no search mechanism.
Why? We didn't consider how our work would change when switching from paper to electronic tenders when drafting the requirements.
Now I know what to do in the future. We add a filter, enter department data, and teach users to use it. This is tactical, but strategically we review the same forgotten requirements to make all the necessary changes in a package, plus we include it in the checklist for the acceptance of final requirements for the future.
Errors when using 5 why
Five whys seems simple, but it can be misused.
Popular ones:
The accusation of everyone and everything is then introduced. After all, the 5 why method focuses on identifying the underlying causes rather than criticizing others. As a result, at the third step, it is not a good idea to conclude that the system is ineffective because users are stupid and that we can therefore do nothing about it.
to fight with all my might so that the outcome would be exactly 5 reasons, neither more nor less. 5 questions is a typical number (it sounds nice, yes), but there could be 3 or 7 in actuality.
Do not capture in-between responses. It is difficult to overestimate the power of the written or printed word, so the result is so-so when the focus is lost. That's it, I suppose. Simple, quick, and brilliant, like other project management tools.
Conclusion
Today we analyzed important study elements:
Early adopters and 5 WHY We've analyzed cases and live examples of how these methods help with product research and growth point identification. Next, consider the HADI cycle.
Nitin Sharma
3 years ago
Quietly Create a side business that will revolutionize everything in a year.
Quitting your job for a side gig isn't smart.
A few years ago, I would have laughed at the idea of starting a side business.
I never thought a side gig could earn more than my 9-to-5. My side gig pays more than my main job now.
You may then tell me to leave your job. But I don't want to gamble, and my side gig is important. Programming and web development help me write better because of my job.
Yes, I share work-related knowledge. Web development, web3, programming, money, investment, and side hustles are key.
Let me now show you how to make one.
Create a side business based on your profession or your interests.
I'd be direct.
Most people don't know where to start or which side business to pursue.
You can make money by taking online surveys, starting a YouTube channel, or playing web3 games, according to several blogs.
You won't make enough money and will waste time.
Nitin directs our efforts. My friend, you've worked and have talent. Profit from your talent.
Example:
College taught me web development. I soon created websites, freelanced, and made money. First year was hardest for me financially and personally.
As I worked, I became more skilled. Soon after, I got more work, wrote about web development on Medium, and started selling products.
I've built multiple income streams from web development. It wasn't easy. Web development skills got me a 9-to-5 job.
Focus on a specific skill and earn money in many ways. Most people start with something they hate or are bad at; the rest is predictable.
Result? They give up, frustrated.
Quietly focus for a year.
I started my side business in college and never told anyone. My parents didn't know what I did for fun.
The only motivation is time constraints. So I focused.
As I've said, I focused on my strengths (learned skills) and made money. Yes, I was among Medium's top 500 authors in a year and got a bonus.
How did I succeed? Since I know success takes time, I never imagined making enough money in a month. I spent a year concentrating.
I became wealthy. Now that I have multiple income sources, some businesses pay me based on my skill.
I recommend learning skills and working quietly for a year. You can do anything with this.
The hardest part will always be the beginning.
When someone says you can make more money working four hours a week. Leave that, it's bad advice.
If someone recommends a paid course to help you succeed, think twice.
The beginning is always the hardest.
I made many mistakes learning web development. When I started my technical content side gig, it was tough. I made mistakes and changed how I create content, which helped.
And it’s applicable everywhere.
Don't worry if you face problems at first. Time and effort heal all wounds.
Quitting your job to work a side job is not a good idea.
Some honest opinions.
Most online gurus encourage side businesses. It takes time to start and grow a side business.
Suppose you quit and started a side business.
After six months, what happens? Your side business won't provide enough money to survive.
Indeed. Later, you'll become demotivated and tense and look for work.
Instead, work 9-5, and start a side business. You decide. Stop watching Netflix and focus on your side business.
I know you're busy, but do it.
Next? It'll succeed or fail in six months. You can continue your side gig for another six months because you have a job and have tried it.
You'll probably make money, but you may need to change your side gig.
That’s it.
You've created a new revenue stream.
Remember.
Starting a side business, a company, or finding work is difficult. There's no free money in a competitive world. You'll only succeed with skill.
Read it again.
Focusing silently for a year can help you succeed.
I studied web development and wrote about it. First year was tough. I went viral, hit the top 500, and other firms asked me to write for them. So, my life changed.
Yours can too. One year of silence is required.
Enjoy!
Jenn Leach
3 years ago
This clever Instagram marketing technique increased my sales to $30,000 per month.
No Paid Ads Required
I had an online store. After a year of running the company alongside my 9-to-5, I made enough to resign.
That day was amazing.
This Instagram marketing plan helped the store succeed.
How did I increase my sales to five figures a month without using any paid advertising?
I used customer event marketing.
I'm not sure this term exists. I invented it to describe what I was doing.
Instagram word-of-mouth, fan engagement, and interaction drove sales.
If a customer liked or disliked a product, the buzz would drive attention to the store.
I used customer-based events to increase engagement and store sales.
Success!
Here are the weekly Instagram customer events I coordinated while running my business:
Be the Buyer Days
Flash sales
Mystery boxes
Be the Buyer Days: How do they work?
Be the Buyer Days are exactly that.
You choose a day to share stock selections with social media followers.
This is an easy approach to engaging customers and getting fans enthusiastic about new releases.
First, pick a handful of items you’re considering ordering. I’d usually pick around 3 for Be the Buyer Day.
Then I'd poll the crowd on Instagram to vote on their favorites.
This was before Instagram stories, polls, and all the other cool features Instagram offers today. I think using these tools now would make this event even better.
I'd ask customers their favorite back then.
The growing comments excited customers.
Then I'd declare the winner, acquire the products, and start selling it.
How do flash sales work?
I mostly ran flash sales.
You choose a limited number of itemsdd for a few-hour sale.
We wanted most sales to result in sold-out items.
When an item sells out, it contributes to the sensation of scarcity and can inspire customers to visit your store to buy a comparable product, join your email list, become a fan, etc.
We hoped they'd act quickly.
I'd hold flash deals twice a week, which generated scarcity and boosted sales.
The store had a few thousand Instagram followers when I started flash deals.
Each flash sale item would make $400 to $600.
$400 x 3= $1,200
That's $1,200 on social media!
Twice a week, you'll make roughly $10K a month from Instagram.
$1,200/day x 8 events/month=$9,600
Flash sales did great.
We held weekly flash deals and sent social media and email reminders. That’s about it!
How are mystery boxes put together?
All you do is package a box of store products and sell it as a mystery box on TikTok or retail websites.
A $100 mystery box would cost $30.
You're discounting high-value boxes.
This is a clever approach to get rid of excess inventory and makes customers happy.
It worked!
Be the Buyer Days, flash deals, and mystery boxes helped build my company without paid advertisements.
All companies can use customer event marketing. Involving customers and providing an engaging environment can boost sales.
Try it!