Space and Time 백서

Space and Time

원문

bitpro가 원문에서 글자만 모은 내용이에요. 표·그림·수식은 빠지거나 깨질 수 있어요. 전체 6쪽 중 3쪽

ing a Proof of SQL proof is parsing the SQL text. This effectively acts as a preprocessing step, creating an abstract syntax tree (AST) that can be consumed by the remainder of the process. See this resource for a more in-depth explanation of how many query engines work. The parser works similarly to other parsers: by first creating an AST. This AST is a tree of SQL operations and components. For instance, consider the following query, which is converted to the AST shown below: SELECT hash, timestamp FROM blocks WHERE block > 1000 AND transaction_count = 0 Figure 6: Diagram of AST Nodes for Example Query 3.3 Query Executor and Interactive Protocol Builder The second step in the process of creating a Proof of SQL proof is to execute the query and build the protocol that will produce the proof. The resulting protocol is an interactive protocol, in part 18 because the protocol depends on the data that is in the database. While this protocol is described as an interactive protocol, the Fiat-Shamir transformation allows the proof to be non-interactive. In the language of most other ZK-protocols, this is the step in which the circuit is designed. To execute the query and build the proof, the Prover passes over the AST nodes and does the following four things for each node: 1. Query execution 2. Witness generation 3. Commitment computation 4. Constraint building To verify the query, the Verifier also passes over the AST node. When doing this, the Verifier only needs to do the last step out of the four that the Prover does (that is, constraint building). 3.3.1 Query Execution / Witness Generation The most obvious example of a Verifier is a smart contract that is querying the database, but it can be any trusted party. For example, an end client’s browser could act as a Verifier . Proof of SQL is necessary when an application has either restricted compute or restricted storage but still needs a security guarantee that the analytics run on data has been executed correctly, and that the underlying data has not been tampered with. The Prover is computationally intensive, whereas the Verifier is lightweight and designed to be executed on client devices or within smart contracts (which have extremely limited storage and computation capability). However, the Prover can be any device since there is no need to trust it, and in practice, it will be the cheapest resource available. A key architectural concept worth highlighting here is the idea of a commitment , which is a type of digital fingerprint – a lightweight digest of the data in the table. Commitments are the source of truth for a table. In order to detect tampering, the Verifier compares the Prover ’s response with the commitment. This is the primary reason for SXT Chain: to maintain the commitments for tables. In one sense, the Proof of SQL protocol can be thought of as a query engine, while Space and Time is the entire database management system. The remainder of this section is primarily focused on describing the query engine: Proof of SQL proper. The chain’s Validators are responsible for maintaining these commitments. This is described elsewhere in the paper. For the purposes of this section, we will simply assume that the Verifier has trustworthy access to this commitment so that it is able to detect any tampering. First, the Prover must generate the result of the query and any intermediate values needed to produce the result and proof. The word “witness” is used to mean intermediate values that are needed to verify certain steps of the query execution, but aren’t known by the Verifier . The Verifier doesn’t actually need to have knowledge of what the witness is, but the protocol 19 guarantees that such a witness exists. The existence of a valid witness is sufficient to prove that the result is correct. This is, in part, why the term zero-knowledge applies, since the Verifier has zero knowledge of the witness. Query execution and witness generation are almost the same, and are tightly linked. The SQL execution engine operates on table data in a columnar fashion, and produces intermediate values. The witness is the intermediate columns that are needed to verify the SQL execution. In some situations, additional witness columns on top of those needed solely for execution are also needed. As an example, we will look at the previous query again, and will use the following table as the blocks table: SELECT hash, timestamp FROM blocks WHERE block > 1000 AND transaction_count = 0 block hash timestamp transaction_count 997 0xef6e7e8 01:23 2 998 0xad5674d 01:33 1 999 0xcbc4567 01:44 0 1000 0x1ea13ea 01:52 4 1001 0xc460f97 02:04 0 1002 0x96b501c 02:15 6 The output of the Equals, Inequality, and And nodes would be: Equals (transaction_count = 0) Inequality (block > 1000) And 0 (false) 0 (false) 0 (false) 0 (true) 0 (false) 0 (false) 1 (true) 0 (false) 0 (false) 0 (false) 0 (false) 0 (false) 1 (true) 1 (true) 1 (true) 0 (false) 1 (true) 0 (false) 20 While none of these are the actual result, they are used in the computation of the result, and are needed to verify that the result is correct. Thus, they are considered part of the witness, and must be generated by the Prover . 3.3.2 Commitment Computation / Multiple Rounds Once the witness has been computed, it must be committed to, ensuring that the Prover cannot “change its mind” after the fact. This is the most computationally expensive step of the process and is therefore pushed to GPUs. For the most part, the commitment scheme can be treated as a “black box” compared with the rest of the protocol. See section 3.7 for more details on the exact commitment scheme used. Some of the nodes in the AST require a two-round protocol to efficiently create a witness. This is because the witness depends on random challenges from the Verifier . As a result, the commitment computation step and witness generation step execute twice. After the first computation of the commitments, new random challenges are sent from the Verifier (see, for example, the Group By protocol). When the commitment computation is done in a two-rounds fashion, the Verifier simulates the interactive protocol via the Fiat Shamir heuristic. This is done before passing over the AST nodes, meaning that the Verifier needs only one pass through the nodes. 3.3.3 Constraint Building Finally, polynomial constraints are created that specify relationships that must hold between the witness columns. This is a very natural mapping because SQL is a relational language whose queries correspond cleanly to these polynomial relationships/constraints between the intermediate columns of the SQL execution. See sections 3.5 and 3.6 for more details on what these polynomial constraints look like. 3.4 Notation We will briefly discuss some of the mathematical notation needed for the following sections. Most of this notation follows the literature fairly closely, although we diverge in some areas so that we can write things more concisely. Since we are dealing primarily with data in tables that are processed in a columnar fashion, we will use notation that reflects this. We will notate columns of data with capital letters such as where is the number of rows. If needed, we can embed in a larger vector space simply by appending 's to the column. Furthermore, we can think of as a multilinear polynomial in variables. That is, there is a unique multilinear 21 such that for . In other words, the bit representation of the index of a value gives the coordinates that evaluate to that value for . As an example, if , then . We write to denote entrywise multiplication. So, means that for all . We write to denote the sum of the (non-zero) entries of . So, means that . Finally, we let denote the column that is 1 for the first entries and 0 otherwise. 3.5 Example Subprotocols The following examples are explicit examples of nodes of the query plan. The first is an example of a boolean expression and the second is an example of a sum aggregation node. 3.5.1 Equality Protocol Builder One of the simplest examples is an equality expression: Consider the Equals node from the example in sections 3.1 and 3.2, where we let be the transaction_count column and be the result of the Equals node. It is straightforward to show that this result is correct if and only if there exists a witness column, , such that, and . These two equations are the constraints that must be satisfied. It happens that the following column is a valid witness. - transaction_count - result of Equals node (transaction_count = 0) 22 2 0 (false) 1 0 (false) 0 1 (true) 4 0 (false) 0 1 (true) 6 0 (false) 3.5.2 Group By Protocol Builder For this example, we will describe a simplified version of an aggregation/GROUP BY clause. Consider the query SELECT from_wallet, SUM(amount) FROM table GROUP BY from_wallet for the table: - amount - from_wallet to_wallet 74 1025 1034 24 1034 1099 12 1025 1099 56 1099 1025 22 1099 1000 45 1025 1025 The correct result is: - from_wallet (result) - sum (result) 1025 175 1034 24 1099 34 It can be shown that the result of this query is correct if and only if there exist witness columns and such that the following hold for some randomly chosen : 23 , , and where is the number of rows in the original table, while is the number of rows in the result. It is important to note that and depend on , while and do not. If was chosen before the commitments of and were sent to the Verifier , the values of and could be changed based on the value of allowing a malicious Prover to provide the wrong result. In other words, must be a function of and . Suppose, for example, that happened to be . Then, we would have the following: 74 1025 1025 175 24 1034 1034 24 12 1025 1099 34 56 1099 0 0 0 22 1099 0 0 0 45 1025 0 0 0 In summary, this would be the sequence of interactions in the interactive version of the protocol: ● Verifier → Prover : The query: SELECT from_wallet, SUM(amount) FROM table GROUP BY from_wallet ● Prover → Verifier : The results and any intermediate results: and . ● Verifier → Prover : Random challenges: . ● Prover → Verifier : Witness columns: and . ● Verifier and Prover : Remaining interactive protocol (sum-check + commitment opening) 3.6 Relation Proof Protocol (Sum-check) The first two steps of the protocol (sections 3.2 and 3.3) allow the Prover and Verifier to agree on a collection of relations between columns of data and provide the Verifier with commitments to these columns of data. The next step is for the Prover to convince the Verifier that these relations hold. 24 Once the first two steps of the protocol are complete, the Prover has constructed a collection of witness columns and a collection of polynomial constraints that these witness columns satisfy. Additionally, the Prover has sent commitments to each of the witness columns to the Verifier , and the Verifier has constructed the same collection of polynomial constraints and sums. In other words, the Prover has a collection of columns and the Verifier has the commitments . Furthermore, both the Prover and Verifier have agreed on a collection of relations and sums between these vectors: a collection of low degree polynomials and . It is the Prover’s job to show that for each . Note that this is the same as saying that for all , but not for arbitrary . Additionally, the Prover must show that for each . At this point, the Verifier sends the Prover the challenges . This gives a structured challenge column, , defined by for . This, in turn, allows the Prover and Verifier to agree on the following combined constraint: This constraint holds with high probability exactly when the original constraints hold as well. This is proven using the multilinear sum-check protocol. See section 4.1 of Thaler [5] for an excellent explanation of how sum-check works. The last step of sum-check is the evaluation of the combined polynomial at a random point, which reduces to evaluations of at that point. These evaluations are proven using the commitment scheme and the commitments , described in the next section. 3.7 Commitment Evaluator After the first three steps (sections 3.1, 3.2, 3.5), the Prover has produced a proof of the query along with the result with only one missing component: the opening/evaluation of the commitments/columns of data. There are a variety of commitment schemes that enable this, so for the rest of the protocol, this can be treated as a black box. However, because the biggest computational cost revolves around the commitments and their uses, the decision of which commitment scheme to use is important. Proof of SQL uses the Dory commitment scheme [6] and the HyperKZG commitment scheme, and are working on a third, novel, scheme that will supersede both. Importantly, the Space and Time Validators are designed to maintain multiple 25 commitment schemes, and more can be added in the future as new, state-of-the-art commitment schemes are developed. There are several motivating factors that drive these choices. We will list them in rough order of importance. 1. Updateable/Homomorphic Commitments: As a reminder, in the Proof of SQL protocol, the Prover holds the data that is in the tables, while the Verifier holds onto the commitments. Since the vast majority of tables in a database are not static, there needs to be some mechanism by which the Verifier can update commitments when new data is appended to a table. More specifically, we want some function such that: new commitment = Update(old commitment, appended data) In other words, data access is not required in order to update commitments to the data. Any homomorphic commitment scheme has this property. Dory and HyperKZG are homomorphic commitment schemes. In addition to being updateable, homomorphism has other helpful properties, such as supporting deltas/snapshots. 2. Efficient Verifier: Because the amount of data that is being queried against can be very large, we need the Verifier to have sub-linear performance. Dory’s and HyperKZG’s verifiers run in time. However, the HyperKZG is additionally cheap enough to be run inside an Ethereum smart contract. 3. Transparency: While this is a beneficial property for any protocol, it is particularly important for Proof of SQL because large data volumes exist. Without a transparent setup, a trusted setup would be necessary, which would require an upper bound on table size. While a large upper bound could be set, making this sufficiently large would require a very large trusted setup. Unfortunately, HyperKZG requires a trusted setup. However, there is a highly reputable universal setup initial run for ZCash (and later others) that supports up to 0.5 billion rows of data. 4. Partition Friendly: In any efficient database, partitioning and other smart indexing schemes are essential to running performant queries. In particular, we need to be able to run queries without needing to process all of the data in the tables. In addition to being homomorphic, Dory is a 2D commitment scheme, and the Prover time is in certain circumstances. This means that access to all of the data is not needed for certain evaluations. 26 4 Use Cases for the Next-Generation of Web3 4.1 Building a Flexible ZK-Rollup/L2 Proof of SQL can power bridgeless, gas-minimized microtransactions across multiple ledgers. ZK-rollups reduce Ethereum gas fees by batching offchain transactions and posting a single proof onchain. With Proof of SQL, developers can build a ZK-rollup on top of Space and Time, instantly appending transactions to a tamperproof ledger and rolling them up to the main chain. Unlike typical L2 solutions, Proof of SQL supports data processing (joins, aggregations, etc.) and scales beyond a single ledger, while providing instant finality and bridging-free cross-chain interactions. Transactions incur gas only for deposits and withdrawals; execution remains offchain, dramatically reducing fees and complexity. 4.2 Secure Bridges and Multichain Data Backends Crypto app ecosystems remain fragmented, with each chain operating in isolation. Space and Time unifies these silos by indexing data from multiple chains and storing it in tamperproof tables. A smart contract on Ethereum, for instance, can verify real-time state from BNB Chain via Proof of SQL—no bridging required. This reduces engineering overhead, eliminates the need for separate cross-chain infrastructure, and enables more reliable bridge security: a bridge contract can verify locked assets on Chain A before releasing tokens on Chain B, using ZK-proven indexed balances for fraud-resistant transfers. 4.3 Dapp Backend (Decentralized) Traditional dapps rely on a lightweight onchain contract plus a centralized backend for data processing. Space and Time replaces the centralized component with a serverless, decentralized backend and database, providing APIs for SQL queries, role-based auth, and Python-based business logic. Smart contracts emit events that Space and Time automatically indexes, and offchain data can also be stored for fast retrieval and tamperproof verification. Developers retain a purely decentralized stack without compromising performance. 4.4 Data-Dri
프로젝트로 돌아가기