{"tags":["grin","mimblewimble","privacy","privacy-blockchain","private-transactions","privacy-coin"],"id":"433e9df1049d4862b908d5825f27dadb_2","article_id":"433e9df1049d4862b908d5825f27dadb","article_version":2,"title":"Introduction to MimbleWimble and Grin","content":"{\"markdown\":\"This article is originally part of the [grin documentation](https://github.com/mimblewimble/grin/blob/master/doc/intro.md)\\n\\nYou can learn how to [get started with grin here](https://github.com/mimblewimble/docs/wiki/Getting-Started-With-Grin%3A-Links-and-Resources)\\n\\n*Read this in other languages:, [简体中文](https://raw.githubusercontent.com/mimblewimble/grin/master/doc/intro_ZH-CN.md), [Español](https://raw.githubusercontent.com/mimblewimble/grin/master/doc/intro_ES.md), [Nederlands](https://raw.githubusercontent.com/mimblewimble/grin/master/doc/intro_NL.md), [Русский](https://raw.githubusercontent.com/mimblewimble/grin/master/doc/intro_RU.md), [日本語](https://raw.githubusercontent.com/mimblewimble/grin/master/doc/intro_JP.md), [Deutsch](https://raw.githubusercontent.com/mimblewimble/grin/master/doc/intro_DE.md), [Portuguese](https://raw.githubusercontent.com/mimblewimble/grin/master/doc/intro_PT-BR.md), [Korean](https://raw.githubusercontent.com/mimblewimble/grin/master/doc/intro_KR.md).*\\n\\n>MimbleWimble is a blockchain format and protocol that provides\\nextremely good scalability, privacy and fungibility by relying on strong\\ncryptographic primitives. It addresses gaps existing in almost all current\\nblockchain implementations.\\n\\nGrin is an open source software project that implements a MimbleWimble\\nblockchain and fills the gaps required for a full blockchain and\\ncryptocurrency deployment.\\n\\nThe main goal and characteristics of the Grin project are:\\n\\n* Privacy by default. This enables complete fungibility without precluding\\n the ability to selectively disclose information as needed.\\n* Scales mostly with the number of users and minimally with the number of\\n transactions (<100 byte `kernel`), resulting in a large space saving compared\\n to other blockchains.\\n* Strong and proven cryptography. MimbleWimble only relies on Elliptic Curve\\n Cryptography which has been tried and tested for decades.\\n* Design simplicity that makes it easy to audit and maintain over time.\\n* Community driven, encouraging mining decentralization.\\n\\nA detailed post on the step-by-step of how Grin transactions work (with graphics) can be found [in this Medium post](https://medium.com/@brandonarvanaghi/grin-transactions-explained-step-by-step-fdceb905a853). \\n\\n## Tongue Tying for Everyone\\n\\nThis document is targeted at readers with a good\\nunderstanding of blockchains and basic cryptography. With that in mind, we attempt\\nto explain the technical buildup of MimbleWimble and how it's applied in Grin. We hope\\nthis document is understandable to most technically-minded readers. Our objective is\\nto encourage you to get interested in Grin and contribute in any way possible.\\n\\nTo achieve this objective, we will introduce the main concepts required for a good\\nunderstanding of Grin as a MimbleWimble implementation. We will start with a brief\\ndescription of some relevant properties of Elliptic Curve Cryptography (ECC) to lay the\\nfoundation on which Grin is based and then describe all the key elements of a\\nMimbleWimble blockchain's transactions and blocks.\\n\\n### Tiny Bits of Elliptic Curves\\n\\nWe start with a brief primer on Elliptic Curve Cryptography, reviewing just the\\nproperties necessary to understand how MimbleWimble works and without\\ndelving too much into the intricacies of ECC. For readers who would want to\\ndive deeper into those assumptions, there are other opportunities to\\n[learn more](http://andrea.corbellini.name/2015/05/17/elliptic-curve-cryptography-a-gentle-introduction/).\\n\\nAn Elliptic Curve for the purpose of cryptography is simply a large set of points that\\nwe will call _C_. These points can be added, subtracted, or multiplied by integers (also called scalars).\\nGiven an integer _k_ and\\nusing the scalar multiplication operation we can compute `k*H`, which is also a point on\\ncurve _C_. Given another integer _j_ we can also calculate `(k+j)*H`, which equals\\n`k*H + j*H`. The addition and scalar multiplication operations on an elliptic curve\\nmaintain the commutative and associative properties of addition and multiplication:\\n\\n (k+j)*H = k*H + j*H\\n\\nIn ECC, if we pick a very large number _k_ as a private key, `k*H` is\\nconsidered the corresponding public key. Even if one knows the\\nvalue of the public key `k*H`, deducing _k_ is close to impossible (or said\\ndifferently, while multiplication is trivial, \\\"division\\\" by curve points is\\nextremely difficult).\\n\\nThe previous formula `(k+j)*H = k*H + j*H`, with _k_ and _j_ both private\\nkeys, demonstrates that a public key obtained from the addition of two private\\nkeys (`(k+j)*H`) is identical to the addition of the public keys for each of those\\ntwo private keys (`k*H + j*H`). In the Bitcoin blockchain, Hierarchical\\nDeterministic wallets heavily rely on this principle. MimbleWimble and the Grin\\nimplementation do as well.\\n\\n### Transacting with MimbleWimble\\n\\nThe structure of transactions demonstrates a crucial tenet of MimbleWimble:\\nstrong privacy and confidentiality guarantees.\\n\\nThe validation of MimbleWimble transactions relies on two basic properties:\\n\\n* **Verification of zero sums.** The sum of outputs minus inputs always equals zero,\\n proving that the transaction did not create new funds, _without revealing the actual amounts_.\\n* **Possession of private keys.** Like with most other cryptocurrencies, ownership of\\n transaction outputs is guaranteed by the possession of ECC private keys. However,\\n the proof that an entity owns those private keys is not achieved by directly signing\\n the transaction.\\n\\nThe next sections on balance, ownership, change and proofs details how those two\\nfundamental properties are achieved.\\n\\n#### Balance\\n\\nBuilding upon the properties of ECC we described above, one can obscure the values\\nin a transaction.\\n\\nIf _v_ is the value of a transaction input or output and _H_ a point on the elliptic curve _C_, we can simply \\nembed `v*H` instead of _v_ in a transaction. This works because using the ECC\\noperations, we can still validate that the sum of the outputs of a transaction equals the\\nsum of inputs:\\n\\n v1 + v2 = v3 => v1*H + v2*H = v3*H\\n\\nVerifying this property on every transaction allows the protocol to verify that a\\ntransaction doesn't create money out of thin air, without knowing what the actual\\nvalues are. However, there are a finite number of usable values (transaction amounts) and one \\ncould try every single \\none of them to guess the value of your transaction. In addition, knowing v1 (from\\na previous transaction for example) and the resulting `v1*H` reveals all outputs with\\nvalue v1 across the blockchain. For these reasons, we introduce a second point _G_ on the same elliptic curve\\n(practically _G_ is just another generator point on the same curve group as _H_) and\\na private key _r_ used as a *blinding factor*.\\n\\nAn input or output value in a transaction can then be expressed as:\\n\\n r*G + v*H\\n\\nWhere:\\n\\n* _r_ is a private key used as a blinding factor, _G_ is a point on the elliptic curve _C_ and\\n their product `r*G` is the public key for _r_ (using _G_ as generator point).\\n* _v_ is the value of an input or output and _H_ is another point on the elliptic curve _C_,\\n together producing another public key `v*H` (using _H_ as generator point).\\n\\nNeither _v_ nor _r_ can be deduced, leveraging the fundamental properties of Elliptic\\nCurve Cryptography. `r*G + v*H` is called a _Pedersen Commitment_.\\n\\nAs an example, let's assume we want to build a transaction with two inputs and one\\noutput. We have (ignoring fees):\\n\\n* `vi1` and `vi2` as input values.\\n* `vo3` as output value.\\n\\nSuch that:\\n\\n vi1 + vi2 = vo3\\n\\nGenerating a private key as a blinding factor for each input value and replacing each value\\nwith their respective Pedersen Commitments in the previous equation, we obtain:\\n\\n (ri1*G + vi1*H) + (ri2*G + vi2*H) = (ro3*G + vo3*H)\\n\\nWhich as a consequence requires that:\\n\\n ri1 + ri2 = ro3\\n\\nThis is the first pillar of MimbleWimble: the arithmetic required to validate a\\ntransaction can be done without knowing any of the values.\\n\\nAs a final note, this idea is actually derived from Greg Maxwell's\\n[Confidential Transactions](https://elementsproject.org/features/confidential-transactions/investigation),\\nwhich is itself derived from an \\n[Adam Back proposal for homomorphic values](https://bitcointalk.org/index.php?topic=305791.0) \\napplied to Bitcoin.\\n\\n#### Ownership\\n\\nIn the previous section we introduced a private key as a blinding factor to obscure the\\ntransaction's values. The second insight of MimbleWimble is that this private\\nkey can be leveraged to prove ownership of the value.\\n\\nAlice sends you 3 coins and to obscure that amount, you chose 28 as your\\nblinding factor (note that in practice, the blinding factor being a private key, it's an\\nextremely large number). Somewhere on the blockchain, the following output appears and\\nshould only be spendable by you:\\n\\n X = 28*G + 3*H\\n\\n_X_, the result of the addition, is visible by everyone. The value 3 is only known to you and Alice,\\nand 28 is only known to you.\\n\\nTo transfer those 3 coins again, the protocol requires 28 to be known somehow.\\nTo demonstrate how this works, let's say you want to transfer those 3 same coins to Carol.\\nYou need to build a simple transaction such that:\\n\\n Xi => Y\\n\\nWhere _Xi_ is an input that spends your _X_ output and _Y_ is Carol's output. There is no way to build\\nsuch a transaction and balance it without knowing your private key of 28. Indeed, if Carol\\nis to balance this transaction, she needs to know both the value sent and your private key\\nso that:\\n\\n Y - Xi = (28*G + 3*H) - (28*G + 3*H) = 0*G + 0*H\\n\\nBy checking that everything has been zeroed out, we can again make sure that\\nno new money has been created.\\n\\nWait! Stop! Now you know the private key in Carol's output (which, in this case, must\\nbe the same as yours to balance out) and so you could\\nsteal the money back from Carol!\\n\\nTo solve this, Carol uses a private key of her choosing.\\nShe picks 113 say, and what ends up on the blockchain is:\\n\\n Y - Xi = (113*G + 3*H) - (28*G + 3*H) = 85*G + 0*H\\n\\nNow the transaction no longer sums to zero and we have an _excess value_ on _G_\\n(85), which is the result of the summation of all blinding factors. But because `85*G` is\\na valid public key on the elliptic curve _G_, with private key 85,\\nfor any x and y, only if `y = 0` is `x*G + y*H` a valid public key on the elliptic curve \\nusing generator point _G_.\\n\\nSo all the protocol needs to verify is that (`Y - Xi`) is a valid public key on the curve \\nand that the transacting parties collectively know the private key `x` (85 in our transaction with\\nCarol) of this public key. If they can prove that they know the private key to `x*G + y*H` using\\ngenerator point _G_ then this proves that `y` must be `0` (meaning above that the sum of all \\ninputs and outputs equals `0`).\\n\\nThe simplest way to do so is to require a signature built with the excess value (85),\\nwhich then validates that:\\n\\n* The transacting parties collectively know the private key (the excess value 85), and\\n* The sum of the transaction outputs, minus the inputs, sum to a zero value\\n (because only a valid public key, matching the private key, will check against\\n the signature).\\n\\nThis signature, attached to every transaction, together with some additional data (like mining\\nfees), is called a _transaction kernel_ and is checked by all validators.\\n\\n#### Some Finer Points\\n\\nThis section elaborates on the building of transactions by discussing how change is\\nintroduced and the requirement for range proofs so all values are proven to be\\nnon-negative. Neither of these are absolutely required to understand MimbleWimble and\\nGrin, so if you're in a hurry, feel free to jump straight to\\n[Putting It All Together](#putting-it-all-together).\\n\\n##### Change\\n\\nLet's say you only want to send 2 coins to Carol from the 3 you received from\\nAlice. To do this you would send the remaining 1 coin back to yourself as change.\\nYou generate another private key (say 12) as a blinding factor to\\nprotect your change output. Carol uses her own private key as before.\\n\\n Change output: 12*G + 1*H\\n Carol's output: 113*G + 2*H\\n\\nWhat ends up on the blockchain is something very similar to before.\\nAnd the signature is again built with the excess value, 97 in this example.\\n\\n (12*G + 1*H) + (113*G + 2*H) - (28*G + 3*H) = 97*G + 0*H\\n\\n##### Range Proofs\\n\\nIn all the above calculations, we rely on the transaction values to always be positive. The\\nintroduction of negative amounts would be extremely problematic as one could\\ncreate new funds in every transaction.\\n\\nFor example, one could create a transaction with an input of 2 and outputs of 5\\nand -3 and still obtain a well-balanced transaction, following the definition in\\nthe previous sections. This can't be easily detected because even if _x_ is\\nnegative, the corresponding point `x*H` on the curve looks like any other.\\n\\nTo solve this problem, MimbleWimble leverages another cryptographic concept (also\\ncoming from Confidential Transactions) called\\nrange proofs: a proof that a number falls within a given range, without revealing\\nthe number. We won't elaborate on the range proof, but you just need to know\\nthat for any `r*G + v*H` we can build a proof that will show that _v_ is greater than\\nzero and does not overflow.\\n\\nIt's also important to note that in order to create a valid range proof from the example above, both of the values 113 and 28 used in creating and signing for the excess value must be known. The reason for this, as well as a more detailed description of range proofs are further detailed in the [range proof paper](https://eprint.iacr.org/2017/1066.pdf).\\nThe requirement to know both values to generate valid rangeproofs is an important feature since it prevents a censoring attack where a third party could lock up UTXOs without knowing their private key by creating a transaction from\\n\\n Carol's UTXO: 113*G + 2*H\\n Attacker's output: (113 + 99)*G + 2*H\\n \\nwhich can be signed by the attacker since Carols private key of 113 cancels due to the adverserial choice of keys. The new output could only be spent by both the attacker and Carol together. However, while the attacker can provide a valid signature for the transaction, it is impossible to create a valid rangeproof for the new output invalidating this attack. \\n\\n\\n#### Putting It All Together\\n\\nA MimbleWimble transaction includes the following:\\n\\n* A set of inputs, that reference and spend a set of previous outputs.\\n* A set of new outputs that include:\\n * A value and a blinding factor (which is just a new private key) multiplied on\\n a curve and summed to be `r*G + v*H`.\\n * A range proof that shows that v is non-negative.\\n* An explicit transaction fee, in clear.\\n* A signature, computed by taking the excess blinding value (the sum of all\\n outputs plus the fee, minus the inputs) and using it as a private key.\\n\\n### Blocks and Chain State\\n\\nWe've explained above how MimbleWimble transactions can provide\\nstrong anonymity guarantees while maintaining the properties required for a valid\\nblockchain, i.e., a transaction does not create money and proof of ownership\\nis established through private keys.\\n\\nThe MimbleWimble block format builds on this by introducing one additional\\nconcept: _cut-through_. With this addition, a MimbleWimble chain gains:\\n\\n* Extremely good scalability, as the great majority of transaction data can be\\n eliminated over time, without compromising security.\\n* Further anonymity by mixing and removing transaction data.\\n* And the ability for new nodes to sync up with the rest of the network very\\n efficiently.\\n\\n#### Transaction Aggregation\\n\\nRecall that a transaction consists of the following -\\n\\n* a set of inputs that reference and spent a set of previous outputs\\n* a set of new outputs (Pedersen commitments)\\n* a transaction kernel, consisting of\\n * kernel excess (Pedersen commitment to zero)\\n * transaction signature (using kernel excess as public key)\\n\\nA tx is signed and the signature included in a _transaction kernel_. The signature is generated using the _kernel excess_ as a public key proving that the transaction sums to 0.\\n\\n (42*G + 1*H) + (99*G + 2*H) - (113*G + 3*H) = 28*G + 0*H\\n\\nThe public key in this example being `28*G`.\\n\\nWe can say the following is true for any valid transaction (ignoring fees for simplicity) -\\n\\n sum(outputs) - sum(inputs) = kernel_excess\\n\\nThe same holds true for blocks themselves once we realize a block is simply a set of aggregated inputs, outputs and transaction kernels. We can sum the tx outputs, subtract the sum of the tx inputs and compare the resulting Pedersen commitment to the sum of the kernel excesses -\\n\\n sum(outputs) - sum(inputs) = sum(kernel_excess)\\n\\nSimplifying slightly, (again ignoring transaction fees) we can say that MimbleWimble blocks can be treated exactly as MimbleWimble transactions.\\n\\n##### Kernel Offsets\\n\\nThere is a subtle problem with MimbleWimble blocks and transactions as described above. It is possible (and in some cases trivial) to reconstruct the constituent transactions in a block. This is clearly bad for privacy. This is the \\\"subset\\\" problem - given a set of inputs, outputs and transaction kernels a subset of these will recombine to reconstruct a valid transaction.\\n\\nFor example, given the following two transactions -\\n\\n (in1, in2) -> (out1), (kern1)\\n (in3) -> (out2), (kern2)\\n\\nWe can aggregate them into the following block (or aggregate transaction) -\\n\\n (in1, in2, in3) -> (out1, out2), (kern1, kern2)\\n\\nIt is trivially easy to try all possible permutations to recover one of the transactions (where it sums successfully to zero) -\\n\\n (in1, in2) -> (out1), (kern1)\\n\\nWe also know that everything remaining can be used to reconstruct the other valid transaction -\\n\\n (in3) -> (out2), (kern2)\\n\\nTo mitigate this we include a _kernel offset_ with every transaction kernel. This is a blinding factor (private key) that needs to be added back to the kernel excess to verify the commitments sum to zero -\\n\\n sum(outputs) - sum(inputs) = kernel_excess + kernel_offset\\n\\nWhen we aggregate transactions in a block we store a _single_ aggregate offset in the block header. And now we have a single offset that cannot be decomposed into the individual transaction kernel offsets and the transactions can no longer be reconstructed -\\n\\n sum(outputs) - sum(inputs) = sum(kernel_excess) + kernel_offset\\n\\nWe \\\"split\\\" the key `k` into `k1+k2` during transaction construction. For a transaction kernel `(k1+k2)*G` we publish `k1*G` (the excess) and `k2` (the offset) and sign the transaction with `k1*G` as before.\\nDuring block construction we can simply sum the `k2` offsets to generate a single aggregate `k2` offset to cover all transactions in the block. The `k2` offset for any individual transaction is unrecoverable.\\n\\n#### Cut-through\\n\\nBlocks let miners assemble multiple transactions into a single set that's added\\nto the chain. In the following block representations, containing 3 transactions,\\nwe only show inputs and\\noutputs of transactions. Inputs reference outputs they spend. An output included\\nin a previous block is marked with a lower-case x.\\n\\n I1(x1) --- O1\\n |- O2\\n\\n I2(x2) --- O3\\n I3(O2) -|\\n\\n I4(O3) --- O4\\n |- O5\\n\\nWe notice the two following properties:\\n\\n* Within this block, some outputs are directly spent by included inputs (I3\\n spends O2 and I4 spends O3).\\n* The structure of each transaction does not actually matter. As all transactions\\n individually sum to zero, the sum of all transaction inputs and outputs must be zero.\\n\\nSimilarly to a transaction, all that needs to be checked in a block is that ownership\\nhas been proven (which comes from _transaction kernels_) and that the whole block did\\nnot add any money supply (other than what's allowed by the coinbase).\\nTherefore, matching inputs and outputs can be eliminated, as their contribution to the overall\\nsum cancels out. Which leads to the following, much more compact block:\\n\\n I1(x1) | O1\\n I2(x2) | O4\\n | O5\\n\\nNote that all transaction structure has been eliminated and the order of inputs and\\noutputs does not matter anymore. However, the sum of all outputs in this block,\\nminus the inputs, is still guaranteed to be zero.\\n\\nA block is simply built from:\\n\\n* A block header.\\n* The list of inputs remaining after cut-through.\\n* The list of outputs remaining after cut-through.\\n* A single kernel offset to cover the full block.\\n* The transaction kernels containing, for each transaction:\\n * The public key `r*G` obtained from the summation of all the commitments.\\n * The signatures generated using the excess value.\\n * The mining fee.\\n\\nWhen structured this way, a MimbleWimble block offers extremely good privacy\\nguarantees:\\n\\n* Intermediate (cut-through) transactions will be represented only by their transaction kernels.\\n* All outputs look the same: just very large numbers that are impossible to\\n differentiate from one another. If one wanted to exclude some outputs, they'd have\\n to exclude all.\\n* All transaction structure has been removed, making it impossible to tell which output\\n was matched with each input.\\n\\nAnd yet, it all still validates!\\n\\n#### Cut-through All The Way\\n\\nGoing back to the previous example block, outputs x1 and x2, spent by I1 and\\nI2, must have appeared previously in the blockchain. So after the addition of\\nthis block, those outputs as well as I1 and I2 can also be removed from the\\noverall chain, as they do not contribute to the overall sum.\\n\\nGeneralizing, we conclude that the chain state (excluding headers) at any point\\nin time can be summarized by just these pieces of information:\\n\\n1. The total amount of coins created by mining in the chain.\\n2. The complete set of unspent outputs.\\n3. The transactions kernels for each transaction.\\n\\nThe first piece of information can be deduced just using the block\\nheight (its distance from the genesis block). And both the unspent outputs and the\\ntransaction kernels are extremely compact. This has 2 important consequences:\\n\\n* The state a given node in a MimbleWimble blockchain needs to maintain is very\\n small (on the order of a few gigabytes for a bitcoin-sized blockchain, and\\n potentially optimizable to a few hundreds of megabytes).\\n* When a new node joins a network building up a MimbleWimble chain, the amount of\\n information that needs to be transferred is also very small.\\n\\nIn addition, the complete set of unspent outputs cannot be tampered with, even\\nonly by adding or removing an output. Doing so would cause the summation of all\\nblinding factors in the transaction kernels to differ from the summation of blinding\\nfactors in the outputs.\\n\\n### Conclusion\\n\\nIn this document we covered the basic principles that underlie a MimbleWimble\\nblockchain. By using the addition properties of Elliptic Curve Cryptography, we're\\nable to build transactions that are completely opaque but can still be properly\\nvalidated. And by generalizing those properties to blocks, we can eliminate a large\\namount of blockchain data, allowing for great scaling and fast sync of new peers.\"}","author":"37648fc15a8365735289e002d65d44d80c505e8b","timestamp":1556034079921,"attributes":{"background":"https://api.kauri.io:443/ipfs/QmPY2duvgnnWPimVvpzdEbRKydCkLhmnbZ6ZnPLJaUCXgP"}}