or
or
By clicking below, you agree to our terms of service.
New to HackMD? Sign up
Syntax | Example | Reference | |
---|---|---|---|
# Header | Header | 基本排版 | |
- Unordered List |
|
||
1. Ordered List |
|
||
- [ ] Todo List |
|
||
> Blockquote | Blockquote |
||
**Bold font** | Bold font | ||
*Italics font* | Italics font | ||
~~Strikethrough~~ | |||
19^th^ | 19th | ||
H~2~O | H2O | ||
++Inserted text++ | Inserted text | ||
==Marked text== | Marked text | ||
[link text](https:// "title") | Link | ||
 | Image | ||
`Code` | Code |
在筆記中貼入程式碼 | |
```javascript var i = 0; ``` |
|
||
:smile: | ![]() |
Emoji list | |
{%youtube youtube_id %} | Externals | ||
$L^aT_eX$ | LaTeX | ||
:::info This is a alert area. ::: |
This is a alert area. |
On a scale of 0-10, how likely is it that you would recommend HackMD to your friends, family or business associates?
Please give us some advice and help us improve HackMD.
Do you want to remove this version name and description?
Syncing
xxxxxxxxxx
ZkpComRef: Interfaces, Formats and Interoperability
Please start by reading the editorial disclaimer to ensure proper expectations about the process.
Collaboration Instructions
This page was prepared for a breakout session during the ZKProof 4th workshop in order to receive concurrent/collaborative suggestions of content that may be useful for the "ZKProof Community Reference" (ZkpComRef).
Goal: this document will focus on expanding Section 3.4 on APIs and File Formats and Section 3.7 on Constraint-System Interoperability.
Content
Each contribution should be either self-contained or written within the context of the section (as an edit of the current subsections). The field is advancing fast, and more interesting solutions for interfacing between frontends and backends are being published, different formats (PLONK, R1CS, Circuits, etc.) are being built and more needs for interoperability exist.
Contributors are free to chose the relevant topics, either expanding on existing titles or adding new subsections. Here is a list of potential topics to be covered:
Examples of topics:
Guidelines
What to include in the contribution:
Each contribution may have a different set of requirements or "titles", please try to think about the following questions when you write the contribution:
Add your contribution:
Email confirmation: After adding a contribution, please send a brief email to editors@zkproof.org to confirm your suggestion (mention the suggestion number and title).
Contribution #0: TEMPLATE VERSION
Do not edit or delete this template; instead, copy-paste its content inside one of the available suggestion placeholders below, and then edit it there.
Topic Description
Specification
Considerations
Contribution #1: PFCS (Prime Field Constraint System)
Topic Description
This is a possible generalization of R1CS and other constraint systems used in zero-knowledge proofs. The inspiring purpose is to facilitate formal proofs of correctness of R1CS with respect to higher-level specifications, but it may have broader uses.
Specification
A PFCS is a system of constraints over a prime field; the constraints include variables that range over a prime field. The motivation for PFCS stems from zero-knowledge proofs, but there may be more general applications. PFCS generalizes R1CS in two ways:
This is a prototype formalization of PFCS in the ACL2 theorem prover: https://github.com/acl2/acl2/tree/master/books/kestrel/crypto/pfcs
This is the hyperlinked documentation generated from that code:
https://www.cs.utexas.edu/users/moore/acl2/manuals/current/manual/?topic=PFCS____PRIME-FIELD-CONSTRAINT-SYSTEMS
Considerations
This seems a fairly simple idea, and may overlap with other similar initiatives in zkinterface and elsewhere. The details may vary, but the main idea is to provide more structure.
Formal verification is facilitated by the additional structure in the same way as procedural decomposition facilitates traditional program verification.
Contribution #2: zkInterface
(copy-paste here the template)
Contribution #3: SIEVE IR
Not yet public, but we can start preparing.
(copy-paste here the template)
The SIEVE IR is a circuit based intermediate representation currently in progress within DARPA's SIEVE program. The IR is based on circuits, and is parameterizable along two axis.
The IR comes with three "resources" as the inputs to a proof system. The relation defines a circuit, while two input streams provide common inputs (instance) and prover inputs (short witness).
Contribution #4: ACIR (Abstract Circuit Intermediate Representation)
A uniform constraint system over proving systems and NP relation (R1CS and PLONK-CSAT).
It allows uniformity over any proving system by allowing for black box functions, and special opcodes which allow for prover provided values.
(copy-paste here the template)
Contribution #5: UltraPLONK
Format
To specify the constraint system used in PLONK in an abstract manner, we need to specify:
One format which can be used to accomodate for custom constraints, is to view them as blackbox functions, where their functionality is known beforehand. This suggestion assumes the custom constraints are known along with their functionality.
The width is unbounded, which means that you can have any fan-in, fan-out configuration.
The available constraints are not theoretically bounded, so the format should accomodate for this.
A custom constraint can be seen as a polynomial identity which is encoded in this PLONK configuration.
The available custom constraints are accumulated into a quotient polynomial, where the degree of the quotient polynomial is a function of the degree of the highest polynomial identity.
(copy-paste here the template)
Contribution #6:</h2>
<blockquote class="raw part" data-startline="171" data-endline="171">
<p data-position="9261" data-size="0"><span data-position="9261" data-size="15">Suggested by : </span><small><span data-position="15" data-size="12"><i class="fa fa-user"></i><span class="px-1" data-position="9282" data-size="5">name1</span></span></small><small><span data-position="27" data-size="12"><i class="fa fa-user"></i><span class="px-1" data-position="9294" data-size="5">name2</span></span></small></p>
</blockquote>
<p class="part" data-startline="173" data-endline="173" data-position="9302" data-size="0"><strong data-position="9302" data-size="0"><span data-position="9304" data-size="30">(copy-paste here the template)</span></strong></p>
<hr>
<h2 class="raw part" data-startline="177" data-endline="177"><span data-position="9346" data-size="34">Contribution #7: Uniformity Matrix</span></h2>
<blockquote class="raw part" data-startline="179" data-endline="179">
<p data-position="9383" data-size="0"><span data-position="9383" data-size="15">Suggested by : </span><small><span data-position="15" data-size="22"><i class="fa fa-user"></i><span class="px-1" data-position="9404" data-size="15">Kimberlee Model</span></span></small><small><span data-position="37" data-size="12"><i class="fa fa-user"></i><span class="px-1" data-position="9426" data-size="5">name2</span></span></small></p>
</blockquote>
<p class="part" data-startline="181" data-endline="181" data-position="9434" data-size="0"><span data-position="9434" data-size="57">Multiple of the interfaces given here express uniformity.</span></p>
<p class="part" data-startline="183" data-endline="183" data-position="9493" data-size="0"><span data-position="9493" data-size="32">TODO: explain what is uniformity</span></p>
<ul class="part" data-startline="184" data-endline="186" data-position="9527" data-size="0">
<li class="raw" data-startline="184" data-endline="184" data-position="9529" data-size="0"><span data-position="9529" data-size="85">Uniformity for the purpose of the representation being "smaller" than the computation</span></li>
<li class="raw" data-startline="185" data-endline="186" data-position="9618" data-size="0"><span data-position="9618" data-size="62">or for allowing the proof to be "smaller" than the computation</span></li>
</ul>
<p class="part" data-startline="187" data-endline="187" data-position="9682" data-size="0"><span data-position="9682" data-size="24">TODO: fill in the table</span></p>
<table class="part" data-startline="189" data-endline="195">
<thead>
<tr>
<th><span data-position="9710" data-size="9">interface</span></th>
<th><span data-position="9723" data-size="15">constraint type</span></th>
<th><span data-position="9741" data-size="16">fixed repetition</span></th>
<th><span data-position="9760" data-size="11">conditional</span></th>
<th><span data-position="9776" data-size="26">encapsulated functionality</span></th>
</tr>
</thead>
<tbody>
<tr>
<td><span data-position="9904" data-size="4">PFCS</span></td>
<td><span data-position="9918" data-size="13">expr1 = expr2</span></td>
<td><span data-position="9935" data-size="2">no</span></td>
<td><span data-position="9954" data-size="13">not currently</span></td>
<td><span data-position="9970" data-size="3">yes</span></td>
</tr>
<tr>
<td><span data-position="10001" data-size="11">zkInterface</span></td>
<td><span data-position="10015" data-size="4">R1CS</span></td>
<td><span data-position="10032" data-size="4">TODO</span></td>
<td><span data-position="10051" data-size="4">TODO</span></td>
<td><span data-position="10067" data-size="4">TODO</span></td>
</tr>
<tr>
<td><span data-position="10098" data-size="8">SIEVE IR</span></td>
<td><span data-position="10112" data-size="8">Circuits</span></td>
<td><span data-position="10129" data-size="13">(in progress)</span></td>
<td><span data-position="10148" data-size="13">(in progress)</span></td>
<td><span data-position="10164" data-size="13">(in progress)</span></td>
</tr>
<tr>
<td><span data-position="10195" data-size="4">ACIR</span></td>
<td><span data-position="10209" data-size="8">Circuits</span></td>
<td><span data-position="10226" data-size="2">no</span></td>
<td><span data-position="10245" data-size="2">no</span></td>
<td><span data-position="10261" data-size="3">yes</span></td>
</tr>
<tr>
<td><span data-position="10292" data-size="5">PLONK</span></td>
<td><span data-position="10306" data-size="4">TODO</span></td>
<td><span data-position="10323" data-size="4">TODO</span></td>
<td><span data-position="10342" data-size="4">TODO</span></td>
<td><span data-position="10358" data-size="4">TODO</span></td>
</tr>
</tbody>
</table>
<p class="part" data-startline="197" data-endline="197" data-position="10388" data-size="0"><span data-position="10388" data-size="64">TODO: explain each column on the table (possibly add more cols?)</span></p>
<ul class="part" data-startline="199" data-endline="203" data-position="10455" data-size="0">
<li class="raw" data-startline="199" data-endline="199" data-position="10457" data-size="0"><strong data-position="10457" data-size="0"><span data-position="10459" data-size="15">constraint type</span></strong><span data-position="10476" data-size="26">: Form of the constraints.</span></li>
<li class="raw" data-startline="200" data-endline="200" data-position="10506" data-size="0"><strong data-position="10506" data-size="0"><span data-position="10508" data-size="16">fixed repetition</span></strong><span data-position="10526" data-size="28">: Support for bounded loops.</span></li>
<li class="raw" data-startline="201" data-endline="201" data-position="10558" data-size="0"><strong data-position="10558" data-size="0"><span data-position="10560" data-size="11">conditional</span></strong><span data-position="10573" data-size="66">: Support for branching (i.e. alternatives) on private conditions.</span></li>
<li class="raw" data-startline="202" data-endline="203" data-position="10644" data-size="0"><strong data-position="10644" data-size="0"><span data-position="10646" data-size="26">encapsulated functionality</span></strong><span data-position="10674" data-size="60">: Support for hierarchical/procedural structure and scoping.</span></li>
</ul>
<hr>