没有合适的资源?快使用搜索试试~ 我知道了~
filecoin时空证明论文1
需积分: 0 0 下载量 39 浏览量
2022-08-03
12:36:57
上传
评论
收藏 247KB PDF 举报
温馨提示
试读
18页
filecoin时空证明论文1
资源详情
资源评论
资源推荐
Rational Proofs of Space-Time
Tal Moran
⇤
Ilan Orlov
†
Abstract
We introduce a new cryptographic primitive: Proofs of Space-Time (PoSTs) and construct a practical protocol
for implementing these proofs. A PoST allows a prover to convince a verifier that she spent a “space-time” resource
(storing data—space—over a period of time). Formally, we define the PoST resource as a trade-o↵ between CPU
work and space-time (under reasonable cost assumptions, a rational user will prefer to use the lower-cost space-time
resource over CPU work).
Compared to a proof-of-work, a PoST requires less energy use, as the “difficulty” can be increased by extending
the time period over which data is stored without increasing computation costs. Our definition is very similar to
“Proofs of Space” [ePrint 2013/796, 2013/805] but, unlike the previous definitions, takes into account amortization
attacks and storage duration. Moreover, our protocol uses a very di↵erent (and simpler) technique, making use of the
fact that we explicitly allow a space-time tradeo↵, and doesn’t require any non-standard assumptions (beyond random
oracles).
1 Introduction
A major problem in designing secure decentralized protocols for the internet is a lack of identity verification. It is
often easy for an attacker to create many “fake” identities that cannot be distinguished from the real thing. Several
strategies have been suggested for defending against such attacks (often referred to as “sybil attacks”); one of the most
popular is to force users of the system to spend resources in order to participate. Creating multiple identities would
require an attacker to spend a correspondingly larger amount of resources, making this attack much more expensive.
Any bounded resource can be used as the “payment”; one of the more common is computing resources, since they
do not require any additional infrastructure beyond that already needed to access the Internet. In order to ensure that
users actually do spend the appropriate resource payment, the users must employ a “proof of work”.
Proofs of work have been used for reducing spam [6], for defending against denial-of-service attacks [15] and
fairly recently, as the underlying mechanism for implementing a decentralized bulletin-board—this is the technical
heart of the Bitcoin protocol [11].
While e↵ective, proofs-of-work have a significant drawback; they require energy in direct proportion to the re-
source used (i.e., the amount of electricity required to run the CPU during the proof of work generally depends linearly
on the amount of work being performed). This is especially problematic in the context of the Bitcoin protocol, since
the security of the system relies on all honest parties constantly performing proofs of work. In addition to having an
environmental impact, this also sets a lower bound on transaction fees (since rational parties would only participate in
the protocol if their reward exceeds their energy cost). Motivated in large part by the need to replace proofs-of-work
as a basis for crypto-currencies, two (very similar) proposals for Proofs of Space (PoS) have been published [7, 2].
Park et al. also designed an alternative crypto-currency that is based on Proofs of Space [12].
A PoS is a two-phase protocol
1
: it consists of an initialization phase and (sometime later) an execution phase. In
an (N
0
, N
1
, T )-PoS the prover shows that she either (1) had access to at least N
0
storage between the initialization and
execution phases and at least N
1
space during the execution phase, or (2) used more than T time during the execution
phase.
At first glance, this definition might seem sufficient as a replacement for proof-of-work. However, in contrast to
work, space can be reused. Using the PoS definition as a “resource payment” scheme thus violates two properties we
would like any such scheme to satisfy:
⇤
IDC Herzliya. Email: [email protected]. Supported by ISF grant no. 1790/13 and Bar-Ilan Cyber-center grant no.
†
Outbrain
1
We use the formal definitions of [7], which are more general than those in [2]
1
1. Amortization-Resistance: A prover with access to max (N
0
, N
1
) space can, without violating the formal PoS se-
curity guarantee, generate an arbitrary number of di↵erent (N
0
, N
1
, T )-PoS proofs while using the same amount
of resources as an honest prover generating a single proof; thus, the amortized cost per proof can be arbitrarily
low.
2. Rationally Stored Proofs: Loosely speaking, in a rationally stored proof a verifier is convinced that a rational
prover has expended a space resource over a period of time. There may exist a successful adversarial strategy
that does not require the adversary to expend space over time, but this strategy will be more costly than the
honest one. If we are interested in designing a crypto-currency that replaces CPU work with a space-based
resource, our proof of resource consumption must be a rationally stored proof, otherwise rational parties will
prefer to use the adversarial strategy, and we can no longer claim that the crypto-currency is energy-efficient.
The cost of storage is proportional to the product of the storage space and the time it is used (e.g., in most
cloud storage services, it costs the same to store 10TB for two months or 20TB for one month
2
). Under the PoS
definition, a prover can pay an arbitrarily small amount by discarding almost all stored data after the initialization
phase and rerunning the initialization in the execution phase (the prover only needs to store the communication
from the verifier in the initialization phase). More generally, a rational prover will prefer to use computation
over storage whenever the cost of storing the data between the phases is greater than the cost of rerunning the
initialization; when this occurs the PoS basically devolves into a standard proof-of-work in terms of energy
usage.
Even if we ignore energy use, this is a problem if the PoS is used in a protocol where the prover must generate
many proofs, but only some will be verified: the dishonest prover will not have to expend resources on the
unverified proofs in this case.
Although the protocols of [7, 2] are not completely undermined by these attacks, they are more than just a defi-
nitional problem. In particular, in the suggested PoS protocols based on graph pebbling, the work performed by the
honest prover in the initialization phase is proportional to the work required to access the graph (i.e., O(N
0
)). It’s not
clear how to increase the initialization costs without increasing either the memory size or verification cost linearly.
This strongly bounds the time that can be allowed between the initialization and execution phases if we want rational
provers to use space resources rather than CPU work. In the Spacemint protocol, for example, the authors suggest
running the proofs every minute or so [12]. If one wanted to run a proof only once a month, a rational miner might
prefer to rerun the initialization phase each time.
1.1 Our Contributions
“Fixed” Definition. In this paper, we define a new proof-of-resource-payment scheme: a “Proof of Spacetime”
(PoST), that we believe is better suited as a scalable energy-efficient replacement for proof-of-work. Our definition is
similar to a Proof of Space, but addresses both amortization and rationality of storage.
In a PoST, we consider two di↵erent “spendable” resources: one is CPU work (i.e., as in previous proofs-of-work),
and the second is “spacetime”: filling a specified amount of storage for a specified period of time (during which
it cannot be used for anything else); we believe spacetime is the “correct” space-based analog to work (which is a
measure of CPU power over time). Like work, spacetime is directly convertible to cost.
Rational Storage vs. Space Rather than require the prover to show exactly which resource was spent in the
execution phase, we allow the prover to choose arbitrarily the division between the two, as long as the total amount of
resources spent is enough.
That is, the prover convinces a verifier that she either spent a certain amount of CPU work, or reserved a certain
amount of storage space for some specified period of time or spent some linear combination of the two. However,
by setting parameters correctly, we can ensure that rational provers will prefer to use spacetime over work; when
this is the case we say that a PoST is Rationally Stored (we give a formal definition in Section 2.2.4). In situations
where it is reasonable to assume rational adversaries (such as in crypto-currencies), our definition opens the door to
new constructions that might not satisfy the PoS requirements. For example, the PoS definition essentially requires a
memory-hard function, while our construction is rationally stored but is not memory-hard!
2
Of course, this is also true for a local disk; during the interval in which we are using the disk to store data A, we can’t use it to store anything
else, so our “cost” is the utility we could have gained over the same period (e.g., by renting out the disk to a cloud-storage company).
2
Novel Construction. We construct a PoST based on incompressible proofs-of-work (IPoW); a variant of proofs-
of-work for which we can lower-bound the storage required for the proof itself. We give a candidate construction
based on the standard “hash preimage” PoW. Our protocols and proofs use a very di↵erent technique than the Proofs
of Space protocols, and we believe they are simpler to implement.
Standard Assumptions. Our constructions (and proofs) are in the random oracle model (like most previous
work on memory-hard functions and proofs of space). Unlike the existing PoS constructions, our analysis does not
require any non-standard assumptions (we use an information-theoretic argument to reduce breaking the soundness to
compressing a random string).
Di↵erent Parameter Regimes. In comparison with [7], we think of the time between the initialization and proof
phases as weeks rather than minutes (this could enable, for example, a crypto-currency in which the “miners” could
be completely powered o↵ for weeks at a time). One can think of our constructions as complementary to the existing
PoS constructions for di↵erent parameter regimes—On the one hand, the proof phase of our PoST protocol is less
efficient (it requires access to the entire storage, so a proof might take minutes rather than seconds, as is the case for
the pebbling-based constructions). This means it is not as well suited to very short periods between proofs. On the
other hand—unlike the existing PoS constructions—the computational difficulty of our initialization phase is tunable
independently of the amount of space, so it is possible to use it to prove reasonable storage size over long periods (e.g.,
weeks or months). In this parameter regime, a proof that takes several minutes would be reasonable.
Improvements to Spacemint. Finally, we propose a modification to the Spacemint crypto-currency protocol that
removes some restrictions on the types of PoS protocols it can use—allowing it to use PoSTs rather than the specific
PoS constructions it is currently based on (see Section 5)
1.2 Related Work
Memory-Bound Functions One of the inspirations for our protocol is the memory-bound function defined by
Dwork, Goldberg and Naor [5]. The goal in designing a memory-bound function is to make the performance bot-
tleneck for function evaluation the memory latency rather than CPU speed. The DGN design uses a “pointer-chasing”
technique in a random table to prove that an adversary who computes the function must touch many entries. Our
protocol is based on a similar idea. However, since our security goals are di↵erent (e.g., we do not need to ensure the
protocol actually uses a large amount of space, but do need to enforce a tradeo↵ between space and work) our protocol
(and proof techniques) are di↵erent.
Memory-Hard Functions Loosely speaking, a memory-hard function is a function that requires a large amount of
memory to evaluate [13, 1]. One of the main motivations for constructing such functions is to construct proofs-of-
work that are “ASIC-resistant” (based on the assumption that the large memory requirement would make such chips
prohibitively expensive). Note that the proposed memory-hard functions are still proofs-of-work; the prover must
constantly utilize her CPU in order to produce additional proofs. PoSTs, on the other hand, allow the prover to “rest”
(e.g., by turning o↵ her computer) while still expending space-time (since expending this resource only requires that
storage be filled with data for a period of time).
Proofs of Storage/Retrievability In a proof-of-storage/retrievability a prover convinces a verifier that she is cor-
rectly storing a file previously provided by the verifier [8, 4, 3, 9, 14]. The main motivation behind these protocols is
verifiable cloud storage; they are not suitable for use in a PoST protocol due to high communication requirements (the
verifier must send the entire file to the server in the first phase), and because they are not publicly verifiable. That is,
if the prover colludes with the owner of the file, she could use a very small amount of storage space and still be able
to prove that she can retrieve a large amount of pseudorandom data.
Permacoin Miller, Juels, Shi, Parno and Katz proposed a the Permacoin protocol, a cryptocurrency that includes,
in addition to the standard PoWs, a special, distributed, proof of retrievability that allows the cryptocurrency to serve
as a distributed backup for useful data [10]. In strict contrast to PoSTs, the Permacoin construction is amortizable by
design—an adversary who stores the entire dataset can reuse it for as many clients as it wishes. Thus, Permacoin still
requires regular PoWs, and cannot be used to replace them entirely with a storage-based resource. Also by design,
clients require a large amount of communication to retrieve the data they must store, in contrast to PoSs and PoSTs in
which clients trade computation for communication.
3
2 Proofs of Spacetime
A PoST deals in two types of resources: one is processing power and the other is storage. All our constructions are in
the random oracle model—we model processing power by counting the number of queries to the random oracle.
Modeling storage is a bit trickier. Our purpose is to allow an energy-efficient proof-of-resource-consumption for
rational parties, where we assume that the prover is rewarded for each successful proof (this is, roughly speaking, the
case in Bitcoin). Thus, simply proving that you used a lot of space in a computation is insufficient; otherwise it would
be rational to perform computations without pause (reusing the same space). Instead, we measure spacetime—a unit
of space “reserved” for a unit of time (and unusable for anything else during that time). To model this, we separate
the computation into two phases; we think of the first phase as occurring at time t = 0 and the second at time t = 1
(after a unit of time has passed). After executing the first phase, the prover outputs a state 2
{
0, 1
}
⇤
to be transferred
to the second phase; this is the only information that can be passed between phases. The size of the state || (in bits)
measures the space used by the prover over the time period between phases;
Informally, the soundness guarantee of a PoST is that the total number of resource units used by the adversary is
lower bounded by some specified value—the adversary can decide how to divide them between processing units and
spacetime units.
We give the formal definition of a PoST in Section 2.2, in Section 3 we present a simple construction of a PoST,
and in Section 3.1 we prove its security.
2.1 Units and Notation
Our basic units of measurement are CPU throughput, Space and Time. These can correspond to arbitrary real-world
units (e.g., 2
30
hash computations per minute, one Gigabyte and one minute, respectively). We define the rest of our
units in terms of the basics:
• Work: CPU⇥time; A unit of CPU e↵ort expended (e.g., 2
30
hash computations).
• Spacetime: space⇥time; A space unit that is “reserved” for a unit of time (and unusable for anything else during
that time).
In our definitions, and in particular when talking about the behavior of rational adversaries, we would like to
measure the total cost incurred by the prover, regardless of the type of resource expended. To do this, we need to
specify the conversion ratio between work and spacetime:
Real-world Cost We define to be the work-per-spacetime cost ratio in terms of real-world prices. That is, in the
real-world one spacetime unit costs as much as work units (the value of may change over time, and depends on the
relative real-world costs of storage space and processing power).
We define the corresponding cost function, the real-world cost of a PoST to be a normalized cost in work units: a
PoST that uses || spacetime units and x work units has real-world cost c = || + x.
2.2 Defining a PoST Scheme
A PoST scheme consists of two phases, each of which is an interactive protocol between a prover P and a verifier V.
3
Both parties have access to a random oracle H.
Initialization Phase Both parties receive as input an id string id 2
{
0, 1
}
k
. At the conclusion of this phase, both the
prover and the verifier output state strings (
P
2
{
0, 1
}
⇤
and
V
2
{
0, 1
}
⇤
, respectively):
(
P
,
V
)
D
P
H
(id), V
H
(id)
E
.
Execution Phase Both parties receive the id and their corresponding state from the initialization phase. At the end of
this phase, the verifier either accepts or rejects (out
V
2
{
0, 1
}
, where 1 is interpreted as “accept”). The prover
has no output:
(·, out
V
)
D
P
H
(id,
P
), V
H
(id,
V
)
E
.
3
Although the definition allows general interaction, in our construction the first phase is non-interactive (the prover sends a single message) and
the second consists of a single round.
4
剩余17页未读,继续阅读
赶路的稻草人
- 粉丝: 24
- 资源: 330
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0