Mimblewimble in IoT
Implementing privacy and anonymity in INT Transactions
The years of 2017 and ’18 were years focused on the topic of scaling. Coins forked and projects were hyped with this word as their sole mantra. What this debate brought us were solutions and showed us where we are right now satisfying the current need when paired with a plan for the future. What will be the focus of years to come will be anonymity and fungibility in mass adoption.
In the quickly evolving world of connected data, privacy is becoming a topic of immediate importance. As it stands, we trust our privacy to centralized corporations where safety is ensured by the strength of your passwords and how much effort an attacker dedicates to breaking them. As we grow into the new age of the Internet, where all things are connected, trustless and cryptographic privacy must be at the base of all that it rests upon. In this future, what is at risk is not just photographs and credit card numbers, it is everything you interact with and the data it collects.
If the goal is to do this in a decentralized and trustless network, the challenge will be finding solutions that have a range of applicability that equal the diversity of the ecosystem with the ability to match the scales predicted. Understanding this, INT has begun research into implementing two different privacy protocols into their network that conquer two of the major necessities of IoT: scalable private transactions and private smart contracts.
One of the privacy protocols INT is looking into is Mimblewimble. Mimblewimble is a fairly new and novel implementation of the same elements of Elliptic-Curve Cryptography that serves as the basis of most cryptocurrencies.
In bitcoin-wizards IRC channel in August 2016, an anonymous user posted a Tor link to a whitepaper claiming “an idea for improving privacy in bitcoin.” What followed was a blockchain proposal that uses a transaction construction radically different than anything seen today creating one of the most elegant uses of elliptic curve cryptography seen to date.
While the whitepaper posted was enough to lay out the ideas and reasoning to support the theory, it contained no explicit mathematics or security analysis. Andrew Poelstra, a mathematician and the Director of Research at Blockstream, immediately began analyzing its merits and over the next two months, created a detailed whitepaper [Poel16] outlining the cryptography, fundamental theorems, and protocol involved in creating a standalone blockchain.
What it sets out to do as a protocol is to wholly conceal the values in transactions and eliminate the need for addresses while simultaneously solving the scaling issue.
Let’s say you want to hide the amount that you are sending. One great way to hide information that is well known and quick: hashing! Hashing allows you to deterministically produce a random string of constant length regardless of the size of the input, that is impossible to reverse. We could then hash the amount and send that in the transaction.
X = SHA256(amount)
4A44DC15364204A80FE80E9039455CC1608281820FE2B24F1E5233ADE6AF1DD5 = SHA256(10)
But since hashing is deterministic, all someone would have to do would be to catalog all the hashes for all possible amounts and the whole purpose for doing so in the first place would be nullified. So instead of just hashing the amount, lets first multiply this amount by a private blinding factor. If kept private, there is no way of knowing the amount inside the hash.
X = SHA256(blinding factor * amount)
This is called a commitment, you are committing to a value without revealing it and in a way that it cannot be changed without changing the resultant value of the commitment.
But how then would a node validate a transaction using this commitment scheme? At the very least, we need to prove that you satisfy two conditions; one, you have enough coins, and two, you are not creating coins in the process. The way most protocols validate this is by consuming a previous input transaction (or multiple) and in the process, creating an output that does not exceed the sum of the inputs. If we hash the values and have no way validate this condition, one could create coins out of thin air.
input(commit(bf,10), Alice) -> output(commit(bf,9), BOB), outputchange(commit(bf,5), Alice)Orinput(4A44DC15364204A80FE80E9039455CC1608281820FE2B24F1E5233ADE6AF1DD5, Alice) ->output(19581E27DE7CED00FF1CE50B2047E7A567C76B1CBAEBABE5EF03F7C3017BB5B7, Bob)output(EF2D127DE37B942BAAD06145E54B0C619A1F22327B2EBBCFBEC78F5564AFE39D, Alice)
As shown above, the later hashed values look just as valid as anything else and result in Alice creating 4 coins and receiving them as change in her transaction. In any transaction, the sum of the inputs must equal the sum of the outputs. We need some way of doing mathematics on these hashed values to be able to prove:
commit(bf1,x) = commit(bf2,y1) + commit(bf3,y2)
which, if it is a valid transaction would be:
commit(bf1,x) - commit(bf2+bf3,y1+y2) = commit(bf1-(bf2+bf3),0)
Or just a commit of the leftover blinding factors.
By the virtue of hashing algorithms, this isn’t possible. To verify this we would have to make all blinding factors and amounts public. But in doing so, nothing is private. How then can we make a valued public that is made with a private-value in such a way that you cannot reverse engineer the private value and still validate it satisfies some condition? It sounds a bit like public and private key cryptography…
What we learned in our primer on Elliptic-Curve Cryptography was that by using an elliptic curve to define our number space, we can use a point on the curve, G, and multiply it by any number, x, and what you get is another valid point, P, on the same curve. This calculation is quick but in taking the resultant point and the publically known generator point G, it is practically impossible to figure out what multiplier was used. This way we can use the point P as the public key and the number x as the private key. Interestingly, they also have the curious property of being additive and communicative.
If you take point P which is x • G and add point Q to it which is y • G, its resulting point, W = P + Q, is equal to creating a new point with the combined numbers x+y. So:
This property, homomorphism, allows us to do math with numbers we do not know.
So if instead of using the raw amount and blinding factor in our commit, we use them each multiplied by a known generator point on an elliptic curve. Our commit can now be defined as:
This is called a Pedersen Commitment and serves as the core of all Confidential Transactions.
Let’s call the blinding factors r, and the amounts v, and use H and G as generator points on the same elliptic curve (without going deep into Schnorr signatures, we will just accept that we have to use two different points for the blinding factor and value commits for validation purposes**). Applying this to our previous commitments:
and using the communicative properties:
which for a valid transaction, this would equal:
This resultant difference is just a commit to the excess blinding factor, also called a commitment-to-zero:
You can see that in any case where the blinding factors were selected randomly, the commit-to-zero will be non-zero and in fact, is still a valid point on the elliptic curve with a public key,
And private key being the difference of the blinding factors.
So, if the sum of the inputs minus the sum of the outputs produces a valid public key on the curve, you know that the values have balanced to zero and no coins were created. If the resultant difference is not of the form:
for some excess blinding factor, it would not be a valid public key on the curve, and we would know that it is not a balanced transaction. To prove this, the transaction is then signed with this public key to prove the transaction is balanced and that all blinding factors are known, and in the process, no information about the transaction have been revealed (the by step details of the signature process can be read in [Arvan19]).
All the above work assumed the numbers were positive. One could create just as valid of a balanced transaction with negative numbers, allowing users to create new coins with every transaction. Called Range Proofs, each transaction must be accompanied by a zero-knowledge argument of knowledge to prove that a private committed value lies within a predetermined range of values. Mimblewimble, as well as Monero, use BulletProofs which is a new way of calculating the proof which cuts down the size of the transaction by 80–90%.
Up to this point, the protocol described is more-or-less identical between Mimblewimble and Monero. The point of deviation is how transactions are signed.
In Monero, there are two sets of keys/addresses, the spend keys, and the view keys. The spend key is used to generate and sign transactions, while the view key is used to “receive” transactions. Transactions are signed with what is called a Ring Signature which is derived from the output being spent, proving that one key out of the group of keys possesses the spend key. This is done by creating a combined Schnorr signature with your private key and a mix of decoy signers from the public keys of previous transactions. These decoy signers are all mathematically equally valid which results in an inability to determine which one is the real signer. Being that Monero uses Pedersen Commitments shown above, the addresses are never publically visible but are just used for the claiming, signing of transactions and generating blinding factors.
Mimblewimble, on the other hand, does not use addresses of any type. Yes. That’s right, no addresses. This is the true brilliance of the protocol. What Jedusor proved was that the blinding factors within the Pedersen commit and the commit-to-zero can be used as single-use public/private key pairs to create and sign transactions.
All address based protocols using elliptic-curve cryptography generate public-private key pairs in essentially the same way. By multiplying a very large random number (k_priv) by a point (G) on an elliptic curve, the result (K_pub) is another valid point on the same curve.
This serves as the core of all address generation. Does that look familiar?
Remember this commit from above:
Each blinding factor multiplied by generator point G (in red) is exactly that! r•G is the public key with private key r! So instead of using addresses, we can use these blinding factors as proof we own the inputs and outputs by using these values to build the signature.
This seemingly minor change removes the linkability of addresses and the need for a scriptSig process to check for signature validity, which greatly simplifies the structure and size of Confidential Transactions. Of course, this means (at this time) that the transaction process requires interaction between parties to create signatures.
Even though all addresses and amounts are now hidden, there is still some information that can be gathered from the transactions. In the above transaction format, it is still clear which outputs are consumed and what comes out of the transaction. This “transaction graph” can reveal information about the owners of the blinding factors and build a picture of the user based on seen transaction activity. In order to further hide and condense information, Mimblewimble implements an idea from Greg Maxwell called CoinJoin [Max13] which was originally developed for use in Bitcoin. CoinJoin is a trustless method for combining multiple inputs and outputs from multiple transactions, joining them into a single transaction. What this does is a mask that sender paid which recipient. To accomplish this in Bitcoin, users or wallets must interact to join transactions of like amounts so you cannot distinguish one from the other. If you were able to combine signatures without sharing private keys, you could create a combined signature for many transactions (like ring signatures) and not be bound by needing like amounts.
In Mimblewimble, doing the balance calculation for one transaction or many transactions still works out to a valid commit-to-zero. All we would need to do is to create a combined signature for the combined transaction. Mimblewimble is innately enabled to construct these combined signatures with the commit of Schnorr challenge transaction construction. Using “one-way aggregate signatures” (OWAS), nodes can combine transactions, while creating the block, into a single transaction with one aggregate signature. Using this, Mimblewimble joins all transactions at the block level, effectively creating each block as one big transaction of all inputs consumed and all outputs created. This simultaneously blurs the transaction graph and has the power to remove in-between transactions that were spent during the block, cutting down the total size of blocks and the size of the blockchain.
We can take this one step further. To validate this fully “joined” block, the node would sum all of the output commitments together, then subtract all the input commitments and validate that the result is a valid commit-to-zero. What is stopping us from only joining the transactions within a block? We could theoretically combine two blocks, removing any transactions that are created and spent in those blocks, and the result again is a valid transaction of just unspent commitments and nothing else. We could then do this all the way back to the genesis block, reducing the whole blockchain to just a state of unspent commitments. This is called Cut-through. When doing this, we don’t have any need to retain the range proofs of spent outputs, they have been verified and can be discarded. This lends itself to a massive reduction in blockchain growth, reducing growth from O(number of txs) to O(number of unspent outputs).
To illustrate the impact of this, let’s imagine if Mimblewimble was implemented in the Bitcoin network from the beginning, with the network at block 576,000, the blockchain is about 210 GB with 413,675,000 total transactions and 55,400,000 total unspent outputs. In Mimblewimble, transaction outputs are about 5 kB (including range proof ~5 kB and Pedersen commit ~33 bytes), transaction inputs are about 32 bytes and transaction proof are about 105 bytes (commit-to-zero and signature), block headers are about 250 bytes (Merkle proof and PoW) and non-confidential transactions are negligible. This sums up to a staggering 5.3 TB for a full sync blockchain of all information, with “only” 279 GB of that being the UTXOs. When we cut-through, we don’t want to lose all the history of transactions, so we retain the proofs for all transactions as well as the UTXO set and all block headers. This reduces the blockchain to 322 GB, a 94% reduction in size. The result is basically a total consensus state of only that which has not been spent with a full proof history, greatly reducing the amount of sync time for new nodes.
If Bulletproofs are implemented, the range proof is reduced from over 5kB to less than 1 kB, dropping the UTXO set in the above example from 279 GB to 57 GB.
There is also an interesting implication in PoS blockchains with explicit finality. Once finality has been obtained, or at some arbitrary blockchain depth beyond it, there is no longer the need to retain range proofs. Those transactions have been validated, the consensus state has been built upon it and they make up the vast majority of the blockchain size. If we say in this example that finality happens at 100 blocks deep, and assume that 10% of the UTXO set is pre-finality, this would reduce the blockchain size by another 250 GB, resulting in a full sync weight of 73 GB, a 98.6% reduction (even down 65% from its current state). Imagine this. A 73 GB blockchain for 10 years of fully anonymous Bitcoin transactions, and one third the current blockchain size.
It’s important to note that cut-through has no impact on privacy or security. Each node may choose whether or not to store the entire chain without performing any cut-through with the only cost being increased disk storage requirements. Cut-through is purely a scalability feature resulting in Mimblewimble based blockchains being on average three times smaller than Bitcoin and fifteen times smaller than Monero (even with the recent implementation of Bulletproofs).
What does this mean for INT and IoT?
Transactions within an IoT network require speed, scaling to tremendous volumes, adapting to a variety of uses and devices with the ability to keep sensitive information private. Up till now, IoT networks have focused solely on scaling, creating networks that can transact with tremendous volume with varying degrees of decentralization and no focus on privacy. Without privacy, these networks will just make those who use it targets who feed their attackers the ammunition.
Mimblewimble’s revolutionary use of elliptic-curve cryptography brings us a privacy protocol using Pedersen commitments for fully confidential transactions and in the process, removes the dependence on addresses and private keys in the way we are used to them. This transaction framework combined with Bulletproofs brings lightweight privacy and anonymity on par with Monero, in a blockchain that is 15 times smaller, utilizing full cut-through. This provides the solution to private transactions that fit the scalability requirements of the INT network.
The Mimblewimble protocol has been implemented in two different live networks, Grin and Beam. Both are purely transactional networks, focused on the private and anonymous transfer of value. Grin has taken a Bitcoin-like approach with community-funded development, no pre-mine or founders reward while Beam has the mindset of a startup, with VC funding and a large emphasis on a user-friendly experience.
INT, on the other hand, is researching implementing this protocol either on the main chain, creating all INT asset transfer private or as an optional and add-on subchain, allowing users to transfer their INT from non-private chain to the private chain, or vice versa, at will.
Where it falls short？
What makes this protocol revolutionary is the same thing that limits it. Almost all protocols, like Bitcoin, Ethereum, etc., use a basic scripting language with a function calls out in the actual transaction data that tells the verifier what script to use to validate it. In the simplest case, the data provided with the input calls “scriptSig” and provides two pieces of data, the signature that matches the transaction and the public key that proves you own the private key that created it. The output scripts use this provided data with the logic passed with it, to show the validator how to prove they are allowed to spend it. Using the public key provided, the validator then hashes it, checks that it matches the hashed public key in the output, if it does, it then checks to make sure the signature provided matches the input signature.
This verification protocol allows some limited scripting ability in being able to tell validators what to do with the data provided. The Bitcoin network can be updated with new functions allowing it to adapt to new processes or data. Using this, the Bitcoin protocol can verify multiple signatures, lock transactions for a defined timespan and do more complex things like lock bitcoin in an account until some outside action is taken.
In order to achieve more widely applicable public smart contracts like those in Ethereum, they need to be provided data in a non-shielded way or create shielded proofs that prove you satisfy the smart contract conditions.
In Mimblewimble, as a consequence of using the blinding factors as the key pairs, greatly simplifying the signature verification process, there are no normal scripting opportunities in the base protocol. What is recorded on the blockchain is just:
- Inputs used — which are old commits consumed
- New outputs — which are new commits to publish
- Transaction kernel — which contains the signature for the transaction with excess blinding factor, transaction fee, and lock_height.
And none of these items can be related to one another and contain no useful data to drive action.
There are some proposals for creative solutions to this problem by doing so-called scriptless-scripts†. By utilizing the properties of the Schnorr signatures used, you can achieve multisig transactions and more complex condition-based transactions like atomic cross-chain swaps and maybe even lightning network type state channels. Still, this is not enough complexity to fulfill all the needs of IoT smart contracts.
And on top of it all, implementing cut-through would remove transactions that might be smart contracts or rely on them.
So you can see in this design we can successfully hide values and ownership but only for a single dimensional data point, quantity. Doing anything more complex than transferring ownership of coin is beyond its capabilities. But the proof of ownership and commit-to-zero is really just a specific type of Zero-knowledge (ZK) proof. So, what if, instead of blinding a value we blind a proof?
Part 2 of this series will cover implementing private smart contracts with zkSNARKs.
References and Notes
** In order to prove that v=0 and therefore the commit to zero, in fact, has no Hcomponent without revealing r, we must use Schnorr protocol:
prover generates random integer n, computes and sends point 𝑇←n𝐻
verifier generates and sends random integer 𝑖
prover computes and sends integer 𝑠←𝑖𝑏+n modq, where q is the (public) order of the curve
verifier knowing point r𝐻 computes point 𝑖(r𝐻), then point 𝑖(r𝐻)+𝑇; computes point 𝑠𝐻; and ensures 𝑖(r𝐻)+𝑇=𝑠𝐻.