In Proofs, We Trust

Part Two

24.01.2018

Proof Systems are the engine behind blockchains

As long as the millions of untrusting bitcoiners are able to prove their bitcoin transactions to each other, the network lives on. In Part I, we charted out the basics of proof systems. Here we explore the economics around it.

Satya is obsessed with the Bering Sea Billionaire’s club! He wants to be a member as if it is going to make everything better. Unfortunately, since the last quarter, he suffered some unexpected financial losses and is no longer a billionaire. This just amped up his desire even more, and now he is now seriously considering how to influence Kali (the sole gatekeeper of the club) — bribe or coercion.

In the face of such a threat, Kali, being a salaried employee in the club and not a billionaire herself, has nothing much at stake to resist this. The stakes are too high for Satya and too low for Kali. This is bad!

  • Prover with high stakes can influence the verifier, by colluding outside the club

  • Verifier, having low stakes, might give in, invalidating any proof so far

As a general principle, in every proof system, verification must be backed by at least the same if not a much higher stake than that behind proving.

If this cannot be guaranteed, all club members must either trust that Kali is following the protocol in spite of good reasons not to do so, or just assume that the security of the proof system has been compromised, — the former being the case of transitive trust. Here, the trust is transitive since all club members trust Kali only because of their trust in the executives who trusted Kali to act as the sole verifier.

Transitive Trust: Members → Executives → Kali

The executives, being billionaires themselves and also being the representatives of the club, have a lot more stake than Kali, to the point that their stakes are higher than that of a sole applicant. This makes them more trustworthy with respect to being the guardian behind the proof system that Kali is part of. Thus, only by means of transitive trust can Kali be trusted by those outside the protocol.

In a Proof System protocol where the prover has more stakes than the verifier, then the trust must be mediated by way of third parties with stakes higher than that of the prover, making it a transitive trust setup. This can be a severe limitation where the prover and the verifier are unable to agree upon a trusted third party, such as the case of high stakes escrows.

This limitation cannot be addressed using the cybersecurity measures of firewalls and access control systems, as it still does not prevent Satya and Kali from interacting outside the club membership protocol. However, if we invite all existing members to verify alongside Kali, as a second pair of eyes, that is, if the network itself can act as high stakes mediating party, we raise the stakes of verification over that of proving.

  • the members, as verifiers, will bring their high stakes of being billionaires themselves

  • for every applicant, as a prover, now there are multiple verifiers cumulatively putting in their stakes against the stake of the single applicant

With this approach, what we are essentially doing is replacing the mediator from a trusted third party (the executive team) with the members of the club.

Here we assume that the prover is unable to do bilocation or we have measures against a Sybil attack. In effect, we carry from this that if there are multiple provers, they are not coordinating with each other for the same proof or a range of proofs. Without this, the stakes on the proving side could become higher than that on the verifying side since the stakes would get cumulatively added with each new prover in the prover-coalition. Imagine a worst case scenario, where there are much more non-billionaires provers than the number of club members as verifiers. This is like an economic DDOS attack from a Proof System perspective.

However, members would verify every proof provided the cost of verification is less than the value of membership in the club and the payouts that might be received in spotting bad provers. To ensure this, the verification should be automated as part of the client software in such a way that the verification is carried out unnoticed. As for the payout structure, we will devise one in the next section.

For any proof system to work, the cost of verification must always be less than the value gained from the proof system, making it economically feasible.

Additionally, as motivating factor for every member, the client software can have a live dashboard displaying all members who are verifying at this moment — as a real-time indicator of how members are getting involved is strengthening the club membership.

With this setup, we now have an economic asymmetry favouring the prover, — one claiming-to-be-billionaire applicant (the prover) versus many billionaires (the verifiers).

  • the cost of defending the integrity of membership is split amongst all of the verifiers

  • the cost of attack gets multiplied each time a new verifier gets added as each prover is matched with this one new verifier now

Soon these verifiers start encouraging others to weigh in, and in time we have a growing culture of verification resulting in high enough stakes on the verification side of things. Finally, there is a tipping point, when it is cheaper to defend than to attack from the perspective of stakes which is a direct measure of the involvement of the members in the signup process.

Therefore, we must design systems that foster greater involvement from its members with the principal aims of:

  1. incentivizing higher participation from existing members during signups
  2. so verification be backed by higher stakes than that in proving

As long as the above is true, observers outside the proof system have reasons to trust the proofs as if these are self-evident. Therefore, cryptography alone is not enough to establish self-evident proofs, it is the economics behind it that shape its trustworthiness as well, making every proof system a crypto-economic one even if it not explicitly stated.

As a general principle, for a proof to be self-evident, it must always be packaged along with a record of the economic setup that secured it.

As a natural evolution of this culture of widespread verification, the executives of the club decide to formalize this economic setup to publish the new rules of club membership as follows

The New Rules of Club Membership

Membership of the club is based on each member possessing a valid proof of balance (along with proof of identity) demonstrating that one is a billionaire. In this regard, we want to encourage all members to help out keeping the integrity of the club. With that purpose, we mandate the following rules incentivizing a club-wide verification of new applicants as well as existing members.

NOTE: Please read up to the last mandate to make sense of it all. This is due to the non-linearity of the mandate list._

Mandate 1. Making applicant verification lucrative. For every new signup, applicants have to provide a link to their professional network which will be broadcasted to all members asking everyone to verify the proof of balance. This is referred to as a “call for verification”.

Value-at-risk: Potential gains with accepting this new applicant. Members will feel encouraged to verify the proofs as they might be benefited when the person gets to be a member.

Mandate 2. Making members renew their proofs of balance. All proofs of balance expire every 6 months from when it was first submitted. Therefore, every member has to re-submit new proofs of balance every six months, while any member can pick out the proof of some other member to check if it is still valid. If it does not check out, the member who just verified can just broadcast a “call for verification” message to the network. Receiving this message, others can verify the proof of that member in question and publish their result back to the network.

Value-at-risk: Reputation of the Club. Since the financial status of members can change in everyday life:

  • members will be forced to keep their proofs updated by submitting newer proofs every six months, and

  • at the same time verify other to not lose the reputation of the club.

Mandate 3. Bonded membership. We, as the executives, mandate a security fee to sign up to the club. Only bonded members are allowed in the club.

The fee gets slashed (or lost or taken) if:

  • a new applicant is caught cheating his proof of balance

  • an existing member no longer has a valid proof of balance, leading to a loss of membership

There is no finder’s fee — all slashed fees get distributed amongst everyone in the club. Upon getting slashed, members can apply again with fresh fees. Since the fees come from the funds of members, this makes a natural scarcity out of it.

Value-at-risk: Slashable Security Fee.

How does it work? With the first three mandates in place, each member’s reputation is linked with that of the club, and in turn with each other, making their incentives mutually dependent on an incentive web. Being locked up in this web, everyone is forced to participate in verifying all proofs from new applicants as well as from each other in a cat-n-mouse game of paranoia.

As a general principle, having multiple verifiers tied up in an interdependent incentive web is better than a single verifier equaling the same amount of stakes. This is because of the natural check-and-balance amongst the many untrusting verifiers — leading to compounded stakes, not just combined!

There is a cutoff where the stakes are so high, that the incentive web gets stuck on a recursive loop of over-verification in order to remove any possibility of cheating. That is why the compounded stakes in verification must be comparable to the value of what is being secured.

While the paranoia ensures no one can cheat on their proof of balance, be it members (on being reviewed) or new applicants (on signing up), there needs to be a moment in time where all of the verification results are consolidated for publishing the final result of whether the club accepted the proof or not. Without this consolidation, the paranoia will deteriorate into a network-wide panic where members keep verifying each other without any end.

To facilitate the network-wide consolidation of the verification results, we introduce in the next two mandates of 4 & 5, timed breaks when an agreement can be reached. Specifically, in the next mandate of 6, we ensure that members do not collude with each other to invalidate a valid proof or validate an invalid one. Through the combined effort of 4, 5, and 6, the network is able to reach a consensus on a proof.

Mandate 4. Timeout Rounds. We set an upper limit of 24 hours by when the verification results of a proof have to be submitted to the network by all members. The results of a verification expire with the arrival of the next round. This timeout keeps the panic at bay by introducing breaks in the network-wide verification of each proof.

Value-at-risk: Equilibrium. In that, if this is lost, panic will ensue where members will be stuck in never-ending loops of verification with no end in sight.

Mandate 5. Tallying the verification results. On each round, it is the executive team who will be tallying the results of the verification from all members to declare if there has been an agreement. Without the executive club, the members will lack any knowledge common to all whether the applicant’s proof has been finally accepted so they can move on to verifying other proofs.

Value-at-risk: Common Knowledge.

Mandate 6. Supermajority Agreement. During every instance of tallying, the supermajority is required to come to a common agreement on the validity of the proof of balance. A supermajority means that at least 2/3rd of all members have to agree.

Value-at-risk: Collusion Free Diversity.

Mandate 7. Keep the integrity of the club. Lastly, we mandate that in any timing round, if more than 1/3rd of existing members are found to no longer be billionaires as a result of the “call for verification” on existing members, the club is terminated. In light of mandate 6, if more than 1/3rd members are lost in a single round, some members must be are lying about others.

Value-at-risk: The very existence of the club.

Mandate 8. Making the proofs accessible and self-evident. The final result, only for valid proofs, will be committed to a store accessible to all members of the club, allowing anyone to pick any proof in a few months to keep expired proofs from staying there.

In the spirit of storing the final result in the form of a self-evident proof, it should contain the:

  • Cryptographic remnant: The proof of balance of the person in question

  • Economic conditions:
    – All signatures of those who verified it to be true as a proof the economic setup
    – Receipt of the locked security fee of the person in question

Being part crypto and part economic, we can refer to self-evident proofs as crypto-economic in nature.

Value-at-risk: Provable trust on the verifiers.

NOTE: As the proofs, that are invalid, get dropped, they do not get stored in the vault. This means that the same proof can be submitted many times, in which case, a new security fee will get slashed each time. This will prevent repetitive attempts as long as the fees are coming from limited funds.

Mandate   Intention Value-at-risk Consequence
0. Automate verification in the client software used by every member of the club Make verifcation cheap with no opt-in needed Members turning off the client software All proofs to be verified unnoticed
1.
Works with: 7.
Publish the professional network of the applicant Make verifying applicants lucrative Network Effects: Potential gains with accepting this new applicant Maximum participation: more members to act as verifiers
2.
Works with: 3.
Expiring all proofs of balance in 6 months Making members renew their proofs of balance Reputation of the club Existing members face a verification challenge in the same spirit as that of new applicants
3. No security fee, no membership Bonded membership Slashable security fee No one cheats on their proof of balance
1. & 2. & 3.
Works with: 4. - 6.
Get most members to become verifiers since each member’s reputation is linked with that of the club, and in turn with each other Incentive Web: Web of interdependent incentives tying in all users and verifiers against provers Existence of the club Paranoia: All members actively participating fueled by a fear of losing their security fee and the existence of club at large  
4.
Works with: 5.
Upper limit of 24 hours for the response to be provided Timing Rounds Equilibrium Paranoia sans panic
5.
Works with: 4.
Every 24 hours, the executive tallies all responses Tallying the verification results Common Knowledge Agreement on the validity of a proof
6.
Works with: 5.
At least 2/3rd of all existing members have to agree The result to be a true representation of the club Collusion Free Diversity Higher involvement of club members leading to more social events to maximize networking in real life
4. & 5. & 6.
Works with: 1. - 3.
Network agreement on acceptance of all new applicants and the validity of existing members Consolidation Rounds Consensus Minimizes the trust on Kali as the sole verifier
7.
Works with: 3., 4. - 6.
Club null & void if > ⅓rd found to be no longer billionaires in a consolidation round Keep the integrity of the club by making clique formation difficult The very existence of the club No one unduly claims a proof to be false
8.
Works with: 1. - 7.
All proof to be self-evident because it contains the economic rationale behind it’s cryptographic verification Make the proofs accessible and self-evident Provable trust on the verifiers Pros: Anyone outside of the proof system can trust the proof without needing to trust the verifier.
Con: However, they still need to trust the executive team as the timestamping server and as the tallying agent.

Table 1. Scheme of Mandates

Conclusion

In the initial setup, Kali was the sole verifier.She did not have much skin in the game as compared to a rich prover who badly wanted to be part of the club. This leads to an unfavourable economic asymmetry, making the proof system insecure.

This was addressed by replacing Kali with the members of the club to act as verifiers together since the members, being billionaires, have a much higher stake, which when combined would be higher than most provers. Thus, we devised an elaborate scheme of mandates to catch all members in a web of incentives that make them rely on each other for the security of the club.

In this new scheme, with our mandates, we still kept the executives to have the final say on the validity of a proof of balance. This is essentially a delegated trust model because the members have to eventually delegate their responsibilities on the final result to the hands of the executives. However, delegated trust has its own problems:

1) Delegation to the executive team alone is, in effect, a single point of failure.

2) Unless the members are able to take action against the executives on a faulty consolidation, it is still questionable to put all that trust in a few people.

In order to address these, we will explore in the next and final part of this series how to utilize the club members to do what the executives are doing currently – consolidation of all verification. Something of this sort can be found in the way consolidation is carried out in blockchains using its “consensus mechanism”, which we will explore in an effort to realize a solution that is feasible.

Irony aside, with the rising price of a bitcoin, Bitcoin is turning out to be a billionaire’s club.

Afterthought

As an afterthought, let us recap the design principles that we discovered in this article.

0. Proof Systems offer the litmus test of truth.

What is true is what is verifiable — only and if so. Unless of course, it is true by assumption.

  1. A proof system is a protocol that enables one party, called a prover, to convince another party, called a verifier, of a fact within a reasonable amount of doubt. This could extend to multiple parties on either side.
  2. Proof = Successfully Verified Evidence-to-a-Claim. The prover puts forward claims, whose veracity is fact-checked by the verifier based on the pieces of evidence supporting the claim. On successful verification, the evidence gets baptized as a proof.
  3. A proof is valid only in the context of the proof system used to verify the evidence. A bitcoin transaction is not necessarily valid in Dash.

A Proof System where a part of the evidence is provided by the TTP

1. Verifier Integrity. The real burden of proofs in economic networks is on verifiers more so than on provers.

  1. From the perspective of network integrity, an invalid proof from a prover is much less harmful than verifiers invalidating a valid proof or validating an invalid proof.
  2. If not involved in the actual interaction of a proof system, its proofs are valid only for those who trust the verifier. Either be a verifier or trust in some who already are.

2. Crypto-Economics. In every proof system, verification must be backed by at least the same, if not a much higher stake than behind proving.

Crypto Economics
Performance(Construction) < Performance (Verification) « Performance(Deconstruction)
NOTE: Performance as in computational performance
Stakes(Verification) >= Stakes(Proving)

Table 2. Crypto-Economics.

This makes every proof system an economic system in addition to the cryptographic system that it is explicitly stated to be as.

  1. All computationally secure cryptographic protocol is always already a crypto-economic protocol.
  2. In well designed crypto-economic protocols, it is harder (higher stakes) to attack than to defend since the adversarial conflict favours the defender.

3. Verification Viability. For any proof system to work, the cost of verification must always be less than the value gained by the verifier(/s) from the proof system in order to make verification economically feasible.

  1. Making verification automatic and fast, while rewarding verifiers for spotting bad proofs — gives network participants incentive to become verifiers.

4. Gestaltonomics. The whole stake of an interdependent incentive web is greater than the sum of all stakes.

Having multiple verifiers tied up in an interdependent incentive web is better than a single verifier with the same amount of stakes.

  1. There is a natural check-and-balance amongst multiple verifiers, even more so if they are unable to trust each other — leading to compounded stakes, as verifying each other’s verification builds up on each other ‘s stakes.
  2. In a proof system, it is ideal to have multiple verifiers for every prover leveraging the compounded stakes on verification towards a favourable economic security.

5. Paranoia sans panic. In an incentive web, the compounded stakes in verification must be comparable to that of the value of what is being secured.

  1. There is a cut-off where the incentive web’s stakes are so high, that the verifiers get stuck on a recursive loop of verifying each other in order to remove any possibility of cheating.
  2. There must be timed breaks and a privileged verifier helping the verifiers break this loop.

6. Self-Evident Proofs. For a proof to be self-evident, proofs must always be packaged along with a record of the economic setup that secured it.

  1. Putting the signatures of all those who verified helps in proving the compounded stakes behind it beyond just the fact that the cryptographic signature checks out.
Continue the conversation

Anuj Das Gupta is a researcher and technologist.

stratumn logo

More Thinking