US9967088B2 — Rewritable blockchain (Part 1 of 2)
Document text
Research, not advice. Part of the Bitcoin research archive (October 2026). Claims labelled unverified, contested or fringe are reported, not endorsed; statuses of bills and rules are as of the date checked. Government, court and patent records are public domain; the research notes are CC BY 4.0.
THAI MULT ATTMATULUNULMANIMAI US009967088B2
(12) United States Patent (10) Patent No.: US 9 ,967,088 B2
Ateniese et al. (45) Date of Patent: May 8 , 2018
(54) REWRITABLE BLOCKCHAIN (58 ) Field of Classification Search
( 71) Applicants :Accenture Global Solutions Limited , CPC ....... HO4L 9/0637 ; H04L 9 /3226 ; H04L 9 /14 ;
HO4L 9 /0894 ; H04L 9/ 0841;
Dublin (IE ); GSC Secrypt, Hoboken , (Continued )
NJ (US )
( 72 ) Inventors: Giuseppe Ateniese , Hoboken , NJ (US ); ( 56 ) References Cited
Michael T. Chiaramonte , New York , U .S . PATENT DOCUMENTS
NY (US); David Treat, Wilmington,
MA (US); Bernardo Magri, Rome 6 , 108,783 A * 8/2000 Krawczyk ... ........ H04L 9/3236
(IT ) ; Daniele Venturi, Rome (IT ) 380 /28
(73 ) Assignee: Accenture Global Solutions Limited , 6 ,292,897 B1 9/2001 Gennaro et al.
Dublin (IE ) (Continued )
( * ) Notice : Subject to any disclaimer, the term of this OTHER PUBLICATIONS
patent is extended or adjusted under 35
U .S .C . 154 (b ) by 0 days. days. Rass, Stefan . “ Dynamic Proofs of Retrievability from Chameleon
Hashes ” . In SECRYPT ’ 13 , Seiten 296 - 304. SciTePress, 2013 .*
(21) Appl. No.: 15 /596,904 (Continued )
(22) Filed : May 16 , 2017 Primary Examiner — Darren B Schwartz
(74 ) Attorney, Agent, or Firm — Brinks Gilson & Lione ;
(65 ) Prior Publication Data Daniel H . Broaddus
US 2017 /0338947 A1 Nov. 23 , 2017 ABSTRACT
(57)
(30 ) Foreign Application Priority Data A system includes circuitry for rewriting blockchains in a
May 23 , 2016 (EP ) ................................. ... 16425044 non - tamper- evident or tamper -evident operation using a key
Aug. 11 , 2016 (EP ) ............ .. . ..... .. . .. 16425086
secret held by a trusted party. The blockchains may include
Feb . 17 , 2017 (EP ) ...... ..... .. ........... 17425018 a series of blocks secured integrity codes that may prevent
non -tamper - evident rewrites by non -trusted parties that are
(51) Int. Cl. not in possession of the key secret. In some cases , the key
H04L 9 /06 (2006 . 01) may allow valid but tamper-evident rewrites of the block
G06F 3 / 06 ( 2006 .01) chain by trusted entities . Integrity outputs may be generated
(Continued )
from the integrity codes based on the content of the previous
blocks in the series such that attempts by untrusted parties to
(52 ) CPC
U .S. CI........... H04L 9 /0637 (2013 .01 ); G06F 3/0619 replace a block may be detected through coding - inconsis
tencies with other blocks.
(2013 .01); G06F 3/0622 (2013 .01 );
( Continued ) 30 Claims, 15 Drawing Sheets
200
00:00 . 0
206 202 213
Lot 81 B3
-creen
IC (B2) = {C (B2')
00 -0 -0 - 0 204 210
206 2110
BG - -- -- - ---- Bn
250
202
0.000 . 0
DO 81 B3 - -- A - - --
0 -0 0 - 0
208 210
80 B2'
IC (B2 ) = 1C (81 )
US 9 , 967 ,088 B2
Page 2
(51) Int. Ci. OTHER PUBLICATIONS
H04L 9 /32 (2006 .01 ) Essentially Optimal Robust Secret Sharing with Maximal Corrup
H04L 9 / 14 (2006 .01) tions, Nov . 5 , 2015 , pp . 1 -38 , Cryptology ePrint Archive .
H04L 9 /08 (2006 .01) Accenture ' s “ Editable Blockchain " Prototype Draws Criticism —
CryptoCoinsNews, cyrptocoinsnews.com , Sep . 28 , 2016 , pp . 1 -3 .
H04L 9 /30 ( 2006 .01) Charles Moore, How Accenture Hacked the Blockchain , LinkedIn.
(52 ) U .S . CI. com , Nov . 2 , 2016 , pp . 1 - 14 .
Giuseppe Ateniese and Breno de Medeiros , A Provably Secure
CPC .......... GO6F 3/ 0659 ( 2013 .01); G06F 3 /0673 Nyberg -Rueppel Signature Variant with Applications, International
( 2013 .01); H04L 9/0643 (2013 .01); H04L Association for Cryptologic Research (IACR ) ePrint, 2004, pp .
9 / 0841 (2013.01) ; H04L 9 /0894 ( 2013 . 01 ); 1 - 17 .
H04L 9/14 (2013 .01); H04L 9/30 (2013.01); Dave Birch , Mutable and immutable blockchains , Tomorrow 's
Transactions, Sep . 26 , 2016 , pp . 1 -3 .
H04L 9 /3226 (2013 .01) Tal Rabin and Michael Ben -Or, Verifiable Secret Sharing and
( 58 ) Field of Classification Search Multiparty Protocols with Honest Majority ( Extended Abstract),
CPC ....... HO4L 9/ 0643; H04L 9 / 30 ; G06F 3 /0673 ; STOC '89 Proceedings of the twenty -first annual ACM symposium
G06F 3 /0619; G06F 3 /0622 ; G06F on Theory of computing , Association for Computing Machinery
(ACM ) Digital Library , May 14 - 17 , 1989 , pp . 73- 85 .
3 /0659 Giuseppe Ateniese and Breno de Medeiros , on the Key Exposure
See application file for complete search history . Problem in Chameleon Hashes , Security in Communication Net
works (SCN ) 2004. Lecture Notes in Computer Science , vol. 3352.
Springer, Berlin , Heidelberg , pp . 1 - 16 .
(56 ) References Cited U . S . Appl. No. 15 /596 ,899 — Notice of Allowance and Fees Due,
Jul. 17 , 2017 .
U .S . PATENT DOCUMENTS U .S . Appl. No . 15 /596 , 932 — Notice of Allowance and Fees Due,
Jul. 26 , 2017 .
7 ,730 ,319 B2 * 6 /2010 Ramzan ................ H04L 9/ 3013 U . S . Appl. No . 15 / 596 ,922 — PAIR Transaction History — Showing
380 / 28 entry ofReasons for Allowance on Aug. 6 , 2017 _ Captured Aug. 9 ,
9 ,436 ,923 B1 9/ 2016 Sriram et al. 2017 .
2002 /0099946 AL 7 / 2002 Herbert et al. D . Larimer, “Momentum - A Memory -Hard Proof-of-Work via
2002/0194209 A112 / 2002 Bolosky et al . Finding Birthday Collisions,” Invictus Innovcations Inc , Tech . Rep .,
2007 /0226514 Al * 9/ 2007 Maletsky G06F 21/ 32 Oct. 2013 .
713 /186 G . Ateniese , B . de Medeiros. “ Identity -based Chameleon Hash and
2007/ 0294205 Al 12 / 2007 Xu et al. Applications” . FC 2004 , LNCS , vol. 3110 , Springer- Verlag (2004 ),
2008 /0104407 Al 5 / 2008 Horne et al.
2008 /0195583 Al * 8 / 2008
008 Hsu ... ................ G06F 17 /30477 pp . 164 - 180 .
2009/0024848 AL 1/ 2009 Takasugi et al. Ateniese, et al., Sanitizable Signatures, European Symposium on
2009/0193256 A1* 7/ 2009 Takenaka ..... .. HO4L 9 /302 Research in Computer Security 2005 , LNCS 3679 , pp . 159 - 177,
713/ 176 Springer -Verlag Berlin Heidelberg , 2005.
2009 /0271631 A1 * 10 / 2009 Teranishi ............. HO4L 9 /3247 European Patent Office , International Search Report and Written
713 / 176 Opinion for PCT Application No . PCT/EP2017 /062240 dated Jul.
2010 /0005306 A1 * 1/2010 Izu .... . G06F 21/64 10 , 2017 , 11 pages .
713 / 176 European Patent Office , International Search Report and Written
2010 / 0046749 AL 2/ 2010 Hatano et al. Opinion for PCT Application No. PCT/EP2017 / 062241 dated Jul.
2010 /0169653 AL 7 / 2010 Takenaka et al. 11, 2017 , 11 pages.
2012/ 0072732 A1 3 / 2012 Canard et al. European Patent Office , International Search Report and Written
2015 / 0046337 A1 * 2/ 2015 Hu G06Q 20 /0658 Opinion for PCT Application No. PCT/EP2017 /062242 dated Jul.
705/65 11 , 2017 , 11 pages.
2015/0121062 A1 * 4 /2015 Gajek ................ H04L 63/0471 European Patent Office , International Search Report and Written
713 / 153 Opinion for PCT Application No. PCT/EP2017 /062243 dated Jul.
2015 /0128283 Al * 5 /2015 Mashima .............. GO6Q 10 / 10 10 , 2017 , 12 pages.
726 /26 Christian Decker, et al., “ Bitcoin , Transaction Malleability and
2015/0244690 A1* 8/ 2015 Mossbarger ......... HO4L 63/ 061 MtGox , Network and Parallel Computing” , 2014 , Springer Inter
713 /171
2015 /0332283 Al 11/ 2015 Witchey national Publishing , Cham , Switzerland , vol. 8713 , pp . 313 - 326 ,
2015 /0332395 AL 11/ 2015 Walker et al. 2014 .
2015 /0356555 Al 12 / 2015 Pennanen U .S . Appl. No. 15 /684,721 — Notice of Allowanec and Fees Due,
2016 /0027229 Al 1/ 2016 Spanos et al. Oct. 6 , 2017
2016 / 0085955 A1 3 / 2016 Lerner Juels , A , et al., “ PORs: Proofs of Retrievability for Large Files," In
2016/ 0110292 Al * 4/ 2016 Choi G06F 12/ 0866 ACM Conference on Computer and Communications Security, CCS
711/ 103 2007, pp . 584 -597 . ACM .
2016 /0125403 A15 / 2016 Hu et al. Zheng , R , et al., “ Fair and Dynamic Proofs of Retrievability ,” In
2016 /0162897 A1 6 / 2016 Feeney Proceedings of the first ACM Conference on Data and Application
2016 / 0212109 A1 7 / 2016 Hird Security and Privacy, CODASPY, 2011, New York , NY, USA.
2016 / 0218879 A1 7 / 2016 Ferrin ACM , pp . 237 -248 .
2016 /0292396 AL 10 /2016 Akerwall
2016 /0321654 AL 11 /2016 Lesavich et al. Puddu , Ivan , et al., " uchain : How to Forget without Hard Forks,”
2016/ 0328424 A1 * 11 / 2016 Borley G06F 17/30911 https://www .airbnb .com and https:// gillab . inf.ethz .ch / puddui/fabric ,
2016 /0344737 AL 11/ 2016 Anton et al. dated Feb . 10 , 2017 , (21p ).
2016 /0358165 A1 12/2016 Maxwell Zyskind , Guy, et al., “ Enigma: Decentralized Computation Plat
2017 /0031676 AL 2 / 2017 Cecchetti et al. form with Guaranteed Privacy ,” guyz @ mit .edu , oznathan @ gmail.
2017/0034217 AL 2/ 2017 Anton et al. com , pentland @ mit .edu , Jun. 6 , 2015 , ( 14p ).
2017/ 0048217 A1 * 2 / 2017 Biggs .............. H04L 9 /0833 Office Action corresponding to U . S . Appl. No. 15 /726 , 023 , dated
2017 /0109735 Al 4/ 2017 Sheng et al . Jan . 9 , 2018, ( 12p ).
2017 /0163733 A1 6 / 2017 Grefen et al.
2017 /0213209 Al 7/ 2017 Dillenberger * cited by examiner
U . S . Patent May 8 , 2018 Sheet 1 of 15 | US 9, 967. 088 B2
100
???
102 ? 104\ 106 .
( BlockID ) ( 124.BlockD 125 . BlackID Blocked BlockiD
num )
rammentreamwan
( C80) ( ICB1 )
APurrenentHear
CB2) IC ( Bin- 1 )
A.
12 /Data00 ( Data 10 Data 20 Data 30 Data no
Data 1 Data 31 Data nt
Data12 Data 12
80 1 B3
150
02 4,
DEEPRO - 0 |152
Bn
Figure 1
atent May 8 , 2018 Sheet 2 of 15 US 9 ,967 ,088 B2
CO?1:28) - 0
248
26 - ?02 20 -
BI Am E1
B2 IC{B2} = {C{B2'}
204 -
?? . ** * * * ** **
250
24 -
O - O .G 20-
O? . . 208
CB2} = { C { {'}
- * -* * * * * * * * * * * * * * * * * * * * *
Figure 2
atent May 8 , 2018 Sheet 3 of 15 US 9,967,088 B2
????????????????????????
PBlockchainLrocegsincg 342
316 320 322 323 324 326
318
.
Proce(
s
)s or BMemory Mleotcakcdhatian Flags BDlocakcthain PFairaemletdesr IUntserfeacre GUI
00 00
V
)
328
312 314 Figure
3
MCPai3nroacguweimet4rnyt
CIonmtuenrifcatcieosn RXuitryEtheBT
/
CircTX WLAN
/rnet
LTE
3G
4G
/
GigE
SLyosgtiecm Intnerpfaucets
sereins remoniecomo
encanto
con
e
con
carnets
them
were
womencome
simone
sono
come
more
ancient
come
one
w
300
O00
U . S . Patent
man
brevet
o
f
May 8 , 2018
Rewrite MLanoagemienct 441 Blockchain PLrocegsincg 442
416 420 422 423 424
424 480 421
--- --- Sheet 4 of 15 US 9,967,088 B2
-
Proce(
s)ssor BMemory Mleotcakcdhatian Flags BDlocakcthain PMroetmecotredy SecKeyrets
tem como
inmod a una .. .. .. .
412 4281 418
Fig4ure
CIonmtuenrifcatcieosn RXuitryEtheWLAN
/
CircTX /rnet
BT
4G
3G
LTE
/
GigE
SLyosgtiecm
MCPai4nroacguw3eimter4nyt
Interpfaucets
IUntserfeacre GUI
00 00 wwwwwwwww
somrestaurantedermemes
word
om
te
manier
waar
mense
mensen
ww
-
commosttheareseriesmotionmenemi
]
avrom
waren
were
more
and
more
C
4002
0 0 0 0
U . S . Patent May 8 , 2018 Sheet 5 of 15 US 9,967,088 B2
441
Access blockchain . 502
Key
secret in
memory ?
Yes 506 Key
secret No lindicate that non -tamper
accessible via evident editing is not available.
interface
412 ?
Yes
in
n
Prompt for rewrites. 510 win
in
n
i
Automatically obtain rewrites. 511
www
Call rewrite logic to perform
rewrites .
Figure 5
Patent May 8 , 2018 Sheet 6 of 15 US 9,967,088 B2
0 -0 -0 -0 - 0
9 BRS
60
Blockchain DB
berdachun
Access a blockchain .
Leg50 Access a key secret for the 604
integrity code of the blockchain .
BRS
0000 -0 . ... .
Receive a rewrite command to one
perform on the blockchain .
Trusted Party
Process the key secret, the
0 -0 -000
replacementdata , and the
originaldata to determine
additional data .
608 0 -0 -00 - 0
T
0000 - 0 BRS
w
Delete one or more prior or 609
subsequent blocks .
BRS Additional data
Generate the additional data . 610
BRS
Additional data
Combine the replacement data 40
and the additional data .
BRS
Write the replacement data
combined with the additional
0-0-0 -0 - 0
data in place of the original 614
data .
BRS Blockchain DB
Figure 6
U . S . Patent May 8 , 2018 Sheet 7 of 15 US 9 ,967,088 B2
700
H (X) * H (X )
- Figure 7A
796
CH (X)= CH(X")
0860 780-6
ii i i i i i i i i i i i ii i i i i i i i i i i i i i i i ii i i i i i i i i i
762 762
-@ --O . @ - @ --
760
798
Si
- @ - @ --
0- 0- 0 iiiiiiiii 164
00
Figure 7B
786
U . S . Patent May 8 , 2018 Sheet 8 of 15 US 9,967,088 B2
800
s' = H ( ctr , Gís, x,1)) 803 s" = Héctr", G (s', *', 7) . 803 , s." - Héctr", G {s”,X ",{"))
HashPrev (s) 802 HashPrev ( s') 802 HashPrev (s") 802
Payload (x ) 804 Payload (x ) 804 Payload (X") 804
Counter (ctr ) 806 Counter (ctr") 806 Counter (ctr") 806
Randoniness (0 808 Randonness.(6 .808 Randomness (1 ) 808
832 820 - 834
$ s' = H (ctr, Gís, x , 0)) 803 " = Héctr', G (s', *x *, *r')) - 803. S'' = H (ctr" , G (s", X", x"))
HashPrev (s ) 802 HashPrev (s') 802 HashPrev (s") 802
Payload (x ) 804 Payload (*x") 804 Payload (x") 804
Counter (ctr ) 806 Counter (ctr") 806 Counter(ctr") 806
Randomness (1) 808. Randomness ( 7)808 Randomness(0) 808
832 822 834
Figure 8
U . S . Patent May 8 , 2018 Sheet 9 of 15 US 9,967,088 B2
00:00 . 0
902
906
B1 B3
904
903
952
0 .0 .0 .0 . 0
956
904
Figure 9
U . S . Patent May 8 , 2018 Sheet 10 of 15 US 9, 967,088 B2
{{ {
{{{ 2.
" ?? ??? ??? ??? ??? ??? ??? ???? ? ??? ?? ?? ?? ??? ??? ??? ?? ?? ?? ??? ?? ???? ?? ?? ?? ?? ?? ?? ???? ??? ??? ?? ?? ?? ?? ?? ?? ??
?? ?? ??????????????????????????????????????????????????????? ??????????????????????????????????????????????????????????? ??????????????????????????????????????????????????????????? ???????????????????????????????????????????????????????????
???
? ? ?? ?
????
????
1006 ???
?????
????? ??? ? ?
?????
??
??? ???
????
2012 1022 1032 1042 ???
???
1004 ??? ?????
?
?
-- - - -- - - -- - - -- -- -- - - -- -- -- -- -- - - -- - - -- -- -- -- - - -- - - - - - -- -- - - -- - - -- - - -- - -- - - -- -- -- -- --
?????
????
??
??? ???
108 ????
? ??
?????
???
?? ???
?????
1014 1024 1234 10444 ????
?????
?? ?? ?
??? ??
?? ?? ? ?? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?? ? ? ?? ?? ?? ?? ?? ?? ??? ? ?? ?? ??? ?? ?? ?? ?? ?? ?? . ?
1010 1020 1030 1040
Figure 10
atent May 8 , 2018 Sheet 11 of 15 US 9 , 967,088 B2
Rewrite MLanoagemienct 441
eenmetmotoren
center
-
420 480
416 420
416
1 50
Ap end
Proc(
s
)es or PMemory rMoetmecotredy SecKeyret 010-030 4
bordo
com
swinewoiim
wa
wamesanciensarvest
UPntarusteyd Ap end Fig11ure
BRS
401
Ang
coo6
0000
-
Terminal
1110 metara UPntarusteyd
Terminal
TPraursteyd 1101 -
300
m
bongomooolale BPS
Concerto
con UPntarusteyd
O
1102
/
"
os
-
como
Rewrite
00
- Ap end
10
0
-000
U . S . Patent May 8 , 2018 Sheet 12 of 15 US 9 ,967,088 B2
RewriteMLanoagemienct 441
BPS com anime
1299 commemon anno como Menosamo
processmore
>war -
-
1200
Rewrite 416 420 dorotleteratur480
minini1150
CS1oem2cbKeyir6ne2td n
000000
-
03
orm
)
.
o
N
1299
1260
- 1 10
1260
_
1260
)es or
Proc(
s
Memory Pr
M e
o te
m o
ctre y
d SecKeyret
wowotworow
1299 tommom .
com - m
4
1 10
wwwcomescom - min.com um
Ap end Fig12ure
Terminal
"
0000
-
0Ap end 400
BRS
i
10
iTerminal nd-0000o
w
UPntarusteyd
Terminal 300
1172
TPrausrteyd 1 01 BPS 102 UnPtarurstedy
0000
-
)
Rewrite Ap end
1200 0
-000 -
000
atent May 8 , 2018 Sheet 13 of 15 US 9 , 967,088 B2
ANAN Record
1308 Party www www mama mmm aman www www www amma man
1399
Transaction w w 1399
1310
1308 Party
wwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
Ap end mw
ma
an
um
am
.
www
mom
nan
men
mow
man
ano
1310
1399
1304 Service Provider .
ww
1310
Fig13ure
BRS 1310 ann
now
una
man
www
.
same
we
an
mano
400
Deletion 1350
*
*
33
0
.
0
. 1310
*
*
1399
um
an
mana
.
anno
mano
ane
man
ana
con
una
1310
1399
130 now
man
mann
1302 wwwwwwwwwwwwwwwwwww ww ww www www Aww
U . S . Patent May 8, 2018 Sheet 14 of 15 . US 9 ,967, 088 B2
-
349
-
-
--
--
-
-
---
-
--
--
-
149 0
? +
+
1402 (4
Internet
300
BPS
1404
1404
RecANord Data Fig14ure
Ap ed
Enterprise 1410 1404
-
:
-
:
-
:
-
:
-
:
:
-
.
BRS
-
40
40
3404 seseseseses
- - -- -- --
-
-
Truncate -
:
144 -
-
3404
-
:
-
:
-
:
-
:
:
-
-
*
*
1434
3404 ???
*
*
*
{
408 - - - - - ---
400
*
1498 AMA * * * * *
U . S . Patent May 8 , 2018 Sheet 15 of 15 US 9 , 967,088 B2
W
15 2 one
1544 -
1544 154
-
1546
-
- 1538
re
-
-
400
1504 TPrausrteyd Fig15ure
00
-
0
- .
0
-
0
-
0
-
a 0
6
-
2
*
.
.
BRS
1542 1542 1542
-
-
TPrausrteyd
-
1541 1541
1532
.
.
1554
www
1500
15527
1500 1530 1550
1979
1504
US 9, 967,088 B2
REWRITABLE BLOCKCHAIN FIG . 13 shows an example blockchain record mainte
nance scenario .
PRIORITY CLAIM FIG . 14 shows an example internet of things rewriteable
blockchain scenario .
This application claimspriority to European Patent Appli- 5 FIG . 15 shows example blockchain loops.
cation Serial No. 17425018 . 3 , filed 17 Feb . 2017, and titled
Rewritable Blockchain , which is incorporated by reference DETAILED DESCRIPTION
in its entirety . This application also claims priority to Euro
pean Patent Application Serial No. 16425086 .2, filed 11 A blockchain may include a series of data blocks , the
Aug. 2016 , and titled Rewritable Blockchain . This applica 10 blocks including a code, such as a cryptographic hash or
tion also claims priority to European Patent Application of previous, which
checksum may be coding - consistent with the content
blocks in the series. In some cases, determining
Serial No. 16425044 . 1, filed 23 May 2016 , and titled multiple different sets of blocks that produce the same
Rewritable Blockchain . integrity code may be insoluble , prohibitively computation
CROSS -REFERENCE TO RELATED 15 ally complex , or otherwise effort intensive enough to frus
APPLICATIONS trate attempts to tamper with the contents of the blockchain
while maintaining the self-consistence of the integrity codes .
However, in some implementations a trusted party may have
This application is related to U .S . patent application Ser . access to a key secret, or portion of a key secret, such that
No . 15 /596 , 899, filed herewith on 16 May 2017, titled 20 the party , acting alone or with those in possession of the
Distributed Key Secret for Rewritable Blockchain , which is other portions of the key secret, may edit the blockchain
incorporated by reference in its entirety . This application is contents without leaving indication of tampering .
related to U . S . patent application Ser. No. 15 /596 ,922 , filed In various systemsmultiple parties may use a blockchain
herewith on 16 May 2017 , titled Multiple-Link Blockchain , based file or ledger to maintain a tamper-evident record of
which is incorporated by reference in its entirety . This 25 events , transactions, or other updates. In some cases , a
application is related to U .S . patent application Ser. No. blockchain may register tampering after a change made to
15 /596 , 932, filed herewith on 16 May 2017 , titled Rewrit- the blockchain by an untrusted party , for example a party not
able Blockchain , which is incorporated by reference in its in possession of the key secret. Thus, the parties may
entirety . individually verify that updates by other parties are valid and
30 coding -consistent with the previous data blocks of the
TECHNICAL FIELD blockchain . The self- consistence of the integrity codes
allows the updates to the blockchain to be verified even if the
This disclosure relates to data verification , validation , and party lacks an archived version of the blockchain to use as
re-writing in complex real-world systems. a reference . When a rewrite to one or more data blocks in a
35 blockchain does not introduce coding -inconsistency among
BACKGROUND the integrity outputs and data block contents of the blocks in
the blockchain , the rewrite may be characterized as preserv
Rapid advances in electronics and communication tech - ing the validity of the blockchain .
nologies , driven by immense customer demand , have blockchain may be secured by an integrity code. An
resulted in the widespread adoption of electronic transac - 40 integrity code may produce a particular integrity output
tions and record keeping. As one example , e -currencies, when particular data is provided as input to the integrity
such as Bitcoin , have displaced paper currencies in millions code. In some cases , when data different than the particular
of transactions per year. Improvements in the verification data is provided to the integrity code as input, the integrity
and recordation of such electronic transactions will continue code may produce a different integrity output. In an example
to increase the features and options available to operators 45 scenario an integrity output from the integrity code gener
engaging in electronic transactions. ated from particular input data from a data block is stored
and the data block is later changed . If the changed data is
BRIEF DESCRIPTION OF THE DRAWINGS provided to the integrity code as input, the integrity code
may produce an integrity output that is different or otherwise
FIG . 1 shows two example views of a blockchain . 50 coding -inconsistent with the stored integrity output. There
FIG . 2 shows two example rewrites to the example fore , the change may be detected in this example scenario .
blockchain of FIG . 1 . A blockchain may include a series of blocks where each
FIG . 3 shows an example blockchain processing system . subsequent block in the series holds the integrity output for
FIG . 4 shows an example blockchain rewriting system . a previous block . The series may form a chain of blocks in
FIG . 5 shows example rewrite management logic . 55 which each subsequent block holds an integrity output
FIG . 6 shows example rewrite logic . generated from the data present in the immediately prior
FIG . 7A shows two example collision searches . block . Accordingly , if a block is changed , a coding- incon
FIG . 7B shows an example rewrite to a blockchain using sistency with the integrity output stored in a subsequent
a collision . block may be detected . Since the integrity outputs are part
FIG . 8 shows an example blockchain portion paired with 60 of the stored data in the blocks, changes to the integrity
an example updated blockchain portion . outputs themselves may also be detected through coding
FIG . 9 shows an example dual-link blockchain portion . inconsistencies . This self-consistency of the integrity code
FIG . 10 shows an example hybrid blockchain . may be used to secure a blockchain with respect to covert
FIG . 11 shows an example rewritable blockchain sce tampering.
nario . 65 When secured by an integrity code, a tamper-evident
FIG . 12 shows an example distributed key secret block - change may include virtually any change for which a
chain rewrite scenario . coding- inconsistency between the integrity outputs of the
US 9 ,967,088 B2
integrity code for a blockchain and the data within the to jettison a blockchain due to inappropriate content, a
blockchain can be detected . For example, the data in a block trusted party may rewrite the existing blockchain . Accord
of the blockchain may be hashed , run through a checksum , ingly, blockchain rewrite dramatically improves system effi
or have another integrity code applied . If the data in the ciency, compared to recreating a new blockchain . Block
block is later found to conflict with the integrity output of the 5 chain rewrite may also reduce the probability of a malicious
hash , checksum , or other integrity code , the change may be party using a defunct blockchain , which may have been
identified as tamper - evident. A conflict may occur when the discarded due to inappropriate content, to spoof a system by
data currently in a block does not produce an identical or notifying the system that it did not receive a prior notifica
equivalent integrity output to the earlier obtained integrity tion of the blockchain discard . Accordingly , the rewritable
output when the integrity code is applied to the data cur - 10 blockchain may have the technical effect of improved data
rently in the block . When a change is made to a block and security and tamper -resistance . In other words , the tech
no coding - inconsistency with the previously stored integrity niques and architectures discussed herein comprise concrete ,
outputs of the integrity code can be detected afterward , that real-world applications of and improvements to existing
change may be non - tamper- evident. In some cases, a non technologies in the marketplace .
tamper -evident rewrite may be implemented by substituting 15 Further, the techniques and architectures , including those
a first block with a second block with different data content for rewritable blockchains, distributed key secrets, dual- link
that produces the same (or an equivalent) integrity output. blockchains, loops , and other techniques and architectures
In some cases , after entry , some blocks in a blockchain discussed require one to proceed contrary to accepted wis
may include information that is no longer appropriate for dom . In particular, conventional approaches to blockchain
inclusion in the blockchain . For example , blocks may expire 20 distributed databases require immutability of the blockchain
after time or after a determined number of subsequent as a foundational feature . Expressed another way , immuta
entries , private information may be included in the blocks, bility has been repeatedly explained in prior work as an
inaccurate entries may be included in the blocks, informa- essential feature in establishing the technological value of a
tion prejudicial to one or more of the parties using the blockchain . Immutability in blockchains has been incor
blockchain may be included in the blocks, incomplete infor - 25 rectly viewed and dictated as the required way to ensure that
mation may be included, or other inappropriate information parties using a blockchain trust the validity of the data
may be included . Accordingly , a trusted party , for example contained in the blockchain . Accordingly , the techniques
a neutral third party , a governing party , or a group of architectures described here that add rewritability to a block
individually untrusted parties, may rewrite , remove , or chain proceed contrary to accepted wisdom . The present
supplement data included in the blocks in a non - tamper - 30 techniques and architectures proceed contrary to accepted
evident fashion . The systems and techniques described wisdom by introducing rewritability , while still maintaining
below implement technical solutions for rewriting blocks in high security , and therefore the high technological value of
the blockchain to allow trusted parties to redact information the blockchain . As such , despite the significant departures of
from the blockchain , without causing the blockchain to fail the present techniques and architectures from prior teach
for its intended purpose . For example , the parties may use a 35 ings , the present techniques and architectures provide high
modified blockchain as if it was the earlier, and unmodified , levels of trust in the blockchain despite its mutability .
blockchain . FIG . 1 shows example two example views 100 , 150 of a
Blockchain rewrites may be used to perform low level blockchain where each subsequent block includes an integ
( e.g ., from a hardware architecture standpoint) operations rity code (e. g ., a hash , chameleon hash , or other integrity
such as memory rewrites, deletions, and additions. Accord - 40 code ) using the previous block as an input . For instance ,
ingly , the techniques and architectures may improve the block B1 104 includes a integrity output, IC (BO ), in this
operation of the underlying hardware of a computer system integrity output field 124 determined from content of pre
because the system may utilize blockchain protocols for vious block BO 102 serving as input to the integrity code .
storing data for which verifiability is implemented . For The content of B0 102 used in determination of IC (BO )may
example , operating system software for secure systemsmay 45 include any or all of the fields within B0 , such as Data 00
be stored in blockchain payloads to protect the data from 121 , the ?null ] integrity output field 122 , or the BlockID 123 .
manipulation by malware, unauthorized parties, unauthor - The data fields (e .g., Data 00 121, Data 10 131, and other
ized devices, or other unintended / unauthorized alterations. data fields ) of the blocks may be used to store any type of
Additionally or alternatively, blocks may represent a data . For example , the blockchain data fields may hold
smallest increment of data that may be distributed when an 50 account data , personal data , transaction data , currency val
update is made . For example , one or more updated block ues , contract terms, documents , version data , links, pointers ,
may be sent separately from the entire blockchain during an archival data, other data , or any combination thereof.
update . However , in some cases, at least the entire block - The fields in a block that are not used to determine the
chain may be distributed with individual valid updates . For integrity output in a subsequent block may not necessarily
example , when a new secured transaction is performed and 55 be secured by the blockchain . For example , these fields may
added to a ledger secured via a blockchain , the entire be altered without generating coding -inconsistencies among
blockchain (e. g., full transaction history ) may be re -distrib - the blocks. Further, if any integrity output field is not used
uted with the updated transaction added . Blockchain rewrite in the determination of the integrity output for a subsequent
systems, such as exemplary implementations described block in the chain , the blockchain may not necessarily
herein , that allow truncation , right- sizing, extension , or other 60 ensure the coding - consistency among blocks discussed
blockchain size adjustments may improve the operation the above because the unsecured integrity output may be
underlying hardware by allowing adjustment of the data changed without necessarily generating evidence of tamper.
overhead consumed during blockchain update and distribu - Accordingly, in various implementations, the integrity out
tion . put field and at least a secured portion of a data payload of
In addition , the ability of a trusted party to rewrite a 65 a block are used in determination of the integrity output for
blockchain may improve tamper - resistance by providing an a subsequent block ( e . g ., the next block ) in the blockchain .
established rewrite solution . Accordingly , rather than having Similarly , IC (B1) in the integrity output field 125 of block
US 9 ,967,088 B2
B2 106 may be based on fields within Block B1 104 , secret. For instance, blockchains A , B , and C may all allow
including, for example , any of the integrity output field 124 , rewrite with master key secret MK . Further, blockchain A
the data fields, or the BlockID field of block B1 104. In the may have an individual rewrite key secret A1,blockchain B
example, the integrity code, IC , may be a chameleon hash , may have an individual rewrite key secret B1, and block
as discussed below . 5 chain C may have an individual rewrite key secret C1. In this
The blockchain blocks may be locked 152 to one another example, a processing system may rewrite blockchain B
via the integrity codes . In one sense , the blocks are locked using MK or B1, but not with A1 or C1.
to one another because the integrity code output fields in Further, in some implementations , a granting key secret
each of the blocks are based on the content in the previous may be used to issue key secrets to trusted parties . For
block at the time the integrity output was generated ( e . g ., 10 example , encrypted cache EC may include additional key
when the block was added to the chain ). Accordingly , if a secrets for blockchains A , B , and C (e . g ., key secrets
previous block changes after a current block is added , the A2 . . . AN , Bn . . . Bn , C2 . . . Cn ). A trusted party in
change will be tamper- evident because the change will be possession of a granting key secret GK to decrypt EC and
coding-inconsistent with the integrity output stored in the allow issuance of the stored keys to new trusted parties . In
current block . Hence , the content of the previous block is 15 some cases, a master key secret may double as a granting
“ locked - in ” once a current block with a stored integrity key secret. For example, processing systems may use master
output based on the previous block is added to the block - key secret to generate block content for rewriting, and the
chain . In the example blockchain in FIG . 1, the content of B1 master key secret may serve as a decryption key for an
104 may be locked once B2 106 , which contains IC (B1) in encrypted cache of key secrets.
its integrity output field , is added to the blockchain . As a 20 In addition, distributed key schemes discussed below ,
result, the content of B0 102 which was locked by B1 104 may be applied for granting key secrets and master key
is further secured by B2 106 because B2 106 prevents B1 secrets. In some systems, trusted parties may individually
104 from being changed in a non -tamper-evident manner. perform rewrites to the blockchain . However, the same
In an example scenario , the rewritable blockchain may be trusted parties may combine, using any of the distributed key
implemented using chameleon hash as the integrity code, as 25 schemes discussed below , their keys to gain the authority
discussed below . However, virtually any code may be used associated with a granting key or master key . For example ,
for which tampering is self- evident for parties not in pos - three individually trusted parties may each perform rewrites
session of a key secret allowing editing. without the assent of the other parties. However, the three
FIG . 2 shows two example rewrites 200 , 250 to the parties may be forced to combine their key secrets, e .g .,
example blockchain of FIG . 1. In the first example 200 , the 30 coordinate , to gain granting privileges and grant a fourth
block B2 202 is replaced with a block B2 204 with new party its own key secret.
content The new block B2' 204 includes content generated in various implementations, increased privileges may be
using the key secret such that the integrity output generated obtained through coordination of a specified threshold num
when using block B2' 204 as input is the same as that using ber of parties , by specific pre -determined parties, by parties
original block B2 202 as input. For example , IC (B2)= IC 35 of a given class, by all parties, or by another defined group
( B2'). of parties. The distributed key secret scheme may determine
In the second example 250 , the block B2 202 is removed the participation level rules for coordination .
Block B1 206 from the original chain may be replaced with In various implementations, keys secrets may be assigned
block B1' 208 to be coding -consistent with the integrity to operators using key secret assignment schemes . The key
output contained in block B3 210 . For example , the block 40 secret assignment schemesmay include assignment schemes
B1' 208 may include content generated using the key secret based on operator identity , association , priority , or other
such that the updated block B1' 208 may appear to be the basis .
correct block (and is a correct block in terms of the block - In some cases, the blockchain is flagged to indicate that it
chain integrity code ) to precede subsequent block B3 210 . is subject to editing. The flags or fields indicating that the
That is, B1 is replaced after deletion of block B2 so that B1' 45 blockchain is rewritable may identify the trusted parties with
can immediately proceed B3 without any violation of the authority to rewrite the blockchain . This may assist parties
blockchain integrity code . with an interest in rewriting the blockchain in identifying the
In various implementations, different rewritable block - trusted parties able to perform the rewriting. For example, a
chains may have different key secrets . Thus , a trusted party blockchain may be accompanied by metadata describing the
able to rewrite a given blockchain may not necessarily be 50 purpose, original, operational parameter, or other informa
able to act as a trusted party and rewrite a second , different, tion on the blockchain . Flags for rewriting may be incorpo
blockchain . Using different key secrets for different block rated within the metadata . However, when such metadata is
chains may prevent multiple blockchains from being com - included outside of the blockchain it may be changed
promised simultaneously through the disclosure of a single without evidence of tampering . Allowing the metadata to be
key secret. However, multiple blockchains using the same 55 changed freely may reduce computing resources needed to
“ master” key secret may be generated by blockchain sys - perform an edit and increase the number of parties that may
tems ( e . g ., a key secretmay be a master key secret if it may correct a metadata error. In other systems, processing sys
be used with multiple different blockchain systems) . Using tems may write such metadata into the blocks of the block
a common secret among multiple blockchains may allow for chain itself, for example , into dedicated fields or the data
more streamlined administration than using different key 60 payload of blocks. Writing the metadata to the blockchain
secrets for the different blockchains . itself may prevent unauthorized parties from altering block
Additionally or alternatively , a blockchain may have chain metadata (e.g., for potentially malicious purposes).
multiple different key secrets that allow non - tamper -evident In some implementations, the existence of the trusted
editing. In an example scenario , a master key secret may be parties may be kept secret from the untrusted parties or a
used with multiple blockchains each with individual key 65 portion of the trusted parties. In some cases, the integrity
secrets that do not necessarily allow non - tamper -evident code may not necessarily provide an indication by inspec
editing on the other blockchains covered by themaster key tion of its operation that trusted parties may edit entries in
US 9 ,967,088 B2
the blockchain . That is, the algorithm that generates the blockchain -based verifications to an operator of the BPS
integrity code does not itself easily reveal that it supports 300 . The user interface 318 may also render GUIs with tools
blockchain rewrite . Keeping the existence of the trusted to support block additions to blockchains.
parties in confidence may discourage parties from attempt. FIG . 4 shows an example blockchain rewriting system
ing to steal or otherwise acquire the trusted party 's key 5 (BRS ) 400 . The BRS 400 may be used by, for example , a
secret. Further, parties may have increased confidence in the trusted party performing redaction , revision , or supplemen
blockchain if the parties assume that the blockchain cannot tation on a blockchain . For example, a supplementation may
be edited by another party without the tampering being include adding content to an existing block . Even in block
evident. chains that do not support non -tamper - evident rewrites, an
In some implementations , entities with knowledge of a 10 authorized operator may add a new block , e . g ., a new
key secretmay make alterations to the blockchain . This key transaction record , to the blockchain . However, alterations
secret could be in the possession , in whole or in part, of to existing blocks ( including additions) may generate evi
operators , a centralized auditor, or other parties. Addition - dence of tamper unless performed by a trusted party in
ally or alternatively , shares ( e.g ., portions ) of the key could possession of a key secret. The BRS 400 may include system
be distributed among several individually untrusted parties. 15 logic 414 to support verifications, updates, and rewrites to
The integrity code may be a virtual padlock on the link blockchains. The system logic 414 may include processors
connecting two blocks . 416 ,memory 420 , and / or other circuitry, which may be used
The key secret to open the virtual padlock can be managed to implement the blockchain processing logic 442 and the
according to the requirements of specific applications. For rewrite management logic (RML ) 441.
example , in a business negotiation ( or government treaty 20 The memory 420 may be used to store blockchain meta
negotiations ) a key secret allowing alteration of proposed data 422 and/ or blockchain data 424 used in blockchain
contract (treaty ) terms may be held by neutral third party. rewrites and block additions. The memory 420 may further
Additionally or alternatively, equal portions ( e.g ., halves , store key secrets 421 , such as an encryption key value ,
thirds) of the key secret may be held by each party in the trapdoor information , or other secret value , that may allow
negotiation , such that terms may be altered with the consent 25 non - tamper - evident rewriting of a blockchain . In some
of all parties or a defined plurality of the parties. In collab - cases, the key secrets 421 may be stored in protected
orative software design implementations , key secrets may be memory 480 , such as encrypted files or data drives, physi
distributed in portions to stakeholders to enforce consensus cally secured drives, drives coupled to triggers for anti- theft
before allowing alteration to certain software code . Below , countermeasures, or self -deleting drives to prevent acciden
example key secret distribution schemes are discussed , 30 tal or surreptitious disclosure of the stored key secrets 421.
including centralized and distributed schemes . However, The memory storing key secrets may include trusted
other schemes are possible . memory or other memory in possession of or controlled ,
FIG . 3 shows an example blockchain processing system either directly or indirectly , by a trusted party .
(BPS ) 300 . The BPS 300 may include system logic 314 to The memory 420 may further include applications and
support verifications of and rewrites to blockchains. The 35 structures , for example , coded objects , templates , or one or
system logic 314 may include processors 316 , memory 320 , more other data structures to support verification of updates
and/ or other circuitry , which may be used to implement the to blockchains and detect evidence of tampering. The
blockchain processing logic 342 . The memory 320 may be memory may further include flags 423 which may indicate
used to store blockchain metadata 322 and/ or blockchain whether particular blockchains can be edited and the iden
data 324 used in blockchain rewrites and block additions. 40 tities of the trusted parties . The BRS 400 may also include
The memory may further include program instructions one or more communication interfaces 412 , which may
that implement blockchain processing, and one or more support wireless, e . g . Bluetooth , Wi-Fi, WLAN , cellular
supporting data structures, for example , coded objects , tem ( 3G , 4G , LTE / A ), and / or wired , ethernet, Gigabit ethernet,
plates, or other data structures to support verification of optical networking protocols. The communication interface
updates to blockchains and detect evidence of tampering . 45 412 may support communication with other parties making
The memory may further include flags 323 which may updates to blockchains or performing blockchain transfers .
indicate whether particular blockchains can be edited . In an Additionally or alternatively, the communication interface
example , the flags 323 , may be implemented using a bit 412 may support secure information exchanges , such as
within specific fields within a blockchain or blockchain secure socket layer (SSL ) or public - key encryption -based
metadata to indicate editability . Further, the memory 320 50 protocols for sending and receiving key secrets between
may include parameter fields 326 that may include the trusted parties . Further, the secure protocols may be used to
identities of contact information of the trusted parties, for combine key secrets among individually untrusted parties
example , names, addresses , phone, email, or other contact each having some portion of a key secret, as discussed
information . below . The BRS 400 may include power management
The BPS 300 may also include one or more communica - 55 circuitry 434 and one or more input interfaces 428 .
tion interfaces 312 , which may support wireless , e.g . Blu The BRS 400 may also include a user interface 418 that
etooth , Wi-Fi, wireless local area network (WLAN ), cellular may include man -machine interfaces and / or graphical user
(third generation (3G ), fourth generation (4G ), Long Term interfaces (GUI). The GUImay be used to present data from
Evolution Advanced (LTE / A )), and /or wired , ethernet, Giga - blockchain -based verifications to an operator of the BRS
bit ethernet, optical networking protocols . The communica - 60 400 . Additionally or alternatively, the user interface 418 may
tion interface 312 may support communication with other be used to present blockchain rewriting tools to the operator.
parties making updates to blockchains or performing block In some cases, the user interface 418 may include a GUI
chain transfers. The BPS 300 may include power manage - with tools to facilitate blockchain rewrites and deletions .
ment circuitry 334 and one ormore input interfaces 328 . The T he GUI tools for rewriting may include " what you see is
BPS 300 may also include a user interface 318 that may 65 what you get” tools that allow operators to manipulate the
include man -machine interfaces and /or graphical user inter - content of the blockchain , e . g ., using word -processor -like
faces (GUI). The GUImay be used to present data from tools , web - editing - like tools, file-browsing -like tools, or any
US 9, 967, 088 B2
10
combination thereof. Additionally or alternatively, the user The blockchain may include one or more data blocks that
interface 418 may include command - line editing tools. The are secured by an integrity code. For example, a rewrite
tools , whether text or graphic based , may allow operators to protected cryptographic hash function , such as a hash func
access key secrets and perform edits on blockchains for tion without a key secret for allowing non -tamper- evident
which they are authorized . In some cases, the tools may deny 5 rewrites, a chameleon hash , cyclic redundancy checks
writing capabilities to operators lacking the proper key (CRCs), checksums, or other integrity codes may be used to
secret for the blockchain that they are attempting to edit . secure the data blocks within the blockchain . In some
implementations, the individual data blocks may be secured
However, in some implementations, the tools may allow
such unauthorized editing because it will result in tamper by a particular integrity output that is coding -consistent with
evident rewrite that will invalidate the unauthorized edits toto 10 output
the data content of the block . For example, an integrity
may be coding - consistent with the content of block
the blockchain . when applying the integrity code to the contents of the block
FIG . 5 shows example RML 441 , which may be imple that produces that integrity output. When an integrity output
mented in or with circuitry . The RML 441 may handle is coding -consistent with the data that it secures, the data
management of key secrets and implementation or of rewrite
rewrite 15 may be deemed valid . As discussed above , that particular
commands. For example, the RML 441 may determine integrity output may be placed within a neighboring block to
availability of key secrets for particular blockchains and prevent or frustrate attempts to rewrite the data content in a
pass those key secrets to the rewrite logic 600 (discussed non - tamper-evident fashion . Further, as discussed below
below ) for execution of the rewrites . The RML 441 may also with respect to hybrid blockchains , some blockchains may
handle reception of rewrite commands or reception of com - 20 include portions ( e.g ., of individual blocks or groups of
mands for the automation ofblockchain rewrites. Once , the blocks ) that may allow for non - tamper - evident rewrites
RML 441 identifies the change requested and the blockchain alongside portions that may not necessarily allow for non
involved , the RML 441 may access the blockchain (502 ). tamper - evident rewrites by trusted parties.
The RML 441 may determine whether the memory 420 of The rewrite logic 600 may access a key secret, such as a
the BRS 400 holds a key secret allowing rewrites to the 25 cryptographic key or trapdoor information , that is paired to
accessed blockchain (504 ). If the memory 420 does not store the integrity code of the blockchain (604). The key secret
the key secret, the RML 441 may determine whether the key may include data that allows a system , e. g ., the BRS 400, to
secret is accessible via secure communication or via secure compute collisions, e . g ., two different data blocks that
combination of portions of the key secret using the com - produce the same integrity output for the integrity code.
munication interface 412 (506 ). For example , the portions 30 Using the computed collisions , a device may rewrite the
may include portions of a key secret held by parties that blockchain without the rewritten blocks being coding - incon
individually are untrusted , but as a group, with their portions sistent with the integrity code . For example, an operator may
combined into a fullkey secret, form a trusted party . In some instruct a BRS 400 compute a collision using a key secret
implementations, the key secret or portion thereof may be and rewrite a blockchain .
accessed via a secure communication using communication 35 The rewrite logic 600 may receive a command , e . g ., from
interface 412 , e . g ., to protect against interception of the key the RML 441, to perform a rewrite on the blockchain (606 ).
secret during communication . If the key secret cannot be For example, the command may have been received from an
accessed , the RML 441 may indicate, via the GUI 418 that operator for a trusted party that wishes to replace or delete
non - tamper- evident rewrites to the blockchain are not avail - data ( e. g., content) from a particular block . The operator
able (508 ). If the key secret is accessible , either in memory 40 may indicate , e . g ., in a command issued through a man
or via secure communication , the RML 441 may prompt the machine interface to the BRS 400 , the original data and the
operator for rewrites to the blockchain (510 ). replacement data from input devices of a user interface .
Additionally or alternatively, the RML 441 may automati - Additionally or alternatively, commands to replace data may
cally obtain rewrites (511 ). For example , rewrites may be be received via a network communication interface , for
available from a rewrite queue , embedded within a previ- 45 example from a terminal associated with the trusted party.
ously received command , obtained from other blockchains, The rewrite logic 600 may receive the command to perform
determined from content identified by the systems as mali- the rewrite from the RML 441. Further commands to per
cious code or other inappropriate content, or other rewrites form rewrites may originate from automated sources such as
automatically obtained by the RML 441. The rewrites may those describe above with respect to the RML 441 .
be stored as a command identifying changes to be made to 50 The rewrite logic 600 may process the key secret, the
one or more blocks and, if content is to be added by the replacement data , and the original data to determine addi
change , content to be written to the blocks. The command tional data for which the replacement data and the additional
itself may include the content to be written or , alternatively , data produce the same integrity output for the integrity code
may include a pointer to location of the content. The RML that is produced for the original data (608 ). Accordingly, the
441 may call rewrite logic 600 (see FIG . 6 ) to perform the 55 replacement data and additional data may supplant the
rewrites (512 ). For example , when non - tamper -evident original data without necessarily creating evidence of tam
rewrites are available , the BRL 441 may call rewrite logic pering . In an example scenario , where the integrity code is
600 to execute the rewrites to the block . FIG . 6 shows a chameleon hash , the key secret for the chameleon hash
example rewrite logic 600 , which may be implemented in or allows the rewrite logic 600 to determine collisions for
with circuitry . The rewrite logic 600 may access a block - 60 virtually any original data content. In this example scenario ,
chain (602 ). For example , the rewrite logic 600 may access using the key secret, the rewrite logic 600 may compute
memory where a blockchain is stored . Additionally or alter additional data that produces the same hash output as any
natively, the rewrite logic 600 may access a blockchain via given original data when combined with replacement data
a networking communication interface (e .g ., communication selected by a trusted entity .
interfaces 412 ). In some cases, the rewrite logic 600 may 65 A deletion operation may be executed in the same or
access the blockchain using a secured connection or on similar fashion as other rewrites . However, rather than
secured memory as discussed above . selecting a replacement data and additional data to be
US 9, 967,088 B2
12
coding -consistent with neighboring blocks (e. g ., blocks blockchain may be used in various scenarios. The scenarios ,
immediately subsequent or immediately prior in the block - for example, may include removing improper content from
chain ) . The replacement data and additional data may be a blockchain , providing support for applications that use
selected to be coding -consistent with other blocks further up rewritable storage , complying with governmental regula
or down the blockchain . For example, if the replacement 5 tions such as to the right to be forgotten ” , or other sce
data of the rewritten block collides with the data of a narios.
subsequent block further down the blockchain ( e.g ., non The techniques and architectures, including those for
adjacent blocks) rather than that of the block that is being rewritable blockchains , distributed key secrets, dual- link
replaced , one or more subsequent blocks (e . g ., one or more blockchains , loops, and other techniques and architectures
consecutive blocks in the blockchain immediately following 10 discussed herein may be used in conjunction with various
the rewritten block ) may be removed . Additionally or alter- blockchain consensus techniques . For example , in some
natively, if the integrity output field in the replacement data cases , rewritable blockchains may be used with proof of
includes an integrity output of a block that is two or more work based consensus mechanisms. Accordingly , operators ,
blocks prior to the block being replaced , one ormore blocks e .g ., untrusted operators , may be granted the ability to
prior to the block being replaced may be deleted . Accord - 15 append a block to the rewritable blockchain upon finding a
ingly , when a rewrite includes a deletion , the rewrite logic solution of a pre - defined challenge and showing proof of
600 may delete one or more blocks prior to or subsequent to work for the solution . In some implementations, consensus
the block being rewritten (609 ). mechanisms based on “ practical Byzantine fault tolerance ”
Once the rewrite logic 600 determines the proper addi- may be implemented . Further, some implementations may
tional data , the rewrite logic 600 may generate the additional 20 use " smart contract” type consensus mechanisms where
data (610 ) and combine the additional data with the replace - operators may append blocks upon a showing of compliance
ment data (612). In some implementations, particularly in with the terms or rules of the smart contract . Integrity codes
schemes where the rewritability of the blockchain is kept may be implemented independently of the particular con
confidential, the existence of the additional data may be sensus mechanism used in a blockchain . Accordingly , integ
masked . Thus, a party not in possession of the key secret 25 rity code , include integrity code supporting blockchain
would not be able to immediately identify the rewritable rewrites, may be implemented with virtually any blockchain
blockchain as rewritable simply by noting the existence of consensus mechanism .
the additional data . In some implementations, chameleon hash functions,
For example , the additional data may be placed in a field which may allow for efficient determination of hash colli
within the blocks that contains data with another identified 30 sions when given a key secret, may be used by the system
purpose . For example , the additional data may be appended e .g ., BRS 400 . In some cases, the system may use a
to integrity output fields or to " randomness ” fields as dis - chameleon hash to grant a trusted entity , multiple individu
cussed below with regard to FIG . 8 . ally untrusted parties that togethermakeup a trusted party , or
However, in some cases, declining to expressly identify a other entity the ability to make non - tamper- evident rewrites
specific purpose for the additional data , which would be 35 to a blockchain .
otherwise incomprehensible, may be sufficient to prevent In some implementations, a hash function may remain
untrusted operators from developing a suspicion that the collision resistant even after polynomially many collisions
blockchain that they are using is a rewritable blockchain . have been already found (using the key secret). This prop
In various implementations, the chameleon hash may be erty may be called key - exposure freeness. As discussed
identifiable by both trusted and untrusted parties to facilitate 40 below , a transformation may be used to convert a chameleon
verification of block content. hash function into one additionally satisfying key - exposure
The rewrite logic 600 may then write replacement data freeness .
combined with the additional data in place of the original FIG . 7A shows two example collision searches 700 , 720 .
data (614 ). For example , the rewrite logic 600 may over - For a hash function lacking a key secret (H ), collisions may
write the original data with the combined replacement and 45 be difficult to find . Accordingly , finding X and X ' such that
additional data . Because the combined data is coding-con H (X ) = H (x ') may be prohibitively difficult ( 700 ). However,
sistent with the integrity output of the original data , the for a chameleon hash CH , an device in possession of the key
overwrite of the original data may be performed in a secret 722 may be able to find X and X ' such that
non - tamper -evident manner, at least with regard to the CH ( X ) = CH ( X ') ( 750 ).
integrity code . In other words, the rewrite may be non - 50 FIG . 7B shows an example rewrite to a blockchain 760
tamper -evident, even if replacing the original data with the using a collision . Blockchain 760 includes blocks 762 , 764 ,
replacement data alone would result in a tamper- evident 766 , and 768 . Block 766 includes integrity output 784 .
rewrite . As discussed below , dual-chain and multiple chain When two different blocks 766 , 770 with different content
blockchains may be used in some implementations. Accord produce the same integrity output 786 for an integrity code ,
ingly , rewriting a blockchain coding -consistently with a first 55 the blocks 766 , 770 are a collision for the integrity code
integrity code of the blockchain may not necessarily result (796 ). Block 766 may be replaced with block 770 and
in a fully non -tamper -evident rewrite . maintain coding- consistence with subsequent block 768
The replacement data may include completely rewritten because blocks 766 and 770 produce the same integrity
data ; an altered version of the original data , such as a output. However, if block 770 does not contain the proper
redacted version of the original data ; the original data with 60 integrity output ( e . g ., integrity output 784), block 770 will
additions; a complete deletion of the original data ; or other not be coding -consistent with block 764 . With access to the
data . key secret of an integrity code , a party is able to specify the
The techniques and architectures discussed herein allow integrity output present in block 770 (797 ). Accordingly,
rewrites to the content of a blockchain that may be imple - block 770 can be made coding - consistent with block 764 by
mented in services, such as decentralized services, that 65 including integrity output 784 (798 ). Block 770 is still
exploit blockchain -based technologies . Non -tamper - evi- coding -consistent with block 768 because Block 770 col
dent, validity preserving , or other type of rewrites to a lides with block 766 . Alternatively, if Block 770 is instead
US 9 ,967,088 B2
13 14
constructed to include integrity output 782 , the insertion of In some cases , PKE or other secure exchange schemes
Block 770 may be used to delete block 764 (799 ). With may be used by individually -untrusted parties to combine
integrity output 782, block 770 is coding-consistent with portions or shares of a key secret of the integrity code to
block 762 ( as its preceding block ) and block 768 ( as the generate a full key secret capable of non -tamper - evident
block immediately subsequent) . Accordingly, block 764 5 rewrites of a blockchain . In some cases secure exchange
may be removed from the blockchain with no evidence of toschemes may be used to ensure that third parties are unable
acquire the portions of the key secret by observing the
tamper.
In some real -world applications, an append -only ledger schemesexchange. Additionally or alternatively, secure exchange
may be used by individually untrusted parties to
for the majority of parties (to preserve security ) that allows 10 prevent other individually untrusted parties from acquiring
rewriting may be implemented . To implement the real -world multiple portions during an exchange . For example , in an
application , rewriting maybe constrained such that it may be unsecured exchange , once an individually untrusted party
performed by trusted parties or in defined circumstances. collects the portions from the other untrusted parties , the
Two examples of real-world applications are discussed collecting party irrevocably becomes a trusted party . How
below with regard to FIGS. 13 and 14 . 15 ever , in a secure exchange, such as how PKE is imple
In some cases, applications such as smart contracts or mented, an untrusted party may collect portions of the key
overlay applications may not necessarily work and scale if secret from the other untrusted parties without actually
learning
the blockchain may notbe edited in a validly -preserving or Accordingly the content of the collected individual portions .
non - tamper -evident fashion . A smart contract may include a , collecting portions of the key secret from other
individually untrusted parties does not necessarily result in
sequence of instructions, for example computational instruc - 2020 the collecting party becoming a trusted party . Thus, the
tions , that a party performs in exchange for compensation . individually untrusted parties may together makeup a trusted
Further, rewritable blockchains may provide support for party , but after expiration or other invalidation of a com
updates to the application that the blockchain is used to bined key , the individually untrusted parties return to their
secure. If a blockchain -based system is overhauled after separate untrusted status until they again agree to combine
inception , a rewritable blockchain may be used to rebuild the 25 their individual portions. In some cases, a combined key
blockchain to reflect to overhaul. may expire after a pre - determined period of time or after
Notation performing a pre -determined volume of rewrites . For
For a string x , its length may be denoted by Ixl; if X is a example , the combination process may specify a pre - deter
set, [ X may represent the number of elements in X . When mined expiration parameter which may delineate a number
x is chosen randomly in X , the selection may be denoted as 30 of rewrites, a number of blocks that may be rewritten , a
duration , a volume of data that may be altered , a specific
X4 $ X . When A is an algorithm , y < $ A (x ) may denote a listing of blocks that may be rewritten , one or more event
run of A on input x and output y ; if A is randomized , then occurrences, or a combination thereof.
y is a random variable and A ( x ; r ) may denote a run of Aon In other cases , the key may be combined in such a way
input x and randomness r. An algorithm A is a probabilistic that the parties working together can determine the addi
polynomial-time (PPT) if A is randomized and for any input 35 tional content used to perform a non - tamper- evident rewrite
x , re {0 , 1 } * . The computation of A (x ; r) may terminate in of the block . However , no single party necessarily collects a
after up to poly (1x1) steps . complete (but encrypted ) key such that no single party could
A security parametermay be denoted as KEN . A function determine the additional content on behalf of the other
V : N > [ 0 , 1 ] may be negligible within the security param - parties . Rather, each individually untrusted party within a
eter (or simply negligible ) if it vanishes faster than the 40 group that makes up a trusted party may calculate a portion
inverse of any polynomial in K , i. e . V ( K ) = K -0 (1). For a
random variable X , P [X = x ] may denote the probability that of the additional content (or perform some portion of the
processing ). An end result from the combined efforts of the
X takes on a particular value xEX (where X is the setwhere individually untrusted parties serves as the additional con
X is defined ). Given two ensembles X = { XK }KEN and tent to support the non - tamper-evident rewrite of a single
Y = { YxKEN , X = Y may denote that the two ensembles are 45 block . For any subsequent rewrites the individually
identically distributed , and X = c Y may denote that the two untrusted parties may cooperate again for each specific
ensembles are computationally indistinguishable , for block that is designated for rewriting by the group that
example , for a given scenario . makes up the trusted party .
Public -Key Encryption The individually untrusted partiesmay be different opera
A Public -Key Encryption (PKE ) scheme is a technique by 50 tors (e . g., entities, institutions , devices, or other parties ) with
which information may be exchanged publicly between two different operator profiles on a single system . Additionally or
or more parties without necessarily disclosing encryption alternatively, individually untrusted parties may be distrib
keys , key secrets , or other secrets publicly . Further , PKE uted over multiple systems. The individually untrusted par
may be achieved without necessarily requiring full disclo ties may store their respective portions of the key secret in
sure ofkey secrets or other secrets among the parties in the 55 different memory locations , which may have the same or
exchange . In an implementation , a PKE may be executed different security features . The individual memory locations
using a tuple of algorithms PKE = (KGen . Enc. Dec ) defined may be associated with individual ones of the individually
as follows: (1 ) The probabilistic algorithm KGen takes as an untrusted parties. For example , the memory locations may
input the security parameter KEN , and outputs a public / correspond to a storage device owned or maintained by the
secret key pair (pk , sk ). ( 2) The probabilistic algorithm Enc 60 larly , trustedones
respective of the individually untrusted parties. Simi
parties may maintain associated memory loca
takes as an input the public key pk , a message mEM , and tions. In some cases, the memory location may serve as an
implicit randomness PERle, and outputs a ciphertext c = Enc identifier (whole or in part ) of a party. For example ,memory
( pk , m ; p ). The set of all ciphertexts is denoted by C . ( 3 ) The location for a trusted party may be used to confirm that the
deterministic algorithm Dec takes as an input the secret key key secret is being controlled ( e . g ., access control, read/
sk and a ciphertext CEC and outputs m = Dec( sk , c ) which is 65 write control, or other control) by a proper trusted party . For
either equal to some message m e M or to an error example , a key secret may be rejected by the system if it is
symbol 1 . not accessed from a trusted memory location (e .g., a
US 9 ,967,088 B2
15 16
memory location used , indirectly controlled , maintained , or statements . In some implementations, a stricter schememay
owned by a trusted party ). Similarly , portions of key secret allow the prover to see proofs of possibly false statements ;
held by untrusted parties may be tied to specific memory see discussion below .
locations.
Example implementations thatmay be used to support the 5 Example Property 4 ( True- Simulation Extractability
techniques and architectures described above are described Let N / A = ( 1, P, V ) be NIZK for an NP relation R , with
below . For example , the implementations discussed below
may be used to construct chameleon hashes. However, other ciently-knowledge
zero simulator S = ( S1, S2), and let f be an effi
computable function . N / A satisfies true - simulation f
integrity codes may be used to non -tamper -evident block extractability ( f tSE for short ) if there exists a PPT extractor
chain rewrites . 10 E such that for all PPT adversaries A there is a negligible
Non -Interactive Zero -Knowledge function v : N > [0 , 1 ] such that
IfR : {0 , 1 } * x {0 , 1} > {0 , 1 } is an NP relation on pairs (x ,
y ), with corresponding language L := { y : 5xs.t. R (x , y )= 1 } , a
non - interactive argument for R may allow a prover P to zit $ E (T , y* , * * ) ]
convince a verifier V that a common element y belongs to 15 y* & Q ^ ( V (w , y*, 7 *) = 1 ) : (y*,7 *) < $ Aºt( , )(w ) s
the language L (where both P and V are modeled as PPT " V r* s.t. f( x* ) = 2* (R ( x * . v* ) = 0 ) .
algorithms). The prover P may be facilitated by knowing a (W , 7) + $ S1 ( 16 )
witness x for YEL . vík ).
Example Property 1 (Non - Interactive Argument) .
A non - interactive argument for an NP relation R is a tuple 20
of efficient algorithms N / A = (1, P, V ) specified as follows. where oracle O , takes as input pairs (x , y ) and returns the
04 $ I( 1" ): The probabilistic algorithm I takes as an input same as S , ( t , y :) as long as R ( x ;, y :) = 1 (and I otherwise ),
the security parameter KEN , a and outputs the public and is the set of all values y , asked to oracle O .
common reference string (CRS ) W . Note that in the above example property 4 the adversary
It < $ P ( w , x , y ): The probabilistic algorithm P takes as an 25 is only allowed to see simulated proof for true statements . A
input the CRS w and a pair x , y such thatI R ( x , y ) = 1 , and stronger variant ensures that simulation extractability holds
returns a proof for membership of yEL . even if the adversary is allowed to see simulated proofs for
d = V ( W , y, h ): The deterministic algorithm V takes as an possibly false statements. The latter property is also known
input the CRS w and a pair (y, ), and returns a decision under the name of robust NIZK .
bit dE {0 , 1} 30 As noted in tSE NIZK are significantly more efficient to
Non - interactive arguments may , in some cases , satisfy construct, indeed they can be generically obtained combin
three properties known as completeness, zero -knowledge , ing a NIZK (such as the Groth -Sahai NIZK ) with a CCA
and soundness, which are discussed below . The CRS may be secure PKE scheme.
used to facilitate non - interactive zero -knowledge condi Chameleon Hash Functions
tions. 35 A chameleon hash may include a cryptographic hash
The completeness property may establish that an honest function for which a device in possession of a key secret
prover (holding a valid witness x ) should be able to convince may compute collisions. Without the key secret, the chame
the verifier that yEL . leon hash may be designed to make it computationally
Example Property 2 (Completeness for Arguments ). impractical to find collisions. However, knowledge of the
Let N / A = (1, P, V ) be a non -interactive argument for an NP 40 key secret, for example , a cryptographic key, trapdoor
relation R . N / A may satisfy completeness if for all pairs (x , information or other secret , may allow for computationally
y ) such that R (x , y )= 1, there exists a negligible function v: practical generation of collisions for the hash function .
N > [0 , 1 ] such that Knowledge of the key secret may allow for collision deter
P [V (0 ,y, ) = 1: < $ P (W ,x,y);0 <- $ /(1K ]21 - v(K ). mination and generation for blocks containing at least some
45 arbitrary content .
Zero -Knowledge . Secret- Coin Chameleon Hashing
The zero -knowledge property indicates that a possibly Example Property 5 (Secret- Coin Chameleon Hash ).
malicious verifier may not necessarily acquire knowledge of secret-coin chameleon hash function is a tuple of
a witness that it could not acquire by itself. This may efficient algorithms CH = (HGen , Hash , HVer, HCol) speci
contribute to non - interactive zero -knowledge (NIZK ). 50 fied as follows.
Example Property 3 (Zero -Knowledge ). (hk , tk )< $ HGen (1k ): The probabilistic key generation
Let N / A = (1, P , V ) be a non - interactive argument for an NP algorithm HGen takes as an input the security param
relation R . N / A satisfies zero -knowledge if there exists a eter KEN , and outputs a public hash key hk and a key
PPT simulator S : = (S1, S2) such that for all adversaries A secret tk .
there is a negligible function v : N > [0 , 1 ] such that 55 (h , $ ) < $ Hash (hk , m ): The probabilistic hashing algo
rithm Hash takes as an input the hash key hk , a message
mEM , and implicit random coins rER hash , and outputs
= b ' .: b' + $ A (W , T,nb), 10 + $ P (w , x, y), 761 + $ S2(T, y ) ] 1 ]
a pair (h , 5 ) that consists of the hash output h and a
bir $ {0 , 1}, (x, y ) – $ A (W , T), (W , T $ S1(1k ) ] 2
-
check string .
uns 60 d =HVer?hk , m , (h , 5 )): The deterministic verification
algorithm HVer takes as an input a message mem , a
candidate hash output h , and a check string , and
Simulation Extractability . returns a bit d that equals 1 if (h , 5) is a valid hash / check
The soundness property indicates that it is hard for a pair for the message m ( otherwise d equals ( ) .
malicious prover to generate an accepting proof u for an 65 Ti< $ HCol(tk , (h , m , 5 ), m '): The probabilistic collision
element y£L . In some cases soundness may still hold even finding algorithm HCol takes as an input the trapdoor
if the malicious prover can access simulated proofs for true key tk , a valid tuple (h , m , $ ), and a new message
US 9, 967, 088 B2
17 18
m 'EM , and returns a new check string ' such that functions may, at least partially , address the key exposure
HVer (hk , m , (h , $ ))= HVer(hk , m ', (h , } ')) = 1. If (h , $) is problem because they use a trusted party to process identi
not a valid hash / check pair for message m then the ties .
algorithm returns I . Added Collision Resistance .
The hashing algorithm may be randomized , and, upon 5 An example of a collision for a secret-coin or public -coin
input some message m , it may produce a hash output h hash function is a tuple h , (m , $ ), ( m ', ') such that mum ' and
together with a check value & that helps verifying the correct (h , $ ) and (h , & ') are valid hash /check pairs for m and m '
computation of the hash given the public hash key. The (respectively ). For a chameleon hash function the following
random coins of the hashing algorithm are , however, secret. security property , which indicates that it should be hard to
A particular case is the one where the check value & consists find collisions for the hash function even given access to the
of the random coins used to generate h , as the hash com collision finding algorithm (returning collisions for adap
putation becomes deterministic once m and r are fixed ; we tively chosen hash outputs).
call such a chameleon hash function public -coin and we Example Property 8 ( Added Collision Resistance ).
define it formally below . In an example scenario , CH = (HGen , Hash , HVer, HCol)
19 may be a (secret-coin or public -coin ) chameleon hash func
Example Property 6 (Public -Coin Chameleon Hash ). tion . CH may satisfy the properties of added collision
A public -coin chameleon hash function is a collection of resistance if for all PPT breakers B , there exists a negligible
algorithms CH = (HGen , Hash , HVer, HCol) specified as in function v : N > [0 , 1 ] such that
Example Property 5, with the following differences: 20
The hashing algorithm Hash , upon input of the hash key
hk and message mEM , returns a pair ( h , r ), where HVer?hk,m (h,F ) = (h, (m , 5), (m ', 8 ) – $ Bºnk ik (-)(hk )
TER - denote the implicit random coins used to P |Her(hk , m ', (h , 6') = 1) :
generate the hash output. ^ m m ')^ (h € ) (hk, tk ) < $ HGen(1K)
The verification algorithm HVer, given as input the hash 25 vík ).
key hk , message m , and a pair (h , r ), returns 1 if and
only if Hash (m ; r)= h . where the set Q is the set of all hash outputs queried by B
Since the verification algorithm simply re- runs the hash to its oracle , and oracle Onk, tk is defined as follows: Upon
ing algorithm , some implementations may drop the verifi
cation algorithm from CH in the case of public -coin cha 30 HVer
input a collision query of the form ((h , m , $ ), m ') run
(hk , m , (h , 5 )): = d ; if d = 1 return the output of HCol( tk ,
meleon hashing . ( h , m , 5 ) , m '), otherwise return 1 . If B is not allowed to query
Example Property 7 (Correctness for Chameleon Hash oracle Onk, tko CH may be collision -resistant without neces
ing). sarily having added collision resistance.
Let CH =CHGen , Hash , HVer , HCol) be a (secret -coin or 35 Generic Transformation
public -coin ) chameleon hash function with message space Example chameleon hash functions that provide added
M . CH satisfies correctness if for all mEM there exists a collision resistance include
collision resistance hash functions based on the
include ha
negligible function v : N > [0 , 1 ] such that: Nyberg -Rueppel signature scheme. The security of these
example chameleon hash functions can be demonstrated
P [HVer?hk,m ,(1 ,3 ) = 1:(h ,£) $ Hash (hk,m ); 40 using a discrete logarithm assumption within in the “ generic
(hk,tk )< $ HGen( 1K )]21 -v(K ). group model.”
Virtually any chameleon hash may be used to produce a The example construction below is for a chameleon hash
public - coin collision -resistant chameleon hash . However, in based on Nyberg -Rueppel principles . Added collision resis
some cases , secret - coin chameleon hash functions can be tance may be achieved in a non -ad hoc fashion for a variety
used for the same applications as public -coin ones ones, inin 4545 of different complexity environments. The transformation
particular for constructing chameleon signatures and online ! may NIZK .
be based on a CPA -secure PKE scheme and with tSE
offline signatures . However for a secret -coin chameleon
hash the system may store the check value & ( instead of the Let CH = (HGen , Hash , HCol) be a public -coin chameleon
randomness r ) in order to verify a hash output. Further, and hash function ( with message space Mhash and randomness
the hash verification may not necessarily include re- comom 50 space Rhash ), let PKE = (KGen , Enc, Dec) be a PKE scheme
puting the hash . (with message space Rhash and randomness space Rpke ), and
Collision resistance may not necessarily be sufficient for let N / A = (I, P , V ) be a non -interactive argument system for
the language
some of the applications of chameleon hash . While the hash LCH = { (pk , c, hk , h , m ): 3 (r, Q s .t. h = Hash ( hk ,
function is collision - resistant, a party seeing a collision for 55 m ; ra c = Encípk , r ; 0 ). ( 1 ) An example secret- coin chame
the hash function may be able to find other collisions or leon hash function CH * = (HGen * Hash * . HVer* . HCol* )
recover the key secret. Added collision resistance , can be may be specified as follows:
used to make it more difficult to find collisions even after HGen * (1K ): Run (hk , tk )< - $ HGen ( 1K ), (pk , sk )< - $
witnessing polynomially -many collisions. KGen (1 % ), and w < $ I(1K ). Return the pair (hk * , tk * ),
Another type of chameleon hashing may include 60 such that hk * := (hk , w , pk ), and tk * := ( tk , sk ).
“ labeled ” hash functions , where the hash algorithm takes as Hash * (hk * , m ): Sample a random value rER hash and run
input an additional value A called the label or tag . In some Hash (hk , m ; r ): = h . Sample a random value pERte and
cases, labeled hash functions may be resistant to key expo runc: = Enc (pk , r; q . Compute the proof t < $ Pw, x , y ),
sure. For example , for some labeled hash functions it is where x : = (r, Q and y: = {pk , c, hk , h , m ), and return (h ,
unfeasible for a system to find collisions for a “ fresh ” label 65 5 ) such that & : = (c , ).
2 * , even given access to an oracle that outputs collisions for HVer* (hk * , m , (h , $ )): Parse & = (c, t ) and return the output
other arbitrary labels 2 = . Identity -based chameleon hash of V (w , y, it ) where y = (pk , c, hk , h , m ).
US 9 ,967,088 B2
19 20
HCol* (tk * , (h , m , 5 ), m '): First run HVer?hk * , m , (h , redacted , a set of indices that represents the positions in the
$ )): = d ; if d = 0 then output I , otherwise , decrypt the chain C ) of the blocks that are being redacted , and another
randomness r:= Dec(sk , c ), compute a collision ris $ set containing the new x ” s values for the individual blocks
HCol(tk , (h , m , r ), m '), sample a random p'ER pke and that are being redacted . The example algorithm may accept
encrypt the new randomness c ': = Enc ( pk , r'; p '). Com - 5 chameleon hash trapdoor key tk as an input. The algorithm
pute the proof It's $ P ( w , x ', y'), such that x ' = (r', p ') and intuition is that for each block to be redacted we compute a
y ': = (pk, c', hk , h , m '), and return E := (c', It'). collision for the hash of the block with its new content x '. A
The system may be implemented using various protocols . new chain C ' is created by replacing the original block with
For example , public -coin chameleon hash function based its modified
system may implement Sigma-protocols . A Sigma-protocol 10 Algorithm 1 , counterpart . At the end of the execution of
is an interactive proving scheme, in which the “ prover ” and redacted chain as a specialauthority
the central
chain ,
may broadcast the new
such that the users of the
the “ verifier” engage in a multiple - stage communication .
During the multiple - stage communication , the prover may system adopt the new redacted chain in favor of other chains
convince the verifier that prover is in possession of specific even , for example, longer ones.
information . To achieve tSE NIZK , a CCA - secure PKE 15
NIZK argument system may be used . An encryption scheme Algorithm 1: Chain Redaction
is CCA - secure when it is secure against a pre - defined
ciphertext attack . input: The input chain C of length n , a set of block indices I = [n ],
Example Blockchain a set of x's values { x';}iel, and the chameleon hash
trapdoor key tk .
In an example scenario , a block is a triple of the form 20 output stout.: The redacted chain C of length n .
B = (s , x , ctr ), where se {0 , N 1 } \ , XE {0 , 1 } * and ctr e N . C 'EC;
Where B is valid if: Parse the chain C ' as (B1, ... , Bn );
for i := 1 to n do
| if i E I then
validblock ,” (B ): = (H (ctr,G (s,x )) < D )^ (ctr < q) = 1 . 1 | Parse the i-th block of C ' as B ; := { (Si, X?, ctr?, (h;, $;)) ;
Where H : {0 , 1} * > {0 , 1} K and G : {0 , 1 }* > {0 , 1 } K are 25 |! |! &B = ( HCol (tk, (h;, Sio || x;, $:), ( ; || x;'));
s , x,,ctr?, ( h , $ )) ;
collision resistant hash functions and the parameters
DEN and qEN are the block ' s difficulty level and the Iloco
| end
| B ; 11. C';
maximum number of hash queries that a user is allowed to end
make within a round of the protocol, respectively . return C '
The example blockchain , C , may be a chain (or sequence ) 30
of blocks. In the example , the rightmost block is the head of
the chain , denoted by Head ( C ). Any chain C with a head In some cases, collision resistant chameleon hash func
Head( C ) := (s, x , ctr ) can be extended to a new longer chain tions may be susceptible to key exposure . For example, for
some collision resistant chameleon hash functions it may be
C ': = C ||B ' by attaching a ( valid ) block B ':= (s', x ', ctr ') such possible
that s'= H ( ctr , G (s, x )); the head of the new chain Cci' isis 3535 possib to retrieve the key secret after seeing collisions for
Head (C ')= B '. A chain C can also be empty , and denoted as the function . Note that both algorithms presented ( Algo
rithm 1 and 2 ) may expose one or more collisions for a
C = E . The function len (C ) denotes the length (number of redaction . For example , an algorithm may expose a collision
blocks ) of a chain C . For a chain C of length n and for redaction or for each block changed or redacted . In some
any k20 , ( \* is the chain resulting from removing the k 40 cases, a system may implement a chameleon hash with
rightmost blocks of C . and analogously hlc is the chain added collision resistance to avoid key exposure . However,
resulting in removing the k leftmost blocks of C , if k?n some systems
trolled levels ofmay rely onexposure
collision collision
. resistance and con
then C '* = E and C = E . If C is a prefix of C ', it may be In some cases, a trusted party may remove entire blocks
denoted Cx C '. Further, the difficulty level D may differ 45 from a rewritable blockchain . For example , a use case may
among blocks in a chain . be scalability maintenance , such as saving disk space and
Example Rewritable Blockchain computational power relative to what may be used to handle
In an example rewritable blockchain scenario for the larger (unredacted ) chains. To remove the block Bi, the
example blockchain above , a block may be a tuple B := { S, X , block Bit1 may be altered by assigning Si+ 1684. The system
ctr, (h , $ )) , the new component ( h , 3 ) may be a hash /check 50 may then compute a collision for B . , that produces the new
pair for a secret- coin chameleon hash . The function G may block B 'in which may be inserted in the chain in place of
be a secret- coin chameleon hash CH = (HGen , Hash , HVer, block B , 11 , which leaves the chain in a coding- consistent
HCol) . The validation predicate for this modified block may state . At the end of the execution of Algorithm 2 , the central
be: authority may broadcast the new shrunken chain as a special
55 chain , such that the users of the system adopt the new
validblock P (B ): = (H (ctr,h )< D ) ^ (HVer(hk ,(s,x ),(h , redacted chain in favor of other chains.
$))) ^ ( ctr < q) = 1.
The domain of the chameleon hash may be adjusted , for
example , to a size commensurate to the application of the Algorithm 2: Chain Shrinking
blockchain by hashing the input of the argument, Hash , with 60 input: The input chain C of length n , a set of block indices I = [n ]
a regular collision resistant hash of the desired output size . and the chameleon hash trapdoor key tk .
The verification of a chameleon hash may be computed output: The new chain C ' of length n - III.
C 'EC;
using its own verification function (HVer). However, some Parse
hash functions, such as those without key secrets , may be for i: = the1 tochainn doC as (B1, ... , B . );
verified by precomputing the hash . 65 if i E I then
In some cases, a chain redacting algorithm , such as I Parse the i-th block of C' as B ; := { s?, X;, ctr ;, (h ;, &;)) ;
example algorithm 1, may take as an input: a chain C to be
US 9 , 967, 088 B2
21 22
-continued some cases, the users may broadcast the new chain as a new
special chain . In some implementations , rewrites to the
Algorithm 2 : Chain Shrinking blockchain may occur infrequently . Use of special chain
I L Parse the i + 1-th block of C ' as broadcasts may not necessarily cause frequent disruption .
B1: = S +1, +1, ctv1 , ( h -1, 51) ; 5 However , special and non -special transmissions may be
|
-
| Siti's HCol (tk , (h ;+ 1, Sit1 || Xi+1, $i+1), (s; || X;+ 1)); used in various implementations .
1 Biti' := { S?, Xj+1, ctri+19 (hi+ 1, Sit1')) ; An example choice for the set U would be to pick a subset
-
I C ' CF|| B :1,'|'*" C';
end
of users that are online . However, this choice can be
end
dependent on the application . We also deal with the issue
return C ' 10 where some users in U are in factmalicious, and their goal
is to learn tk or to prevent its correct reconstruction .
Concrete Instantiations
Decentralized Key Secret Exchange In some example implementations, chameleon hash (CH )
In some implementations, a candidate trusted authority constructions that are described in : Giuseppe Ateniese and
may be apparent. For example , in some financial interac - 15 Breno de Medeiros, “ On the key exposure problem in
tions, a bank or bank official may hold a key secret for the chameleon hashes” , SCN , pages 165 - 179, 2004 may be used
integrity code , such as a chameleon hash . In some cases, by the system . As discussed above , an example CH con
peer -to - peer applications may not necessarily have such a struction that may be implemented has a twin Nyberg
clear candidate trusted party . This situation may be Rueppel signature along with added collision resistance , for
addressed by using a decentralized key secret distribution 20 example a CH that exhibits example property 8 . The param
scheme. In this case , the trapdoor key may not necessarily be eters for the function may include a random prime q and
known by any individual party , but rather be shared among p = 2q + 1. The parameters may further include a generator g
some fixed set of users, such that the users together makeup of the subgroup of quadratic residues of Z *py,, and a
the trusted party . When a block needs to be redacted , the collision resistant hash function H .
users from this set engage in a secure multiparty computa - 25 (hk , tk ) < $ HGen ( 1 ) : The key secret is a random value
tion protocol (MPC ) to compute Algorithm 1 . tkE [1, 4 - 1], and the hash key is hkgk.
In some cases, secure key exchanges, such as MPCs,may h := Hash ( m , r, s ): To hash a message mEM with random
operate by having the parties send a start signal. In some values (r, S)EZ XZq compute and return
cases , some parties may be honest or dishonest. Honest h : = r - hkH (m , ') gå mod p ) mod q . Z
parties may aim to work with the other parties to access the 30 { 0 , 1 ] := HVer (h , m , r, s): To verify just return Hash (m , r,
complete key secret . However, dishonest parties may wish to S) = h .
disrupt the process by sending false shares . Nevertheless, the (r', s')< $ HCol(h , m , r, s, m '): To compute a collision for
secure key exchange still may involve receiving shares with message m ', pick a random kE [ 1, 4 - 1), computer'<- h +
both honest and dishonest parties. After receiving the “ start” (g* mod p ) mod q , and compute s'<- k - H (m ', r') tk mod
signal from all honest parties , a system may run (hk , tk )< $ 35 q . Return (r', s ').
HGen ( 1 % ) and send hk to the dishonest party . Accordingly , Semi-Honest Scenario .
the individualparties in the exchange P ; may receive shares . In an example scenario , the users in subgroup U are
The system may construct a complete set of shares semi-trusted . In this scenario , the semi-honest users in
( S , . . . , , ) from honest parties because the shares sent by subgroup U may be trusted to execute the protocol and
the dishonest parties may constitute an unqualified set. 40 behave according to the rules, for example , the users in
Once, a complete set is formed , the system may send s; to subgroup U may be relied upon to input the correct shares .
each honest party . For this semi- honest scenario , a n -threshold key secret
The system may receive the shares s ; from each party P . sharing scheme based on sums is described below :
and reconstruct the trapdoor key tk : = Rec (si, . . . , Sn ). The Sharing Phase :
shares of the dishonest parties are chosen by the dishonest 45 The dealer chooses a secret s and n shares s; such that
party . Upon receiving a “ compute collision ” signal for the
pair ((h , m , 5 ), m ') from all honest parties, compute
E '< HCol(tk , (h , m , 5 ), m ') and send ( h , m , $ ) and Et to the s = Si.
dishonest party . Upon receiving an “ OK ” signal from the I
dishonest party , the system may forward the value to all 50
honest parties . However, if an “ OK ” is not received , the
system may forward I (e.g., a runtime failure indicator) to The n parties P ; receive their respective key secret shares
all honest parties .
In an example scenario , an example system may include Reconstruction Phase :
n active users. A subset UE [n ] of users may hold a share of 55 The dealer receives from the parties Pi a share s; and
the trapdoor key tk . The subset U of users may execute a reconstructs the key secret
decentralized key generation protocol. At the end of the run ,
users in the subset U get a share si of tk . When a block
B2:= ' s , x , ctr, (h , $ ) is redacted into the modified S =
block By: ( s, x , ctr , (h , 5 )) the users may inspect their own 60
blockchains and find block Br. The users in the subset may
then execute the distributed hash collision protocol to com
pute the value & . The usersmay input their own private share In the example scenario , the users u e U individually
S ; of tk , the values s , x , h , & and X . At the end of the protocol, choose a random x , E [ 1 , 9 - 1 ] as their respective key secret
the users in subset U receive the value & of block Bk . The 65 shares and broadcast the value yixgt . The hash trapdoor
users may update their own blockchain by replacing block key may be tk - X = 1" X ; x; mod q, and the hash key may be
Bx with block B , and broadcast this new rewritten chain . In hk gtk . This protocol may be non - interactive because it
US 9 ,967,088 B2
23 24
may not necessarily require any exchange of messages Structure at the Block Level
among the users . Further, no set of n - 1 users may neces FIG . 8 shows an example blockchain portion 800 paired
sarily be able reconstruct tk . Further, the system may frus - with an example updated blockchain portion 850. In the
trate attempts to learn information about tk because the example , blockchain portions 800, 850 an outer hash H is
shares are just random elements . 5 paired with an inner hash G . The inner hash may be nested
In the example scenario , the users UEU may agree on a within the outer hash such that the output of the inner hash
pair ( h , m , r, s ), m '). The users individually choose a is provided to the outer hash as an input. In the example ,
respective random k , E , 9 - 1 ] , broadcast g " , and later blockchain portion , the inner hash G may be a chameleon
compute r ' < h + ( II:_ , " gkimod p ) mod q . In some cases , the hash function . The outer hash H may be a chameleon hash
systems of the individual users may compute h ' H ( m ', r ) 10 function or another hash function . The blocks may include
without necessarily receiving additional input from the other a HashPrev ( e.g . previous hash ) 802 field which may include
users in the subgroup . To compute s ' the users may execute a store for holding the hash output corresponding to the
a MPC protocol to compute the multiplication s' < h '.tk by previous block , for example s, s', s" . The blocks 820, 822 ,
inputting the users respective shares of tk . The user may 832 , 834 may not necessarily include a hash output of their
execute an additional and another MPC protocol to compute 15 own input. However, the hash output for the blocks is shown
the difference s'ék- s" by inputting the previously chosen above the block to demonstrate the linkage 803 to the next
shares of k . block ( e .g ., the linkage 803 between block 832 and 820 and
Dishonest Scenario . between 820 and 834 ). The blocks 820 , 822 , 832 , 834 may
Additionally or alternatively, an example scenario may further include a Payload 804 field which may hold data
include some users, entities, parties, devices , or other enti- 20 (e. g ., X , X ', X " ) secured within the block , such as, transaction
ties , that may be dishonest. For example , dishonest users information , smart contract content, numerical values , cur
may deviate from a protocol specification to attempt to learn rency denominations, or other secured data .
other users ' key secret shares. To maintain security in such counter field 806 may also be included , for example ctr,
scenario robust secret sharing schemes may be implemented ctr ', ctr" . The counter field 806 may include a counter or
for key secret sharing . In some cases, robust secret sharing 25 nonce that may be used for proof of work (PoW ) compu
may support a threshold number ( e .g ., an integer t< n ) of tation , accounting, block tracking , or other purposes . In
users that may be dishonest. A user executing a robust secret cryptocurrency implementations, PoW may be used to
sharing may reconstruct the correct key secret from the verify the validity of a currency award to a particular party .
given shares even if (up to the threshold number of users are PoW may include solutions to computational problems
dishonest. A robust secret sharing scheme may be imple - 30 where the solutions a computationally complex to derive ,
mented using a Shamir secret sharing scheme plus Reed - but comparatively computationally simple to verify. PoW
Solomon (RS ) error correcting code . In the key secret may also be used in smart contracts to verify that a particular
reconstruction phase , the RS codes are used in each share party has completed their obligations under the contract.
before reconstructing the key secret. In some cases, a Shamir The Randomness 808 field may be updated when the
secret sharing scheme paired with RS error correction may 35 block is redacted , for example , when a collision is com
operate with up to one third of the users being actively puted . In some cases the Randomness field may hold the
dishonest. In some example schemes , any dishonest user third data , ( e . g ., r , r', r " ) that may be paired with the
threshold may be supported , for example , this may include replacement data to allow a non -tamper- evident rewrite to
a threshold that allows just short of a majority of users to be the blockchain . When a block 820 is redacted , the values s',
dishonest. 40 x ', ctr', and r'may be replaced by s', * x ', ctr', and * r'. In the
The users in the subgroup may chose a respective random example scenario , s' and ctr may notnecessarily be modified
string p ; E and parses it as p ;:= tk ;||p1||| 22 ||. . ||p;" , so that the since ctr 'may be used by the outer hash to compute the PoW
subgroup may agree on a polynomial P ( X ). The polynomial and is the link to the previous block that remains the same.
may be defined as P ( X ): = k + P X + P X² + . . . + P - X - , Using a chameleon hash key secret for the inner hash
with P (i): = & j= 1" pi and P (0 ):= & iflmtk?. To distribute the 45 function G , it may be possible to find a collision such that
shares, the users may execute a MPC protocol to compute G (s ', x ', and r') = G ( s', * x ', and * r'). Accordingly , H (ctr', G (s',
the shares of each user i. For a user i, the corresponding x ', and r')) = H ( ctr', G (s', * x ', and * r') ). As a result s" may
share maybe the sum P (i): = :- " p . In the reconstruction remain unchanged through redaction . The updated block
phase , the shares of the users may be decoded using RS portion 850 includes the replacement block 822 with values
codes. 50 * x ' and * r'.
In some implementations, sharing schemes such as those In some implementations, the system may delete a block
described in Tal Rabin and Michael Ben -Or, “ Verifiable by replacing S; + 1 with s ; in Block , and then running the
secret sharing and multiparty protocols with honest majority redaction process on Block ; 11 . Additionally or alternatively ,
( extended abstract)” , ACM STOC , pages 73- 85 , 1989 may the system may delete a block by making the value Si+ 1 in
be used . For example , sharing schemes discussed therein 55 Blocki+1 point to Blocki- 1. In some cases, the ctr value in
may use a broadcast channel and be capable of successful Block :- , may be changed to maintain coding -consistency
operation where a majority of parties are honest. with the updated value Si + 1 in Block + 1.
Further, some implementations , may use schemes such Multiple Chain Blockchain
those with an optimizable share size described in : Allison In some implementations, a trusted entity may perform a
Bishop , Valerio Pastro , Rajmohan Rajaraman , and Daniel 60 redaction that may be concealed and users may be unaware
Wichs, “ Essentially optimal robust secret sharing with maxi- that a new blockchain has replaced the original blockchain .
mal corruptions ” IACR Cryptology ePrint Archive, 2015 : That is , users may not necessarily be able to detect whether
1032 , 2015 may be used . For example , sharing schemes parts of the blockchain were redacted or not unless old
discussed therein may have corruption settings that lack copies of the blockchain could be restored .
linear dependence between the share size and the number of 65 However, in some implementations, it may be advanta
parties, n . In some cases , the share size may grow linear with geous to make redactions evident. For example , tamper
k , where 2 - k is the probability of failure . evident redactions may be advantageous in systems where
US 9 ,967,088 B2
25 26
redactions are audited , where previous agreement calls for 902 . However, the write -locked link 906 , or other link for
evidence when redactions are performed , or in other cases which the trusted party lacks the key , may be broken to
when evidence of redaction is advantageous or otherwise signal that a redaction took place . Referring to 950 , the old
preferable . In systems that are redaction evident, content block B2 902 , with possibly sensitive information may be
removal or modification may leave a rewrite identifier or 5 removed , but the broken link 956 acts as an indelible mark
“ scar ” (e . g ., a rewrite artifact) that may not necessarily be or scar that provides a persistent record that a redaction to
removable by anyone including the trusted parties . How - produce new block B2' 952 took place .
ever, in some implementations, the scar may be removable Multiple chain blockchains may also be used to generate
by a subset of the trusted parties or through coordination of a hybrid blockchain with non - rewriteable blockchain space
multiple parties, as discussed below . 10 paired with rewritable blockchain space . For example , a
In some redaction evident implementations, a single system may secure a first of each block in of a set of blocks
blockchain may include chains, one based on the write in a blockchain with an integrity code that lacks a key secret.
locked chain , e. g ., a hash function that lacks a key secret or Accordingly , any attempt by any party to rewrite these parts
a hash function for which the key secret is unknown , and one of the blocks would be tamper evident. The example system
based on a rewritable blockchain , e .g ., a chameleon hash . If 15 may secure remaining parts of the blocks with an integrity
in both chains the write -locked and rewritable chains are code that supports rewrites by trusted parties. These rewrit
intact, then there was no redaction and the blocks are able portions could be altered by trusted parties without
original. If the write -locked chain is broken and the chame- generating evidence of tamper. Accordingly, a hybrid block
leon chain is intact, then there was a redaction by a trusted chain may be used by operators to generate a blockchain
entity . However , if the rewritable chain is broken , then there 20 system with immutable core data that is paired with tertiary
was an edit to the blockchain by an untrusted entity and the data that may be rewritten by a limited number of trusted
blockchain may be invalidated . In some cases , if the rewrit parties .
able chain is broken , the blockchain may be invalidated FIG . 10 shows an example hybrid blockchain 1000 . The
regardless of the state of the write -locked chain . Accord hybrid blockchain 1000 includes blocks 1010 , 1020 , 1030 ,
ingly , in such cases, the integrity of the blockchain is 25 1040 with a core 1002 part and a tertiary part 1004 . The
ensured by the chameleon chain while the write - lock chain block portions 1012 , 1022, 1032 , 1042 making up the core
acts as a detection mechanism . Thus, in blockchains sup - part 1002 are secured by a core integrity code 1006 which
porting rewrites with scar evidence , the validity of the may not necessarily support non -tamper - evident rewrites by
blockchain is logically separated from the creation of a any party. Conversely , the block portions 1014 , 1024 , 1034 ,
record of tamper. 30 1044 making up the tertiary parts 1004 of the blocks 1010 ,
In some implementations , multiple chains may be used to 1020 , 1030 , 1040 may be secured by a tertiary integrity code
differentiate among different trusted entities. Accordingly , 1008 that supports non - tamper -evident rewrites.
multiple rewriteable chains may be included in a blockchain In various implementations, the core 1006 and tertiary
along with zero or more write -locked chains. In a multiple - 1008 integrity codes may themselves implement multiple
trusted entity tracking blockchain , the chain corresponding 35 chains. For example , the core integrity code 1006 or the
to the trusted entity thatmade the redaction will be unbroken tertiary integrity code 1008 may support scarring, as dis
while other chains, include chains corresponding to other cussed above , such that valid rewrites may be performed on
trusted entities or write - locked chains may be broken . In the parts 1002 , 1004, but those changes still generate evi
some implementations , the inclusion of multiple rewritable dence of tampering despite being valid . Additionally or
chains provides the tamper scar or rewrite identifier without 40 alternatively , the core 1006 and tertiary 1008 integrity codes
an accompanying write - locked chain since only the chain may support multiple- trusted -party ratification, or require
corresponding to the trusted entity thatmade the edit may be different numbers of key secret portions to support editing .
left unbroken , while the other chains , although rewritable by For example , edits to the core parts 1002 may depend on
other trusted entities ,may be broken as a result of the edit. ratification by two trusted parties to perform a non - tamper
In some cases , a scar may be later removed when another 45 evident rewrite , while non -tamper -evident edits to the ter
trusted entity or entities in possession of the key to one or tiary portion may be performed by a single trusted party . For
more of the other chains ratifies the edits made by the earlier distributed key secret systems, an example system may
trusted party . This may protect the blockchain from untrace allow a non - tamper -evident rewrite to the tertiary part 1004
able unilateral edits by one trusted party , but still allow a using M portions of the key secret, while only allowing
single trusted party to remove sensitive information