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프로젝트로 돌아가기