pepper-project.github.io/summary-perf.htm at master · pepper-project/pepper-project.github.io · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.1//EN" "http://www.w3.org/TR/xhtml11/DTD/xhtml11.dtd">
<html xmlns="http://www.w3.org/1999/xhtml" xml:lang="en">
  <head>
    <meta name="keywords" content="verifiable,verified,verified computation,verifiable compuation,outsourced computation,third-party computing,PCP,probabilistically-checkable proofs,arguments,interactive proofs,IPs" />
    <link href="https://fonts.googleapis.com/css?family=Roboto" rel="stylesheet">
    <link rel="stylesheet" type="text/css" href="bootstrap/css/bootstrap.css" />
    <link rel="stylesheet" type="text/css" href="index.css" />
    <title>Pepper: toward practical verifiable computation</title>
  </head>
  <body>
    <div id="wrap">
      <div class="container">
        <!--fixed navbar on top of the page-->
        <div class="navbar navbar-inverse navbar-fixed-top">
          <div class="container">
            <div class="navbar-header">
              <a class="navbar-brand" href="index.htm">
                  <span>Pepper: toward practical verifiable computation</span>
              </a>
            </div>
          </div>
        </div>
      </div>
      <div class="container">
        <div class="row">
          <div class="sidebar col-xs-3">
            <div class="container">
              <ul id="nav-tab" class="nav sidenav affix">
                <li class="">
                <a class="tab-toggle" href="index.htm">Home</a>
                </li>
                <li>
                  <a class="collapse-toggle" href="summary-perf-collapsed.htm">About <span class="up-caret"></span></a>
                  <ul id="about-collapse" class="in">
                    <li class=""><a class="tab-toggle" href="what-is-pepper.htm">What is Pepper?</a></li>
                    <li class=""><a class="tab-toggle" href="our-approach.htm">Approach and research</a></li>
                    <li class=""><a class="tab-toggle" href="summary-results.htm">Summary of results</a></li>
                    <li class=""><a class="tab-toggle" href="summary-systems.htm">Built systems</a></li>
                    <li class="active"><a class="tab-toggle" href="summary-perf.htm">Performance</a></li>
                  </ul>
                </li >
                <li class=""><a class="tab-toggle" href="publications.htm">Publications</a></li>
                <li class=""><a class="tab-toggle" href="talks.htm">Presentations</a></li>
                <li class=""><a class="tab-toggle" href="tutorials.htm">Tutorials and exercises</a></li>
                <li class=""><a class="tab-toggle" href="people.htm">People</a></li>
                <li class=""><a class="tab-toggle" href="related.htm">Related projects</a></li>
                <li class=""><a class="tab-toggle" href="source.htm">Source code</a></li>
                <li class=""><a class="tab-toggle" href="funding.htm">Funding and support</a></li>
                <li class=""><a class="tab-toggle" href="contact.htm">Contact</a></li>
              </ul>
            </div>
          </div>
          <!--content for each tab -->
          <div class="tab-content col-xs-9">
            <div class="my-tab-pane" id="summary-perf">
    <div class="content">
        <div class="descriptive">
            <h3>Summary of performance</h3>

            <p>Here is a high-level summary. (Our <a
                href="publications.htm">publications</a>
            provide detail. See especially <a href="http://dl.acm.org/citation.cfm?id=2728770.2641562">this
            CACM article</a> and
            <a class="cross-tab-toggle"
                href="summary-systems.htm#buffet">Buffet</a>.) </p>

            <p>None of our systems (or the <a
                href="related.htm">others in this area</a>)
            have achieved true practicality yet.</p>

            <p>There are two principal issues, for all
            of these projects:</p>

            <p>
            <b>(1) Costs to the verifier.</b> To check that a
            remote computation was performed correctly, the
            verifier must incur a <i>per-computation setup
                cost</i>: this cost (which consists of CPU
            and network costs) amortizes over multiple
            instances of the same computation (potentially
            over <a href="related.htm">all future
                instances</a>), on different inputs.
            However, the cross-over point, in terms of when
            the setup cost is paid for, is quite high:
            tens or hundreds of thousands of
            instances of the same computation.
            </p>
                <ul>
                    <li>This setup cost can be slashed
                    (as in
                    <a class="cross-tab-toggle" href="summary-systems.htm#allspice">Allspice</a>)
                    or eliminated (as
                    in <a href="related.htm">CMT</a>).
                    Unfortunately, these solutions apply
                    only to restricted classes of
                    computations.</li>
                    <li>Using the techniques of <a
                    href="related.htm">BCTV</a>, the setup cost can be reused over all
                    computations of the same size.
                    However, the cost of these techniques is very high,
                    and in practice, one would need to incur the setup
                    cost thousands of times anyway (as explained in <a
                    class="cross-tab-toggle"
                    href="summary-systems.htm#buffet">Buffet</a>).</li>
                    <li>Using <a
                    href="http://eprint.iacr.org/2014/595">other
                    techniques</a> of BCTV,
                    the setup cost can be made independent of the computation.
                    However, these techniques are primarily theory at this
                    point; for example, the prover's computational costs are many orders of
                    magnitude higher than the other works in the
                    area.</li>

                </ul>

            <p>
            <b>(2) Costs to the prover.</b> The CPU costs to the
            prover are currently immense: orders of
            magnitude (factors between a thousand and a
            million) more than simply executing the
            computation. An additional bottleneck is memory:
            the prover must materialize a transcript
            of a computation's execution.
            </p>

            <p>
            As a consequence of the above costs, all
            projects in this area are currently limited to
            small-scale computations: programs that take several million
            steps, but not more.
            </p>
        </div>
    </div>
</div>

          </div>
        </div>
      </div>
    </div>
    <script type="text/javascript" src="js/jquery.min.js"></script>
    <script type="text/javascript" src="bootstrap/js/bootstrap.js" ></script>


  </body>
</html>