Anonymizing Commit and Reveal Transactions in Decentralized OracleSolutions

Malicious incentives, laziness and non-responsiveness can easily jeopardize decentralized networks if not addressed appropriately. In this post, we will review those hurdles and how we can solve them.

Designing oracle solutions is challenging and making them sufficiently decentralized is even more so. If the outcome of a smart contract depends on data provided by an oracle, the likelihood of an attacker trying to change the result by tampering with the oracle increases inasmuch as their stake in the contract is greater than the cost of performing such deception. P+Epsilon and Sybil attacks are classic examples on how adversaries may game the system for their own benefit.

Commit-Reveal schemes are often used by voting systems to fight against cheaters. They work in a similar way to how in many electoral systems the voters are required to introduce the ballot of their preference into envelopes that are kept sealed until the voting hours are over. Only later the envelopes are opened and the votes are tallied. Commit-reveal schemes use cryptography instead of sealed envelopes to guarantee secrecy of the vote and prevent the votes that have been already been cast from conditioning the decision of subsequent voters. This is especially important for voting systems in which the voters get some reward from being in consensus with a majority of fellow voters (e.g. Schelling schemes).

In Commit-Reveal schemes, voters must publicly cast an “encrypted” claim (which may simply be the hash of their vote plus a secret nonce) that they cannot withdraw or deny. After they have done so, they can safely reveal the actual vote they encrypted (plus the secret nonce, if used). Due to the deterministic nature of the encryption and the infeasibility to backdate commitments, vote integrity is guaranteed and free-riding is effectively prevented.

In this post we will try to explore specific problems that arise when commit-reveal schemes are coupled with identities (i.e., public keys and IP addresses). In systems like Witnet or other decentralized oracles, successfully following up commits with valid reveals has a huge impact on rewards distribution and, most importantly, on the results of the data requests. If the identity of the committers is publicly known, they may face attacks and reprisal from fellow committers in order to prevent them from publishing their reveals.

Denial of Service Against Fellow Committers

One of the main problems affecting decentralized networks powered by commit-reveal schemes is the malign incentive for any committer to try to perform a Denial of Service attack on other committers. This can be due to:

  1. Profit maximization. If rewards are granted only to the committers whose reveals are aligned with the consensus, a committer might have the incentive to try to force fellow committers out of the game, thus causing the reward to be distributed among a fewer number of players.
  2. Partisan interest. If a high value smart contract depends on the result of a data request, committers with partisan interest in a particular outcome could try to force others out of the game and make their own potentially biased reveals prevail, which would give them unilateral control of the outcome.

Problem no. 1 can be easily solved by refunding the creator of the data request the proportional share of the reward that was intended for every commitment that was not followed by its corresponding reveal
Problem no. 2 is not that trivial. Such malign incentives will always exist and will be feasible as long as the actors participating in the commit stage are easily identifiable.

With decentralized oracle solutions and in particular with Witnet, transactions are signed by their issuer. Those signatures can only be verified if the associated public key is known to the verifier or simply embedded in the transaction. Furthermore, the proofs used in the cryptographic sortition algorithms that distribute eligibility across the identities in the network also depend on public key cryptosystems. If an attacker is able to link public keys to IPs — by repeatedly observing the origin of the transactions signed by the key — then it will be on track to deanonymize the origin of the commitments and perform such attack.

Thus, we notice a clear need to explore ways to prevent attackers from performing targeted DoS attacks against particular identities while preserving the verifiability of the transactions. The solution can indeed come from two different sides. First, we can explore mechanisms that conceal the originating node of the transactions so as to hinder the matching of public keys to IP addresses. Second, we can explore cryptographic schemes that give us the desired anonymity. While this post focuses on the latter, at the end we will give a brief overview of the well known Dandelion, which belongs to the first category of protections and may soon be adopted by Bitcoin.

Cryptographic Schemes To Anonymize Commit-Reveal

We will be discussing Ring Signatures, Time-release protocols and ZKSNARKs.

Ring Signatures

Ring Signatures are utilized by Monero to provide anonymity on transactions. The basic idea is that while a transaction is signed by a single public key, the signature is obfuscated with a ring of public keys among which an external observer can not tell who the true signer was. The public key ring needs to contain the public key of the true signer, but it also contains several unrelated public keys without any need of interaction from their owners. I will try to explain the basics in this post, but for more information you can check Alonso et.al. and Bender et.al.

First, we need to assume the usage of an Elliptic Curve and that each node contains a public-private key pair under such elliptic curve. As a quick reminder, private keys are just scalars, while public keys are the multiplication of those scalars with the curve generation point. You can get a basic notion of Elliptic Curves on my previous post, which also assumes the existence of two functions Hp and Hn that are able to map octets to a point in the elliptic curve and elliptic curve points to octets respectively.

Ring Signature Generation and Verification

I will use the algorithm described in the figure, but believe me, is not that complicated when you make sense of it. Essentially, our inputs are a private key (k_π, being π the index of the corresponding public key in the ring), a public key ring R and a message m (and of course, the EC parameters). This is how the signature generation looks like:

  • Line number 1 of the signature generation just takes the ring of public keys R to a point in the curve and multiplies it by the signer’s secret key.
  • Line number 2 generates random numbers for all the public keys in the ring (r_i for all indices except π, α for π)
  • Line number 3 takes a set of points/integers and hashes them to an integer cπ+1. This could be considered as the partial signature for index π+1. This is where our ring starts, as we will generate partial signatures for every index, and each one will depend on the previous one.
  • Line number 4 generates values for the rest of the indices in a loop. Note the hash at index π+2 depends on the hash at index π+1, etc.
  • Line number 5 defines the random integer at index π= α-c_π*k_π .
  • The complete signature is composed by the point generated in line number 1, and the pairs (c_i, r_i) for every index in the public key ring.

One might ask now why would this prove that the signature was generated with a secret key corresponding to one of the public keys in the ring. If we observe line 7 in the verification process, we see that we calculate the same Hn as in line numbers 3 and 4 except for the last two items. More than that, if we exclude index π (the index of the signers public key), we see that z_i’ and z_i’’ are defined exactly as in line 4. Therefore, we expect that line number 8 is correct at least for every index that is not π.

But what happens at index π? Lets guess it out:

  • r_π *G + c_π *PK_π = (α-c_π*k_π)G + c_π *PK_π = αG
  • r_π*Hp(R) +c_π*K = (α-c_π*k_π)Hp(R)+c_π*k_π*Hp(R) =αHp(R)

Which is essentially, how we defined our c_π in line 3. Therefore we prove that we know one of the private keys associated to one of the public keys in the ring (the one generating the originating c_π), and that we signed the correct message. The verifier, under ECC security assumptions can not guess the private key used from any of the values sent.

Ring signatures work on the basis that the signature for each public key in the ring depends on the value the previous signature.

Thus, ring signatures might hide our public key under a set of public keys. That means, in the context of commit-reveal schemes, that the attacker would have to DoS every public key included in the rings of the committers. And he has to do this before each of them reveals, reducing his capabilities substantially (in Witnet for instance, she would have to do this in at most 180 seconds). Of course this comes at a cost of higher signature sizes, but hey, security never comes for free.

One of the things I have defended in previous posts is the necessity to use VRFs for signatures, while we talked about signatures in this post. For those worried, there exist frameworks based on VRFs that you can check out in Franklin et.al.

Time-release protocol

One of the problems of commit-reveal schemes is the fact that a reveal stage is needed to retrieve the voted value. Intuitively, if everybody was able to see the decrypt the committed value after a time t, then the reveal stage would not be needed. This is what time-release protocols do. More specifically, they have the following assumptions:

  • The message is encrypted before time t, this is, no one can decrypt the message before time t.
  • Decrypted message after time t, this is, the decrypted message is available for everybody after time t.
  • Non-interactive, i.e., the encryptor does not need to interact with the network to decrypt the message.
  • Not resource intensive, the message can be decrypted without utilizing intensive resources.

If there existed a protocol able to accomplish the aforementioned goals, then we could use it in commit-reveal protocols to defeat targeted DoS attacks. In Liu et. al. they propose such a mechanism based on the Bitcoin network and assumptions, but we can adapt it to Witnet or other blockchains easily. In the following we describe the most important pieces of the proposed protocol.

The time-release protocol proposed in Liu et. al. bases its theory in 3 different pieces: CNF-SAT NP-complete problems, multilinear maps and witness encryption.

  • CNF-SAT NP-complete problems: NP problems are decision problems verifiable in polynomial time. NP-complete problems are those problems to which any other NP problem can be reduced. CNF-SAT (conjunctive normal form boolean satisfiability problem) is indeed a NP-complete problem. Therefore, any problem in NP can be reduced to a CNF-SAT problem that can be verified in polynomial time.
  • Multilinear maps: Cryptographic multilinear maps are maps applied to group families (g1,g2..,gn) of the same order that satisfy e(g1^α, g2^β) = g3^(α*β). Applying the multilinear map to the group family generators will give us a generator gt = e(g1,g2,..,gn) that takes part on the encryption process.
  • Witness Encryption: The concept of witness encryption is built upon CNF-SAT and Multilinear maps. Consider we have a NP-complete problem that we can reduce to CNF-SAT problem. The problem will be formed by a set of literals (variables in the equation) and a set of clauses (e.g. (v1 ∧ v2)⊕(v2∧v3)). The solution to the CNF-SAT problem is called a witness w. It turns out one can build an encryption protocol based on the fact that one has a valid witness. This is, only those having a valid witness will be able to decrypt the message. The encryption process starts by using the generator gt to encode a set of secret random variables that are generated depending on the number of literals and clauses. This encoding is then used as a key to encrypt the input. However, apart from the ciphertext, additional information is shared with the decryptor, mainly vectors that include a subset of generators from the family group powered to a subset of the secret random values generated. They key fact is that, if the decryptor knows a valid witness, she can apply the magic of multilinear maps to these auxiliary vectors and the witness to get to the key that decrypts the ciphertext. I will not extend on the math that validates this, as the reader can always take a look at Liu et. al.. The key idea of the witness encryption is that, unless you find a valid witness, the message will remain encrypted.
Witness encryption provides encrypted messages until a valid solution is found for a CNF-SAT problem

The remaining question thus is, how do we get to do build a time-release protocol with these ingredients? Well, lets imagine for instance, the Bitcoin network, whose consensus is decided based on the very well known Proof of Work (PoW). We know that the difficulty of the PoW puzzle is adjusted so that a bitcoin block is generated roughly every 10 minutes, which already gives us a notion of time. Basically, if we want a message to remain encrypted for 60 minutes, all we have to do is translate the problem of solving 6 consecutive PoW puzzles to a CNF-SAT problem, whose witness is precisely the 6 consecutive nonce||hashes. An individual (or group of individuals) might be able to solve the puzzles, but definitely the network will be able to solve them sooner. In a way, the resources of the network are utilized in favor of the protocol. After roughly 60 minutes, the message is publicly decryptable.

Program converted to CNF-SAT for k*10 minutes delay in Bitcoin (taken from [6])

With respect to a potential application to Witnet (or ultimately other blockchain protocols) the idea would be very similar. In the end to become eligible for mining, one needs to proove that the signature of a message falls below a given target. Therefore, it is very unlikely that an individual (or set of individuals) obtain sufficient valid eligibility proofs before the entire network does. The immediate application would be to get rid of the reveal process (as everybody would be able to decrypt after time t), thus eliminating the possibility for a targeted DoS attack. Unfortunately, multilinear maps are still quite impractical and the amount of time for encryption and decryption are high enough not to consider it a practical possibility nowadays. However, I believe this solution will have significant impact in the future, once our computational power is high enough to fulfill the requirements.

ZKSNARKs

ZKSNARKs (Zero-Knowledge Succint Non-Interactive Argument of Knowledge) are cryptographic protocols thanks to which a verifier can verify a prover is in possession of a secret without:

  • Requiring big interactions with the prover (just a proof from the prover is sent)
  • Revealing anything from the secret the prover knows
  • Requiring large size messages

The construction of ZKSNARKs is also based on complexity theory and multilinear maps. We will skip in this section both the explanation for NP-complete problems and multilinear maps. It is worth mentioning though ZKSNARKs dont use the CNF-SAT NP-complete problem, but rather they use Quadratic Span Programs (QSPs), which we will later explain. ZKSNARKS are used by Zcash to provide blinded transactions that yet are verifiable.

Essentially ZKSNARKs are based on a proof generation process P and a proof verification process V. The prover, knowing a witness (i.e., a solution for a problem reduced to QSP) for a particular input x computes proof = P(w, x). The proof does not reveal anything from the witness. The verifier, upon reception of the proof computes V(proof, x) which will yield a true/false answer, depending on whether the proof was valid.

Quatratic Span Programs are NP-complete problems consisting of:

  • A field F (with a generator g) and inputs of length n
  • polynomials v0,…,vm,w0,…,wm
  • a target polynomial t
  • an injective function f mapping {(i,j) where 0<i<n and j ϵ{0,1}} to {1,…m}

The goal of such construction is to find a linear combination of the polynomials v0,..vm,w0,…wm that divides the target polynomial t. Logically, the input x restricts some of the linear combination factors that can be used. The coefficients of the solution to the linear combination are the so called witness (yes, as in CNF-SAT) and will be noted as the tuple a=(a1,…am) and b=(b1,…,bm). The verification process can be facilitated by the prover providing a polynomial h such that t*h = v_a*w_b. However, checking an entire polynomial is costly and thus, in ZKSNARKs, usually only a secret random point is verified.

This is indeed what Zcash calls toxic waste: the protocol generates two secret numbers s and α and publishes:

  • g^s⁰, g^s¹….,g^(s^d)
  • g^ α*s⁰,.. g^ α*s¹…., g^( α*s^d)

Note that we can “encryptely” evaluate any polynomial of degree at most d with those values, i.e., we can calculate g^h(s) if the degree of h is lower than d. Further note that, thanks to multilinear maps we can verify that e(g^h(s), g^ α) = e(g^(α*h(s)), g). The Zero Knowledge property thus can already be verified, since the prover can send g^(τ+h(s)) and g^α(τ+h(s)) and the equality still holds, while the prover did not reveal anything not even from g^h(s).

However, since there are other fixed polynomials (t, v0,v1..,vm, w0,w1..,wm) identifying the QSP problem, the protocol has to also provide those evaluated at s and encrypted, mainly:

  • g^(t(s)), g^(α*t(s))
  • g^(v0(s)), g^(v1(s))…,g^(vm(s)), g^(α*v0(s)), g^(α*v1(s))…,g^(α*vm(s))
  • g^(w0(s)), g^(w1(s))…,g^(wm(s)), g^(α*w0(s)), g^(α*w1(s))…,g^(α*wm(s))

There are other published secret numbers also published as toxic waste that are further needed to ensure that we are evaluating the correct polynomial. The toxic waste defines the QSP problem that needs to be solved. Now, the solution is to find a valid witness for it, and transmit it in an encrypted way. Basically the prover transmits v’ and w’ and h’ referring to the linear combination (with the witness coefficients) of v, w and to the polynomial that the target polynomial divides to (h’). All this is sent in an encrypted way (i.e., g^x and g^α*x), to ensure the prover evaluated the correct point. The verifier can verify that the provided values indeed match thanks to the properties of multilinear maps, i.e., that the encrypted evaluations provided of w’ and v’ indeed divide the encrypted evaluations of h and t. I am not going to extend more, as one can check the mathematical proof by Reitwießner.

The important idea from ZKSNARKs is that, given a reduction to a QSP problem, one can proof having knowledge of the witness (coefficients a and b) that solves it without having to reveal it and in a reasonable time (as we are only evaluating the polynomials at a single point). As an application to our commit-reveal problem, the verification of the signature of the commitment transaction can be done without revealing the identity (or the public key corresponding to the signing key). This would anonymize commit transactions, and therefore, discourage DoS attacks. However, current implementations of ZKSNARKs would limit the amount of commitments (and therefore, data request resolutions) a node can do per epoch. Current implementations still take 7 seconds to generate a proof, an amount of time that is impractical for Witnet, where nodes need to resolve data requests rapidly. Thus, while ZKSNARKS might be a good solution for other approaches, they do not seem applicable to Witnet currently.

P2P protocol To Anonymize Commit-Reveal

So far we have seen cryptographic schemes that might be able to anonymize (at different costs) the identity of the committer in a commit-reveal transaction. However, there is another way in which we can anonymize the identity of a committer: a DoS can not be performed against a public key if the attacker can not link it to the corresponding IP. Thus, if we obfuscate the relation between IP and public key, an attacker might not know who is behind a public key.

In bitcoin (and in Witnet) transactions are first transmitted to the transmitter node’s peers, and subsequently, its propagated through the network. For this reason, a highly connected attacker could be able to perform an IP-public key matching by checking the times at which they receive transactions from their peers. While privacy has generated a high amount of discussion in the crypto community, we have a very specific intention here: hide the identity of the committer to preserve the integrity of the data request.

Solving the IP-public key mapping has been one of the major objectives of Dandelion. Dandelion’s proposal is to modify the P2P gossip protocol so that an attacker can not link an IP to a public key. Dandelion works in 2 different phases:

  • Stem phase: Provides anonymity to the protocol, where each node decides randomly whether the transaction is broadcasted to every peer or to a single one. Upon reception, the recipient node throws a dice which decides whether he continues the stem phase or proceeds to the Fluff phase. This phase obfuscate the path taken by a transaction before it is distributed to the rest of the network, and therefore, makes it more difficult to trace back the public key of the transaction’s originator to its IP.
  • Fluff phase: The diffusion phase, in which the transaction is broadcasted to the entire network.
Dandelion protocol, the stem phase dotted in blue and the fluff phase in black

Thus, Witnet (and other decentralized protocols) might choose an approach like Dandelion to obfuscate the sources of transactions. The main benefit over the cryptographic protocols we have seen before, is the low overhead that it adds to nodes. However, we need to take into account that this is still an obfuscation solution, and not a cryptographically secure solution.

Conclusions

The protocols discussed above give us a clear view of what can be practically adopted by Witnet. It seems that both time-release and ZKSNARKs — although ideal from a security perspective — are not good candidates for Witnet. The first for being overall impractical, the second for substantially limiting the number of commitments a node can do in an epoch. Dandelion and ring signatures seem like a more practical approach for Witnet albeit sacrificing security. Dandelion seems very adaptable to Witnet’s P2P network, while we would still have to analyze the trade-offs between signature sizes and security in the case of ring signatures. In any case, I hope the analysis made helps other projects visualize the best solution for their use cases.

Thanks you for taking the time to read!

Please let us know if you have any questions or comments below. You can follow Witnet or myself on Twitter and stay up to date on our blog.


Thanks to Mario, James and Adán for contributing to the post! :)