Connect with us

Blockchain

How Ethereum can scale with SNARKs 101

Published

on


The beginner guide I would have liked a few months ago before digging into this stuff

Marco De Rossi

What you’ll need:

  • a computer science background
  • the basics of Ethereum
  • the basics of calculus (constraints optimisation)

What you’ll get:

  • the basics of zero-knowledge SNARKs
  • the basics of Merkle trees
  • how Ethereum could scale to thousands of transactions per second thanks to SNARKs

SNARKs allow a Prover to prove to a Verifier that she/he has a solution W to the problem F with shared/known inputs X, without revealing W.

Finding the solution to the problem could require a huge amount of computational power and memory.

So the Verifier can basically be 100% sure that the Prover has worked properly (and found a solution), with neither re-doing the job by herself/himself to check the solution nor knowing the solution at all. It’s magic!

The process has 3 steps:

  • SETUP — The problem F (that need to be expressed as quadratic arithmetic program, see below) is prepared for SNARKs. This process is very high memory and computing intensive depending on the complexity of the problem (→ The number of inputs and constraints → The dimension of the matrix of the constraints satisfaction problem). The player who does the Setup (could be the Verifier itself) must be trusted by all parties, since the output of the Setup is used in the next phases. The setup is usually done using libsnark, a C++ library which is the most popular implementation for zkSNARKs.
  • PROVING — The Prover, who has a solution W for the problem F with shared inputs X (maybe she/he spent huge amounts of CPU and memory to find it!), uses libsnark and the output of the Setup phase to create a proof 𝚷. This process is definitely high memory and computing intensive (depending on the complexity of the problem, as above). The size of the output (i.e. proof 𝚷) is instead succinct and constant independently from the complexity of the problem. The Prover needs to trust who has done the Setup phase, since she/he uses its output…
  • VERIFYING — A Verifier — giving as input the output of the Setup phase, shared inputs X and proof 𝚷 – checks the proof. If the verification is successful, the Prover managed to prove to a Verifier that she/he has found the solution W to the problem F… without revealing W! The nice part is that not only the Proof is succinct and has always the same length.., the verification process is fast and not memory/computing intensive at all. Unlike the two previous phases… the verification can be easily done with a smartphone in milliseconds!

A good recap (source):

How can this happen? Well, it’s Merlin magic! If you want to get the maths behind this, start from here.

How can I transform my software to a quadratic arithmetic program?

As mentioned above, Setup phase’s problem F needs to be a quadratic arithmetic program. Rules of the game are tough:

  • Your software’s inputs should be numbers. Convert your stuff (arrays, strings, etc) to numbers. That’s trivial.
  • A “quadratically constrained system of equations” means:

where x is the n-dimensional vector of your inputs, m is the number of constraints (i.e. the number of equations of your system), C is the n-by-n coefficients Matrix and q is a n-dimensional coefficients vector. If you don’t like matrix and vectors, here is the n = 3 and m = 2 case (3 inputs, 2 constraints):

  • The implementation is an arithmetic circuit, which means that the outcome is Problem solved (the system is solved, i.e. all polynomials are equal to 0) or Problem not solved (all the other cases). In other words: “these inputs are/aren’t one of the solutions to this Problem”.
  • C₁, C₂, …, C𝚖, q₁, q₂, …, q𝚖 coefficients are the constraints of the system. This is basically what defines your software. Change them… and you’ll get another software! Getting back to how SNARKs work: C₁, C₂, …, C𝚖, q₁, q₂, …, q𝚖 are the input of the Setup phase. The output of the Setup phase (that you need for Proving and Verifying) is therefore strictly related to those C₁, C₂, …, C𝚖, q₁, q₂, …, q𝚖 and works only for that Problem. If you change them you’re defining another software/problem and you need to re-run the Setup phase! x₁, x₂, …, x𝗇 are the variables (i.e. what you have to guess to get a system’s solution). So when we say “Dear Prover, could you please find a secret solution W for problem F with shared/public inputs X” we mean for example “Dear Prover, can you find the x₁, x₂, …, x𝗇 values which solve the system with, for example, x₇ = 2393, x₅₂₆ = 5647?” You can do what you want with all x𝗇, except for x₇ and x₅₂₆, which are constrained to the shared/public inputs.

It’s a tough life but you can survive… If you need loops you can unfold them repeating the same operation many times. Or if you need for example x₁⁴ x₂⁵, you define a new input x₃ = x₁⁴ x₂⁵ and use x₃ in your constraints. It’s all about adding variables and constraints… Even for pretty simple softwares it’s easy to reach hundreds of millions or billions of inputs and constraints!

Want to know more? Read here. And also check out this basic code_to_r1cs.py from ethereum/research.

What’s a Merkle tree?

An hash function is a rule that maps an input of arbitrary size to an output of fixed size. We could invent a pretty useless hash function “Concatenate the first two with the last two letters” which transforms “Woody Allen” to “Woen” and “Paul McCartney” to “Paey”.

A Merkle tree is a data structure where every parent is the hash of its two sons. At the top you find the Root, which is the hash of the two sons of level 1. At the bottom, every leaf is the hash of an external input.

Using our fictionary “Woody Allen”→”Woen” hash function:

When a leaf changes, the modification is propagated up to the Root. If ANTHONY changes, also ANNY (leaf), CENY and CECO (Root) change. Whichever leaf changes, the Root changes too.

You don’t need the entire tree to recalculate the Root. In our example, if ANTHONY changes and you know both JACO and CECILY, you can easily recalculate the Root even if you completely ignore JAMES, MARCO, JAES and MACO. For huge trees this saves a lot of time!

So what?

Merkle trees are great for data integrity checks. Usually: you know which is the valid Root, and you check that the received data matches that Root. For example: a trusted party who can’t give you the entire data set of the first names of people on Earth (no time, no bandwidth or maybe she/he hasn’t the data at all) gives you only the Root (e.g. “CECO”). Afterwords: you receive millions of first names, with reference to the leaf number, by thousands of untrusted parties. Well, since you have the correct Root you can check who you can rely on, who is giving you fake data…

Merkle trees are part of your life too! When you’re downloading a 3GB Torrent file, your file is divided in millions of little chunks. The hash of every chunk is stored in a leaf. Since you know which is the valid Root of the tree, every time you receive a chunk of the file by somebody, you can check if it’s correct. If it’s not, you can ask the same chunk to somebody else.

You can do that even if you haven’t download yet the entire tree/all the leaves: if you know that the Root is CECO and you trust JACO… when you receive the chunk ANTHONY you can verify it even if you haven’t downloaded yet the chunks MARCO and JAMES.

Why Merkle trees are useful in distributed ledger technology is straightforward: you use consensus protocols (slow, expensive) only for reaching consensus on the Root. Then the untrusted nodes of the network can efficiently and directly share data… and can sleep safe and sound thanks to integrity checks with the Root.

When God asked Ethereum to choose 2 superpowers among Security, Scalability and Decentralization… Ethereum sacrificed Scalability. Actually there is no strong cap on “transactions per second”: the cap concerns the amount of gas of each block — which is, simplifying, the amount of operations that I can do in each block. This limit is 8 million gas. That could mean many “tiny” transactions (no data attached to the transactions, no operations to be executed on that data) or few large transactions. It’s up to Ethereum’s nodes, which submit transactions, and to Ethereum’s miners, who include in the block the transactions which pay more.

A block is mined every ~15 seconds. That means ~32 million gas per minute, which is definitely not enough if we want Ethereum’s dapps to go mainstream.

By the way: stop with those tedious comparisons between Ethereum and Visa. A centralized system will always be faster than Ethereum… by design! They do different stuff and you need them in different situations. If you don’t need decentralization and a trust-less environment… of course you should choose Visa. In short: the fact that your blender spins faster than your washing machine doesn’t mean you’ll clean your trousers in a blender!

Let’s put the puzzle together! Imagine you could “compress” many tiny transactions in one large transaction thanks to SNARKs. If the gas spent by this large transaction is less than the sum of the gas spent by the tiny transactions, that means you’re saving gas.

And saving gas means:

  • Users spending less for transactions overall → This would be a push for the entire ecosystem
  • Being able to put more stuff in a block → Ethereum spinning faster than your blender!

How does it work?

There are users, a relayer (or more relayers) who aggregates transactions and a smart contract.

  1. Users willing to play this game send their Ether (or tokens) to a publicly audited smart contract. For every new player a new leaf in a Merkle tree is created. The leaf includes information about the Ether’s owner (her/his address, which is also the public key), amount of Ether and nonce (the transactions’ counter of that account, which is 0 when the leaf is added)
  2. When A wants to send Ether to B (they both need to have a leaf/account in the smart contract), A packs a transaction, which includes the address of the fromaccount, the to account, the nonce of the from account, the amount of Ether to be transferred and the signature of the transaction (signed with the private key of the “from” account, obviously). She/he then sends the packed transaction to the relayer.
  3. The relayer aggregates all the transactions received in a given time window (e.g. one hour), updates the Merkle tree with the new balances’ amounts and creates a SNARK proof which proves that all signatures and the new Merkle tree’s root are valid. The relayer finally sends the new state and the proof to the smart contract.
  4. The smart contract validates the Proof on-chain. If it’s valid it saves the Merkle tree root of the New state in the internal memory of the contract.

Basically, the Merkle tree root depicts the entire state of all the accounts. And you can’t change it (= steal money) unless you can prove the validity of the signatures whose transactions lead to the New state summarized by the new root you’re submitting.

In a nutshell: users have super fast and almost free transactions, like on Coinbase, without needing to trust the relayer, who can’t do anything, unlike on Coinbase, without your signature.

It’s a non custodial side chain whose state is summarized by a Merkle tree root.

Let’s connect what we learnt above about SNARKs with what we just discussed about scaling. There are different ways to do that. I’ll compare 2 recipes: Vitalik’s version and barryWhiteHat’s version.

The SETUP is done by…

The guy who starts the project, who also creates the smart contract. The more auditable it is, the better.You should trust her/him… it’s a trusted setup!

The smart contract saves…

2 Merkle roots (bytes32 values): the first tree contains accounts’ addresses (public signatures), the second accounts’ balances and nonces

PROVING is done by…

The relayer

The relayer sends to the smart contract…

  • the 2 Merkle roots of the New state (addresses tree and balances+nonces tree)
  • the list of transactions, without signatures. “Each transaction costs 68 gas per byte. Hence, for a regular transfer, we can expect the marginal cost to be 68 * 3 (from) + 68 * 3 (to) + 68 * 1 (fee) + 68 * 4 + 4 * 2 (amount) + 68 * 2 (nonce), or 892 gas”

PROVING process’s known inputs are…

  • the 2 Old state Merkle roots
  • the 2 New state Merkle roots
  • transactions list

PROVING process proves that…

Given

  • the 2 Old state Merkle roots (already stored in the contract)
  • the 2 New state Merkle roots (sent in the aggr. transaction)
  • the transactions list (sent in the aggr. transaction)

… the relayer has valid signatures to move from state with 2 Old roots to state with 2 New roots with those transactions.

VERIFYING is done by…

The smart contract (coded in solidity, vyper, as you like!)

VERIFYING process’s known inputs are…

The same PROVING’s process known inputs, clearly…!

Limits to scalability

Every aggregated transaction uses 650k gas for SNARK verification (fixed cost) plus ~900 gas of marginal cost per transaction (It costs to send data!). So using the entire block the relayer can aggregate at most:

which means ~544 tx per second

barryWhiteHat’s version

The SETUP is done by…

The guy who starts the project.

The smart contract saves…

1 Merkle root with the current State. Every leaf is the hashed state of an account.

Want to create an account?

state = AccountState(pubkey, balance, nonce)
state.index = self._tree.append(state.hash())

PROVING is done by…

The relayer

The relayer sends to the smart contract…

  • proof 𝚷
  • the New state Merkle root
  • proof 𝚷

PROVING process’s known inputs are…

  • the Old state Merkle root
  • the New state Merkle root

PROVING process proves that…

Given

  • the Old Merkle root (already stored in the contract)
  • the New Merkle root (senti in the aggr. transaction)

… the relayer has a list of transactions with valid signatures to move from state with Old root to state with New root

VERIFYING is done by…

The smart contract (coded in solidity, vyper, as you like!)

VERIFYING process’s known inputs are…

The same PROVING’s process known inputs, clearly…!

Limits to scalability

The relayer is not sending transactions’ data to the smart contract (which is costly), so the limit is actually the amount of gas to verify the SNARK proof.

Mentioning Howard Wu’s work about running SNARK’s PROVING phase on distributed systems, barryWhiteHat optimistically states that is possible to confirm 16666 transactions in a huge SNARK (1 billion constraints!).

barryWhiteHat also thinks it’s possible to verify proof 𝚷 on-chain with 500k gas, which means that you can put 16 SNARKs (8 million/500k) per block, which is ~1.07 SNARKs per seconds… which means ~17,832 tx per second (16,666 * 1.07).

To infinity and beyond

  • All that glitters is not gold / 1. The amount of computing power and memory that you need in the Proving phase can be literally shocking. Especially in barryWhiteHat’s version, where part of the complexity is moved off-chain. barry writes “On a laptop with 7 GB of ram and 20 GB of swap space it struggles to aggregate 20 transactions per second”. Well, if the goal is 17,832 tx per second… LOL. This introduces non trivial parallel computation challenges. But if the average $ cost per transaction is far cheaper than the ordinary no-SNARKs option… the game is worth the candle.
  • All that glitters is not gold / 2. There is a relevant data availability issue! Since only the tree’s root is saved in the contract, you must be sure that an entire version of the tree (or, it’s the same, the entire transactions history) is always available. If data is not available the relayer, even with valid signed transactions, can’t do anything because she/he can’t prove Old State → Transactions → New State.
  • In order the relayer to be trustless and Ethers in the contract to have the same value of Ethers outside (liquidity problem)… users should be able to withdraw money from the smart contract when they want, without relying on a (specific) relayer. How? This is not in the scope of this 101 post, but you can read about this in the enclosed links.
  • Want to understand more about how the current State (addresses, balances and nonces) can be handled with a Merkle tree? Adding a leaf, updating a leaf, etc? Check out this library (test file here) which uses this underlying module. Thanks HarryR!
  • Want to setup your personal Ethereum-SNARKs environment? Let’s start off-chain with C++ (Setup, Proving, Verifying) here. Then you can move to Ethereum (don’t forget, only the Verification is done on-chain!) with Zokrates (repo, the documentation to get started with).
  • How about using RSA accumulators instead of Merkle trees? Google “rsa accumulators ethereum” to start…

Enjoy!

Twitter @marco_derossi

Source: https://tokeneconomy.co/how-ethereum-can-scale-with-snarks-101-5b06ff048bb7?source=rss—-fbbd350c08fc—4

Blockchain

Axie Infinity Records Holders ATH: 420% Year to Date Growth

Published

on

Popular non-fungible token (NFT) gaming platform Axie Infinity continues to see increased adoption from users, following exponential growth in the number of wallet addresses.

Axie Sees Surge in Address Holders

According to data provided by IntoTheBlock on Tuesday (September 28, 2021), Axie Infinity Shards (AXS) ownership is on the rise, with 17,480 address holders. This figure represents a new all-time high (ATH) and a 420% increase year-to-date (YTD). Meanwhile, this growth is indicative of the rising popularity of Axie Infinity and play-to-earn non-fungible token (NFT) gaming.

Back in July, CryptoPotato reported that the value of the AXS token skyrocketed nearly 400% within one month, leading to a market capitalization of over the $1 billion mark. Later in August, AXS was among the assets listed on the major cryptocurrency exchange Coinbase Pro, which also gave it an immediate boost.

Axis Infinity, developed by Sky Mavis and released in 2018, arguably popularised the play-to-earn trend and has recorded a number of impressive milestones in recent times. Data from DappRadar revealed that the project recorded over $2 billion in NFT sales volume, solidifying Axie’s place as the most valuable NFT collection, thereby surpassing major names such as CryptoPunks, Art Blocks, and NBA Top Shot.

The data also showed that more than 600,000 users traded Axis Infinity NFTs, resulting in 4,887,645 transactions. The project currently boasts over 1.5 million daily active users.


ADVERTISEMENT

According to Jeff Zirlin, co-founder of Axie Infinity, half of the platform’s users got to interact with cryptocurrency and blockchain for the first time through Axie, while 25% of them did not own a bank account.

The Growth of NFT Gaming

The NFT industry is becoming popular with celebrities, major sports leagues, and companies buying digital art in whatever form, or selling them. However, blockchain-based games are seeing a special kind of attention.

A report by DeFiPrime stated that the NFT Gaming market has a total market valuation of nearly $180 billion as of August 2021, with the value estimated to rise to $196 billion. An excerpt from the report reads:

“NFT games may have the potential to become the standard for the gaming market if it sees enough attention and popularity. Already they have made major changes to games and made it much more fun for players. From there, it could be a very major change to the way people play games and could be as major as Doom was to the market or 3D was for environments.”

SPECIAL OFFER (Sponsored)

Binance Futures 50 USDT FREE Voucher: Use this link to register & get 10% off fees and 50 USDT when trading 500 USDT (limited offer).

PrimeXBT Special Offer: Use this link to register & enter POTATO50 code to get 50% free bonus on any deposit up to 1 BTC.

You Might Also Like:


PlatoAi. Web3 Reimagined. Data Intelligence Amplified.

Click here to access.

Source: https://cryptopotato.com/axie-infinity-records-holders-ath-420-year-to-date-growth/

Continue Reading

Blockchain

Bitcoin, Ethereum will draw their market strength from this key aspect

Published

on

Bitcoin and Ethereum are currently surviving a bearish scare, with both assets just about holding a position above their immediate supports. For Bitcoin, the $41,000-level is establishing a strong bounceback range while Ethereum has managed to remain above $3000.

On the contrary, some altcoins have recorded strong recoveries, with Solana, Bitcoin Cash, and Uniswap hiking by more than 10% in one 24-hour window.

Now, these altcoins seemed to have the relative edge at press time. However, there are a couple of key metrics which may allow us to evaluate the actual strength of Bitcoin, Ethereum as the market goes forward.

How much importance should be given to utility?

Source: Sanbase

Over the past few years, market stability has been dependent on different aspects. During the bullish rally of 2017, investor sentiment was key and when major traders started to become bearish, the digital assets collapsed.

Then, it was constructive institutional inflows at the beginning of 2019. At the time, it was suggested that institutions can allow tokens such as BTC, ETH to hold higher price positions. The price fell in 2020, irrespective of rising interest.

However, one key idea missed by most speculators might be the utility side of things, which is presently one of the most important functionality. Gone are the days when astute marketing allowed assets such as TRON to climb into the top-10.

Now, according to Santiment, Bitcoin has hit a two-month high in terms of circulation. What’s more, if the chart is closely observed, the average BTC transferred has risen consistently over the month of September.

Source: Sanbase

Similarly, Ethereum hit a similar feat but its 1-day circulation index was at a 3-month high, indicative of high token utility and movement.

Ethereum’s price has dropped sharply over the course of the past few weeks, but circulation has remained high.

Bitcoin, Ethereum spaces have evolved

Now, to be fair, it is important to account for volatility and the fact the circulation isn’t as high as it was during May 2021. However, maintaining a development and transaction-intensive ecosystem, one which allows the price to be built on strong foundations, is eventually advantageous.

Now, with respect to the assets that have grown over the past few days, besides BCH, both Solana and Uniswap are extremely utilized tokens. While one is the native token of a major DEX, another asset is currently responsible for bringing better L2 solutions.

Likewise, for Bitcoin and Ethereum, higher utility and circulation should keep the asset relevant, and progressively exhibit significant recoveries over Q4 of 2021.

Where to Invest?

Subscribe to our newsletter

PlatoAi. Web3 Reimagined. Data Intelligence Amplified.

Click here to access.

Source: https://ambcrypto.com/bitcoin-ethereum-will-draw-their-market-strength-from-this-key-aspect

Continue Reading

Blockchain

Swaps.app Offering Seamless Crypto Swaps With No KYC Process

Published

on

Swaps.app Offering Seamless Crypto Swaps With No KYC Process

Advertisement &  & 

Swaps.app is simplifying how users are converting Bitcoin and other cryptocurrencies by eliminating the current barriers available in the market.

The EU-regulated company is changing how people swap cryptocurrencies for money with its “swap’n’Go” approach. The platform is a user-friendly space that allows anyone around the globe to effort conduct various trading activities.  

Swaps.app has various unique features. The platform notably offers low commissions and a faster transaction experience to its users compared to many other venues in the market.

Swaps.app offers the lowest fees in the industry while at the same time offering the best buying rates. Transactions performed on the Swaps.app employ price execution from top liquidity providers. In turn, this assures that Swaps.app customers get the best price possible for their purchase.

In addition, transactions on the platform take about 3 minutes. This is because there is no Know-Your-Customer (KYC) process and allows transactions to take three minutes to complete. This is a breath of fresh hair since the registration process associated with cryptocurrency exchanges is usually lengthy and cumbersome compared to most. The process has notably caused many people not to engage in cryptocurrency trade. 

Advertisement &  & 

Another notable feature is that coins get to users’ digital wallets within 15 minutes of payment approval. Swaps.app has two currencies available for purchase, including Tether (USDT) and Bitcoin (BTC). Currently, the platform is accepting two payment methods, Visa and MasterCard debit and credit cards. Users can purchase varying amounts of cryptocurrencies up to €1,000 per month.

To merchants and developers, Swaps.app provides a convenient order widget that can be integrated into any webpage with just a few clicks.

In addition to being regulated by the authorities, Swaps.app integrates a full 3-DS V2 for safe and secure transactions. Reportedly, card purchases that use PCI DSS Level 1 certification will be authorized by code and verified by Visa or Mastercard ID Check.

Swaps.app is now available to over 160 plus countries and is available 24/7 throughout the year. The platform is owned and operated by Octo Liquidity, based in Tallinn, Estonia.

PlatoAi. Web3 Reimagined. Data Intelligence Amplified.

Click here to access.

Source: https://zycrypto.com/swaps-app-offering-seamless-crypto-swaps-with-no-kyc-process/

Continue Reading
News5 days ago

Axie Infinity: Pagbabago ng SLP at AXS Breeding Requirements

Uncategorized5 days ago

How to identify items in Diablo 2: Resurrected

Blockchain4 days ago

Most expensive NFTs ever sold and the Non-Fungible Token’s expansion of expense.

Blockchain5 days ago

QuadrigaCX Saga to Be Covered By Netflix Documentary

Uncategorized4 days ago

Hashrate beats the S&P 500 or A word on the benefits of hashrate rental.

Uncategorized5 days ago

Why is NFT art valuable? Understand why they are worth millions

Blockchain3 days ago

The Three Kingdoms: Bringing a New Era of Play-to-Earn Games to The Blockchain Industry

Blockchain5 days ago

SEC Chair Gary Gensler Reveals Plans To Clean Up Crypto Space – Stablecoins At Grave Risk?

Uncategorized3 days ago

NBA 2K22 City Spawn Locations: How to Unlock

Blockchain2 days ago

BOOM Esports and NoPing e-sports claim the top spots in BTS Pro Series Season 8 SEA and Americas

Blockchain5 days ago

Cardano Launches dAppStore for Certified DeFi Apps

Blockchain4 days ago

Mars4 NFT Land Tokenomics

Blockchain5 days ago

Netflix Set to Premier Documentary About QuadrigaCX CEO in 2022

Blockchain5 days ago

With DeFi still in focus, Cobo raises $40M in Series B funding

Blockchain4 days ago

With BlockFi, Celsius under the radar now, what next for crypto-regulations

News4 days ago

The World’s Top 10 Companies Could Be Interested in Cryptocurrencies

Blockchain5 days ago

Bitcoin’s LN packs a punch, but is it truly far from having security concerns 

Uncategorized3 days ago

Best Stats for the Barbarian in Diablo II: Resurrected

Uncategorized4 days ago

FTX Relocates From Hong Kong to Bitcoin-Friendly Bahamas

Blockchain4 days ago

Top 10 NFT Sales Of This Week: September 19-25

Trending